Rational and convergent model-free adaptive learning for team Markov games

In this paper, we address multi-agent decision problems where all agents share a common goal. This class of problems is suitably modeled using finite-state Markov games with identical interests. We tackle the problem of coordination and contribute a new algorithm, coordinated Q-learning (CQL). CQL combines Q-learning with biased adaptive play, a coordination mechanism based on the principle of fictitious-play. We analyze how the two methods can be combined without compromising the convergence of either. We illustrate the performance of CQL in several different environments and discuss several properties of this algorithm. Recent years have witnessed increasing interest in extending reinforcement learning (RL) to multi-agent problems. However, reinforcement learning methods often require the environment to be stationary. If a learning agent interacting with an environment where other agents co-exist can disregard them as part of the environment, there is an implicit violation of the stationarity assumption that can lead to poor convergence of the learning algorithms. Even if convergence is attained, the learned policy can be unsatisfactory. Markov games (also known as stochastic games), understood as extensions of Markov pro