Publications
Publications › References ›
2026
Conference papers
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 KB
BibTeX
- 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.