Robust PAC Learning of Concurrent Stochastic Games

Robust PAC Learning of Concurrent Stochastic Games

arXiv:2609.04189v1 [cs.LG] 3 Sep 2026

Angel Y. He Department of Engineering Science University of Oxford angelyhe@robots.ox.ac.uk

David Parker Department of Computer Science University of Oxford david.parker@cs.ox.ac.uk

Abstract 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 L1 confidence sets over transition kernels and solves a robust CSG to compute a social-welfare optimal ε-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 ε-approximate NE whose social-welfare value is ε-close to optimal, or provides a sound certificate that no exact NE exists. Under a minimum reachability condition preach > 0 over relevant state–action pairs, the algorithm terminates after a polynomial number
of trajectory samples, 2 e Rmax with sample complexity O H 4 |S|2 |A|/(preach ε2 ) . Empirical results on benchmark CSGs demonstrate near-optimal performance, correct handling of equilibrium (non-)existence, and sample complexity consistent with theory.

1

Introduction

Learning to act optimally in multi-agent stochastic environments is fundamentally harder when the transition dynamics are unknown: even small estimation errors can destabilise equilibria or make a nominally near-optimal strategy far from equilibrium under the true model. Concurrent stochastic games (CSGs) [39], where players choose actions simultaneously without observing one another, are the canonical model for such settings — yet most existing approaches to equilibrium computation assume that transition probabilities are precisely known. This paper asks: how many environment interactions suffice to compute an approximately optimal equilibrium with high probability, and what happens when no exact equilibrium exists? Uncertainty in stochastic decision-making has been studied from two complementary angles. On the robust-planning side, robust MDPs (RMDPs) [21, 35, 48] including interval MDPs [17], and their stochastic-game extensions [4, 9] optimise worst-case performance over a prescribed uncertainty set. Recent work has extended this line to robust CSGs (RCSGs) [18] and distributionally robust Markov games (DRMGs) [30, 38, 40, 51]. On the learning side, Probably Approximately Correct (PAC) [44] algorithms provide sample-complexity guarantees for MDPs [2, 7, 22, 24, 42] and turnbased stochastic games [3, 32, 50]. However, these two lines of work have remained largely separate in the concurrent general-sum setting: robust methods typically assume availability of the uncertainty set or a generative model [21, 30, 35, 40, 51], while PAC methods do not address robust equilibrium computation or equilibrium existence under unknown dynamics. Work at their intersection on robust PAC learning remains largely restricted to the single-agent setting [36, 37, 46, 49, 52]. Combining robust equilibrium computation with PAC learning in concurrent games poses two challenges absent from prior work: 1) Equilibrium existence under uncertainty. While ε-NE exist for any ε > 0 [13], exact stationary (i.e., memoryless and time-independent) NE may fail to exist in CSGs [6]. The issue is not merely pathological: in multi-agent systems, an NE represents a stable Preprint.

operating point in which no agent has unilateral incentive to deviate. When no such equilibrium exists, any deployed strategy may be inherently unstable, potentially inducing unpredictable or undesirable system behaviour, as observed in domains such as traffic coordination, network routing, and competitive markets [19, 23]. Moreover, even when an exact NE exists in the true game, an uncertainty set around the true transition kernel may not have a robust equilibrium [18]. A PAC framework for CSGs should therefore support both approximate equilibrium computation and principled handling of non-existence. 2) Global coverage from stochastic trajectories. Obtaining sufficient joint state–action coverage from online trajectories is challenging in our setting because no individual player controls the joint action and the transition kernel is uncertain. Under centralised exploration, we address this by coordinating joint actions and constructing an auxiliary exploration RMDP on which we compute joint profiles to robustly reach under-visited state–action pairs. This yields a per-episode lower bound on visiting insufficiently explored pairs in the true game. Because the set of under-visited pairs and the exploration policy adapt to the observed history, these episode-level events are dependent; we therefore use a martingale concentration argument based on Freedman’s inequality [16] to aggregate the conditional lower bound into a high-probability global coverage and sample-complexity guarantee. Contributions. We introduce PAC-CSG, the first PAC-learning framework for two-player generalsum CSGs under transition uncertainty with sound detection of stationary equilibrium non-existence. When an exact NE exists, the algorithm returns an ε-NE (i.e., stable up to ε under unilateral deviations) whose social-welfare value is ε-close to optimal; otherwise, it may return a sound certificate of nonexistence. We consider finite- and infinite-horizon probabilistic and reward reachability objectives, which are standard in verification and planning [27, 28], unlike the discounted reward objectives common in reinforcement learning (RL) [2, 42]. To realise this framework, we design an algorithm that maintains L1 confidence sets over transition kernels and combines robust equilibrium computation with an auxiliary RMDP-based exploration mechanism that formulates joint state–action coverage as a robust reachability problem. Under a graph reachability condition, the algorithm terminates
2 4 2 2 e after O Rmax H |S| |A|/(preach ε ) trajectory samples and outputs either an ε-optimal ε-NE or a sound non-existence certificate, where preach is the minimum reachability probability over all relevant state–action pairs. Finally, we evaluate the approach on six CSG benchmarks, demonstrating near-optimality, correct handling of equilibrium (non-)existence, and sample complexity scaling consistent with the theoretical bounds. Related work. Robust planning in stochastic games addresses decision-making under a prescribed model uncertainty set. In the single-agent setting, this includes robust MDPs [21, 35, 48] and interval MDPs [17], which optimise worst-case performance over admissible transition kernels. Multi-agent extensions are more recent: robust turn-based stochastic games [9] and qualitative objectives [4] have been studied, and He and Parker [18]’s robust CSG framework introduces robust equilibrium notions for general-sum concurrent games. These approaches assume that the uncertainty set is specified a priori and focus on computing robust policies or equilibria, rather than learning them from data. PAC learning methods are well developed for MDPs via E3 [24], R-MAX [7], and related PAC-MDP analyses [42]. Closely related exploration guarantees include regret-minimisation methods such as UCRL2 [22] and UCBVI [2]. These results have been extended to turn-based stochastic games in both zero-sum self-play [3, 32] and general-sum settings [50]. However, they do not address the concurrent setting, where no single agent controls state–action visitation, nor do they incorporate robustness to transition uncertainty or equilibrium existence considerations. Robust RL considers learning under model uncertainty from data. In the single-agent setting, both model-based and model-free approaches provide sample complexity guarantees [36, 37, 46, 49, 52]. In multi-agent settings, recent work studies distributionally robust Markov games (DRMGs), primarily in zero-sum settings [30, 38, 40, 51], including sample-efficient algorithms under generative-model assumptions that largely remove the need for exploration. Other work considers alternative solution concepts, e.g., robust correlated equilibria [33]. Closest to our setting is Farhat et al. [15], who study online robust multi-agent RL under similar uncertainty sets. However, they optimise regret rather than providing PAC guarantees, and do not address equilibrium existence in general-sum concurrent games. In contrast, we provide a high-confidence output guarantee: either an ε-NE when one exists, or a sound certificate of non-existence. This distinction is fundamental in our concurrent general-sum setting: PAC learning targets the quality of a single output equilibrium, whereas regret minimisation controls performance over the entire learning trajectory. 2

2

Preliminaries

We denote by D(X) the set of discrete probability distributions over a finite set X, and let 1[A] be the indicator function that equals 1 if A holds and 0 otherwise. Definition 1 (Concurrent stochastic game). A (reward-augmented) concurrent stochastic game (CSG) is a tuple G = (N, S, s̄, A, Γ, P, r) where: N = {1, . . . , n} is a finite set of players; S is a finite set of states with initial state s̄ ∈ S; A = i∈N (Ai ∪ {⊥}) is the set of joint actions, where each Ai is a finite action set and ⊥ is a distinguished idle action; Γ : S → 2∪i Ai assigns available actions; P : S × A ⇀ D(S) is a transition kernel; and r = (r1 , . . . , rn ) with rewards ri : S × A → R.

×

At each state s, each player i ∈ N simultaneously selects an action ai ∈ Ai (s), where Ai (s) = Γ(s) ∩ Ai if Γ(s) ∩ Ai ̸= ∅ and Ai (s) = {⊥} otherwise. The joint action a = (a1 , . . . , an ) ∈ A(s) := i∈N Ai (s) induces a transition to state s′ according to Psa := P (s, a). Henceforth let X := {(s, a) : s ∈ S, a ∈ A(s)} denote the set of all admissible state–action pairs (or “slots”).

×

A strategy for player i is a function σi mapping finite histories to distributions over actions. A stationary (or memoryless) strategy depends only on the current state, i.e., σi (π) = σi (s) for all histories π ending in state s. We focus on this class of strategies throughout this work. A strategy profile (or just profile) is a tuple of strategies, one for each player, denoted σ = (σ1 , . . . , σn ) ∈ Σ := Σ . For a profile σ and a unilateral deviation σi′ ∈ Σi , we write σ−i [σi′ ] for the profile obtained i∈N i by replacing player i’s strategy σi with σi′ .

×

Each player i is associated with an objective Xi mapping infinite paths to R. For a profile σ, kernel P utility, i.e., the social welfare, as u(σ, P | s) := P, and state s, we define players’ total expected σ,P u (σ, P | s), where u (σ, P | s) := E [X i i ] is player i’s expected utility. For the value in s i∈N i the initial state s̄, we write u(σ, P ) := u(σ, P | s̄). Robust CSGs (RCSGs) [18] add transition uncertainty to CSGs. Formally, an RCSG is a tuple G = (N, S, s̄, A, Γ, P, r), where P : S × A ⇀ 2D(S) is an uncertain transition kernel, and all other components are as in Definition 1. Fixing a P ∈ P in an RCSG induces a CSG, which we denoteQGP . We focus on (s, a)-rectangular uncertainty, where the global uncertainty set factorises as P = (s,a)∈X P(s, a), so transition uncertainty at each slot can be resolved independently. For a profile σ, we denote its robust and optimistic values over P, respectively, as uP (σ) := inf u(σ, P ),

ūP (σ) := sup u(σ, P ).

P ∈P

P ∈P

Objectives. Following He and Parker [18], Kwiatkowska et al. [27], we focus on four objectives (two finite-horizon, two infinite-horizon). Let ST ⊆ S be a set of target states, and Xnt := {(s, a) ∈ X : s ̸∈ ST } the set of non-target slots. For finite-horizon objectives fix H ∈ N: (1) Bounded probabilistic reachability: X(π) = 1[∃j ≤ H. π(j) ∈ ST ]; (2) Bounded cumulative rePH−1 ward: X(π) = i=0 r(π(i), π[i]); (3) Probabilistic reachability: X(π) = 1[∃j ∈ N. π(j) ∈ ST ]; PτT −1 and (4) Reachability reward (or stochastic shortest paths): X(π) = i=0 r(π(i), π[i]) if ∃j ∈ N. π(j) ∈ ST and X(π) = ∞ otherwise, where τT = min {j ∈ N | π(j) ∈ ST }. For the reachability objectives, transitions after entering ST do not affect Qthe objective, so we only need to resolve uncertainty over Xnt . Thus, henceforth we consider P = (s,a)∈Xnt P(s, a). For the bounded cumulative reward objective, ST = ∅ so Xnt = X .

Solution concepts. A Nash equilibrium (NE) in a CSG is a profile σ such that, for all players i, states s and deviations σi′ , ui (σ, P | s) ≥ ui (σ−i [σi′ ], P | s). A social-welfare optimal NE (SWNE) is an NE maximising u(σ, P | s). We require these equilibrium conditions to hold from every state, yielding a subgame-perfect equilibrium. For an RCSG, we further require the same equilibrium requirement to hold robustly, i.e., across every P ∈ P. In addition, since exact stationary NE may not exist [6] but ε-NE exists for any ε > 0, we use approximate robust equilibria: Definition 2 (ε-RNE). A profile σ is a robust ε-Nash equilibrium (ε-RNE) iff for all players i, states s, and deviations σi′ , inf P ∈P [ui (σ, P | s) − ui (σ−i [σi′ ], P | s)] ≥ −ε. The corresponding ε-RNE value is defined as uP (σ) := inf P ∈P u(σ, P ). 3

The case ε = 0 yields a robust NE (RNE). Following this definition, a robust social-welfare optimal ε-NE (ε-RSWNE) is just an ε-RNE σ that maximises uP (σ), the robust total utility of the players. Henceforth we write Σε-RNE (P) for the set of all ε-RNE under P, ΣRNE (P) for the set of RNE, and similarly Σε-NE (P ) and ΣNE (P ) for the set of ε-NE and NE, respectively, under kernel P .

3

PAC-CSG

Game setting. We model the true environment as a finite two-player general-sum CSG G ⋆ = (N = {1, 2}, S, s̄, A, Γ, P ⋆ , r), where P ⋆ is unknown but the state space, action availability, rewards, and transition support of G ⋆ are known. When it exists, denote the SWNE value of G ⋆ by V ⋆ := supσ∈ΣNE (P ⋆ ) u(σ, P ⋆ ) = u(σ ⋆ , P ⋆ ), with σ ⋆ being the corresponding profile. We assume bounded rewards: |ri (s, a)| ≤ Rmax . We also enforce the standard graph preservation constraint [10, 34], requiring all P ∈ P to share the same support. This ensures the tractability of robust dynamic programming [21, 35] over (s, a)-rectangular uncertainty models. Learning. Throughout, we assume a centralised learner that jointly controls both players. Learning proceeds episodically: quantities derived from data up to episode t are indexed by t, and T denotes the total number of episodes before termination. At episode t, the learner maintains an uncertainty 1 set Pt around an empirical kernel Pbt . This set confidence balls: for each qis defined via per-slot L
2 |S| cont b (s, a) ∈ Xnt , ∥Psa − Psa,t ∥1 ≤ αt (s, a) := ln (2 − 2)/δsa,n , where n := Nt (s, a) is the n

cont visit count of (s, a) up to episode t and δsa,n is a suitable failure probability defined in Corollary 10, App. B. The radius αt (s, a) follows from Weissman’s L1 concentration inequality [47] and is derived in Lemma 9, App. B. Pt contains all transition kernels consistent with the observed data so far with high probability, and induces an empirical L1 -CSG Gt = (N, S, s̄, A, Γ, Pt , r). Further, the learner selects an exploration profile σte by solving an exploration RMDP Gte (see Definition 5) induced by the same uncertainty set Pt , executes it in G ⋆ , and uses the resulting trajectories to update Gt .

3.1

PAC-CSG

