Approximate Dynamic Programming for Two-Player Zero-Sum Markov Games

Julien Pérolat, Bruno Scherrer, Bilal Piot, Olivier Pietquin

Scaling up competitive multi-agent reinforcement learning requires rigorous theoretical foundations. Bridging the gap between single-agent decision-making and complex two-player games, this research provides a unified error analysis for approximate dynamic programming (ADP) in Markov Games.

Specifically, the work introduces a novel $L_p$-norm error propagation analysis for major Reinforcement Learning algorithms applied to two-player zero-sum games. It also presents AGPI-Q, a practical, data-driven algorithm capable of learning Nash equilibria from batch data without requiring a perfect model of the game's underlying rules.

The Challenge of Error Propagation in Markov Games

In single-agent environments, decision-making is typically modeled using Markov Decision Processes (MDPs). However, when two agents compete, the framework expands to Markov Games (MGs). To solve large-scale games where visiting every state is computationally impossible, practitioners rely on Approximate Dynamic Programming (ADP).

The core challenge in ADP is that every approximation of a value function or a "greedy" policy introduces a small error. Because these algorithms are iterative, these tiny errors can accumulate and "explode" over time. While error propagation is well-understood for single-agent MDPs using $L_p$-norms (which practically relate to standard machine learning loss functions like Mean Squared Error), the theory for two-player games has historically been restricted to the less-practical $L_\infty$-norm (maximum error) or limited to highly specific algorithms.

Algorithmic Framework: AGPI and AGPI-Q

To address these limitations, the research focuses on three algorithmic frameworks adapted for games:

  1. Approximate Value Iteration (AVI): Updating values step-by-step.
  2. Approximate Policy Iteration (API): Fully evaluating a policy before improving it.
  3. Approximate Generalized Policy Iteration (AGPI): A hybrid approach that interpolates between AVI and API using a parameter $m$, which dictates the number of evaluation steps.

Key Contributions: * Unified Theory: The authors prove that AGPI generalizes both AVI and API, providing a single, unified bound for how errors propagate in $L_p$-norm. * AGPI-Q Algorithm: They propose a practical "Fitted-Q" style algorithm tailored for games. It takes a batch of transition data (state, actions, reward, next state) and uses a regression-based approach to find the minimax equilibrium. * Greedy Step via Linear Programming: In each iteration, the algorithm solves a series of mini-matrix games (one for each data point) using linear programming to find the local Nash equilibrium.

Experimental Validation: The Game of Alesia

The algorithm's efficacy is evaluated on a simultaneous two-player game called Alesia. In this game, two players manage a finite budget and place bets to move a token on a 5-box board. The player who bets more moves the token toward their side, making it a strategic game of resource management and bluffing.

Using synthetic datasets of varying sizes ($N = 2500, 5000, 10000$ samples), the researchers tested how well AGPI-Q approximates the true value function compared to an exact solution.

Average error vs. Iterations for varying evaluation steps ($m$)

Empirically, AGPI-Q successfully converged to the true value function. The experiments also highlighted the power of the parameter $m$. This parameter acts as a "speed vs. stability" knob. As demonstrated in the results, using a larger $m$ (more evaluation steps) significantly speeds up the initial learning phase and reduces the average error rapidly in early iterations. However, theoretical bounds and empirical observations suggest that high $m$ values might lead to a slightly higher "error floor" asymptotically if the sample size is small.

Theoretical Insights and Limitations

Beyond empirical success, the paper offers several deep theoretical insights:

  • The Non-Linearity Hurdle: In single-agent MDPs, the Bellman operator is affine, simplifying proofs. In zero-sum games, the operator involves a non-linear max-min calculation. The authors developed advanced proof techniques to handle this non-linearity within $L_p$ spaces.
  • Feature-Free Learning: By pairing AGPI-Q with non-parametric models (like CART trees), the algorithm can learn the structure of a game directly from data, eliminating the need for human-engineered features.
  • Error Bounds: The derived bound shows that the final policy's performance loss is proportional to the approximation errors, scaled by a factor of $\frac{1}{(1-\gamma)^2}$ (where $\gamma$ is the discount factor). This matches the best-known bounds for single-agent MDPs, proving that games are not inherently "looser" in their error propagation.

Limitations and Future Directions: Like most ADP theory, the bounds are highly sensitive to the discount factor $\gamma$. As $\gamma$ approaches 1 (indicating a high priority on future rewards), the error bounds inflate significantly. The authors suggest that employing non-stationary policies (policies that change over time) could help break this $\gamma$ sensitivity. Finally, while Alesia serves as a strong proof-of-concept, future work will need to scale AGPI-Q to larger, real-world datasets and more complex game architectures.

Summary updated

Abstract

This paper provides an analysis of error propagation in Approximate Dynamic Programming applied to zero-sum two-player Stochastic Games. We provide a novel and unified error propagation analysis in...
BibTeX
@inproceedings{perolat2015approximate,
  author = {Julien Pérolat and Bruno Scherrer and Bilal Piot and Olivier Pietquin},
  title = {{Approximate Dynamic Programming for Two-Player Zero-Sum Markov Games}},
  booktitle = {International Conference on Machine Learning},
  year = {2015},
  url = {https://openreview.net/forum?id=SJbaSsb_bH},
}
Figure