Pith. sign in

REVIEW 3 major objections 3 minor 38 references

Limit-sure reachability for small memory policies in POMDPs is NP-complete

T0 review · 3 major / 3 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read Determining whether a POMDP can reach its target with probability arbitrarily close to 1 under a memoryless or small-memory policy is NP-complete.

desk verdict Solid new NP-completeness result for limit-sure reachability under small-memory POMDP policies; the core upper-bound witness argument in Lemma 6 needs repair before the result is fully proved. read the letter →

arxiv 2412.00941 v2 pith:SHEUIEQX submitted 2024-12-01 cs.CC

Ali Asadi , Krishnendu Chatterjee , Raimundo Saona , Ali Shafiee This is my paper · ORCID
classification cs.CC MSC 68Q1768Q2590C40
keywords POMDPlimit-surewinningmemorylesspoliciesreachabilityNP-completenessrankPuiseuxfunctionsparityobjectives
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 settles the computational complexity of limit-sure reachability in partially observable Markov decision processes (POMDPs) under memoryless and constant-memory policies: the problem is NP-complete. The authors show that, unlike almost-sure winning, the limit-sure property is witnessed not by a single policy but by a sequence of policies whose probabilities concentrate on higher-rank actions as the allowed error tends to zero. They prove that every limit-sure winning blind MDP admits a rank policy witness of polynomial size, and that such a witness can be verified in polynomial time, giving the NP upper bound. The NP-hardness comes from a reduction from 3-SAT. If correct, this closes the complexity gap between almost-sure (NP-complete) and limit-sure problems for small-memory policies.

What carries the argument

The argument is carried by rank policies and the graph of communicating classes of the induced Puiseux Markov chain. A rank policy assigns each action a rank i(a) and plays it with probability proportional to $epsilon^{{i(a)}}$; the graph of communicating classes has one vertex per communicating class of the epsilon-parameterized Markov chain and edges recording which classes are reachable in the limit as epsilon goes to zero. The graph's structure—in particular whether every reachable absorbing communicating class other than the target has a nonempty exit distribution—characterizes limit-sure reachability (Lemma 5). The NP upper bound follows because the ranks can be chosen as polynomial-size integers and verified in polynomial time using minimum directed spanning tree computations.

What would settle it

Exhibit a blind MDP for which the minimal rank policy witness requires integer ranks whose binary representation is super-polynomial in the number of states. If such an MDP exists, the polynomial-size witness claim (Lemma 6) is false and the NP upper bound does not hold. Alternatively, search for a limit-sure winning blind MDP whose rank policy must use a number of distinct ranks exponential in the state count; its existence would also refute the proof.

Watch

Extended reading notes

Core claim

The central discovery is that limit-sure reachability under memoryless policies in POMDPs is neither polynomial-time solvable nor undecidable; it is NP-complete. The key technical insight is the introduction of rank policies: memoryless policies in which each action is assigned a non-negative integer rank and is played with probability proportional to epsilon raised to that rank. As epsilon tends to zero, lower-rank actions receive higher probability, and if low-rank actions form a cycle, higher-rank actions determine the exit distribution from that cycle. The paper proves that any limit-sure winning blind MDP admits a rank policy witness whose ranks are integers of polynomial bit size, and that the witness property can be checked in polynomial time. This stands in contrast to almost-sure winning, where uniform randomization over the support of a policy suffices, and to the general limit-sure problem, which is undecidable.

Load-bearing premise

The NP membership proof assumes that every limit-sure winning blind MDP has a rank policy witness with integer ranks of polynomial bit size; if some instance requires exponentially large ranks, the guessed witness would be too long and the NP upper bound collapses.

Editorial extensions

