Introduction
In the realm of online learning and decision-making, environments are typically categorized into two distinct types. In stochastic environments, the world follows a fixed, albeit unknown, pattern (akin to flipping a biased coin). In contrast, adversarial environments are dynamic and potentially reactive, with the environment changing its behavior to thwart the learner (akin to a strategic game of poker).
While the machine learning community has developed a solid understanding of what makes stochastic problems statistically "easy" or "hard"—largely through tools like the Decision-Estimation Coefficient (DEC)—the adversarial landscape has remained fragmented. Historically, researchers have relied on a patchwork of specific results for bandit problems and a handful of "impossible" results for Reinforcement Learning (RL). This paper seeks a unifying theory, asking a fundamental question: Is there a single mathematical quantity that determines the statistical complexity of any adversarial decision-making problem, from simple bandits to complex RL?
The Core Insight: The "Convexity Gap"
The authors demonstrate that the fundamental "price" of moving from stable, stochastic environments to unpredictable, adversarial ones is governed by how a model class behaves under "convexification."
They prove that the Decision-Estimation Coefficient (DEC)—a measure of how difficult it is to learn a model—remains the key to understanding regret. However, in adversarial settings, there is a critical twist: one must apply the DEC to the convex hull of the model class. This effectively means the learner must be prepared for any "mixture" of possible environments the adversary might deploy.
This insight perfectly explains the gap between different adversarial problems. For multi-armed bandits, the model class is already convex, meaning the complexity does not change significantly when moving from stochastic to adversarial settings. However, for Reinforcement Learning, the model class is highly non-convex. "Convexifying" this class leads to an exponential explosion in complexity, mathematically explaining why adversarial RL is often exponentially harder than its stochastic counterpart.
Methodology: High-Probability Exploration-by-Optimization
To formalize this, the authors extend the Decision Making with Structured Observations (DMSO) framework to an adversarial setting. In this framework, a learner picks a decision, an adaptive adversary picks a model (like a Markov Decision Process or a reward function), and the learner receives a reward and an observation.
To solve this game, the paper introduces a novel algorithm called High-Probability Exploration-by-Optimization ($ExO^+$). Its key features include:
- Minimax Optimization: At each step, $ExO^+$ solves a minimax problem to find a sampling distribution that balances immediate performance (low regret) with information gathering (good estimation).
- High-Probability Guarantees: Unlike previous iterations of this technique that only provided "on average" guarantees, $ExO^+$ delivers robust guarantees that hold even against adaptive adversaries who alter their strategies based on the learner's past actions.
Key Results and Unification
The paper establishes that the convexified DEC is both necessary and sufficient for achieving low regret in adversarial decision-making.
- Upper and Lower Bounds: The authors prove that the regret of $ExO^+$ scales with the convexified DEC: $\text{Regret} \lesssim \text{dec}_{\gamma}(\text{co}(\mathcal{M})) \cdot T$. They also provide a matching lower bound (up to localization), demonstrating that for any algorithm with reasonable behavior, regret must scale with this same convexified DEC.
- Characterization of Learnability: The results establish a "zero-one law" for adversarial learning: sublinear regret is possible if and only if the convexified DEC decays polynomially as the scale parameter increases.
- Unifying Complexity Measures: En route to these guarantees, the paper shows that several prominent complexity measures—including the Information Ratio, Exploration-by-Optimization, and the DEC—are fundamentally connected. They all essentially measure the same underlying trade-off between information gain and immediate reward.
- Explaining Intractability: The framework successfully recovers known negative results, such as the intractability of tabular MDPs with adversarial dynamics, precisely because their convexified DEC is exponentially large.
Limitations and Future Directions
As a purely theoretical work focused on fundamental limits, the paper does not rely on empirical datasets, but it does highlight several avenues for future research:
- Computational Efficiency: The $ExO^+$ algorithm requires solving a minimax optimization problem over the entire decision space at every step. For problems with massive or continuous decision spaces, this is currently computationally prohibitive.
- Observing Rewards: The tight lower bounds currently assume the learner can observe rewards. Extending these bounds to "partial monitoring" settings, where rewards are hidden, remains an open challenge.
- Semi-Adversarial Models: The "all-or-nothing" nature of these results (where problems are either as easy as stochastic ones or entirely impossible) might be softened by investigating "semi-adversarial" environments. Exploring these robust, intermediate models is a promising next step for the field.
Summary updated