Abstract
This paper investigates the robustness of online learning algorithms to adversarial corruption in stochastic environments. Focusing on the "prediction with expert advice" and "multi-armed bandit" (MAB) problems, we demonstrate that the optimal regret penalty scales with the square root of the corruption level ($\sqrt{C}$). We show that standard algorithms, such as Hedge with a decreasing learning rate, naturally achieve this optimal robustness without prior knowledge of the corruption budget.
Introduction
In online decision-making, environments are typically modeled as either stochastic (losses from a fixed distribution) or adversarial (worst-case losses). While "best-of-both-worlds" (BOBW) algorithms bridge these extremes, real-world scenarios often involve intermediate regimes—specifically, stochastic environments subject to adversarial corruptions (e.g., data poisoning or sensor failures). This work addresses the fundamental question: what is the absolute best performance (lowest regret) a learning algorithm can guarantee when an adversary corrupts a stochastic environment with a total budget $C$?
Methodology
The study utilizes the framework of an "adversarial regime with a self-bounding constraint," which generalizes corrupted stochastic environments. The analysis focuses on the robustness of existing, well-known algorithms:
- Decreasing Hedge: The classic Multiplicative Weights algorithm with a learning rate $\eta_t \propto 1/\sqrt{t}$.
- Adaptive Hedge: Algorithms utilizing second-order regret bounds.
To establish optimality, the paper constructs specific adversarial environments to derive minimax lower bounds. By strategically modifying losses to reduce the "suboptimality gap" $\Delta$, the analysis identifies the minimum regret any algorithm must incur.
Key Insights
- Square-Root Scaling: The optimal regret penalty due to corruption $C$ is proportional to $\sqrt{C}$, rather than the linear scaling suggested by previous work. This implies significantly higher robustness for large $C$.
- Adaptivity: The analyzed algorithms achieve $O(\sqrt{C})$ robustness without prior knowledge of the corruption budget $C$ or the suboptimality gap $\Delta$.
- Inherent Robustness of Standard Algorithms: Simple algorithms like decreasing Hedge are shown to be fundamentally more robust than baseline approaches like Follow-the-Leader (FTL).
Key Results
The primary theoretical contributions are summarized in the table below, which compares the upper and lower bounds derived for both the expert problem and the multi-armed bandit setting.
For the expert problem, the paper proves that decreasing Hedge achieves a regret bound of $O\left(\frac{\log N}{\Delta} + \sqrt{\frac{C \log N}{\Delta}}\right)$, matching the derived minimax lower bound. For the MAB problem, a lower bound of $\Omega\left(\frac{N}{\Delta} + \sqrt{\frac{CN}{\Delta}}\right)$ is established, which is nearly tight with existing upper bounds (e.g., Zimmert and Seldin, 2021).
Discussion and Future Work
While the bounds for the expert problem are tight, a logarithmic gap ($\log T$) remains in the MAB setting. Future research will focus on closing this gap and extending the $O(R + \sqrt{CR})$ robustness signature to more complex online decision problems, including online linear optimization and convex bandits.
Summary updated