arXiv:2609.04189v2 cs.LG

동시 확률 게임의 강건한 PAC 학습

Robust PAC Learning of Concurrent Stochastic Games

Angel Y. He, David Parker

제출 2026-09-03

저자 비고

arXiv 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

한국어 초록

우리는 전이 불확실성이 있는 일반합(general-sum) 동시 확률 게임(concurrent stochastic games, CSG)을 위한 최초의 PAC(Probably Approximately Correct) 학습 프레임워크를 제안하며, 이때 내시 균형(Nash equilibrium, NE)의 존재 여부라는 문제도 함께 다룬다. 제안하는 알고리즘은 전이 커널에 대해 데이터 기반 $L^1$ 신뢰 집합(confidence set)을 유지하고, 강건한(robust) CSG를 풀어 사회적 후생(social-welfare) 측면에서 최적인 $\varepsilon$-NE를 계산하며, 강건 MDP 기반의 탐험(exploration) 메커니즘을 사용해 결합 상태-행동 커버리지를 확보한다. 특히 우리는 균형 존재 여부에 대한 원리적인 추론을 가능하게 하는 내시 마진(Nash margin) 특성화를 도입한다. 이에 따라 프레임워크는 사회적 후생 값이 최적값에 $\varepsilon$ 이내로 근접한 $\varepsilon$-근사 NE를 반환하거나, 정확한 NE가 존재하지 않는다는 타당한(sound) 증명서(certificate)를 제공한다. 관련 상태-행동 쌍에 대해 최소 도달 가능성 조건 $p_{\mathrm{reach}}>0$이 성립하면, 알고리즘은 다항식 개수의 궤적 샘플 이후 종료되며, 표본 복잡도는 $\widetilde{O}\left( {R_{\max}^2 H^4 |S|^2 |A| / (p_{\mathrm{reach}} \varepsilon^2)} \right)$이다. 벤치마크 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 $\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.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2609.04189v2
  2. arXiv:2609.04189v1제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.