Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Games
Not on the map. Why?
Abstract (arXiv)
We propose a novel independent and payoff-based learning framework for stochastic games that is model-free, game-agnostic, and gradient-free. The learning dynamics follow a best-response-type actor-critic architecture, where agents update their strategies (actors) using feedback from two distinct critics: a fast critic that intuitively responds to observed payoffs under limited information, and a slow critic that deliberatively approximates the solution to the underlying dynamic programming problem. Crucially, the learning process relies on non-equilibrium adaptation through smoothed best responses to observed payoffs. We establish convergence to (approximate) equilibria in two-agent zero-sum and multi-agent identical-interest stochastic games over an infinite horizon. This provides one of the first payoff-based and fully decentralized learning algorithms with theoretical guarantees in both settings. Empirical results further validate the robustness and effectiveness of the proposed approach across both classes of games.
Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 29 of its 45 references that are in the map. First posted on arXiv 31 Jan 2026.
Builds on
29 of 45 references.
References · 29
- 2019Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmscited by 555
- 2016Safe, Multi-Agent, Reinforcement Learning for Autonomous Drivingcited by 301
- 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 112
- 2021V-Learning -- A Simple, Efficient, Decentralized Algorithm for Multiagent RLcited by 111
- 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 104
- 2018Learning to Navigate in Cities Without a Mapcited by 103
- 2021Independent Policy Gradient Methods for Competitive Reinforcement Learningcited by 97
- 2021Global Convergence of Multi-Agent Policy Gradient in Markov Potential Gamescited by 89
- 2021Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Gamescited by 66
- 2021When Can We Learn General-Sum Markov Games with a Large Number of Players Sample-Efficiently?cited by 63
- 2022Independent Policy Gradient for Large-Scale Markov Potential Games: Sharper Rates, Function Approximation, and Game-Agnostic Convergencecited by 54
- 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
17 more
- 2022The Complexity of Markov Equilibrium in Stochastic Gamescited by 45
- 2021Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov Gamescited by 42
- 2015Decentralized Q-Learning for Stochastic Teams and Gamescited by 34
- 2021Independent Natural Policy Gradient Always Converges in Markov Potential Gamescited by 34
- 2021Gradient play in stochastic games: stationary points, convergence, and sample complexitycited by 32
- 2022On Almost Sure Convergence Rates of Stochastic Gradient Methodscited by 32
- 2023Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedbackcited by 28
- 2020Fictitious play in zero-sum stochastic gamescited by 24
- 2021Independent Learning in Stochastic Gamescited by 20
- 2022Independent and Decentralized Learning in Markov Potential Gamescited by 19
- 2021Provably Efficient Policy Optimization for Two-Player Zero-Sum Markov Gamescited by 18
- 2023A Finite-Sample Analysis of Payoff-Based Independent Learning in Zero-Sum Stochastic Gamescited by 15
- 2021Satisficing Paths and Independent Multi-Agent Reinforcement Learning in Stochastic Gamescited by 9
- 2021Best-Response Dynamics and Fictitious Play in Identical-Interest and Zero-Sum Stochastic Gamescited by 9
- 2022Fictitious Play in Markov Games with Single Controllercited by 9
- 2023Multi-Player Zero-Sum Markov Games with Networked Separable Interactionscited by 8
- 2024Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Gamescited by 2
Built on by
Not cited yet.