Decentralized learning finds stable strategies in complex multiplayer games
Decentralized Bandit Learning of Markov Perfect Equilibria
Machine Learning
Summary
This paper looks at how multiple decision-makers can learn to play a game well without sharing their individual scores, only knowing the overall game state. The authors show that by adding small random tweaks to their choices and updating based on their own rewards, players can almost always settle into a stable and predictable pattern of behavior called a Markov perfect equilibrium. They prove this learning method gradually improves and gets closer to the ideal strategy at a known speed. They also show a version that works for games that end after a fixed number of turns.
What this means in practice
- •For multi-agent system designers: Create decentralized algorithms letting agents learn stable strategies in dynamic settings without sharing reward data.
- •For robotics teams: Coordinate multiple robots in environments where each only receives feedback from its own actions yet adapts to others' behaviors over time.
Authors
Felix Höfer, H. Mete Soner
Abstract
We study decentralized bandit learning in discounted infinite-horizon, general-sum Markov games with continuous actions. Agents observe the public state, but only their own realized rewards, and use simultaneous perturbation stochastic approximation to update their actions. Under strong monotonicity of the negative running-reward gradients and sufficiently small time steps, we prove that the fully decentralized procedure converges almost surely to the unique stationary Markov perfect equilibrium. We obtain an $O(n^{-1/2})$ convergence rate and present a natural extension to episodic finite-horizon learning.