# Improved Algorithms for Multi-period Multi-class Packing Problems with Bandit Feedback

arXiv: https://arxiv.org/abs/2301.13791 · HTML: https://mlsanity.com/paper/2301.13791/

## 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 (most cited first, 21 of 21)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [An Introduction to Matrix Concentration Inequalities](https://mlsanity.com/paper/1501.01571/) (2015)
- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [Linear Stochastic Bandits Under Safety Constraints](https://mlsanity.com/paper/1908.05814/) (2019)
- [Mostly Exploration-Free Algorithms for Contextual Bandits](https://mlsanity.com/paper/1704.09011/) (2017)
- [Bandits with concave rewards and convex knapsacks](https://mlsanity.com/paper/1402.5758/) (2014)
- [Linear Contextual Bandits with Knapsacks](https://mlsanity.com/paper/1507.06738/) (2015)
- [Adversarial Bandits with Knapsacks](https://mlsanity.com/paper/1811.11881/) (2018)
- [Stochastic Bandits with Linear Constraints](https://mlsanity.com/paper/2006.10185/) (2020)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [Sparsity-Agnostic Lasso Bandit](https://mlsanity.com/paper/2007.08477/) (2020)
- [Safe Linear Thompson Sampling with Side Information](https://mlsanity.com/paper/1911.02156/) (2019)
- [Fast Algorithms for Online Stochastic Convex Programming](https://mlsanity.com/paper/1410.7596/) (2014)
- [Balanced Linear Contextual Bandits](https://mlsanity.com/paper/1812.06227/) (2018)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Doubly robust Thompson sampling for linear payoffs](https://mlsanity.com/paper/2102.01229/) (2021)
- [The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks](https://mlsanity.com/paper/2102.06385/) (2021)
- [Structured Linear Contextual Bandits: A Sharp and Geometric Smoothed Analysis](https://mlsanity.com/paper/2002.11332/) (2020)
- [Double Doubly Robust Thompson Sampling for Generalized Linear Contextual Bandits](https://mlsanity.com/paper/2209.06983/) (2022)
- [Bandits with Knapsacks beyond the Worst-Case](https://mlsanity.com/paper/2002.00253/) (2020)
- [Squeeze All: Novel Estimator and Self-Normalized Bound for Linear Contextual Bandits](https://mlsanity.com/paper/2206.05404/) (2022)

## Built on by (most cited first, 2 of 2)

- [Learning the Pareto Front Using Bootstrapped Observation Samples](https://mlsanity.com/paper/2306.00096/) (2023)
- [A Doubly Robust Approach to Sparse Reinforcement Learning](https://mlsanity.com/paper/2310.15286/) (2023)

## 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.