arXiv CSopen access

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives: A Decentralized Private Approach via Expected Conditional Distance Ali Asadi # Institute of Science and Technology Austria (ISTA), Austria

Krishnendu Chatterjee # Institute of Science and Technology Austria (ISTA), Austria

Pavol Kebis # Institute of Science and Technology Austria (ISTA), Austria

arXiv:2607.14877v1 [cs.LG] 16 Jul 2026

Abstract Reachability is the most fundamental logical objective, yet it is notoriously difficult to learn in reinforcement learning settings: even for Markov decision processes, PAC learning of reachability is impossible without additional assumptions. This difficulty also holds in turn-based stochastic games (TBSGs), where two adversarial players interact on a finite state space. In this work, we consider turn-based stochastic games with reachability objectives. For such settings, adversarial learning, in which players are adversarial even in the learning phase, is impossible. Therefore, the goal is to consider learning, in which both players learn the unknown model together. In this spirit, previous literature on PAC learning in TBSGs considers (a) public information shared by both players; and (b) centralized learning, which means that players share the same learning algorithm. In this work, our contribution is two-fold. First, we relax these strong assumptions and ensure learning: (i) with private information not shared with the other player; and (ii) decentralized learning where the players do not share the same learning algorithm. To the best of our knowledge, this work is the first positive result for decentralized and private information learning of TBSGs with reachability objectives. Second, we introduce a game-theoretic generalization of the Expected Conditional Distance (ECD) parameter, which measures the expected length of reaching the target set. We establish a polynomial-sample complexity bound with respect to the number of states, actions, ECD parameter, and inverses of error tolerance and failure probability. 2012 ACM Subject Classification Theory of computation → Logic and verification Keywords and phrases formal methods, games and logic, logical aspects of AI, model checking Digital Object Identifier 10.4230/LIPIcs.CONCUR.2026.3 Funding The research was partially supported by Austrian Science Fund (FWF) 10.55776/COE12, ERC CoG 863818 (ForM-SMArt), FWF-2022-SFB F8502 (SPyCoDe), and ERC-2020-AdG 101020093 (VAMOS) grants.

1

Introduction

Turn-Based Stochastic Games. Turn-based stochastic games (TBSGs) [7] are zero-sum turn-based games played over a finite state space by two adversarial players, Max and Min, along with randomness in the transition function. The state space is partitioned into two disjoint sets for Max and Min. At each time step, the player owning the current state chooses an action. The subsequent state is then determined by a probabilistic transition function. This model generalizes several classical formalisms such as Markov decision processes (MDP) [19], which have only one player and stochastic uncertainty, and graph games [6, 11], where the transition function collapses to Dirac distributions. © CC-BY; licensed under Creative Commons License CC-BY 4.0 37th International Conference on Concurrency Theory (CONCUR 2026). Editors: Ana Sokolova and Patrick Totzke; Article No. 3; pp. 3:1–3:24 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

3:2

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives

Objectives. In TBSGs, the interaction of players is guided by an objective function, which formally captures the desired behaviour of the model. Objectives are typically categorized into: (a) logical objectives, e.g., reachability, safety, and parity; and (b) quantitative objectives, e.g., finite-horizon, discounted sum, and mean payoff. This work focuses on reachability objectives, which are the most fundamental logical objectives, i.e., given a set of target states, the objective requires that some target state is eventually visited. It is important to distinguish reachability from discounted sum or finite-horizon objectives. Discounted sum objectives introduce a discount factor λ < 1, which effectively imposes a "soft" horizon. Finite-horizon objectives strictly bound the interaction to L steps. In contrast, reachability is an unbounded property; a target might be reached after an arbitrarily large number of steps. Strategies and Values. Strategies are recipes that define the choice of actions of the players. They are functions that, given a game history, return a distribution over actions. Given a TBSG and an objective, the value of player Max at a state is the maximal expectation that the player can guarantee for the objective against all strategies of player Min. A strategy is ε-optimal if it guarantees the value up to additive error ε. PAC Learning. While classical model checking assumes a known model, in the reinforcement learning setting the model is unknown. The players must learn near-optimal strategies solely through interaction with a simulator. In this setting, the gold standard is Probably Approximately Correct (PAC) guarantees for learning near-optimal strategies [21]. The PAC-RL problem is defined as follows. Can we design learning algorithms for both players such that for any error tolerance ϵ > 0 and failure probability p ∈ (0, 1), the algorithms output strategies that are ϵ-optimal with probability at least 1 − p? Crucially, for the problem to be considered tractable, the number of samples required by the algorithm (called sample complexity) must be polynomial in number of states and actions, inverse error tolerance 1/ϵ and inverse failure probability 1/p. Expected Conditional Distance. Even in MDPs, the PAC-RL problem for reachability objectives is impossible in general [1, 23]. Thus, to circumvent this impossibility the literature considers further assumptions including prior knowledge on (a) the topology of the underlying graph [10]; (b) the minimum non-zero probability [2]; and (c) a parameter called the Expected Conditional Distance (ECD), which was introduced in [20] for MDPs. The ECD parameter provides a measure of the expected number of steps to reach the target. We generalize ECD to the TBSG setting. This generalization is quite subtle, as several natural generalizations of ECD to games fail to achieve PAC guarantees. Intuitively, if a game has a small ECD, it implies that if the target is reachable, it is reachable relatively quickly on average. This assumption excludes pathological games where the only optimal strategies involve waiting for exponentially many steps. Bounding the ECD allows us to truncate the infinite-horizon, converting the intractable reachability problem into a tractable finite-horizon approximation. Tractable Private and Decentralized Learning. Adversarial learning, in which players are adversarial even in the learning phase, is impossible for TBSGs with reachability objectives: consider a game with an initial player-Min state and an additional action that immediately leads to the target. In the learning phase, Min chooses the trivial target-reaching action, which is never part of the optimal strategy, rendering learning useless. Since adversarial learning with PAC guarantees is impossible, the goal is to consider learning where both players learn the unknown model together. In this setting, [2] established an anytime algorithm with the prior knowledge on (a) the minimum non-zero transition probability; or (b) the topology

A. Asadi, K. Chatterjee, P. Kebis

3:3

of the underlying graph. However, this prior work [2] has two important limitations: First, it assumes (i) public information shared by both players; and (ii) centralized learning where players share the same learning algorithm. Second, while the algorithm is anytime, it does not provide sample-complexity bounds for the PAC-RL problem. Motivation. The motivation of this work is two-fold. The main motivation is to relax the above two strong assumption and ensure learning: (i) with private information not shared with the other player; and (ii) decentralized learning where the players do not share the same learning algorithm. Second, even in previous setting of centralized learning with public information, sample complexity bound was not established. The goal is to establish a polynomial-sample complexity bound with respect to the number of states, actions, ECD parameter, and inverses of error tolerance and failure probability. Our Contributions. We address the above gaps by considering the decentralized private information setting of TBSGs with reachability objectives. We present a pair of algorithms for both players which are PAC-RL learnable with prior knowledge on the ECD parameter. The sample complexity of these algorithms is polynomial in the game parameters, the inverses of the error tolerance and failure probability, and the ECD parameter. To the best of our knowledge, this pair of algorithms is the first positive result for decentralized private information PAC-RL learning in TBSGs with reachability objectives. Technical Contributions. Our technical contributions are as follows. We generalize the Expected Conditional Distance (ECD) parameter to the TBSG setting. We provide a reduction showing that, if the ECD of a game is small, we can approximate the reachability value using a finite-horizon reachability objective. We define a finite-horizon expanded game over state-step pairs that unfolds the horizon into the state space, enabling backward induction and local learning at each state-step. We present a learning procedure where both players use backward induction to learn local ϵ-optimal actions one step at a time. The algorithm uses a best-arm identification routine at each state-step to identify ϵ-optimal actions with high confidence. The algorithm iteratively constructs a set of strategies in stages. Each newly constructed strategy is added to the set used in subsequent stages to ensure that previously discovered state-steps of the game remain reachable while the players explore new state-steps. To explore new state-steps, we maintain a set of unexplored ones. These are treated as auxiliary target sets, incentivising the players to visit more of the state-step space. Proofs omitted due to space restrictions are provided in the Appendix. Technical Novelty. The technical novelty of this work is two-fold. The first novelty is the appropriate definition of ECD for games. Second, the previous works rely on estimating the underlying probabilistic transitions, which is infeasible in private decentralized learning. Our approach carefully combines different techniques: best arm identification; tracking strategies for exploration; and backward induction to directly compute near-optimal strategies. Related Works. The intersection of formal verification and reinforcement learning has recently received significant attention. We summarize some related works as follows. MDPs. PAC guarantees for complex logical objectives, such as Linear Temporal Logic (LTL) [18], has seen significant development but remains constrained by specific environmental assumptions, due to the inherent impossibility of learnability in general settings without additional assumptions [1, 23]. Early PAC learning algorithm presented in [10] required complete knowledge of the environment’s topology. [2] improved upon this by requiring only a lower bound on the minimum non-zero transition probability. More recently, [17] has established PAC results using the mixing time of the environment. [20] has introduced the ECD parameter and established PAC results relying on this parameter.

CONCUR 2026

3:4

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives

TBSGs. Early works on learning in TBSGs focused mainly on quantitative objectives and did not provide PAC guarantees [14, 15, 5]. For logical objectives, [22] has established PAC learning algorithms for TBSGs with LTL objectives by combining the special case of almost-sure satisfaction of a specification with optimizing quantitative objectives. [2] obtained PAC guarantees for reachability objectives by computing under- and overapproximation of values, originally introduced in [13]. It is noteworthy that all these works consider the centralized public information setting.

2

Preliminaries