If this is right

  • Limit-sure winning under memoryless policies is decidable in NP, in contrast with the undecidability of the general limit-sure problem for unrestricted policies.
  • Constant-memory policies do not change the complexity: the problem remains NP-complete for any memory bound that is polynomial in the size of the POMDP.
  • The NP-completeness extends to parity (omega-regular) objectives under constant memory, since recurrent classes of a Markov chain satisfy parity with probability either 0 or 1.
  • Limit-sure winning and almost-sure winning have the same complexity for small-memory policies but require different witnesses: rank policies rather than uniform supports of actions.
  • The polynomial-size rank witness characterization gives a concrete target for encoding the problem into SAT or mixed-integer linear programming solvers.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • If the polynomial-size rank witness lemma is correct, a practical consequence follows: limit-sure reachability for small-memory POMDPs can be encoded into SAT or mixed-integer programming, enabling solver-based synthesis of controllers that achieve the target with arbitrary precision.
  • The gap between NP-completeness for small memory and undecidability for general policies suggests that any hardness for general policies must come from unbounded memory; this may transfer to other objectives such as mean-payoff or total reward.
  • A testable extension is that the rank-policy witness characterization may give a sound and complete abstraction for parametric Markov chains, complementing the known NP results for almost-sure reachability in that setting.
  • The distinction between limit-sure and almost-sure witnesses hints that approximation schemes for POMDPs may need to reason about asymptotic action probabilities, not just supports, which could inform the design of heuristics for planning under partial observability.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 3 minor

Summary. The paper studies limit-sure reachability in partially observable Markov decision processes (POMDPs) under memoryless and, more generally, constant-memory policies. The main claimed result, Theorem 1, is that deciding whether a POMDP with a reachability objective is limit-sure winning under memoryless policies is NP-complete; Corollaries 2 and 3 extend this to constant-memory policies and parity objectives. The upper bound is developed through a sequence of reductions: Lemma 1 reduces POMDPs to blind MDPs, Lemma 2 uses Tarski-Seidenberg to obtain Puiseux-function policy witnesses, Lemmas 3–5 characterize limit-sure winning in the induced Puiseux Markov chains via communicating classes, Lemma 6 asserts the existence of polynomial-size integer-rank policy witnesses, and Lemma 7 provides a polynomial-time verifier for such witnesses. The lower bound is an explicit reduction from 3-SAT (Proposition 1). The paper closes with extensions to parity objectives and parametric Markov chains.

Significance. If the proof is completed, the result is significant: it settles the complexity of limit-sure reachability for the practically important class of small-memory POMDP policies, complementing the EXPTIME-completeness of almost-sure winning and the undecidability of general limit-sure winning. The high-level strategy is interesting and plausible, and the 3-SAT lower-bound construction appears solid. The paper also deserves credit for a clear presentation of the rank-policy concept and for explicitly separating the lower and upper bounds. However, the NP upper bound as printed rests on Lemma 6, whose proof contains a load-bearing gap: the passage from arbitrary Puiseux policies to integer-rank policies is asserted rather than proved, and the polynomial-size certificate claim is not established because the characterizing inequality system may have exponentially many constraints. A second gap occurs in Lemma 1's converse direction. These issues are local and appear fixable, but they must be repaired before the central claim can be accepted.

major comments (3)
  1. [§3.2, Lemma 6] The step in which an arbitrary Puiseux policy σ is replaced, 'without loss of generality', by a rank policy of the form σ(ε)(a) = ε^{i(a)} / Σ_b ε^{i(b)} is not proved. The displayed definition of i(a), namely i(a) := inf{ r ≥ 0 : lim_{ε→0+} (Σ_a σ(ε)(a)δ(s,a)(s̃))/ε^r }, is ill-formed: the left-hand side does not depend on s and s̃ while the right-hand side does, and the sum over a makes the right-hand side independent of a. A genuine Puiseux policy can have leading exponents α_a ∈ Q and nonzero coefficients; the proof must show that after substituting ε ← ε^L for a common denominator L and dropping the coefficients, the communicating classes and exit-distribution supports are unchanged. This is load-bearing because the rank policy is exactly the NP certificate guessed in the upper bound.
  2. [§3.2, Lemma 6] The claim that the inequality system characterizing the graph of communicating classes has a polynomial-size solution is not established. The system is over the |A| variables (i(a))_{a∈A}, but it contains constraints for every pair of exit graphs of every communicating class; a communicating class B can have exponentially many exit graphs, so the finite system can be exponential. The proof does not show that a polynomial-size subsystem suffices to force the same graph, nor does it explain how Cramer's rule is applied to a system of polynomial size. Consequently, the 'moreover' part of Lemma 6 — that the rank policy description is of polynomial size — does not follow from the argument as written. Without this, Lemma 7 gives a verifier for a certificate whose existence has not been proved, and the NP upper bound is incomplete.
  3. [§3.2, Lemma 1] In the converse direction of the reduction from POMDPs to blind MDPs, the policy σ(z)(a) := σ'((a,z)) / Σ_{ã} σ'((ã,z)) is undefined when the denominator is zero. This case can occur even for observations that are reached with positive probability under σ': in the blind MDP, a state with observation z is then trapped by self-loops, whereas an arbitrary choice of σ(z) in the POMDP may advance the process. Defining an arbitrary distribution at such z does not by itself restore the coupling argument as printed. The value-equality statement may still be true — for example, one might perturb any limit-sure witness to give every observation positive mass and use a semicontinuity argument — but that argument is not supplied, and the reduction is the first step of the upper bound.
