PaperlayerView exact revision on arXiv

Source-linked AI summary

Robust PAC Learning of Concurrent Stochastic Games

Angel Y. He, David Parker

arXiv:2609.04189v1cs.LGcs.GTcs.LOcs.MA

TL;DR

Unknown transitions complicate PAC equilibrium learning in concurrent stochastic games, where exact stationary Nash equilibria may not exist. PAC-CSG combines data-driven transition confidence sets, robust equilibrium computation, and targeted exploration, using Nash margins to reason about existence. It provides approximate equilibria or sound non-existence certificates, with benchmark results illustrating both outcomes.

  • Problem

    In concurrent stochastic games, transition probabilities are often unknown, and existing approaches commonly assume known transitions without addressing robust equilibrium learning or equilibrium existence.

    Source: §1 · p. 1

  • Method

    PAC-CSG maintains L1 confidence sets over transition kernels, computes robust equilibria, uses targeted exploration, and applies Nash margins to reason about equilibrium existence.

    Source: §1 · p. 2, §3 · p. 4, §3.1 · p. 4

  • Results

    10/10 Cyclic Preferences runs returned NOT_FOUND; on Hide-or-Run, the learner returned an ε-NE approaching the limiting equilibrium rather than NOT_FOUND.

    Source: §5.1 · pp. 9–10

  • Takeaways & Limitations

    The framework can return an ε-NE when an exact NE exists or a sound certificate that no exact NE exists.

    Source: §1 · p. 2

    The non-existence certificate is sound but incomplete, and exact stationary NE may fail to exist in CSGs.

    Source: §3.1 · pp. 4–5

Abstract

from arXiv · show

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.

1 Introduction

The paper studies PAC learning in concurrent stochastic games with unknown transitions, where equilibrium computation must account for both uncertainty and the possibility that exact stationary equilibria do not exist. PAC-CSG combines robust equilibrium computation with targeted exploration to provide a high-confidence approximate equilibrium or a sound non-existence certificate.

1 Introduction

  • Unknown transitions make equilibrium learning difficult because estimation errors can destabilise equilibria or leave nominally near-optimal strategies far from equilibrium in the true model.Most existing equilibrium-computation approaches assume known transition probabilities.Source: §1 · p. 1
  • The work joins robust equilibrium computation and PAC learning, two lines that have remained largely separate for general-sum concurrent games.Robust approaches typically assume a prescribed uncertainty set or generative model, while PAC approaches do not address robust equilibrium computation or existence under unknown dynamics.Source: §1 · p. 1
  • Centralised exploration coordinates joint actions and uses an auxiliary exploration RMDP to reach under-visited state–action pairs despite uncertain transitions.History-dependent visitation events are aggregated with a Freedman martingale argument to obtain a high-probability global coverage guarantee.Source: §1 · p. 2
  • PAC-CSG returns an ε-NE with social-welfare value ε-close to optimal when an exact NE exists, or may provide a sound certificate that none exists.The framework considers finite- and infinite-horizon probabilistic and reward reachability objectives.Source: §1 · p. 2

2 Preliminaries

The preliminaries define concurrent stochastic games, the stationary strategy setting, and the robust equilibrium concepts used in the paper. They also specify the transition-uncertainty model and the reachability and reward objectives under study.

2 Preliminaries

  • A CSG specifies players, states, a start state, joint actions, action availability, a transition kernel, and player rewards.Players choose available actions simultaneously, and the joint action induces a transition to the next state.Source: §2 · p. 3
  • The paper focuses on stationary strategies, which depend only on the current state, and evaluates profiles using players’ expected utilities and their sum, the social welfare.A social-welfare optimal NE maximises social welfare among equilibria.Source: §2 · p. 3
  • A robust CSG represents transition uncertainty with a set of kernels, whose uncertainty factorises independently across state–action pairs.Robust equilibrium conditions must hold across every admissible transition kernel.Source: §2 · p. 3
  • The paper studies bounded and unbounded probabilistic reachability and reward objectives, including cumulative reward and reachability reward.For reachability objectives, transitions after entering a target state do not affect the objective.Source: §2 · p. 3
  • An ε-RNE permits bounded unilateral deviation gains across all states and kernels, and an ε-RSWNE maximises robust social welfare among such profiles.Exact stationary NE may not exist, motivating approximate equilibrium concepts.Source: §2 · pp. 3–4

3 PAC-CSG