In this section, we define the notations of turn-based stochastic games and PAC learning. Notation. For a positive integer n, the set {0, 1, 2, . . . , n} is denoted by [n]. Open and closed intervals of reals are denoted (x, y) = {a ∈ R | x < a < y} and [x, y] = {a ∈ R | x ≤ a ≤ y}, respectively. Sets are denoted by calligraphic letters, e.g., S, A. Elements of sets are denoted by lowercase letters, e.g., s, a. The set of probability distributions over a set S is denoted by ∆(S). The set of natural numbers is N = {0, 1, 2, . . .}.

2.1

Turn-Based Stochastic Games

▶ Definition 1 (Turn-Based Stochastic Games). A turn-based stochastic game (TBSG for short) is a tuple G = (S, A, δ, µ) where S = SMax ⊎ SMin is a finite set of states, partitioned into the set of player-Max states SMax and the set of player-Min states SMin ; A is a finite set of actions; δ : S × A → ∆(S) is a probabilistic transition function which, given a state and an action, assigns a probability distribution over the successor state; and µ ∈ ∆(S) is a probability distribution over the initial state. Dynamic. At the beginning, an initial state s0 ∼ µ is drawn, and the game proceeds as follows. In each step ℓ ∈ N, the owner of the state sℓ selects an action aℓ ∈ A, possibly at random, and the successor state sℓ+1 ∼ δ(sℓ , aℓ ) is drawn. Histories and Plays. A history is a finite sequence h = (s0 , a0 , s1 , a1 , . . . , sL ) of states and actions such that for all ℓ ∈ [L − 1], we have δ(sℓ , aℓ )(sℓ+1 ) > 0. A play is an infinite sequence of states and actions ω = (s0 , a0 , s1 , a1 , . . .) such that, for all ℓ ∈ N, we have δ(sℓ , aℓ )(sℓ+1 ) > 0. The set of all plays is denoted by Ω. Strategies. A strategy determines how a player chooses an action based on the history up to a given step. Formally, a strategy for a player i ∈ {Max, Min} is a function πi : (S ×A)⋆ ×Si → ∆(A). The set of all strategies is denoted by Πi . A strategy is Markovian if it depends on the current state and current step of the play, i.e., πi : Si × N → ∆(A). A strategy is pure if it prescribes deterministic actions, i.e., it corresponds to a function πi : (S × A)⋆ × Si → A. A strategy is memoryless if it decides only based on the current state, i.e., πi : Si → ∆(A). A strategy is positional if it is pure and memoryless. Note that in TBSGs with reachability objectives positional strategies are as powerful as general strategies [7]. Given strategies for both players πMax and πMin , we denote the strategy profile by (πMax , πMin ), and if the context is clear, we simply use π. Probability Measures. For a history h, its cone is the set of plays where h is their prefix. Given a strategy profile π and an initial belief µ, the unique probability measure over Borel sets of infinite plays is denoted by Pπµ (·), which is defined by Carathéodory’s extension theorem by extending the natural definition over cones of plays [4]. Reachability Objectives. An objective in a TBSG is a Borel set of plays Φ ⊆ Ω in the

A. Asadi, K. Chatterjee, P. Kebis

3:5

Cantor topology on Ω [12]. In this work, we consider reachability objectives which lie in the first level of the Borel hierarchy. Given a set of target states T , the reachability objective requires that a target state is eventually visited, i.e., Reach(T ) := {ω ∈ Ω : ∃ℓ ∈ N sℓ ∈ T }. The goal of player Max is to maximize the probability of satisfying the objective, while the goal of player Min is to minimize it. We now recall a fundamental determinacy for TBSGs with reachability objectives. ▶ Theorem 2 (Determinacy [7]). For all TBSGs with a target set T ⊆ S, we have sup

inf

πMax ∈ΠMax πMin ∈ΠMin

Pπµ (ω ∈ Reach(T )) =

inf

sup

πMin ∈ΠMin πMax ∈ΠMax

Pπµ (ω ∈ Reach(T )) .

Values. Theorem 2 implies that switching the quantifiers does not make a difference and leads to a unique notion of value. Formally, given a target set T , the value is a function of initial distribution ValG R(T ) (µ) :=

sup

inf

πMax ∈ΠMax πMin ∈ΠMin

Pπµ (ω ∈ Reach(T )).

