{"id":"arxiv/2609.14959","url":"https://arxiv.org/abs/2609.14959","tags":["cs.LG","cs.GT","cs.MA","eess.SY","math.OC"],"score":0,"title":"High-Probability Nash Regret for Decentralized Learning in Markov $α$-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games","domain":"cs.LG","source":"arxiv","authors":["S. Rasoul Etesami"],"reviews":0,"subject":"cs.LG","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-14","reactions":{}}