PAC-CSG learns a two-player general-sum CSG with unknown transitions using data-driven uncertainty sets and exploration. Its Nash margin formalises equilibrium existence and supports an output guarantee that distinguishes approximate equilibria from sound, but incomplete, non-existence certificates.

3 PAC-CSG

  • The true game has unknown transitions but known state space, action availability, rewards, and transition support; rewards are bounded and uncertainty preserves graph support.These assumptions support robust dynamic programming over rectangular uncertainty models.Source: §3 · p. 4
  • At each episode, the learner builds per-slot L1 confidence sets around the empirical kernel and uses an exploration RMDP induced by those sets to gather trajectories and update its model.The confidence sets contain the true kernel with high probability.Source: §3 · p. 4

3.1 PAC-CSG

  • The Nash margin measures a profile’s distance from equilibrium, while the global margin is nonnegative exactly when the true game has an exact NE.The social-welfare optimal NE value is well-defined precisely when the global margin is nonnegative.Source: §3.1 · p. 4
  • With high probability and polynomially many interactions, PAC-CSG outputs an ε-NE that is ε-optimal when an exact NE exists, or a sound declaration that the global margin is undefined or negative.The non-existence branch is sound but incomplete: the learner may instead terminate with an approximate equilibrium for a game without an exact stationary NE.Source: §3.1 · pp. 4–5
  • The algorithm constructs confidence sets, tests robust equilibrium conditions, and, if needed, uses exploration and trajectory sampling to update its model.Its output is either the returned profile and value or NOT_FOUND when the non-existence branch is taken.Source: §3.1 · p. 5

4 PAC-CSG guarantees

The guarantees connect transition uncertainty to value and equilibrium error, then use targeted exploration to cover relevant state–action pairs. Under reachability assumptions, the analysis bounds the samples needed for a PAC output and extends the result to certain infinite-horizon objectives.

4.1 Estimation Error and Value Stability

  • For any fixed profile, transition uncertainty bounds the value difference by ∆t; when the optimal NE margin is at least 4∆t − ε, the returned profile’s true-game value gap is at most 4∆t.A true NE with margin µ induces an approximate robust NE with error 4∆t − µ.Source: §4.1 · p. 6
  • On the event that the true kernel remains in the confidence sets, an ε-RSWNE of the empirical uncertainty model is an ε-NE of the true game.Solver failure instead implies that the true game has no NE with margin at least 4∆t − ε.Source: §4.1 · p. 6

4.2 Exploration

  • The exploration RMDP assigns unknown state–action pairs transitions to an absorbing state with reward, making expected reward equivalent to the probability of reaching an unknown pair.Its pessimistic robust objective supports the high-probability coverage guarantee because a best-case visitation probability need not lower-bound visitation under the true kernel.Source: §4.2 · p. 7

4.3 PAC-CSG

  • Under graph reachability, every relevant state–action pair is reachable with positive probability, and targeted exploration provides high-probability coverage of all such pairs.The analysis uses Freedman’s inequality to aggregate history-dependent episode visitation and derive the finite-horizon sample bound; the supplied theorem passage does not expose its full formula.Source: §4.2 · p. 7, §4.3 · p. 7
  • For the infinite-horizon extension, almost-sure reachability of target states under every supported kernel yields an effective horizon that bounds the stopping time.Replacing H with this effective horizon gives corresponding guarantees, with adjusted constants; this assumption ensures value-iteration convergence but not stationary NE existence.Source: §4.3 · p. 8

5 Experimentation

The experiments test PAC-CSG’s equilibrium outputs, exploration strategies, and sample-complexity scaling on benchmark concurrent stochastic games. The results report oracle-level values when stationary equilibria exist, sound handling of selected non-existence cases, and scaling consistent with theoretical bounds over tested instances.

5 Experimentation

  • The evaluation uses six small, interpretable CSG benchmarks and compares learned outputs with exact solutions; experiments average trajectory sampling over 10 random seeds.The benchmark set covers non-existence, sparse delayed rewards, limiting equilibria, mixed equilibria, transition sensitivity, and safety-critical coordination.Source: §5 · p. 8
  • The scaling study varies one problem dimension at a time in Safe vs. Risky while holding the other parameters at their specified defaults.The tested dimensions are |S|, |A|, H, and ε.Source: §5 · p. 8

