Decentralized Bandit Learning of Markov Perfect Equilibria

Felix Höfer; H. Mete Soner

cs.LGOct 9, 2026

Decentralized Bandit Learning of Markov Perfect Equilibria

Authors: Felix Höfer, H. Mete Soner

Organizations: Booth School of Business, The University of Chicago, Chicago, IL, 60637, USA · Department of Operations Research and Financial Engineering, Princeton University, Princeton, NJ, 08540, USA

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.

Figures & tables

Panel of Figure 1 — Figure 1: State transitions for two servers ( $N=2$ ) and total capacity $k=4$ . Each node $(\ell,S)$ records the number of waiting jobs and the set of busy servers. Blue arrows represent arrivals and red arrows service completions. Self-transitions, including rejected arrivals at full capacity, are omitted.

Explore similar work

High-Probability Nash Regret for Decentralized Learning in Markov $α$ -Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
Sep 14, 2026S. Rasoul EtesamiPolicy Gradient Asynchronous RL
Department of Industrial and Systems Engineering Coordinated Science Laboratory University of Illinois Urbana-Champaign, Urbana, IL, USA
Independent Reinforcement Learning in Discounted Markov Games
Sep 1, 2026Asrin Efe Yorulmaz, Ugur Aydin, Tamer BasarReinforcement Learning Game Theory
Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign, Urbana, IL, 61801, USA
Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains
Oct 1, 2026S. Rasoul EtesamiGame Theory Online Mirror Descent
Department of Industrial and Systems Engineering, Coordinated Science Laboratory University of Illinois Urbana-Champaign, Urbana, IL, USA 61801

Sep 14, 2026J/K move · Enter open · S save

High-Probability Nash Regret for Decentralized Learning in Markov $α$ -Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games

S. Rasoul Etesami

Department of Industrial and Systems Engineering Coordinated Science Laboratory University of Illinois Urbana-Champaign, Urbana, IL, USA

Policy Gradient Asynchronous RL Game Theory Decentralized MARL Nash Equilibrium Computation

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

High-Probability Nash Regret for Decentralized Learning in Markov ααα-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games

Independent Reinforcement Learning in Discounted Markov Games

Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains

High-Probability Nash Regret for Decentralized Learning in Markov $α$ -Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games