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

By Julien Pérolat, Bruno Scherrer, Bilal Piot, Olivier Pietquin. 2015

129 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Multi-agent Reinforcement Learning in Sequential Social Dilemmas (2017, methodology): “Several algorithms and analyses have been developed for the two-player zero-sum case [22, 27, 28, 29, 30].”
Robust Adversarial Reinforcement Learning (2017, background): “The adversarial setting we propose can be expressed as a two player γ discounted zero-sum Markov game (Littman, 1994; Perolat et al., 2015).”
Actor-Critic Policy Optimization in Partially Observable Multiagent Environments (2018, background): “Much work in classical MARL focuses on Markov games where the environment is fully observable and agents take actions simultaneously, which in some cases admit Bellman operators [55, 103, 70, 69].”
Algorithms for computing strategies in two-player simultaneous move games (2016, unknown): “approximation error for sampling techniques in discounted Markov games are presented in [21], and new bounds for approximate dynamic programming have also been recently shown [22].”
From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization (2020, background): “Generally speaking, in the sequential setting, learning in games can be addressed by either approximate dynamic programming in the perfect information case (Lagoudakis & Parr, 2002; Pérolat et al., 2015; 2016; Pérolat et al., 2016; 2017; Geist et al., 2019), regret minimization algorithms (Zinkevich”
A Theory of Regularized Markov Decision Processes (2019, background): “Notably, the unregularized error propagation analysis of (14) by Perolat et al. (2015) could be easily adapted to the regularized case (much like how the analysis of AMPI directly led to the analysis of Sec.”
Softened Approximate Policy Iteration for Markov Games (2016, unknown): “Adapting the Hoffman & Karp algorithm, belonging to the PI-like algorithms, with function approximation is cumbersome but feasible (Perolat et al., 2015). However, Pollatschek & Avi-Itzhak-like algorithms for MGs with function approximation have been the topic of very little attention except from La”
Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium (2020, methodology): “The work in Lagoudakis and Parr (2012); Perolat et al. (2015); Pérolat et al. (2016b,a,c); Yang et al. (2019) considers function approximation techniques applied to variants of value-iteration methods and establishes ﬁnite-time convergence to the NEs of two-player zero-sum Markov games.”
A Theoretical Analysis of Deep Q-Learning (2019, methodology): “t al. (2018); Srinivasan et al. (2018); Wei et al. (2017) and the references therein. In addition, batch reinforcement learning is also applied to zero-sum Markov games by Lagoudakis and Parr (2002); Perolat et al. (2015); P´erolat et al. (2016a,b); Zhang et al. (2018), which are closely related to ”