Value Function Approximation in Zero-Sum Markov Games

2012/12/12 by Michail G. Lagoudakis, Lagoudakis, Michail, Ronald Parr +1 · 6 citations
Computer Science · Decision Sciences · #Reinforcement Learning in Robotics #Formal Methods in Verification #Simulation Techniques and Applications

paper · pdf · doi:10.48550/arxiv.1301.0580

Abstract

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.

Cited by

• Deep SOR Minimax Q-learning for Two-player Zero-sum Game
• Actor-Critic Provably Finds Nash Equilibria of Linear-Quadratic Mean-Field Games
• On Reinforcement Learning for Turn-based Zero-sum Markov Games
• A Multi-Resolution Dynamic Game Framework for Cross-Echelon Decision-Making in Cyber Warfare
• Multi-agent Reinforcement Learning in Sequential Social Dilemmas
• Policy Optimization Provably Converges to Nash Equilibria in Zero-Sum Linear Quadratic Games

Related

• Towards General Function Approximation in Zero-Sum Markov Games
• Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium
• A New Policy Iteration Algorithm For Reinforcement Learning in Zero-Sum Markov Games
• Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Games
• Policy Optimization for Markov Games: Unified Framework and Faster Convergence