# High-dimensional Linear Bandits with Knapsacks

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 40 references that are in the map.
- First posted on arXiv 2 Nov 2023.

## Builds on (most cited first, 26 of 26)

- [Bandits with Knapsacks](https://mlsanity.com/paper/1305.2545/) (2013)
- [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)
- [Sequential Batch Learning in Finite-Action Linear Contextual Bandits](https://mlsanity.com/paper/2004.06321/) (2020)
- [High-Dimensional Sparse Linear Bandits](https://mlsanity.com/paper/2011.04020/) (2020)
- [The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems](https://mlsanity.com/paper/2011.10124/) (2020)
- [Doubly-Robust Lasso Bandit](https://mlsanity.com/paper/1907.11362/) (2019)
- [Resourceful Contextual Bandits](https://mlsanity.com/paper/1402.6779/) (2014)
- [Sparsity-Agnostic Lasso Bandit](https://mlsanity.com/paper/2007.08477/) (2020)
- [Dynamic Batch Learning in High-Dimensional Sparse Linear Contextual Bandits](https://mlsanity.com/paper/2008.11918/) (2020)
- [Online Stochastic Optimization with Wasserstein Based Non-stationarity](https://mlsanity.com/paper/2012.06961/) (2020)
- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [Generalized Low-rank plus Sparse Tensor Estimation by Fast Riemannian Optimization](https://mlsanity.com/paper/2103.08895/) (2021)
- [A Simple Unified Framework for High Dimensional Bandit Problems](https://mlsanity.com/paper/2102.09626/) (2021)
- [Statistical Inference for Online Decision Making via Stochastic Gradient Descent](https://mlsanity.com/paper/2010.07341/) (2020)
- [PopArt: Efficient Sparse Regression and Experimental Design for Optimal Sparse Linear Bandits](https://mlsanity.com/paper/2210.15345/) (2022)
- [A Tight Bound of Hard Thresholding](https://mlsanity.com/paper/1605.01656/) (2016)
- [Thresholded Lasso Bandit](https://mlsanity.com/paper/2010.11994/) (2020)
- [The Symmetry between Arms and Knapsacks: A Primal-Dual Approach for Bandits with Knapsacks](https://mlsanity.com/paper/2102.06385/) (2021)
- [Linear Convergence of Stochastic Iterative Greedy Algorithms with Sparse Constraints](https://mlsanity.com/paper/1407.0088/) (2014)
- [Optimal Contextual Bandits with Knapsacks under Realizability via Regression Oracles](https://mlsanity.com/paper/2210.11834/) (2022)
- [Optimal Regularized Online Allocation by Adaptive Re-Solving](https://mlsanity.com/paper/2209.00399/) (2022)
- [Stability and Risk Bounds of Iterative Hard Thresholding](https://mlsanity.com/paper/2203.09413/) (2022)
- [Sample Efficient Stochastic Gradient Iterative Hard Thresholding Method for Stochastic Sparse Linear Regression with Limited Attribute Observation](https://mlsanity.com/paper/1809.01765/) (2018)
- [Online Tensor Learning: Computational and Statistical Trade-offs, Adaptivity and Optimal Regret](https://mlsanity.com/paper/2306.03372/) (2023)

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

- [Online Policy Learning and Inference by Matrix Completion](https://mlsanity.com/paper/2404.17398/) (2024)
- [Learning to Price with Resource Constraints: From Full Information to Machine-Learned Prices](https://mlsanity.com/paper/2501.14155/) (2025)
- [Drift-Aware LLM Routing with Sparse Contexts and Shared Budgets](https://mlsanity.com/paper/2609.00662/) (2026)

## Abstract (arXiv)

We investigate the contextual bandits with knapsack (CBwK) problem in a high-dimensional linear setting, where the feature dimension can be very large. Our goal is to harness sparsity to obtain sharper regret guarantees. To this end, we first develop an online variant of the hard thresholding algorithm that performs the sparse estimation in an online manner. We then embed this estimator in a primal-dual scheme: every knapsack constraint is paired with a dual variable, which is updated by an online learning rule to keep the cumulative resource consumption within budget. This integrated approach achieves a two-phase sub-linear regret that scales only logarithmically with the feature dimension, improving on the polynomial dependency reported in prior work. Furthermore, we show that either of the following structural assumptions is sufficient for a sharper regret bound of tildeO(s0 √T): (i) a diverse-covariate condition; and (ii) a margin condition. When both conditions hold simultaneously, we can further control the regret to O(s02 log(dT)log T) by a dual resolving scheme. As a by-product, applying our framework to high-dimensional contextual bandits without knapsack constraints recovers the optimal regret rates in both the data-poor and data-rich regimes. Finally, numerical experiments confirm the empirical efficiency of our algorithms in high-dimensional settings.