On the Heterogeneity of Independent Learning Dynamics in Zero-sum Stochastic Games

2021/12/12 by Muhammed O. Sayin, Sayin, Muhammed O., K. Alperen Cetiner +1
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Computer Science and Game Theory (cs.GT) #Dynamical Systems (math.DS) #FOS: Computer and information sciences #FOS: Mathematics #Game Theory and Applications #Optimization and Control (math.OC) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2112.06181

openalex publication_date 2021/12/12 · openalex created_date 2021/12/31 · openalex updated_date 2026/07/28

Abstract

We analyze the convergence properties of the two-timescale fictitious play combining the classical fictitious play with the Q-learning for two-player zero-sum stochastic games with player-dependent learning rates. We show its almost sure convergence under the standard assumptions in two-timescale stochastic approximation methods when the discount factor is less than the product of the ratios of player-dependent step sizes. To this end, we formulate a novel Lyapunov function formulation and present a one-sided asynchronous convergence result.

Related

• Convergence of Heterogeneous Learning Dynamics in Zero-sum Stochastic Games
• Fictitious play in zero-sum stochastic games
• On the Global Convergence of Stochastic Fictitious Play in Stochastic Games with Turn-based Controllers
• Two-Timescale Q-Learning with Function Approximation in Zero-Sum Stochastic Games
• A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Games