Multi-Agent Q-Learning via Best Choice Dynamics

Motivated by multi-agent Q-learning scenarios, this paper introduces a distributed action selection algorithm that relies on individual agents interacting with local neighbors to learn a joint action. The algorithm, termed Best Choice Dynamics, has each agent communicate its current planned action to its neighbors, who in turn utilize this information to update their own actions. We characterize the convergence and robustness of the algorithm against message losses, showing that it converges to locally optimal joint actions in finite time. We also discuss its relative advantages with respect to message-passing algorithms and best response dynamics regarding convergence guarantees, lack of oscillations, and communication complexity. We illustrate the algorithm performance in various simulation scenarios, including both on-line training and offline training with distributed on-line roll-out.