mlsanityData to 14 Oct 2026

Robust PAC Learning of Concurrent Stochastic Games

arXiv 2609.04189 ↗First posted 3 Sep 2026cs.LG cs.GT cs.LOcited by 0

Not on the map. Why?

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.

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

21 of 56 references.

References · 21

  1. 2017Minimax Regret Bounds for Reinforcement Learningcited by 503
  2. 2020Provable Self-Play Algorithms for Competitive Reinforcement Learningcited by 113
  3. 2020A Sharp Analysis of Model-based Reinforcement Learning with Self-Playcited by 105
  4. 2022Robust Reinforcement Learning using Offline Datacited by 96
  5. 2020Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexitycited by 92
  6. 2021Sample Complexity of Robust Reinforcement Learning with a Generative Modelcited by 83
  7. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 36
  8. 2021Towards Theoretical Understandings of Robust Markov Decision Processes: Sample Complexity and Asymptoticscited by 27
  9. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 25
  10. 2024Robust Markov Decision Processes: A Place Where AI and Formal Methods Meetcited by 18
  11. 2022Minimax-Optimal Multi-Agent RL in Markov Games With a Generative Modelcited by 15
  12. 2024Solving Robust Markov Decision Processes: Generic, Reliable, Efficientcited by 11
9 more
  1. 2023Active Coverage for PAC Reinforcement Learningcited by 8
  2. 2020Automatic Verification of Concurrent Stochastic Systemscited by 7
  3. 2022Correlated Equilibria and Fairness in Concurrent Stochastic Gamescited by 4
  4. 2025Sample-Efficient Distributionally Robust Multi-Agent Reinforcement Learning via Online Interactioncited by 3
  5. 2025Distributionally Robust Markov Games with Average Rewardcited by 3
  6. 2020PAC Reinforcement Learning Algorithm for General-Sum Markov Gamescited by 2
  7. 2025Polytopal Stochastic Gamescited by 2
  8. 2019The Complexity of Subgame Perfect Equilibria in Quantitative Reachability Gamescited by 1
  9. 2026Robust Verification of Concurrent Stochastic Gamescited by 1

Built on by

Not cited yet.