Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions

Qiwei Di; Quanquan Gu

cs.LGOct 28, 2026

Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions

Authors: Qiwei Di, Quanquan Gu

Organizations: Department of Computer Science, University of California, Los Angeles, CA 90095, USA

Abstract

We study adversarial linear bandits with strong corruption, in which an adaptive adversary chooses the reward vectors and a strong adversary corrupts each observed reward after seeing the learner's action, subject to a known total corruption budget $C$ . Strong corruption breaks the importance-weighted reward estimates used by adversarial bandit algorithms: by corrupting only the rounds in which a rarely sampled action is drawn, the adversary amplifies each unit of corruption by the inverse of its sampling probability. The best known bound for this problem, $\tilde O(\sqrt{d^3T} + dC)$ by Liu et al. (2024), is a factor $\sqrt{d}$ above the corruption-free rate in its leading term, and whether $\tilde O(d\sqrt{T} + dC)$ regret is achievable was left open. We propose CRW-FTRL, which runs follow-the-regularized-leader with a radius-weighted entropy regularizer and estimates rewards with a normalized kernel estimator whose sensitivity to corruption is governed by per-action radii instead of inverse sampling probabilities. The radii are nondecreasing and are chosen jointly with the sampling distribution through a monotone log-determinant barrier problem, so that a negative linear term in the regularizer cancels both the corruption bias and the estimation error of every comparator. For $K$ actions in $\mathbb{R}^d$ , CRW-FTRL achieves $\tilde O(\sqrt{dT\log K} + dC)$ regret with high probability against an adaptive adversary, which matches the best known corruption-free rate and the $Ω(dC)$ lower bound up to logarithmic factors. Applied to a discretization of a general compact action set, it yields $\tilde O(d\sqrt{T} + dC)$ regret, which settles the statistical rate of corrupted adversarial linear bandits under strong corruption.

Figures & tables

Algorithm	Rewards	Measure	Regret
Robust Phased Elimination ( Bogunovic et al., 2021 )	Stoch.	$C$	$\widetilde{O}(\sqrt{dT\log K}+d^{3/2}C)$
CW-OFUL ( He et al., 2022 )	Stoch.	$C$	$\widetilde{O}(d\sqrt{T}+dC)$
Randomized Phased Elimination ( Liu et al., 2024 )	Stoch.	$C_{\infty}$	$\widetilde{O}(d\sqrt{T}+\sqrt{d}C_{\infty})$
FTRL with log-det ( Liu et al., 2024 )	Adv.	$C_{\infty}$	$\widetilde{O}(d\sqrt{T}+\sqrt{d}C_{\infty})$
Continuous Exp. Weights ( Liu et al., 2024 )	Adv.	$C$	$\widetilde{O}(\sqrt{d^{3}T}+dC)$
CRW-FTRL (Algorithm 1 , ours), $\|\mathcal{A}\|=K$	Adv.	$C$	$\widetilde{O}(\sqrt{dT\log K}+dC)$

Table 1: Comparison of regret bounds for linear bandits with corruptions. “Stoch.” and “Adv.” indicate whether the reward vectors

\bm{\theta}_{t}

are fixed or chosen by an adaptive adversary.

C=\sum_{t=1}^{T}|c_{t}|

is the strong corruption measure and

C_{\infty}\geq C

is the weak measure of Liu et al. (2024) .

K

is the number of actions,

\widetilde{O}(\cdot)

and

\widetilde{\Omega}(\cdot)

hide logarithmic factors, and the lower bounds hold in the nontrivial regime where the stated bound is at most

O(T)

Adversarial Bandits

Adversarial bandits study how to choose actions and learn from partial feedback when rewards or losses can change strategically over time.

See all 54 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

May 3, 2026

Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptions

We study linear dueling bandits in volatile environments characterized by the simultaneous presence of post-serving contexts, delayed feedback, and adversarial corruption. Feedback is subject to unknown stochastic or adversarial delays and a cumulative corruption budget

\mathcal{C}

. To address these challenges, we propose e RCDP-UCB, which integrates a learned approximator that predicts post-serving contexts from pre-serving information. It further employs an adaptive weighting strategy that clips feature vectors to mitigate the impact of corrupted and delayed observations simultaneously. Under standard regularity conditions and a parametric post-serving mapping, we rigorously establish that our algorithm is delay-regime-agnostic, achieving a regret upper bound of

\widetilde{\mathcal{O}}(d(\sqrt{T} + \mathcal{C} + \mathcal{D}))

, where

d

is the total feature dimension and

\mathcal{D}

encapsulates the delay complexity. Crucially, our analysis reveals an additive cost structure between corruption and delay, avoiding the multiplicative degradation typical of prior works. We further establish lower bounds that nearly match our upper bounds up to a

\sqrt{d}

factor for adversarial delays in the absence of post-serving contexts. Code is available at https://github.com/youngmin0oh/rcdp-public.

Youngmin Oh

InfiniTree, Republic of Korea

Multi-Armed Bandits Bandits with Delayed Feedback Contextual Bandits UCB Algorithms

Ask PDF

Feb 11, 2026

A Jointly Efficient and Near-Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions

We consider heteroskedastic generalized linear bandits (GLBs) with adversarial corruptions and propose HCW-GLB-OMD, a simple algorithm that combines an online mirror descent (OMD)-based estimator with Hessian-based confidence weights. Although both components are well studied, establishing guarantees for the combined algorithm requires a nontrivial analysis. We establish a corruption-robust confidence sequence using technical tools not required in prior analyses, including a weighted likelihood supermartingale and a self-bounding argument. For the regret analysis, we derive a new Hessian potential lemma to handle the interaction between adversarial corruption and adaptive confidence weighting. For self-concordant GLMs, we prove a high-probability regret bound of

\widetilde{\mathcal{O}}\bigl( d \sqrt{\sum_t g(τ_t) \dotμ_{t,\star}} + d^2 g_{\max} κ+ d(1+κ)(C\vee1) \bigr)

, where

\dotμ_{t,\star}

is the slope of

μ

at the optimal arm at time

t

g(τ_t)

is the observed dispersion,

g_{\max}=\max_t g(τ_t)

κ

is the worst-case inverse slope of

μ

, and

C

is the corruption budget. The algorithm attains this bound with one OMD update per round and

\mathcal{O}(d^2)

storage. We complement this guarantee with matching lower bounds for the leading

\sqrt{T}

term and, up to

κ

, the

dC

corruption term.

Sanghwa Kim, Junghyun Lee, Se-Young Yun

Kim Jaechul Graduate School of AI, KAIST Seoul 02455, Republic of Korea

Multi-Armed Bandits Online Mirror Descent Robust Multi-Armed Bandits Corruption Robustness Contextual Bandits Generalized Linear Models+1

Ask PDF

Abstract

Adversarial Bandits

Explore similar work

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

Robust Linear Dueling Bandits with Post-serving Context under Unknown Delays and Adversarial Corruptions

A Jointly Efficient and Near-Optimal Algorithm for Heteroskedastic Generalized Linear Bandits with Adversarial Corruptions