Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions
cs.LG, stat.ML
Submitted: 2026-10-28
Updated: 2026-10-28
Comments: 39 pages, 1 table
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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…
Terminology
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, 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 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 R d, CRW-FTRL achieves O(sqrt dT 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 O(d sqrt T + dC) regret, which settles the statistical rate of corrupted adversarial linear bandits under strong corruption.
Related papers
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis
- (Mis)generalization of Helpful-Only Fine-tuning