5.1 Results and Discussion

  • Across benchmarks, returned profiles attain oracle true-game values whenever a stationary NE exists; the second Safe vs. Risky case also recovers the ∞ NE value.For cases without a stationary NE, the algorithm returns NOT_FOUND for Cyclic Preferences and an ε-NE approaching the limiting value for the first Hide-or-Run case.Source: §5.1 · p. 8, Table 1 · p. 9
  • Cyclic Preferences returns NOT_FOUND in 10/10 runs, while Hide-or-Run returns an ε-NE approaching its limiting equilibrium rather than a non-existence certificate.The certificate is sound when emitted, but need not be emitted for every game without an exact stationary NE.Source: §5.1 · pp. 9–10
  • Uniform exploration requires 2.0×, 2.5×, and 17× more trajectories on Safe vs. Risky, Cyclic Preferences, and Delayed Coordination, respectively.Round-robin requires 2.3× more trajectories on Traffic Merge; on Delayed Coordination, the optimistic explorer’s value estimate differs from truth by 0.06 while the robust explorer’s is near-perfect.Source: §5.1 · p. 10
  • The fitted sample-complexity exponents are 1.44 for |S|, 0.89 for |A|, 3.94 for H, and 2.11 for 1/ε, consistent with the theorem’s worst-case bound over tested instances.The experiments do not establish tight asymptotic rates; Figure 1 plots scaling against |S|, |A|, H, and ε.Source: Figure 1 · p. 9, §5.1 · p. 10

6 Conclusion

The conclusion presents PAC-CSG as a framework for learning under transition uncertainty while handling stationary equilibrium existence or non-existence. The accompanying proof and concentration results connect Nash margin to equilibrium existence and construct confidence sets that contain the true kernel with high probability.

6 Conclusion

  • PAC-CSG combines L1 uncertainty sets and robust reachability exploration to return an ε-social-welfare-optimal ε-NE or a sound certificate of NE non-existence.Its termination guarantee is stated under a graph reachability condition.Source: §6 · p. 10

A Proof for Nash margin property (Definition 3)

  • The Nash-margin proof shows that a profile with nonnegative Nash margin is an NE, so a nonempty NE set admits a social-welfare-maximizing NE.The reverse direction is addressed through the maximum achievable Nash margin.Source: A Proof for Nash margin property… · p. 14

B Concentration bounds and confidence radii

  • Per-slot L1 confidence sets use empirical transition frequencies within the known successor support; concentration and a union bound ensure the true kernel remains in Pt across episodes with probability at least 1 − δcont.When a slot has no samples, its uncertainty set is the support-preserving simplex and its point estimate is uniform over that support.Source: B Concentration bounds and confidence… · pp. 14–15

C Proofs for value sensitivity (Lemma 2)

This proof section propagates transition-model error through stopped state marginals to bound utility sensitivity. It then extends the sensitivity results to comparisons between kernels and to social welfare.

C Proofs for value sensitivity (Lemma 2)

  • A recursion for stopped state marginals propagates one-step transition errors, starting from identical initial-state distributions under the true and estimated kernels.The argument uses L1 norms and the triangle inequality; bounded probabilistic reachability is handled through an equivalent finite-horizon terminal-reward encoding.Source: C Proofs for value sensitivity (Lemma 2) · pp. 15–17
  • For any kernel P in Pt, strategy profile, player, and initial state, the utility difference between P and the point estimate is bounded by Δt = 2H^2RmaxΔL1_t.The bound follows from the transition-error propagation argument.Source: C Proofs for value sensitivity (Lemma 2) · pp. 16–17
  • Corollaries extend sensitivity bounds to two kernels in Pt and to social welfare by summing the player-wise bounds.The pairwise kernel bound follows from applying the single-kernel sensitivity result twice.Source: C Proofs for value sensitivity (Lemma 2) · p. 17

D Proofs for equilibrium existence (Proposition 4)

The solver guarantees that a robust equilibrium found in the empirical model transfers to an approximate NE in the true game; failure is interpreted through the Nash margin. The anytime value-gap bound applies when the true game has an equilibrium with sufficient margin.

