Sequential Decision Making Under Adversarial Corruption

242 concepts105 papers1 proposal

The Fragility of Classical Online Learning

In sequential decision-making frameworks—such as multi-armed bandits, reinforcement learning (RL), and online optimization—algorithms typically assume one of two extreme environments. They either expect a stochastic world, where feedback is drawn from a stable, clean probability distribution, or a worst-case adversarial world, where an opponent chooses the feedback at every step to maximize the learner's loss.

However, real-world deployment often falls into a messy middle ground: the environment is predominantly stable, but a small fraction of the data is corrupted by sensor glitches, malicious attackers, or strategic users. Classical algorithms designed for purely stochastic environments are surprisingly fragile when faced with this reality. For instance, in Temporal Difference (TD) learning, even a tiny fraction of corrupted reward data can steer the algorithm toward an arbitrary, incorrect value function, as shown by Sreejeet Maity et al. in Adversarially-Robust TD Learning with Markovian Data: Finite-Time Rates and Fundamental Limits.

Why does this happen? Traditional algorithms often rely on absolute measurements or empirical averages. As Johannes Kirschner et al. point out in Bias-Robust Bayesian Optimization via Dueling Bandits, when feedback signals are corrupted by an adversarial or time-varying bias, an algorithm tracking absolute values cannot distinguish between a genuinely high reward and a high bias term. Consequently, a clever adversary can easily trap the learner into choosing suboptimal actions indefinitely, leading to catastrophic failure or linear regret.

The Goal: Additive Regret and Graceful Degradation

To bridge this gap, a growing body of research focuses on designing algorithms that are robust to a corruption budget $C$, which represents the total magnitude or volume of adversarial interference over a time horizon $T$.

The core intuition behind this direction is graceful degradation. If the environment turns out to be perfectly clean ($C = 0$), the algorithm should achieve optimal performance (such as logarithmic regret in stochastic bandits). If an adversary injects corruption ($C > 0$), the algorithm's performance should suffer a penalty that is strictly bounded by the size of the corruption, rather than multiplying the inherent complexity of the learning task.

Mathematically, this is achieved through an additive regret decomposition: $$\text{Regret} \le \text{Regret}_{\text{clean}} + f(C)$$ where $f(C)$ typically scales linearly ($O(C)$) or sublinearly (such as $O(\sqrt{C})$) with the total corruption budget.

This formulation enables "Best-of-Both-Worlds" or "Best-of-Three-Worlds" guarantees. For example, Chung-Wei Lee et al. in Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously and Shinji Ito et al. in Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds demonstrate that linear bandit algorithms can maintain high efficiency in stable settings while ensuring that performance degrades gracefully if the environment is compromised. Similarly, in model-based RL, Chenlu Ye et al. show in Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruption that the impact of adversarial corruption can be completely decoupled from the time-based learning difficulty.

Core Mechanisms for Thwarting Corruption

How can an algorithm distinguish between a rare, high-reward stochastic event and an adversarial lie? Researchers have converged on several key mechanisms to build intuition and achieve robustness.

1. Uncertainty Weighting and Robust Estimators

Instead of treating all feedback equally, robust algorithms dynamically down-weight observations that appear highly anomalous or occur in regions of high uncertainty. In Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback, Qiwei Di et al. utilize an uncertainty-weighted Maximum Likelihood Estimation (MLE) strategy. By scaling down the influence of potentially corrupted feedback based on the learner's current uncertainty, they ensure that the penalty for adversarial corruption remains strictly proportional to the actual volume of corruption present.

At an extreme level, replacing the empirical mean with robust statistics like the median can protect the learner from unbounded corruptions. Debabrota Basu et al. introduce this in CRIMED: Lower and Upper Bounds on Regret for Bandits with Unbounded Stochastic Corruption, showing that median-based estimators can withstand severe, unbounded data manipulation.

2. Discarding Magnitudes in Favor of Direction and Preferences

Adversaries often exploit algorithms by providing massive, unbounded reward signals or gradients that pull the model parameters far off course. One elegant defense is to ignore the magnitude of the feedback entirely.

In optimization, Berkay Turan et al. analyze this in On Robustness of the Normalized Subgradient Method with Randomly Corrupted Subgradients. By utilizing the Normalized Subgradient Method (NSM), which discards gradient magnitude and only retains directional information, the algorithm becomes completely immune to the scale of the corruption. Even if an adversary provides an infinitely large malicious vector, its impact is capped because the vector is normalized before the update step.

A parallel intuition applies to preference-based learning, such as dueling bandits. Instead of asking for the absolute score of an action, the algorithm only observes relative preferences (whether action $A$ is preferred to action $B$). As explored by Aadirupa Saha et al. in Versatile Dueling Bandits: Best-of-both World Analyses for Learning from Relative Preferences, decoupling decision-making into relative comparisons prevents the high-order polynomial performance degradation typically seen when absolute feedback is poisoned.

3. Randomized Exploration and Multi-Layered Strategies

If an algorithm's exploration strategy is completely deterministic, a strategic adversary can predict its next choice and perfectly tailor a corruption attack. To counter this, robust algorithms inject strategic randomness or maintain multiple parallel learning tracks.

Andreas Krause et al. implement this in Corruption-Tolerant Gaussian Process Bandit Optimization using a "Fast-Slow" strategy. By randomly switching between aggressive (fast) and cautious (slow) estimation instances, the algorithm prevents the adversary from consistently manipulating the model's beliefs, ensuring that cumulative regret scales linearly with the corruption budget.

Fundamental Limits and the Breakdown Point

While these robust mechanisms provide powerful safeguards, they cannot completely eliminate the cost of adversarial interference. Information theory dictates a fundamental performance floor in the presence of corruption.

As shown by Andi Nika et al. in Corruption-Robust Offline Two-Player Zero-Sum Markov Games, there is an unavoidable information-theoretic limit where the suboptimality gap scales linearly with the fraction of corrupted samples. No learning algorithm can completely erase this error because an adversary can use their budget to make a suboptimal policy look identical to the optimal one.

Furthermore, there is a strict threshold beyond which learning becomes completely impossible. In the context of multi-armed bandits with stochastic corruption, Debabrota Basu et al. establish a 50% breakdown point. If the probability of corruption reaches or exceeds 50%, an adversary can perfectly mimic the behavior of the optimal arm using a suboptimal one, making it mathematically impossible for any learner to identify the true optimum. Below this breakdown point, however, robust algorithms successfully preserve logarithmic regret, demonstrating the power of corruption-robust design.

Key Foundational Work

Better Algorithms for Stochastic Bandits with Adversarial Corruptions (2019) — contributed 4 concept elements to this direction.
Better Algorithms for Stochastic Bandits with Adversarial Corruptions (2019) — contributed 3 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_adversarial_corruption_robustness_0b03bd52,
  title = {adversarial corruption robustness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adversarial-corruption-robustness/rdr_0b03bd529dd14117a5b6b0ae62f9a7e2},
  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_adversarial_corruption_robustness_0b03bd52_v1,
  title = {adversarial corruption robustness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adversarial-corruption-robustness/rdr_0b03bd529dd14117a5b6b0ae62f9a7e2/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake