Abstract
A central problem in online learning and decision making—from bandits to reinforcement learning—is to understand what modeling assumptions lead to sample-efficient learning guarantees. We consider a general adversarial decision making framework that encompasses (structured) bandit problems with adversarial rewards and reinforcement learning problems with adversarial dynamics. Our main result is to show—via new upper and lower bounds—that the Decision-Estimation Coefficient, a complexity measure introduced by Foster et al. in the stochastic counterpart to our setting, is necessary and sufficient to obtain low regret for adversarial decision making. However, compared to the stochastic setting, one must apply the Decision-Estimation Coefficient to the convex hull of the class of models (or, hypotheses) under consideration. This establishes that the price of accommodating adversarial rewards or dynamics is governed by the behavior of the model class under convexification, and recovers a number of existing results—both positive and negative. En route to obtaining these guarantees, we provide new structural results that connect the Decision-Estimation Coefficient to variants of other well-known complexity measures, including the Information Ratio of Russo and Van Roy and the Exploration-by-Optimization objective of Lattimore and György.
Introduction
In the field of online learning, a learner interacts with an environment to maximize cumulative rewards through a sequence of decisions. While the theoretical foundations for stochastic environments—where the environment follows a fixed, albeit unknown, distribution—are well-established, a general theory for structured adversarial decision-making has remained elusive. In adversarial settings, the environment may adaptively change its behavior, constrained only by a specific model class (e.g., linear structures or Markov Decision Processes).
This research addresses the fundamental question: What is the intrinsic mathematical quantity that determines whether a learner can achieve sublinear regret against an adaptive opponent? By extending the Decision-Estimation Coefficient (DEC) framework, this paper provides a unifying theory that characterizes the statistical complexity of adversarial decision-making across bandits and reinforcement learning (RL).
The Decision-Estimation Coefficient and Convexification
The Decision-Estimation Coefficient (DEC) was originally introduced to characterize the complexity of Decision Making with Structured Observations (DMSO) in stochastic settings. It quantifies the fundamental trade-off between the "regret" a learner incurs by choosing a specific action and the "information" gained about the underlying environment model.
The Price of Adversity
The core insight of this work is that the transition from stochastic to adversarial environments is governed by convexification. To achieve low regret against an adversary, the DEC must be evaluated over the convex hull of the model class, denoted as $co(\mathcal{M})$.
This convexification represents the adversary's ability to play "mixtures" of different models within the class. If a model class is already convex (such as in linear bandits), the adversarial problem is essentially no more difficult than its stochastic counterpart. However, for non-convex classes, the jump in complexity can be significant. This explains why certain problems, like tabular reinforcement learning, are efficiently learnable in stochastic settings but become statistically intractable in adversarial ones: the convex hull of tabular MDPs includes "latent MDPs," which are known to suffer from exponential complexity.
Algorithmic Framework: ExO+
To achieve the theoretical upper bounds, the authors introduce a new algorithm: High-Probability Exploration-by-Optimization (ExO+).
Previous iterations of Exploration-by-Optimization were limited to guarantees "in expectation," which could be exploited by an adaptive adversary. ExO+ provides high-probability guarantees, ensuring robustness even when the learner encounters sequences of unfavorable outcomes. The algorithm functions by solving a minimax optimization problem at each step, balancing the immediate cost of exploration against the information gained to refine future decisions.
Key Theoretical Results
The paper establishes the DEC as the "gold standard" for adversarial complexity through two primary results:
- Upper Bound: The ExO+ algorithm achieves a regret bound that scales with the DEC of the convexified model class ($dec_{\gamma}(co(\mathcal{M})) \cdot T$). This proves that a small convexified DEC is sufficient for learnability.
- Lower Bound: The authors demonstrate that for any reasonable learning algorithm, the regret must scale with a localized version of the same convexified DEC. This proves that the measure is necessary.
Together, these results provide a formal "if and only if" condition for learnability: a problem class allows for sublinear regret in an adversarial setting if and only if its convexified DEC decays at an appropriate rate as the scale parameter $\gamma$ increases.
Structural Unification
Beyond the primary bounds, the work provides a structural unification of the field. The authors provide new proofs connecting the DEC to other prominent complexity measures, including:
- The Information Ratio: Introduced by Russo and Van Roy for Bayesian settings.
- Exploration-by-Optimization Objective: Introduced by Lattimore and György.
These connections demonstrate that the DEC is not merely a new metric, but a fundamental bridge that links disparate theories of online learning.
Limitations and Future Directions
While this work provides a comprehensive statistical characterization, several challenges remain:
- Computational Complexity: The ExO+ algorithm requires solving a complex minimax problem at every time step. Its runtime scales with the number of possible decisions ($|\Pi|$), making it computationally prohibitive for large or continuous action spaces common in robotics.
- Localization Gaps: There remains a gap between the "global" nature of the current upper bound and the "localized" nature of the lower bound. In stochastic theory, localization is the key to achieving optimal, tight bounds; closing this gap for the adversarial case is a priority for future research.
- Intermediate Environments: Future work may explore the spectrum between purely stochastic and purely adversarial environments to identify complexity measures for "semi-adversarial" models that might allow for more efficient algorithms.
Summary updated