Research map / Bandits and online learning / Contextual bandits and Thompson sampling
High-dimensional Linear Bandits with Knapsacks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes an online hard-thresholding sparse estimator (Online HT) combined with primal-dual/resolving CBwK algorithms to obtain dimension-logarithmic regret for high-dimensional linear bandits with knapsacks.
Problem
Contextual bandits with knapsacks where covariates are high-dimensional and the reward and resource-consumption parameters are s0-sparse; prior CBwK regrets scale polynomially in the dimension d.
Approach
An online variant of iterative hard thresholding with gradient averaging (Online HT) gives statistically optimal sparse estimates with O(d^2) memory and per-step cost, which is plugged into a primal-dual framework (Hedge dual updates or dual resolving) with epsilon-greedy or greedy exploration; diverse covariate and margin conditions yield O(s0 sqrt T) and O(s0^2 log(dT) log T) regret.
Key results
- Online HT with working sparsity s>=s0 achieves fast estimation error decay and near-exact support recovery in a d=1000, s0=10 synthetic experiment, competitive with LASSO at lower per-step cost O(d^2).
- Theory gives CBwK regret of order (V^UB/C_min+1)sqrt(T) plus a T^{2/3} term under no covariate condition, O(s0 sqrt T) under diverse covariate or margin conditions, and O(s0^2 m^2 log(mKdT) log T) with resolving.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use diverse covariate conditions and set explicit exploration ε_t=0 | Primal-Dual High-dimensional CBwK · CBwK | regret: from \widetilde{O}\left(\left(\frac{\VU}{C_{\min}}\right)^{\frac{1}{3}}T^{\frac{2}{3}} \right) to \widetilde{O}\left( s_ | Helped |
| Assume the static dual margin condition | Primal-Dual High-dimensional CBwK · CBwK | regret: \widetilde{O}(s_0\sqrt{T}) | Helped |
| Use local dual resolving under local dual diversity, margin, and non-degeneracy conditions | Primal-Dual High-dimensional CBwK · CBwK | regret: O(s_0^2m^2{\log(mKdT)}\log T) | Helped |
| Use Online HT with ε-greedy exploration | High Dimensional Bandit by Online HT · High-dimensional contextual bandit, data-poor regime | regret: \widetilde{O}( s_0^{\frac{2}{3}} T^{\frac{2}{3}} ) | Helped |
| Use the diverse covariate condition and set ε_t=0 | High Dimensional Bandit by Online HT · High-dimensional contextual bandit, data-rich regime | regret: \widetilde{O}( \sqrt{s_0 T} ) | Helped |
| Set working sparsity s=5, below the true sparsity s_0=10 (ablation) | Online HT · Sparse recovery | support recovery rate | Hurt |
| Set working sparsity s=20 rather than underspecifying it (ablation) | Online HT · Sparse recovery | support recovery rate | Helped |
| Set working sparsity s=40 rather than underspecifying it (ablation) | Online HT · Sparse recovery | support recovery rate | Helped |
| Use working sparsity s below s_0, forcing thresholding to discard true-support coordinates (ablation) | Online HT · Sparse recovery | support recovery rate | Hurt |
Surprising findings
- The dual-update regret term scales with V^UB/C_min, so scarce resources make the dual term dominate rather than the primal estimation term.
Limitations
- Logarithmic regret requires non-degeneracy and local second-order growth and margin conditions on the dual problem.
- Regret depends polynomially on the number of resources m (O(m^2)) in the resolving analysis, and the O(s0 sqrt T) bounds rely on diverse covariate or margin assumptions.
Experimental setup
Datasets: synthetic simulated linear bandit data
Benchmarks: synthetic sparse recovery synthetic high-dimensional bandit
Metrics: regret estimation error support recovery rate
Baselines: LASSO
Builds on: bandits with knapsacks LASSO bandit iterative hard thresholding Hedge / online mirror descent dual resolving
Closest papers by meaning
- No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization (ICML 2025 · similarity 0.91)
- Thompson Sampling for High-Dimensional Sparse Linear Contextual Bandits (ICML 2023 · similarity 0.91)
- Smoothed Adversarial Linear Contextual Bandits with Knapsacks (ICML 2022 · similarity 0.91)
- Bandits with Replenishable Knapsacks: the Best of both Worlds (ICLR 2024 · similarity 0.89)
- Beyond Primal-Dual Methods in Bandits with Stochastic and Adversarial Constraints (NeurIPS 2024 · similarity 0.89)
- Logistic Bandits with $\tilde{O}(\sqrt{dT})$ Regret without Context Diversity Assumptions (NeurIPS 2026 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.