# Scalable and Independent Learning of Nash Equilibrium Policies in n-Player Stochastic Games with Unknown Independent Chains

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 43 references that are in the map.
- First posted on arXiv 4 Dec 2023.

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

- [Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms](https://mlsanity.com/paper/1911.10635/) (2019)
- [Explore no more: Improved high-probability regret bounds for non-stochastic bandits](https://mlsanity.com/paper/1506.03271/) (2015)
- [Independent Policy Gradient Methods for Competitive Reinforcement Learning](https://mlsanity.com/paper/2101.04233/) (2021)
- [Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games](https://mlsanity.com/paper/2106.01969/) (2021)
- [Learning Adversarial MDPs with Bandit Feedback and Unknown Transition](https://mlsanity.com/paper/1912.01192/) (2019)
- [Learning in games with continuous action sets and unknown payoff functions](https://mlsanity.com/paper/1608.07310/) (2016)
- [Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games](https://mlsanity.com/paper/2102.04540/) (2021)
- [Decentralized Q-Learning in Zero-sum Markov Games](https://mlsanity.com/paper/2106.02748/) (2021)
- [Efficiently Solving MDPs with Stochastic Mirror Descent](https://mlsanity.com/paper/2008.12776/) (2020)
- [Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs](https://mlsanity.com/paper/2006.08040/) (2020)
- [A Primal-Dual Approach to Constrained Markov Decision Processes](https://mlsanity.com/paper/2101.10895/) (2021)
- [Primal-Dual π Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems](https://mlsanity.com/paper/1710.06100/) (2017)
- [Fictitious play in zero-sum stochastic games](https://mlsanity.com/paper/2010.04223/) (2020)
- [Learning in Nonzero-Sum Stochastic Games with Potentials](https://mlsanity.com/paper/2103.09284/) (2021)
- [Policy Gradient Methods Find the Nash Equilibrium in N-player General-sum Linear-quadratic Games](https://mlsanity.com/paper/2107.13090/) (2021)
- [Learning Parametric Closed-Loop Policies for Markov Potential Games](https://mlsanity.com/paper/1802.00899/) (2018)
- [Reinforcement Learning in Non-Stationary Discrete-Time Linear-Quadratic Mean-Field Games](https://mlsanity.com/paper/2009.04350/) (2020)
- [Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions](https://mlsanity.com/paper/2207.12463/) (2022)
- [Large Scale Markov Decision Processes with Changing Rewards](https://mlsanity.com/paper/1905.10649/) (2019)
- [Learning Stationary Nash Equilibrium Policies in n-Player Stochastic Games with Independent Chains](https://mlsanity.com/paper/2201.12224/) (2022)
- [Stochastic Games for Smart Grid Energy Management with Prospect Prosumers](https://mlsanity.com/paper/1610.02067/) (2016)
- [Large Player games on Wireless Networks](https://mlsanity.com/paper/1710.08800/) (2017)
- [Finite-horizon Approximations and Episodic Equilibrium for Stochastic Games](https://mlsanity.com/paper/2310.07256/) (2023)

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

- [Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property](https://mlsanity.com/paper/2312.12067/) (2023)

## Abstract (arXiv)

We study a subclass of n-player stochastic games, namely, stochastic games with independent chains and unknown transition matrices. In this class of games, players control their own internal Markov chains whose transitions do not depend on the states/actions of other players. However, players' decisions are coupled through their payoff functions. We assume players can receive only realizations of their payoffs, and that the players can not observe the states and actions of other players, nor do they know the transition probability matrices of their own Markov chain. Relying on a compact dual formulation of the game based on occupancy measures and the technique of confidence set to maintain high-probability estimates of the unknown transition matrices, we propose a fully decentralized mirror descent algorithm to learn an ε-NE for this class of games. The proposed algorithm has the desired properties of independence, scalability, and convergence. Specifically, under no assumptions on the reward functions, we show the proposed algorithm converges in polynomial time in a weaker distance (namely, the averaged Nikaido-Isoda gap) to the set of ε-NE policies with arbitrarily high probability. Moreover, assuming the existence of a variationally stable Nash equilibrium policy, we show that the proposed algorithm converges asymptotically to the stable ε-NE policy with arbitrarily high probability. In addition to Markov potential games and linear-quadratic stochastic games, this work provides another subclass of n-player stochastic games that, under some mild assumptions, admit polynomial-time learning algorithms for finding their stationary ε-NE policies.