面向一般和并发随机博弈的鲁棒 PAC 学习框架

View PDF HTML (experimental)

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.

Comments:	Camera-ready version of a paper accepted to NeurIPS 2026. Main text: 10 pages, 1 figure, 2 tables; Appendix: 22 pages, 2 figures, 1 table. Minor revisions to the experiment compute resources
Subjects:	Machine Learning (cs.LG); Computer Science and Game Theory (cs.GT); Logic in Computer Science (cs.LO); Multiagent Systems (cs.MA)
Cite as:	arXiv:2609.04189 [cs.LG]
	(or arXiv:2609.04189v2 [cs.LG] for this version)
	https://doi.org/10.48550/arXiv.2609.04189 arXiv-issued DOI via DataCite

Submission history

From: Angel He [view email]
[v1] Thu, 3 Sep 2026 17:58:57 UTC (613 KB)
[v2] Tue, 6 Oct 2026 20:04:45 UTC (620 KB)