D Proofs for equilibrium existence (Proposition 4)

  • The information-theoretic PAC guarantee abstracts equilibrium computation as an oracle and is decoupled from solver computational complexity.Practical solvers exist for general-sum L1-RCSGs, but polynomial-time implementations are known only in certain settings, such as the zero-sum case.Source: D Proofs for equilibrium existence… · p. 18
  • A returned ε-RSWNE of the empirical uncertainty set is an ε-NE of the true game on the containment event.The transfer follows because the true transition kernel belongs to the confidence set.Source: D Proofs for equilibrium existence… · p. 18
  • A NOT_FOUND result implies either that no exact NE exists or that the true game's social-welfare optimal NE has margin below 4Δ_t − ε.The solver's failure means no ε-RNE exists in the empirical uncertainty set; if an SWNE exists, a larger margin would imply one.Source: D Proofs for equilibrium existence… · p. 18

E Proofs for anytime guarantees (Corollary 5)

F Supplementary details and proofs for exploration principles (Sec. 4.2)

Exploration targets unknown state-action pairs by maximizing worst-case reachability under the current uncertainty set. Independent trajectories and a reachability lower bound yield a per-episode coverage guarantee, while the absorbing construction is used for analysis rather than implementation.

F Supplementary details and proofs for exploration principles (Sec. 4.2)

  • A slot is unknown until it has reached the visit threshold n_min, and the total required visits are bounded by |S||A|n_min.The absorbing construction is analytical only; continuing trajectories in implementation does not reduce the lower bound, and the exploration RMDP need only be re-solved when slot status changes.Source: F Supplementary details and proofs for… · p. 19
  • The minimum reachability probability p_reach lower-bounds the probability of reaching a designated unknown slot under the robust exploration policy.The bound takes the infimum over support-preserving kernels.Source: F Supplementary details and proofs for… · pp. 19–20
  • The exploration RMDP maximizes expected reward, which is equivalent to maximizing the probability of reaching an unknown slot.The absorbing construction ensures a trajectory contributes at most once.Source: F Supplementary details and proofs for… · p. 20
  • Conditioned on the interaction history, sampled trajectories are independent; the multi-trajectory strategy ensures a high probability of visiting an unknown slot in each episode.The stated coverage guarantee is at least 1 − δ_cov.Source: F Supplementary details and proofs for… · pp. 20–21

G Proofs for PAC-CSG (Theorem 7)

The PAC guarantee proof combines confidence control, exploration-based coverage, and a stopping rule tied to transition uncertainty. Once relevant state-action slots meet the visit threshold, the algorithm terminates with the guarantee described by Theorem 7.

G Proofs for PAC-CSG (Theorem 7)

  • The proof splits the confidence budget equally between transition containment and coverage, setting δ_cont = δ_cov = δ/2.The combined event then holds with probability at least 1 − δ.Source: G Proofs for PAC-CSG (Theorem 7) · pp. 22, 25
  • With probability at least 1 − δ_cov, the algorithm makes all relevant slots known within the episode bound established by the counting argument.Each exploratory episode discovers at least one previously unknown slot, and the total visits required are N_tot.Source: G Proofs for PAC-CSG (Theorem 7) · pp. 22–23
  • Once every relevant slot has at least n_min visits, the transition uncertainty satisfies Δ_t ≤ ε/4, meeting the stopping threshold.At termination, Corollary 22 supplies the output guarantee for the applicable Nash-margin case.Source: G Proofs for PAC-CSG (Theorem 7) · p. 25
  • Theorem 7 gives a PAC guarantee with termination after a bounded number of trajectory samples, with logarithmic factors suppressed.Its output is an approximate equilibrium or a non-existence certificate.Source: G Proofs for PAC-CSG (Theorem 7) · pp. 22, 25

H Supplementary details and proofs for infinite-horizon objectives

The supplementary results extend the PAC analysis to unbounded reachability objectives under a properness condition that gives a finite effective horizon. They also describe zero-sum simplifications, helper routines, and the exploration baselines used for comparison.

H Supplementary details and proofs for infinite-horizon objectives

I Extension: Learning zero-sum CSGs

  • In zero-sum CSGs, the single utility removes the factor-of-2 loss, improves the stopping threshold from ε/4 to ε/2, and reduces the solver to a polynomial-time minimax L1-CSG/RMDP problem.For the stated finite-horizon objectives, optimal strategies exist; in the infinite-horizon setting, they need not.Source: I Extension: Learning zero-sum CSGs · p. 30

J Helper functions for Algorithm 1

  • The helper routine computes p_reach using a reachability RMDP with full-simplex uncertainty over the true support; implementation uses a 10^-5 probability lower bound within that support.This preserves the graph and yields a strictly positive p_reach without knowing transition probabilities.Source: J Helper functions for Algorithm 1 · p. 30

