Standard algorithms for multi-armed bandits (MAB) are built on the principle of Optimism Under Uncertainty. By maintaining a confidence interval around the estimated reward of each arm and always picking the arm with the highest upper bound, a learner naturally balances exploration and exploitation.
However, this optimism is a double-edged sword. In recent years, researchers have shown that a malicious adversary can exploit this trust. By strategically "poisoning" rewards—for example, by slightly lowering the observed reward of the optimal arm—an attacker can trick standard algorithms into permanently discarding the best option. This leads to linear regret, where the learner fails to improve over time.
To counter this, a new class of robust algorithms has emerged. The core intuition is simple: if an adversary can manipulate rewards within a certain budget, the learner must expand its confidence intervals to account for the maximum possible damage that budget could inflict.
The Vulnerability of Shrinking Bounds
In a purely stochastic environment, the confidence interval around an arm's mean reward shrinks at a rate of $1/\sqrt{n}$, where $n$ is the number of times the arm has been pulled. As we gather more data, we become more certain.
An adversary breaks this certainty. As noted by Lin Yang and John C. S. Lui in Adversarial Bandits with Corruptions: Regret Lower Bound and No-regret Algorithm, even a small corruption budget allows an adaptive attacker to suppress the rewards of optimal arms when their selection probability is low. If the learner's confidence interval shrinks faster than the adversary's ability to manipulate the mean, the "true" optimal arm may eventually fall below the estimated rewards of sub-optimal arms, causing the learner to stop pulling it entirely.
The Core Defense: Budget-Aware Inflation
The primary mechanism for robustness across this research direction is the inclusion of a bias-offset term or compensation bonus. Instead of a standard confidence radius, the learner uses an expanded radius:
$$\text{Confidence Radius} = \text{Statistical Uncertainty} + \frac{\text{Corruption Budget}}{\text{Number of Samples}}$$
This adjustment, explored by Jinhang Zuo and Xuchuang Wang in Stochastic Bandits Robust to Adversarial Attacks, ensures that the true underlying reward remains within the bounds even if the adversary has exhausted their entire budget on that specific arm.
By widening the radius, the learner remains "pessimistic" about the observations but "optimistic" about the potential true reward. This prevents the premature elimination of optimal candidates, a strategy also applied to hierarchical multi-objective settings by Bo Xue and Xi Lin in Problem-dependent Regret for Lexicographic Multi-Armed Bandits with Adversarial Corruptions.
Adapting to Unknown Attack Budgets
A major practical hurdle is that the learner rarely knows the adversary's total corruption budget $C$ in advance. If the learner assumes a budget that is too small, they remain vulnerable; if they assume one that is too large, they explore excessively and suffer high regret.
To solve this, Cho-Jui Hsieh and James Sharpnack proposed a Bandit-over-Bandit framework in Robust Stochastic Linear Contextual Bandits Under Adversarial Attacks. In this architecture, a master algorithm treats different potential budget levels as "arms" themselves, adaptively learning the optimal level of exploration needed to counteract the actual interference encountered.
Similarly, for Gaussian Process (GP) bandits, Andreas Krause, Ilija Bogunovic, and Jonathan Scarlett developed a "Fast-Slow" strategy in Corruption-Tolerant Gaussian Process Bandit Optimization. By switching between aggressive and cautious estimation instances, the algorithm can maintain near-optimal performance in clean environments while remaining resilient when data is poisoned.
Generalizing to Complex Decision Spaces
The principle of expanded uncertainty extends beyond simple discrete arms:
- Continuous Spaces: In Robust Lipschitz Bandits to Adversarial Corruptions, Yue Kang demonstrates that inflating the confidence radius by a term proportional to the budget-to-sample ratio allows for sub-linear regret even in continuous arm sets.
- Reinforcement Learning: In complex environments like Block MDPs, Tianhao Wu and Simon S. Du introduced CR-MVP, which uses a dual-component exploration bonus. One term handles standard statistical variance, while a dedicated bias-offset term neutralizes adversarial manipulation of both rewards and observations (On Reinforcement Learning with Adversarial Corruption and Its Application to Block MDP).
- Thompson Sampling: Traditional Bayesian approaches are notoriously fragile to poisoning. Gagandeep Singh and Yinglun Xu adapted the optimism principle to posteriors, adding compensation terms to empirical means to ensure the probability of selecting the best action remains high enough to sustain exploration under attack (Robust Thompson Sampling Algorithms Against Reward Poisoning Attacks).
By explicitly modeling the adversary's potential impact as a form of "structured uncertainty," these researchers have transformed bandit algorithms from fragile statistical tools into robust decision-making frameworks capable of operating in hostile, real-world environments.