# Prediction with Corrupted Expert Advice

arXiv: https://arxiv.org/abs/2002.10286 · HTML: https://mlsanity.com/paper/2002.10286/

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2020.

## Built on by (most cited first, 27 of 27)

- [The best of both worlds: stochastic and adversarial episodic MDPs with unknown transition](https://mlsanity.com/paper/2106.04117/) (2021)
- [Nearly Optimal Best-of-Both-Worlds Algorithms for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2206.00873/) (2022)
- [Optimistic Online Mirror Descent for Bridging Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2302.04552/) (2023)
- [Defense Against Reward Poisoning Attacks in Reinforcement Learning](https://mlsanity.com/paper/2102.05776/) (2021)
- [On Optimal Robustness to Adversarial Corruption in Online Decision Problems](https://mlsanity.com/paper/2109.10963/) (2021)
- [Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness](https://mlsanity.com/paper/2202.07554/) (2022)
- [Memory Bounds for the Experts Problem](https://mlsanity.com/paper/2204.09837/) (2022)
- [Adversarially Robust Multi-Armed Bandit Algorithm with Variance-Dependent Regret Bounds](https://mlsanity.com/paper/2206.06810/) (2022)
- [A Robust Phased Elimination Algorithm for Corruption-Tolerant Gaussian Process Bandits](https://mlsanity.com/paper/2202.01850/) (2022)
- [A Regret-Variance Trade-Off in Online Learning](https://mlsanity.com/paper/2206.02656/) (2022)
- [Accelerated Rates between Stochastic and Adversarial Online Convex Optimization](https://mlsanity.com/paper/2303.03272/) (2023)
- [Multiplicative Reweighting for Robust Neural Network Optimization](https://mlsanity.com/paper/2102.12192/) (2021)
- [Robust Online Convex Optimization in the Presence of Outliers](https://mlsanity.com/paper/2107.01881/) (2021)
- [Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs](https://mlsanity.com/paper/2107.09572/) (2021)
- [Non-stochastic Bandits With Evolving Observations](https://mlsanity.com/paper/2405.16843/) (2024)
- [Parameter-free Algorithms for the Stochastically Extended Adversarial Model](https://mlsanity.com/paper/2510.04685/) (2025)
- [Bridging Adversarial and Nonstationary Multi-armed Bandit](https://mlsanity.com/paper/2201.01628/) (2022)
- [Multi-Agent Bandit Learning through Heterogeneous Action Erasure Channels](https://mlsanity.com/paper/2312.14259/) (2023)
- [When Lower-Order Terms Dominate: Adaptive Expert Algorithms for Heavy-Tailed Losses](https://mlsanity.com/paper/2506.01722/) (2025)
- [On the Adversarial Robustness of Benjamini Hochberg](https://mlsanity.com/paper/2501.03402/) (2025)
- [The SMART approach to instance-optimal online learning](https://mlsanity.com/paper/2402.17720/) (2024)
- [MAC Advice for Facility Location Mechanism Design](https://mlsanity.com/paper/2403.12181/) (2024)
- [Learning for Bandits under Action Erasures](https://mlsanity.com/paper/2406.18072/) (2024)
- [Does Feedback Help in Bandits with Arm Erasures?](https://mlsanity.com/paper/2504.20894/) (2025)
- [Best-Arm Identification with Noisy Actuation](https://mlsanity.com/paper/2604.02255/) (2026)
- [Adversarial Online Classification with a Preview](https://mlsanity.com/paper/2608.29503/) (2026)
- [Prediction with Expert Advice under Heavy-Tailed Losses](https://mlsanity.com/paper/2610.14904/) (2026)

## Abstract (arXiv)

We revisit the fundamental problem of prediction with expert advice, in a setting where the environment is benign and generates losses stochastically, but the feedback observed by the learner is subject to a moderate adversarial corruption. We prove that a variant of the classical Multiplicative Weights algorithm with decreasing step sizes achieves constant regret in this setting and performs optimally in a wide range of environments, regardless of the magnitude of the injected corruption. Our results reveal a surprising disparity between the often comparable Follow the Regularized Leader (FTRL) and Online Mirror Descent (OMD) frameworks: we show that for experts in the corrupted stochastic regime, the regret performance of OMD is in fact strictly inferior to that of FTRL.