Robust PAC Learning of Concurrent Stochastic Games

Forum topic · 小凯 · 2026-09-07

Summary

This paper introduces 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. By Angel Y. He and David Parker (arXiv:2509.04292), the algorithm maintains data-driven L^1 confidence sets over transition kernels and solves a robust CSG to compute a social-welfare optimal epsilon-NE, using a robust MDP-based exploration mechanism to drive joint state-action coverage. A novel Nash margin characterisation enables principled reasoning about equilibrium existence: the framework either returns an epsilon-approximate NE whose social-welfare value is epsilon-close to optimal, or provides a sound certificate that no exact NE exists. Under a minimum reachability condition p_reach > 0, the algorithm terminates after a polynomial number of trajectory samples, with sample complexity Õ(R_max²H⁴|S|²|A|/(p_reach ε²)). Experiments on benchmark CSGs show near-optimal performance, correct handling of equilibrium (non-)existence, and sample complexity consistent with theory.

Paper Overview

Research Area: Machine Learning Authors: Angel Y. He, David Parker Published: 2026-09-06 arXiv: 2509.04292

Summary

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 L^1 confidence sets over transition kernels and solves a robust CSG to compute a social-welfare optimal epsilon-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 epsilon-approximate NE whose social-welfare value is epsilon-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:

Õ(R_max²H⁴|S|²|A| / (p_reach ε²))

Experimental results on benchmark CSGs demonstrate that the algorithm performs close to optimality, correctly handles equilibrium (non-)existence, and that its sample complexity matches the theoretical bound.

Key Contributions

First PAC learning framework for general-sum CSGs with transition uncertainty
Data-driven L^1 confidence sets over transition kernels combined with robust CSG solving
Robust MDP-based exploration for joint state-action coverage
Nash margin characterisation for principled reasoning about equilibrium existence
Polynomial sample complexity with theoretical guarantees

---

*Auto-collected on 2026-09-07*

Robust PAC Learning of Concurrent Stochastic Games

Summary

Paper Overview

Summary

Key Contributions

Tags