Empirical Policy Optimization For \(n\)-player Markov Games

Abstract

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 t

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyzhu2021empirical

Related papers

• Policy Optimization For Markov Games: Unified Framework And Faster Convergence (2022)0.00
• Policy Optimization For Continuous-time Linear-quadratic Graphon Mean Field Games (2025)0.00
• Optimistic Policy Gradient In Multi-player Markov Games With A Single Controller: Convergence Beyond The Minty Property (2023)3.58
• Independent Policy Gradient For Large-scale Markov Potential Games: Sharper Rates, Function Approximation, And Game-agnostic Convergence (2022)0.00
• Faster Last-iterate Convergence Of Policy Optimization In Zero-sum Markov Games (2022)0.00
• Provably Fast Convergence Of Independent Natural Policy Gradient For Markov Potential Games (2023)0.00
• Minimax-optimal Multi-agent RL In Markov Games With A Generative Model (2022)2.26
• Efficiently Computing Nash Equilibria In Adversarial Team Markov Games (2022)0.00