Robust PAC Learning of Concurrent Stochastic Games

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 novel robust MDP-based exploration mechanism to drive joint state-action coverage without unilateral control. 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_{\mathrm{reach}}>0$ over all state-action pairs, the algorithm terminates after a polynomial number of interactions, with sample complexity $\tilde{\mathcal{O}}\left(R_{\max }^2{H}^4|S{|}^2|A|/(p_{\mathrm{reach}}{\epsilon }^2)\right)$. Empirical results on benchmark CSGs demonstrate near-optimal performance, correct handling of equilibrium (non-)existence, and sample complexity consistent with theory; implementation available at: https://anonymous.4open.science/r/pg1.