Summary
The paper addresses how groups of decision-makers can learn stable ways to act together in complex systems modeled as Markov games. The authors develop new algorithms that allow these players to update their strategies over time, either in separate rounds or continuously and independently. Their methods come with mathematical guarantees that the players' combined strategies will approach stable outcomes called Nash equilibria without depending on difficult-to-measure factors. They also apply these ideas to scheduling jobs on machines to improve distributed decision-making in practical settings.
What this means in practice
- •For distributed system engineers: Use scalable decentralized algorithms to learn stable coordination policies for resource-sharing systems modeled as Markov congestion games.
- •For operations managers in manufacturing: Implement online job scheduling strategies on stochastic machines that adapt to changing conditions while ensuring stable task dispatching.
Abstract
We study decentralized learning of Nash equilibria (NE) in infinite-horizon discounted Markov games under bandit feedback, focusing on Markov $α$-potential games. We develop KL-projected natural policy gradient (NPG) algorithms in two settings: an episodic setting with frozen policies during sampling and a fully online setting in which players receive a single realized cost sample per time step and update their policies asynchronously along a continuing trajectory. We establish finite-time high-probability NE regret bounds of order $\widetilde O(T^{-1/4})$ and $\widetilde O(T^{-2/15})$ for the episodic and fully online settings, respectively, up to fixed approximation terms. Crucially, our bounds eliminate the distribution-mismatch coefficient, which can scale prohibitively with the size of the state space, while accommodating potential approximation, estimation-oracle bias, and transition sensitivity. We further identify a state-wise potential structure that yields sharper guarantees with additive dependence on the potential approximation error $α$. We specialize the framework to independent-resource Markov congestion games (IMCGs), establish their approximate-potential and transition-sensitivity properties, and construct decentralized estimation oracles from realized costs. As an application, we introduce strategic online job scheduling on stochastic machines and obtain a scalable decentralized algorithm for learning stable dispatching policies. Overall, our results provide the first finite-time high-probability NE regret guarantees for fully online asynchronous decentralized learning in Markov $α$-potential games, remove distribution-mismatch coefficients from the regret bounds, accommodate fixed estimation-oracle bias, and provide scalable decentralized learning with finite-time guarantees for IMCGs.