Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
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, Õ(√(d3T) + dC) by Liu et al. (2024), is a factor √d above the corruption-free rate in its leading term, and whether Õ(d√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 ℝd, CRW-FTRL achieves Õ(√(dTlog 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 Õ(d√T + dC) regret, which settles the statistical rate of corrupted adversarial linear bandits under strong corruption.
Related
- Bandits with Multiple Optimal Arms: Minimax Regret and Non-Adaptivity
- RobustLDS: Learning linear dynamical systems under adversarial corruptions
- m-Set Adversarial Bandits with Winner Feedback
- Nearly Linear-Time Follow-the-Perturbed-Leader for Weakly Observable Graph Bandits
- Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
BibTeX
@misc{di2026nearly,
title = {{Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions}},
author = {Qiwei Di and Quanquan Gu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.38243},
eprint = {2610.38243},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.38243},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
AU - Qiwei Di
AU - Quanquan Gu
PY - 2026
DA - 2026/10/28
PB - arXiv
DO - 10.48550/arxiv.2610.38243
UR - https://arxiv.org/abs/2610.38243
AB - 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, Õ(√(d^3T) + dC) by Liu et al. (2024), is a factor √d above the corruption-free rate in its leading term, and whether Õ(d√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 ℝ^d, CRW-FTRL achieves Õ(√(dTlog 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 Õ(d√T + dC) regret, which settles the statistical rate of corrupted adversarial linear bandits under strong corruption.
ER -