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

Mar 16, 2026

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

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.

Naoto Tani, Futoshi Futami

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

Contextual Bandits Linear Contextual Bandits Multi-Armed Bandits

Ask PDF

Oct 8, 2025

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

We study linear contextual bandits with paid observations, where at each round the learner observes a context, selects an action, and may pay a fixed cost to observe feedback from a subset of arms. We propose two Follow-the-Regularized-Leader algorithms with Best-of-Both-Worlds guarantees. The first, Agg-SPB, extends the SPB-matching framework of Tsuchiya and Ito (2024) by aggregating context-dependent stability terms, achieving the characteristic

T^{2/3}

adversarial regret rate and logarithmic dependence on

T

in stochastic environments. The second, CE-SPB, combines arm-dependent observation probabilities with an entropy-adaptive learning rate inspired by Kuroki et al. (2024). It achieves an entropy-adaptive

\widetilde{O}(T^{2/3})

adversarial guarantee and polylogarithmic stochastic regret, while avoiding the minimum-context-mass dependence arising in the stochastic analysis of Agg-SPB. Both algorithms further extend to corrupted stochastic environments with explicit corruption-dependent guarantees. These results establish that logarithmic stochastic regret is compatible with the

T^{2/3}

adversarial regime for linear contextual bandits with paid observations, while highlighting a tradeoff between sharper horizon dependence in stochastic settings and path-dependent matching without explicit minimum-context-mass dependence.

Nathan Boyer, Dorian Baudry, Patrick Rebeschini

ENS Paris-Saclay, France · Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France · Department of Statistics, University of Oxford

Multi-Armed Bandits Follow-the-Regularized-Leader Contextual Bandits Adversarial Bandits Linear Contextual Bandits

Ask PDF

May 7, 2026

Constrained Contextual Bandits with Adversarial Contexts

We study constrained contextual bandits with adversarial contexts, where each action yields a random reward and incurs a random cost. The conditional mean reward and cost belong to known function classes and are learned through online regression oracles. The benchmark is a stationary randomized policy whose expected cost is non-positive at every observed context. We extend the seminal

\mathsf{SquareCB}

algorithm of Foster and Rakhlin (2020), which reduces the contextual bandits to a regression problem, to the constrained setting. A surrogate reward function is constructed which penalizes the positive part of the expected cost of an action distribution, and an auxiliary variable accumulates its predicted value. Then we use an exponential Lyapunov function to control both regret and cumulative constraint violation via a single inequality. If the cumulative squared prediction error is at most

U_T

, our algorithm achieves

O(\sqrt{KTU_T})

regret and

O(\sqrt{KTU_T}\log T)

cumulative expected cost, with high probability, improving upon the previous

O(T^{3/4})

type bounds obtained in stochastic contextual settings with an unknown context distribution. Our results require neither additional margin conditions nor probabilistic assumptions on the context sequence.

Dhruv Sarkar, Abhishek Sinha

Indian Institute of Technology Kharagpur, India · Tata Institute of Fundamental Research, Mumbai, India

Contextual Bandits Adversarial Bandits

Ask PDF

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