We omit writing G when clear from the context. Approximately Optimal Strategies. Given ε ≥ 0, a strategy πMax for player Max is ε-optimal if it guarantees the value up to an additive error ε, i.e., if inf πMin ∈ΠMin Pπµ (ω ∈ Reach(T )) ≥ ValR(T ) (µ) − ε. We denote the set of ε-optimal strategies by ΠεMax . In particular, we call a 0-optimal strategy simply optimal. The definition of ε-optimal strategies for player Min is analogous. Best-responses. For a player-Min strategy πMin , we define the set of best-responses for player Max as n Max ,πMin ) BR(πMin ) := πMax ∈ ΠMax : P(π (ω ∈ Reach(T )) = µ o (π ′ ,π ) sup Pµ Max Min (ω ∈ Reach(T )) . ′ πMax ∈ΠMax

The set of best-responses for player Min is defined analogously.

2.2

Reinforcement Learning for TBSGs

In the reinforcement learning setting for TBSGs with reachability objectives, we consider a scenario where the players have no information about the transition probabilities δ or the initial distribution µ; only the parameters S and A are known to both players, and the players access the TBSG only through a simulator M. The goal of both players is to use learning algorithms to find a near-optimal strategy profile. In this work, the learning algorithms are decoupled, i.e., each player has its own learning algorithm that does not communicate with the other player’s algorithm. The assumption of private states is another difference that distinguishes our setting from previously considered settings on TBSGs. We assume that the current state of a play is announced only to its owner and not to the other player. In the rest, we formalize the notion of simulators, learning algorithms, and PAC-RL in this setting. ▶ Definition 3 (Simulators). Given a TBSG G = (S, A, δ, µ) with a target set T ⊆ S, a simulator M stores the current state of the game, receives inputs from both players, performs actions, and outputs to players the new state to which the play is proceeded. Precisely, it works as follows:

CONCUR 2026

3:6

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives

1. Any player i can propose to terminate the simulator with a strategy πi by calling the procedure M.propose(πi ). The simulator terminates with a strategy profile π only if both players propose. 2. M informs both players that a new play has started; 3. M samples the initial state s ∼ µ; 4. M repeats the following: a. the active player i is Max if s ∈ SMax or Min if s ∈ SMin ; b. if s ∈ T , both players are informed that the target was reached and the simulator returns to step 1; c. both players are informed who the active player is but only the active player has access to the current state s; d. active player i either (I) chooses an action a ∈ A by calling the procedure M.step(a); or (II) resets the game by calling the procedure M.reset(). Note that a is announced only to the simulator and not the other player. The play proceeds with transitioning to a new state s′ ∼ δ(s, a) and returning to step 4. ▶ Definition 4 (Learning Algorithms). A learning algorithm Ai for a player i ∈ {Max, Min} is an algorithm that interacts with the simulator M by calling the procedures M.step(a), M.reset(), and M.propose(πi ) where a ∈ A, and πi is a player-i strategy. A learning algorithm is decoupled if it does not communicate with the other player’s learning algorithm. ▶ Definition 5 (PAC-RL). A pair of learning algorithms (AMax , AMin ) is PAC-RL for reachability objectives if there exists a function f such that for all ε, p ∈ (0, 1) and all TBSGs G = (S, A, δ, µ) with a target set T , taking N = f (|S|, |A|, p1 , 1ε ), with probability at least 1 − p, the simulator terminates with a strategy profile (πMax , πMin ) after at most N procedure calls where both strategies are ε-optimal. Sample Complexity. The function f in the definition of PAC-RL is called the sample complexity of the learning algorithms. If f is a polynomial function, then we say that the learning algorithms have polynomial sample complexity. General Hardness. It is known that, even for MDPs with reachability objectives, there is no algorithm that is PAC-RL in general [1, 23], meaning that there is no function f that satisfies the condition of PAC-RL. In order to circumvent this hardness, we consider a parameter called Expected Conditional Distance (ECD).

3

Expected Conditional Distance

In this section, we introduce a parameter for TBSGs called the Expected Conditional Distance (ECD). The ECD parameter was previously studied for MDPs with reachability objectives [20]. The main goal of this parameter is to reduce the PAC-RL for reachability to PAC-RL for finite-horizon reachability. The generalization of this parameter to TBSGs is quite subtle, since we show below that several natural generalizations do not yield a suitable bound on the horizon. We then provide an appropriate generalization to TBSGs and give a reduction from PAC-RL with the ECD parameter to PAC-RL for finite-horizon reachability objectives. Finally, we discuss several key aspects of our parameter which justify the usefulness: (a) its important properties that make it useful for PAC learning; (b) how it can be bounded using other classical parameters from the literature; and (c) how it compares with the well-studied stochastic shortest path parameter.

A. Asadi, K. Chatterjee, P. Kebis

3:7

0.1 a

⊥

0.9 0.2

s0 b

s1

a

b 0.999

0.8 0.001

⊤

Figure 1 A game where alternative generalizations of ECD fail

▶ Definition 6 (Alternative Generalizations). Given a TBSG G = (S, A, δ, µ) with a target set T ⊆ S, consider the following alternative definitions of ECD: ECD1G := ECD2G := ECD3G := ECD4G := ECD5G :=

sup

inf

ETRG (πMax , πMin ) ,

πMin ∈ΠMin πMax ∈ΠMax

sup

ETRG (πMax , πMin ) ,

inf

πMin ∈Π0Min πMax ∈BR(πMin )

inf

sup

ETRG (πMax , πMin ) ,

πMax ∈Π0Max πMin ∈ΠMin

sup

inf

ETRG (πMax , πMin ) ,

πMin ∈ΠMin πMax ∈Π0Max

inf

sup

ETRG (πMax , πMin ) ,

πMin ∈ΠMin πMax ∈ΠMax

where ETR(π) is the expected time to reach the target set using the strategy profile (πMax , πMin ):   ETRG (πMax , πMin ) := Eπµ arg inf 1(sn ∈ T ) | (sn )n∈N ∩ T ̸= ∅ . n∈N

These definitions fail in the following example for a reduction of PAC-RL for reachability to PAC-RL for finite-horizon reachability. ▶ Example 7. Consider a game, shown in Figure 1, with four states S = {s0 , s1 , ⊤, ⊥} where ⊤ and ⊥ are absorbing states. State s0 belongs to Max and s1 belongs to Min. The action set is A = {a, b}. The target set is T = {⊤}. In state s0 , playing action a leads to ⊤ with probability 0.9 and leads to ⊥ with probability 0.1, and playing action b leads to s1 with probability 1. In state s1 , playing action a leads to ⊤ with probability 0.8 and leads to ⊥ with probability 0.2, and playing action b leads to ⊤ with probability 0.001 and self loops with probability 0.999. The initial state is s0 . Therefore, in the case of the infinite-horizon version of the game, the optimal strategies for both players are to play the action a. However, for any finite-horizon game with horizon L ≤ 100, the optimal strategy for Min is to play action b. We need the ECD parameter to bound a horizon length for which a near-optimal strategy in the finite-horizon game is also near-optimal in the infinite-horizon game. However, all of the definitions above fail as their values are at most 2. The values ECD1G , ECD2G , ECD3G , and ECD4G are equal to 1 for this game since the infimum over player-Max actions selects action a which ends the game immediately. The value of ECD5G is 2 since the infimum over player-Min actions selects the action a. It is noteworthy that changing the probabilities of action b in the state s1 makes the gap between the needed horizon and ECD values larger. In contrast, our definition of ECD provides a suitable bound on the horizon since ECDG = 1001.

CONCUR 2026

3:8

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives

▶ Definition 8 (Expected Conditional Distance). Given a TBSG G = (S, A, δ, µ) with a target set T ⊆ S, the expected conditional distance is defined as follows. ECDG :=

sup

inf

ETRG (πMax , πMin ) ,

πMin ∈ΠMin πMax ∈BR(πMin )

where ETRG (πMax , πMin ) is defined as in Definition 6. Description of ECD. If the ECD parameter is bounded by L, then for all strategies for player Min, there exists a best-response strategy of player Max that can reach the target set T in expected time at most L. More formally, the ECD parameter is defined as follows. For any player-Min strategy, take the set of player-Max strategies that are best-responses for the reachability objective. Among these reachability-optimal strategies, ECD takes the one that minimizes the expected number of steps to reach the target, conditioned on the target being reached. Finally, ECD takes the maximum of this quantity over all player-Min strategies. We now define the PAC learning framework with respect to the ECD parameter. ▶ Definition 9 (PAC-RL with ECD). A pair of learning algorithms (AMax , AMin ) is PAC-RL with ECD if there exists a function f such that for all ε, p ∈ (0, 1), all L ∈ N, and all TBSGs G = (S, A, δ, µ) with a target set T ⊆ S such that ECDG ≤ L, taking N = f (|S|, |A|, p1 , 1ε , L), with probability at least 1−p, the simulator terminates with a strategy profile (πMax , πMin ) after at most N procedure calls where both strategies are ε-optimal. ▶ Remark 10. The difference between this definition and the standard PAC-RL definition is the inclusion of the ECD parameter L in the function f . We now define an objective called finite-horizon reachability and show that the problem of PAC-RL with ECD for reachability objectives can be reduced to the problem of PAC-RL for finite-horizon reachability objectives. ▶ Definition 11 (Finite-horizon Reachability Objectives). Given a set of target states T and a time horizon L ∈ N, the finite-horizon reachability objective requires that a target state is visited within the first L steps, i.e., ReachL (T ) := {ω ∈ Ω : ∃ℓ ∈ [L] sℓ ∈ T }. We also admit L ∈ R in which case the target has to be visited within the first ⌊L⌋ where ⌊x⌋ is the biggest π number n ∈ N such that n ≤ x. We denote ValG RL (T ) (µ) := supπMax ∈ΠMax inf πMin ∈ΠMin Pµ (ω ∈ ReachL (T )). We omit writing G when clear from the context. We similarly define the PAC-RL for finite-horizon reachability objectives. ▶ Definition 12 (PAC-RL for Finite-horizon Reachability Objectives). A pair of learning algorithms (AMax , AMin ) is PAC-RL for finite-horizon reachability objectives if there exists a function f such that for all ε, p ∈ (0, 1), all TBSGs G = (S, A, δ, µ) with a target set T , and all time-horizons L ∈ N, taking N = f (|S|, |A|, p1 , 1ε , L), with probability at least 1 − p, the simulator terminates with a strategy profile (πMax , πMin ) after at most N procedure calls where both strategies are ε-optimal. ▶ Proposition 13. Let π be a strategy profile such that ETRG (π) ≤ L. Then, for all ε > 0 we have Pπµ (ω ∈ Reach L (T )) − Pπµ (ω ∈ Reach(T )) ≤ ε . ε

Proof. Recall that ETRG (π) = Eπµ (arg inf n∈N 1(sn ∈ T ) | (sn )n∈N ∩ T ̸= ∅). By Markov’s
inequality and ETRG (π) ≤ L, we have Pπµ arg inf n∈N 1(sn ∈ T ) > Lε | (sn )n∈N ∩ T ̸= ∅ ≤ ε, which yields the result. ◀

A. Asadi, K. Chatterjee, P. Kebis

3:9

▶ Theorem 14. If a pair of learning algorithms (AMax , AMin ) is PAC-RL for finite-horizon reachability objectives, then it is PAC-RL with ECD for reachability objectives. Proof Sketch. Let H = 2(L + 1)/ε. Run the finite-horizon PAC-RL algorithm with horizon H and error tolerance ε/2. With probability at least 1 − p, it returns a profile π ⋆ that is ε/2-optimal for the finite-horizon reachability game. Since ECDG ≤ L, for every player-Min strategy πMin there exists a best-response πMax of Max such that ETRG (πMax , πMin ) ≤ L + 1. By Proposition 13, truncating reachability to horizon H = 2(L + 1)/ε changes the reachability probability of such a best response by at most ε/2. Therefore, |ValR(T ) (µ) − ValR 2(L+1) (T ) (µ)| ≤ 2ε . Combining this with the ε/2-optimality of π ⋆ in the finite-horizon ε

game gives that π ⋆ is ε-optimal for the original reachability objective. Hence PAC-RL for finite-horizon reachability implies PAC-RL with ECD for reachability. ◀ We now discuss several key aspects of the ECD parameter which justify why we use this parameter in this work. Properties of ECD. our ECD definition has two important properties: First, for every game it is finite. Second, it has a meaningful intuition to bound the horizon of the game, i.e., it captures that for every strategy of player Min, there exists a counter-strategy of player Max such that (i) the counter-strategy is optimal for the reachability objectives with respect to the strategy of player Min; and (ii) the expected time to reach is small. Estimation of ECD. A related parameter is the minimum non-zero transition probability pmin of a TBSG G. This parameter has been used in the context of PAC learning for TBSGs with reachability objectives [2]. The minimum non-zero transition probability pmin provides a bound on the expected time to reach the target set T . Indeed, if pmin > 0, then for any strategy profile π, we have ETRG (π) ≤ (1/pmin )|S| . However, this worst-case bound is exponential, while the ECD parameter can be much smaller. Better bounds require more information about the game. Since we provide the theoretical foundation in this work, model-dependent estimation of this parameter is subject for future work. Stochastic Shortest Path. A closely-related parameter to ECD is the stochastic shortest path (SSP) parameter [3]. The difference between SSP and ECD is that, in SSP, player Max requires to reach the target set T as soon as possible, while player Min wants to delay the reachability of the target set T as much as possible. The SSP parameter measures non-reaching plays as having infinite cost. Therefore, this parameter can be infinite. In contrast, our definition guarantees that the parameter is always finite. Finiteness of the parameter is necessary for the reduction to finite-horizon games.

4

PAC-RL for Finite-horizon Reachability

In this section, we present a pair of algorithms (LeTuReGaMax , LeTuReGaMin ) for PACRL of TBSGs with finite-horizon reachability. LeTuReGa stands for Learning Turn-based Reachability Games. ▶ Theorem 15. The pair of algorithms (LeTuReGaMax , LeTuReGa Min ) is PAC-RL   for finite-horizon reachability objectives with sample complexity O

|S|3 L7 |A| log(|S|2 L2 /p) ε3

.

Theorems 14 and 15 imply a result for reachability objectives with ECD assumption. ▶ Corollary 16. The pair of algorithms (LeTuReGaMax ,LeTuReGaMin ) is PAC-RL with 

ECD for reachability objectives with sample complexity O

|S|3 L7 |A| log(|S|2 L2 /(pε2 )) ε10

.

CONCUR 2026

3:10

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives

Proof. To obtain ε-optimal strategies for the infinite-horizon reachability, we use finitehorizon algorithms with the length of the game 2(L + 1)/ε (see the proof of Theorem 14). ◀ Significance. Corollary 16 establishes that reachability becomes PAC learnable in turnbased stochastic games in a decentralized and private information setting under bounded ECD. To the best of our knowledge, this is the first result that (i) handles decentralized and private learning; or (ii) provides explicit polynomial sample complexity bounds. This section is organized as follows. We first recall some algorithms from bandit learning literature. Then, we describe the LeTuReGa algorithms and finally, we prove Theorem 15.

4.1

Best-Arm Identification

In this subsection, we recall a problem in the bandit learning literature and an optimal solution for it. The best arm identification bandit learning problem asks to find an ε-optimal arm with probability 1 − p. Let A be a set of arms where each arm is associated with an unknown value r : A → [0, 1]. A player can sample an arm a ∈ A to obtain a random reward R ∈ {0, 1} such that E(R) = r(a). We say an algorithm can identify an ε-optimal arm with sample complexity f and confidence 1 − p, if for any set of arms A and any p, ε ∈ [0, 1], after f (|A|, 1/p, 1/ε) samples, with probability at least 1 − p it outputs a candidate arm a′ such that | maxa r(a) − r(a′ )| ≤ ε. A basic approach is to sample each arm log(|A|/p) times, ε2 estimate its unknown value, and then select the best arm. The guarantees follow directly from Hoeffding’s bound. A better sample complexity is achieved by the Median Elimination algorithm [9][Theorem 10], presented in Algorithm 2 in Section C. See Lemma 17 for the formal statement. This sample complexity matches the lower bound for this problem [16]. ▶ Lemma 17 ([9][Theorem 10). ] For a set of arms A, a value function r : A → [0, 1], error and confidence ε, p ∈ (0, 1),  Algorithm  2 identifies an ε-optimal arm with confidence 1 − p and sample complexity O

4.2

|A| log(1/p) ε2

.

Algorithm

This section presents a pair of algorithms for PAC-RL of TBSGs with finite-horizon reachability objectives. First, we give an overview of the main techniques used in the algorithm. We then provide a more detailed description. The pseudocode of the algorithm is provided in Algorithm 1. The correctness of the algorithm is proven in the next subsection. Algorithm Overview. Firstly, the algorithm extends the set of states to state-steps, i.e., it learns which action is good enough for every state-step pair, where step is bounded by the horizon. The algorithm keeps track of unexplored state-steps. Initially, all state-steps are considered unexplored except for the target set. The set of unexplored state-steps shrinks over time, and it is treated as a target to enhance exploration. In the learning process, the algorithm learns how to visit more state-steps and identifies good-enough actions for each of them. The procedure follows in stages. In each stage, the algorithm constructs a new strategy by backward induction. For each state-step, it uses a best arm identification routine, which proposes a local ε-optimal action with high confidence. The algorithm always learns one step at a time, fixing the strategy in the rest of the game. At the end of the induction, a candidate strategy is constructed. This strategy is then used to discover new state-steps. If no new state-steps are discovered from the perspective of the player, this player proposes to the simulator to terminate the algorithm with the recently constructed strategy. The procedure terminates only when both players propose to the simulator to terminate. We now define some notions used in our algorithm.

A. Asadi, K. Chatterjee, P. Kebis

3:11

▶ Definition 18 (Expanded Game). For a given TBSG G = (S, A, δ, µ) with a target set T ⊆ S and a time horizon L ∈ N, we define the expanded game G′ := (S ′ , A, δ ′ , µ′ ) where ′ ′ S ′ := SMax ⊎ SMin where Si′ := {(s, ℓ) : s ∈ Si , ℓ ∈ [L]} for i ∈ {Max, Min}; For all states s, s′ ∈ S, actions a ∈ A and steps ℓ, ℓ′ ∈ [L], the transition function δ ′ is defined as  ′ ′   δ(s, a)(s ) if ℓ ∈ [L − 1] ∧ ℓ = ℓ + 1 δ ′ ((s, ℓ), a)(s′ , ℓ′ ) := 1 if ℓ = L ∧ ℓ′ = L ∧ s′ = s   0 otherwise; For all states s ∈ S and steps ℓ ∈ [L], the initial distribution µ′ is defined as ( µ(s) if ℓ = 0 µ′ (s, ℓ) := 0 otherwise. The target set is defined as TMax := T × [L]. We also define a target set for the player Min as TMin := {(s, L) | s ̸∈ T }. The expanded game is the original game accompanied by a counter. A play starts with the counter value of 0, and in every step the counter is incremented. The counter is bounded by L, which means the state stays invariant after L steps. Consequently, the expanded game is equivalent to the original game for the finite-horizon L. Moreover, the fact that the state is not changed after L steps implies that the finite-horizon variant has the same value as the infinite-horizon for the expanded game. Thus, we obtain the following result. ▶ Proposition 19. For a given TBSG G = (S, A, δ, µ) with a target set T ⊆ S and a time G′ G′ horizon L ∈ N, we have ValG RL (T ) = ValRL (TMax ) = ValR(TMax ) . ▶ Remark 20. Recall that positional strategies are as powerful as general strategies for TBSGs with reachability objectives. Thus, by Proposition 19, we only consider positional strategies in the expanded game, and we need to consider Markovian strategies in the original game. ▶ Definition 21. Given an expanded TBSG game G = (S ′ , A, δ ′ , µ′ ) and two disjoint sets U, V ⊆ S ′ , we define NotUntil(U, V ) := {ω ∈ (S ′ × A)∗ × S ′ : ∃ℓ ≥ 0, sℓ ∈ V, ∀j ∈ [ℓ − 1] : sj ̸∈ U }. Intuitively, NotUntil(U, V ) is the set of finite plays that avoid reaching any state from U until a state from V is reached. In the algorithm, we use constants which we define below. ▶ Definition 22 (Constants). Let G = (S, A, δ, µ) be a TBSG with finite-horizon L and p, ε ∈ [0, 1] be the confidence and error of the PAC guarantees. We define the constants used in the algorithm as follows. ε εemp := 8|S|L ; ε εbai := 2L ; C is the constant given by the best arm identification algorithm constant that is implicitly present in the O-notation [9][Theorem 10]; and 2 2 L /p) K := C|A| εlog(|S| . 2 ε emp bai

We are now able to explain the algorithms in detail. Algorithm Details. Pseudocode of the algorithms is given in Algorithm 1. We describe the algorithm for player i ∈ {Max, Min}. The algorithm starts by initialising the set of

CONCUR 2026

3:12

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives

unexplored state-steps Ui0 to be any state owned by player i which is not in the last step |S ′ | (Line 1) and the strategies πi0 , . . . , πi (Line 2). A strategy πiq is constructed in the stage q using backward induction (Line 27) and it is used in all of the following stages q + 1, q + 2, . . . for the purpose of exploration (Line 8). After the initialisation, the algorithm runs at most |S ′ | stages (Line 4) and in each stage it performs backward induction on the length of the game L (Line 6). In a stage q, after it performs an induction, it checks whether the set of unexplored state-steps has shrinked or not (Line 31). If not, it means the strategy learnt in the stage q − 1 did not explore anything new, which makes it a good candidate for an ε-optimal strategy. However, this holds only if the set of unexplored states is unchanged for both players in the same stage, which results in the termination of the procedure. The backward induction is split into a sampling phase (Line 7 to Line 18) and an analysis phase (Line 22 to Line 27). Let the stage be q and the level of induction be ℓ. In the sampling phase, the algorithm learns the best action for a state-step (s, ℓ) where s ∈ Si . To achieve this, the algorithm uses formerly constructed strategies πi0 , . . . , πiq−1 in the first ℓ − 1 steps of the game. In the step ℓ it plays according to a best-arm identification routine that tries various actions to determine the best one with high confidence. In the steps ℓ + 1 onwards, it plays according to the currently learnt strategy πiq which is being inductively constructed (Line 11). The algorithm samples qK plays, that is, K plays for every formerly constructed strategy πir for r ∈ [q − 1] (Line 12). The algorithm tracks whether player i is successful in a particular play (Line 16). For player Max, this happens when the play reaches a target state or an unexplored state-step. For player Min, it happens either when the target states are completely avoided, or when an unexplored state-step is reached before a target state is reached. For every state s, the algorithm keeps track of how many times the best arm identification routine was called for that state (Line 18). In the analysis phase of the induction, the algorithm changes the strategy πiq to play according to the result of the best-arm identification routine for the step ℓ in a state s (Line 27). This happens only if the state was visited a sufficient number of times (Line 26). Furthermore, if a state s was visited even higher number of times (Line 23), the state-step (s, ℓ) is removed from the set of unexplored state-steps (Line 24). Comparison with existing work. In the algorithm design, we drew inspiration from [8]. However, our work differs significantly from theirs. First, we consider turn-based games with reachability objectives where PAC-RL guarantees are impossible in general, while they consider concurrent discounted-sum games which are easy in PAC learning. Second, they use an adversarial bandit learning routine, while we use a best-arm identification routine. Third, our approach removes the need to estimate the visitation distribution, it is simpler in general, and mainly, the complexity of our algorithm is more efficient than theirs.

4.3

Proof of Theorem 15

Overview of the proof. We proceed as follows: (a) we prove that the learning simulation terminates (Lemma 23); (b) we define some notations that we use in the next steps (Definition 25); (c) we define an event (Definition 28) that occurs with high probability (Lemma 29); and (d) we show that under this event, the strategy profile proposed by the algorithms is ε-optimal for the finite-horizon reachability game (Lemmas 30–32). ▶ Lemma 23. The learning simulation of algorithms (LeTuReGaMax , LeTuReGaMin ) terminates after at most |S ′ | stages. Proof. At the end of every stage q, if Uiq = Uiq−1 , then the algorithm LeTuReGai proposes πiq−1 as the candidate strategy. The learning simulation terminates (Line 32) if both algorithms propose a candidate strategy. Otherwise, at least one state-step has to be

A. Asadi, K. Chatterjee, P. Kebis

3:13

Algorithm 1 Algorithm LeTuReGai for player i ∈ {Max, Min}

Data: Si , |S|, A, p, ε, L Ui0 ← Si × [L − 1] ; // set of unexplored states q uniform 2 πi ← π for all q ∈ 0, 1, . . . , |S ′ | ; // memoryless uniform strategy q ′ ′ 3 Ci (s, ℓ) ← 0 for all q ∈ [|S |], (s, ℓ) ∈ S ; // visit counter of (s, ℓ) in stage q ′ 4 for q ∈ 1, . . . , |S | do q q−1 5 Ui ← Ui ; 6 for ℓ ∈ L − 1, . . . , 1 do 7 Initialise a best-arm identification (BAI) routine for all s ∈ Si with (εbai , |S 2p|L2 ) parameters ;

1

8 9 10

11

for πi ∈ πi0 , . . . , πiq−1 do for k ∈ 1, . . . , K do Let πiBAI (s) be the action that the BAI routine wants to sample at the state s, for all s ∈ Si ; Define a positional strategy for any s ∈ Si , j ∈ [L]    πi (s, j) if the step j < ℓ ′ πi (s, j) ← πiBAI (s) if the step j = ℓ ;   π q (s, j) if the step j > ℓ i

Interact with the simulator M to sample a play (s1 , a1 , s2 , a2 , . . . , sJ−1 , aJ−1 , sJ ) using the strategy πi′ . Notice that J < L only if sJ ∈ T ; 13 if J > ℓ and sℓ ∈ Si then 14 P lay ← ((sℓ+1 , ℓ + 1), aℓ+1 , . . . , (sJ , J)); ( q NotUntil(∅, UMax ∪ TMax ) if i = Max 15 W inning ← ; q NotUntil(TMax , UMin ∪ TMin ) if i = Min 16 Result ← 1(P lay ∈ W inning); 17 Update the BAI routine at the state sℓ with (aℓ , Result) ; // Note that aℓ was requested by πiBAI (sℓ ) 18 Increment Ciq (sℓ , ℓ); 19 end 20 end 21 end 22 for s ∈ Si do 23 if Ciq (s, ℓ) ≥ 3Kεemp then 24 Uiq ← Uiq /{(s, ℓ)}; 25 end 26 if Ciq (s, ℓ) ≥ Kεemp then 27 Make πiq to play the action suggested by BAI at the state (s, ℓ); 28 end 29 end 30 end 31 if Uiq = Uiq−1 then 32 Call M.propose(πiq−1 ); 33 end 34 end 12

CONCUR 2026

3:14

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives

q q removed either from UMax or UMin . However, this cannot happen more than |S ′ | times as 0 0 ′ |UMax ∪ UMin | ≤ |S | which means the simulation terminates after at most |S ′ | stages. ◀

▶ Definition 24. We define f ∈ {1, . . . , |S ′ |} as the stage q − 1, i.e., the second-to-last stage before termination. π Notions of V and Q values. We define the value VB,W (s, ℓ) which is the probability of ′ reaching a state-step from W ⊆ S while avoiding B ⊆ S ′ , starting in a state-step (s, ℓ) and playing according to the expanded game G′ and a strategy profile π. The value QπB,W (s, ℓ, a) π is defined similarly to VB,W (s, ℓ) but the first action taken is a.

▶ Definition 25. Let G′ = (S ′ , A, δ ′ , µ′ ) be an expanded game for an original game G = (S, A, δ, µ). Let B, W ⊆ S ′ be two disjoint subsets and π a positional strategy profile for the expanded game. For all states s ∈ S and steps ℓ ∈ [L], we inductively define   if (s, ℓ) ∈ W  1 π VB,W (s, ℓ) := 0 if (s, ℓ) ∈ B or (s, ℓ) = (s, L) ̸∈ W   Qπ (s, ℓ, π(s, ℓ)) otherwise B,W

and for all states s ∈ S, steps ℓ ∈ [L − 1], and actions a ∈ A, we have X π QπB,W (s, ℓ, a) := δ(s, a)(s′ )VB,W (s′ , ℓ + 1) . s′ ∈S

P π π := s∈S µ(s)VB,W We also denote VB,W (s, 0). Proposition 26 connects these notions with the values computed by the algorithms. ▶ Proposition 26. For all positional strategy profiles π for the expanded game, all states s ∈ S, and all sets B, W ⊆ S ′ , the following statements hold. For all steps ℓ ∈ [L], we have π VB,W (s, ℓ) = Pπ(s,ℓ) ((sℓ , aℓ , . . . , sL ) ∈ NotUntil (B, W )) ;

for all steps ℓ ∈ [L − 1] and actions a ∈ A, we have QπB,W (s, ℓ, a) = Pπδ′ ((s,ℓ),a) ((sℓ+1 , aℓ+1 , . . . , sL ) ∈ NotUntil (B, W )) . Proof Sketch. The proof is by backward induction on ℓ. At the last step , the claim is immediate from the definition. For ℓ < L, by the induction hypothesis and the law of total P π probability, the quantity QπB,W (s, ℓ, a) = s′ ∈S δ(s, a)(s′ )VB,W (s′ , ℓ + 1) is the probability of π satisfying NotUntil(B, W ) after taking action a. Then VB,W (s, ℓ) follows directly because it is 0 on B, 1 on W , and otherwise equals QπB,W (s, ℓ, π(s, ℓ)). Thus both recursive definitions coincide with the reach-avoid probabilities. ◀ Event E. We define an event E which is a collection of conditions. To do so, we first define some useful notations. P q q ▶ Definition 27. We define C q (s, ℓ) := i∈{Max,Min} Ciq (s, ℓ) and U q := UMax ∪ UMin for all q ∈ [f ], s ∈ S, ℓ ∈ [L]. Intuitively, C q (s, ℓ) is the number of times the pair (s, ℓ) is visited in the stage q. By U q , we denote all unexplored state-step pairs. ▶ Definition 28. After both algorithms terminate, we say an event E happens if for all stages q ∈ [f ] and every state (s, ℓ) ∈ S ′ , all of the following conditions hold:

A. Asadi, K. Chatterjee, P. Kebis

3:15

(a) r

X

C q (s, ℓ) − K

π ≤ Kεemp ; V∅,{(s,ℓ)}

(1)

r∈[q−1] ′

(b) if C q (s, ℓ) ≥ 3Kεemp then C q (s, ℓ) ≥ Kεemp for all stages q ′ ∈ {q, . . . , f }; and (c) for all a ∈ A, if s ∈ SMax then q

Qπ∅,U q

Max

q πq q ∪TMax (s, ℓ, a) − Q∅,UMax ∪TMax (s, ℓ, πMax (s, ℓ)) < εbai

and if s ∈ SMin then q

QπTMax ,U q

Min

q πq q ∪TMin (s, ℓ, a) − QTMax ,UMin ∪TMin (s, ℓ, πMin (s, ℓ)) < εbai .

▶ Lemma 29. The probability of the event E is at least 1 − p. Proof Sketch. The event E consists of three parts. It is enough to show that (a) and (c) hold with probability at least 1 − p/2, while (b) follows deterministically from (a). A union bound then gives the result. For part (a), fix a stage q and a state-step (s, ℓ). The count Cq (s, ℓ) is exactly the total number of visits to (s, ℓ) in the K samples taken for each earlier profile π r . Hence it can be written as a sum of independent indicators whose expectation P πr is K r∈[q−1] V∅,{(s,ℓ)} . Applying Hoeffding’s inequality shows that Cq (s, ℓ) concentrates around this expectation within Kεemp , and taking a union bound over all stages, steps, and states gives probability at least 1 − p/2. For part (c), once (s, ℓ) ∈ / Uiq , parts (a) and (b) ensure that the best-arm identification routine at (s, ℓ) has been called enough for its (εbai , p/(|S|2 L2 )) guarantee. Therefore, by Proposition 26, the selected action is εbai -optimal with the stated confidence. Agian, a union bound gives probability at least 1 − p/2. ◀ Near-optimality of π f . In the following, we condition on the event E. Lemma 30 bounds the probability of reaching the set of state-steps U f under the strategy profile π f . Lemma 31 states that π f is Lεemp -optimal when treating U f as a target. Lemma 32 combines the two lemmas to show that the strategy profile π f is ε-optimal in the expanded game with finite-horizon reachability objectives. f

π ′ ▶ Lemma 30. Under the event E, we have V∅,U f ≤ 4|S |εemp .

Proof. First, the termination condition implies that U f = U f +1 . For any (s, ℓ) ∈ S ′ , we have that (s, ℓ) ∈ U f iff (s, ℓ) ∈ U f +1 if and only if (s, ℓ) has not been removed from f +1 f +1 UMax nor UMin . Therefore, for all (s, ℓ) ∈ U f , we have C q (s, ℓ) < 3Kεemp for all stages q ∈ {1, . . . , f + 1}. Using the property (a) of the event E for the stage f + 1, we get that P πr πf r∈[f ] V∅,{(s,ℓ)} ≤ 4εemp which implies in particular that V∅,{(s,ℓ)} ≤ 4εemp . Using the fact P πf πf that V∅,U ◀ f ≤ (s,l)∈U f V∅,{(s,ℓ)} we obtain the desired inequality. ▶ Lemma 31. Under the event E, the following statements hold. For all strategies πMax for the player Max, we have V

f πMax ,πMin

f ∅,UMax ∪TMax

f

π − V∅,U f

Max

∪TMax

≤ Lεbai ;

for all strategies πMin of the player Min, we have πf

,πMin

V Max f

TMax ,UMin ∪TMin

− VTπ

f

f Max ,UMin ∪TMin

≤ Lεbai .

CONCUR 2026

3:16

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives

Proof Sketch. Use backward induction on ℓ and prove the stronger bound V

f πMax ,πMin

f ∅,UMax ∪TMax

f

π (s, ℓ)−V∅,U f

Max

∪TMax

(s, ℓ) ≤ (L−l)εbai . The base case is immediate because both

values are fixed. For the induction step, the continuation error is bounded by (L − ℓ − 1)εbai by the induction hypothesis. If s ∈ Smax , there is at most one additional local error from the f choice of πmax (s, ℓ), and event E(c) gives that this action is εbai -optimal. Hence the total loss is at most (L − ℓ)εbai . If s ∈ Smin , no extra local loss is incurred, so the same bound follows. Evaluating this at the initial distribution gives the first inequality. The second inequality follows from symmetric arguments. ◀ ▶ Lemma 32. Under the event E, the following statements hold. sup

f πMax ,πMin

Pµ

πMax ∈ΠMax

ValRL (µ) −

(ω ∈ ReachL (T )) − ValRL (µ) ≤ ε ; πf

PµMax

inf

,πMin

(ω ∈ ReachL (T )) ≤ ε .

πMin ∈ΠMin

Proof Sketch. By Proposition 26, finite-horizon reachability can be written using the V π values: Pπµ (ω ∈ ReachL (T )) = V∅,T = 1 − VTπMax ,TMin . For Max, enlarge the target set from Max f Tmax to Umax ∪ Tmax . Lemma 31 says that π f is Lεbai -optimal for this auxiliary target, and Lemma 30 says that the reachability probability to the unexplored set U f under π f is at πMax ,π f

f

π most 4|S ′ |εemp . Hence, for any player-Max strategy πMax , we have V∅,TMax Min − V∅,T ≤ Max ′ Lεbai + 4|S |εemp ≤ ε. The inequality for Min is proven analogously. Use the auxiliary target f Umin ∪ Tmin , apply Lemma 31, and then remove the unexplored-set error using Lemma 30. Thus the strategies of both players are ε-optimal in the finite-horizon game. ◀

Proof of Theorem 15. We prove the correctness and sample complexity of the algorithms. Correctness. By Lemma 23, the algorithms terminate and by Lemma 32, the algorithms output ε-optimal strategies. Thanks to Proposition 19, the value of the original game and the expanded game coincide. Sample Complexity. We bound the number of procedure calls to the simulator M. Every sampled play at Line 12 corresponds to at most L + 1 procedure calls (either M.step(·) or M.reset()). Furthermore, there are at most |S ′ | + 1 number of M.propose(·) calls. We bound the number of sampled plays at Line 12. The loop at Line 4 is iterated at most |S|L number of times, the loop at Line 6 at most L times, the loop at Line 8 at most |S|L times, the loop at Line 9 at most K times, which means the number of plays sampled is bounded by |S|L · L · |S|L · K = |S|2 L3

C|A| log(|S|2 L2 /p) εemp ε2bai

C|A| log(|S|2 L2 /p) = 32|S| L6 ∈O ε3 3



|S|3 L6 |A| log(|S|2 L2 /p) ε3

Multiplying this by L + 1 and adding |S ′ | + 1 yields the result.



◀

Concluding Remarks. In this work, we consider the PAC learning of turn-based stochastic games with reachability objectives. We provide algorithms that ensure learning: (a) with private information; and (b) decentralized setting. Moreover, we generalize the ECD parameter from MDPs to games and establish a polynomial-sample complexity bound with respect to the number of states, actions, ECD parameter, and inverses of error tolerance and failure probability. This framework suggests several interesting open problems: (i) extending to concurrent stochastic games; and (ii) the setting where samplings are drawn from an arbitrary state rather than relying on simulator which restarts from the initial distribution.

A. Asadi, K. Chatterjee, P. Kebis

3:17

References 1

2

3 4 5 6 7 8

9

10 11 12 13

14 15 16 17 18 19 20

21 22 23

Rajeev Alur, Suguman Bansal, Osbert Bastani, and Kishor Jothimurugan. A framework for transforming specifications in reinforcement learning. In Principles of Systems Design, volume 13660 of Lecture Notes in Computer Science, pages 604–624. Springer, 2022. Pranav Ashok, Jan Kretínský, and Maximilian Weininger. PAC statistical model checking for markov decision processes and stochastic games. In Isil Dillig and Serdar Tasiran, editors, CAV 2019, New York City, NY, USA, July 15-18, 2019, volume 11561 of Lecture Notes in Computer Science, pages 497–519. Springer, 2019. doi:10.1007/978-3-030-25540-4\_29. Dimitri P. Bertsekas and John N. Tsitsiklis. An analysis of stochastic shortest path problems. Math. Oper. Res., 16(3):580–595, 1991. Patrick Billingsley. Probability and Measure. Wiley, Hoboken, NJ, USA, 2012. Ronen I. Brafman and Moshe Tennenholtz. A near-optimal poly-time algorithm for learning a class of stochastic games. In IJCAI, pages 734–739. Morgan Kaufmann, 1999. Ashok K. Chandra, Dexter Kozen, and Larry J. Stockmeyer. Alternation. J. ACM, 28(1):114– 133, 1981. Anne Condon. The complexity of stochastic games. Inf. Comput., 96(2):203–224, 1992. Constantinos Daskalakis, Noah Golowich, and Kaiqing Zhang. The complexity of markov equilibrium in stochastic games. In Gergely Neu and Lorenzo Rosasco, editors, COLT 2023, 12-15 July 2023, Bangalore, India, volume 195 of Proceedings of Machine Learning Research, pages 4180–4234. PMLR, 2023. Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. J. Mach. Learn. Res., 7:1079– 1105, 2006. Jie Fu and Ufuk Topcu. Probably approximately correct MDP learning and control with temporal logic constraints. In Robotics: Science and Systems, 2014. Yuri Gurevich and Leo Harrington. Trees, automata, and games. In STOC, pages 60–65. ACM, 1982. Alexander S. Kechris. Classical Descriptive Set Theory. Springer, New York, NY, USA, 1995. doi:10.1007/978-1-4612-4190-4. Edon Kelmendi, Julia Krämer, Jan Kretínský, and Maximilian Weininger. Value iteration for simple stochastic games: Stopping criterion and learning algorithm. In CAV (1), volume 10981 of Lecture Notes in Computer Science, pages 623–642. Springer, 2018. S. Lakshmivarahan and Kumpati S. Narendra. Learning algorithms for two-person zero-sum stochastic games with incomplete information. Math. Oper. Res., 6(3):379–386, 1981. Michael L. Littman. Markov games as a framework for multi-agent reinforcement learning. In ICML, pages 157–163. Morgan Kaufmann, 1994. Shie Mannor and John N. Tsitsiklis. The sample complexity of exploration in the multi-armed bandit problem. J. Mach. Learn. Res., 5:623–648, 2004. Mateo Perez, Fabio Somenzi, and Ashutosh Trivedi. A PAC learning algorithm for LTL and omega-regular objectives in mdps. In AAAI, pages 21510–21517. AAAI Press, 2024. Amir Pnueli. The temporal logic of programs. In FOCS, pages 46–57. IEEE Computer Society, 1977. Martin L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Statistics. Wiley, 1994. Jakub Svoboda, Suguman Bansal, and Krishnendu Chatterjee. Reinforcement learning from reachability specifications: PAC guarantees with expected conditional distance. In ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. Leslie G. Valiant. A theory of the learnable. Commun. ACM, 27(11):1134–1142, 1984. Min Wen and Ufuk Topcu. Probably approximately correct learning in stochastic games with temporal logic specifications. In IJCAI, pages 3630–3636. IJCAI/AAAI Press, 2016. Cambridge Yang, Michael L. Littman, and Michael Carbin. Reinforcement learning for general LTL objectives is intractable. CoRR, abs/2111.12679, 2021.

CONCUR 2026

3:18

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives

A

Proofs of Section 3

▶ Theorem 14. If a pair of learning algorithms (AMax , AMin ) is PAC-RL for finite-horizon reachability objectives, then it is PAC-RL with ECD for reachability objectives. Proof. Consider a TBSG G = (S, A, δ, µ), error tolerance ε ∈ (0, 1), failure probability p ∈ (0, 1), a parameter L ∈ R, and a target set T ⊆ S such that ECDG ≤ L. Let π ⋆ be a strategy profile outputted by the pair of algorithms (AMax , AMin ) such that, with probability at least 1 − p, both strategies are 2ε -optimal for the game G with finite-horizon reachability objective to the set T of length 2(L+1) , i.e., the following two inequalities ε ValR 2(L+1) (T ) (µ) − ε

(π

Pµ Max

sup

(π ⋆

Pµ Max

inf

,πMin )

(ω ∈ Reach 2(L+1) (T )) ≤ ε

πMin ∈ΠMin

⋆ ,πMin )

(ω ∈ Reach 2(L+1) (T )) − ValR 2(L+1) (T ) (µ) ≤ ε

πMax ∈ΠMax

ε

ε 2

(2)

ε 2

(3)

hold with probability at least 1 − p. From this point on, we condition on this event. First, we prove that ValR(T ) (µ) − ValR 2(L+1) (T ) (µ) ≤ ε

ε . 2

Indeed, since Reach 2(L+1) (T ) ⊆ Reach(T ), we have ε

ValR 2(L+1) (T ) (µ) ≤ ValR(T ) (µ) .

(4)

ε

Therefore, we only need to show that ε ValR 2(L+1) (T ) (µ) ≥ ValR(T ) (µ) − . 2 ε

(5)

From Definition 8, we have that for all πMin ∈ ΠMin , there exists πMax ∈ BR(πMin ) such that ET RG (π) ≤ ECDG + 1. We define a function φ : ΠMin → ΠMax such that ET RG (φ(πMin ), πMin ) ≤ ECDG + 1 and φ(πMin ) ∈ BR(πMin ) for all πMin . For all πMin ∈ ΠMin , we have  (1)    sup Pπµ ω ∈ Reach 2(L+1) (T ) sup Pπµ ω ∈ Reach 2(L+1) (T ) ≥ ε

πMax ∈ΠMax

ε

πMax ∈BR(πMin )

(2)



Min ),πMin ≥ Pφ(π ω ∈ Reach 2(L+1) (T ) µ



ε

(3)

ε 2 ε (4) = sup Pπµ (ω ∈ Reach(T )) − 2 πMax ∈ΠMax Min ),πMin ≥ Pφ(π (ω ∈ Reach(T )) − µ

(6)

where (1) follows from BR(πMin ) ⊆ ΠMax ; (2) follows from the definition of sup and since φ(πMin ) ∈ BR(πMin ); (3) follows from ET RG (φ(πMin ), πMin ) ≤ ECDG + 1 ≤ L + 1 and by Proposition 13; (4) follows from the definition of best response and since φ(πMin ) ∈ BR(πMin ). Now, we proceed to prove Inequality 5. We have   (1) ValR 2(L+1) (T ) (µ) = inf sup Pπµ ω ∈ Reach 2(L+1) (T ) πMin ∈ΠMin πMax ∈ΠMax

ε

(2)

≥

inf

sup

πMin ∈ΠMin πMax ∈ΠMax

ε

Pπµ (ω ∈ Reach(T )) −

ε (3) ε = ValR(T ) (µ) − , 2 2

A. Asadi, K. Chatterjee, P. Kebis

3:19

where (1) follows from the definition of finite-horizon reachability value; (2) follows from Inequality 6; (3) follows from the definition of reachability value. ⋆ We now show that π ⋆ is ε-optimal for reachability objectives. For the strategy πMax , we have ValR(T ) (µ) −

(π ⋆

Pµ Max

inf

,πMin )

(ω ∈ Reach(T ))

πMin ∈ΠMin (1)

≤ ValR(T ) (µ) −

(π ⋆

Pµ Max

inf

,πMin )

(ω ∈ Reach 2(L+1) (T )) ε

πMin ∈ΠMin (2) ε

≤

2

+ ValR 2(L+1) (T ) (µ) − ε

inf

(π ⋆

Pµ Max

,πMin )

(3)

(ω ∈ Reach 2(L+1) (T ) ≤ ε , ε

πMin ∈ΠMin

where (1) follows from Reach 2(L+1) (T ) ⊆ Reach(T ); (2) follows from Inequality 5; and (3) ε follows from Inequality 2. ⋆ For the strategy πMin , we have sup

(π

Pµ Max

⋆ ,πMin )

(ω ∈ Reach(T )) − ValR(T ) (µ)

πMax ∈ΠMax (1)

≤

(π

Pµ Max

sup

⋆ ,πMin )

πMax ∈ΠMax (2)

≤

ε

(π

Pµ Max

sup

(ω ∈ Reach(T )) − ValR 2(L+1) (T ) (µ)

⋆ ,πMin )

(ω ∈ Reach 2(L+1) (T )) + ε

πMax ∈ΠMax

(3) ε − ValR 2(L+1) (T ) (µ) ≤ ε , 2 ε

where (1) follows from Inequality 4; (2) follows from Inequality 6, (3) follows from Inequality 3. ◀

B

Proofs of Section 4

▶ Proposition 26. For all positional strategy profiles π for the expanded game, all states s ∈ S, and all sets B, W ⊆ S ′ , the following statements hold. For all steps ℓ ∈ [L], we have π VB,W (s, ℓ) = Pπ(s,ℓ) ((sℓ , aℓ , . . . , sL ) ∈ NotUntil (B, W )) ;

for all steps ℓ ∈ [L − 1] and actions a ∈ A, we have QπB,W (s, ℓ, a) = Pπδ′ ((s,ℓ),a) ((sℓ+1 , aℓ+1 , . . . , sL ) ∈ NotUntil (B, W )) . Proof. We prove both items by an induction on the step ℓ. Induction Base (ℓ = L). We have (1)

(2)

π VB,W (s, L) = 1((s, L) ∈ W ) = Pπ(s,ℓ) ((sL ) ∈ NotUntil (B, W )) ,

where (1) and (2) are by the definitions. Induction Step (ℓ < L). We first show the second item of the result and then we prove the first item. We assume the claims hold for ℓ + 1. We have (1) X π QπB,W (s, ℓ, a) = δ(s, a)(s′ )VB,W (s′ , ℓ + 1) , s′ ∈S

where (1) follows from the definition of QπB,W (s, ℓ, a).

CONCUR 2026

3:20

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives

 π By the induction hypothesis, we have VB,W (s′ , ℓ + 1) = Pπ(s′ ,ℓ+1) (sℓ+1 , aℓ+1 , . . . , sL ) ∈  P ′ NotUntil(B, W ) . Therefore, we have QπB,W (s, ℓ, a) = s′ ∈S δ(s, a)(s ) ·   Pπ(s′ ,ℓ+1) (sℓ+1 , aℓ+1 , . . . , sL ) ∈ NotUntil(B, W ) . Finally, by the law of total probability, the right-hand side is exactly the probability of the same event when the initial state-step is drawn from δ ′ ((s, ℓ), a) (i.e., (s′ , ℓ + 1) is chosen with probability δ(s, a)(s′ )): X δ(s, a)(s′ ) · Pπ(s′ ,ℓ+1) (·) = Pπδ′ ((s,ℓ),a) (·), s′ ∈S

which proves the second item. We now prove the first item. There are three cases. π Case 1: (s, ℓ) ∈ B. Then VB,W (s, ℓ) = 0 by Definition 25. Also, by starting the suffix from (s, ℓ), the condition of the event NotUntil(B, W ) is violated immediately. Hence   Pπ(s,ℓ) (sℓ , aℓ , . . . , sL ) ∈ NotUntil(B, W ) = 0. π Case 2: (s, ℓ) ∈ W . Then VB,W (s, ℓ) = 1 by Definition 25. By starting the suffix from (s, ℓ), the event NotUntil(B, W ) holds immediately. Thus   Pπ(s,ℓ) (sℓ , aℓ , . . . , sL ) ∈ NotUntil(B, W ) = 1.

Case 3: (s, ℓ) ∈ / B ∪ W . Then Definition 25 gives
π VB,W (s, ℓ) = QπB,W s, ℓ, π(s, ℓ) . By the induction hypothesis for the second item applied at step ℓ with state s and action π(s, ℓ), we have  
QπB,W s, ℓ, π(s, ℓ) = Pπδ′ ((s,ℓ), π(s,ℓ)) (sℓ+1 , aℓ+1 , . . . , sL ) ∈ NotUntil(B, W ) . Since (s, ℓ) ∈ / B∪W , the right-hand side is exactly the probability of satisfying NotUntil(B, W ) starting from (s, ℓ) under π, after taking the first (deterministic) action π(s, ℓ); hence this equals   Pπ(s,ℓ) (sℓ , aℓ , . . . , sL ) ∈ NotUntil(B, W ) which closes the third case. Combining the three cases proves the first item and completes the proof.

◀

▶ Lemma 29. The probability of the event E is at least 1 − p. Proof. We prove the probability of sub-events (a) and (c) is at least 1 − p/2 and the subevent (b) follows directly from the sub-event (a). Taking a union bound gives us the desired probability. Let q ∈ [|S ′ |] be a stage and (s, ℓ) ∈ S ′ be a state. (a) For a stage r ∈ [q − 1] and k ∈ [K], let Xr,k be the event of reaching a state-step (s, ℓ) P in a play induced by the strategy profile π r . We define X := r∈[q−1],k∈[K] Xr,k . By P r π Proposition 26, we have E(X) = K r∈[q−1] V∅,{(s,ℓ)} . q Lines 11 to 18 show that C (s, ℓ) = X since the value of C q (s, ℓ) only depends on the first ℓ − 1 steps of the sampled plays which are driven by the strategy profiles π 0 , . . . , π q−1 .

A. Asadi, K. Chatterjee, P. Kebis

Thus, we obtain 

3:21

 r

X

P  C q (s, ℓ) − K

(1)

π ≤ Kεemp  = P (|X − E(X)| ≤ Kεemp ) V∅,{(s,ℓ)}

r∈[q−1] (2)

(4)
(3) ≥ 1 − 2exp −(Kεemp )2 ≥ 1 − 2exp(−Kεemp ) ≥ 1 −

p , 2|S|2 L2

P πr where (1) follows from X = C q (s, ℓ) and E(X) = K r∈[q−1] V∅,{(s,ℓ)} , (2) follows from Hoeffding’s inequality, (3) follows from Kε ≥ 1, and (4) follows from Kεemp ≥ emp   2

2

log |S|4pL . Taking the union bound for all stages, steps and states, we get that the probability of the sub-event is 1 − p/2. (b) This is a direct consequence of the sub-event (a). Assuming 3Kεemp ≤ C q (s, ℓ) we get that 3Kεemp ≤ C q (s, ℓ) X πr ≤K V{(s,ℓ)} + Kεemp

(By Equation (1))

r∈[q−1] r

X

≤K

(q ′ ≥ q)

π V{(s,ℓ)} + Kεemp

r∈[q ′ −1] ′

≤ C q (s, ℓ) + 2Kεemp

(By Equation (1))

(c) We prove only the first claim as the second one is proven analogously. q The statement holds trivially for s such that (s, ℓ) ∈ UMax ∪ TMax . Hence, we assume q ′ q′ (s, ℓ) ̸∈ UMax which means there exists q < q such that C (s, ℓ) ≥ 3Kεemp (by the condition at Line 23). Assuming sub-events (a) and (b), this implies C q (s, ℓ) ≥ Kεemp . Hence, 2 2 L /p) the best arm identification routine (Line 17) was called at least Kεemp ≥ C|A| log(|S| ε2bai number of times which is sufficient to obtain (εbai , |S 2p|L2 )-PAC guarantees on the selected arm [9][Theorem 10]. First, we need to show that for each action a ∈ A, the samples were independent random variables from the same Bernoulli distribution. This is clear by the definition of the strategy in Line 11 since the part of the play from the step ℓ + 1 onwards is driven by the strategy profile π q which does not change during the sampling. Therefore, sampling an action a in a state-step (s, ℓ) corresponds to sampling a Bernoulli random variable with the value defined by Line 14 to Line 16, i.e., the random play that starts in (s, ℓ) satisfies the condition defined in Line 15. By Proposition 26, this is equal q to Qπ∅,U q ∪TMax (s, ℓ, a). Max

q Since the output of the best-arm identification routine is the action πMax (s, ℓ), we obtain p the desired inequality for all a ∈ A with probability 1 − |S|2 L2 . Taking a union over all stages, steps, and states, we obtain that the probability of the sub-event is 1 − p/2. ◀

▶ Lemma 31. Under the event E, the following statements hold. For all strategies πMax for the player Max, we have V

f πMax ,πMin

f ∅,UMax ∪TMax

f

π − V∅,U f

Max

∪TMax

≤ Lεbai ;

CONCUR 2026

3:22

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives

for all strategies πMin of the player Min, we have πf

,πMin

V Max f

TMax ,UMin ∪TMin

− VTπ

f

f Max ,UMin ∪TMin

≤ Lεbai .

Proof. We start by proving the first claim. Since there always exists an optimal positional strategy for the expanded game (see Remark 20), we assume πMax and πMin to be positional. We prove the claim by an induction on ℓ, i.e., we prove that for all states s ∈ S, we have V

f πMax ,πMin

f ∅,UMax ∪TMax

f

π (s, ℓ) − V∅,U f

Max

∪TMax

(s, ℓ) ≤ (L − l)εbai .

(7)

Induction Base (ℓ = L). The base case ℓ = L is trivial as both values are either 0 or 1 depending on whether s ∈ U f ∪ TMax and the strategies play no role. Induction Step (ℓ < L). We assume Equation (7) for ℓ + 1. There are two cases. f Case (s, ℓ) ̸∈ UMax ∪ TMax : Recall that δ(s, a)(s′ ) denotes the probability of reaching a ′ state s from a state s by playing an action a. First, we assume that s ∈ SMax . Therefore, we get V

f πMax ,πMin

f ∅,UMax ∪TMax

f

π (s, ℓ) − V∅,U f

Max

f πMax ,πMin

(1)

= Q =

(s, ℓ, πMax (s, ℓ)) − Qπ∅,U f

Max

δ(s, πMax (s, ℓ))(s′ )V

s′ ∈S (3) X

≤

(s, ℓ) f

f ∅,UMax ∪TMax

(2) X

∪TMax

f πMax ,πMin

f

Max

s′ ∈S

f (s, ℓ, πMax (s, ℓ)) f

f ∅,UMax ∪TMax

π δ(s, πMax (s, ℓ))(s′ )V∅,U f

∪TMax

(s′ , ℓ + 1) − Qπ∅,U f

Max

∪TMax

f (s, ℓ, πMax (s, ℓ))

∪TMax

f (s, ℓ, πMax (s, ℓ))

f

∪TMax

(s′ , ℓ + 1) − Qπ∅,U f

Max

+ (L − ℓ − 1)εbai (4)

f

f

= QπU f

∪TMax Max

(s, ℓ, πMax (s, ℓ)) − QπU f

Max

∪TMax

f (s, ℓ)) + (L − ℓ − 1)εbai (s, ℓ, πMax

(5)

≤ (L − ℓ)εbai where (1), (2) and (4) follow from Definition 25, (3) follows from the inductive assumption and (5) follows from the event E part (c). If s ∈ SMin , applying the same steps gives us even tighter bound (L − l − 1)εbai . Case (s, ℓ) ∈ U f ∪ TMax : This case is trivial due to Definition 25 and the fact that strategies play no role. Altogether, by Definition 25, we have V

f πMax ,πMin

f ∅,UMax ∪TMax

=

X s∈S

µ(s)V

f πMax ,πMin

f ∅,UMax ∪TMax

(s, 1) ,

which proves the first claim. We now prove the second claim similarly by induction on ℓ: πf

,πMin

V Max f

TMax ,UMin ∪TMin

(s, ℓ) − VTπ

f

f Max ,UMin ∪TMin

(s, ℓ) ≤ (L − l)εbai .

Induction based (ℓ = L). The base case ℓ = L is trivial. Induction Step (ℓ < L). There are two cases.

(8)

A. Asadi, K. Chatterjee, P. Kebis

3:23

f Case (s, ℓ) ̸∈ UMin ∪ TMax ∪ TMin : We first assume s ∈ SMin . Therefore, we get πf

,πMin

V Max f

TMax ,UMin ∪TMin πf

(1)

= Q Max

(s, ℓ) − VTπ

,πMin

f TMax ,UMin ∪TMin

(2) X

=

f

f Max ,UMin ∪TMin

(s, ℓ, πMin (s, ℓ)) − QπT

≤

f

f Max ,UMin ∪TMin

δ(s, πMin (s, ℓ))(s′ )V

s′ ∈S (3) X

(s, ℓ)

f πMin ,πMin f TMax ,UMin ∪TMin

δ(s, πMin (s, ℓ))(s′ )VTπ

f

f Max ,UMin ∪TMin

s′ ∈S

f (s, ℓ, πMin (s, ℓ))

(s′ , ℓ + 1) − QπT

f

(s′ , ℓ + 1) − QπT

f

f Max ,UMin ∪TMin

f Max ,UMin ∪TMin

f (s, ℓ, πMin (s, ℓ))

f (s, ℓ, πMin (s, ℓ))

+ (L − ℓ − 1)εbai (4)

= QπT

f

f Max ,UMin ∪TMin

(s, ℓ, πMin (s, ℓ)) − QπT

f

f Max ,UMin ∪TMin

f (s, ℓ, πMin (s, ℓ)) + (L − ℓ − 1)εbai

(5)

≤ (L − ℓ)εbai where (1), (2) and (4) follow from the Definition 25, (3) follows from the inductive assumption and (5) follows from the event E part (c). If s ∈ SMax , applying the same steps gives us even tighter bound (L − l − 1)εbai . Case (s, ℓ) ∈ U f ∪ TMax ∪ TMin : This is trivial. Altogether, by Definition 25, we have πf

,πMin

V Max f

TMax ,UMin ∪TMin

=

X

πf

,πMin

µ(s)V Max f

TMax ,UMin ∪TMin

s∈S

(s, 1) ,

which yields the result. ◀ ▶ Lemma 32. Under the event E, the following statements hold. f πMax ,πMin

Pµ

sup πMax ∈ΠMax

ValRL (µ) −

(ω ∈ ReachL (T )) − ValRL (µ) ≤ ε ; πf

PµMax

inf

,πMin

(ω ∈ ReachL (T )) ≤ ε .

πMin ∈ΠMin

Proof. Observe that for all strategy profiles π, we have Pπµ (ω ∈ ReachL (T )) = Pπµ′ ((s0 , a0 , . . . , sL ) ∈ NotUntil(∅, TMax )) = 1 − Pπµ′ ((s0 , a0 , . . . , sL ) ∈ NotUntil(TMax , TMin ) . Therefore, by Proposition 26 Item (1), we only need to prove the following statements. For all strategies πMax of the player Max, we have πMax ,π f

f

π V∅,TMax Min − V∅,T ≤ ε; Max

for all strategies πMin of the player Min, we have πf

,πMin

f

π Max VTMax ,TMin − VTMax ,TMin ≤ ε .

CONCUR 2026

3:24

PAC Learning in Turn-Based Stochastic Games with Reachability Objectives

For the first claim, we have πMax ,π f

f

(1)

π V∅,TMax Min − V∅,T ≤ V Max (2)

f πMax ,πMin

f ∅,UMax ∪TMax f πMax ,πMin f ∅,UMax ∪TMax

= V

(3)

f πMax ,πMin f ∅,UMax ∪TMax

≤ V (4)

≤ V

f πMax ,πMin

f ∅,UMax ∪TMax

f

π − V∅,T Max f

f

π π − V∅,T − V∅,U f Max

Max

f

f

π π − V∅,T − V∅,U f Max

f

π + V∅,U f

Max

+ 4|S ′ |εemp

Max

f

π − V∅,U f

(5)

Max

∪TMax

+ 4|S ′ |εemp

(6)

≤ Lεbai + 4|S ′ |εemp ≤ ε,

f where (1) follows from the fact that TMax ⊆ UMax ∪ TMax , (2) follows from algebraic πf πf πf manipulation, (3) follows from Lemma 30, (4) follows from V∅,U ≤ V∅,T + V∅,U , f f Max ∪T Max

Max

Max

(5) follows from Lemma 31, and (6) follows from Definition 22. Similarly for the second claim, we have πf

,πMin

f

(1)

πf

,πMin

π Max Max VTMax f ,TMin − VTMax ,TMin ≤ V

TMax ,UMin ∪TMin

(2)

πf

,πMin

≤ V Max f

TMax ,UMin ∪TMin

(3)

πf

,πMin

≤ V Max f

TMax ,UMin ∪TMin

(4)

πf

,πMin

≤ V Max f

TMax ,UMin ∪TMin

(5)

f

− VTπMax ,TMin f

− VTπMax ,TMin − VTπ

f

f Max ,UMin

f

− VTπMax ,TMin − VTπ

f

f Max ,UMin

− VTπ

f

f Max ,UMin ∪TMin

+ VTπ

f

f Max ,UMin

+ 4|S ′ |εemp

+ 4|S ′ |εemp

(6)

≤ Lεbai + 4|S ′ |εemp ≤ ε ,

f where (1) follows from the fact that TMin ⊆ UMin ∪ TMin , (2) follows from algebraic manipulaf f f tion, (3) follows from Lemma 30, (4) follows from VTπ ,U f ∪T ≤ VTπMax ,TMin + VTπ ,U f , Max

Min

Min

Max

Min

(5) follows from Lemma 31, and (6) follows from Definition 22. ◀

C

Outlines of Algorithms Algorithm 2 Best-Arm Identification Algorithm from [9][Section 3.2]

Data: A, ε, p A′ = A, ε′ = ε/4, p′ = p/2; ′ 2 while |A | > 1 do ′ ) 3 For all a ∈ A′ , sample a for log(3/p (ε′ /2)2 number of times and let ā be its empirical 1

value; Let m be the median value of {ā | a ∈ A′ }; 5 A′ ← A′ \ {a ∈ A′ | ā < m}; 6 ε′ ← ε′ 43 ; p′ ← p′ 12 ; 7 end ′ 8 return a ∈ A 4