-
作者：Banerjee, Imon; Honnappa, Harsha; Rao, Vinayak
作者单位：Northwestern University; Purdue University System; Purdue University; Purdue University System; Purdue University
摘要：In this work, we study a natural nonparametric estimator of the transition probability matrices of a finite controlled Markov chain. We consider an off-line setting with a fixed data set of size m, collected using a so-called logging policy. We develop sample complexity bounds for the estimator and establish conditions for minimaxity. Our statistical bounds depend on the logging policy through its mixing properties. We show that achieving a particular statistical risk bound involves a subtle a...
-
作者：Charlet, Nils; Van Houdt, Benny
作者单位：University of Antwerp
摘要：Recently it was shown that the response time of first-come-first-served (FCFS) scheduling can be stochastically and asymptotically improved upon by the Nudge scheduling algorithm in case of light-tailed job size distributions. Such improvements are feasible even when the jobs are partitioned into two types, and the scheduler only has information about the type of incoming jobs (but not their size). In this paper, we introduce Nudge*(M) scheduling, where basically any incoming type 1 job is all...
-
作者：Li, Zihao; Wang, Hao; Yan, Zhenzhen
作者单位：National University of Singapore; Chinese Academy of Sciences; University of Science & Technology of China, CAS; Nanyang Technological University; Nanyang Technological University
摘要：We study a fully online matching problem with general stochastic arrivals and departures. In this model, each online arrival follows a known identical and independent distribution over a fixed set of agent types. Its sojourn time is unknown in advance and follows type-specific distributions with known expectations. The goal is to maximize the weighted reward from successful matches. To solve this problem, we propose a linear program (LP)-based algorithm whose competitive ratio is lower bounded...
-
作者：Correa, Jose; Cristi, Andres; Norouzi-Fard, Ashkan; Norouzi-Fard, Ashkan
作者单位：Universidad de Chile; Alphabet Inc.; Google Incorporated
摘要：There is growing awareness and concern about fairness in machine learning and algorithm design. This is particularly true in online selection problems, where decisions are often biased: for example, when assessing credit risks or hiring staff. We address the issues of fairness and bias in online selection by studying multicolor versions of the classic secretary and prophet problems. In the multicolor secretary problem, we consider that each candidate has a color, and we can only compare candid...
-
作者：Chen, Xi; Lyu, Jiameng; Zhang, Xuan; Zhou, Yuan
作者单位：New York University; Fudan University; University of Illinois System; University of Illinois Urbana-Champaign; Tsinghua University
摘要：Price discrimination, which refers to the strategy of setting different prices for different customer groups, has been widely used in online retailing. Although it helps boost the collected revenue for online retailers, it might create serious concerns about fairness, which even violates regulations and laws. This paper studies the problem of dynamic discriminatory pricing under a relative price fairness constraint in the pricing literature. We first establish a regret lower bound of ohm(T4=5)...
-
作者：Simchi-Levi, David; Xu, Yunzong; Zhao, Jinglong
作者单位：Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); University of Illinois System; University of Illinois Urbana-Champaign; Boston University
摘要：This paper studies the impact of limited switches on resource-constrained dynamic pricing with demand learning. We focus on the classical price-based blind network revenue management problem and extend our results to the bandits with knapsacks problem. In both settings, a decision maker faces stochastic and distributionally unknown demand, and must allocate finite initial inventory across multiple resources over time. In addition to standard resource constraints, we impose a switching constrai...
-
作者：Ba, Wenjia; Lin, Tianyi; Zhang, Jiawei; Zhou, Zhengyuan
作者单位：University of British Columbia; Columbia University; New York University
摘要：We consider online no-regret learning in unknown games with bandit feedback, where each player can only observe its reward at each time-determined by all players' current joint action-rather than its gradient. We focus on the class of smooth and strongly monotone games and study optimal no-regret learning therein. Leveraging self-concordant barrier functions, we first construct a new bandit learning algorithm and show that it root ffiffiffi achieves the single-agent optimal regret of Theta ( n...
-
作者：Jia, Su; Li, Andrew; Ravi, R.; Oli, Nishant; Duff, Paul; Anderson, Ian
作者单位：Amazon.com; Carnegie Mellon University
摘要：Modern platforms leverage randomized experiments to make informed decisions from a given set of items (treatment arms). As a particularly challenging scenario, these items can (i) arrive in a high volume, with thousands of new items being released per hour, and (ii) have a short lifetime due to their transient nature. We study a Bayesian multiple-play bandit problem that encapsulates the key features of this scenario. In each round, a set of arms arrives. Each arm has a lifetime w and an unkno...
-
作者：Jiang, Songchen; Li, Zhaolin; Bi, Sheng; Teo, Chung-Piaw; Huang, Min
作者单位：Northeastern University - China; National University of Singapore; University of Sydney; Shanghai University of Finance & Economics
摘要：We generalize Scarf's classical min-max newsvendor model from a singleperiod setting to a multiperiod inventory system with independent demand across periods. This extension leverages mean-variance analysis to capture the dynamic effects of lead times, yielding closed-form expressions for the optimal base-stock level. As a concrete application, we study a single-product, dual-sourcing system with constant lead times and backlogging. We show that the optimal tailored base-surge policy admits a ...
-
作者：Wang, Tong; Xiao, Li; Xu, Fen
作者单位：City University of Hong Kong; University of Macau; Huazhong University of Science & Technology
摘要：This paper establishes two new preservation results of multimodularity for two classes of resource allocation problems, where multiple resources can be used to satisfy multiple demands. Our results show that if allocation priorities between multiple resources and demands are determined by several marginal cost/value inequalities of the objective function, then the multimodularity and marginal cost/value inequalities are both preserved after optimization. We demonstrate their applications to se...