K.1 Exploration Baselines

  • The exploration baselines contrast the algorithm's worst-case reachability policy with optimistic, round-robin, and uniform-random sampling policies.The optimistic policy targets best-case reachability, while round-robin targets the least-sampled unknown slot.Source: §K.1 · p. 31

K.2 Learning Dynamics

Learning dynamics are bottlenecked by the hardest-to-sample state–action pair, whose worst-case confidence radius can delay strategy improvement until near termination.

K.2 Learning Dynamics

  • In Delayed Coordination, ∆t and strategy value change abruptly: value stays 0 versus true value 2, then reaches 1 before the cooperative equilibrium near termination.The fully cooperative equilibrium requires coordination at each of s0, s1, and s2; the run’s Nash margin is zero, so the value-transfer precondition is not expected to hold before stopping.Source: §K.2 · p. 33
  • The analysis tracks ∆t, the true value gap, the known-pair fraction, confidence-radius distribution, and trajectories sampled per episode.The figures show these quantities in a representative Delayed Coordination run.Source: §K.2 · pp. 32–33
  • κt reaches 0.95 (19 of 20 pairs) before full coverage, while one difficult-to-sample pair dominates ∆t’s worst-case confidence radius.The average-to-maximum confidence-radius ratio first falls as most pairs are resolved, then rises as the hardest pair is sampled.Source: §K.2 · p. 33
  • The per-episode trajectory requirement grows as O(log t), as the coverage failure budget shrinks across episodes while keeping total coverage failure probability bounded.The per-episode budget is δcov/(t(t + 1)), with total failure probability from coverage at most δcov.Source: §K.2 · p. 33
  • The ∆t ≤ ε/4 stopping rule is conservative because it is driven by the worst-case pair; targeted exploration of high-impact, poorly explored regions is proposed as a possible improvement.The authors suggest rewards proportional to confidence radii and/or inversely proportional to visitation probabilities.Source: §K.2 · p. 33

K.3 Full experimental results

  • For stationary-NE cases, learned values match true-game values except on action-indifferent states; Hide-or-Run is limit-equilibrium, and the third Safe vs. Risky property returns infinity.Table 3 reports mean ± std over 10 runs; ε = 0.1 except for Delayed Coordination’s unbounded-reachability property, which uses ε = 0.2.Source: Table 3 · p. 34

L Limitations

  • The framework assumes centralized exploration and p_reach > 0 for every relevant pair; zero-reachability settings lack its online-trajectory termination guarantee.Comparable confidence sets under decentralized learning would not by themselves supply the joint-coverage and termination analysis.Source: L Limitations · p. 34
  • Other assumptions include shared transition support, bounded rewards, and, for infinite-horizon reachability rewards, almost-sure target reachability with a uniform pT lower bound.The pT bound is used to obtain a geometric tail bound and finite effective horizon.Source: L Limitations · pp. 34–35

L.1 Intrinsic limitations

The paper identifies equilibrium-solver cost, sample-complexity dependence, incomplete non-existence detection, and extensions beyond two-player stationary settings as limitations or open directions.

L.1 Intrinsic limitations

  • General-sum CSG solving can require exponential time, and computing subgame-perfect Nash equilibria for nonzero-sum reachability objectives is PSPACE-complete.The approach depends on a black-box RCSG solver, instantiated with PRISM-games.Source: §L.1 · p. 35
  • The sample-complexity bound has leading H^4 dependence; reducing it to H^3 may require stronger variance-control assumptions and a more involved analysis.The paper names empirical-Bernstein or stagewise concentration techniques as possible approaches.Source: §L.1 · p. 35
  • The non-existence certificate is sound but incomplete: when no exact NE exists, the algorithm may still return an ε-NE.The authors attribute this difficulty to approximate equilibria persisting arbitrarily close to the boundary of exact equilibrium existence.Source: §L.1 · p. 35
  • Extensions to more than two players or non-stationary environments remain open, introducing greater equilibrium and joint-action complexity or evolving dynamics.Non-stationary settings would require adapting to transition kernels and equilibrium structure that change over time.Source: §L.1 · p. 35

M Broader Impacts

  • Potential applications include robust autonomous systems, while competitive or adversarial uses could exploit robustness for strategic advantage.The paper is theoretical and does not target specific deployments; it calls for careful consideration of downstream uses.Source: M Broader Impacts · p. 35
Loading 2609.04189v1…