首个可证明的博弈学习框架，能判断均衡是否存在并求出近优解。
Robust PAC Learning of Concurrent Stochastic Games
- 基于置信集和鲁棒马尔可夫决策模型，实现数据驱动的博弈学习
- 在合理条件下，样本复杂度为多项式，且能给出均衡存在性证明
- 适用于需验证均衡存在性或追求社会福利最优的多智能体系统
我们提出了首个针对一般和博弈中存在转移不确定性的并发随机博弈（CSGs）的可能近似正确（PAC）学习框架，并解决了纳什均衡（NE）存在性问题。算法通过维护关于转移核的数据驱动$L^1$置信集，求解鲁棒型CSG以计算社会福利最优的$varepsilon$-NE，利用基于鲁棒MDP的探索机制实现联合状态-动作覆盖。关键创新在于引入纳什间距表征，可对均衡存在性进行合理推断：框架要么返回一个社会福利值与最优值$varepsilon$-接近的$varepsilon$-近似均衡，要么提供一个可靠的证明表明精确均衡不存在。在相关状态-动作对满足最小可达性条件 $p_{\mathrm{reach}}>0$ 下，算法在多项式数量轨迹样本后终止，样本复杂度为 $ ildeset{O}( R_{\max}^2 H^4 |S|^2 |A| / (p_{\mathrm{reach}} \varepsilon^2) )$。基准测试实验表明其性能接近最优，准确处理均衡（非）存在性，且样本复杂度符合理论预测。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。