In single-agent Markov decision processes, an agent
can optimize its policy based on the interaction with the environment.
In multiplayer Markov games (MGs), however, the
interaction is nonstationary due to the behaviors of other players,
so the agent has no fixed optimization objective. The challenge
becomes finding equilibrium policies for all players. In this
research, 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 an empirical policy optimization
algorithm, which 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, and a pong example to show the potential on
large games.