Robust PAC Learning of Concurrent Stochastic Games

[HP26b] Angel Y. He and David Parker. Robust PAC Learning of Concurrent Stochastic Games. In Proc. 40th Annual Conference on Neural Information Processing Systems (NeurIPS'26). To appear. December 2026. pdf bib [Introduces a PAC-learning framework for general-sum concurrent stochastic games, with an implementation building on PRISM-games.]

Downloads
PDF 741 KBBibTeX
Search for this paper
Google · Google Scholar

Abstract

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 ε-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 ε-approximate NE whose social-welfare value is ε-close to optimal, or provides a sound certificate that no exact NE exists. Under a minimum reachability condition p_reach > 0 over relevant state–action pairs, the algorithm terminates after a polynomial number of trajectory samples, with sample complexity O(︁R^2_max H^4 |S|^2 |A|/(p_reach ε^2)). Empirical results on benchmark CSGs demonstrate near-optimal performance, correct handling of equilibrium (non-)existence, and sample complexity consistent with theory.