minor comments (3)
  1. [§3.2, Lemma 5] In the proof of the converse direction, the final displayed conclusion states that lim_{ε→0+} P(exit(C) < ∞) = 0, but the argument appears to establish the opposite: the probability of eventually exiting any non-target subset C should tend to 1, not 0. Please correct this sign or explain the intended event.
  2. [§3.2, Lemma 6] The selection defining i(s → s̃) is not fully specified: the proof says 'for some a ∈ I(s → s̃)' without stating whether this selection is part of the guessed witness or is existentially quantified in the inequality system. The subsequent constraints depend on this choice, so the definition should be made precise.
  3. [§1, Related works] There is a typo in 'this line of work doe not apply'; it should read 'does not apply'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is self-contained, anchored in external results (Tarski–Seidenberg, Solan, arborescence algorithms), with a self-contained NP-hardness reduction from 3-SAT.

full rationale

The central claim (Theorem 1) is proved by a chain that does not reduce to its own inputs. Lemma 2 transfers limit-sure reachability to a first-order sentence over the reals using the external Tarski–Seidenberg principle (Theorem 3) and the Puiseux real-closed field (Theorem 2, citing Bewley–Kohlberg). Lemmas 3–5 rest on Solan's externally cited results on Puiseux Markov chains (Theorems 5 and 6), not on the authors' own prior work. Lemma 6's rank-policy witness is not defined as a witness by construction: the rank policy is independently specified as integer-power action weights, and the proof argues from the existence of a Puiseux witness to a satisfied finite system of linear inequalities, then applies Cramer's rule to obtain an integer solution; whether the proof of polynomial size is fully rigorous is a correctness risk, not a circularity. Lemma 7 gives an independent polynomial-time verifier using spanning-tree algorithms [GGST86]. The hardness direction is supported by an explicit, self-contained reduction from 3-SAT in Section 3.3, so the citation to [CKS13] for a related NP-hardness result is not load-bearing. Self-citations such as [CCD16] and [CKS13] concern background or related problems, and the paper does not import a uniqueness theorem from the authors' own prior work to force its choice of rank policies. No fitted value is renamed as a prediction, no known result is repackaged as new, and no ansatz is smuggled in solely via self-citation. The manuscript's weaknesses (e.g., the undefined inverse mapping in Lemma 1 when an observation has zero probability, and the sketchy derivation of the polynomial-size rank witness in Lemma 6) are gaps or typos in proof presentation, not circular dependencies between the claimed result and its assumptions.

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

The central claim rests on standard external results: the real-closedness of Puiseux functions (Theorem 2), the Tarski-Seidenberg principle (Theorem 3), Solan's characterization of exit distributions in Puiseux Markov chains (Theorems 5 and 6), and the least-fixpoint characterization of reachability in Markov chains (Theorem 4). These are uncontroversial and are not outputs of this paper. The paper introduces one new proof construct, the rank policy, which is proven to exist if and only if a Puiseux policy witness exists; it has no independent empirical handle but is justified by the accompanying proofs. There are no free parameters fitted to data.

