Additive Regret Bounds for Corruption Robust Reinforcement Learning

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

Version 1 of 119 papers23 conceptsfrozen 2026-10-04

In classical reinforcement learning (RL), we typically assume the environment is either stochastic or follows a fixed, albeit unknown, logic. However, real-world systems—from recommendation engines targeted by botnets to autonomous vehicles facing sensor tampering—must operate in "dirty" environments where an adversary can strategically corrupt rewards or state transitions.

The central challenge in this research direction is preventing these corruptions from causing the agent's performance to collapse over time. Recent breakthroughs have moved the field from algorithms that suffer significantly under attack to those that achieve additive regret bounds, where the cost of corruption is decoupled from the learning process itself.

The Shift to Additive Regret

In the presence of an adversary who can corrupt data with a total "budget" $C$, early robust algorithms often suffered from multiplicative regret. In those models, the impact of corruption would scale with the time horizon $T$, meaning even a small, early manipulation could lead to a permanent, growing gap in performance.

The core insight of recent work, such as that by Simon Shaolei Du and Kevin Jamieson in Improved Corruption Robust Algorithms for Episodic Reinforcement Learning, is that it is possible to achieve regret bounds of the form $R(T) + O(C)$. This additive structure is transformative: it ensures that the penalty for being attacked is proportional only to the total amount of corruption $C$, rather than the duration of the learning process $T$. As the agent interacts more with the environment, the "standard" learning error $R(T)$ vanishes on a per-step basis, and the corruption term remains a fixed, separate overhead.

Decoupling Exploration from Corruption

How do you learn the true nature of an environment when the feedback you receive is intentionally misleading? A recurring mechanism to solve this is uncertainty weighting.

Researchers like Chenlu Ye, Quanquan Gu, and Tong Zhang have developed techniques that weight observations based on the learner's current confidence. In their work on Nonlinear Contextual Bandits and MDPs, they use uncertainty weighting to ensure that potentially corrupted data points do not overly influence the model's updates.

By down-weighting samples where the model is highly uncertain or where the potential for adversarial influence is high, these algorithms effectively "filter" the corruption. This allows for robust Maximum Likelihood Estimation (MLE) even in complex, nonlinear settings. As Chenlu Ye demonstrates in Towards Robust Model-Based Reinforcement Learning Against Adversarial Corruption, this weighting allows model-based RL to remain stable even when the environment's underlying transitions are being manipulated.

Robustness in Strategic and Preference-Based Learning

The need for corruption robustness extends beyond simple reward poisoning into settings where the "arms" or "agents" themselves are strategic.

  1. Strategic Manipulations: In combinatorial bandits, Jing Dong and Baoxiang Wang have shown that the learner's regret is fundamentally constrained by the strategic agents' manipulation budget Combinatorial Bandits under Strategic Manipulations.
  2. Preference Learning (RLHF): As preference-based learning becomes central to training large language models, the vulnerability to flipped labels (adversarial feedback) grows. Qiwei Di and Jiafan He addressed this in Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback, applying uncertainty-weighted MLE to ensure that a few malicious preference labels cannot derail the entire alignment process.
  3. Click Fraud: In cascading bandits (used in search and advertising), Fakhreddine Ghaffari and colleagues developed the $M^2UCB-V$ algorithm to remain robust against click fraud by using a "mean-of-medians" estimator, which provides a more stable average that is less sensitive to the outliers typical of adversarial attacks Online Learning to Rank under Corruption.

Why It Works: The Intuition of Stability

The success of these algorithms relies on the principle that adversarial influence is finite. If an adversary has a budget $C$, they can only trick the agent so many times or by so much. By using robust estimators (like mean-of-medians) and adaptive weighting (uncertainty weighting), the agent ensures that it doesn't "over-learn" from any single interaction.

In a standard algorithm, a single massive corruption could pull the policy toward a sub-optimal region forever. In these robust variants, the agent maintains a "skepticism" that scales with its uncertainty. This ensures that the impact of the adversary is strictly bounded by the actual volume of their interference, allowing the agent to eventually converge to the optimal policy as if the "clean" data eventually drowned out the "poisoned" noise.

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_additive_regret_bounds_for_corruption_ro_582b75a3,
  title = {Additive Regret Bounds for Corruption Robust Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/additive-regret-bounds-for-corruption-robust-reinforcement-learning/rdr_582b75a3872141a7ae3b91afb9dc5dd4},
  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_additive_regret_bounds_for_corruption_ro_582b75a3_v1,
  title = {Additive Regret Bounds for Corruption Robust Reinforcement Learning},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/additive-regret-bounds-for-corruption-robust-reinforcement-learning/rdr_582b75a3872141a7ae3b91afb9dc5dd4/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}