# Corruption-Robust Sparse Linear Contextual Bandits with Knapsack Constraints

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 44 references that are in the map.
- First posted on arXiv 29 Sep 2026.

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

- [Regret Bound Balancing and Elimination for Model Selection in Bandits and RL](https://mlsanity.com/paper/2012.13045/) (2020)
- [Stochastic Linear Optimization with Adversarial Corruption](https://mlsanity.com/paper/1909.02109/) (2019)
- [Model Selection for Generic Contextual Bandits](https://mlsanity.com/paper/2107.03455/) (2021)
- [Towards Costless Model Selection in Contextual Bandits: A Bias-Variance Perspective](https://mlsanity.com/paper/2106.06483/) (2021)

## Abstract (arXiv)

We study sparse linear contextual bandits with knapsack constraints under joint reward and consumption corruption. Consumption corruption creates a challenge beyond corrupted rewards: it affects not only statistical estimates, but also the recorded budget, resource prices, and stopping decisions that govern future allocation. We develop Robust Optimistic Primal--Dual (ROPD), an estimator-modular framework that combines corruption-aware confidence widths with online resource prices and a budget-safety rule. With concrete sparse implementation, ROPD achieves regret against a clean population-LP benchmark of widetilde O(T2/3+Gamma T1/3) under forced exploration and population-design coverage, and widetilde O(√ T+Gamma) under on-policy realized-design coverage, for a supplied valid corruption bound Gamma under the stated proportional-budget scaling and fixed model/design parameters. When the corruption level is unknown, Shared-Grid adapts confidence radii around common point estimates fitted to a single realized history, incurring explicit initialization and master-comparison costs; its sharper on-policy guarantee additionally requires recommendation coverage. Both methods preserve observed budgets on every realization and bound clean resource violation by cumulative consumption corruption. These results connect corruption-robust sparse estimation with resource accounting, pricing, and stopping in high-dimensional online allocation.