Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity.

Aaron Sidford, Mengdi Wang, Lin F. Yang, Yinyu Ye

Introduction

In the landscape of Reinforcement Learning (RL), the transition from single-agent environments to multi-agent strategic interactions introduces significant theoretical hurdles. While Markov Decision Processes (MDPs) provide a robust framework for single-agent learning, Stochastic Games (SGs) extend this to scenarios where multiple agents influence the environment's state. This paper addresses a fundamental question in RL theory: is learning an optimal strategy in a two-player zero-sum stochastic game fundamentally more difficult than learning in a single-agent MDP?

The authors settle this question for the discounted setting, providing an algorithm that achieves near-optimal sample and time complexity, effectively bridging the gap between MDPs and SGs.

The Challenge of Multi-Agent Dynamics

The primary difficulty in solving SGs compared to MDPs lies in the lack of monotonicity. In a single-agent MDP, improving a policy typically leads to a monotonic increase in the value function. However, in a two-player zero-sum game, the "max" player and "min" player have opposing objectives. If the max player improves their strategy, the min player will adapt their counter-strategy, which can cause the state values to fluctuate wildly.

This instability historically prevented the application of high-efficiency variance reduction techniques—such as those introduced by Sidford et al. (2018) for MDPs—to the multi-agent setting. Without monotonicity, the error bounds used in variance-reduced Q-learning often fail to converge at optimal rates.

Methodology: QVI-MDVSS

The authors introduce QVI-MDVSS (Q-Value Iteration for Monotone Decreasing/Increasing Value-Strategy Sequences). The algorithm overcomes the instability of SGs through three primary mechanisms:

  1. Variance-Reduced Q-Learning: The algorithm employs a two-tier sampling strategy. It first establishes a high-accuracy "anchor" for the value function using a large batch of samples. Subsequent iterations use smaller batches to estimate only the deviations from this anchor, significantly reducing the noise in the updates.
  2. Forced Monotonicity: To stabilize the learning process, the authors apply "one-sided" error bounds. By carefully shifting the value estimates, they ensure that the sequence of values generated by the algorithm is monotonically decreasing (or increasing). This artificial stability allows the algorithm to leverage variance reduction without the risk of oscillatory behavior.
  3. Auxiliary Markovian Strategy: Since the optimal strategy may not be stable during the learning phase, the algorithm constructs a time-dependent "proxy" strategy. This allows the learner to track and bound the accumulation of errors over the horizon of the game.

Key Results and Complexity

The paper provides a rigorous proof that the sample complexity of solving a discounted two-player zero-sum stochastic game is $\tilde{O}((1-\gamma)^{-3}\epsilon^{-2})$ per state-action pair.

  • Optimality: This result matches the information-theoretic lower bound $\Omega((1-\gamma)^{-3}\epsilon^{-2})$ established by Azar et al. (2013) for single-player MDPs. This implies that, from a sampling perspective, learning to play against an optimal opponent is no harder than learning to navigate a static environment.
  • Efficiency: Beyond sample complexity, the algorithm is computationally efficient. Its runtime is nearly linear in the number of samples, and its space complexity is nearly linear in the number of state-action pairs ($|S||A|$).
  • Generative Model: These bounds hold under the "generative model" assumption, where the learner can sample transitions from any state-action pair at will.

Discussion and Future Directions

While this work represents a major milestone, it also highlights several avenues for future research. The current algorithm is designed for turn-based games. While turn-based games can technically encode simultaneous-move games, a direct and potentially more efficient treatment of simultaneous settings remains an open area.

Furthermore, the reliance on a generative model limits immediate application to "online" RL, where an agent must learn from continuous trajectories. Finally, the zero-sum nature of the two-player interaction is central to the proof; extending these near-optimal bounds to general-sum games or $N$-player environments involves overcoming the inherent complexity of finding Nash equilibria in those settings.

In conclusion, this research provides a blueprint for generalizing advanced MDP techniques to multi-agent settings, proving that strategic interaction does not necessarily impose a higher sample-complexity tax.

Summary updated

Abstract

In this paper, we settle 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 due to Azar et al (2013). We achieve our results by showing how to generalize a near-optimal Q-learning based algorithms for MDP, in particular Sidford et al (2018), to two-player strategy computation algorithms. This overcomes limitations of standard Q-learning and strategy iteration or alternating minimization based approaches and we hope will pave the way for future reinforcement learning results by facilitating the extension of MDP results to multi-agent settings with little loss.
BibTeX
@inproceedings{sidford2020solving,
  author = {Aaron Sidford and Mengdi Wang and Lin F. Yang and Yinyu Ye},
  title = {{Solving Discounted Stochastic Two-Player Games with Near-Optimal Time and Sample Complexity.}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2020},
  url = {https://openreview.net/forum?id=r3kJz1juFv},
}
Figure