Abstract
This research introduces the first near-optimal algorithms for reinforcement learning in two-player zero-sum Markov games using self-play. By developing Nash V-learning, the authors bridge a significant theoretical gap, matching the information-theoretic lower bound for sample complexity in terms of states and actions. This work demonstrates that agents can learn optimal strategies with significantly fewer samples than previously theorized, moving from a dependence on the product of actions ($A \times B$) to their sum ($A + B$).
Introduction
In single-agent reinforcement learning (RL), the sample complexity—the number of interactions required to find a near-optimal policy—is well-understood. However, multi-agent RL, specifically two-player zero-sum Markov games where a "max-player" and a "min-player" compete, presents a much higher degree of complexity. The objective in these games is to find a Nash Equilibrium, a state where neither player can improve their outcome by unilaterally changing their strategy.
Prior to this work, a substantial gap existed between known upper bounds (the performance of existing algorithms like VI-ULCB) and the theoretical lower bounds. Existing algorithms typically scaled quadratically with the number of states ($S^2$) or the product of actions ($A \times B$). This paper addresses a fundamental question: Can we design algorithms that reach the linear information-theoretic limit of $\Omega(S(A+B))$?
Methods
The authors propose two primary algorithms that utilize self-play—where the algorithm learns by playing against versions of itself—and optimism in the face of uncertainty to encourage exploration of unknown states.
- Optimistic Nash Q-learning: An advancement over classical Nash Q-learning, this algorithm maintains upper and lower confidence bounds for Q-values and employs a Coarse Correlated Equilibrium (CCE) subroutine. While it improves sample complexity to $\tilde{O}(SAB)$, it remains dependent on the product of actions.
- Nash V-learning: The paper's primary contribution, this algorithm integrates Follow-the-Regularized-Leader (FTRL) with standard Q-learning. By focusing updates on V-values (state values) rather than Q-values (state-action values), it successfully decouples the dependence on actions, achieving the target complexity of $\tilde{O}(S(A+B))$.
- Certified Policies: To address the fact that self-play can produce non-Markovian (history-dependent) policies, the authors introduced a "certification" technique. This ensures the extracted policies perform reliably even against a best-response opponent.
Key Results and Insights
The paper successfully closes the sample complexity gap for Markov games. The move from $A \times B$ to $A+B$ represents a significant efficiency gain; for example, in a game where each player has 100 actions, the complexity drops from a factor of 10,000 to 200.
As shown in the table above, Nash V-learning achieves a sample complexity of $\tilde{O}(H^6 S(A+B) / \epsilon^2)$. This matches the information-theoretic lower bound in all problem-dependent parameters ($S, A, B$) except for the polynomial factor of the episode length ($H$). Furthermore, unlike some previous approaches that were computationally prohibitive (PPAD-complete), these new algorithms run in polynomial time.
Another critical insight is the Hardness of Best Response. The authors prove that finding a Nash Equilibrium is computationally easier than finding a Best Response against a fixed, unknown, non-Markovian opponent—the latter being as difficult as the "Learning Parity with Noise" problem in cryptography.
Discussion and Future Work
While this work provides a near-optimal solution for the tabular setting, several avenues for future research remain:
- Function Approximation: The current results apply to discrete, tabular RL. Extending these near-optimal bounds to large state spaces using neural networks (function approximation) is a vital next step.
- The H-Factor: A gap still exists regarding the episode length ($H$), where the upper bound is $H^6$ and the lower bound is $H^3$.
- General-Sum Games: This research focuses on zero-sum games. Providing similar efficiency guarantees for general-sum games, where players may have mutual interests, remains a significant challenge in the field.
Summary updated