Corruption-Robust Sparse Linear Contextual Bandits with Knapsack Constraints

Yige Wang; Hanyang Li; Yiming Zong; Wanteng Ma; Jiashuo Jiang

cs.LGSep 29, 2026

Corruption-Robust Sparse Linear Contextual Bandits with Knapsack Constraints

Authors: Yige Wang, Hanyang Li, Yiming Zong, Wanteng Ma, Jiashuo Jiang

Organizations: Department of Industrial Engineering and Decision Analytics, The Hong Kong University of Science and Technology · Department of Statistics and Data Science, The Wharton School, University of Pennsylvania

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.

Figures & tables

Corruption information	Sampling	Coverage	Corruption-free term
Bound $\Gamma\geq C_{Z}$	Forced	Population design	$\widetilde{O}(T^{2/3})$
Bound $\Gamma\geq C_{Z}$	On-policy	Realized design	$\widetilde{O}(\sqrt{T})$
Not supplied	Forced	Population design	$\widetilde{O}(T^{2/3})+\Reg_{\mathrm{mst}}(T)$
Not supplied	On-policy	Realized design and recommendation coverage	$\widetilde{O}(\sqrt{T})+\Reg_{\mathrm{mst}}(T)$

Table 1: Guarantee regimes and leading terms when corruption is absent.

Quantity	Meaning	Observed by the learner?
$r^{0}(a,x),b^{0}(a,x)$	clean conditional means	No
$r_{t}^{\mathrm{cl}}(a),b_{t}^{\mathrm{cl}}(a)$	clean noisy realizations before corruption	No
$r_{t}(a_{t}),b_{t}(a_{t})$	clipped feedback after corruption	Yes, for the chosen action

Table 2: Three levels of reward and resource-consumption feedback.

Symbol	Meaning
$T,K,d,m$	Number of rounds, non-null actions, context coordinates, and resources.
$x_{t},a_{t}$ ; $B$	Observed context and selected action at round $t$ ; resource-budget vector.
$r^{0},b^{0}$	Clean conditional reward and consumption means used by the benchmark.
$r^{\mathrm{cl}},b^{\mathrm{cl}}$	Clean noisy realizations before corruption.
$r,b$	Clipped corrupted feedback observed for the played action.
$c^{r},c^{b}$	Changes from clean to observed outcomes, measured after clipping.

Table 3: Model notation and selected quantities introduced later.

Input	Definition and role
$B^{\mathrm{op}}$	Operating budget used by the observed-consumption safety account; the default is $B$ .
$\Gamma$	Deterministic supplied bound satisfying $C_{Z}\leq\Gamma$ on every admissible realization.
$Z$	For $B^{\mathrm{op}}=B$ , a positive scale satisfying Assumption 2.2 ; $Z=T/B_{\min}$ suffices. The reduced-budget calibration is described below.
$\eta_{q}$	Multiplicative-weights stepsize for the resource-price distribution.
$\epsilon_{t}$	Probability of a uniform non-null forced-exploration override; it is zero in on-policy mode.
$n_{0}$	Action-specific retained-sample threshold before nontrivial sparse confidence is used.

Table 4: Inputs to the complete known-corruption method.

Symbol	Definition and role
$t_{\mathrm{init}}$	Prescribed cyclic initialization length, divisible by $K$ and subject to budget safety.
$\|\mathcal{G}\|$	Number of corruption candidates in $\mathcal{G}$ .
$K_{0}$	Number of actions including the null action, $K_{0}=\|\mathcal{A}_{0}\|=K+1$ .
$p_{\min}$	Probability floor for each action on the master-controlled branch.
$\alpha_{m}$	EXP4.P confidence-bonus coefficient.
$N_{a}^{\mathrm{rec},\Gamma}(t)$	Post-initialization active-round count of candidate $\Gamma$ recommending action $a$ before $t$ .

Table 5: Additional notation for Shared-Grid and recommendation coverage.

Experiment	Theory connection	Finite-sample question
Figure 1	Theorem 4.1 , Corollary 4.2	How absolute regret changes as a valid known corruption level increases.
Figure 2	Theorem 5.2 , Corollary 5.3	How much additional regret unknown corruption causes after accounting for each method’s clean finite-horizon cost.
Figure 3	Joint reward–consumption model and the Reward-Only ablation	How the location of a fixed corruption budget across reward and resource channels changes performance.
Figure 4	Proposition 2.1 and the pathwise parts of Theorems 4.1 – 5.2	How over- and under-reported consumption affect stopping and clean resource use.

Table 6: Theory-to-experiment map. The experiments are finite-sample illustrations of the mechanisms in the corresponding guarantees; empirical design and master diagnostics do not replace the stated probabilistic coverage conditions.