Unlike single-agent or zero-sum settings, exact stationary NE need not exist in our setting. Remark 1 (NE existence). For any finite CSG, Σε-NE (P ) ̸= ∅ for all ε > 0 [6, 13]. However, exact stationary NE (ε = 0) may fail to exist in CSGs. For finite-horizon CSGs, backward induction generally yields time-dependent equilibrium strategies. In the infinite-horizon setting, Bouyer et al. [6] illustrate non-existence via two-player concurrent terminal-reward games with no NE at all (and hence no stationary NE), including the Hide-or-run game used in our experiments; see Sec. 5. Finally, for an RCSG G, even if every induced CSG GP admits an (ε-)NE, an (ε-)RNE need not exist in G [18], as it must satisfy equilibrium conditions simultaneously for all admissible kernels P . To reason about equilibrium existence quantitatively, we introduce the notion of Nash margin. Definition 3 (Nash margin). For a CSG with kernel P and profile space Σ, define the Nash margin of a profile σ ∈ Σ as µ(σ, P ) := mini∈N mins∈S inf σi′ ∈Σi [ui (σ, P | s) − ui (σ−i [σi′ ], P | s)]. Further define the global Nash margin µ̄ in G ⋆ as µ̄ := maxσ∈Σ µ(σ, P ⋆ ); and, if µ̄ ≥ 0, define the socialwelfare optimal Nash margin as µ⋆ := µ(σ ⋆ , P ⋆ ). Thus, µ(σ, P ) measures how close a profile is to being an NE, while µ̄ captures how close G ⋆ is to admitting an equilibrium overall. In particular, µ(σ, P ) ≥ 0 iff σ ∈ ΣNE (P ), and µ̄ ≥ 0 iff ΣNE (P ⋆ ) ̸= ∅. Since an ε-NE exists in any finite CSG for all ε > 0, the global margin satisfies µ̄ ≥ −ε for arbitrarily small ε. The use of max (rather than sup) in the definition of µ̄ ensures that this margin is well-defined only when the maximum is attained by some profile. Finally, V ⋆ is well-defined iff µ⋆ ≥ 0, which holds precisely when µ̄ ≥ 0, i.e., G ⋆ admits an exact NE. We formalise this relationship in Proposition 8, App. A. This characterises our PAC formulation in Definition 4, which conditions on whether µ̄ ≥ 0. We present a concrete realisation of this framework in Alg. 1. Definition 4 (PAC-CSG). An algorithm for a finite CSG is PAC if, for any ε, δ ∈ (0, 1), with probability at least 1 − δ, after a number of interactions polynomial in |S|, |A|, 1/ε, log(1/δ) and problem constants, it outputs one of the following: 4

(a) (Approximate equilibrium) An ε-NE profile σ̂ such that, if µ̄ ≥ 0, then V ⋆ − u(σ̂, P ⋆ ) ≤ ε, i.e., σ̂ is ε-optimal; in this case, the algorithm always terminates in this branch. (b) (Near-non-existence certificate) A sound declaration that µ̄ is not well-defined or µ̄ < 0, i.e., no exact NE exists in G ⋆ . Importantly, here ε-NE and ε-optimality are distinct requirements: the former bounds unilateral incentives to deviate, while the latter bounds the social-welfare loss relative to the optimal NE. The existence branch (a) certifies that the true game admits a well-separated (SW)NE and returns a corresponding profile, while the non-existence branch (b) certifies that no exact NE exists based on the (well-definedness) and value of µ̄. Branch (b), however, provides a sound but incomplete certificate: if the algorithm outputs µ̄ < 0, then G ⋆ admits no exact NE. The converse need not hold: even when µ̄ < 0, the algorithm may still terminate via branch (a), since ε-NE always exist. Intuitively, non-existence is detected only with sufficiently strong evidence (i.e., enough samples). We develop this condition in the next section. Algorithm 1 PAC learning of 2-player CSGs Input: δ, ε, H, Rmax , (S, A, Γ, r), Supp(P ⋆ ) 1: δ cont , δ cov ← δ/2; t ← 1 b, nmin , preach ← I NITIALISE(S, A, Γ, Rmax , H, Supp(P ⋆ )) 2: N, K, P ▷ see Alg. 2, App. J 3: while true do 4: P ← C ONSTRUCT U NCERTAIN K ERNEL(N, δ cont , S, A, Γ, Supp(P ⋆ )) ▷ see Alg. 3, App. J 5: G ← B UILDL1CSG(S, A, Γ, P, r) 6: ∆ ← 12 Rmax H 2 max(s,a)∈Xnt supp∈P(s,a) ∥p − Pbsa ∥1 7: if ∆ ≤ ε/4 then 8: σ̂, V̂ , found ← S OLVEL1CSG(G, ε) 9: if found = false then return “NOT_FOUND : µ̄ undefined or µ̄ < 0” else return σ̂, V̂ 10: end if 11: end if 12: G e ← B UILD E XPLORATION RMDP(S, A, Γ, P, r, K) ▷ following Def. 5 13: σ e ← S OLVEL1MDP(G e ) 14: δtcov ← δ cov /(t(t + 1)); N π ← ⌈−(1/preach ) log δtcov ⌉ 15: π ← S AMPLE T RAJECTORIES(σ e , H, N π ) ▷ execute σ e in G ⋆ 16: N, K ← U PDATE(N, K, π, nmin , S, A, Γ); t ← t + 1 ▷ see Alg. 4, App. J 17: end while

4

PAC-CSG guarantees

We begin with finite-horizon objectives and extend the analysis to the infinite-horizon setting in Sec. 4.3. Our approach follows a three-step pipeline: 1) In Sec. 4.1, we relate statistical uncertainty in the transition kernel to value estimation error via a sensitivity lemma (Lemma 2), showing that solving a robust equilibrium in Pt yields an approximate NE in the true game once ∆t ≤ ε/4. 2) In Sec. 4.2, we construct an exploration RMDP and show that, under Assumption 1, every relevant (s, a)-pair is reachable, ensuring that targeted exploration drives ∆t below the required threshold. 3) Finally, in Sec. 4.3, we combine these results and use a Freedman martingale argument to lift stochastic per-episode visitation into a high-probability bound on the number of episodes, yielding the overall sample complexity. Throughout, we condition on the high-probability event E cont that P ⋆ ∈ Pt for all episodes t ≥ 1, as established in Corollary 10, App. B. 4.1

Estimation Error and Value Stability

Our analysis begins by relating uncertainty in the transition kernel to errors in value estimates. Suppose E cont holds, i.e., P ⋆ ∈ Pt . We show that this uncertainty induces a controlled deviation in the value of any fixed strategy profile.1 1 In Alg. 1, ∆

t is computed conservatively by maximising the transition error over the confidence set Pt ; on E

cont , this

computed quantity upper-bounds the true ∆t , and hence subsequent claims on ∆t apply to the computed quantity too.

5

1 L1 ⋆ b Lemma 2 (Sensitivity). Define ∆t := 12 Rmax H 2 ∆L t , where ∆t := max(s,a)∈Xnt ∥Psa − Psa ∥1 . Then for any P ∈ Pt , profile σ, player i ∈ N , and state s0 ∈ S, |ui (σ, P | s0 ) − ui (σ, Pb | s0 )| ≤ ∆t . 1

Proof sketch. We track how a per-(s, a) L1 perturbation of size ∆L t propagates through the trajectory 1 distribution. At step h, the deviation between state marginals satisfies ∥µh − µ̂h ∥1 ≤ h ∆L t (Proposition 11, App. B). Summing the induced reward difference Rmax ∥µh − µ̂h ∥1 over h = PH−1 0, . . . , H − 1 and using h=0 h ≤ H 2 /2 yields the bound. Full proof in App. C. Thus, on E cont , for any fixed profile σ̂, its value in the true game G ⋆ is close to its robust value over Pt , up to an error of order ∆t , which vanishes as the confidence radius shrinks with additional data. The following lemma further lets us reason about NE existence in G ⋆ by solving for a robust equilibrium over Pt (using a black-box RCSG solver; see Assumption 2, App. D): it shows that any true NE induces an approximate RNE in Pt , with quality degrading proportionally in ∆t . Consequently, solver failure to find an ε-RNE implies that no NE in G ⋆ has sufficiently large margin, i.e., ≥ 4∆t − ε. Lemma 3 (NE(P ⋆ ) ⇒ approximate RNE(Pt )). If σ is an (exact) NE under P ⋆ achieving Nash margin µ := µ(σ, P ⋆ ) ≥ 0, then it is also an (4∆t − µ)-RNE under Pt .

Proof sketch. For any player i ∈ {1, 2} and unilateral deviation σi′ , Lemma 2 bounds the difference in deviation gains under P ⋆ and any P ∈ Pt by 4∆t . Since σ has Nash margin µ under P ⋆ , its deviation gain there is at most −µ. Thus, under every P ∈ Pt , the deviation gain is at most 4∆t − µ, implying that σ is an (4∆t − µ)-RNE. Full proof in App. D. Proposition 4 (Solver guarantees for equilibrium computation). On the event E cont : (1) (Equilibrium transfer) If the solver returns an ε-RSWNE σ̂ of Pt , then σ̂ is an ε-NE of G ⋆ . (2) (Failure implies near non-existence) If the solver returns NOT_FOUND, then either µ⋆ is undefined or µ⋆ < 4∆t − ε. Proof sketch. (1) Any ε-RSWNE under Pt is, by definition, an ε-RNE under Pt , and hence an ε-NE for every P ∈ Pt , including P ⋆ (on E cont ). (2) If the solver returns NOT_FOUND, then by Assumption 2 no ε-RNE exists under Pt . We then distinguish two cases. If no NE exists under P ⋆ , then the SWNE does not exist and µ⋆ is undefined. Otherwise, the SWNE exists, and if µ⋆ ≥ 4∆t − ε, the NE–RNE transfer lemma (Lemma 3) would imply that the SWNE is an ε-RNE under Pt , contradicting the solver’s failure. Full proof in App. D. Together, these results link equilibrium computation in the empirical model to the true game: when µ⋆ ≥ 4∆t − ε, the solver returns an approximate NE; when µ⋆ < 4∆t − ε, solver failure yields a sound certificate of non-existence once uncertainty is sufficiently small. Combined with the value stability results, this yields the following per-episode guarantee. Corollary 5 (Per-episode value gap). If µ⋆ ≥ 4∆t − ε, then V ⋆ − u(σ̂t , P ⋆ ) ≤ 4∆t . [Proof in App. E] It therefore remains to ensure that ∆t falls below ε/4 in a finite number of samples. Since ∆t scales with the maximum per-(s, a) confidence radius, this requires sufficient coverage of all relevant slots. We tackle this using a targeted, RMDP-based exploration scheme presented in the next section. 4.2

Exploration

A key challenge in PAC learning of concurrent games is obtaining sufficient joint state–action coverage from stochastic trajectories under transition uncertainty. To isolate this statistical challenge, we assume centralised exploration, allowing the learner to coordinate the players’ joint actions. To this end, we construct an auxiliary exploration RMDP that casts coverage of under-visited (s, a)-pairs as a robust reachability problem. For each (s, a), we maintain a boolean flag indicating whether the slot is known, i.e., whether it has been visited sufficiently many times; this threshold is precisely defined in Lemma 20, App. F. Let Ut and Kt denote the sets of unknown and known (non-target) slots at the beginning of episode t, respectively (so U1 = Xnt ; see formal definition in App. F). 6

Exploration RMDP. At each episode t, we construct an exploration RMDP Gte that coincides with the empirical RCSG Gt on all known slots. On each unknown slot (s, a) ∈ Ut , the model instead transitions deterministically to an auxiliary absorbing state z, with a nonzero reward accrued upon this transition. Note that this absorbing construction is used for analysis only (see App. F). The learner’s objective is to maximise expected reward, which is equivalent to maximising the probability of reaching unknown slots under this construction. Definition 5 (Exploration RMDP). The exploration RMDP at episode t is an L1 -MDP Gte = (S e , s, Ae , Pte , rte ) where S e := S ∪ {z} and Ae := A1 × A2 . For each (s, a) ∈ S e × Ae : if (s, a) ∈ Ut ∨ s = z ∨ s ∈ ST then Pte (s, a) = {δz }, where δz is the Dirac distribution that assigns probability 1 to z and 0 to all others; else Pte (s, a) = Pt (s, a); rte is such that rte (s, a) := 1[(s, a) ∈ Ut ]. e

Next, let pet (P ) := Pσt ,P [reach Ut ], i.e., the probability of reaching any unknown (s, a)-pair during episode t. Define the exploration profile as σte ∈ arg max uPte (σ) = arg max inf e pet (P ). σ∈Σ P ∈Pt

σ∈Σ

(1)

This pessimistic (robust) objective is essential for the high-probability global coverage guarantee (Lemma 19, App. G) used to prove Theorem 7: a best-case visitation probability under P ∈ Pt need not lower-bound the visitation probability under the true kernel P ⋆ . Assumption 1 (Graph reachability). Let PSupp := {P : Supp(P ) = Supp(P ⋆ )}. The game graph of G ⋆ is such that every (s, a) ∈ Xnt is reachable from s̄ under some profile, i.e., preach :=

min

max

inf

(s,a)∈Xnt σ∈Σ P ∈PSupp

Pσ,P [reach (s, a) before entering ST ] > 0.

(2)

Reachability conditions like Assumption 1 are standard in prior work [1, 7, 22]. Since the transition support of P ⋆ is known as input to Alg. 1, preach can be precomputed by solving a corresponding reachability RMDP over the known game graph (see App. J for details). Together with the exploration RMDP construction, this yields the following result; the full proof is in App. F. Lemma 6 (Exploration probability). For all episodes t ≥ 1 with Ut ̸= ∅, pet (P ⋆ ) ≥ preach . We execute σte in G ⋆ to sample trajectories. By collecting multiple samples per episode (with the number specified in Proposition 17, App. F), each episode visits an unknown slot with nontrivial probability. Repeating this across episodes yields high-probability coverage of all relevant slots, ensuring that each is visited sufficiently often. The precise sample and episode counts are derived in Lemma 19 and Corollary 21 (App. F), and are used to establish the sample complexity bound in the next section. 4.3

PAC-CSG

