Robust PAC Learning of Concurrent Stochastic Games
2026-09-03 • Machine Learning
Machine LearningComputer Science and Game TheoryLogic in Computer ScienceMultiagent Systems
AI summaryⓘ
The authors created a learning method for multiplayer games where the rules can change unpredictably and players have different goals. Their method can find a strategy balance point (Nash equilibrium) that is almost the best for everyone, or it can prove when no exact balance exists. They use a way to explore the game safely, ensuring enough information is gathered to learn effectively. Their approach works efficiently with a reasonable amount of gameplay data and was tested successfully on standard game examples.
Probably Approximately Correct (PAC) learningConcurrent Stochastic Games (CSGs)Nash Equilibrium (NE)Transition UncertaintyRobust Markov Decision Processes (MDPs)Social WelfareSample ComplexityExplorationTrajectory Samples
Authors
Angel Y. He, David Parker
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 $\varepsilon$-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 $\varepsilon$-approximate NE whose social-welfare value is $\varepsilon$-close to optimal, or provides a sound certificate that no exact NE exists. Under a minimum reachability condition $p_{\mathrm{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_{\mathrm{reach}} \varepsilon^2)} \right)$. Empirical results on benchmark CSGs demonstrate near-optimal performance, correct handling of equilibrium (non-)existence, and sample complexity consistent with theory.