# Unsynchronized Decentralized Q-Learning: Two Timescale Analysis By Persistence

arXiv: https://arxiv.org/abs/2308.03239 · HTML: https://mlsanity.com/paper/2308.03239/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 39 references that are in the map.
- First posted on arXiv 7 Aug 2023.

## Builds on (most cited first, 14 of 14)

- [A Survey and Critique of Multiagent Deep Reinforcement Learning](https://mlsanity.com/paper/1810.05587/) (2018)
- [Cycles in adversarial regularized learning](https://mlsanity.com/paper/1709.02738/) (2017)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [A Survey of Learning in Multiagent Environments: Dealing with Non-Stationarity](https://mlsanity.com/paper/1707.09183/) (2017)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [Decentralized Q-Learning for Stochastic Teams and Games](https://mlsanity.com/paper/1506.07924/) (2015)
- [Learning in Nonzero-Sum Stochastic Games with Potentials](https://mlsanity.com/paper/2103.09284/) (2021)
- [Independent Learning in Stochastic Games](https://mlsanity.com/paper/2111.11743/) (2021)
- [Independent and Decentralized Learning in Markov Potential Games](https://mlsanity.com/paper/2205.14590/) (2022)
- [Policy-Gradient Algorithms Have No Guarantees of Convergence in Linear Quadratic Games](https://mlsanity.com/paper/1907.03712/) (2019)
- [Decentralized Learning for Optimality in Stochastic Dynamic Teams and Games with Local Control and Global State Information](https://mlsanity.com/paper/1903.05812/) (2019)
- [Dealing With Non-stationarity in Decentralized Cooperative Multi-Agent Deep Reinforcement Learning via Multi-Timescale Learning](https://mlsanity.com/paper/2302.02792/) (2023)
- [Satisficing Paths and Independent Multi-Agent Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/2110.04638/) (2021)

## Built on by (most cited first, 4 of 4)

- [Meta Stackelberg Game: Robust Federated Learning against Adaptive and Mixed Poisoning Attacks](https://mlsanity.com/paper/2410.17431/) (2024)
- [Fully Decentralized Cooperative Multi-Agent Reinforcement Learning: A Survey](https://mlsanity.com/paper/2401.04934/) (2024)
- [Convergence of Decentralized Actor-Critic Algorithm in General-sum Markov Games](https://mlsanity.com/paper/2409.04613/) (2024)
- [Decentralized Bandit Learning of Markov Perfect Equilibria](https://mlsanity.com/paper/2610.14333/) (2026)

## Abstract (arXiv)

Non-stationarity is a fundamental challenge in multi-agent reinforcement learning (MARL), where agents update their behaviour as they learn. Many theoretical advances in MARL avoid the challenge of non-stationarity by coordinating the policy updates of agents in various ways, including synchronizing times at which agents are allowed to revise their policies. Synchronization enables analysis of many MARL algorithms via multi-timescale methods, but such synchronization is infeasible in many decentralized applications. In this paper, we study an unsynchronized variant of the decentralized Q-learning algorithm, a recent MARL algorithm for stochastic games. We provide sufficient conditions under which the unsynchronized algorithm drives play to equilibrium with high probability. Our solution utilizes constant learning rates in the Q-factor update, which we show to be critical for relaxing the synchronization assumptions of earlier work. Our analysis also applies to unsynchronized generalizations of a number of other algorithms from the regret testing tradition, whose performance is analyzed by multi-timescale methods that study Markov chains obtained via policy update dynamics. This work extends the applicability of the decentralized Q-learning algorithm and its relatives to settings in which parameters are selected in an independent manner, and tames non-stationarity without imposing the coordination assumptions of prior work.