PreprintCC BY-NC-ND 4.0arXiv
Decentralized Bandit Learning of Markov Perfect Equilibria
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.
Related
- High-Probability Nash Regret for Decentralized Learning in Markov α-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
- Partially Observed Mean Field Games Without Perfect Recall: Optimality Conditions and Equilibria
- Computing Stationary Equilibria in Measure-Dependent Markov Systems
- Quantitative Convergence of Markov Equilibria for Time-Inconsistent Controlled Diffusions
- Scaling Bayesian Bandit Encoding with Shared Learning
BibTeX
@misc{hofer2026decentralized,
title = {{Decentralized Bandit Learning of Markov Perfect Equilibria}},
author = {Felix Höfer and H. Mete Soner},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14333},
eprint = {2610.14333},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14333},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Decentralized Bandit Learning of Markov Perfect Equilibria
AU - Felix Höfer
AU - H. Mete Soner
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.14333
UR - https://arxiv.org/abs/2610.14333
AB - 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.
ER -