We now combine the previous results to obtain the PAC guarantee, in line with Definition 4.
2 e Rmax Theorem 7 (PAC guarantee for finite-horizon objectives). Set nmin = O H 4 |S|/ε2 . Then with probability at least 1 − δ, Alg. 1 terminates after at most   2 Rmax H 4 |S|2 |A| e (3) O ε2 preach e suppresses logarithmic factors in the problem parameters. Upon trajectory samples, where O(·) termination, the algorithm’s output satisfies the PAC-CSG guarantee of Definition 4. Proof sketch. We split the failure budget as δ cont = δ cov = δ/2 and condition on E := E cont ∩ E cov , which holds with probability ≥ 1 − δ. On E cont , Corollary 5 reduces near-optimality to ensuring
2 e Rmax ∆t ≤ ε/4, which holds once every (s, a) ∈ Xnt is visited at least nmin = O H 4 |S|/ε2 times (Lemma 20). Under Assumption 1, Lemma 19 shows that this coverage is achieved after e min |S||A|) episodes: for each episode, let Xt indicate whether at least one sampled trajectory O(n reaches an unknown slot. Since these indicators are history-dependent, we apply Freedman’s inequality to their martingale differences, using the lower bound preach from Lemma 6, to obtain a high-probability bound on the number of episodes needed until all relevant slots are sufficiently e visited. Moreover, Proposition 17 yields O(log t/preach ) trajectories per episode t, giving the stated sample complexity. Finally, Proposition 4 yields the output branching. Full details are in App. G. 7

Infinite-horizon extension. We further assume almost-sure reachability of ST , i.e., ST is reached with probability 1 from every state under every P ∈ PSupp by some profile (Assumption 3), following prior work [5, 18, 27]. This ensures value iteration convergence but not the existence of stationary NE. Under this assumption, the process admits an effective horizon Heff which upper bounds the stopping time, with Heff ≤ |S|/pT (see Lemma 24). Here, pT is the minimum worst-case probability of reaching ST within |S| steps from any state. Replacing H with Heff yields the corresponding infinite-horizon guarantees, with constants adjusted accordingly. Full details are in App. H.

5

Experimentation

We evaluate our method on a suite of benchmark CSGs to validate our theoretical guarantees. Experimental setup. We implement Alg. 1 in Java and evaluate it in the PRISM-games model checker [26]. Unless otherwise stated, we set δ = 0.05, ε = 0.2 and Rmax = 1. For RQ1, we instead use ε = 0.1. Results are averaged over 10 random seeds for trajectory sampling. For the learning-dynamics experiments in Appendix K.2, we additionally evaluate the empirical model and strategy against the known ground-truth CSG; these quantities are used only for evaluation and are not available to the learner. Experiments ran on a 3.2 GHz Apple M1 CPU, 16 GB RAM. Our implementation, including the models and property specifications, is available at https://github. com/7angel4/prism-games/tree/csg-learning. We compare our learners’ output against the PRISM-games CSG solver as ground truth. Benchmarks. We evaluate on six small, interpretable CSGs, chosen to enable repeated exact NE computation and comparison against exact solutions. These are illustrated in Fig. 2, App. K. Each benchmark is paired with a set of finite- and infinite-horizon properties expressed in probabilistic alternating-time temporal logic with rewards (rPATL) [11, 27], designed to isolate a distinct challenge: 1) Cyclic Preferences has no exact stationary NE for infinite-horizon reachability reward, testing detection of non-existence; 2) Delayed Coordination isolates hard exploration under sparse, delayed rewards; 3) Hide-or-Run adapted from De Alfaro et al. [13] has no stationary NE profiles; its value is only achieved in the limit via mixed strategies converging to “hide w.p. 1” for the zero-sum objective of player 1 eventually reaching s1 ; 4) Mixed NE requires a mixed equilibrium; 5) Safe vs. Risky contrasts actions with differing sensitivity to transition probabilities; and 6) Traffic Merge evaluates safety-critical multi-step coordination. Together, they cover all objective types in our framework. We aim to address the following research questions: RQ1: Correctness. (a) Near-optimality. When G ⋆ admits an NE, does the algorithm output an ε-optimal ε-NE? (b) Equilibrium existence detection. When no exact stationary NE exists, when does the algorithm return a sound non-existence certificate, and when does incompleteness arise? RQ2: Exploration strategy. How does the robust exploration RMDP compare with simpler or optimistic exploration rules under an otherwise identical PAC loop and stopping condition? We compare against: (i) uniform-random joint-action exploration; (ii) round-robin exploration targeting the least-visited unknown slot under the point-estimate model; and (iii) optimistic exploration, which maximises best-case rather than worst-case reachability (see Eq. (1)) over the current uncertainty set. We define each explorer in detail in Appendix K.1. RQ3: Empirical sample-complexity scaling. How does the number of sampled trajectories until convergence scale with the number of states |S|, joint actions |A|, horizon H and precision ε? We use parametrised variants of Safe vs. Risky that vary one problem dimension at a time while preserving the underlying equilibrium structure. Specifically, we test |S| ∈ {4, 8, 12, 20, 36, 60}, |A| ∈ {4, 9, 16, 25, 36, 49, 64}, H ∈ {1, 2, 3, 5, 7, 9, 11, 15} and ε ∈ {0.05, 0.1, 0.15, 0.2, 0.3, 0.4}. For each scaling experiment, all parameters other than the varied dimension are held at the default values |S| = 4, |A| = 4 (as in Fig. 2e), with H = 3, ε = 0.2, and the same property used throughout. 5.1

Results and Discussion

RQ1(a) Near-optimality. For all case studies in Table 1 that admit an exact NE (i.e., µ̄ ≥ 0), the learned profile σ̂ attains the same true-game value as the oracle up to ties between indifferent actions. 8

Table 1: Comparison of our algorithm’s output with the CSG-solver oracle across benchmarks. All cases use ε = 0.1. The returned profile attains the oracle’s true-game value whenever a stationary NE exists. For Cyclic Preferences and the first Hide-or-Run case, no stationary NE exists; the algorithm returns NOT_FOUND in the former and an ε-NE approaching the limiting equilibrium value in the latter. For the second Safe vs. Risky case, the NE value is ∞, which our algorithm also recovers. The final column reports the robust-value estimate gap V ⋆ − V̂ . Full results are in Table 3, App. K.3. Case study

Property

Cyclic Prefs. Delayed Coord. Hide-or-run Hide-or-run Mixed NE Safe vs. Risky Safe vs. Risky Traffic Merge

⟨⟨p1 : p2 ⟩⟩max=? (Rr1 [F s3 ] + Rr2 [F s3 ])
⟨⟨p1 : p2 ⟩⟩max=? Rr1 [C≤5 ] + Rr2 [C≤5 ] ⟨⟨p1 ⟩⟩Pmax=? [F  s1 ]  ⟨⟨p1 ⟩⟩Pmax=? F ≤5 s1 ⟨⟨p1 : p2 ⟩⟩max=? (P[F s1 ] + P[F s2 ]) ⟨⟨p1 : p2 ⟩⟩max=? (P[F s1 ] + P[F s2 ]) ⟨⟨p1 : p2 ⟩⟩max=? (Rr1 [F s1 ] + Rr2 [F s2 ]) ⟨⟨p1 ⟩⟩Pmax=? [F ≤5 s4 ]

ε-NE found?

NE exists?

V ⋆ − V̂ (×10−3 )

✗ ✓ ✓ ✓ ✓ ✓ ✓ ✓

✗ ✓ ✗ ✓ ✓ ✓ ✓(∞) ✓

– 1.573 ± 0.069 0.000 ± 0.000 0.000 ± 0.000 3.083 ± 0.000 1.743 ± 0.000 – 0.000 ± 0.000

Table 2: Samples to convergence (millions) and value gap V ⋆ − V̂ for our robust exploration RMDP and the optimistic, round-robin, and uniform-random baselines. Values are reported as mean ± standard deviation; the lowest value gap and sample count for each benchmark are shown in bold. V ⋆ − V̂

Samples

0.005 ± 0.000 0.005 ± 0.000 0.005 ± 0.000 0.005 ± 0.000

6.90 ± 0.00 6.90 ± 0.00 16.22 ± 0.00 7.02 ± 0.00

Samples

Robust (ours) 5.90 ± 0.00 Optimistic 5.90 ± 0.00 Round-robin 6.09 ± 0.09 Uniform 11.61 ± 0.01

6 × 107

(R2 = 0.998; error < 0.04%)

samples (log scale)

samples (log scale)

N π ∝ |S|1.44 8

10

107 4

8

12

20

|S| (log scale) 1 (a) |S|-scaling

36

60

4 × 107

V ⋆ − V̂

N π ∝ |A|0.89

109

(R2 = 1.000; error < 0.04%)

2 × 107 7

10

4

9

16

25

Samples

V ⋆ − V̂

Samples

V ⋆ − V̂

– – – –

42.95 ± 0.00 43.15 ± 0.87 44.92 ± 0.83 730.09 ± 0.28

0.000 ± 0.000 0.060 ± 0.097 0.060 ± 0.097 0.180 ± 0.063

0.000 ± 0.000 18.41 ± 0.01 0.000 ± 0.000 18.41 ± 0.01 0.000 ± 0.000 19.07 ± 0.01 0.000 ± 0.000 46.84 ± 0.02

3 × 107

6 × 106

Cyclic Prefs. Delayed Coord. ⟨⟨p1 : p2 ⟩⟩max=? (Rr1 [F s3 ] + Rr2 [F s3 ]) ⟨⟨p1 : p2 ⟩⟩max=? (P[F s3 ] + P[F s3 ])

samples (log scale)

Explorer

Traffic Merge   ⟨⟨p1 ⟩⟩Pmax=? F ≤5 s4

36 49 64

(R2 = 0.980; error < 0.10%)

8

10

107 106 105 100

|A| (log scale)

101

H (log scale)

1 (b) |A|-scaling

108

N π ∝ H 3.94

samples (log scale)

Safe vs. Risky
⟨⟨p1 : p2 ⟩⟩max=? P[F ≤3 s1 ] + P[F ≤3 s2 ]

1 (c) H-scaling

N π ∝ 1/ε2.11

(R2 = 1.000; error < 0.08%)

107

0.05

0.1

0.15 0.2

0.3

0.4

ε (log scale) 1 (d) ε-scaling

Figure 1: Scaling of sample complexity (log–log scale) in the Safe vs. Risky game, following the setup in RQ3, with respect to (a) |S|, (b) |A|, (c) H, and (d) ε. Error bars show standard deviation over 10 runs; all are plotted but negligible (< 0.10% of the mean) and thus not visible. For the finite-valued cases, this yields a value gap V ⋆ − u(σ̂, P ⋆ ) = 0 ≪ ε. The robust value estimate V̂ can, however, differ slightly from V ⋆ . Nevertheless, the estimation gap V ⋆ − V̂ consistently remains below 4∆t ≤ ε, as guaranteed by Lemma 14 (App. E). This empirically validates the stopping condition ∆t ≤ ε/4, which ensures near-optimality of the output profile via Corollary 5: once ∆t falls below this threshold, the robust solution computed on Pt transfers to the true model with error at most 4∆t ≤ ε. Further, the second Safe vs. Risky property exhibits a degenerate case in which the SWNE value is unbounded: since both s1 and s2 are absorbing self-loops, once either is reached the game loops indefinitely, allowing the corresponding player to accumulate unbounded reward (while the reachability objective is effectively zero-sum); see Fig. 2, App. K. The algorithm correctly returns V ⋆ = ∞ together with a profile that attains it, demonstrating that our implementation handles unbounded total reward despite assuming bounded per-step rewards in the analysis. RQ1(b) Equilibrium existence detection. Two benchmarks specifically consider the NE existence problem. 1) Cyclic Preferences provides a clean non-existence case. The game does not exhibit a fixed-point solution and possesses no exact NE. Our solver correctly returns NOT_FOUND in 10/10 runs, yielding a sound certificate that no exact stationary NE exists. This is consistent with Proposition 4 which stipulates that solver failure implies µ⋆ < 4∆t − ε, which is ≤ 0 at termination; and thus µ̄ ≤ 0 by Proposition 8, App. A. 2) Hide-or-Run illustrates incompleteness of the non-existence certificate. 9

The game has no optimal stationary profile, but only an NE value in the limit (i.e., approached by a sequence of mixed strategies). In all runs, our finite-sample learner returns an ε-NE approaching the limiting equilibrium (hide w.p. 0.999 at s0 ) rather than NOT_FOUND. This does not violate soundness, however: the non-existence certificate is required to be correct when emitted, but need not be emitted for every game lacking an exact stationary NE. RQ2 Exploration strategy. Table 2 compares all explorers under the same PAC loop and stopping criterion. Uniform exploration is consistently less sample-efficient, requiring 2.0× more trajectories on Safe vs. Risky, 2.5× on Cyclic Preferences, and 17× on Delayed Coordination. Round-robin performs similarly to the robust explorer on the shallow benchmarks but requires 2.3× more trajectories on Traffic Merge. Optimistic exploration has similar sample consumption to robust exploration on most benchmarks, but uses slightly more samples on Delayed Coordination, where it also gives less stable and less accurate robust-value estimates: its estimated value differs from the true value by 0.06, whereas our robust explorer gives a near-perfect estimate. These results suggest that targeted exploration matters most when useful state-action pairs are difficult to reach, while pessimistic or robust planning provides more reliable coverage under transition uncertainty. We further analyse the learning dynamics of our robust explorer in Appendix K.2, including the evolution of uncertainty, known-slot coverage, confidence-radius imbalance, and per-episode sample consumption. RQ3 Sample complexity scaling. Fig. 1 shows the dependence of total sample consumption on different problem parameters. Log–log fits give empirical exponents of 1.44 for |S|, 0.89 for |A|, 3.94 for H and 2.11 for 1/ε. These are consistent with the worst-case bound of |S|2 |A|H 4 /ε2 in Theorem 7. In particular, the horizon exponent closely tracks the theoretical dependence over the tested range, while state and action space growth is milder than the upper bound. These experiments do not establish tight asymptotic rates, but show that the observed scaling is consistent with the theorem over the tested instances.

6

Conclusion

We introduced PAC-CSG, the first PAC learning framework for general-sum concurrent stochastic games under transition uncertainty that handles stationary NE (non-)existence. The algorithm combines L1 uncertainty sets with a new RMDP formulation that casts joint state–action coverage as a robust reachability problem, and uses a black-box RCSG solver to compute ε-RSWNEs. Under a
2 e Rmax H 4 |S|2 |A|/(ε2 preach ) trajectory samples graph reachability condition, it terminates after O and outputs either an ε-social-welfare-optimal ε-NE or a sound certificate of NE non-existence. Beyond these guarantees, our results highlight two key insights: 1) robust equilibrium computation in the empirical model transfers to the true game; and 2) equilibrium non-existence can be detected in a sound, data-driven manner. Empirically, our framework achieves near-optimality, sound nonexistence detection, and sample complexity consistent with theory. Future work includes relaxing the standard assumptions of centralised exploration, known transition support, and reachability, as well as improving scalability in |S| and |A|, e.g., through value-aware exploration; see App. L for further discussion.

Acknowledgments and Disclosure of Funding This work is supported by the EPSRC Centre for Doctoral Training no. EP/Y035070/1 and the UKRI AI Hub on Mathematical Foundations of AI.

References [1] A. Al-Marjani, A. Tirinzoni, and E. Kaufmann. Active coverage for pac reinforcement learning. In G. Neu and L. Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 5044–5109. PMLR, 2023. URL https://proceedings.mlr.press/v195/al-marjani23a.html. [2] M. G. Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, page 263–272. JMLR.org, 2017. 10

[3] Y. Bai and C. Jin. Provable self-play algorithms for competitive reinforcement learning. In Proceedings of the 37th International Conference on Machine Learning, ICML’20. JMLR.org, 2020. [4] R. Berthon, J.-P. Katoen, M. Mittelmann, and A. Murano. Robust strategies for stochastic multiagent systems. In Proceedings of the 24th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’25, page 2437–2439, Richland, SC, 2025. International Foundation for Autonomous Agents and Multiagent Systems. ISBN 9798400714269. [5] D. P. Bertsekas and J. N. Tsitsiklis. An analysis of stochastic shortest path problems. Mathematics of Operations Research, 16(3):580–595, 1991. [6] P. Bouyer, N. Markey, and D. Stan. Mixed nash equilibria in concurrent terminal-reward games. In FSTTCS 2014, 2014. [7] R. I. Brafman and M. Tennenholtz. R-max-a general polynomial time algorithm for near-optimal reinforcement learning. Journal of Machine Learning Research, 3(Oct):213–231, 2002. [8] T. Brihaye, V. Bruyère, A. Goeminne, J.-F. Raskin, and M. Van den Bogaard. The complexity of subgame perfect equilibria in quantitative reachability games. Logical Methods in Computer Science, 16, 2020. [9] P. F. Castro and P. D’Argenio. Polytopal stochastic games. In Principles of Verification: Cycling the Probabilistic Landscape: Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birthday, pages 99—-117. Springer, 2024. [10] K. Chatterjee, K. Sen, and T. A. Henzinger. Model-checking ω-regular properties of interval Markov chains. In International Conference on Foundations of Software Science and Computational Structures, pages 302–317. Springer, 2008. [11] T. Chen, V. Forejt, M. Kwiatkowska, D. Parker, and A. Simaitis. Automatic verification of competitive stochastic systems. In C. Flanagan and B. König, editors, Tools and Algorithms for the Construction and Analysis of Systems, pages 315–330, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg. ISBN 978-3-642-28756-5. [12] L. De Alfaro and T. A. Henzinger. Concurrent omega-regular games. In Proceedings Fifteenth Annual IEEE Symposium on Logic in Computer Science (Cat. No. 99CB36332), pages 141–154. IEEE, 2000. [13] L. De Alfaro, T. A. Henzinger, and O. Kupferman. Concurrent reachability games. Theoretical computer science, 386(3):188–217, 2007. [14] L. Euler. De serie lambertina plurimisque eius insignibus proprietatibus. Acta Academiae scientiarum imperialis petropolitanae, pages 29–51, 1783. [15] Z. U. Farhat, D. Ghosh, G. K. Atia, and Y. Wang. Sample-efficient distributionally robust multi-agent reinforcement learning via online interaction, 2026. URL https://arxiv.org/ abs/2508.02948. [16] D. A. Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100–118, 1975. [17] R. Givan, S. Leach, and T. Dean. Bounded-parameter Markov decision processes. Artificial Intelligence, 122(1-2):71–109, 2000. [18] A. Y. He and D. Parker. Robust verification of concurrent stochastic games. In Proc. 32nd International Conference on Tools and Algorithms for the Construction and Analysis of Systems (TACAS’26), LNCS. Springer, 2026. [19] C. A. Holt and A. E. Roth. The nash equilibrium: A perspective. Proceedings of the National Academy of Sciences, 101(12):3999–4002, 2004. doi: 10.1073/pnas.0308738101. URL https: //www.pnas.org/doi/abs/10.1073/pnas.0308738101. [20] J. Hu and M. P. Wellman. Nash q-learning for general-sum stochastic games. J. Mach. Learn. Res., 4(null):1039–1069, Dec. 2003. ISSN 1532-4435. 11

