# Satisficing Paths and Independent Multi-Agent Reinforcement Learning in Stochastic Games

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 90 references that are in the map.
- First posted on arXiv 9 Oct 2021.

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

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Trust Region Policy Optimization](https://mlsanity.com/paper/1502.05477/) (2015)
- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [On the Theory of Policy Gradient Methods: Optimality, Approximation, and Distribution Shift](https://mlsanity.com/paper/1908.00261/) (2019)
- [Near-Optimal Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2006.12007/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [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)
- [Online Reinforcement Learning in Stochastic Games](https://mlsanity.com/paper/1712.00579/) (2017)
- [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)
- [Fictitious play in zero-sum stochastic games](https://mlsanity.com/paper/2010.04223/) (2020)
- [Decentralized Learning for Optimality in Stochastic Dynamic Teams and Games with Local Control and Global State Information](https://mlsanity.com/paper/1903.05812/) (2019)
- [Deception in Optimal Control](https://mlsanity.com/paper/1805.03090/) (2018)
- [Optimal Solutions to Infinite-Player Stochastic Teams and Mean-Field Teams](https://mlsanity.com/paper/1808.02962/) (2018)
- [Distributed Inertial Best-Response Dynamics](https://mlsanity.com/paper/1605.00601/) (2016)
- [Optimality of Independently Randomized Symmetric Policies for Exchangeable Stochastic Teams with Infinitely Many Decision Makers](https://mlsanity.com/paper/2008.11570/) (2020)

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

- [Independent and Decentralized Learning in Markov Potential Games](https://mlsanity.com/paper/2205.14590/) (2022)
- [Q-Learning for Stochastic Control under General Information Structures and Non-Markovian Environments](https://mlsanity.com/paper/2311.00123/) (2023)
- [Markov α-Potential Games](https://mlsanity.com/paper/2305.12553/) (2023)
- [Unsynchronized Decentralized Q-Learning: Two Timescale Analysis By Persistence](https://mlsanity.com/paper/2308.03239/) (2023)
- [Paths to Equilibrium in Games](https://mlsanity.com/paper/2403.18079/) (2024)
- [Decentralized Multi-Agent Reinforcement Learning for Continuous-Space Stochastic Games](https://mlsanity.com/paper/2303.13539/) (2023)
- [Playing Markov Games Without Observing Payoffs](https://mlsanity.com/paper/2509.00179/) (2025)
- [Grouped Satisficing Paths in Pure Strategy Games: a Topological Perspective](https://mlsanity.com/paper/2509.23157/) (2025)
- [Actor-Dual-Critic Dynamics for Zero-sum and Identical-Interest Stochastic Games](https://mlsanity.com/paper/2602.00606/) (2026)

## Abstract (arXiv)

In multi-agent reinforcement learning (MARL), independent learners are those that do not observe the actions of other agents in the system. Due to the decentralization of information, it is challenging to design independent learners that drive play to equilibrium. This paper investigates the feasibility of using satisficing dynamics to guide independent learners to approximate equilibrium in stochastic games. For ε ≥ 0, an ε-satisficing policy update rule is any rule that instructs the agent to not change its policy when it is ε-best-responding to the policies of the remaining players; ε-satisficing paths are defined to be sequences of joint policies obtained when each agent uses some ε-satisficing policy update rule to select its next policy. We establish structural results on the existence of ε-satisficing paths into ε-equilibrium in both symmetric N-player games and general stochastic games with two players. We then present an independent learning algorithm for N-player symmetric games and give high probability guarantees of convergence to ε-equilibrium under self-play. This guarantee is made using symmetry alone, leveraging the previously unexploited structure of ε-satisficing paths.