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, $\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.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper resolves an open problem in adversarial linear bandits by proposing CRW-FTRL, which achieves minimax optimal regret under strong corruption. The technical contribution is significant, introducing a novel reward estimation and regularization scheme that effectively neutralizes the advantage of strong adversaries, thereby establishing tight theoretical bounds for this challenging setting.
Methodology
The paper proposes CRW-FTRL, a novel algorithm for adversarial linear bandits with strong corruption. The core innovation lies in replacing standard importance-weighted reward estimates—which are vulnerable to strong adversaries who target rarely sampled actions—with a normalized kernel estimator governed by per-action radii. These radii are determined via a monotone log-determinant barrier problem, coupled with a radius-weighted entropy regularizer. This design effectively decouples the sensitivity of the reward estimator from the inverse sampling probabilities, preventing the adversary from amplifying corruption. The theoretical framework is rigorous, leveraging FTRL with a specific regularizer structure to cancel out both corruption bias and estimation error.
Results & evaluation
The provided text is a theoretical paper focused on regret bounds. It does not contain empirical experiments, benchmarks, or comparisons with baselines in a practical setting. The contribution is entirely analytical, proving that the proposed algorithm achieves minimax optimal regret rates.
Reproducibility
As a purely theoretical paper, reproducibility is tied to the correctness of the proofs rather than code implementation. The algorithm is described in sufficient detail for implementation, but the lack of code or empirical validation limits practical reproducibility assessment.
Limitations
The primary limitation is the lack of empirical validation. The paper acknowledges that the reduction to general compact action sets via discretization is not computationally efficient, leaving the question of a computationally efficient algorithm for general action sets open. Additionally, the results are high-probability bounds, and the constants hidden in the tilde-O notation may be significant in practice.
Broader impact
This work settles a key open question in the theory of corrupted bandits, providing minimax optimal rates for adversarial linear bandits with strong corruption. It has significant implications for the design of robust online learning algorithms in adversarial environments, such as online advertising and recommendation systems where feedback can be manipulated. The techniques developed (radius-weighted regularizers, kernel estimators with controlled sensitivity) may be applicable to other robust learning problems. The paper resolves an open problem in adversarial linear bandits by proposing CRW-FTRL, which achieves minimax optimal regret under strong corruption. The technical contribution is significant, introducing a novel reward estimation and regularization scheme that effectively neutralizes the advantage of strong adversaries, thereby establishing tight theoretical bounds for this challenging setting.
Author of this paper? Send a correction.