2024/02/02 by Mao, Weichao, Qiu, Haoran, Wang, Chen +3 · 1 citation
#Artificial Intelligence (cs.AI) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.2403.07890
No-regret learning has a long history of being closely connected to game theory. Recent works have devised uncoupled no-regret learning dynamics that, when adopted by all the players in normal-form games, converge to various equilibrium solutions at a near-optimal rate of \widetildeO(T-1), a significant improvement over the O(1/√(T)) rate of classic no-regret learners. However, analogous convergence results are scarce in Markov games, a more generic setting that lays the foundation for multi-agent reinforcement learning. In this work, we close this gap by showing that the optimistic-follow-the-regularized-leader (OFTRL) algorithm, together with appropriate value update procedures, can find \widetildeO(T-1)-approximate (coarse) correlated equilibria in full-information general-sum Markov games within T iterations. Numerical results are also included to corroborate our theoretical findings.