Empirical Policy Optimization for n-Player Markov Games.

Area of Science:

• Artificial Intelligence
• Game Theory
• Machine Learning

Background:

• Single-agent Markov decision processes (MDPs) allow policy optimization.
• Multiplayer Markov games (MGs) present nonstationary environments due to other players' actions.
• Finding equilibrium policies in MGs is challenging due to the lack of a fixed optimization objective.

Purpose of the Study:

• To propose a novel learning scheme for achieving Nash equilibrium in multiplayer Markov games.
• To address the nonstationarity challenge in MGs by considering historical performance.
• To develop a provably convergent algorithm for approximating Nash equilibrium.

Main Methods:

• Treating the evolution of player policies as a dynamical process.
• Developing a learning scheme that aggregates historical performance for policy evolution.
• Combining neural networks with a reinforcement-learning framework for empirical policy optimization.
• Implementing a distributed system where each player optimizes its policy based on individual observations.

Main Results:

• Demonstrated provable convergence to an approximation of Nash equilibrium for various MGs.
• Validated the convergence property on small-scale MGs using numerical examples.
• Showcased the potential of the algorithm on large-scale games, exemplified by a Pong simulation.

Conclusions:

• The proposed learning scheme effectively approximates Nash equilibrium in multiplayer Markov games.
• The historical performance aggregation method is key to overcoming nonstationarity.
• The empirical policy optimization algorithm shows promise for complex, large-scale reinforcement learning applications.