Pith. sign in

REVIEW 3 major objections 10 minor 22 references

Improved subexponential analysis of the Random-Action-Removal algorithm for 2-player turn-based games and non-binary AUSOs

T0 review · 3 major / 10 minor · reviewed 2026-07-08 · glm-5.2

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

Pith's one-line read Tighter bound for game-solving algorithm hits e^{O(√n)}

desk verdict Solid improvement to the best known bound for Random-Action-Removal on 2-TBSGs. The proof checks out. read the letter →

arxiv 2607.06334 v1 pith:JV6OEEJB submitted 2026-07-07 cs.DS

Uri Zwick This is my paper · ORCID
classification cs.DS
keywords algorithmgamesrandom-action-removalanalysismatouproblemssharirsqrt
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

This paper proves that the Random-Action-Removal algorithm, a simple randomized strategy-iteration method for solving 2-player turn-based stochastic games and finding sinks of non-binary AUSOs, runs in e^{O(√(n ln(m/n)))} expected time on games with n states and m actions. This improves the previous e^{O(√(n ln(m/√n)))} bound inherited from a 1992 analysis that treated these games as generic LP-type problems. The key insight is that games and AUSOs possess a hypercube structure: actions are partitioned by state, and every strategy picks exactly one action per state. This structure was ignored in prior analyses. Exploiting it yields a tighter bivariate recurrence relation that tracks how frozen states, states whose actions become irrelevant as the algorithm progresses, reduce the effective problem size during the second recursive call. Solving this new recurrence requires a discrete WKB method, an asymptotic technique from mathematical physics, because the standard generating-function approach used for the old recurrence does not apply. The resulting bound is especially significant when m = O(n), the natural sparse regime, where the running time drops from e^{O(√(n ln n))} to e^{O(√n)}, giving a smooth transition between binary and non-binary games. The same e^{O(√(n ln(m/n)))} bound was previously achievable only by a substantially more complicated algorithm with worse constant factors; this paper shows the simple, unmodified Random-Action-Removal algorithm already achieves it.

What carries the argument

The argument rests on three components: (1) the notion of frozen states, which explains why the second recursive call is effectively on a smaller AUSO; (2) a bivariate recurrence F(n,k) that captures this state reduction; and (3) a discrete WKB asymptotic analysis of that recurrence, using an ansatz U(n,k) = (n+k)e^{S(n,k)} where S satisfies the PDE (n+k)S_n S_k = 1, which in turn reduces to an ODE for Φ(α) that can be bounded rigorously.

What would settle it

Compute F(n,k) exactly for moderately large n and k with k > n (say n = 100, k = 500) and check whether F(n,k) exceeds U(n,k) = (n+k)e^{2√(nΦ(k/n))}. Alternatively, construct a specific family of AUSOs where the number of frozen states in the second recursive call is consistently smaller than the analysis assumes, which would make the actual expected path length larger than F(n,k).

Watch

Extended reading notes

Core claim

