Research map / Learning theory and algorithms / Submodular and game algorithms

Robust PAC Learning of Concurrent Stochastic Games

NeurIPS 2026 · Learning theory and algorithms › Submodular and game algorithms · approach: Zero-sum game learning dynamics · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Introduces PAC-CSG, a PAC learning framework for two-player general-sum concurrent stochastic games with L1 transition uncertainty that computes an epsilon-robust social-welfare optimal NE or certifies NE non-existence, using a robust-MDP exploration scheme.

Problem

Learning approximately optimal Nash equilibria in general-sum concurrent stochastic games with unknown transition dynamics, with sample-complexity guarantees and sound handling of stationary NE non-existence.

Approach

Maintains per-slot L1 (Weissman) confidence sets over transitions, solves a robust CSG for an epsilon-RSWNE, and uses an exploration RMDP that casts joint state-action coverage as robust reachability; a Nash margin characterisation lets the learner sound-certify non-existence when the robust solver fails.

Key results

• On Cyclic Preferences the solver returns not-found in 10/10 runs, a sound certificate of no exact stationary NE.
• Value gap V*-V_hat stays below 4*Delta_t (about 0.003 or less on most benchmarks, 0.000 on Traffic Merge and Hide-or-Run).
• Empirical log-log sample-complexity exponents on Safe vs. Risky are 1.44 for |S|, 0.89 for |A|, 3.94 for H and 2.11 for 1/epsilon.

Surprising findings

• Uniform exploration needs up to 17x more trajectories than the robust explorer on Delayed Coordination.
• Hide-or-Run has no exact stationary NE, yet the learner returns an epsilon-NE approaching the limiting value rather than certifying non-existence, showing the certificate is incomplete.

Limitations

• Assumes centralised exploration, known transition support, and graph reachability (p_reach > 0).
• Scalability in |S| and |A| is limited; experiments are on small benchmark games.
• Non-existence certificate is sound but incomplete; it is not emitted for every game without an exact stationary NE.

Experimental setup

Datasets: six small benchmark CSGs (Cyclic Preferences, Delayed Coordination, Hide-or-Run, Mixed NE, Safe vs. Risky, Traffic Merge

Benchmarks: Cyclic Preferences Delayed Coordination Hide-or-Run Mixed NE Safe vs. Risky Traffic Merge

Metrics: value gap V*-V_hat samples to convergence epsilon-NE found / non-existence certificate empirical scaling exponents

Baselines: uniform-random joint-action exploration round-robin exploration optimistic exploration

Builds on: Weissman L1 concentration inequality robust CSG framework Freedman inequality PRISM-games solver

Closest papers by meaning

• Roping in Uncertainty: Robustness and Regularization in Markov Games (ICML 2024 · similarity 0.88)
• Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence beyond the Minty Property (AAAI 2024 · similarity 0.88)
• Robust Equilibria in Continuous Games: From Strategic to Dynamic Robustness (NeurIPS 2025 · similarity 0.88)
• Learning Nash Equilibrium of Markov Potential Games with a Shared Constraint via Primal-Dual Optimization (AAAI 2025 · similarity 0.87)
• Learning Equilibria in Adversarial Team Markov Games: A Nonconvex-Hidden-Concave Min-Max Optimization Problem (NeurIPS 2024 · similarity 0.87)
• Playing Markov Games Without Observing Payoffs (NeurIPS 2026 · similarity 0.87)