Asymptotic Instance-Optimal Algorithms for Interactive Decision Making

Kefan Dong, Tengyu Ma

In the field of interactive decision-making—encompassing multi-armed bandits, linear bandits, and reinforcement learning (RL)—the standard benchmark for algorithm performance has long been minimax regret. Minimax regret measures how an algorithm performs on the most difficult possible instance of a problem. While this provides a safety net, it is inherently pessimistic. It fails to account for the fact that many real-world problem instances are "easy," and an ideal agent should be able to exploit that simplicity to achieve much lower regret.

This paper introduces Test-to-Commit (T2C), the first algorithm to achieve asymptotic instance-optimality for a broad class of interactive decision-making problems with a finite number of decisions. By framing the learning process as an active hypothesis testing task, the researchers from Stanford University have established a framework that matches the theoretical lower bound for regret on every specific problem instance.

The Quest for Instance-Optimality

An instance-optimal algorithm is often considered the "Holy Grail" of decision theory. Unlike minimax algorithms, which are designed for the worst-case scenario, an instance-optimal algorithm performs as well as any "consistent" algorithm (one that achieves non-trivial regret on all possible instances) could possibly perform on a specific instance $f$.

While instance-optimality was well-established for simple Multi-Armed Bandits (MAB) through the seminal work of Lai and Robbins (1985), extending these results to structured problems like Reinforcement Learning remained an open challenge. In RL, actions do not merely yield rewards; they transition the agent to new states and provide structured observations, making the "cost" of exploration much harder to quantify.

The Complexity of Verification: $\mathcal{C}(f)$

The core theoretical contribution of this work is the characterization of a new complexity measure, $\mathcal{C}(f)$. This measure represents the minimum cost—expressed in terms of regret—required to distinguish the true instance $f$ from all alternative instances that would require a different optimal decision.

Essentially, the paper argues that the fundamental limit of learning is the cost of verification. To be optimal, an agent must spend exactly enough effort to prove its current best hypothesis is correct, and no more. The complexity $\mathcal{C}(f)$ is derived from an optimization problem that determines the most economical way to collect data (observations) to reject all sub-optimal hypotheses.

The Test-to-Commit (T2C) Algorithm

The T2C algorithm implements this verification-based approach through three distinct phases:

  1. Initialization: The agent performs uniform exploration for a brief period to generate an initial Maximum Likelihood Estimate (MLE) of the problem instance, denoted as $\hat{f}$.
  2. Identification: This is the critical innovation. The agent solves an optimization problem to identify the most efficient decisions to test whether $\hat{f}$ is indeed the true instance. It then conducts a log-likelihood ratio test. If the collected data aligns with the predictions of $\hat{f}$, the agent gains high statistical confidence in its estimate.
  3. Exploitation: If the test passes, the agent "commits" to the optimal decision for $\hat{f}$ for the remainder of the time horizon. If the test fails—indicating the initial estimate was incorrect—the agent reverts to a robust, standard algorithm (such as UCB) to ensure it still achieves reasonable performance.

By using the log-likelihood ratio test, T2C avoids being tied to specific noise distributions (like Gaussian noise), allowing it to generalize across various decision-making structures.

Key Results and Impact

The authors provide rigorous proofs demonstrating that T2C is asymptotically instance-optimal. As the number of interactions $n$ approaches infinity, the regret of T2C scales as $\mathcal{C}(f) \ln n$, matching the theoretical lower bound exactly.

Bridging Theory and Practice

  • Tabular Reinforcement Learning: T2C is the first algorithm proven to be asymptotically instance-optimal for tabular Markov Decision Processes (MDPs). This improves upon previous "instance-dependent" bounds, which were often loose or failed to match the true complexity of the instance.
  • Unification: The framework successfully recovers classical results for Multi-Armed Bandits and more recent bounds for Linear Bandits, providing a unified language for interactive learning.

Limitations and Future Directions

While T2C represents a major theoretical breakthrough, several hurdles remain for practical implementation:

  • Computational Complexity: In Reinforcement Learning contexts, solving the optimization problem to find the most economical testing strategy involves iterating over the space of all possible policies. In tabular MDPs, this space grows exponentially with the number of states, making the algorithm computationally expensive.
  • Asymptotic vs. Finite-Time: The optimality is guaranteed as $n \to \infty$. In real-world scenarios with short horizons, the "lower-order terms" (regret components that do not scale with $\ln n$) may be significant, potentially making T2C less efficient than simpler heuristics in the short term.
  • Action Spaces: The current theory is limited to a finite number of possible decisions. Extending instance-optimality to continuous action spaces, such as those found in robotics, remains a significant open question for the field.

Summary updated

Abstract

Past research on interactive decision making problems (bandits, reinforcement learning, etc.) mostly focuses on the minimax regret that measures the algorithm's performance on the hardest instance. However, an ideal algorithm should adapt to the complexity of a particular problem instance and incur smaller regrets on easy instances than worst-case instances. In this paper, we design the first asymptotic instance-optimal algorithm for general interactive decision making problems with finite number of decisions under mild conditions. On every instance $f$, our algorithm outperforms all consistent algorithms (those achieving non-trivial regrets on all instances), and has asymptotic regret $\mathcal{C}(f) \ln n$, where $\mathcal{C}(f)$ is an exact characterization of the complexity of $f$. The key step of the algorithm involves hypothesis testing with active data collection. It computes the most economical decisions with which the algorithm collects observations to test whether an estimated instance is indeed correct; thus, the complexity $\mathcal{C}(f)$ is the minimum cost to test the instance $f$ against other instances. Our results, instantiated on concrete problems, recover the classical gap-dependent bounds for multi-armed bandits [Lai and Robbins, 1985] and prior works on linear bandits [Lattimore and Szepesvari, 2017], and improve upon the previous best instance-dependent upper bound [Xu et al., 2021] for reinforcement learning.
BibTeX
@inproceedings{dong2023asymptotic,
  author = {Kefan Dong and Tengyu Ma},
  title = {{Asymptotic Instance-Optimal Algorithms for Interactive Decision Making}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=oGVu9spZaJJ},
}
Figure