Strong-Corruption Adversarial Linear Bandits: CRW-FTRL Achieves Near-Minimax Optimal Regret

Adversarial linear bandits are a classic model in sequential decision-making, but when reward observations are maliciously tampered with, the theoretical guarantees of traditional algorithms degrade severely. A recent study proposes the CRW-FTRL algorithm, which under the strong-corruption model raises the regret upper bound to the same order as the corruption-free optimal rate and matches the known lower bound.

Why strong corruption breaks classical algorithms

In the strong-corruption setting, an adaptive adversary first chooses the reward vector, and after seeing the learner's action, the strong adversary can tamper with the observed reward at each round, with a total tampering budget of known constant (C). This attack pattern directly defeats the importance-weighted reward estimator commonly used in adversarial bandits: the adversary only needs to inject corruption in rounds where actions with extremely low sampling probability are selected, and each unit of corruption is amplified by the inverse of the sampling probability.

This means that even if the total corruption budget is not large, the algorithm can be completely misled by perturbations in a few key rounds. The best upper bound previously given by Liu et al. was (\tilde O(\sqrt{d^3T} + dC)), whose main term is a (\sqrt{d}) factor worse than the corruption-free rate. Whether a regret of (\tilde O(d\sqrt{T} + dC)) can be achieved has remained an open problem.

Importance-weighted estimation is a common technique for handling feedback in adversarial bandits: when the algorithm selects action (a) with probability (p_t(a)) and observes reward (r_t(a)), the unbiased estimator is (\hat{r}_t(a) = r_t(a) \cdot \mathbb{I}{a_t = a} / p_t(a)). It allows the algorithm to unbiasedly estimate the expected reward of all actions from only the feedback of the selected action, and is the cornerstone of algorithms such as FTRL and EXP3. However, the variance of this estimator is proportional to (1/p_t(a)), and when certain actions are sampled with extremely low probability, the corresponding estimates become highly unstable. In the strong-corruption scenario, if the adversary precisely injects errors in these low-probability rounds, the amount of corruption is amplified to (1/p_t(a)) times the original value, thereby causing a huge cumulative bias with a very small total budget. Therefore, importance-weighted estimation is structurally fragile against malicious tampering and requires a fundamental redesign of the estimator.

Core design of CRW-FTRL

CRW-FTRL stands for "radius-weighted follow-the-regularized-leader." Instead of importance weighting, it employs a normalized kernel estimator to estimate rewards, whose sensitivity to corruption is controlled by the "radius" of each action rather than the inverse of the sampling probability.

These radii are non-decreasing and are jointly solved with the sampling distribution through a monotone log-determinant barrier problem. The key to this design is that the negative linear term in the regularization can simultaneously cancel the corruption bias and the estimation error of each comparator. In other words, the algorithm encodes robustness against corruption into the regularization structure itself, rather than patching the estimator after the fact.

Follow-the-regularized-leader (FTRL) is a class of online learning frameworks: at each round, the algorithm selects the action that maximizes "the cumulative reward estimate minus the regularization term," i.e., (a_t = \arg\max_{a} \left( \sum_{s=1}^{t-1} \hat{r}_s(a) - R_t(a) \right)), where (\hat{r}_s) is the reward estimate and (R_t) is the regularization term. Regret analysis of FTRL typically decomposes the cumulative regret into an estimation error term and a regularization term, and controls the stability and exploration of the algorithm through a carefully designed regularizer (such as the log-determinant barrier function). In the presence of corruption, the estimation error term includes the bias caused by corruption, and the design of the regularization term needs to additionally absorb this bias. The contribution of CRW-FTRL is that it incorporates radius weights into the regularizer, so that the negative linear term can simultaneously cancel the corruption bias and the comparator's estimation error, thereby recovering the corruption-free optimal main term in the regret bound.

Theoretical guarantees: matching the lower bound and the corruption-free rate

For (K) actions in (\mathbb{R}^d), CRW-FTRL achieves a regret of (\tilde O(\sqrt{dT\log K} + dC)) against an adaptive adversary with high probability. The main term of this upper bound matches the known optimal corruption-free rate, and the corruption-related term (dC) matches the (\Omega(dC)) lower bound up to logarithmic factors.

Applying the algorithm to the discretization of a general compact action set yields a regret of (\tilde O(d\sqrt{T} + dC)), thereby formally establishing the statistical rate of adversarial linear bandits under strong corruption. From a theoretical perspective, this resolves the open problem left by Liu et al. and completely eliminates the (\sqrt{d}) gap in the main term.

Lower bounds in online learning characterize the limit of the optimal regret that any algorithm can achieve on a given problem class. In corruption-free adversarial linear bandits, the known minimax lower bound is (\Omega(d\sqrt{T})) (ignoring logarithmic factors), and Liu et al. proved the corruption-related lower bound of (\Omega(dC)) under the strong-corruption setting. The regret upper bound of CRW-FTRL, (\tilde O(\sqrt{dT\log K} + dC)), matches both lower bounds up to logarithmic factors, meaning it is statistically rate-optimal. In particular, the matching of the corruption term (dC) with the lower bound shows that the algorithm's sensitivity to corruption has reached the information-theoretic limit, and the additional cost caused by corruption cannot be reduced by further improving the algorithm.

Methodological implications and boundaries

This work conveys a more general message: in the face of observation corruption, algorithm frameworks that rely solely on importance weighting have structural flaws and require a simultaneous redesign of both the estimator and the regularizer. The radius-weighting idea provides a reusable template—replacing global inverse-probability weights with action-dependent scale parameters, thereby limiting the amplification effect of single-point corruption.

It should be noted that this result is currently based on theoretical analysis, and experimental verification and numerical performance in practical deployment are not yet reflected in the abstract. In addition, the assumption that the corruption budget (C) is known may not hold in practical scenarios; how to maintain near-optimal regret when the budget is not fully known remains a direction worth attention.