assumptions (5)
  • standard math The field of Puiseux functions is real-closed
    Quoted as Theorem 2 from [BK76]; used to apply the Tarski-Seidenberg transfer in Lemma 2.
  • standard math Tarski-Seidenberg principle for real-closed fields
    Quoted as Theorem 3 from [BPR06]; transfers first-order truth between R and Puiseux functions.
  • domain assumption Solan's theorems on exit distributions in Puiseux Markov chains
    Quoted as Theorems 5 and 6 from [Sol03]; load-bearing for the graph-of-communicating-classes characterization in Lemmas 3-5.
  • standard math Reachability value in a Markov chain is the least solution of the linear fixpoint equations
    Quoted as Theorem 4 from [BK08]; used in Lemma 2 to encode the reachability probability as a fixpoint condition.
  • standard math Kuhn's theorem on reduction of randomized strategies to mixtures of deterministic strategies
    Invoked in the 3-SAT reduction to argue it suffices to consider deterministic memoryless policies.
invented entities (1)
  • Rank policy
    purpose: A memoryless Puiseux policy in which each action a is played with probability proportional to ε^{i(a)} for integer ranks i(a); used as a polynomial-size witness for limit-sure reachability in blind MDPs.
    Introduced in Lemma 6 as a proof construct. It has no empirical falsifiable handle outside the paper; its existence is derived from the Puiseux policy witness.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Limit-sure reachability for small memory policies in POMDPs is NP-complete." pith.science (2026). https://pith.science/paper/SHEUIEQX

@misc{pith2026241200941,
  author       = {Pith},
  title        = {Pith review of: Limit-sure reachability for small memory policies in POMDPs is NP-complete},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SHEUIEQX}},
  note         = {Machine review of arXiv:2412.00941}
}
read the original abstract

A standard model that arises in several applications in sequential decision making is partially observable Markov decision processes (POMDPs) where a decision-making agent interacts with an uncertain environment. A basic objective in such POMDPs is the reachability objective, where given a target set of states, the goal is to eventually arrive at one of them. The limit-sure problem asks whether reachability can be ensured with probability arbitrarily close to 1. In general, the limit-sure reachability problem for POMDPs is undecidable. However, in many practical cases the most relevant question is the existence of policies with a small amount of memory. In this work, we study the limit-sure reachability problem for POMDPs with a fixed amount of memory. We establish that the computational complexity of the problem is NP-complete.

Figures

Figures reproduced from arXiv: 2412.00941 by the authors.