[21] G. N. Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257–280, 2005. [22] T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. J. Mach. Learn. Res., 11:1563–1600, Aug. 2010. ISSN 1532-4435. [23] X. Jin, M. Dan, N. Zhang, W. Yu, X. Fu, and S. K. Das. Chapter 2 - game theory for infrastructure security: The power of intent-based adversary models11part of the results included in this chapter was presented in [1], [2]. In Handbook on Securing Cyber-Physical Critical Infrastructure, pages 31–53. Morgan Kaufmann, Boston, 2012. ISBN 978-0-12-415815-3. doi: https://doi.org/10.1016/B978-0-12-415815-3.00002-9. URL https://www.sciencedirect. com/science/article/pii/B9780124158153000029. [24] M. Kearns and S. Singh. Near-optimal reinforcement learning in polynomial time. Machine Learning, 49(2):209–232, 2002. ISSN 1573-0565. doi: 10.1023/A:1017984413808. URL https://doi.org/10.1023/A:1017984413808. [25] M. Kwiatkowska, G. Norman, and D. Parker. prismmodelchecker.org/, 2013–2026.

PRISM model checker.

https://www.

[26] M. Kwiatkowska, G. Norman, D. Parker, and G. Santos. PRISM-games 3.0: Stochastic game verification with concurrency, equilibria and time. In Proc. 32nd International Conference on Computer Aided Verification (CAV’20), volume 12225 of LNCS, pages 475–487. Springer, 2020. [27] M. Kwiatkowska, G. Norman, D. Parker, and G. Santos. Automatic verification of concurrent stochastic systems. Formal Methods in System Design, 58(1):188–250, 2021. [28] M. Kwiatkowska, G. Norman, D. Parker, and G. Santos. Correlated equilibria and fairness in concurrent stochastic games. In International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pages 60–78. Springer, 2022. [29] J. H. Lambert. Observationes variae in mathesin puram. Acta Helvetica, 3(1):128–168, 1758. [30] G. Li, Y. Chi, Y. Wei, and Y. Chen. Minimax-optimal multi-agent rl in markov games with a generative model. Advances in Neural Information Processing Systems, 35:15353–15367, 2022. [31] M. L. Littman. Markov games as a framework for multi-agent reinforcement learning. In W. W. Cohen and H. Hirsh, editors, Machine Learning Proceedings 1994, pages 157–163. Morgan Kaufmann, San Francisco (CA), 1994. ISBN 978-1-55860-335-6. doi: https://doi.org/10. 1016/B978-1-55860-335-6.50027-1. URL https://www.sciencedirect.com/science/ article/pii/B9781558603356500271. [32] Q. Liu, T. Yu, Y. Bai, and C. Jin. A sharp analysis of model-based reinforcement learning with self-play. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 7001–7010. PMLR, 2021. URL https://proceedings.mlr.press/v139/liu21z.html. [33] S. Ma, Z. Chen, S. Zou, and Y. Zhou. Decentralized robust v-learning for solving markov games with model uncertainty. J. Mach. Learn. Res., 24(1), Jan. 2023. ISSN 1532-4435. [34] T. Meggendorfer, M. Weininger, and P. Wienhöft. Solving robust Markov decision processes: Generic, reliable, efficient. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39(25), pages 26631–26641, 2025. [35] A. Nilim and L. El Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780–798, 2005. [36] K. Panaganti and D. Kalathil. Sample complexity of robust reinforcement learning with a generative model. In G. Camps-Valls, F. J. R. Ruiz, and I. Valera, editors, Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 9582–9602. PMLR, 28–30 Mar 2022. URL https://proceedings.mlr.press/v151/panaganti22a.html. 12

[37] K. Panaganti, Z. Xu, D. Kalathil, and M. Ghavamzadeh. Robust reinforcement learning using offline data. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS ’22, Red Hook, NY, USA, 2022. Curran Associates Inc. ISBN 9781713871088. [38] Z. Roch and Y. Wang. Distributionally robust Markov games with average reward, 2025. URL https://arxiv.org/abs/2508.03136. [39] L. S. Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095–1100, 1953. [40] L. Shi, E. Mazumdar, Y. Chi, and A. Wierman. Sample-efficient robust multi-agent reinforcement learning in the face of environmental uncertainty. In Proceedings of the 41st International Conference on Machine Learning, ICML’24. JMLR.org, 2024. [41] J. Stirling. Methodus differentialis: sive tractatus de summatione et interpolatione serierum infinitarum. 1730. [42] A. L. Strehl, L. Li, and M. L. Littman. Reinforcement learning in finite mdps: Pac analysis. Journal of Machine Learning Research, 10(84):2413–2444, 2009. URL http://jmlr.org/ papers/v10/strehl09a.html. [43] M. Suilen, T. Badings, E. M. Bovy, D. Parker, and N. Jansen. Robust Markov decision processes: A place where AI and formal methods meet. In Principles of Verification: Cycling the Probabilistic Landscape: Essays Dedicated to Joost-Pieter Katoen on the Occasion of His 60th Birthday, pages 126–154. Springer, 2024. [44] L. G. Valiant. A theory of the learnable. Communications of the ACM, 27(11):1134–1142, 1984. [45] J. Von Neumann and O. Morgenstern. Theory of games and economic behavior, princeton, 1944. [46] S. Wang, N. Si, J. Blanchet, and Z. Zhou. A finite sample complexity bound for distributionally robust q-learning. In F. Ruiz, J. Dy, and J.-W. van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 3370–3398. PMLR, 2023. URL https://proceedings. mlr.press/v206/wang23b.html. [47] T. Weissman, E. Ordentlich, G. Seroussi, S. Verdu, and M. J. Weinberger. Inequalities for the l1 deviation of the empirical distribution. Hewlett-Packard Labs, Tech. Rep, page 125, 2003. [48] W. Wiesemann, D. Kuhn, and B. Rustem. Robust Markov decision processes. Mathematics of Operations Research, 38(1):153–183, 2013. [49] W. Yang, L. Zhang, and Z. Zhang. Towards theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 50(6):3223–3248, 2022. [50] A. Zehfroosh and H. G. Tanner. Pac reinforcement learning algorithm for general-sum markov games. IEEE Transactions on Automatic Control, 68(5):2821–2831, 2023. doi: 10.1109/TAC. 2022.3219340. [51] K. Zhang, S. M. Kakade, T. Başar, and L. F. Yang. Model-based multi-agent rl in zero-sum markov games with near-optimal sample complexity. J. Mach. Learn. Res., 24(1), Jan. 2023. ISSN 1532-4435. [52] Z. Zhou, Z. Zhou, Q. Bai, L. Qiu, J. Blanchet, and P. Glynn. Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In A. Banerjee and K. Fukumizu, editors, Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pages 3331–3339. PMLR, 2021. URL https://proceedings.mlr.press/v130/zhou21d.html.

13

A

Proof for Nash margin property (Definition 3)

Proposition 8. µ̄ ≥ 0 iff µ⋆ ≥ 0. Proof. We prove both directions. (⇒) Suppose µ̄ ≥ 0. By definition of µ̄, there exists a profile σ with Nash margin at least 0, i.e., an NE profile. Therefore, the set of NE profiles is non-empty. By definition, an SWNE is an NE that maximises social welfare among all NE profiles. Since the set of NE profiles is non-empty, such a profile exists. As every SWNE is an NE, it must also have non-negative Nash margin, and hence µ⋆ ≥ 0.

(⇐) Since µ̄ is the maximum achievable Nash margin, by definition µ̄ ≥ µ⋆ ≥ 0.

B

Concentration bounds and confidence radii

In this section, we establish the Weissman concentration result (Lemma 9) and the containment event E cont (via Corollary 10) used in Sec. 4.1. We begin by analysing the concentration of empirical transition probabilities, which are used to construct the per-slot L1 uncertainty sets Pt (s, a) for each episode t ≥ 1 in Alg. 1.

For a state–action pair (s, a) ∈ Xnt , let Nsa ≥ 0 denote the number of independent samples drawn ⋆ from the true transition distribution Psa (·), and let Nsas′ denote the number of observed transitions ′ to state s . Further let

Succ(s, a) := {s′ | (s, a, s′ ) ∈ Supp(P ⋆ )}, and define the support-preserving simplex ∆+ (Succ(s, a)) := {p ∈ ∆(Succ(s, a)) : Supp(p) = Succ(s, a)} . Equivalently, ∆+ (Succ(s, a)) contains exactly those transition distributions whose support equals the known successor support of that slot. In the theoretical analysis, we use this support-preserving class; in implementation, we replace it with the corresponding closed simplex by imposing a 10−5 lower bound on probabilities within the support. This ensures graph preservation. If Nsa = 0, we define the empirical uncertainty set Pt (s, a) = ∆+ (Succ(s, a)) and set the point estimate Pbsa to be the uniform distribution over this support. If Nsa > 0, we define the empirical estimate as Pbsa (s′ ) = Nsas′ /Nsa , and construct the corresponding L1 uncertainty set as described below. Lemma 9 (Per-slot concentration). Consider a given state–action pair (s, a) with n ≥ 1 i.i.d. draws ⋆ from Psa (·), and fix a failure probability δ sa ∈ (0, 1). Define the Weissman L1 confidence radius r 2 2|S| − 2 sa αsa (n; δ ) := ln . n δ sa Then   ⋆ Pr ∥Psa (·) − Pbsa (·)∥1 ≤ αsa (n) ≥ 1 − δ sa . [↑ main]

Proof. We apply the Weissman inequality [47], which states that for any ε > 0,     nε2 ⋆ |S| b Pr ∥Psa − Psa ∥1 ≥ ε ≤ (2 − 2) exp − . 2 Setting the right-hand side equal to δ sa and solving for ε: r   nε2 2 2|S| − 2 |S| sa (2 − 2) exp − =δ =⇒ ε = ln =: αsa (n; δsa ). 2 n δ sa

14

Corollary 10 (Containment of P ⋆ in Pt ). Fix δ cont ∈ (0, 1). For brevity, write n := Nt (s, a) and cont define δsa,n := δ cont /(|S||A|n(n + 1)). For each episode t ≥ 1, define the slot-wise uncertainty set n
o cont Pt (s, a) := p ∈ ∆+ (Succ(s, a)) : ∥p − Pbsa,n ∥1 ≤ αsa n; δsa,n , and the global uncertainty set Pt :=

Y (s,a)∈Xnt

Pt (s, a),