The central discovery is that the hypercube structure of games and AUSOs, specifically the partitioning of actions into states where each strategy selects exactly one action per state, can be exploited to derive a strictly tighter recurrence for the expected number of improvement steps. When the algorithm removes a random action and recurses, the second recursive call often starts from a vertex where several states are frozen, meaning the effective number of states drops from n to n-i for some i. This yields the recurrence F(n,k) = F(n,k-1) + (1/(n+k)) * sum of F(n-i,k), where k = m - 2n is the excess action count. The solution to this recurrence is bounded by U(n,k) = (n+k) * e^{2√(nΦ(k/n))

Load-bearing premise

The inductive proof that U(n,k) bounds F(n,k) works by showing that a certain quantity S_k is at most 1/√N (where N = n+k). This bound on S_k is derived from properties of the function Φ(α) and its differential equation. If S_k were to exceed 1/√N for some parameter values, the key inequality in the induction step would fail and the entire bounding argument would collapse.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 10 minor

Summary. This paper presents an improved analysis of the Random-Action-Removal algorithm for solving 2-player turn-based stochastic games (2-TBSGs) and, more generally, for finding the sink of an Acyclic Unique Sink Orientation (AUSO) of a non-binary hypercube. The algorithm, a recasting of the dual simplex algorithm of Matoušek, Sharir, and Welzl (MSW), was previously known to run in $e^{O(√{n ln(m/√n)})}$ time for games with $n$ states and $m$ actions. The author exploits the hypercube structure of games—specifically, the partition of actions into states—to derive a tighter bivariate recurrence relation (Definition 5.4). The key innovation is the 'frozen states' argument (Lemma 5.3), which shows that the second recursive call of the algorithm often operates on an AUSO with effectively fewer states. The resulting recurrence is then solved using a discrete WKB (Wentzel–Kramers–Brillouin) method: an ansatz $U(n,k) = (n+k)e^{2√{nΦ(k/n)}}$ is proposed, where $Φ(α)$ satisfies an ODE derived as the eikonal equation. The main theorem (Theorem 8.2) proves $F(n,k) ≤ U(n,k)$ by induction, reducing to the verification of inequality (11), which is established via concavity arguments and the bound $S_k ≤ 1/√N$. The final bound is $e^{O(√{n ln(m/n)})}$, improving the previous result and matching (with better constants) the bound of Hansen and Zwick (STOC 2015) obtained via a more complex algorithm.

Significance. The result is a genuine improvement over the state of the art for a natural and important class of games. The improvement from $e^{O(√{n ln(m/√n)})}$ to $e^{O(√{n ln(m/n)})}$ is especially notable when $m = O(n)$, where the bound drops from $e^{O(√{n ln n})}$ to $e^{O(√n)}$, providing a smooth transition from binary to non-binary games. The paper is commendably self-contained and transparent: the proof of Theorem 8.2 is fully rigorous and verifiable by hand, with all ODE existence/uniqueness/bounds deferred to Appendix J using standard techniques (Peano existence, one-sided Lipschitz, comparison principle). The discrete WKB technique applied to algorithm analysis is interesting in its own right and may find broader use. The author also discloses AI assistance (Gemini, ChatGPT) for heuristic derivation, but the final argument is traditional and checkable. The paper provides falsifiable numerical evidence (Figure 3) consistent with the theoretical bounds.

major comments (3)
  1. Theorem 8.2, inequality (7): The induction proof requires $F(n,k) ≤ U(n,k)$ for $k ≤ n$ as the base case, citing Lemma 7.1. However, Lemma 7.1 gives $F(n,k) ≤ e^{2√{n+k}}$, while $U(n,k) = (n+k)e^{2√{nΦ(k/n)}}$ with $Φ(α) = 1+α$ for $α ≤ 1$. This yields $U(n,k) = (n+k)e^{2√{n+k}}$ for $k ≤ n$. The factor $(n+k)$ makes $U(n,k)$ strictly larger than the Lemma 7.1 bound, so the base case does hold. However, the text on p.10 states 'For $k ≤ n$ we already know that the inequality holds, even without the multiplicative $n+k$ factor.' This is correct but the logical flow could be clearer: the reader needs to verify that $e^{2√{n+k}} ≤ (n+k)e^{2√{n+k}}$, which is trivial but should be stated explicitly for completeness of the induction base.
  2. Section 5, Lemma 5.5, proof: The recurrence (1) sums $F(n-i, k)$ for $i = 1, ..., n$, but in inequality (7) of Theorem 8.2 the sum is $U(j, k)$ for $j = 0, ..., n-1$. These are equivalent under the substitution $j = n - i$, but the indices in the recurrence (1) as stated sum from $i=1$ to $n$, which includes $F(0, k) = 1$. In inequality (7), the sum is $j=0$ to $n-1$, which also includes $U(0, k)$. This is consistent, but the notation switch between $F(n-i, k)$ and $U(j, k)$ could briefly be flagged to avoid confusion.
  3. Appendix J.1: The comparison principle argument for $Φ(α) ≥ g(α) = 4α/(1+α)$ checks that $g'(α) ≤ f(α, g(α))$. The computation shows $g'(α) = (2/(1+α))^2 = 4/(1+α)^2$ and $f(α, g(α)) = g(α)/(2α) = 2/(1+α)$. The claim that $4/(1+α)^2 ≤ 2/(1+α)$ for $α ≥ 1$ is correct (it reduces to $2 ≤ 1+α$). This is fine, but the intermediate step $f(α, g(α)) = g(α)/(2α)$ should be briefly justified: when $Φ = g(α) = 4α/(1+α)$, the discriminant $Φ^2 - 4αΦ/(1+α) = 0$, so $f(α, g(α)) = g(α)/(2α)$. This is implicit but worth making explicit.
minor comments (10)
  1. Title and Abstract: 'theRandom-Action-Removal' — missing space after 'the' in the title line of the full text.
  2. p.3, 'reachs' should be 'reaches'.
  3. p.6, 'perfored' should be 'performed' (appears twice: once in the Section 8 heading and once in Theorem 8.2 statement).
  4. p.9, equation (4): The expression $e^{2q nΦ(k/n)}$ uses 'q' for the square root symbol. This appears to be a rendering issue but should be checked in the source.
  5. p.9, Lemma 8.1: The bound is stated as $Φ(α) ≤ 2 + ℓ + ln(ℓ+1)$ where $ℓ = ln((1+α)/2)$. The abstract and introduction claim $e^{O(√{n ln(m/n)})}$. The connection between $Φ(α) = O(ln α)$ and the final $O(√{n ln(m/n)})$ bound is made implicitly. A one-line remark after Lemma 8.1 or after Theorem 8.2 explicitly stating 'Since $Φ(k/n) = O(ln(k/n)) = O(ln(m/n))$, the bound is $e^{O(√{n ln(m/n)})}$' would improve readability.
  6. Figure 3 caption: 'numerical 100( )' appears garbled. Should read something like 'numerical $Φ̃_{100}(α)$' or similar.
  7. Appendix I, p.22: The heuristic derivation mentions $U(n,k-1)/U(n,k) ≈ e^{-S_k} ≈ 1 - S_k$, but the rigorous proof in Section 8 uses the mean value theorem and concavity to get $(1-1/N)e^{-S_k}$. The transition from heuristic to rigorous could note that the $(n+k)$ prefactor is introduced precisely to supply the $(1-1/N)$ factor.
  8. References: The citation [GJR08] is listed as 'Gärtner, Morris, and Rüst' in the text but the bibliographic entry uses 'Morris Jr.' — minor inconsistency.
  9. p.5, Section 3: 'Apositional strategy' should be 'A positional strategy'.
  10. p.12, proof of Theorem 8.2: 'it is enough to show' appears twice in close succession (once for inequality (12), once for $S_k ≤ 1/√N$). Slight rewording could improve flow.

Simulated Author's Rebuttal

3 responses · 0 unresolved

We thank the referee for a careful reading and for three constructive comments, all of which request minor clarifications that we are happy to incorporate. All three points concern presentation rather than correctness.

read point-by-point responses

  1. Referee: Theorem 8.2, inequality (7): The induction proof requires F(n,k) ≤ U(n,k) for k ≤ n as the base case, citing Lemma 7.1. However, Lemma 7.1 gives F(n,k) ≤ e^{2√(n+k)}, while U(n,k) = (n+k)e^{2√(nΦ(k/n)}} with Φ(α) = 1+α for α ≤ 1. This yields U(n,k) = (n+k)e^{2√(n+k}} for k ≤ n. The factor (n+k) makes U(n,k) strictly larger than the Lemma 7.1 bound, so the base case does hold. However, the text on p.10 states 'For k ≤ n we already know that the inequality holds, even without the multiplicative n+k factor.' This is correct but the logical flow could be clearer: the reader needs to verify that e^{2√(n+k}} ≤ (n+k)e^{2√(n+k}}, which is trivial but should be stated explicitly for completeness of the induction base.

    Authors: The referee is correct that the base case verification, while trivial, should be stated explicitly. We will revise the text on p.10 to spell out the chain of inequalities: by Lemma 7.1, F(n,k) ≤ e^{2√(n+k)}; for k ≤ n (i.e., α = k/n ≤ 1), we have Φ(α) = 1+α, so U(n,k) = (n+k)e^{2√(n+k)}; since n+k ≥ 1, we have e^{2√(n+k)} ≤ (n+k)e^{2√(n+k)} = U(n,k), and hence F(n,k) ≤ U(n,k). This makes the induction base fully explicit. revision: yes

  2. Referee: Section 5, Lemma 5.5, proof: The recurrence (1) sums F(n-i, k) for i = 1, ..., n, but in inequality (7) of Theorem 8.2 the sum is U(j, k) for j = 0, ..., n-1. These are equivalent under the substitution j = n - i, but the indices in the recurrence (1) as stated sum from i=1 to n, which includes F(0, k) = 1. In inequality (7), the sum is j=0 to n-1, which also includes U(0, k). This is consistent, but the notation switch between F(n-i, k) and U(j, k) could briefly be flagged to avoid confusion.

    Authors: We agree that the change of summation index between recurrence (1) (written as a sum over i = 1, ..., n of F(n-i, k)) and inequality (7) (written as a sum over j = 0, ..., n-1 of U(j, k)) could cause confusion. We will add a brief remark at the point where inequality (7) is introduced, noting that the substitution j = n-i converts the sum in recurrence (1) into the form used in (7), and that the two formulations are equivalent. revision: yes

  3. Referee: Appendix J.1: The comparison principle argument for Φ(α) ≥ g(α) = 4α/(1+α) checks that g'(α) ≤ f(α, g(α)). The computation shows g'(α) = (2/(1+α))^2 = 4/(1+α)^2 and f(α, g(α)) = g(α)/(2α) = 2/(1+α). The claim that 4/(1+α)^2 ≤ 2/(1+α) for α ≥ 1 is correct (it reduces to 2 ≤ 1+α). This is fine, but the intermediate step f(α, g(α)) = g(α)/(2α) should be briefly justified: when Φ = g(α) = 4α/(1+α), the discriminant Φ^2 - 4αΦ/(1+α) = 0, so f(α, g(α)) = g(α)/(2α). This is implicit but worth making explicit.

    Authors: The referee's observation is correct. When Φ = g(α) = 4α/(1+α), the discriminant under the square root in equation (6) becomes Φ² - 4αΦ/(1+α) = (4α/(1+α))² - 4α·(4α/(1+α))/(1+α) = 16α²/(1+α)² - 16α²/(1+α)² = 0, so the square root vanishes and f(α, g(α)) = g(α)/(2α). We will add this one-line justification to Appendix J.1. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity found

full rationale

The paper's central derivation chain is self-contained. The recurrence relation (Definition 5.4) is derived from first principles via Lemma 5.3, which exploits the hypercube structure of AUSOs to show that frozen states reduce the effective problem size. The ansatz U(n,k) = (n+k)e^{2√(nΦ(k/n))} is introduced as a candidate upper bound, not fitted to the target result. The ODE (5) for Φ(α) is derived from the PDE (n+k)S_n S_k = 1 (Lemma 8.4), which itself follows algebraically from the definitions of S_n and S_k via the chain rule (Lemma 8.3). The key inequality S_k ≤ 1/√N, which closes the induction in Theorem 8.2, is proven using the standard inequality √x - √(x-c) ≤ √c for x ≥ c, with the condition Φ ≥ 4α/(1+α) established in Appendix J via the comparison principle for ODEs. The bound Φ(α) ≤ 2 + ℓ + ln(ℓ+1) is proven rigorously in Appendix J.2 by showing B'(α) ≥ f(α, B(α)) through explicit calculation. While the paper cites Hansen and Zwick [HZ15] for a related but different algorithm, the present analysis does not depend on that result for its correctness. The paper also cites Gärtner [Gär02] for the binary case (k=0), but extends that analysis independently. No step in the derivation chain reduces to its inputs by construction, and no self-citation is load-bearing for the central proof. The AI disclosure notes that Gemini and ChatGPT assisted with Section 8 and Appendices I-L, but the authors state all content was verified by traditional methods, and the proofs as written are self-contained and checkable without computational tools. The derivation is genuinely self-contained against external benchmarks (the exact values of F(n,k) in Figure 2 serve as numerical verification).

Assumptions & free parameters 0 free parameters · 3 assumptions · 1 invented entities

The axiom ledger is minimal. The core derivation relies on standard mathematical properties of the games (hypercube structure) and the recurrence relation. The main 'invented' object is the function Φ(α), which is defined implicitly by a differential equation and whose properties are rigorously derived, not postulated. The ansatz for the solution form is standard for WKB analysis.

assumptions (3)
  • domain assumption Games and AUSOs have a hypercube structure where each action belongs to a specific state and each strategy uses exactly one action per state.
    This is the key structural property exploited in Section 5 to derive the improved recurrence relation. It is a standard property of the games considered.
  • standard math The function S(n,k) = 2√(nΦ(k/n) is concave in n and k when 0 < n < k.
    Proven in Lemma 8.5 and Appendix L, this property is used to bound the sum in inequality (8) via the tangent line.
  • ad hoc to paper The solution to the recurrence F(n,k) has the asymptotic form e^{S(n,k)}.
    This ansatz, justified heuristically in Appendix I and numerically in Figure 3, is the basis for the WKB method used in Section 8.
invented entities (1)
  • Function Φ(α) independent evidence
    purpose: Defines the asymptotic behavior of the upper bound U(n,k) via the differential equation α(Φ')² - ΦΦ' + Φ/(1+α) = 0.
    While introduced to bound the recurrence, its properties are rigorously proven in Appendix J, including existence, uniqueness, and upper/lower bounds, making it a well-defined mathematical object rather than a postulated physical entity.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improved subexponential analysis of the Random-Action-Removal algorithm for 2-player turn-based games and non-binary AUSOs." pith.science (2026). https://pith.science/paper/JV6OEEJB

@misc{pith2026260706334,
  author       = {Pith},
  title        = {Pith review of: Improved subexponential analysis of the Random-Action-Removal algorithm for 2-player turn-based games and non-binary AUSOs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JV6OEEJB}},
  note         = {Machine review of arXiv:2607.06334}
}
abstract

We give a concise description and an improved analysis of the Random-Action-Removal algorithm for solving 2-player, 0-sum, turn-based, possibly infinite duration, stochastic or non-stochastic games played on graphs, or on finite sets of states. More generally, the algorithm can be used to find the sink of an Acyclic Unique Sink Orientation (AUSO) of a non-binary hypercube. The families of games that can be solved by the algorithm include discounted and non-discounted stochastic games (SGs) and Mean Payoff Games (MPGs). The obtained algorithm is the fastest known randomized algorithm for solving such games, slightly improving on a much more complicated algorithm of Hansen and Zwick (STOC 2015). The Random-Action-Removal algorithm is an adaptation of the Random-Facet algorithm used to solve linear programming (LP) problems, or, more generally, LP-type problems. Two dual variants of the Random-Facet algorithm were developed independently by Kalai (STOC 1992) and by Matou{\v{s}}ek, Sharir and Welzl (SoCG 1992). For LP problems, the algorithm of Kalai is a primal \emph{simplex} algorithm, while the algorithm of Matou{\v{s}}ek, Sharir and Welzl is a dual \emph{simplex} algorithm. The Random-Action-Removal algorithm for games or AUSOs is an adaptation of the dual algorithm of Matou{\v{s}}ek, Sharir and Welzl, and is a randomized \emph{strategy iteration} algorithm. Our improved analysis shows that the Random-Action-Removal algorithm solves games with~$n$ states and $m\ge 2n$ actions in $e^{O(\sqrt{n\ln(m/n)})}$ time. This improves on a previous $e^{O(\sqrt{n\ln(m/\sqrt n)})}$ bound for the algorithm that follows from the analysis of Matou{\v{s}}ek, Sharir and Welzl (SoCG 1992). An $e^{O(\sqrt{n\ln(m/n)})}$ bound, with worse constant factors, was previously obtained using a much more complicated algorithm for solving LP and LP-type problems of Hansen and Zwick (STOC 2015).

Figures

Figures reproduced from arXiv: 2607.06334 by the authors.

Figure 1
Figure 1. Pseudocode of the Random-Action-Removal algorithm. 0 1 2 3 4 5 6 7 8 0 1 1 1 1 1 1 1 1 1 1 2 5 2 17 6 37 12 197 60 69 20 503 140 1041 280 9649 2520 2 7 2 14 3 45 8 773 120 322 45 9817 1260 84323 10080 4267 480 472373 50400 3 17 3 185 24 48 5 545 48 65461 5040 24391 1680 206819 12960 15711797 907200 185713321 9979200 4 209 24 713 60 10843 720 45827 2520 24467 1152 1255151 51840 49176893 1814400 597058757 19958400 390… view at source ↗
Figure 2
Figure 2. The values of F(n, k) for 0 ≤ n ≤ 4 and 0 ≤ k ≤ 8 in exact and approximate forms. 19 [PITH_FULL_IMAGE:figures/full_fig_p019_2.png] view at source ↗
Figure 3
Figure 3. A plot of Φ(α) and related functions. J.3 Lower bound on Φ(α) Let L(α) = 2 + ℓ + ln(1 + ℓ) −  ℓ ℓ + 13 = 2 + ln 1 + α 2 + ln  1 + ln 1 + α 2  − [PITH_FULL_IMAGE:figures/full_fig_p025_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 22 canonical work pages

  1. [1]

    Optim.24.4 (2014), pp

    [ABGJ14] Xavier Allamigeon, Pascal Benchimol, Stéphane Gaubert, and Michael Joswig.Combina- torial Simplex Algorithms Can Solve Mean Payoff Games.SIAM J. Optim.24.4 (2014), pp. 2096–2117.doi:10.1137/140953800. [ACDG13] Marianne Akian, Jean Cochet-Terrasson, Sylvie Detournay, and Stéphane Gaubert.Solv- ing multichain stochastic games with mean payoff by po...

    work page doi:10.1137/140953800 2014

  2. [2]

    1834– 1841.doi:10.1109/CDC.2013.6760149

    IEEE, 2013, pp. 1834– 1841.doi:10.1109/CDC.2013.6760149. [AG11] Krzysztof R. Apt and Erich Grädel.Lectures in game theory for computer scientists. Cambridge University Press,

    work page doi:10.1109/cdc.2013.6760149 2013

  3. [3]

    Guterman.Tropical Polyhedra are Equivalent to mean Payoff Games.Int

    [AGG12] Marianne Akian, Stéphane Gaubert, and Alexander E. Guterman.Tropical Polyhedra are Equivalent to mean Payoff Games.Int. J. Algebra Comput.22.1 (2012).doi:10. 1142/S0218196711006674. [AGS18] Xavier Allamigeon, Stéphane Gaubert, and Mateusz Skomra.Solving generic nonar- chimedean semidefinite programs using stochastic game algorithms.J. Symb. Comput...

    work page doi:10.1016/j.jsc.2017.07.002 2012

  4. [4]

    FSTTCS.2021.24,doi:10.4230/LIPIcs.FSTTCS.2021.24

    LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, 12:1–12:22.doi:10.4230/LIPIcs. MFCS.2021.12. [Apo69] Tom M. Apostol.Calculus, Volume II: Multi-Variable Calculus and Linear Algebra with Applications. 2nd. New York: John Wiley & Sons,

    work page doi:10.4230/lipics 2021

  5. [5]

    97–118.doi:10.1007/s10703-010-0105-x

    [BCD+11] Luboš Brim, Jakub Chaloupka, Laurent Doyen, Raffaella Gentilini, and Jean-François Raskin.Faster algorithms for mean-payoff games.Formal Methods in System Design38.2 (2011), pp. 97–118.doi:10.1007/s10703-010-0105-x. [Bel57] Richard E. Bellman.A Markovian decision process.Journal of Mathematics and Me- chanics6.5 (1957), pp. 679–684.doi:10.1512/iu...

    work page doi:10.1007/s10703-010-0105-x 2011

  6. [6]

    Bender and Steven A

    [BO99] Carl M. Bender and Steven A. Orszag.Advanced Mathematical Methods for Scientists and Engineers I: Asymptotic Methods and Perturbation Theory. New York: Springer, 1999.doi:10.1007/978-1-4757-3069-2. [BV05] Henrik Björklund and Sergei Vorobyov.Combinatorial structure and randomized subex- ponential algorithms for infinite games.Theoretical Computer S...

    work page doi:10.1007/978-1-4757-3069-2 1999

  7. [7]

    2333–2349.doi:10.1137/ 1.9781611975482.142

    SIAM, 2019, pp. 2333–2349.doi:10.1137/ 1.9781611975482.142. [CFGO22] Thomas Colcombet, Nathanaël Fijalkow, Paweł Gawrychowski, and Pierre Ohlmann. The Theory of Universal Graphs for Infinite Duration Games.Log. Methods Comput. Sci.18.3 (2022).doi:10.46298/lmcs-18(3:29)2022. [CJK+22] Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank ...

    work page doi:10.46298/lmcs-18(3:29)2022 2019

  8. [8]

    Allen Emerson and Charanjit S

    [EJ91] E. Allen Emerson and Charanjit S. Jutla.Tree automata,µ-calculus and determinacy. In:Proceedings of the 32nd FOCS. IEEE Computer Society Press, 1991, pp. 368–377. doi:10.1109/SFCS.1991.185392. [EJS93] E. Allen Emerson, Charanjit S. Jutla, and A. Prasad Sistla.On model-checking for fragments ofµ-calculus. In:International Conference on Computer Aide...

    work page doi:10.1109/sfcs.1991.185392 1991

Show all 22 references
  1. [9]

    Princeton, NJ: Princeton University Press, 1957, pp

    Annals of Mathematics Studies. Princeton, NJ: Princeton University Press, 1957, pp. 67–78. [FBB+25] Nathanaël Fijalkow, Nathalie Bertrand, Patricia Bouyer-Decitre, Romain Brenguier, Ar- naud Carayol, John Fearnley, Hugo Gimbert, Florian Horn, Rasmus Ibsen-Jensen, Nico- las Mar...

    1957

  2. [10]

    [Fea10] John Fearnley.Exponential Lower Bounds for Policy Iteration. In:Proc. of 37th ICALP. 2010, pp. 551–562.doi:10.1007/978-3-642-14162-1_46. [FGO20] Nathanaël Fijalkow, Paweł Gawrychowski, and Pierre Ohlmann.Value Iteration Using Universal Graphs and the Complexity of Mean...

    2010 doi

  3. [11]

    Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, 34:1–34:15.doi:10

    LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, 34:1–34:15.doi:10. 4230/LIPIcs.MFCS.2020.34. 29 [FJK+19] John Fearnley, Sanjay Jain, Bart de Keijzer, Sven Schewe, Frank Stephan, and Dominik Wojtczak.An ordered approach to solving parity games in quasi-polynomi...

    2020 doi

  4. [12]

    Randomized Optimization by Simplex Type Methods

    [FW88] Colin L. Frenzen and Roderick Wong.Uniform Asymptotic Expansions of Laguerre Poly- nomials.SIAM Journal on Mathematical Analysis19.5 (1988), pp. 1232–1248.doi:10. 1137/0519087. [Gär02] Bernd Gärtner.The Random-Facet simplex algorithm on combinatorial cubes.Random Struct...

    1988 doi

  5. [13]

    [Gil57] DeanGillette.Stochastic games with zero stop probability.In:Contributions to the Theory of Games, Volume III

    [GI17] Hugo Gimbert and Rasmus Ibsen-Jensen.A short proof of correctness of the quasi- polynomial time algorithm for parity games.CoRRabs/1702.01953 (2017).url:http: //arxiv.org/abs/1702.01953. [Gil57] DeanGillette.Stochastic games with zero stop probability.In:Contributions t...

    2017 arXiv

  6. [14]

    Princeton, NJ: Princeton University Press, 1957, pp

    Annals of Mathematics Studies. Princeton, NJ: Princeton University Press, 1957, pp. 179–187. [GJR08] Bernd Gärtner, Walter D. Morris Jr., and Leo Rüst.Unique Sink Orientations of Grids. Algorithmica51.2 (2008), pp. 200–235.doi:10.1007/s00453-007-9090-x. [GKK88] Vladimir A. Gur...

    1957 doi

  7. [15]

    Springer, 2002.doi:10.1007/3- 540-36387-4

    LNCS. Springer, 2002.doi:10.1007/3- 540-36387-4. [Hal07] Nir Halman.Simple Stochastic Games, Parity Games, Mean Payoff Games and Dis- counted Payoff Games Are All LP-Type Problems.Algorithmica49.1 (2007), pp. 37–50. doi:10.1007/S00453-007-0175-3. [HMZ13] Thomas Dueholm Hansen,...

    2002 doi

  8. [16]

    209–218.doi: 10.1145/2746539.2746557

    ACM, 2015, pp. 209–218.doi: 10.1145/2746539.2746557. [JL17] Marcin Jurdziński and Ranko Lazić.Succinct progress measures for solving parity games. In:Proc. of 32nd LICS. 2017, pp. 1–9.doi:10.1109/LICS.2017.8005092. [Kal92a] Gil Kalai.A Subexponential Randomized Simplex Algorit...

    2015 doi

  9. [17]

    639–648.doi:10

    ACM, 2018, pp. 639–648.doi:10. 1145/3209108.3209115. [LL69] Thomas M. Liggett and Steven A. Lippman.Stochastic Games with Perfect Informa- tion and Time Average Payoff.SIAM Review11.4 (1969), pp. 604–607.doi:10.1137/ 1011093. [LP81] Vladimir Lifschitz and Boris Pittel.The numb...

    2018 doi

  10. [18]

    [SB18] Richard S

    [Put94] MartinL.Puterman.Markov decision processes.Wiley,1994.doi:10.1002/9780470316887. [SB18] Richard S. Sutton and Andrew G. Barto.Reinforcement Learning: An Introduction. 2nd ed. Cambridge, MA: MIT Press,

    1994 doi

  11. [19]

    31 [Sch16] Bruno Scherrer.Improved and Generalized Upper Bounds on the Complexity of Policy Iteration.Math. Oper. Res.41.3 (2016), pp. 758–774.doi:10.1287/moor.2015.0753. [Sha53] Lloyd S. Shapley.Stochastic Games.Proceedings of the National Academy of Sciences U.S.A.39 (1953),...

    2016 doi

  12. [20]

    [SW01] Tibor Szabó and Emo Welzl.Unique Sink Orientations of Cubes

    Cambridge University Press, 2022.doi:10.1017/9781009029704. [SW01] Tibor Szabó and Emo Welzl.Unique Sink Orientations of Cubes. In:Proc. of 42th FOCS. 2001, pp. 547–555.doi:10.1109/SFCS.2001.959931. [Tes12] Gerald Teschl.Ordinary Differential Equations and Dynamical Systems. Vol

    2022 doi

  13. [21]

    [Wal98] Wolfgang Walter.Ordinary Differential Equations

    doi:10.1090/gsm/140. [Wal98] Wolfgang Walter.Ordinary Differential Equations. Vol

    doi

  14. [22]

    New York, NY: Springer, 1998.doi:10.1007/978-1-4612-0601-9

    Graduate Texts in Mathe- matics. New York, NY: Springer, 1998.doi:10.1007/978-1-4612-0601-9. [Wil88] Kathy Williamson Hoke.Completely unimodal numberings of a simple polytope.Discrete Applied Mathematics20.1 (1988), pp. 69–81.doi:10.1016/0166-218X(88)90042-X. [Ye05] Yinyu Ye.A...

    1998 doi

Pith tools

Reviewed July 8, 2026 · model on record in the stance chip above.