Abstract
This paper settles the sampling complexity of solving discounted two-player turn-based zero-sum stochastic games up to polylogarithmic factors. Given a stochastic game with discount factor $\gamma \in (0,1)$, we provide an algorithm that computes an $\epsilon$-optimal strategy with high probability given $\tilde{O}((1 - \gamma)^{-3} \epsilon^{-2})$ samples from the transition function for each state-action pair. Our algorithm runs in time nearly linear in the number of samples and uses space nearly linear in the number of state-action pairs. As stochastic games generalize Markov decision processes (MDPs), our runtime and sample complexities are optimal. We achieve these results by generalizing near-optimal Q-learning based algorithms for MDPs to two-player strategy computation, overcoming the limitations of standard Q-learning and strategy iteration approaches.
Introduction
In reinforcement learning (RL), Markov Decision Processes (MDPs) serve as the standard framework for single-agent interaction. However, many complex environments—ranging from competitive trading to cybersecurity—are better modeled as Stochastic Games. In these settings, two players (a "max" player and a "min" player) take turns, each attempting to optimize their own outcome in a zero-sum environment.
While researchers have identified "near-optimal" algorithms for MDPs that use the minimum possible number of data samples to find an effective strategy, a significant theoretical gap has persisted for two-player games. Previous methods were often computationally slower, required more data, or relied on restrictive assumptions. This paper introduces a new algorithm, QVI-MDVSS, which proves that solving two-player stochastic games is not fundamentally harder than solving single-player MDPs from a sampling perspective.
The Challenge of Min-Max Dynamics
The primary difficulty in extending MDP results to games lies in the "min-max" nature of the objective. In a single-player MDP, value functions tend to behave monotonically, improving predictably as the agent learns. In a game, one player's gain is another's loss. This adversarial interaction destroys the standard mathematical properties (such as the monotonicity of the Bellman operator) used to guarantee the efficiency of RL algorithms. To bridge this gap, the authors had to develop a method to stabilize the learning process despite the lack of inherent monotonicity.
The QVI-MDVSS Algorithm
The proposed algorithm, Q-Value Iteration with Monotone Decreasing Value-Strategy Sequences (QVI-MDVSS), is built upon three technical pillars:
- Generative Model (The Oracle): The algorithm assumes access to a simulator where it can query any state-action pair and receive a sample of the next state. This allows for targeted data collection.
- Variance Reduction: To achieve high sample efficiency, the algorithm incorporates sophisticated variance reduction techniques adapted from recent MDP research. This allows the agent to "clean up" the noise in its estimates of the game's value, preventing random fluctuations from derailing convergence.
- Monotone Sequences: To solve the stability problem, the authors designed the algorithm to maintain a sequence of strategies and values that decrease monotonically. By shifting estimates slightly using "one-sided error" bounds, the algorithm ensures it always approaches the optimal Nash Equilibrium from a consistent direction.
Key Insights: Complexity Parity
The most significant contribution of this work is the realization of Complexity Parity. The research demonstrates that the sample complexity for two-player games is identical to single-player MDPs (up to logarithmic factors). This suggests that the presence of an adversary does not increase the fundamental data requirements for learning an optimal policy.
To prove this, the authors introduced the concept of a proxy Markovian strategy. This is a time-dependent strategy that acts as a stable reference point, allowing the researchers to track error accumulation more effectively than traditional methods. This technique allows the algorithm to be near-optimal in three dimensions simultaneously: Time (linear to the number of samples), Space (proportional to the number of states and actions), and Samples (matching the theoretical minimum).
Formal Results
The paper provides a rigorous guarantee for the QVI-MDVSS algorithm. To find an $\epsilon$-optimal strategy with high probability, the algorithm requires:
$$O\left(\frac{|S||A|}{(1-\gamma)^3 \epsilon^2}\right) \text{ samples}$$
Where:
- $|S||A|$ is the number of state-action pairs.
- $\gamma$ is the discount factor.
- $\epsilon$ is the desired accuracy.
This result matches the lower bound established by Azar et al. (2013) for single-player MDPs. Because games are a generalization of MDPs, this algorithm is as efficient as physically possible under the generative model assumption.
Limitations and Future Directions
While this work settles a major theoretical question, several avenues for future research remain:
- Online Exploration: The current algorithm relies on a generative model (a simulator). In many real-world tasks, agents must learn through "online" exploration where they cannot jump to arbitrary states.
- Multi-Agent Scaling: The paper focuses on turn-based, two-player zero-sum games. Extending these optimal bounds to simultaneous-move games, non-zero-sum games, or settings with more than two players remains an open challenge.
- Practical Constants: While the asymptotic complexity is optimal, the absolute constants within the algorithm may be large, which could impact performance in practical, small-scale applications.
Summary updated