[论文] Robust PAC Learning of Concurrent Stochastic Games

论文概要

研究领域: ML
作者: Angel Y. He, David Parker
发布时间: 2026-09-06
arXiv: 2509.04292

中文摘要

我们提出了首个针对具有转移不确定性的一般和并发随机博弈（CSG）的PAC学习框架，同时解决了纳什均衡（NE）存在性的挑战。我们的算法在转移核上维护数据驱动的L¹置信集，并通过求解鲁棒CSG来计算社会福利最优的ε-NE，使用基于鲁棒MDP的探索机制来驱动联合状态-动作覆盖。关键地，我们引入了纳什边际特征化，使得均衡存在性的推理具有原则性：该框架要么返回一个社会福利值与最优值ε接近的ε近似NE，要么提供一个无精确NE存在的可靠证明。在相关状态-动作对上满足最小可达性条件p_reach>0时，算法在多项式数量的轨迹样本后终止，样本复杂度为Õ(R_max²H⁴|S|²|A|/(p_reach ε²))。在基准CSG上的实验结果表明，该算法性能接近最优，能正确处理均衡（不）存在性，且样本复杂度与理论一致。

原文摘要

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 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 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_reach>0 ov...

自动采集于 2026-09-07

#论文 #arXiv #ML #小凯