Bandit Learning Robust to Adversarial Corruptions

This direction is merged into another direction: adversarial corruption robustness. Its last version stays readable and citable here.

Version 1 of 118 papers19 conceptsfrozen 2026-10-04

In online learning, researchers traditionally split the world into two extremes. In the stochastic world, rewards are drawn from stable probability distributions, allowing algorithms to converge quickly on the best option. In the adversarial world, rewards are chosen by a malicious opponent, forcing algorithms to be cautious and pessimistic.

Recent research has bridged this gap by focusing on the "stochastic with adversarial corruptions" model. In this setting, the environment is mostly stable, but an adversary can manipulate a portion of the feedback. The goal is to design algorithms that are "Best-of-Both-Worlds"—achieving near-optimal performance when the environment is clean, while ensuring that performance degrades gracefully as the total corruption budget ($C$) increases.

The Gold Standard: Additive Regret Scaling

The central breakthrough across these papers is the achievement of additive regret. In a standard bandit problem, "regret" measures the difference between the rewards the agent actually collected and the rewards it could have collected by always picking the best arm.

In a corrupted environment, we want the regret to look like this: $$\text{Regret} \leq \text{Optimal Stochastic Regret} + \mathcal{O}(C)$$

This linear scaling with the corruption budget $C$ is a critical property. It means the penalty for being attacked is proportional only to the magnitude of the attack itself, rather than being multiplied by the complexity of the problem (like the number of available actions). Andreas Krause, Ilija Bogunovic, and Jonathan Scarlett demonstrated this in Corruption-Tolerant Gaussian Process Bandit Optimization, proving that while a performance penalty is unavoidable, it can be kept strictly proportional to the misinformation introduced.

Mechanisms for Robustness

How do algorithms ignore "lies" from an adversary without also ignoring valuable data? Several key mechanisms have emerged:

  1. The Fast-Slow Strategy: Andreas Krause and colleagues introduced algorithms that switch between "aggressive" estimation (to exploit the stochastic structure) and "cautious" estimation (to guard against corruption). This prevents the adversary from leading the agent down a garden path of suboptimal choices.
  2. Uncertainty-Based Downweighting: In Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptions, Dongruo Zhou and Quanquan Gu developed the CW-OFUL algorithm. It identifies rounds where the model is highly uncertain and downweights that feedback. This ensures that the most potentially corrupted data has the least impact on the model’s long-term strategy.
  3. Best-of-Three-Worlds Adaptation: Some environments are not just corrupted; they might be entirely adversarial or perfectly stochastic. Chung-Wei Lee and Haipeng Luo designed algorithms that automatically detect the environment type, achieving instance-optimality in stable settings and minimax-optimality in chaotic ones simultaneously.

Scaling to Complex Structures

The intuition of additive robustness has been successfully extended beyond simple multi-armed bandits to more complex domains:

  • Linear and Lipschitz Bandits: When the set of possible actions is continuous or infinite, the challenge is to prevent corruption in one area of the action space from "poisoning" the agent's understanding of other areas. Yue Kang and Cho-Jui Hsieh provided the first robust algorithms for Lipschitz bandits, showing that sub-linear regret is possible even when the corruption budget is unknown.
  • Reinforcement Learning: In On Reinforcement Learning with Adversarial Corruption and Its Application to Block MDP, Tianhao Wu and Simon S. Du moved beyond bandits to full MDPs. They showed that even when an adversary corrupts observations in a complex state space, an agent can still learn an optimal policy with regret scaling linearly with the corruption.
  • Multi-Agent Coordination: In decentralized settings, agents must communicate to learn. Fakhreddine Ghaffari and colleagues showed that by using weighted reward estimators, multiple agents can remain robust to corruption even in heterogeneous environments.

The Fundamental Limit

A recurring theme across this literature—from cooperative bandits to contextual search—is the existence of a theoretical lower bound. Researchers have proven that an additive penalty proportional to $C$ is mathematically unavoidable. This realization has shifted the focus of the field: the question is no longer if corruption will hurt performance, but how to design algorithms that ensure the damage is no worse than the corruption itself.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_bandit_learning_robust_to_adversarial_co_b1443a94,
  title = {Bandit Learning Robust to Adversarial Corruptions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bandit-learning-robust-to-adversarial-corruptions/rdr_b1443a9466c7472fa18af0bd4e8adfb6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_bandit_learning_robust_to_adversarial_co_b1443a94_v1,
  title = {Bandit Learning Robust to Adversarial Corruptions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/bandit-learning-robust-to-adversarial-corruptions/rdr_b1443a9466c7472fa18af0bd4e8adfb6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}