Search papers, labs, and topics across Lattice.
This paper introduces a novel PAC learning framework tailored for general-sum concurrent stochastic games (CSGs) that accounts for transition uncertainty and Nash equilibrium (NE) existence. The proposed algorithm leverages data-driven $L^1$ confidence sets and a robust MDP-based exploration mechanism to compute a social-welfare optimal $\varepsilon$-NE, ensuring that either an approximate NE is found or a certificate of non-existence is provided. Empirical evaluations confirm the algorithm's near-optimal performance and validate its theoretical sample complexity, demonstrating its effectiveness in practical scenarios.
The framework not only guarantees the discovery of an approximate Nash equilibrium but also certifies when no exact equilibrium exists, redefining our approach to equilibrium analysis in 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 $\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.
