Bandits with Knapsacks beyond the Worst-Case
arXiv:2002.00253
Abstract
Bandits with Knapsacks (BwK) is a general model for multi-armed bandits under supply/budget constraints. While worst-case regret bounds for BwK are well-understood, we present three results that go beyond the worst-case perspective. First, we provide upper and lower bounds which amount to a full characterization for logarithmic, instance-dependent regret rates. Second, we consider "simple regret" in BwK, which tracks algorithm's performance in a given round, and prove that it is small in all but a few rounds. Third, we provide a general "reduction" from BwK to bandits which takes advantage of some known helpful structure, and apply this reduction to combinatorial semi-bandits, linear contextual bandits, and multinomial-logit bandits. Our results build on the BwK algorithm from \citet{AgrawalDevanur-ec14}, providing new analyses thereof.
arXiv commentThe initial version, titled "Advances in Bandits with Knapsacks", was published on arxiv.org in Jan'20. The present version improves both upper and lower bounds, deriving Theorem 3.2(ii) and Theorem 4.2. Moreover, it simplifies the algorithm and analysis in the main result, and fixes several issues in the lower bounds
References in corpus (14)
- A Contextual-Bandit Approach to Personalized News Article Recommendation
- Tight Regret Bounds for Stochastic Combinatorial Semi-Bandits
- A Finite-Time Analysis of Multi-armed Bandits Problems with Kullback-Leibler Divergences
- Knapsack based Optimal Policies for Budget-Limited Multi-Armed Bandits
- Matroid Bandits: Fast Combinatorial Optimization with Learning
- Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits
- Linear Contextual Bandits with Knapsacks
- Efficient Learning in Large-Scale Combinatorial Semi-Bandits
- An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
- Combinatorial Semi-Bandits with Knapsacks
- Dynamic Ad Allocation: Bandits with Budgets
- Assortment Optimization under Unknown MultiNomial Logit Choice Models
- Logarithmic regret bounds for Bandits with Knapsacks
- Online Learning with Vector Costs and Bandits with Knapsacks