aiqbench analysis
This research presents a scalable, fully online learning algorithm for multi-agent stochastic games that avoids the exponential complexity typically associated with joint state spaces. By leveraging local information and independent chain structures, the method achieves optimal regret bounds without requiring synchronized episodes or global coordination. The work advances theoretical foundations for decentralized machine learning in dynamic environments where transition dynamics are unknown.
Fully Online Decentralized Learning in Stochastic Games with Unknown Independent Chains
arXiv:2610.01181v1 Announce Type: new Abstract: We consider stochastic games with independent controlled chains and unknown transition kernels, where players observe only their local states and realized payoffs. We develop a fully online, decentralized, and uncoordinated mirror-descent algorithm that operates in the dual space of occupancy measures for approximating stationary Nash equilibrium (NE) policies. The algorithm uses a single transition/reward sample at every primitive time step, relies only on local information, and requires neither coverage of the joint state space nor synchronized episodes. Under uniform-ergodicity and finite-coverage assumptions, we show that, with high probability, the time-averaged fixed-comparator regret decays at the canonical $O(T^{-1/2})$ rate, up to logarithmic factors and polynomial dependence on the game parameters. In particular, the complexity depends on the cover times of the individual local state spaces rather than the product state space, avoiding exponential dependence on the number of players and the sizes of the joint state and action spaces. The resulting finite-time regret bound further yields an approximate coarse-correlated-equilibrium guarantee, which is natural for arbitrary reward functions since computing a stationary $\epsilon$-NE is PPAD-hard in this setting. Under an additional global variational-stability condition, we show that the same fully online algorithm converges asymptotically in the last iterate to a stationary $\epsilon$-NE. Our results provide a fully online and scalable learning framework for stochastic games with unknown independent chains. The algorithm can also be viewed as a primal-dual framework for Markov games that exploits the independence and local structure of the players' controlled transition chains.
Abstract:We consider stochastic games with independent controlled chains and unknown transition kernels, where players observe only their local states and realized payoffs. We develop a fully online, decentralized, and uncoordinated mirror-descent algorithm that operates in the dual space of occupancy measures for approximating stationary Nash equilibrium (NE) policies. The algorithm uses a single transition/reward sample at every primitive time step, relies only on local information, and requires neither coverage of the joint state space nor synchronized episodes. Under uniform-ergodicity and finite-coverage assumptions, we show that, with high probability, the time-averaged fixed-comparator regret decays at the canonical $O(T^{-1/2})$ rate, up to logarithmic factors and polynomial dependence on the game parameters. In particular, the complexity depends on the cover times of the individual local state spaces rather than the product state space, avoiding exponential dependence on the number of players and the sizes of the joint state and action spaces. The resulting finite-time regret bound further yields an approximate coarse-correlated-equilibrium guarantee, which is natural for arbitrary reward functions since computing a stationary $\epsilon$-NE is PPAD-hard in this setting. Under an additional global variational-stability condition, we show that the same fully online algorithm converges asymptotically in the last iterate to a stationary $\epsilon$-NE. Our results provide a fully online and scalable learning framework for stochastic games with unknown independent chains. The algorithm can also be viewed as a primal-dual framework for Markov games that exploits the independence and local structure of the players' controlled transition chains.
Machine Learning (cs.LG); Computer Science and Game Theory (cs.GT); Multiagent Systems (cs.MA); Systems and Control (eess.SY); Optimization and Control (math.OC)
arXiv:2610.01181 [cs.LG]
(or arXiv:2610.01181v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2610.01181 arXiv-issued DOI via DataCite (pending registration)
From: S. Rasoul Etesami [view email] [v1] Thu, 1 Oct 2026 06:56:20 UTC (1,228 KB)
Full text under the publisher's open licence · 293 words
Related coverage
High-Probability Nash Regret for Decentralized Learning in Markov $\alpha$-Potential Games: Episodic and Fully Online Asynchronous Algorithms with Applications to Markov Congestion Games
arXiv · Sep 15, 2026
Optimal Regret for Online Market Making with Limit Order Book
arXiv · Oct 8, 2026
Regret Minimization for Piecewise Linear Rewards: Contracts, Auctions, and Beyond
arXiv · Jul 21, 2026
Grantmakers aren’t afraid to die
LessWrong · Sep 17, 2026