Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits
arXiv:1504.06937
Abstract
We study contextual bandits with budget and time constraints, referred to as constrained contextual bandits.The time and budget constraints significantly complicate the exploration and exploitation tradeoff because they introduce complex coupling among contexts over time.Such coupling effects make it difficult to obtain oracle solutions that assume known statistics of bandits. To gain insight, we first study unit-cost systems with known context distribution. When the expected rewards are known, we develop an approximation of the oracle, referred to Adaptive-Linear-Programming (ALP), which achieves near-optimality and only requires the ordering of expected rewards. With these highly desirable features, we then combine ALP with the upper-confidence-bound (UCB) method in the general case where the expected rewards are unknown {\it a priori}. We show that the proposed UCB-ALP algorithm achieves logarithmic regret except for certain boundary cases. Further, we design algorithms and obtain similar regret analysis results for more general systems with unknown context distribution and heterogeneous costs. To the best of our knowledge, this is the first work that shows how to achieve logarithmic regret in constrained contextual bandits. Moreover, this work also sheds light on the study of computationally efficient algorithms for general constrained contextual bandits.
36 pages, 4 figures; accepted by the 29th Annual Conference on Neural Information Processing Systems (NIPS), Montréal, Canada, Dec. 2015
References in corpus (5)
Cited by in corpus (22)
- Uniformly bounded regret in the multi-secretary problem
- Linear Contextual Bandits with Knapsacks
- An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
- Linear Stochastic Bandits Under Safety Constraints
- Online Linear Programming: Dual Convergence, New Algorithms, and Regret Bounds
- Achieving Fairness in the Stochastic Multi-armed Bandit Problem
- An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints
- Stochastic Contextual Bandits with Known Reward Functions
- Online Allocation and Pricing: Constant Regret via Bellman Inequalities
- The Online Saddle Point Problem and Online Convex Optimization with Knapsacks
- Restless Bandits with Many Arms: Beating the Central Limit Theorem
- Logarithmic regret bounds for Bandits with Knapsacks
- Beyond the Click-Through Rate: Web Link Selection with Multi-level Feedback
- Bandit Algorithms for Precision Medicine
- Group Fairness in Bandit Arm Selection
- Logarithmic regret in the dynamic and stochastic knapsack problem with equal rewards
- Asynchronous Optimization over Weakly Coupled Renewal Systems
- Matching while Learning
- Bandits with Knapsacks beyond the Worst-Case
- The Survival Bandit Problem
- Learning Adaptive Display Exposure for Real-Time Advertising
- Price of Safety in Linear Best Arm Identification