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

Ali Asadi; Krishnendu Chatterjee; Pavol Kebis

REVIEW 2 major objections 5 minor 26 references

Turn-based stochastic games with reachability become PAC-learnable under private, decentralized learning, provided the game's expected conditional distance is bounded.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-02 00:51 UTC pith:AXAAKAFS

load-bearing objection The ECD generalization and the reduction are solid, but the decentralized-private PAC claim is unproven: the proof assumes a synchronized joint profile the setting never provides. the 2 major comments →

arxiv 2607.14877 v1 pith:AXAAKAFS submitted 2026-07-16 cs.LG cs.GT

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

Ali Asadi , Krishnendu Chatterjee , Pavol Kebis This is my paper

classification cs.LG cs.GT MSC 68Q3291A15

keywords PAC learningturn-based stochastic gamesreachability objectivesexpected conditional distanceprivate informationdecentralized learningsample complexitybest-arm identification

verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

PAC learning of reachability is provably impossible in general, even for single-player MDPs, and earlier stochastic-game results required public information and a shared learning algorithm. This paper relaxes both assumptions: it gives a pair of learning algorithms, one for each player, that work with private state observations and no communication, and are still guaranteed to output epsilon-optimal strategies for reachability objectives. The enabling tool is a new game-theoretic generalization of the Expected Conditional Distance (ECD), which measures the expected number of steps to reach the target under best responses; bounding this parameter turns the unbounded reachability objective into a tractable finite-horizon approximation. The paper claims the first positive result and a polynomial sample-complexity bound for this decentralized private setting, counting states, actions, the ECD bound, and the inverses of error and confidence.

Core claim

The paper asserts that when the player's expected conditional distance ECD is at most L, the infinite-horizon reachability value can be approximated within epsilon/2 by the finite-horizon value with horizon 2(L+1)/epsilon, so any PAC learner for finite-horizon reachability becomes a PAC learner for reachability. To exploit this, the authors define an expanded game over state-step pairs and supply two decoupled algorithms, LeTuReGaMax and LeTuReGaMin, which learn epsilon-optimal positional strategies through backward induction from the horizon, using best-arm identification at each state-step and maintaining a shrinking set of unexplored state-steps as auxiliary targets to force exploration.

What carries the argument

The game-theoretic Expected Conditional Distance (ECD), defined as the supremum over Min's strategies of the minimal expected time to reach the target among Max's best responses; it is always finite and determines the horizon needed for the finite-horizon approximation to be epsilon-close. The companion machinery is the expanded game over state-step pairs, which converts the unbounded objective into a finite backwards-induction problem solvable by local best-arm identification.

Load-bearing premise

The concentration and optimality proofs assume episodes are generated by a jointly fixed strategy profile and that each player can evaluate success conditions that may depend on the opponent's private state, but the pseudocode does not spell out how two non-communicating players synchronize stages or infer those conditions.

What would settle it

Take a minimal TBSG (e.g., one Max state and one Min state) and run the algorithms with a simulator that reveals only the active player's state. If under any valid interleaving of the two players' calls the stage counters or unexplored-state sets differ at termination, then the joint-profile assumption behind Lemma 29 and Lemma 31 fails, and the claimed PAC guarantee is not established by the proof.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

If the ECD bound L is finite, both players can compute epsilon-optimal strategies using only their own observations, with a number of simulator calls polynomial in |S|, |A|, L, 1/epsilon, and 1/p.
The reduction in Theorem 14 shows that any future finite-horizon PAC-RL algorithm for games can be converted to an infinite-horizon reachability learner under ECD, so the finite-horizon result is the reusable core.
Because the algorithms treat unexplored state-steps as auxiliary targets, they never need to estimate transition probabilities; only local action-quality values are learned, which is what makes the private setting tractable.
The ECD parameter is always finite, so the PAC-learnability claim applies to every TBSG, with the sample complexity growing as L grows.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same ECD-truncation idea may generalize to other omega-regular objectives: any objective for which a bounded 'expected distance to satisfaction' parameter exists could be learned by finite-horizon approximation plus local backward induction.
Since the algorithms rely only on best-arm identification rather than model estimation, they may extend to non-stationary or adversarially perturbed transition dynamics with minor changes to the confidence bounds.
The dependence on L in the sample bound implies that games with large ECD are effectively harder to learn in this framework, matching the intuition that rare but important targets require more exploration.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

