On Optimal Robustness to Adversarial Corruption in Online Decision Problems

Shinji Ito

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:

  1. Decreasing Hedge: The classic Multiplicative Weights algorithm with a learning rate $\eta_t \propto 1/\sqrt{t}$.
  2. 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.

Summary of regret bounds for corrupted stochastic environments in the expert and multi-armed bandit settings.

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

BibTeX
@inproceedings{ito2021optimal,
  author = {Shinji Ito},
  title = {{On Optimal Robustness to Adversarial Corruption in Online Decision Problems}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=1vA0W69V5j},
}
Figure