Figure 1: Known-corruption robustness. At fixed

T=20{,}000

, the effective corruption level

C_{Z}

increases along the horizontal axis. The vertical axis is absolute Relative Regret against the clean population-LP benchmark. Bands are the frozen 95% whole-replication bootstrap intervals.

Figure 2: Unknown-corruption adaptation. At fixed

T=80{,}000

, the horizontal axis is the unknown effective corruption level

C_{Z}

, and the vertical axis is the paired corruption-induced increase in Relative Regret. Bands are 95% paired whole-replication bootstrap intervals.

Figure 3: Corruption channels. Reward, consumption, and joint attacks use the same 1,200 targeted opportunities and the same effective corruption budget

C_{Z}=240

T=40{,}000

. Bars show absolute Relative Regret. Error bars are the frozen 95% whole-replication bootstrap intervals.

Figure 4: Resource accounting under consumption corruption. Over-reported consumption advances stopping (left), while under-reported consumption can hide clean resource use (right). The diagonal in the right panel is the pathwise upper bound

\Viol_{\mathrm{cl}}(T)\leq C_{b}(T)

. Observed-budget violation is zero on every reported trajectory.

Channel	ROPD	Reward-Only Robust	Non-Robust PD
Reward	0.0631	0.0673	0.0709
Consumption	0.5543	0.5551	0.5403
Joint	0.3019	0.3034	0.2939

Table 7: Increase in Relative Regret relative to matched clean controls (percentage points). ROPD and Reward-Only Robust use clean controls with the same supplied

\Gamma=240

; Non-Robust PD has no corruption-bound input.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$I_{t}$	Indicator that round $t$ is active under the pre-action safety rule.
$\tau$	Number of active rounds, $\tau=\sum_{t}I_{t}$ .
$R_{D}$	Dual regret against the best fixed resource-price vector in $\Lambda$ .
$\mathcal{E}_{\mathrm{conf}}$	Common event supplying the pointwise confidence interface.
$\mathcal{R}_{\mathrm{est}}^{0}$	Clean cumulative recommendation-width bound supplied by the estimator interface.
$\psi_{\mathrm{est}}(\Gamma)$	Additional cumulative width caused by retained response corruption.

Appendix

Table 8: Notation used in the known-corruption proof.

Contextual Bandits

Contextual bandits learn which action to take from features of each situation when only the chosen action’s reward is observed.

See all 152 papers

Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise
Mar 16, 2026Naoto Tani, Futoshi FutamiContextual Bandits Linear Contextual Bandits
The University of Osaka · RIKEN AIP · The University of Tokyo
Best-of-Both Worlds for linear contextual bandits with paid observations
Oct 8, 2025Nathan Boyer, Dorian Baudry, Patrick RebeschiniMulti-Armed Bandits Follow-the-Regularized-Leader
ENS Paris-Saclay, France · Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France · Department of Statistics, University of Oxford
Constrained Contextual Bandits with Adversarial Contexts
May 7, 2026Dhruv Sarkar, Abhishek SinhaContextual Bandits Adversarial Bandits
Indian Institute of Technology Kharagpur, India · Tata Institute of Fundamental Research, Mumbai, India

Mar 16, 2026J/K move · Enter open · S save

Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise

Naoto Tani, Futoshi Futami

The University of Osaka · RIKEN AIP · The University of Tokyo

Contextual Bandits Linear Contextual Bandits Multi-Armed Bandits

Open paper AskPDF arXiv

We study linear contextual bandits under adversarial corruption and heavy-tailed noise with finite

(1+ε)

-th moments for some

ε\in (0,1]

. Existing work that addresses both adversarial corruption and heavy-tailed noise relies on a finite variance (i.e., finite second-moment) assumption and suffers from computational inefficiency. We propose a computationally efficient algorithm based on online mirror descent that achieves robustness to both adversarial corruption and heavy-tailed noise. While the existing algorithm incurs

\mathcal{O}(t\log T)

computational cost, our algorithm reduces this to

\mathcal{O}(1)

per round. We establish an additive regret bound consisting of a term depending on the

(1+ε)

-moment bound of the noise and a term depending on the total amount of corruption. In particular, when

ε= 1

, our result recovers existing guarantees under finite-variance assumptions. When no corruption is present, it matches the best-known rates for linear contextual bandits with heavy-tailed noise. Moreover, the algorithm requires no prior knowledge of the noise moment bound or the total amount of corruption and still guarantees sublinear regret.

Abstract

Contextual Bandits

Explore similar work

Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise

Best-of-Both Worlds for linear contextual bandits with paid observations

Constrained Contextual Bandits with Adversarial Contexts