cont cont where αsa n; δsa,n is the Weissman radius from Lemma 9, instantiated at δ sa := δsa,n . Then, with cont probability at least 1 − δ , P ⋆ ∈ Pt for all t ≥ 1. Proof. For each (s, a) and n ≥ 1, define the event n
o cont ⋆ cont Esa,n := ∥Psa − Pbsa,n ∥1 > αsa n; δsa,n . By Lemma 9, δ cont . |S||A|n(n + 1) Taking a union bound over all (s, a) ∈ Xnt and all possible sample counts n ≥ 1,   ∞ [ [ XX X 1 cont  cont = δ cont , Pr  Esa,n ≤ Pr(Esa,n ) = δ cont n(n + 1) n=1 cont cont Pr(Esa,n ) ≤ δsa,n =

(s,a) n≥1

(s,a) n≥1

Hence with probability at least 1 − δ cont , no such failure occurs for any (s, a) and any n, which implies P ⋆ ∈ Pt for all episodes t ≥ 1. Conditioning on containment of the true kernel. Define the per-episode and all-episode containment event: ^ Etcont := {P ⋆ ∈ Pt }, E cont := Etcont . t≥1

Following Corollary 10, we use the summable failure schedule δncont = δ cont /(n(n + 1)) to ensure that Pr(E cont ) ≥ 1 − δ cont . In the remainder of the analysis we condition on E cont .

C

Proofs for value sensitivity (Lemma 2)

We continue to derive the results in Sec. 4.1 of the main paper, focusing on the sensitivity lemma (Lemma 2) and presenting several useful corollaries. In the following, consider a fixed episode t ≥ 1 and a given strategy profile σ ∈ Σ. Proposition 11 (One-step error propagation). Let µh , µ bh denote the stopped state marginals at b time-step h under P and P respectively, following σ, started from the same initial state s0 ∈ S. Define 1 ∆L max αt (s, a). t := (s,a)∈Xnt

Then for all h ≥ 1,

1

∥µh − µ bh ∥1 ≤ h∆L t .

Proof. We prove the recursive bound 1

∥µh+1 − µ bh+1 ∥1 ≤ ∥µh − µ bh ∥1 + ∆L t ,

(4)

from which the result follows by induction using µ0 = µ b0 = δs0 , i.e., the Dirac distribution that assigns probability 1 to state s0 and 0 to all others. 15

For s ̸∈ ST , define the mixed one-step kernels X Ks := σ(a|s)P (·|s, a),

b s := K

X

a

a

Then

X

µh+1 =

µh (s)Ks ,

X

µ bh+1 =

µh+1 − µ bh+1 =

bs, µ bh (s)K

s̸∈ST

s̸∈ST

and hence

X s̸∈ST

(µh (s) − µ bh (s))Ks +

Taking L1 norms and applying the triangle inequality: X (µh (s) − µ bh (s))Ks ∥µh+1 − µ bh+1 ∥1 ≤

1

s̸∈ST

First term.

σ(a|s)Pb(·|s, a).

X s̸∈ST

+

b s ). µ bh (s)(Ks − K

X

bs) µ bh (s)(Ks − K

s̸∈ST

1

.

(5)

Let cs := µh (s) − µ bh (s). Since each Ks is a probability distribution, X X s′

s̸∈ST

cs Ks (s′ ) ≤

X s̸∈ST

|cs |

X

Ks (s′ ) =

s′

X s̸∈ST

|cs |,

hence X s̸∈ST

Second term.

(µh (s) − µ bh (s))Ks

1

≤ ∥µh − µ bh ∥1 .

By convexity,

X s̸∈ST

bs) µ bh (s)(Ks − K

≤ 1

For each s ̸∈ ST , b s ∥1 ≤ ∥Ks − K

X a

s̸∈ST

b s ∥1 ≤ max ∥Ks − K b s ∥1 . µ bh (s)∥Ks − K s̸∈ST

σ(a|s)∥Psa − Pbsa ∥1 ≤ max ∥Psa − Pbsa ∥1

= max a

X

a

X s′

1

|Psa (s′ ) − Pbsa (s′ )| ≤ max αt (s, a) = ∆L t . a

where the last inequality follows from the construction of Pt (see Corollary 10). Substituting into (5) gives 1

∥µh+1 − µ bh+1 ∥1 ≤ ∥µh − µ bh ∥1 + ∆L t . Unrolling the recursion yields 1

∥µh − µ bh ∥1 ≤ h ∆L t . 1 L1 ⋆ b Lemma 2 (Sensitivity). Define ∆t := 12 Rmax H 2 ∆L t , where ∆t := max(s,a)∈Xnt ∥Psa − Psa ∥1 . Then for any P ∈ Pt , profile σ, player i ∈ N , and state s0 ∈ S, |ui (σ, P | s0 ) − ui (σ, Pb | s0 )| ≤ ∆t .

[↑ main]

Proof. The left-hand side could be rewritten as: "H−1 # "H−1 # X X b σ,P σ, P |ui (σ, P | s0 ) − ui (σ, Pb | s0 )| = E ri (sh , ah ) − E ri (sh , ah ) h=0

=

H−1 Xh h=0

h=0

i b Eσ,P [ri (sh , ah )] − Eσ,P [ri (sh , ah )] .

16

Note that for bounded probabilistic reachability, we use the equivalent finite-horizon terminal-reward encoding, so the same argument applies. Moreover, XX Eσ,P [ri (sh , ah )] = Pσ,P (sh = s)σ(a | s) · ri (s, a) s

=

a

X s

X X µh (s)riσ (s), µh (s) σ(a | s)ri (s, a) = s

a

where riσ (s) := Ea∼σ(s) [ri (s, a)]. By assumption, |riσ (s)| ≤ Rmax . Thus, LHS =

H−1 XX h=0

≤

H−1 X h=0

s

riσ (s) µh (s) − µ bh (s)

max |riσ (s)| · s

1

≤ Rmax ∆L t ≤

H−1 X

X s

|µh (s) − µ bh (s)| ≤ Rmax

h = Rmax ∆L t

h=0

1

H−1 X h=0

∥µh − µ bh ∥1

H(H − 1) 2

(by Proposition 11)

1 1 2 H Rmax ∆L t =: ∆t . 2

Henceforth, we define 1

∆t := 12 Rmax H 2 ∆tL ,

where

1

∆L t :=

⋆ max ∥Psa − Pbsa ∥1 .

(s,a)∈Xnt

Corollary 12. For any P, P ′ ∈ Pt , any strategy profile σ, and each player i ∈ N : |ui (σ, P ) − ui (σ, P ′ )| ≤ 2∆t .

Proof. By the triangle inequality and Lemma 2 (applied twice), |ui (σ, P ) − ui (σ, P ′ )| ≤ ui (σ, P ) − ui (σ, Pb) + ui (σ, Pb) − ui (σ, P ′ ) = 2∆t . Corollary 13 (Social-welfare sensitivity). For any P ∈ Pt and any strategy profile σ: u(σ, P ) − u(σ, Pb) ≤ 2∆t . Consequently, for any P, P ′ ∈ Pt :

|u(σ, P ) − u(σ, P ′ )| ≤ 4∆t .

Proof. Apply Lemma 2 to each player i ∈ N and sum up: X X u(σ, P ) − u(σ, Pb) ≤ ui (σ, P ) − ui (σ, Pb) ≤ ∆t = 2∆t . i∈N

i∈N

The pairwise bound follows identically from Corollary 12.

D

Proofs for equilibrium existence (Proposition 4)

This section establishes the key properties of the solver oracle (Proposition 4) that link robust equilibrium computation in the empirical model to equilibrium existence in the true game. We first formalise the solver oracle (Assumption 2), then show that any exact NE of the true game induces an approximate RNE in the empirical model (Lemma 3), and use this to derive the solver guarantees (Proposition 4). Henceforth, we assume access to a black-box (L1 -)RCSG solver S OLVEL1CSG with tolerance ε ≥ 0, which computes an ε-RSWNE of the empirical RCSG Gt . Below we use the notation of Alg. 1. 17

Assumption 2 (S OLVEL1CSG oracle). Consider an (L1 -)RCSG G with uncertainty set P. Given tolerance ε ≥ 0, the solver returns (σ̂, V̂ , found) = S OLVEL1CSG(G, ε) such that found = true iff σ̂ is an ε-RSWNE of G, in which case V̂ = uP (σ̂). Equivalently, found = false iff Σε-RNE (P) = ∅. Note that σ̂ ∈ Σε-RNE (P) implies Σε-RNE (P) ̸= ∅, so the failure condition is equivalently stated as Σε-RNE (P) = ∅. Assumption 2 abstracts equilibrium computation as an oracle, yielding an information-theoretic PAC guarantee that is decoupled from the solver’s computational complexity. Practical solvers for general-sum L1 -RCSGs under our objectives do exist (e.g., in PRISM-games [18]), although polynomial-time implementations are currently known only in certain settings (e.g., the zero-sum case [18]). We defer a detailed discussion of computational aspects to App. L. At each episode t, the solver either succeeds or fails to find an ε-RSWNE of Pt . The following result characterises how each outcome relates to equilibrium properties of the true game G ⋆ . Lemma 3 (NE(P ⋆ ) ⇒ approximate RNE(Pt )). If σ is an (exact) NE under P ⋆ achieving Nash margin µ := µ(σ, P ⋆ ) ≥ 0, then it is also an (4∆t − µ)-RNE under Pt . [↑ main] Proof. Let σ be an NE under P ⋆ with Nash margin µ ≥ 0. By the triangle inequality, for any P ∈ Pt and player i ∈ N , we have: ui (σ−i [σi′ ], P ) − ui (σ, P ) ≤ [ui (σ−i [σi′ ], P ) − ui (σ−i [σi′ ], P ⋆ )] + [ui (σ−i [σi′ ], P ⋆ ) − ui (σ, P ⋆ )] + [ui (σ, P ⋆ ) − ui (σ, P )] ≤ 2∆t − µ + 2∆t = 4∆t − µ where the last inequality follows from Corollary 12 and the definition of µ (Definition 3). Since the bound holds for every P ∈ Pt , taking inf preserves the inequality, giving inf [ui (σ−i [σi′ ], P ) − ui (σ, P )] ≤ 4∆t − µ ∀i ∈ N . P ∈Pt

Hence σ is an (4∆t − µ)-RNE under Pt .

Proposition 4 (Solver guarantees for equilibrium computation). On the event E cont : (1) (Equilibrium transfer) If the solver returns an ε-RSWNE σ̂ of Pt , then σ̂ is an ε-NE of G ⋆ .

(2) (Failure implies near non-existence) If the solver returns NOT_FOUND, then either µ⋆ is undefined or µ⋆ < 4∆t − ε. [↑ main]

Proof. We prove each part individually. 1. Conditioning on E cont we have P ⋆ ∈ Pt . By definition of an ε-RSWNE (see after Definition 2), every ε-RSWNE under Pt is also an ε-RNE under Pt , and every ε-RNE under Pt is an ε-NE of every P ∈ Pt including P ⋆ . Therefore, if the solver returns an ε-RSWNE σ̂ under Pt , then σ̂ is an ε-NE of P ⋆ (the transition kernel of G ⋆ ). 2. Suppose the solver returns NOT_FOUND. By Assumption 2, this means that Σε-RNE (Pt ) = ∅, i.e., no ε-RNE exists under Pt . We now distinguish two cases according to the sign of µ̄ := maxσ∈Σ µ(σ, P ⋆ ) (defined in Definition 3). (a) If µ̄ < 0, then no exact NE, and hence no SWNE (i.e., the NE that achieves the highest social welfare) exists under P ⋆ . However, the social-welfare optimal Nash margin µ⋆ := µ(σ ⋆ , P ⋆ ) (Definition 3) is well-defined only when the SWNE σ ⋆ exists, therefore trivially µ⋆ is undefined. (b) If µ̄ ≥ 0, then ΣNE (P ⋆ ) ̸= ∅, so the SWNE σ ⋆ exists and µ⋆ = µ(σ ⋆ , P ⋆ ) is welldefined. Now suppose, for contradiction, that µ⋆ ≥ 4∆t − ε. Then Lemma 3 implies that σ ⋆ is also a (4∆t − µ⋆ )-RNE under Pt . Since 4∆t − µ⋆ ≤ 4∆t − (4∆t − ε) = ε, ⋆ σ is also an ε-RNE under Pt . Hence Σε-RNE (Pt ) ̸= ∅, and Assumption 2 guarantees that the solver would return FOUND with an ε-RSWNE under Pt , contradicting the assumption that the solver returned NOT_FOUND. 18

E

Proofs for anytime guarantees (Corollary 5)

We now derive anytime guarantees on the robust estimation error V ⋆ − uPt (σ̂) (Lemma 14) and the value gap V ⋆ − u(σ̂, P ⋆ ) (Corollary 5, Sec. 4.1). In this section we assume µ̄ ≥ 0 so that ΣNE (P ⋆ ) ̸= ∅ and hence V ⋆ is well-defined. Also recall that σ̂ is an ε-RSWNE under Pt by Assumption 2. Lemma 14 (Anytime upper bound for V ⋆ ). If µ⋆ ≥ 4∆t − ε, then V ⋆ − uPt (σ̂t ) ≤ 4∆t . Proof. Since µ⋆ ≥ 4∆t − ε, Lemma 3 implies that σ ⋆ ∈ Σε-RNE (Pt ) ̸= ∅. By Corollary 13 applied to σ ⋆ , for every P ∈ Pt : u(σ ⋆ , P ) ≥ u(σ ⋆ , P ⋆ ) − 4∆t = V ⋆ − 4∆t .

Taking inf over P ∈ Pt :

inf u(σ ⋆ , P ) = uPt (σ ⋆ ) ≥ V ⋆ − 4∆t .

P ∈Pt

Since σ̂t maximises the robust value over Σε-RNE (Pt ) and σ ⋆ ∈ Σε-RNE (Pt ): uPt (σ̂t ) =

sup σ∈Σε-RNE (Pt )

uPt (σ) ≥ uPt (σ ⋆ ) ≥ V ⋆ − 4∆t

=⇒

V ⋆ − uPt (σ̂t ) ≤ 4∆t .

Corollary 5 (Per-episode value gap). If µ⋆ ≥ 4∆t − ε, then V ⋆ − u(σ̂t , P ⋆ ) ≤ 4∆t .

[↑ main]

Proof. Immediate from Lemma 14 since u(σ̂t , P ⋆ ) ≥ uPt (σ̂t ) conditioning on E cont .

F

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

This section provides the technical results underlying Sec. 4.2. We first show that the confidence allocation δtcov sums to δ cov (Proposition 18), then bound the number of trajectories per episode required to discover an unknown slot with probability at least 1 − δtcov (Proposition 17), and finally establish the exploration probability lower bound (Lemma 6). Recall the following notation for the exploration analysis. A non-target slot (s, a) is known if it has been visited at least nmin times (defined in Lemma 20, App. G), and unknown otherwise. Let Ut = {(s, a) ∈ Xnt : Nt (s, a) < nmin },

Kt = Xnt \ Ut

denote the sets of unknown and known slots, respectively, at the beginning of episode t. Here, Nt (s, a) is the visit count of (s, a) by episode t. Further define Ntot := |Xnt |nmin ≤ |S||A|nmin , the total number of visits required across all relevant slots. Interpreting the exploration RMDP construction. Consider Definition 5 of the exploration RMDP. The absorbing construction is used purely for analysis: in the implementation, trajectories are not terminated upon visiting Ut or ST . This does not affect the guarantee, since visiting some (s, a) ∈ Ut depends only on the trajectory prefix up to the first such visit. Continuing the trajectory can only increase the probability of this event, so the lower bound in Lemma 6 remains valid. The state z ensures that expected reward coincides with visitation probability (each trajectory contributes at most once); without it, the objective would instead reflect expected visit counts. Finally, the exploration RMDP remains unchanged as long as Ut does not change. This allows an implementation optimisation: Gte need only be re-solved when new (s, a) pairs become known, instead of doing so at every episode. We now show that the reachability constant preach lower bounds the exploration probability pet (P ⋆ ). Lemma 6 (Exploration probability). For all episodes t ≥ 1 with Ut ̸= ∅, pet (P ⋆ ) ≥ preach . [↑ main] 19

Proof. Fix episode t with Ut ̸= ∅ and any (s† , a† ) ∈ Ut .

By Assumption 1, there exists a policy σreach ∈ Σ such that inf

P : Supp(P )=Supp(P ⋆ )

Pσreach ,P [reach (s† , a† ) before ST ] ≥ preach .

By definition of σte (1) as a maximiser of the robust value under rte , for any comparator σ ′ ∈ Σ, "H−1 # "H−1 # X X e ′ σ ′ ,P e σte ,P e rt (sh , ah ) . inf e E rt (sh , ah ) = uPte (σt ) ≥ uPte (σ ) = inf e E P ∈Pt

P ∈Pt

h=0

h=0

Due to the absorbing construction of Gte , any trajectory visits Ut at most once. Hence for any policy σ and kernel P , H−1 X rte (sh , ah ) = 1[reach Ut ] , h=0

and hence maximising expected cumulative reward is equivalent to maximising P[reach Ut ].

Therefore, by optimality of σte and taking σ ′ = σreach , e

inf Pσt ,P [reach Ut ] ≥ inf e Pσreach ,P [reach Ut ]

P ∈Pte

P ∈Pt

≥ inf e Pσreach ,P [reach (s† , a† ) before ST ] ≥ preach P ∈Pt

(6)

where the last inequality follows from the definition of preach (2). Now, since (s† , a† ) ∈ Ut , the event {reach (s† , a† )} depends only on the trajectory prefix before the first visit to Ut . By construction of Gte (Definition 5), any unknown slot (s, a) ∈ Ut transitions deterministically to the absorbing state z, so a trajectory reaching (s† , a† ) must avoid all other unknown slots beforehand. Consequently, the trajectory up to the hitting time of Ut depends only on transitions over Kt .

Finally, to relate this bound to the true kernel, define P e,⋆ ∈ Pte to coincide with P ⋆ ∈ Pt (conditioning on E cont ) on Kt and use the absorbing transitions on Ut ∪ ST . Since the event {reach Ut } depends only on transitions prior to the first visit to Ut , and these transitions lie entirely within Kt , we have e

⋆

e

pet (P ⋆ ) = Pσt ,P [reach Ut ] ≥ Pσt ,P

e,⋆

e

(6)

[reach Ut ] ≥ inf e Pσt ,P [reach Ut ] ≥ preach . P ∈Pt

Multi-trajectory exploration. Let (Ft )t≥0 be the filtration generated by the interaction history up to the end of episode t, and let Ft−1 denote the history available at the start of episode t. At each episode t, we draw Ntπ (conditionally) independent trajectories under σte . For i ∈ {1, . . . , Ntπ }, define

Xt,i := 1[trajectory i visits some (s, a) ∈ Ut ] ,

and let

Xt := 1[∃ i ≤ Ntπ : Xt,i = 1] .

Proposition 15. Conditioned on Ft−1 , the variables Xt,1 , . . . , Xt,Ntπ are independent and satisfy Pr(Xt,i = 1 | Ft−1 ) ≥ pet (P ⋆ )

for all i ∈ {1, . . . , Ntπ }.

Consequently, Pr(Xt = 0 | Ft−1 ) ≤ 1 − pet (P ⋆ )

Ntπ

.

Proof. Immediate from conditional independence of trajectories given Ft−1 and the definition of pet (P ⋆ ) (see Sec. 4.2). 20

Corollary 16 (Per-episode exploration probability). P(Xt = 0 | Ft−1 ) ≤ exp(−preach Ntπ ), Proof. Combining Lemma 6 and Proposition 15 we have P(Xt = 0 | Ft−1 ) = 1 − pet (P ⋆ )

Ntπ

π

≤ (1 − preach )Nt ≤ exp(−preach Ntπ ),

where the last inequality follows from the fact that 1 − x ≤ e−x for x ∈ (0, 1). Proposition 17 (Number of samples per-episode). Consider a given failure probability δtcov > 0. If   1 1 π Nt := log cov preach δt then P(Xt = 0 | Ft−1 ) ≤ δtcov . Proof. Substituting the given definition of Ntπ into the upper bound from Corollary 16 yields     1 1 1 exp(−preach Ntπ ) ≤ exp −preach · log cov = exp − log cov = δtcov . preach δt δt Hence P(Xt = 0 | Ft−1 ) ≤ δtcov as required. Proposition 18 (Coverage confidence allocation). Let δtcov :=

δ cov . t(t + 1)

(7)

Then, for every episode t ≥ 1 with Ut ̸= ∅, the probability of visiting some unknown (s, a) is at least 1 − δ cov . Proof. Using the telescoping identity X t≥1

X 1 = t(t + 1)



t≥1

1 1 − t t+1

 = 1,

we obtain X

δtcov = δ cov .

t≥1

By Proposition 17, each episode satisfies P(Xt = 0 | Ft−1 ) ≤ δtcov . Applying a union bound over all episodes (with Ut ̸= ∅) yields X P(∃t ≥ 1 : Xt = 0) ≤ δtcov = δ cov , t≥1

so with probability at least 1 − δ cov , every episode visits some unknown (s, a). Together, Propositions 17 and 18 give the multi-trajectory exploration strategy used in Alg. 1: drawing Ntπ = ⌈(1/preach ) log(1/δtcov )⌉ trajectories per episode guarantees that each episode is exploratory with probability at least 1 − δtcov . 21

G

Proofs for PAC-CSG (Theorem 7)

In this section we prove the main PAC guarantee, Theorem 7, by combining the three components developed in the previous Appendix items (B–F). The proof proceeds in four steps: (1) Confidence split: we set δ cont = δ cov = δ/2 and condition on E := E cont ∩ E cov , which holds with probability ≥ 1 − δ. (2) Episode count: Lemma 19 bounds
the number of episodes until all relevant slots are known ⋆ 2 4 2 2 e at T = O Rmax H |S| |A|/ε .

(3) Sample count: at each episode t, Proposition 17 (App. F) requires Ntπ = O(log t/preach ) P e ⋆ /preach ). sample trajectories, so the total number of samples required is t≤T ⋆ Ntπ = O(T (4) Correctness: at termination, Corollary 22 applies, yielding either an ε-approximate equilibrium in G ⋆ or the non-existence certificate.

Henceforth we fix the target accuracy ε ∈ (0, 1) and confidence δ ∈ (0, 1). Following Corollary 5, to attain the near-optimality guarantee, we aim for 4∆t ≤ ε

∆t ≤

=⇒

ε , 4

and under this scheme the non-existence margin threshold in Proposition 4(2) becomes 4∆t − ε = 0. For the confidence parameter δ, we distribute it as δ cont = δ cov := δ/2.

Lemma 19 (Counting episodes). Fix a confidence parameter δ cov ∈ (0, 1). With probability at least 1 − δ cov , the total number of episodes executed by the algorithm until all relevant slots are known is at most 8 T ⋆ := 2Ntot + ln(1/δ cov ). (8) 3 Proof. Let T be a fixed number of episodes before all relevant slots are known. For t = 1, . . . , T , recall the definitions of Xt,i , Xt , and Ft−1 from App. F. Further define N e :=

µt := E[Xt | Ft−1 ],

T X t=1

Xt ≤ T.

So N e is the number of exploratory episodes. Define martingale differences Yt := Xt − µt and Zt := −Yt . Then Zt are martingale differences with respect to the filtration Ft−1 . Thus MT :=

T X

Zt =

t=1

T X t=1

µt − N e .

We have E[Zt | Ft−1 ] = 0 and |Zt | ≤ 1. The predictable variance is v :=

T X t=1

E[Zt2 | Ft−1 ] =

T X t=1

µt (1 − µt ) ≤

T X t=1

µt ≤ T,

where the last inequality uses µt ≤ 1.

(9)

We aim to ensure with high probability that N e ≥ Ntot , the total number of visits required across all relevant slots. That is, Pr (N e ≤ Ntot ) ≤ δ cov . (10) By Proposition 17, P(Xt = 0 | Ft−1 ) ≤ δtcov . Therefore µt = P(Xt = 1 | Ft−1 ) ≥ 1 − δtcov and T X t=1

T T X X (7) cov µt ≥ (1 − δt ) = T − δtcov ≥ T − δ cov . t=1

t=1

22

Therefore, on the event {N e ≤ Ntot } we have MT =

T X t=1

Thus,

µt − N e ≥ T − δ cov − Ntot =: a.

Pr(N e ≤ Ntot ) ≤ Pr(MT ≥ a) .

(11)

(12)

Applying Freedman’s inequality [16], and using the bound on the variance v ≤ T (9), we obtain     a2 a2 ≤ exp − (13) Pr(MT ≥ a) ≤ exp − 2(v + a/3) 2(T + a/3) We now choose

T = 2Ntot + CL, L := ln(1/δ cov ), for a constant C > 0 to be determined. Then a = T − Ntot − δ cov = Ntot + CL − δ cov .

(14)

Substituting into the exponent in (13), to achieve (10) it suffices to ensure (Ntot + CL)2 (Ntot + CL − δ cov )2
≥
≥ L, 2 T + a/3 2 T + a/3 since δ cov > 0. Further,

1 1 1 a T + = 2Ntot + CL + Ntot + CL − δ cov ≤ 2Ntot + CL + Ntot + CL = (7Ntot + 4CL) 3 3 3 3 Therefore, it suffices to ensure

3(Ntot + CL)2 ≥ L. 2 (7Ntot + 4CL)

(15)

We find that C = 8/3 is the minimal constant ensuring that (15) holds; we defer the case analysis establishing this to the end (see Solving for C). With this choice of C, (13) yields Pr(MT ≥ a) ≤ exp(−L) = δ cov . By (12), this implies Pr(N e ≤ Ntot ) ≤ Pr(MT ≥ a) ≤ δ cov . Thus, with probability at least 1 − δ cov , we have N e ≥ Ntot . Since each exploratory episode discovers at least one previously unknown slot, a standard counting argument implies that after at most Ntot such episodes all relevant slots are known. Hence, with probability at least 1 − δ cov , all relevant slots become known within T episodes. Finally, substituting C = 8/3 into (14) yields T ⋆ = 2Ntot + 83 ln(1/δ cov ).

Solving for C. We now return to (15) and solve for the smallest constant C that ensures the inequality holds. Introduce x := Ntot /L ≥ 0 (so Ntot = xL). Then 3L2 (x + C)2 3L(x + C)2 = ≥L 2L(7x + 4C) 2(7x + 4C) 3(x + C)2 ⇐⇒ ≥1 2(7x + 4C) ⇐⇒ 3(x + C)2 ≥ 14x + 8C

⇐⇒ h(x) := 3(x + C)2 − 14x − 8C = 3x2 + (6C − 14)x + (3C 2 − 8C) ≥ 0. We require h(x) ≥ 0 for all x ≥ 0. Since h is convex, its minimum occurs at 7 x⋆ = − C. 3 We distinguish two cases. 23

(16)

Case A: x⋆ ≥ 0 (i.e., C ≤ 7/3).

The minimum of h on [0, ∞) occurs at x⋆ , yielding 49 h(x⋆ ) = 6C − . 3 Requiring h(x⋆ ) ≥ 0 gives C ≥ 49/18, contradicting C ≤ 7/3. Hence no feasible C exists in this regime. Case B: x⋆ < 0 (i.e., C > 7/3). In this case, the minimum of h on [0, ∞) occurs at the boundary x = 0, giving h(0) = C(3C − 8). Requiring h(0) ≥ 0 yields C ≥ 8/3.

Therefore, the smallest constant C such that (16) holds for all x ≥ 0 is C = 83 .

cont Lemma 20 (Counting per-slot visits). Define δsa,n := δ cont /(|S||A|n(n + 1)). If a slot (s, a) ∈ Xnt is visited s !' &  2  2 Rmax H 4 |S| ε2 16Rmax H4 δ cont e = O W − nmin := − −1 2 ε2 16Rmax H 4 2(2|S| − 2)|S||A| ε2

times, then

cont αsa (n; δsa,n ) ≤ ε/(2Rmax H 2 ).

Proof. Applying Lemma 9, we require s r 2 (2|S| − 2) 2 (2|S| − 2)|S||A|n(n + 1) ε ln = ln ≤ . cont n δsa,n n δ cont 2Rmax H 2 Solving for n.

Squaring both sides and rearranging gives

2 (2|S| − 2)|S||A|n(n + 1) ε2 (2|S| − 2)|S||A|n(n + 1) ε2 =⇒ ln n. ln ≤ ≤ cont 2 4 cont 2 n δ 4Rmax H δ 8Rmax H 4 Let (2|S| − 2)|S||A| ε2 C := , β := . 2 δ cont 8Rmax H4 Then we need ln (Cn(n + 1)) ≤ βn. Since n(n + 1) ≤ 2n2 for all n ≥ 1, it is enough to require Solving the corresponding equality gives

ln (2Cn2 ) ≤ βn.

  2 β n = − W−1 − √ , β 2 2C

(17)

where W is the Lambert W function [14, 29] defined by W (x)eW (x) = x, and W−1 is the lower real branch of W mapping x ∈ [−1/e, 0)2 to W−1 (x) ≤ −1. Therefore a sufficient condition is s & !' 2 16Rmax H4 ε2 δ cont n≥ − =: nmin W−1 − 2 ε2 16Rmax H 4 2(2|S| − 2)|S||A| Asymptotically, 2 Rmax H4 (2|S| − 2)|S||A| nmin = O log ε2 δ cont





 2  Rmax H 4 |S| e =O . ε2

2 The argument of W cont ∈ (0, 1)). −1 lies in [−1/e, 0) under the standard PAC parameter regimes (e.g., (δ

24

(18)

Henceforth we define nmin as in Lemma 20. Corollary 21. If every (s, a) ∈ Xnt is visited at least nmin times, then ∆t ≤ ε/4. Proof. By Lemma 20, if every (s, a) ∈ Xnt is visited at least nmin times, then on E cont we have: ε ⋆ cont ∀(s, a) ∈ Xnt . ∥Pbsa − Psa ∥1 ≤ αsa (nmin ; δsa,n )≤ min 2Rmax H 2 Therefore, by definition of ∆t : 1 ε 1 ε ⋆ ∆t = Rmax H 2 max ∥Pbsa − Psa = . ∥1 ≤ Rmax H 2 · 2 2 2 2Rmax H 4 (s,a)∈Xnt Corollary 22. Consider the S OLVEL1CSG oracle from Assumption 2 with tolerance ε. Suppose ∆t ≤ ε/4. Then: (a) If µ̄ ≥ 0, the solver returns FOUND, and the output profile σ̂ is an ε-NE under P ⋆ , satisfying V ⋆ − u(σ̂, P ⋆ ) ≤ ε. (b) If µ̄ < 0, then: (i) if the solver returns FOUND, the output profile σ̂ is still an ε-NE under P ⋆ ; (ii) if the solver returns NOT_FOUND, this provides a sound certificate that µ̄ is not welldefined or µ̄ < 0. Proof. Suppose ∆t ≤ ε/4. Then 4∆t − ε ≤ 0. We now proceed by a case analysis on the sign of µ̄. (a) Suppose µ̄ ≥ 0. By Proposition 8, this is equivalent to µ⋆ ≥ 0. Since µ⋆ ≥ 0 ≥ 4∆t − ε, the contrapositive of Proposition 4(2) implies that the solver returns FOUND. Now by Assumption 2, returning FOUND means that the output profile σ̂ is an ε-RSWNE under Pt . Then condition on E cont , Proposition 4(1) implies that σ̂ is also an ε-NE of P ⋆ ∈ Pt . Furthermore, since µ⋆ ≥ 4∆t − ε, we may apply Corollary 5, which gives V ⋆ − u(σ̂, P ⋆ ) ≤ 4∆t ≤ ε.

(b) Now suppose µ̄ < 0. (i) If the solver returns FOUND, outputting an ε-RSWNE σ̂ of Pt , then Proposition 4(1) implies that σ̂ is also an ε-NE of P ⋆ . (ii) If the solver returns NOT_FOUND, then by Proposition 4(2), either µ⋆ is undefined or µ⋆ < 4∆t − ε ≤ 0. Therefore, by Proposition 8, µ̄ is either undefined or satisfies µ̄ < 0.

e R2 H 4 |S|/ε2 . Then Theorem 7 (PAC guarantee for finite-horizon objectives). Set nmin = O max with probability at least 1 − δ, Alg. 1 terminates after at most  2  Rmax H 4 |S|2 |A| e (3) O ε2 preach e suppresses logarithmic factors in the problem parameters. Upon trajectory samples, where O(·) termination, the algorithm’s output satisfies the PAC-CSG guarantee of Definition 4. [↑ main] Proof. Recall the containment and coverage events \ E cont := {P ⋆ ∈ Pt }, E cov := {all (s, a) ∈ Xnt are visited at least nmin times}. t≥1

By Corollary 10 and Lemma 19, Pr(E cont ) ≥ 1 − δ cont , Pr(E cov ) ≥ 1 − δ cov . Setting δ cont = δ cov = δ/2 and defining E := E cont ∩ E cov , we have Pr(E) ≥ 1 − δ. 25

Sample complexity.

Let T := inf{t : ∆t ≤ ε/4}.

For any t < T , the stopping condition is false, in particular ∆t > ε/4. Substituting nmin from Corollary 21 into the episode bound T ⋆ from Lemma 19 yields   2   Rmax H 4 |S|2 |A| 1 8 . T ⋆ = 2|S||A|nmin + ln cov = O 3 δ ε2 By Proposition 17, each episode requires     1 1 1 t log cov = O log cov preach δt preach δ trajectories. Summing over episodes, ⋆

⋆

T X

1

t=1

preach

log

t δ cov

=

1

T X

preach

t=1

! ⋆

log t − T log δ

cov

1 (log(T ⋆ !) − T ⋆ log δ cov ) preach   ⋆   ⋆ T T⋆ e T =O log cov = O , preach δ preach =

where we use Stirling’s approximation [41] log(T !) = O(T log T ). Termination.

Let T cov denote the first episode at which E cov holds. On E cov , Lemma 19 gives T cov ≤ T ⋆ .

By Corollary 21, on E cont , once E cov holds we have ∆T cov ≤ ε/4. Hence, on E, the stopping condition is satisfied by episode T cov , and the algorithm terminates no later than T ⋆ . Correctness of the output. On E, we have both P ⋆ ∈ Pt for all t and ∆T ≤ ε/4. Therefore, Corollary 22 applies at termination, yielding the required output guarantee and completing the proof.

H

Supplementary details and proofs for infinite-horizon objectives

In this section, we extend the PAC-CSG framework to infinite-horizon objectives (unbounded probabilistic reachability and reachability reward / SSP). Following standard SSP formulations [5, 18, 27], we assume the existence of at least one proper profile and restrict attention to this class throughout the analysis. Let τT := inf{h ≥ 0 : sh ∈ ST } denote the hitting time of the target set ST . Further let Σprop ⊆ Σ be the set of proper profiles, under which τT < ∞ almost surely and all values are well-defined and that the underlying S OLVEL1CSG oracle converges. The assumption can be verified via standard graph-based reachability analyses under the known support structure induced by graph preservation [12]. Assumption 3 (Existence of a proper profile). There exists a proper profile σ ∈ Σprop , i.e., one that reaches the target set ST almost surely from all states under all support-preserving kernels: Pσ,P s (τT < ∞) = 1

∀s ∈ S, ∀P : Supp(P ) = Supp(P ⋆ ).

Additionally, the stopping probability is uniformly bounded away from zero: pT := min

inf

inf

s∈S σ∈Σprop P :Supp(P )=Supp(P ⋆ )

26

Pσ,P [τT ≤ |S| | s0 = s] > 0.

This condition strengthens properness by requiring a uniform lower bound on finite-time reachability. It is analogous to standard reachability and diameter assumptions in PAC and reinforcement learning analyses [2, 7, 22, 24], and to the properness conditions used in SSP formulations [5]. It is required to obtain the geometric tail bound in Proposition 23 and the finite effective horizon in Lemma 24. We discuss this assumption and its practical implications further in App. L. Next, we establish a geometric tail bound on the stopping time in terms of pT . Proposition 23. Under Assumption 3, for all σ ∈ Σprop and all support-preserving P : Pσ,P [τT > k|S|] ≤ (1 − pT )k

∀k ≥ 0.

Proof. We proceed by induction on k. The base case k = 0 is immediate. For the inductive step, suppose Pσ,P [τT > k|S|] ≤ (1 − pT )k . Conditioned on {τT > k|S|} we have sk|S| ∈ / ST . By the Markov property, the probability of reaching ST within the next |S| steps depends only on the current state sk|S| . By Assumption 3, from any such state the probability of reaching ST within the next |S| steps is at least pT , uniformly over the realised state sk|S| : Pσ,P [τT ≤ (k + 1)|S| | τT > k|S|, sk|S| ] ≥ pT .

Hence,

Pσ,P [τT > (k + 1)|S| | τT > k|S|] ≤ 1 − pT .

Therefore, Pσ,P [τT > (k + 1)|S|] = Pσ,P [τT > (k + 1)|S| | τT > k|S|] · Pσ,P [τT > k|S|] ≤ (1 − pT )k+1 , where the final inequality uses the inductive hypothesis. Under Assumption 3, we have τT < ∞ almost surely under all proper policies and support-preserving kernels, so the reachability reward is finite. Moreover, the assumption provides a uniform lower bound pT > 0 on the probability of reaching ST within |S| steps from any state; this quantity can be computed by solving a reachability RMDP for ST . This induces an effective horizon. Effective horizon.

Define the effective horizon as Heff := sup sup

σ∈Σprop P : Supp(P )=Supp(P ⋆ )

Eσ,P [τT ].

The following result shows that Heff is finite and admits the bound Heff ≤ |S|/pT . Lemma 24 (Effective horizon). |S| Heff ≤ < ∞. pT Proof. For any σ ∈ Σprop and support-preserving P , Eσ,P [τT ] =

∞ X

Pσ,P [τT > n] =

n=0

≤

k=0 j=0 ∞ X k=0

Pσ,P [τT > k|S| + j]

k=0 j=0

∞ |S|−1 X X

≤ |S|

∞ |S|−1 X X

Pσ,P [τT > k|S|] ≤ |S|

(1 − pT )k =

∞ X

Pσ,P [τT > k|S|]

k=0

|S| , pT

where the last inequality follows from Proposition 23. Hence, Heff can be conservatively bounded by |S|/pT when unknown. In the following, we extend the sensitivity lemma (Lemma 2) to the infinite-horizon setting by replacing H with Heff , which induces only a constant-factor change in ∆t . We first prove the stopped analogue of Proposition 11 from the finite-horizon setting (App. C), following the same proof structure. 27

Proposition 25 (Stopped one-step error propagation). Let µh , µ bh denote the stopped marginals at time-step h under P and Pb respectively, following a proper profile σ from initial state s0 ∈ S: µh (s) := Pσ,P [sh = s, h < τT ],

µ bh (s) := Pσ,P [sh = s, h < τT ]. b

Define 1

∆L t := Then for all h ≥ 1,

max ∥Psa − Pbsa ∥1 .

(s,a)∈Xnt

1

∥µh − µ bh ∥1 ≤ h ∆L t .

Proof. We prove the recursive bound 1

∥µh+1 − µ bh+1 ∥1 ≤ ∥µh − µ bh ∥1 + ∆L t , from which the result follows by induction using µ0 = µ b0 = δs0 . Define the stopped one-step kernels, for s ∈ / ST , X Ks := 1[· ∈ / ST ] σ(a|s)P (·|s, a),

b s := 1[· ∈ K / ST ]

a

These are substochastic, i.e.,

′ s′ Ks (s ) ≤ 1.

µh+1 =

X

so µh+1 − µ bh+1 =

µ bh+1 =

X

s

s

X

(µh (s) − µ bh (s))Ks +

X

s

µh (s)Ks ,

Taking L1 norms and applying the triangle inequality: X ∥µh+1 − µ bh+1 ∥1 ≤ (µh − µ bh )Ks s

Substochasticity implies X (µh − µ bh )Ks

1

s

Second term.

By convexity, X s

For each s ∈ / ST ,

σ(a|s)Pb(·|s, a).

a

P

Then

First term.

X

bs) µ bh (s)(Ks − K

b s ∥1 ≤ ∥Ks − K

X a

1

1

s

b s ). µ bh (s)(Ks − K

X

+

s

bs, µ bh (s)K

bs) µ bh (s)(Ks − K

1

.

≤ ∥µh − µ bh ∥1 .

b s ∥1 . ≤ max ∥Ks − K s∈S / T

1

σ(a|s)∥Psa − Pbsa ∥1 ≤ ∆L t .

Substituting gives 1

∥µh+1 − µ bh+1 ∥1 ≤ ∥µh − µ bh ∥1 + ∆L t . Unrolling yields 1

∥µh − µ bh ∥1 ≤ h ∆L t . We now lift Proposition 25 to derive the infinite-horizon counterpart of the sensitivity lemma (Lemma 2). 28

Lemma 26 (Infinite-horizon sensitivity). Under Assumption 3, define   1 |S| 2 ∆t := Rmax Heff ∆L , H := . eff t pT Then for any P ∈ Pt , profile σ ∈ Σprop , player i ∈ N and state s0 ∈ S, |ui (σ, P | s0 ) − ui (σ, Pb | s0 )| ≤ ∆t . Proof. Let VP (s) := ui (σ, P | s) and Vb (s) := ui (σ, Pb | s), with VP (s) = Vb (s) = 0 for s ∈ ST . For s ∈ / ST , let X X σ(a | s)Pb(· | s, a). Psσ := σ(a | s)P (· | s, a), Pbsσ := a

a

Then

VP (s) = riσ (s) +

X

Psσ (s′ )VP (s′ ),

s′

and analogously for Vb . Since |τT | has expectation at most Heff under Assumption 3, ∥VP ∥∞ , ∥Vb ∥∞ ≤ Rmax Heff . Moreover, for every s ∈ / ST , ∥Psσ − Pbsσ ∥1 ≤ Hence, for s ∈ / ST ,

X a

1 σ(a | s)∥Psa − Pbsa ∥1 ≤ ∆L t .

1

|VP (s) − Vb (s)| ≤ Rmax Heff ∆L t +

X s′

Psσ (s′ )|VP (s′ ) − Vb (s′ )|.

Unrolling this inequality until τT gives 1

1

σ,P 2 L |VP (s0 ) − Vb (s0 )| ≤ Rmax Heff ∆L t Es0 [τT ] ≤ Rmax Heff ∆t = ∆t .

Lemma 26 recovers Lemma 2 (up to constant factors) with the substitution H ← Heff . All intermediate results in the finite-horizon case carry over with H ← Heff and nmin as stated in Theorem 27 below. Theorem 27 (PAC guarantee for infinite-horizon objectives). Alg. 1 with s & !'  2  2 δ cont Rmax |S|5 64Rmax |S|4 ε2 p4T e nmin = − =O W−1 − 2 ε2 p4T 64Rmax |S|4 2(2|S| − 2)|S||A| ε2 p4T satisfies the PAC-CSG guarantee of Definition 4 under the unbounded probabilistic reachability and reachability reward objectives, with sample complexity  2  6 e Rmax |S| |A| . T⋆ = O ε2 p4T preach

I

Extension: Learning zero-sum CSGs

We now specialise the framework to two-player zero-sum CSGs. Since the players have directly opposing objectives, i.e., X1 = −X2 , we write X := X1 , so that X2 = −X. Accordingly, we consider a single utility and reward function, writing u := u1 = −u2 and r := r1 = −r2 . In a zero-sum CSG G, the (minimax) value of G with respect to X is defined whenever the game is determined, i.e., when sup

inf u(σ1 , σ2 ) = inf

σ1 ∈Σ1 σ2 ∈Σ2

sup u(σ1 , σ2 ).

σ2 ∈Σ2 σ1 ∈Σ1

29

In this case, the value is unique, and the corresponding optimal strategies form the set of Nash equilibria of G [45].

Extending to robust CSGs, let G be an RCSG with uncertainty set P. We say the game is robustly determined if determinacy holds under worst-case transition uncertainty, i.e., with respect to uP (σ) = inf P ∈P u(σ, P ). The resulting robust value of G is V := sup inf inf u(σ, P ), σ1

σ2 P ∈P

which coincides with the value of the induced CSG under an adversarial kernel (cf. [18, Definition 6]). The corresponding robust optimal strategies guarantee a value of at least V for all P ∈ P. For our objectives of interest, zero-sum CSGs are always determined in the finite-horizon setting, and optimal strategies exist due to the finite game tree. In contrast, in the infinite-horizon setting, a value exists (e.g., in the limit-sure sense for reachability objectives), but optimal strategies need not exist [13]. Simplifications relative to the general-sum case. Since only a single utility function u is involved, the sensitivity (Lemma 2) and per-episode value gap (Corollary 5) from the general-sum case apply without the factor-of-2 loss incurred when summing over players. Consequently, the stopping threshold on ∆t improves from ε/4 to ε/2 (line 9 in Alg. 1), and the constant in nmin improves accordingly: s & !'   2 2 ε2 4Rmax H4 δ cont Rmax H 4 |S| e W−1 − 2 . nmin = − =O ε2 4Rmax H 4 2(2|S| − 2)|S||A| ε2 All other bounds remain unchanged. Moreover, the RCSG solver S OLVEL1CSG reduces to a minimax L1 -CSG solver, which is equivalent to solving an RMDP and admits a polynomial-time solution [35, 37, 43, 48].

J

Helper functions for Algorithm 1

The helper routines, Algs. 2 to 4, are called by Alg. 1 but omitted from the main paper for brevity. Note that in Alg. 2, preach is computed by solving a reachability problem on an RMDP with the same support as P ⋆ , full-simplex transition uncertainty over that support, and ST as the terminal set; this does not require knowing the transition probabilities. In implementation, we instantiate the support-preserving simplex with a 10−5 lower bound on probabilities within the support, which ensures graph preservation and yields a strictly positive preach consistent with Assumption 1. Algorithm 2 Initialise Input: S, A, Γ, Rmax , H, Supp(P ⋆ ) 1: preach ← min(s,a)∈Xnt maxσ∈Σ inf P ∈PSupp Pσ,P [reach (s, a) before entering ST ] ▷ Eq. (2) 2: for (s, a) ∈ Xnt do 3: N (s, a) ← 0, N (s, a, s′ ) ← 0 ∀s′ 4: K(s, a) ← f alse 5: Pb(· | s, a) ← Uniform 6: end for l p  m 2 7: c ← −16Rmax H 4 /ε2 ; nmin ← c · W−1 δ cont /(2(2|S| − 2)|S||A|) c ▷ by Cor. 21 b, preach 8: return N, K, P

K

Additional experimental details

K.1

Exploration Baselines

We give precise definitions of the four exploration strategies compared in RQ2 (Table 2). In each case, the resulting sampling policy replaces σte in Alg. 1; only the choice of exploration policy differs, with the PAC loop, stopping condition ∆t ≤ ε/4, and all other components held fixed. 30

Algorithm 3 Construct uncertain transition set P(s, a)

Input: N, δ cont , S, A, Γ, Supp(P ⋆ ) 1: for (s, a) ∈ Xnt do 2: if N (s, a) = 0 then 3: Pbsa ← Uniform(Succ(s, a)) 4: P(s, a) ← ∆+ (Succ(s, a)) 5: else 6: Pbsa (s′ ) ← N (s, a, s′ )/N (s, a) ∀s′ ∈ Succ(s, a) cont cont 7: δsa ← p δ / [|S||A| · N (s, a)(N (s, a) + 1)] cont ] 8: α ← (2/N (s, a)) ln [(2|S| − 2)/δsa  9: P(s, a) ← p ∈ ∆+ (Succ(s, a)) : ∥p − Pbsa ∥1 ≤ α 10: end if 11: end for 12: return P

▷ by Lem. 9

Algorithm 4 Update Input: N, K, π = (π1 , . . . , πN π ), nmin , S, A, Γ 1: for (s, a) ∈ Xnt do 2: for i ← 1 to N π do 3: N (s, a) ← N (s, a) + #(s, a) in πi 4: for s′ ∈ S do 5: N (s, a, s′ ) ← N (s, a, s′ ) + #(s, a, s′ ) in πi 6: end for 7: end for 8: K(s, a) ← (N (s, a) ≥ nmin ) 9: end for 10: return N, K (i) Robust (ours). Solves the exploration RMDP Gte (Definition 5) pessimistically, i.e., σte ∈ e arg maxσ∈Σ inf P ∈Pte Eσ ,P [·], maximising worst-case reachability of unknown (s, a)-pairs over the current uncertainty set (see Eq. (1)). This is the exploration rule used by Alg. 1 and underlies our sample-complexity guarantee (Theorem 7). (ii) Optimistic. Solves the same exploration RMDP Gte , but with the inner minimisation e over Pte replaced by a maximisation, i.e. σte ∈ arg maxσ∈Σ supP ∈Pte Eσ ,P [·], targeting best-case rather than worst-case reachability. This corresponds to the optimism-in-theface-of-uncertainty principle common in PAC-MDP exploration, but is not covered by our analysis (Sec. 4.2): an optimistic σte need not lower-bound the true visitation probability under P ⋆ , so the coverage guarantee of Lemma 6 need not hold. (iii) Round-robin. Maintains a single target slot: the unknown (s, a)-pair with the fewest samples so far, ties broken by index. Rather than solving the exploration RMDP, it computes a policy on the point-estimate MDP Pbt (i.e., the empirical kernel treated as exact, with zero confidence radius) that maximises the probability of reaching the target slot within the horizon, and re-solves only when the target slot changes (i.e., becomes known). (iv) Uniform-random. No exploration policy is solved; at each state, each player samples independently and uniformly at random from their available actions. All four share the same per-episode sample count Ntπ (Proposition 17) and stopping condition; only the trajectories collected within each episode differ. K.2

Learning Dynamics

We complement the main experimental evaluation (Sec. 5) with a finer-grained analysis of the learning dynamics induced by our exploration procedure. We ask: how closely does the model-error proxy ∆t reflect actual model and decision quality during learning, and how does the uncertainty and sampling effort evolve over episodes? 31

[a, b], [b, b]

r1 = 1

s0 0.9 [a, a] [b, a]

r1 = 1

others = [c, d], [d, c], [d, d]

s1

[b, a]

[b, b]

[a, a]

[a, b]

[c, c]

s0 0.9

others

0.1

[c, c]

s4

s3

[a, b], [b, a]

s2

0.9

0.9

s2

[hide, throw]

s0

0.1

0.1

s1

[run, wait] [hide, wait]

0.8

others

[b, b]

s1

r2 = 1

s2

others

0.1

s3

[c, c]

(a) Cyclic Preferences

[run, throw]

s3

r1 =1, r2 =0.8

0.2

(b) Delayed Coordination

(c) Hide-or-run

r=1

[push, wait]

s0

s1

s0

[push, push] 0.5

[a, b]

[wait,wait],[wait,go], [go,wait]

0.5 [go, go] [b, a]

0.5

if i < 4

si∈[3]

s1

0.6

[b, b]

[wait, wait] [wait, push]

r=1

0.9

[a, a]

0.7

si+1

0.5 0.1

0.4

0.3

if i+1 = 4

0.5

s3

s2

0.5

s2

s5

s3

s4

r = 0.6

(d) Mixed NE

(e) Safe vs. Risky

(f) Traffic Merge

Figure 2: Six benchmark CSGs (s̄ = s0 ) illustrating distinct challenges for robust PAC learning, including coordination, mixed-strategy equilibria, equilibrium non-existence, and sparse-reward exploration (see Sec. 5). Green states denote target states of the players, while red states denote absorbing trap states.

101

0

10

10−1

Coverage / radius ratio

Error / value gap (log scale)

1.0 ∆t V ⋆ − u(σ̂t , P ⋆ ) final: gap = 0

30

0.8

25 0.6

Ntπ 20

0.4

15 10

0.2 κt αtavg /αtmax 0.0

0.0

0.2

0.4

0.6

0.8

1.0

1.2

t 1 (a) ∆t and true value gap

1.4 ×106

0.0

0.2

0.4

0.6

0.8

1.0

t

(b) κt and 1radius ratio

1.2

1.4 ×106

5 0.0

0.5

1.0

t

×106

(c) Samples1 per episode

Figure 3: Learning dynamics over episodes in a representative run of the Delayed Coordination game
for ⟨⟨p1 : p2 ⟩⟩max=? P[F s3 ] + P[F s3 ] : (a) evolution of ∆t and the true value gap V ⋆ − u(σ̂t , P ⋆ ), with σ̂t re-computed every 200 episodes and the final value gap at termination marked by a star; (b) evolution of κt and the average-to-maximum confidence-radius ratio; and (c) number of sampled trajectories per episode.

⋆ We measure: (i) the model error proxy ∆t := 12 H 2 max(s,a)∈Xnt ∥Pbt,sa − Psa ∥1 (Rmax = 1); (ii) the fraction κt := |Kt |/|U1 | of known (s, a) pairs by episode t; and (iii) the true value gap V ⋆ −u(σ̂t , P ⋆ ), where σ̂t is obtained by periodically solving the empirical game every 200 episodes. Together, these quantities allow us to assess how conservative the sufficient stopping condition ∆t ≤ ε/4 is in practice. We illustrate these dynamics on a representative run of the sparse-reward exploration benchmark, Delayed Coordination, for the infinite-horizon property ⟨⟨p1 : p2 ⟩⟩max=? (P[F s3 ] + P[F s3 ]): the evolution of ∆t and the true value gap is shown in Fig. 3a, the evolution of κt alongside the

32

distribution of confidence radii in Fig. 3b, and the number of sampled trajectories per episode in Fig. 3c. Fig. 3a shows that convergence is not smooth or gradual, especially for the model error ∆t and the true value gap V ⋆ − u(σ̂t , P ⋆ ). Rather than decreasing smoothly, ∆t stays pinned at its worst-case value while a single hard-to-reach (s, a)-pair remains almost entirely unsampled. Since ∆t is governed by the largest per-slot confidence radius rather than the average (Lemma 2), it drops sharply once that slot accumulates enough samples, then follows a staircase pattern as the remaining slots are resolved. Convergence of the extracted strategy is similarly abrupt: σ̂t achieves value 0 (versus the true value V ⋆ = 2) for roughly the first third of training, then rises to and remains at exactly 1 — the value attained by the non-robust point-estimate strategy on most seeds — until the last periodic checkpoint (200 iterations) before ∆t crosses ε/4. Only in the final handful of episodes does σ̂t resolve to the fully cooperative equilibrium, which Delayed Coordination requires at every one of the three consecutive states (s0 , s1 , s2 ) to reach the goal s3 at all (see Fig. 2b). Note that this does not violate Corollary 5’s guarantee V ⋆ − u(σ̂t , P ⋆ ) ≤ 4∆t : the bound requires µ⋆ ≥ 4∆t − ε, and here µ⋆ = 0, since all four joint actions at the indifferent state s4 induce the same transition distribution, so deviating there costs either player nothing and attains the infimum in Definition 3 at 0. Thus, the precondition reduces exactly to ∆t ≤ ε/4, the algorithm’s own stopping condition, so the bound is not expected to hold before the run actually stops, i.e., the regime shown here. Fig. 3b shows that κt increases step-wise but much more smoothly than ∆t , with no comparably large jump around episode 700–800K, suggesting that the other (s, a)-pairs become known relatively steadily throughout training. κt stops at 0.95 (19 of the 20 (s, a)-pairs), indicating that termination is governed by the statistical stopping condition ∆t ≤ ε/4, which can occur before full coverage (Corollary 22). In contrast, the average-to-maximum confidence-radius ratio αtavg /αtmax decreases for roughly the first half of training as most slots are resolved while the single hardest-to-reach slot keeps αtmax near its initial value, then rises back towards 1 once that slot is sampled and the remaining radii converge. Together, these trends imply that learning is bottlenecked by a single difficult-to-sample slot: its large confidence radius dominates ∆t , which reflects the worst-case rather than the average uncertainty across (s, a)-pairs (Lemma 2). On the other hand, Fig. 3c shows that the number of trajectories sampled per episode, Ntπ , grows logarithmically with the episode index t, matching the adaptive sampling rule Ntω ∝ log(1/δtcov ) = O(log t) from Proposition 17 and App. F. This reflects the algorithm’s increasingly conservative per-episode coverage requirement. Specifically, as the confidence budget is distributed across an increasing number of episodes, the allowed per-episode failure probability δtcov decreases as δtcov = δ cov /(t(t + 1)) (Proposition 18), so later episodes require more trajectories to maintain their high-probability coverage guarantee, while keeping the total failure probability from coverage at most δ cov . Overall, these results show that learning is primarily bottlenecked by a small number of hard-toexplore (s, a) pairs: ∆t and strategy quality improve only once these pairs receive sufficient samples, even when most pairs are already well resolved. The stopping condition ∆t ≤ ε/4 is therefore conservative in the sense that it is driven by the single worst-case confidence radius rather than decision-relevant uncertainty. To resolve bottlenecks earlier, future improvements could target highimpact, poorly explored regions more directly, e.g., by designing rewards proportional to confidence radii and/or inversely proportional to visitation probabilities.

K.3

Full experimental results

We present the complete set of experimental results in Table 3, in response to RQ1 outlined in Sec. 5 of the main paper.

Licenses for external tools. Our implementation builds on the PRISM-games model checker, which is distributed under the GNU General Public License (GPL), version 2. We adhere to its licensing terms. Additional dependencies and their licenses are documented at [25]. 33

Table 3: Full experimental results (mean ± std over 10 runs). All cases use ε = 0.1, except Delayed Coordination’s unbounded-reachability property, which uses ε = 0.2 to keep runtime within a reasonable budget. For every case with a stationary NE returned by the CSG solver, our algorithm achieves the same true-game value, with differences only on action-indifferent states (only s4 in Delayed Coordination). Hide-or-Run is a limit-equilibrium case in which the optimal value is approached in the limit but is not attained by any stationary profile. For the third Safe vs. Risky property, our learner outputs V̂ = ∞ in all runs. Case study

Property

Cyclic Prefs.

⟨⟨p1 : p2 ⟩⟩max=? (Rr1 [F s3 ] + Rr2 [F s3 ])
⟨⟨p1 : p2 ⟩⟩max=? P[F ≤3 s3 ] + P[F ≤4 s3 ]

Delayed Coord. Hide-or-run Mixed NE Safe vs. Risky

Traffic Merge

L

No. of episodes (×106 )

Total no. of samples (×107 )

V⋆

2.6237 ± 0.0003 2.4997 ± 0.0002

8.3317 ± 0.0010 7.9101 ± 0.0007

– 0.615

⟨⟨p1 : p2 ⟩⟩max=? (P[F s3 ] + P[F s3 ])
⟨⟨p1 : p2 ⟩⟩max=? Rr1 [C≤5 ] + Rr2 [C≤5 ]

1.4098 ± 0.0000 5.5241 ± 0.0000

4.2953 ± 0.0002 18.3638 ± 0.0002

2.000 3.240

⟨⟨p1 : p2 ⟩⟩max=? (P[F s1 ] + P[F s2 ])
⟨⟨p1 : p2 ⟩⟩max=? P[F ≤4 s1 ] + P[F ≤2 s2 ]

1.4136 ± 0.0000 1.4136 ± 0.0000

4.3077 ± 0.0000 4.3077 ± 0.0000

1.000 1.000

⟨⟨p1 : p2 ⟩⟩min=?  (Rt1 [F s4 ] + Rt2 [F s4 ]) ⟨⟨p1 ⟩⟩Pmax=? F ≤5 s4

0.6712 ± 0.0000 0.2171 ± 0.0001

24.3784 ± 0.0003 3.1098 ± 0.0005

8.000 1.000

⟨⟨p1 ⟩⟩Pmax=? [F  s1 ]  ⟨⟨p1 ⟩⟩Pmax=? F ≤5 s1

⟨⟨p1 : p2 ⟩⟩max=? (P[F s1 ] + P[F s2 ])
⟨⟨p1 : p2 ⟩⟩max=? P[F ≤3 s1 ] + P[F ≤3 s2 ] ⟨⟨p1 : p2 ⟩⟩max=? (Rr1 [F s1 ] + Rr2 [F s2 ])

0.4671 ± 0.0000 1.0625 ± 0.0000

0.3321 ± 0.0411 0.1711 ± 0.0066 0.3321 ± 0.0411

1.3216 ± 0.0000 3.1834 ± 0.0000

0.999 0.800

5.8710 ± 0.0007 2.5460 ± 0.0008 5.8710 ± 0.0007

1.000 1.000 ∞

V ⋆ − V̂

– 0.0021 ± 0.0001

0.0000 ± 0.0000 0.0016 ± 0.0001 0.0000 ± 0.0000 0.0000 ± 0.0000 0.0031 ± 0.0000 0.0031 ± 0.0000 0.0017 ± 0.0000 0.0026 ± 0.0000 – 0.0000 ± 0.0000 0.0000 ± 0.0000

Limitations

We first summarise the assumptions that underpin our analyses, all of which are common in the PAC learning and robust stochastic games literature. (A1) Centralised exploration. We assume that the players perform centralised play during exploration. This assumption is standard in PAC analyses of multi-agent systems, including turn-based stochastic games [7, 42] and Markov games [20, 31], where a centralised learner simplifies the exploration problem. However, it does not capture decentralised or competitive settings where agents act independently or have limited information sharing. We remark that the equilibrium-transfer results in Sec. 4.1 would remain applicable if comparable confidence sets could be obtained under decentralised learning, but the joint-coverage and termination analysis in Secs. 4.2 and 4.3 would require a different exploration mechanism. Developing such a mechanism for decentralised settings remains an important open direction. (A2) Reachability. Our guarantees rely on a reachability condition (Assumption 1) ensuring that every relevant (non-target) (s, a)-pair is reachable under some profile with positive probability at least preach . This excludes degenerate cases where reachability probabilities vanish and is analogous to standard communicating or reachability assumptions in PAC-MDP analyses [2, 22], adapted to our robust setting. Without such a condition, PAC termination under online trajectories cannot be guaranteed in general, as illustrated by standard lower-bound constructions (e.g., chain-game instances). Relaxing it typically requires additional capabilities such as access to a generative model or structured exploration mechanisms [24], which allow coverage to be enforced explicitly. For infinite-horizon reachability reward (stochastic shortest path) objectives, we assume almost-sure target reachability (Assumption 3), ensuring τT < ∞ almost surely and that value functions are well-defined and finite [5, 27]. We additionally impose a uniform lower bound pT > 0 on the probability of reaching ST within |S| steps under a proper policy, which yields a geometric tail bound (Proposition 23) and induces a finite effective horizon (Lemma 24). This assumption is consistent with standard reachability and properness conditions in SSP and PAC analyses [2, 7, 22, 24]. In practice, we precompute the set of reachable state–action pairs via standard reachability analysis over the known support graph when solving the game, following established model checking techniques [27]. This allows us to restrict attention to (s, a)-pairs that are reachable under some profile, eliminating vacuous cases where exploration or reaching is impossible. Both probability lower bounds, preach and pT , can be computed (or conservatively approximated) by solving associated reachability RMDPs over the known support graph. 34

(A3) Graph preservation. We assume the standard graph preservation condition, whereby all transition kernels in the uncertainty set share the same support. This assumption is common in robust MDP and RCSG formulations [18, 21, 34, 35, 43], and is necessary for tractable robust dynamic programming. However, it excludes settings with support mismatch (e.g., rare or unseen transitions), which may arise in practice when data is sparse. (A4) Bounded rewards. We assume that the magnitude of rewards is bounded by a known constant Rmax , which is standard in PAC analyses of reinforcement learning [7, 42]. This assumption ensures well-defined concentration bounds and finite value estimates. In practice, this can typically be satisfied via normalisation. L.1

Intrinsic limitations

Beyond these assumptions, several intrinsic limitations arise from the problem setting. Computational complexity. Our approach depends on a black-box RCSG solver, instantiated in practice via PRISM-games [18]. The complexity of solving general-sum CSGs is well known to be high: for nonzero-sum reachability objectives, computing subgame-perfect Nash equilibria is PSPACE-complete [8], and practical solvers such as [18] can require exponential time in the model size. These complexity results reflect fundamental barriers in equilibrium computation rather than artefacts of our learning framework. Nevertheless, implementation-level optimisations (e.g., parallelised sampling) and increased computational resources can partially mitigate these costs in practice. Sample complexity dependence. The sample complexity scales polynomially with problem parameters, with a leading H 4 dependence arising from compounding transition uncertainty over trajectories. It may be possible to improve this dependence to H 3 using empirical-Bernstein or stagewise concentration techniques [15], but such approaches typically require stronger assumptions, such as finer control over variance across timesteps (e.g., martingale-style concentration over trajectories or stage-dependent confidence bounds that exploit variance information at each timestep), and lead to a more technically involved analysis. Non-existence detection. While our framework supports both equilibrium computation and nonexistence detection, the non-existence certificate is sound but not complete: when no exact NE exists, the algorithm may still return an ε-NE rather than certifying non-existence. This limitation is inherent to the problem: while ε-NE exist for any ε > 0, this implies that approximate equilibria persist arbitrarily close to the boundary of equilibrium existence, making it fundamentally difficult to distinguish exact equilibrium existence from arbitrarily small Nash margins [6]. Other extensions. Natural extensions include handling more than two players and non-stationary environments. Both introduce additional challenges: the former increases equilibrium complexity and joint-action scaling, while the latter requires adapting to evolving transition kernels and equilibrium structure over time.

M

Broader Impacts

This work contributes to the theoretical foundations of learning in multi-agent stochastic systems under uncertainty. Potential positive impacts include improving the robustness and reliability of autonomous systems, such as multi-robot coordination, distributed control, and decision-making in uncertain environments. At the same time, advances in multi-agent learning and equilibrium computation may have unintended applications in competitive or adversarial settings, such as automated negotiation, financial markets, or strategic resource allocation, where robustness could be exploited to gain advantage. While our work is primarily theoretical and does not target specific deployments, we encourage careful consideration of such downstream uses.

35

Related documents

• Governed Human-AI Prioritization Under Uncertainty: Adaptive Estimation and Dependency-Constrained Portfolio Selection#673592
• Digital Decodings: Learning in a Freirean Gaming Circle#352296
• Engineering Efficient Self-Play Chess: Search, Replay, and Throughput Under Limited Compute#1141769
• Guessing a random function and repeated games in continuous time#665098
• Learnable Representations of Geometry#15529