Robust sparse linear bandits handle corruption in budgeted settings
Corruption-Robust Sparse Linear Contextual Bandits with Knapsack Constraints
Machine Learning
Summary
Making decisions with limited resources is tricky when both the rewards and resource use can be corrupted or unreliable. The authors develop new methods to handle these corruptions in a high-dimensional setting where only a few factors matter, ensuring the system stays within its budget. Their approach manages uncertainty about corrupted data and keeps resource usage within acceptable limits. They provide guarantees on how well their methods perform even when corruption levels are unknown.
What this means in practice
- •For online advertising teams: Improve ad allocation decisions while managing advertising budgets under uncertain and corrupted click and cost data.
- •For inventory management teams: Optimize product recommendations balancing sales rewards and resource constraints even when sales and usage data have errors.
Authors
Yige Wang, Hanyang Li, Yiming Zong, Wanteng Ma, Jiashuo Jiang
Abstract
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(T^{2/3}+ΓT^{1/3})$ under forced exploration and population-design coverage, and $\widetilde O(\sqrt T+Γ)$ under on-policy realized-design coverage, for a supplied valid corruption bound $Γ$ 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.