The ECD generalization and the reduction are solid, but the decentralized-private PAC claim is unproven: the proof assumes a synchronized joint profile the setting never provides.

read the letter

Dear X,

Quick take: the paper has a genuinely new ECD generalization for TBSGs and a clean reduction from infinite-horizon reachability to finite-horizon PAC learning, but the headline decentralized/private result is not proven. The proof assumes a synchronized joint strategy profile that the algorithm and simulator never provide. I think the stress-test note is right, and it's a load-bearing gap, not a nitpick.

What's new and good: Definition 8 is a careful generalization, and Example 7 does real work—it shows why the naive min-max variants of ECD fail. Theorem 14 is clean and correct: bounded ECD lets you truncate to a finite horizon with a value error of ε/2. The finite-horizon algorithm itself is a reasonable combination of backward induction, BAI, and an 'unexplored set' exploration trick, and the sample complexity bound is explicit. If the proof were about a centralized learner that controls both players, I'd believe most of it.

Where it falls down. First, and most importantly, the decentralized/private setting is never actually implemented. Algorithm 1 is written from a single player's perspective, but when that player samples a play, the simulator does not fix the opponent's strategy. The opponent is running its own unsynchronized process. The proof of Lemma 29(a) and (c) treats C^q(s,ℓ) as the visit count under a joint profile π^q, and the BAI rewards as Bernoulli draws with mean Q^{π^q}. But the opponent is not necessarily playing π^q at that moment; the players have private observations and no shared stage counter. So the concentration argument doesn't apply to the algorithm as written. This is a serious gap: the claimed first positive result for decentralized private PAC learning is not established. Second, the paper asserts ECD is finite for every game, which is false when a Min strategy makes the target unreachable with probability zero—the conditional expectation is undefined. That's an edge case, but it should be handled explicitly (e.g., define ECD as ∞ and exclude those games, or note that learning is trivial when the value is 0). Third, Lemma 32 proves each bound relative to V^{πf}, not to Val_RL. Combining the two inequalities gives 2ε-optimality unless the constants are re-tuned. That's fixable by adjusting ε_bai and ε_emp, so minor.

Bottom line: the ECD reduction and the algorithmic skeleton are worth a serious referee. The paper needs to either drop the private/decentralized claim or redesign the interaction protocol so that a player can sample against a known joint profile—say, by having the simulator accept the opponent's strategy, which would violate the privacy assumption. As is, I wouldn't cite the main theorem, but I'd point people to the ECD definition and the reduction.

My recommendation: send it to review, with the expectation of major revision. The gap is identifiable and addressable, and the core idea may survive.

Best, [Your name]

Referee Report

2 major / 5 minor

Summary. The paper studies PAC learning of turn-based stochastic games (TBSGs) with reachability objectives under a bounded Expected Conditional Distance (ECD). It introduces a game-theoretic generalization of ECD, proves a reduction from infinite-horizon reachability to finite-horizon reachability, and presents a pair of algorithms (LeTuReGaMax, LeTuReGaMin) that are claimed to be PAC-RL for finite-horizon reachability with polynomial sample complexity, yielding the first positive result for decentralized and private learning of TBSGs with reachability objectives. The technical architecture combines backward induction on an expanded state-step game, best-arm identification at each state-step, and exploration driven by an ``unexplored target'' set.

Significance. The high-level goal is significant: removing the public-information and shared-algorithm assumptions would be a genuine advance in PAC learning for stochastic games. The ECD generalization is nontrivial, and Example 7 convincingly shows why naive definitions fail. The reduction in Theorem 14 is clean and modular, and the algorithm combines interesting ideas (expanded game, BAI, backward induction, and exploration via auxiliary targets). If the correctness proof were fully valid, the paper would make an important contribution. Unfortunately, the proof of the main finite-horizon result relies on a joint sampling oracle that the paper's own private/decentralized model does not provide, and there is also a constant-factor gap in the final optimality argument. I cannot regard the central claim as established.

major comments (2)

