Improved Algorithms for Multi-period Multi-class Packing Problems with Bandit Feedback
Not on the map. Why?
Abstract (arXiv)
We consider the linear contextual multi-class multi-period packing problem (LMMP) where the goal is to pack items such that the total vector of consumption is below a given budget vector and the total value is as large as possible. We consider the setting where the reward and the consumption vector associated with each action is a class-dependent linear function of the context, and the decision-maker receives bandit feedback. LMMP includes linear contextual bandits with knapsacks and online revenue management as special cases. We establish a new estimator which guarantees a faster convergence rate, and consequently, a lower regret in such problems. We propose a bandit policy that is a closed-form function of said estimated parameters. When the contexts are non-degenerate, the regret of the proposed policy is sublinear in the context dimension, the number of classes, and the time horizon T when the budget grows at least as √T. We also resolve an open problem posed by Agrawal & Devanur (2016) and extend the result to a multi-class setting. Our numerical experiments clearly demonstrate that the performance of our policy is superior to other benchmarks in the literature.
Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Builds on 21 of its 40 references that are in the map. First posted on arXiv 31 Jan 2023.
Builds on
21 of 40 references.
References · 21
- 2021Convex optimizationcited by 2,515
- 2015An Introduction to Matrix Concentration Inequalitiescited by 397
- 2013Bandits with Knapsackscited by 164
- 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
- 2017Mostly Exploration-Free Algorithms for Contextual Banditscited by 85
- 2014Bandits with concave rewards and convex knapsackscited by 83
- 2015Linear Contextual Bandits with Knapsackscited by 82
- 2018Adversarial Bandits with Knapsackscited by 73
- 2020Stochastic Bandits with Linear Constraintscited by 68
- 2019Doubly-Robust Lasso Banditcited by 49
- 2020Sparsity-Agnostic Lasso Banditcited by 44
- 2019Safe Linear Thompson Sampling with Side Informationcited by 37
9 more
- 2014Fast Algorithms for Online Stochastic Convex Programmingcited by 36
- 2018Balanced Linear Contextual Banditscited by 30
- 2021An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraintscited by 29
- 2021Doubly robust Thompson sampling for linear payoffscited by 21
- 2021The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsackscited by 16
- 2020Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysiscited by 15
- 2022Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Banditscited by 14
- 2020Bandits with Knapsacks beyond the Worst-Casecited by 6
- 2022Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Banditscited by 6
Built on by
Citing papers per year: 2023: 2.
2 papers.