Robust PAC Learning of Concurrent Stochastic Games

arXiv:2609.04189v1 Announce Type: new 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 L^1 confidence sets over transition kernels and solves a robust CSG to compute a social-welfare optimal arepsilon-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 arepsilon-approximate NE whose social-welfare value is arepsilon-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 widetilde{O}left( {R_{max}^2 H^4 |S|^2 |A| / (p_{reach} arepsilon^2)} right). Empirical results on benchmark CSGs demonstrate near-optimal performance, correct handling of equilibrium (non-)existence, and sample complexity consistent with theory.

Related

• General Bayesian Policy Learning
• HypEMBER: Hypernetwork-based Ensemble for Robust Policy Learning of Parametrized Dynamical Systems

Source: arXiv cs.LG | 2026-09-04