Approximate dynamic programming for two-player zero-sum Markov games

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

TL;DR

This paper tackles the challenge of finding optimal strategies in complex, multi-agent games (specifically, two-player zero-sum Markov games) where exact solutions are computationally infeasible. They introduce a novel algorithm, AGPI-Q, that extends existing methods to handle these games efficiently and demonstrate its effectiveness on a challenging game called Alesia.

What Problem Does This Paper Address?

Many real-world problems, from robotics to economics, can be modeled as multi-agent systems where multiple agents interact and make decisions. Markov Games (MGs), also known as Stochastic Games (SGs), are a powerful framework for modeling these scenarios, extending the well-established Markov Decision Processes (MDPs) to handle multiple interacting agents. However, for complex games with many states and actions, finding the optimal strategy (a Nash equilibrium) becomes computationally intractable. This paper focuses on two-player zero-sum Markov games, where one player's gain is the other's loss, and aims to develop methods for finding approximate solutions to these games, especially when the game's dynamics are unknown and data is available in batches.

Methods

The paper builds upon the foundation of Approximate Dynamic Programming (ADP), a class of techniques used to find approximate solutions to sequential decision-making problems. They analyze the error propagation of three existing ADP algorithms (Approximate Value Iteration, Approximate Policy Iteration, and Approximate Generalized Policy Iteration) in the context of zero-sum Markov games, extending previous work done for MDPs.

The core contribution is the introduction of AGPI-Q (Approximate Generalized Policy Iteration-Q). This algorithm is an extension of the "Fitted-Q" algorithm, which is known for solving MDPs from data. AGPI-Q is designed for zero-sum two-player Markov games and can learn from batch data without needing to know the game's underlying dynamics beforehand. It's also non-parametric, meaning it doesn't require pre-defined features for the game states, which is a significant advantage for applying it to new problems. The algorithm iteratively refines an approximation of the state-action value function (Q-function) through a greedy step (finding the best immediate action) and an evaluation step (estimating the long-term value of that action).

Datasets

The paper does not introduce new benchmark datasets. Instead, they evaluate their AGPI-Q algorithm on a well-known simultaneous two-player game called Alesia. The experiments involve generating synthetic data (samples of game transitions) from this game.

Key Insights and Ideas

  • Unified Error Analysis: The paper provides a unified theoretical analysis of error propagation for several ADP algorithms in the context of zero-sum Markov games, extending existing work from MDPs. This offers a deeper understanding of why these algorithms work and their limitations.
  • AGPI-Q for Complex Games: The introduction of AGPI-Q provides a practical and theoretically grounded method for tackling complex multi-agent games where exact solutions are out of reach. Its ability to learn from batch data without prior knowledge of dynamics is a significant advancement.
  • Non-Parametric Advantage: The non-parametric nature of AGPI-Q means it can be applied to a wide range of games without requiring domain-specific feature engineering, making it more versatile.
  • Impact of Evaluation Steps (m): Experiments suggest that increasing the number of evaluation steps (m) in AGPI-Q can accelerate convergence to a good approximation of the optimal value, though at the cost of increased computation per iteration. This highlights a trade-off between speed and accuracy.

Key Results

The paper presents a theoretical analysis of error bounds for ADP algorithms in zero-sum Markov games. Empirically, they demonstrate the performance of AGPI-Q on the Alesia game. The results show that AGPI-Q can learn a good approximation of the true value function, with the mean-squared error decreasing over iterations. The figures illustrate that the learned value function closely matches the exact value function, especially for larger sample sizes. The experiments also show that increasing the number of evaluation steps (m) leads to faster convergence in terms of mean-squared error, though the overall error might be higher for larger m at the end of training.

Limitations and Future Work

  • Sensitivity to Discount Factor (γ): The authors acknowledge that the derived error bounds are highly sensitive to the discount factor γ. This is a common issue in ADP, and future work should focus on reducing this impact.
  • Non-Stationary Policies: While not explored in this paper, the authors suggest that exploring non-stationary policies (policies that change over time) could potentially reduce the impact of γ in future work.
  • Large-Scale Games and Real Data: The authors express their intention to apply AGPI-Q to larger-scale games and to test it on real-world data, which would be a crucial step in validating its practical utility.
  • Generalization to More Players/Non-Zero-Sum: The current work is focused on two-player zero-sum games. Extending the analysis and algorithms to games with more players or non-zero-sum interactions would be a natural next step.

Summary updated

Abstract

International audience
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