[Definitions 3–5, Algorithm 1, Lemma 29] The proof assumes that each sampled episode is generated by a common joint strategy profile π^r=(π^r_Max,π^r_Min). Definition 28(a) and Lemma 29(a) write C^q(s,ℓ) as a sum of indicators from plays induced by the joint profiles π^0,…,π^{q-1}, and Lemma 29(c) asserts that BAI rewards are i.i.d. draws from Q^{π^q}_{…}(s,ℓ,a). In the stated private/decentralized model, however, no such joint sampling oracle exists: each player only sees its own state and calls M.step/M.reset; it cannot observe the opponent's state or action, and the two algorithms do not communicate. Algorithm 1 (Lines 8–18) instructs each player to sample a play using its own local π'_i, but it never specifies how the opponent's actions are forced to match the same stage q, level ℓ, and strategy index r, nor how the two independent processes synchronize their counters. Without this coordination, the visits and rewards obtai
[§4.3, Lemma 32] The proof bounds deviations from the joint-payoff value V^{πf}, not from the game value Val_RL(μ). In the first displayed chain, the proof ends at V^{πMax,πfMin}_{∅,TMax} − V^{πf}_{∅,TMax} ≤ ε and then treats V^{πf}_{∅,TMax} as if it were Val_RL(μ). To justify this, one needs a lower bound V^{πf}_{∅,TMax} ≥ Val_RL(μ) − ε. The only source for such a bound is the second half of the lemma/Symmetry of Lemma 31, which by the same argument also costs ε. The two one-sided bounds compose to 2ε, not ε. With the stated constants (ε_bai=ε/(2L), ε_emp=ε/(8|S|L)), the proof shows 2ε-optimality. This is a local, re-tunable constant issue, and the asymptotic sample complexity would not change, but as written the lemma's statement is not proven.

minor comments (5)

[Section 3, Properties of ECD] The claim that ECD is finite for every game is false. If the reachability probability under some player-Min strategy is 0, the best responses have reach probability 0 and the conditional expected time ETR is undefined/infinite. Example: a single Min state with a self-loop and no transition to T. The theorem does not depend on this claim because Definition 9 restricts to games with ECD≤L, but the sentence ``our definition guarantees that the parameter is always finite'' should be corrected, e.g., by requiring reachability value >0 or defining ETR=∞.
[Definition 25 and Algorithm 1] There is an off-by-one mismatch: Definition 18 sets the initial distribution at ℓ=0, and the final display in Definition 25 sums over V(s,0), but the inductive definition of V(s,ℓ) is only given for ℓ∈[L]. Either extend the recursion to ℓ=0 or shift the horizon indices consistently throughout.
[Lemma 29(a) proof] The Hoeffding bound is written as exp(−(Kε_emp)^2). For a sum of K(q−1) indicator variables, the exponent should contain a factor 1/(q−1) (or 1/(K|S′|) after a crude union bound). The asymptotic conclusion likely survives, but the displayed calculation is not the correct Hoeffding exponent.
[Algorithm 1, Line 13] The pseudocode says ``J<L only if s_J∈T''. Make explicit that a play may end early when the target is reached, and explain how this interacts with the NotUntil winning condition and with the counting in Lemma 29.
[General] There are minor typos and formatting issues: ``statess∈S'' in Definition 25, inconsistent hyphenation, and the missing Algorithm 2 reference in the main body (it appears only in Appendix C). These do not affect the technical content.

Circularity Check

0 steps flagged

No significant circularity; the derivation is self-contained and the ECD parameter is an input assumption, not a fitted or predicted quantity.

full rationale

The paper's derivation chain is: define ECD (Definition 8), prove a horizon-truncation reduction (Theorem 14 via Proposition 13), present constructive learning algorithms (Algorithm 1), and prove PAC guarantees via concentration and backward induction (Lemmas 23, 29-32). The ECD parameter is an assumption bounding the expected conditional time to reach the target; it is not estimated or fitted from data, and no 'prediction' is a renamed fitted parameter. The sample complexity is computed by counting procedure calls in the algorithm, not assumed from the conclusion. The only self-citation is reference [20] (Svoboda, Bansal, Chatterjee) for introducing ECD in MDPs; the present paper redefines and generalizes ECD, so the citation is merely provenance and not load-bearing. The main risk in the paper is a correctness gap between the decentralized/private setting and the joint strategy profile used in the proofs (e.g., Lemma 29 and Lemma 31 assume plays are generated by pi^r), but this is not circularity because the proofs do not reduce to their own assumptions; rather, the algorithm may not implement the assumed sampling process. Per the required standard, no specific equation or construction in the paper makes its conclusion equivalent to its inputs, hence no circular step is identified.

Axiom & Free-Parameter Ledger

0 free parameters · 6 axioms · 0 invented entities

