Value Function Approximation in Zero-Sum Markov Games

By Michail G. Lagoudakis, Ronald E. Parr. 2002

81 citations recorded by the source corpus.

This paper investigates value function approximation in the context of zero-sum Markov games, which can be viewed as a generalization of the Markov decision process (MDP) framework to the two-agent case. We generalize error bounds from MDPs to Markov games and describe generalizations of reinforcement learning algorithms to Markov games. We present a generalization of the optimal stopping problem to a two-player simultaneous move Markov game. For this special problem, we provide stronger bounds and can guarantee convergence for LSTD and temporal difference learning with linear value function approximation. We demonstrate the viability of value function approximation for Markov games by using the Least squares policy iteration (LSPI) algorithm to learn good policies for a soccer domain and a flow control problem.

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, background): “Most previous work on finding policies for Markov games takes the prescriptive view of multiagent learning [26]: that is, it attempts to answer “what should each agent do?” Several algorithms and analyses have been developed for the two-player zero-sum case [22, 27, 28, 29, 30].”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “To embrace general function classes, the framework of batch RL [237, 200, 201, 197, 202, 238] can be adapted to the multi-agent settings, as in the recent works [239, 44].”
From Poincaré Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularization (2020, background): “…speaking, in the sequential setting, learning in games can be addressed by either approximate dynamic programming in the perfect information case (Lagoudakis & Parr, 2002; Pérolat et al., 2015; 2016; Pérolat et al., 2016; 2017; Geist et al., 2019), regret minimization algorithms (Zinkevich et…”
Softened Approximate Policy Iteration for Markov Games (2016, unknown): “This makes Newton-LSPI a very practical algorithm (Lagoudakis & Parr, 2002).”
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.”