Sequential decision-making algorithms, such as multi-armed bandits and reinforcement learning agents, fundamentally rely on the principle of Optimism Under Uncertainty. By choosing actions based on their Upper Confidence Bounds (UCB) or by sampling from a posterior distribution (Thompson Sampling), an agent balances exploiting known high-reward actions with exploring uncertain ones.
However, this optimism introduces a critical vulnerability. If a malicious adversary can intercept and corrupt the rewards or actions—even within a limited total budget $C$—they can exploit the agent's trust in its uncertainty bounds. For instance, by strategically suppressing the rewards of the optimal arm when it is chosen, an attacker can artificially depress its empirical mean. As Lin Yang 0013 et al. demonstrate, standard bandit algorithms that assume unbiased feedback will permanently abandon these suppressed optimal strategies, resulting in catastrophic linear regret.
To counter this, a growing body of research focuses on designing corruption-robust exploration mechanisms that gracefully degrade performance proportional to the attack budget rather than failing entirely.
Widening Confidence Bounds with Corruption Budgets
To prevent an adversary from permanently hiding the optimal action, the most direct defense is to make the agent more patient and skeptical. If the agent explicitly factors potential manipulation into its uncertainty estimates, it can avoid being misled by poisoned data.
In a standard UCB algorithm, the upper bound for an arm is defined by its empirical mean plus a statistical confidence radius derived from the number of times it has been pulled. To achieve robustness, Andreas Krause et al. and Ilija Bogunovic et al. propose widening these upper confidence bounds by adding a term proportional to the expected corruption budget.
Mathematically, if an adversary can alter rewards, the true mean of an arm might be lower or higher than observed. By expanding the confidence interval by the maximum possible offset introduced by reward misattribution, the authors ensure that the true reward function remains within the estimated bounds with high probability. This prevents the algorithm from prematurely discarding optimal actions due to poisoned observations.
This core mechanism has been generalized across several complex settings:
- Linear and Contextual Bandits: Cho-Jui Hsieh et al. enlarge the exploration bonus in linear UCB by a factor proportional to a candidate attack budget. They utilize a two-layer "Bandit-over-Bandit" framework to adaptively learn the budget when it is completely unknown.
- Continuous Action Spaces: For Lipschitz bandits operating on continuous arm sets, Yue Kang et al. inflate the confidence radius by a term proportional to the ratio of the total corruption budget to the number of times the arm has been sampled, ensuring the algorithm remains sufficiently optimistic to sustain exploration.
- Reinforcement Learning: In complex Markov Decision Processes (MDPs), Tianhao Wu et al. introduce a dual-component exploration bonus. One term handles standard statistical variance, while a dedicated bias-offset term compensates for potential adversarial manipulations of both rewards and observations. Similarly, in offline zero-sum games, Andi Nika et al. augment uncertainty quantifiers with a pessimism bonus that scales with the fraction of corrupted data.
Diluting Attacks via Action Repetition
Simply widening the confidence bounds keeps the optimal arm from being discarded, but it can cause the agent to over-explore sub-optimal arms if the bounds remain too wide. To tighten these bounds efficiently, algorithms must force the adversary to spend their corruption budget at an unsustainable rate.
A powerful mechanism to achieve this is action repetition within structured epochs, as developed by Ilija Bogunovic et al.. Instead of changing actions at every step, the learner plays a chosen action multiple times consecutively and averages the resulting feedback.
Averaging multiple observations dilutes the impact of any single corrupted reward. For an adversary to significantly shift the empirical mean of an arm, they must repeatedly corrupt the rewards across the entire epoch. This forces the attacker to expend a much larger portion of their finite budget. Consequently, the learner's information gain outpaces the attack, allowing a phased elimination strategy to safely discard truly sub-optimal arms.
Maintaining Optimistic Posteriors
While UCB algorithms modify explicit bounds, Bayesian approaches like Thompson Sampling are vulnerable because adversarial reward suppression shifts the posterior distribution away from the optimal action.
To counter this, Gagandeep Singh et al. introduce robust variants of Thompson Sampling that utilize optimistic posteriors. By adding a compensation bonus directly to the empirical mean based on the suspected corruption budget, the algorithm artificially inflates the perceived value of arms that might be under attack. This mechanism ensures that the posterior belief for the optimal action remains high enough to sustain exploration, preventing the adversary from successfully hiding the best choice through negative reward poisoning.
Unpredictability and Forced Exploration
Deterministic exploration strategies are easy targets for adversaries because the attacker can perfectly predict which arm the agent will pull next and tailor the corruption accordingly.
Shiliang Zuo demonstrates that standard UCB and Thompson Sampling can be completely hijacked with a tiny corruption budget of only $O(\sqrt{\log T})$ due to this predictability. To defend against this, the author introduces randomized selection rules inspired by behavioral economics, such as Smoothed and Quantal Responses. By introducing a small amount of intentional sub-optimality and randomness, the learner becomes unpredictable. Furthermore, incorporating a forced exploration mechanism—maintaining a constant baseline probability of exploring all options—forces the attacker to spend an exponentially larger budget to consistently mislead the learner.
Exploiting Geometric Structure and Data Verification
Beyond modifying exploration bonuses, researchers have identified structural and operational levers to mitigate corruptions:
- Geometric Unattackability: In linear stochastic bandits, arms are often correlated via a shared feature space. Huazheng Wang et al. reveal that this geometric correlation can make linear bandits intrinsically unattackable. If an adversary tries to poison an arm's reward, the perturbation propagates across correlated arms. To successfully fool the learner without affecting other arms, the adversary must execute a "Null Space Attack," projecting perturbations strictly into the null space of the target arm's feature vector.
- Limited Data Verification: Instead of guessing the corruption budget, an agent can actively clean its data. Anshuka Rangi et al. show that a learner does not need to verify all data to defeat an attacker. By strategically querying ground-truth rewards for just a tiny, logarithmic fraction of the total observations, the agent can accurately refine its uncertainty intervals and fully recover optimal performance.
Key Foundational Work
Adversarial Bandits with Corruptions: Regret Lower Bound and No-regret Algorithm (2020) — contributed 5 concept elements to this direction.
Corruption-Tolerant Gaussian Process Bandit Optimization (2020) — contributed 1 concept elements to this direction.
Revenue Optimization against Strategic Buyers (2015) — contributed 1 concept elements to this direction.