The central claim rests on the ECD boundedness assumption, standard game-theoretic determinacy, and an unstated synchronization premise. The algorithm constants are derived, not fitted. No new physical or mathematical entities are postulated.

axioms (6)

standard math TBSGs with reachability objectives are determined and positional optimal strategies exist [7, Theorem 2].
Used to justify restricting to positional strategies in the expanded game (Remark 20).
domain assumption The game has ECD_G ≤ L and ECD_G is finite.
PAC learnability is only claimed under this bounded-ECD assumption; the paper asserts finiteness for every game but does not handle zero-reachability cases where the conditional expectation is undefined.
domain assumption Learning is cooperative: both players run learning algorithms together, not adversarially during learning.
Adversarial learning is known impossible; Definition 3/5 formalize the cooperative simulator setting.
ad hoc to paper The two players' algorithms realize a common joint strategy profile π^r in each sampled episode.
Lemma 29(a) sums visits under profile π^r, but the pseudocode does not state how private, non-communicating players synchronize their stage counters and infer winning conditions; shared reset/target announcements may suffice but are not specified.
standard math Median Elimination identifies an ε-optimal arm with O(|A| log(1/p)/ε^2) samples [9, Theorem 10].
Used as the best-arm-identification subroutine; treated as a black box.
standard math Hoeffding's inequality and Markov's inequality.
Used in Proposition 13 and Lemma 29.

pith-pipeline@v1.3.0-alltime-deepseek · 22327 in / 35272 out tokens · 317808 ms · 2026-08-02T00:51:33.795315+00:00 · methodology

0 comments

read the original 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.

discussion (0)

Reference graph

Works this paper leans on

26 extracted references · 2 canonical work pages

[1]

2019 , url =

Pranav Ashok and Jan Kret. 2019 , url =. doi:10.1007/978-3-030-25540-4\_29 , timestamp =

work page doi:10.1007/978-3-030-25540-4 2019
[2]

2024 , timestamp =

Jakub Svoboda and Suguman Bansal and Krishnendu Chatterjee , title =. 2024 , timestamp =

2024
[3]

The Complexity of Markov Equilibrium in Stochastic Games , booktitle =

Constantinos Daskalakis and Noah Golowich and Kaiqing Zhang , editor =. The Complexity of Markov Equilibrium in Stochastic Games , booktitle =. 2023 , timestamp =

2023
[4]

Weichao Mao and Tamer Basar , title =. Dyn. Games Appl. , volume =. 2023 , url =. doi:10.1007/S13235-021-00420-0 , timestamp =

work page doi:10.1007/s13235-021-00420-0 2023
[5]

The Tenth International Conference on Learning Representations,

Ziang Song and Song Mei and Yu Bai , title =. The Tenth International Conference on Learning Representations,. 2022 , url =

2022
[6]

CoRR , volume =

Chi Jin and Qinghua Liu and Yuanhao Wang and Tiancheng Yu , title =. CoRR , volume =. 2021 , url =. 2110.14555 , timestamp =

Pith/arXiv arXiv 2021
[7]

Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems , journal =

Eyal Even. Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems , journal =. 2006 , timestamp =

2006
[8]

Billingsley, Patrick , year =
[9]

, year =

Kechris, Alexander S. , year =
[10]

Anne Condon , title =. Inf. Comput. , volume =
[11]

Principles of Systems Design , series =

Rajeev Alur and Suguman Bansal and Osbert Bastani and Kishor Jothimurugan , title =. Principles of Systems Design , series =
[12]

Littman and Michael Carbin , title =

Cambridge Yang and Michael L. Littman and Michael Carbin , title =. CoRR , volume =
[13]

Puterman , title =

Martin L. Puterman , title =
[14]

Chandra and Dexter Kozen and Larry J

Ashok K. Chandra and Dexter Kozen and Larry J. Stockmeyer , title =. J
[15]

Yuri Gurevich and Leo Harrington , title =
[16]

Amir Pnueli , title =
[17]

Robotics: Science and Systems , year =

Jie Fu and Ufuk Topcu , title =. Robotics: Science and Systems , year =
[18]

Mateo Perez and Fabio Somenzi and Ashutosh Trivedi , title =
[19]

Lakshmivarahan and Kumpati S

S. Lakshmivarahan and Kumpati S. Narendra , title =. Math. Oper. Res. , volume =
[20]

Littman , title =

