# Robust PAC Learning of Concurrent Stochastic Games

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 56 references that are in the map.
- First posted on arXiv 3 Sep 2026.

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

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Provable Self-Play Algorithms for Competitive Reinforcement Learning](https://mlsanity.com/paper/2002.04017/) (2020)
- [A Sharp Analysis of Model-based Reinforcement Learning with Self-Play](https://mlsanity.com/paper/2010.01604/) (2020)
- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2007.07461/) (2020)
- [Sample Complexity of Robust Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2112.01506/) (2021)
- [A Finite Sample Complexity Bound for Distributionally Robust Q-learning](https://mlsanity.com/paper/2302.13203/) (2023)
- [Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptotics](https://mlsanity.com/paper/2105.03863/) (2021)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Model](https://mlsanity.com/paper/2208.10458/) (2022)
- [Solving Robust Markov Decision Processes: Generic, Reliable, Efficient](https://mlsanity.com/paper/2412.10185/) (2024)
- [Active Coverage for PAC Reinforcement Learning](https://mlsanity.com/paper/2306.13601/) (2023)
- [Automatic Verification of Concurrent Stochastic Systems](https://mlsanity.com/paper/2008.04613/) (2020)
- [Correlated Equilibria and Fairness in Concurrent Stochastic Games](https://mlsanity.com/paper/2201.09702/) (2022)
- [Sample-Efficient Distributionally Robust Multi-Agent Reinforcement Learning via Online Interaction](https://mlsanity.com/paper/2508.02948/) (2025)
- [Distributionally Robust Markov Games with Average Reward](https://mlsanity.com/paper/2508.03136/) (2025)
- [PAC Reinforcement Learning Algorithm for General-Sum Markov Games](https://mlsanity.com/paper/2009.02605/) (2020)
- [Polytopal Stochastic Games](https://mlsanity.com/paper/2502.16208/) (2025)
- [The Complexity of Subgame Perfect Equilibria in Quantitative Reachability Games](https://mlsanity.com/paper/1905.00784/) (2019)
- [Robust Verification of Concurrent Stochastic Games](https://mlsanity.com/paper/2601.12003/) (2026)

## Abstract (arXiv)

We introduce the first Probably Approximately Correct (PAC) learning framework for general-sum concurrent stochastic games (CSGs) with transition uncertainty, while addressing the challenge of Nash equilibrium (NE) existence. Our algorithm maintains data-driven L1 confidence sets over transition kernels and solves a robust CSG to compute a social-welfare optimal varepsilon-NE, using a robust MDP-based exploration mechanism to drive joint state-action coverage. Crucially, we introduce a Nash margin characterisation that enables principled reasoning about equilibrium existence: the framework either returns an varepsilon-approximate NE whose social-welfare value is varepsilon-close to optimal, or provides a sound certificate that no exact NE exists. Under a minimum reachability condition preach>0 over relevant state-action pairs, the algorithm terminates after a polynomial number of trajectory samples, with sample complexity widetildeOleft( Rmax2 H4 |S|2 |A| / (preach varepsilon2) right). Empirical results on benchmark CSGs demonstrate near-optimal performance, correct handling of equilibrium (non-)existence, and sample complexity consistent with theory.