Figure 1
Figure 1. Example of POMDP that is limit-sure winning but not almost-sure [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. Graph of communicating classes induced by the Puiseux strategy [PITH_FULL_IMAGE:figures/full_fig_p014_2.png] view at source ↗
Figure 3
Figure 3. Example of the reduction from 3-SAT to the limit-sure winning reacha [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

38 extracted references · 37 canonical work pages

  1. [1]

    Robert J . Aumann. Mixed and Behavior Strategies in Infinite Extensive Games . In Advances in Game Theory . ( AM-52 ) , pages 627--650. Princeton University Press, 1964

    work page 1964

  2. [2]

    A Markovian Decision Process

    Richard Bellman. A Markovian Decision Process . Journal of Mathematics and Mechanics , 6(5):679--684, 1957

    work page 1957

  3. [3]

    Bertsekas

    Dimitri P. Bertsekas. Dynamic Programming and Stochastic Control . Number v. 125 in Mathematics in Science and Engineering. Academic Press, New York, 1976

    work page 1976

  4. [4]

    Probabilistic -automata

    Christel Baier, Marcus Gr \"o sser, and Nathalie Bertrand. Probabilistic -automata. Journal of the ACM , 59(1):1--52, February 2012

    work page 2012

  5. [5]

    Probability and Measure

    Patrick Billingsley. Probability and Measure . Wiley, 2012

    work page 2012

  6. [6]

    The Asymptotic Theory of Stochastic Games

    Truman Bewley and Elon Kohlberg. The Asymptotic Theory of Stochastic Games . Mathematics of Operations Research , 1(3):197--208, 1976

    work page 1976

  7. [7]

    Principles of Model Checking

    Christel Baier and Joost-Pieter Katoen. Principles of Model Checking . MIT Press, 2008

    2008

  8. [8]

    Baruah, G

    S. Baruah, G. Koren, D. Mao, B. Mishra, A. Raghunathan, L. Rosier, D. Shasha, and F. Wang. On the competitiveness of on-line real-time task scheduling. Real-Time Systems , 4(2):125--144, 1992

    work page 1992

Show all 38 references
  1. [9]

    Algorithms in Real Algebraic Geometry , volume 10 of Algorithms and Computation in Mathematics

    Saugata Basu, Richard Pollack, and Marie-Fran c oise Roy. Algorithms in Real Algebraic Geometry , volume 10 of Algorithms and Computation in Mathematics . Springer Berlin Heidelberg, 2006

    2006

  2. [10]

    A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs

    Krishnendu Chatterjee, Martin Chmel \'i k, and Jessica Davies. A Symbolic SAT-Based Algorithm for Almost-Sure Reachability with Small Strategies in POMDPs . Proceedings of the AAAI Conference on Artificial Intelligence , 30(1):3225--3232, 2016

    2016

  3. [11]

    Qualitative analysis of POMDPs with temporal logic specifications for robotics applications

    Krishnendu Chatterjee, Martin Chmelik, Raghav Gupta, and Ayush Kanodia. Qualitative analysis of POMDPs with temporal logic specifications for robotics applications. In 2015 IEEE International Conference on Robotics and Automation ( ICRA ) , pages 325--330, 2015

    2015

  4. [12]

    Henzinger, Arjun Radhakrishna, and Rohit Singh

    Pavol C ern \'y , Krishnendu Chatterjee, Thomas A. Henzinger, Arjun Radhakrishna, and Rohit Singh. Quantitative Synthesis for Concurrent Programs . In Ganesh Gopalakrishnan and Shaz Qadeer, editors, Computer Aided Verification , volume 6806, pages 243--259. Springer Berlin Hei...

    2011

  5. [13]

    Henzinger

    Krishnendu Chatterjee, Laurent Doyen, and Thomas A. Henzinger. Qualitative Analysis of Partially-Observable Markov Decision Processes . In Mathematical Foundations of Computer Science (MFCS) , volume 6281, pages 258--269. Springer Berlin Heidelberg, 2010

    2010

  6. [14]

    Henzinger

    Krishnendu Chatterjee and Thomas A. Henzinger. Probabilistic Automata on Infinite Words : Decidability and Undecidability Results . In Automated Technology for Verification and Analysis , volume 6252, pages 1--16. Springer Berlin Heidelberg, 2010

    2010

  7. [15]

    Digital Images and Formal Languages

    Karel Culik and Jarkko Kari. Digital Images and Formal Languages . In Grzegorz Rozenberg and Arto Salomaa, editors, Handbook of Formal Languages , pages 599--616. Springer Berlin Heidelberg, 1997

    1997

  8. [16]

    Automated analysis of real-time scheduling using graph games

    Krishnendu Chatterjee, Alexander K \"o ler, and Ulrich Schmid. Automated analysis of real-time scheduling using graph games. In Proceedings of the 16th International Conference on Hybrid Systems: Computation and Control , pages 163--172, 2013

    2013

  9. [17]

    Eddy, Anders Krogh, and Graeme Mitchison

    Richard Durbin, Sean R. Eddy, Anders Krogh, and Graeme Mitchison. Biological Sequence Analysis : Probabilistic Models of Proteins and Nucleic Acids . Cambridge University Press, 1 edition, 1998

    1998

  10. [18]

    Dijkstra

    Edsger W. Dijkstra. A discipline of programming . Prentice Hall series in automatic computation. Prentice Hall, Englewood Cliffs, NJ, 1976

    1976

  11. [19]

    Probability: Theory and Examples

    Richard Durrett. Probability: Theory and Examples . Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, fifth edition edition, 2019

    2019

  12. [20]

    Feinberg

    Eugene A. Feinberg. On measurability and representation of strategic measures in Markov decision processes. In Institute of Mathematical Statistics Lecture Notes - Monograph Series , pages 29--43. Institute of Mathematical Statistics, 1996

    1996

  13. [21]

    Competitive Markov Decision Processes

    Jerzy Filar and Koos Vrieze. Competitive Markov Decision Processes . Springer New York, New York, NY, 1997

    1997

  14. [22]

    Gabow, Zvi Galil, Thomas Spencer, and Robert E

    Harold N. Gabow, Zvi Galil, Thomas Spencer, and Robert E. Tarjan. Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica , 6(2):109--122, 1986

    1986

  15. [23]

    Probabilistic Automata on Finite Words : Decidable and Undecidable Problems

    Hugo Gimbert and Youssouf Oualhadj. Probabilistic Automata on Finite Words : Decidable and Undecidable Problems . In Automata, Languages and Programming , volume 6199, pages 527--538. Springer Berlin Heidelberg, 2010

    2010

  16. [24]

    Ronald A. Howard. Dynamic Programming and Markov Processes . MIT Press, 1960

    1960

  17. [25]

    Finite- State Controllers of POMDPs using Parameter Synthesis

    S Junges, N Jansen, R Wimmer, T Quatmann, and L Winterer. Finite- State Controllers of POMDPs using Parameter Synthesis . In Uncertainty in Artificial Intelligence , 2018

    2018

  18. [26]

    P \'e rez, and Tobias Winkler

    Sebastian Junges, Joost-Pieter Katoen, Guillermo A. P \'e rez, and Tobias Winkler. The complexity of reachability in parametric Markov decision processes. Journal of Computer and System Sciences , 119:183--210, 2021

    2021

  19. [27]

    Richard M. Karp. Reducibility among combinatorial problems. In Complexity of Computer Computations: Proceedings of a Symposium on the Complexity of Computer Computations , pages 85--103. Springer US, 1972

    1972

  20. [28]

    Kress-Gazit , G.E

    H. Kress-Gazit , G.E. Fainekos, and G.J. Pappas. Temporal- Logic-Based Reactive Mission and Motion Planning . IEEE Transactions on Robotics , 25(6):1370--1381, December 2009

    2009

  21. [29]

    Littman, and Anthony R

    Leslie Pack Kaelbling, Michael L. Littman, and Anthony R. Cassandra. Planning and acting in partially observable stochastic domains. Artificial Intelligence , 101(1-2):99--134, 1998

    1998

  22. [30]

    Littman, and Andrew W

    Leslie Pack Kaelbling, Michael L. Littman, and Andrew W. Moore. Reinforcement learning: A survey. Journal of Artificial Intelligence Research , 4(1):237--285, 1996

    1996

  23. [31]

    On the undecidability of probabilistic planning and related stochastic optimization problems

    Omid Madani, Steve Hanks, and Anne Condon. On the undecidability of probabilistic planning and related stochastic optimization problems. Artificial Intelligence , 147(1):5--34, July 2003

    2003

  24. [32]

    Finite-state transducers in language and speech processing

    Mehryar Mohri. Finite-state transducers in language and speech processing. Computational Linguistics , 23(2):269--311, June 1997

    1997

  25. [33]

    Introduction to Probabilistic Automata

    Azaria Paz and Werner Rheinboldt. Introduction to Probabilistic Automata . Computer Science and Applied Mathematics. Academic Press, 1971

    1971

  26. [34]

    Papadimitriou and John N

    Christos H. Papadimitriou and John N. Tsitsiklis. The Complexity of Markov Decision Processes . Mathematics of Operations Research , 12(3):441--450, 1987

    1987

  27. [35]

    Puterman

    Martin L. Puterman. Markov Decision Processes : Discrete Stochastic Dynamic Programming . Wiley, 2014

    2014

  28. [36]

    Perturbations of Markov Chains with Applications to Stochastic Games

    Eilon Solan. Perturbations of Markov Chains with Applications to Stochastic Games . In Stochastic Games and Applications , pages 265--280, 2003

    2003

  29. [37]

    Languages, Automata , and Logic

    Wolfgang Thomas. Languages, Automata , and Logic . In Handbook of Formal Languages , pages 389--455. Springer Berlin Heidelberg, 1997

    1997

  30. [38]

    Strong Uniform Value in Gambling Houses and Partially Observable Markov Decision Processes

    Xavier Venel and Bruno Ziliotto. Strong Uniform Value in Gambling Houses and Partially Observable Markov Decision Processes . SIAM Journal on Control and Optimization , 54(4):1983--2008, 2016

    1983

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.