In classical online learning, researchers typically design algorithms for one of two extremes. In the stochastic setting, data is independent and identically distributed (i.i.d.), allowing algorithms to converge quickly by exploiting stability. In the adversarial setting, data is chosen by a malicious opponent, forcing algorithms to be cautious and pessimistic to avoid being misled.
However, real-world data is rarely purely one or the other. A system might be mostly stable but suffer from occasional sensor failures, malicious "poisoning" attacks, or sudden distribution shifts. A new line of research focuses on "Best-of-Both-Worlds" (BOBW) algorithms that automatically adapt to the environment's actual level of chaos without knowing it in advance.
The Corrupted Stochastic Model
The bridge between these two extremes is the corrupted stochastic model. In this framework, the environment is primarily stochastic, but an adversary is allowed a "corruption budget" $C$. This adversary can intercept the true feedback and replace it with arbitrary, even unbounded, values.
The goal is to achieve robustness: the algorithm should perform nearly as well as a specialized stochastic algorithm when $C$ is small, but its performance should degrade gracefully as $C$ increases, never performing worse than a standard adversarial algorithm.
Graceful Degradation and the Square Root of Corruption
A recurring discovery across this research is that the "cost" of corruption—measured as regret—often scales with the square root of the total corruption ($\sqrt{C}$).
Shinji Ito established fundamental limits in On Optimal Robustness to Adversarial Corruption in Online Decision Problems, proving that for multi-armed bandits and expert advice problems, the regret penalty scales with $\sqrt{C}$ rather than linearly. This sub-linear growth is crucial; it means that as long as the corruption is limited, the learner can still extract significant signal from the underlying stochastic process.
This pattern holds even in complex scenarios. For instance, in Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive Regret Bounds, Shinji Ito and Kei Takemura demonstrate that linear bandits can achieve variance-adaptive bounds that simultaneously respect this $\sqrt{C}$ scaling.
Mechanisms for Robustness
How do these algorithms actually ignore the "noise" while following the "signal"? Several key mechanisms have emerged:
1. Hybrid Regularizers
Standard algorithms often use Follow-the-Regularized-Leader (FTRL). To achieve BOBW performance, researchers engineer specific regularizers that blend different properties. Liad Erez and Tomer Koren introduced a hybrid Tsallis-Shannon entropy regularizer in Best-of-All-Worlds Bounds for Online Learning with Feedback Graphs, which allows the algorithm to switch its behavior based on the observed feedback.
2. Selective Filtering
Sometimes the best way to handle a corrupted data point is to ignore it entirely. In Robust Online Convex Optimization in the Presence of Outliers, Sarah Sachs, Tim van Erven, and colleagues show that a simple strategy of filtering out rounds with exceptionally large gradients can protect adaptive algorithms from being "poisoned" by adversarial outliers.
3. Directional Stability
When gradients are corrupted, their magnitude is often the most misleading component. Berkay Turan, Hoi To Wai, and Mahnoosh Alizadeh found that the Normalized Subgradient Method (NSM)—which ignores magnitude and only uses the direction of the gradient—is naturally robust to unbounded corruptions that occur intermittently (On Robustness of the Normalized Subgradient Method with Randomly Corrupted Subgradients).
Expanding the Horizon
The push for corruption-robustness is moving beyond simple bandits into structured decision-making:
- Reinforcement Learning: Shinji Ito and Haipeng Luo extended these ideas to episodic Markov Decision Processes (MDPs) where feedback is only received at the end of an episode (Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback).
- Inverse Optimization: In Finite and Corruption-Robust Regret Bounds in Online Inverse Linear Optimization under M-Convex Action Sets, Taihei Oki and Shinsaku Sakaue proved that if the action sets have specific geometric properties (M-convexity), the learner can achieve regret bounds that are entirely independent of the time horizon $T$, even when some observed actions are intentionally misleading.
By moving away from "worst-case" assumptions and toward "adaptive" robustness, this research direction provides a theoretical foundation for algorithms that are both efficient in practice and resilient under attack.