Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Games
Preprint
Abstract
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.Keywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Independent and Decentralized Learning in Markov Potential GamesIEEE Transactions on Automatic Control, 2025
- Convergence of Decentralized Actor-Critic Algorithm in General–Sum Markov GamesIEEE Control Systems Letters, 2024
- Gradient Play in Stochastic Games: Stationary Points, Convergence, and Sample ComplexityIEEE Transactions on Automatic Control, 2024
- Safe multi-agent reinforcement learning for multi-robot controlArtificial Intelligence, 2023
- Provably Efficient Reinforcement Learning in Decentralized General-Sum Markov GamesDynamic Games and Applications, 2022
- Best-response dynamics in zero-sum stochastic gamesJournal of Economic Theory, 2020
- Mastering the game of Go without human knowledgeNature, 2017
- Decentralized Q-Learning for Stochastic Teams and GamesIEEE Transactions on Automatic Control, 2016
- Generalised weakened fictitious playGames and Economic Behavior, 2006
- Fictitious Play Property for Games with Identical InterestsJournal of Economic Theory, 1996