Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints

Dan Qiao, Yu-Xiang Wang

Introduction

In standard reinforcement learning (RL), algorithms are typically assumed to be "fully adaptive," meaning they can update their decision-making policy after every single interaction with the environment. While this assumption simplifies theoretical analysis, it is often impractical in real-world applications. For instance, in autonomous driving or clinical trials, deploying a new software patch or treatment protocol involves significant overhead, safety checks, and logistical delays. Consequently, data is often collected in large batches, and the policy is updated only a limited number of times.

This constraint is quantified by batch complexity: the number of times an agent is permitted to change its policy over $K$ episodes. While low-adaptivity algorithms have been successfully developed for single-agent Markov Decision Processes (MDPs), the multi-agent setting—specifically two-player zero-sum Markov Games—presents a unique challenge. In these games, an agent must learn to play against an opponent (self-play), where the optimal strategy is a moving target that depends on the opponent's behavior. This paper introduces the first near-optimal algorithms for multi-agent reinforcement learning (MARL) under such adaptivity constraints.

Methodology

The authors propose a novel framework centered on Policy Elimination. Unlike traditional methods that incrementally update a single policy, this framework maintains a "version space" of candidate policies for the max-player and systematically prunes those that are provably sub-optimal based on collected data.

1. Absorbing Markov Games

A primary technical hurdle in MARL is the "uniform convergence" problem—estimating transition dynamics accurately for all possible policy pairs. To address this, the authors construct a surrogate game using Absorbing Markov Games. They identify "infrequent" state-action-state tuples that are statistically difficult to reach and replace them with an "absorbing state" ($s^\dagger$). This simplification ensures that the value function remains a robust approximation of the true game while reducing the complexity of the model estimation.

2. Two-Stage Exploration

To gather high-quality data with minimal updates, the algorithm employs a two-stage exploration strategy:

  • Crude Exploration: A layer-by-layer approach identifies which regions of the state space are easily accessible.
  • Fine Exploration: Utilizing the crude model, the algorithm solves for a "uniformly explorative" policy. This policy is designed to collect data that refines transition estimates across the most relevant parts of the game tree.

3. Log-Log Batching Schedule

To achieve near-optimality with minimal synchronization, the algorithm utilizes an exponentially increasing batch size schedule, defined as $T^{(k)} = K^{1-1/2^k}$. This allows the agent to reach near-optimal regret with a batch complexity that scales only logarithmically with the number of episodes ($O(H + \log \log K)$).

Key Results

The paper provides rigorous mathematical proofs for the performance of the proposed algorithm in tabular two-player zero-sum Markov Games:

  • Regret Bound: The algorithm achieves a regret of $\tilde{O}(\sqrt{H^2 S^2 ABT})$, where $T$ is the total number of steps. This performance matches the theoretical efficiency of fully adaptive model-based algorithms, proving that adaptivity constraints do not necessarily require a sacrifice in cumulative reward.
  • Batch Complexity: The algorithm requires only $O(H + \log \log K)$ batches. In practical terms, for a million episodes ($K=10^6$), the policy only needs to be updated approximately 5 times.
  • Sample Complexity in Reward-Free MARL: In settings where the agent explores without a reward signal to learn environment dynamics, the algorithm identifies an $\epsilon$-approximate Nash policy using $\tilde{O}(H^3 S^2 AB / \epsilon^2)$ episodes. This represents a significant improvement (a factor of $H^2$) over previous state-of-the-art results.

Discussion and Limitations

While this work establishes a new theoretical frontier for low-adaptivity MARL, several challenges remain for practical implementation. First, the computational efficiency of the policy elimination step is high; representing and iterating over the policy space in general Markov Games can be exponentially expensive in terms of the number of states ($S$) and actions ($A$).

Second, the current results are limited to tabular RL, where the state and action spaces are finite and discrete. Extending these guarantees to high-dimensional settings that require function approximation (such as Deep RL) is a critical next step. Finally, the "absorbing state" construction, while theoretically elegant, requires careful tuning of "infrequency" thresholds to be effective in real-world simulators. Despite these hurdles, the paper demonstrates that near-optimal self-play is possible with an incredibly small number of policy deployments, bridging the gap between theoretical RL and practical deployment constraints.

Summary updated

BibTeX
@inproceedings{qiao2024near,
  author = {Dan Qiao and Yu-Xiang Wang},
  title = {{Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=pPNMhdYMaz},
}
Figure