2021/10/18 by Yuanheng Zhu, Zhu, Yuanheng, Dongbin Zhao +5
Computer Science · #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.2110.08979
openalex publication_date 2021/10/18 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In single-agent Markov decision processes, an agent can optimize its policy based on the interaction with environment. In multi-player Markov games (MGs), however, the interaction is non-stationary due to the behaviors of other players, so the agent has no fixed optimization objective. In this paper, we treat the evolution of player policies as a dynamical process and propose a novel learning scheme for Nash equilibrium. The core is to evolve one's policy according to not just its current in-game performance, but an aggregation of its performance over history. We show that for a variety of MGs, players in our learning scheme will provably converge to a point that is an approximation to Nash equilibrium. Combined with neural networks, we develop the empirical policy optimization algorithm, that is implemented in a reinforcement-learning framework and runs in a distributed way, with each player optimizing its policy based on own observations. We use two numerical examples to validate the convergence property on small-scale MGs with n≥ 2 players, and a pong example to show the potential of our algorithm on large games.