Michael L. Littman , title =
[21]

Brafman and Moshe Tennenholtz , title =

Ronen I. Brafman and Moshe Tennenholtz , title =
[22]

Min Wen and Ufuk Topcu , title =
[23]

Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm , booktitle =

Edon Kelmendi and Julia Kr. Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm , booktitle =
[24]

Tsitsiklis , title =

Shie Mannor and John N. Tsitsiklis , title =. J. Mach. Learn. Res. , volume =. 2004 , timestamp =

2004
[25]

Valiant , title =

Leslie G. Valiant , title =. Commun
[26]

Bertsekas and John N

Dimitri P. Bertsekas and John N. Tsitsiklis , title =. Math. Oper. Res. , volume =

[1] [1]

2019 , url =

Pranav Ashok and Jan Kret. 2019 , url =. doi:10.1007/978-3-030-25540-4\_29 , timestamp =

work page doi:10.1007/978-3-030-25540-4 2019

[2] [2]

2024 , timestamp =

Jakub Svoboda and Suguman Bansal and Krishnendu Chatterjee , title =. 2024 , timestamp =

2024

[3] [3]

The Complexity of Markov Equilibrium in Stochastic Games , booktitle =

Constantinos Daskalakis and Noah Golowich and Kaiqing Zhang , editor =. The Complexity of Markov Equilibrium in Stochastic Games , booktitle =. 2023 , timestamp =

2023

[4] [4]

Weichao Mao and Tamer Basar , title =. Dyn. Games Appl. , volume =. 2023 , url =. doi:10.1007/S13235-021-00420-0 , timestamp =

work page doi:10.1007/s13235-021-00420-0 2023

[5] [5]

The Tenth International Conference on Learning Representations,

Ziang Song and Song Mei and Yu Bai , title =. The Tenth International Conference on Learning Representations,. 2022 , url =

2022

[6] [6]

CoRR , volume =

Chi Jin and Qinghua Liu and Yuanhao Wang and Tiancheng Yu , title =. CoRR , volume =. 2021 , url =. 2110.14555 , timestamp =

Pith/arXiv arXiv 2021

[7] [7]

Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems , journal =

Eyal Even. Action Elimination and Stopping Conditions for the Multi-Armed Bandit and Reinforcement Learning Problems , journal =. 2006 , timestamp =

2006

[8] [8]

Billingsley, Patrick , year =

[9] [9]

, year =

Kechris, Alexander S. , year =

[10] [10]

Anne Condon , title =. Inf. Comput. , volume =

[11] [11]

Principles of Systems Design , series =

Rajeev Alur and Suguman Bansal and Osbert Bastani and Kishor Jothimurugan , title =. Principles of Systems Design , series =

[12] [12]

Littman and Michael Carbin , title =

Cambridge Yang and Michael L. Littman and Michael Carbin , title =. CoRR , volume =

[13] [13]

Puterman , title =

Martin L. Puterman , title =

[14] [14]

Chandra and Dexter Kozen and Larry J

Ashok K. Chandra and Dexter Kozen and Larry J. Stockmeyer , title =. J

[15] [15]

Yuri Gurevich and Leo Harrington , title =

[16] [16]

Amir Pnueli , title =

[17] [17]

Robotics: Science and Systems , year =

Jie Fu and Ufuk Topcu , title =. Robotics: Science and Systems , year =

[18] [18]

Mateo Perez and Fabio Somenzi and Ashutosh Trivedi , title =

[19] [19]

Lakshmivarahan and Kumpati S

S. Lakshmivarahan and Kumpati S. Narendra , title =. Math. Oper. Res. , volume =

[20] [20]

Littman , title =

Michael L. Littman , title =

[21] [21]

Brafman and Moshe Tennenholtz , title =

Ronen I. Brafman and Moshe Tennenholtz , title =

[22] [22]

Min Wen and Ufuk Topcu , title =

[23] [23]

Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm , booktitle =

Edon Kelmendi and Julia Kr. Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm , booktitle =

[24] [24]

Tsitsiklis , title =

Shie Mannor and John N. Tsitsiklis , title =. J. Mach. Learn. Res. , volume =. 2004 , timestamp =

2004

[25] [25]

Valiant , title =

Leslie G. Valiant , title =. Commun

[26] [26]

Bertsekas and John N

Dimitri P. Bertsekas and John N. Tsitsiklis , title =. Math. Oper. Res. , volume =