Computing the Reachability Value of Posterior-Deterministic POMDPs Nathanaël Fijalkow, Arka Ghosh, Roman Kniazev, Guillermo A. Pérez, Pierre Vandenhove Abstract Partially observable Markov decision processes (POMDPs) are a fundamental model for sequential decision-making under uncertainty. However, many verification and synthesis problems for POMDPs are undecidable or intractable. Most prominently, the seminal result of Madani et al. (2003) states that there is no algorithm that, given a POMDP and a set of target states, can compute the maximal probability of reaching the target states, or even approximate it up to a non-trivial constant. This is in stark contrast to fully observable Markov decision processes (MDPs), where the reachability value can be computed in polynomial time. In this work, we introduce posterior-deterministic POMDPs , a novel class of POMDPs. Our main technical contribution is to show that for posterior-deterministic POMDPs, the maximal probability of reaching a given set of states can be approximated up to arbitrary precision. A POMDP is posterior-deterministic if the next state can be uniquely determined by the current state, the action taken, and the observation received. While the actual state is generally uncertain in POMDPs, the posterior-deterministic property tells us that once the true state is known it remains known forever. This simple and natural definition includes all MDPs and captures classical non-trivial examples such as the Tiger POMDP (Kaelbling et al. 1998), making it one of the largest known classes of POMDPs for which the reachability value can be approximated. LaBRI, CNRS, University of Bordeaux, Francenathanael.fijalkow@gmail.com0000-0002-6576-4680 LaBRI, University of Bordeaux, Francea.ghosh@uw.edu.pl0000-0003-3839-8459Supported by the Polish National Science Centre (NCN) grant “Linear algebra in orbit-finite dimension” (2022/45/N/ST6/03242) and the SAIF project, funded by the “France 2030” government investment plan managed by the French National Research Agency, under the reference ANR-23-PEIA-0006. LaBRI, University of Bordeaux, Franceroman@knzv.me University of Antwerp – Flanders Make, Belgiumguillermo.perez@uantwerpen.be0000-0002-1200-4952Supported by the Belgian FWO “SynthEx” (G0AH524N) project. UMONS – Université de Mons, Belgiumpierre.vandenhove@umons.ac.be0000-0001-5834-1068Supported by the Belgian Fonds de la Recherche Scientifique – FNRS through the CDR funding “INSTAP” n ∘ J.0228.26. keywords POMDP, reachability, determinism, value approximation ccs Theory of computation Probabilistic computation ccs Computing methodologies Planning under uncertainty † † runningauthor: N. Fijalkow, A. Ghosh, R. Kniazev, G. A. Pérez, and P. Vandenhove 1 Introduction Partially observable Markov decision processes. Partially observable Markov decision processes (POMDPs) constitute the canonical mathematical framework for sequential decision-making under uncertainty. Introduced by Åström [ 2 ] and developed algorithmically by Smallwood and Sondik [ 28 ] , POMDPs were firmly established as a central paradigm in artificial intelligence through the influential work of Kaelbling, Littman, and Cassandra [ 19 ] . A POMDP models a decision-making agent that must act in a stochastic environment whose true state is hidden; the agent receives only noisy observations and must maintain a belief (a probability distribution over possible states) which they update as new observations arrive. The ubiquity of POMDPs stems from their ability to naturally capture real-world scenarios where agents must act on incomplete information. In robotics , POMDPs model navigation under sensor noise, manipulation with uncertain object poses, and collision avoidance for autonomous vehicles [ 21 , 18 , 29 ] . In healthcare , they enable treatment planning when diagnoses are uncertain and patient states evolve stochastically [ 17 , 27 ] . Dialogue systems use POMDPs to model the inference of user intent from noisy speech recognition [ 30 , 31 ] . In verification and controller synthesis , POMDPs arise naturally when synthesizing controllers for systems with imperfect sensors or hidden adversarial behavior [ 1 , 10 ] . Across these domains, the core problem studied remains the same: computing optimal or near-optimal policies in the face of an infinite belief space. The computational barrier. Despite their ubiquity, POMDPs present formidable computational challenges. The belief space is an infinite continuous simplex. Optimal policies must map this infinite space to actions. Additionally, the value function, while piecewise-linear and convex for finite-horizon problems [ 28 ] , can have exponentially many pieces. The complexity landscape is daunting. For finite-horizon POMDPs, even determining whether there is a strategy that achieves a given sum of rewards is PSPACE-complete [ 24 ] . For infinite-horizon objectives, the situation is far worse: Madani, Hanks, and Condon [ 23 ] established that the maximal probability of reaching a given set of states (a.k.a. the reachability value) cannot be approximated, even up to a fixed error of \frac{1}{3} . More precisely, it follows from Condon and Lipton [ 12 ] that deciding whether the reachability value exceeds \frac{2}{3} or is below \frac{1}{3} is undecidable. Almost-sure reachability (determining whether a strategy reaches the target with probability 1 ) is decidable [ 3 ] , but this positive result does not extend to approximating or computing the exact value. This computational barrier motivates a fundamental question: are there natural, expressive classes of POMDPs for which the reachability value can be approximated? The landscape of tractable classes. The search for tractable classes has resulted in several restricted models. At one extreme, fully observable Markov decision processes (MDPs) admit polynomial-time algorithms for reachability and discounted objectives. Decidable classes with some actual partial observability include revealing POMDPs [ 4 ] , where the structure of information revelation is constrained. On a related but distinct note, multiple-environment MDPs (MEMDPs) [ 26 , 11 ] allow to study robustness across uncertain transition dynamics. Importantly, MEMDPs are not POMDPs: the agent knows the state but faces uncertainty about the environment’s parameters. A notable class is that of deterministic POMDPs [ 22 , 7 ] . Here, transition and observation functions are required to be deterministic functions of state-action pairs. Deterministic POMDPs also admit decidable value approximation. Quasi-deterministic POMDPs [ 6 ] weaken these restrictions by only requiring the transition function to be deterministic. The central open question has been: what is the largest natural class of POMDPs for which reachability value approximation is possible? This paper introduces posterior-deterministic POMDPs , a class that we argue provides a compelling answer to this question. Posterior-deterministic POMDPs. Informal definition. A POMDP is posterior-deterministic if, when the current state is known, the successor state after any action-observation pair is uniquely determined. Equivalently, the posterior distribution over states, conditioned on knowing the current state and observing (a,o) , is always a point mass. The key structural insight is the following: Key property. In posterior-deterministic POMDPs, the belief support (the set of states with positive probability at any given moment) can only decrease in size. This property distinguishes posterior-deterministic POMDPs from general POMDPs, where a single observation can “spread” probability mass to new states. It also clarifies the relationship to quasi-deterministic POMDPs: posterior-determinism is a strictly weaker condition. Quasi-deterministic POMDPs require that successor states be determined by the current state and the action taken, yet they allow for stochastic observations. Posterior-deterministic POMDPs further allow for a truly stochastic transition function, requiring only that each observation resolves the successor state uniquely given the current state and the action taken. The class is natural and encompasses important examples: • all MDPs (trivially, since observations reveal the state), • the Tiger POMDP [ 19 ] , a canonical benchmark in the POMDP literature, and • all quasi-deterministic POMDPs, hence all deterministic POMDPs. Contributions. Our main result is that posterior-deterministic POMDPs admit decidable value approximation for reachability objectives. Main theorem. For any posterior-deterministic POMDP \mathcal{P} , initial belief \mathbf{b} , and a tolerance \varepsilon>0 , one can compute a value v\in[0,1] such that |\mathsf{Val}^{\mathcal{P}}(\mathbf{b})-v|\leq\varepsilon . To prove this result, we use an extension of the classical notion of end components from MDP theory to the POMDP setting, applications of martingale theory, and a belief tree unfolding that exploits the structural properties of posterior-deterministic POMDPs to ensure termination and correctness. Outline. Definitions are given in Section 2 . Section 3 introduces posterior-deterministic POMDPs. Section 4 motivates and describes (without any proof yet) the features of our belief tree unfolding, giving rise to the main approximation algorithm. The two subsequent sections contain all the technical arguments: Section 5 is dedicated to the correctness and convergence of our approximation algorithm, and Section 6 studies end components. 2 Preliminaries If X is a finite set, we denote by \mathsf{Dist}(X) the set of all probability distributions over X . The support of a distribution \mu\in\mathsf{Dist}(X) is the set \mathsf{supp}(\mu)=\left\{x\in X\ \middle|\ \mu(x)>0\right\} . POMDPs. A partially observable Markov decision process (POMDP) is a tuple \mathcal{P}=(Q,A,O,\mathbf{T}) where Q is a finite set of states , A is a finite set of actions , O is a finite set of observations , and \mathbf{T}\colon Q\times A\to\mathsf{Dist}(O\times Q) is a transition function . We frequently write \mathbf{T}(o,q^{\prime}\mid q,a) to denote the probability of receiving observation o and going to state q^{\prime} when taking action a in state q (formally, \mathbf{T}(o,q^{\prime}\mid q,a)=\mathbf{T}(q,a)(o,q^{\prime}) ). We also write \mathbf{T}(q^{\prime}\mid q,a) to denote the marginal probability of going to state q^{\prime} when taking action a in state q (formally, \mathbf{T}(q^{\prime}\mid q,a)=\sum_{o\in O}\mathbf{T}(o,q^{\prime}\mid q,a) ) and, similarly, \mathbf{T}(o\mid q,a) to denote the marginal probability of receiving observation o when taking action a in state q (formally, \mathbf{T}(o\mid q,a)=\sum_{q^{\prime}\in Q}\mathbf{T}(o,q^{\prime}\mid q,a) ). An agent interacting with a POMDP takes actions sequentially, which updates the state probabilistically based on function \mathbf{T} . Yet, the agent only observes the observations, not the actual states (and of course, the agent knows which actions they have taken). In particular, they do not know in general which state the POMDP is in at a given moment—which is why it is called partially observable . Let \mathcal{P}=(Q,A,O,\mathbf{T}) be a POMDP. A run of \mathcal{P} is an infinite sequence of states, actions, and observations of the form \rho=q_{0}a_{1}o_{1}q_{1}a_{2}o_{2}\ldots\in(Q\times A\times O)^{\omega} such that \mathbf{T}(q_{i},a_{i+1})(o_{i+1},q_{i+1})>0 for all i\geq 0 . We write \mathsf{Runs}(\mathcal{P}) for the set of runs on \mathcal{P} . A history is a finite prefix of a run ending in a state; it is an element of Q\times(A\times O\times Q)^{*} . We write \mathsf{last}(h) for the last state of the history. We also define an observable history (resp. observable run ) as the projection of a history (resp. run) to (A\times O)^{*} (resp. (A\times O)^{\omega} ), corresponding to the information an agent has access to while taking actions in the POMDP. We write \mathsf{obs}(\cdot) for this projection. The length \left\lvert h\right\rvert of an (observable) history h is the number of actions in it. If \rho is an (observable) run, we write \rho_{\leq n} for the (observable) history consisting of the states, actions, and observations of \rho up to index n included. Beliefs and belief supports. A belief of \mathcal{P} is a distribution \mathbf{b}\in\mathsf{Dist}(Q) . Beliefs are denoted as boldface letters. The set of all beliefs of \mathcal{P} is denoted as \mathsf{Beliefs}(\mathcal{P}) . Beliefs are used to represent the most accurate information about the current state that the agent has. We usually assume that the agent has an initial belief about its starting position in the POMDP. This belief is updated as actions are taken and observations are received. If \mathbf{b} is the current belief, after taking action a and observing o , the new belief \mathbf{b}_{a,o} is given, for q\in Q , by \mathbf{b}_{a,o}(q)=\frac{\sum_{q^{\prime}\in Q}\mathbf{b}(q^{\prime})\cdot\mathbf{T}(o,q\mid q^{\prime},a)}{\sum_{q^{\prime\prime}\in Q}\sum_{q^{\prime}\in Q}\mathbf{b}(q^{\prime})\cdot\mathbf{T}(o,q^{\prime\prime}\mid q^{\prime},a)}\ . (1) In matrix notation, we have \mathbf{b}_{a,o}=\frac{\mathbf{b}\cdot\mathbf{T}_{a,o}}{\lVert\mathbf{b}\cdot\mathbf{T}_{a,o}\rVert_{1}} , where \mathbf{T}_{a,o} is the transition matrix defined as \mathbf{T}_{a,o}(q,q^{\prime})=\mathbf{T}(q,a)(o,q^{\prime}) . The support of a belief \mathbf{b} is the set \mathsf{supp}(\mathbf{b}) . We write \mathsf{BeliefSups}(\mathcal{P}) for the set of all belief supports of \mathcal{P} (corresponding to the set 2^{Q}\setminus\{\emptyset\} ). We will sometimes write a belief \mathbf{b} as \sum_{q\in Q}\mathbf{b}(q)\cdot q . It will sometimes be convenient to restrict the support of a belief. This gives rise to sub-beliefs , functions \mathbf{b} from Q to [0,1] such that \sum_{q\in Q}\mathbf{b}(q)\leq 1 . For a belief \mathbf{b} and subset of states S\subseteq Q , the restriction \left.\mathbf{b}\right|_{S} of \mathbf{b} to S is the sub-belief defined so that \left.\mathbf{b}\right|_{S}(q)=\begin{cases}\mathbf{b}(q)&\text{if $q\in S$}\\ 0&\text{otherwise.}\end{cases} We frequently extend functions defined on states to beliefs in the natural way. For instance, we write \mathbf{T}(o\mid\mathbf{b},a)=\sum_{q\in\mathsf{supp}(\mathbf{b})}\mathbf{T}(o\mid q,a)\cdot\mathbf{b}(q) for the probability of observing o after taking action a from belief \mathbf{b} . Strategies. A strategy in \mathcal{P} is a function \pi\colon(A\times O)^{*}\to\mathsf{Dist}(A) that sequentially takes an action (possibly in a randomised fashion) given the current observable history. Such strategies are sometimes called observation-based in the literature because they only look at the sequence of observations (as well as the actions they have previously taken) to make their decisions. In this paper, all strategies are assumed to be observation-based. Probability measure on runs. For a history h , the cylinder \mathsf{Cyl}(h) is the set of all runs that start with h . Let \mathcal{F} be the \sigma -algebra on the set \mathsf{Runs}(\mathcal{P}) generated by the set \left\{\mathsf{Cyl}(h)\ \middle|\ h\in Q\times(A\times O\times Q)^{*}\right\} . For an initial (sub-)belief \mathbf{b} and a strategy \pi in \mathcal{P} , we define a function \mathbb{P}^{\pi}_{\mathbf{b}} such that for h\in Q\times(A\times O\times Q)^{*} , \mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Cyl}(h)) is the probability of getting the history h starting from \mathbf{b} using strategy \pi . We give a formal inductive definition: if h=q contains a single state, then \mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Cyl}(h))=\mathbf{b}(q) . If h=h^{\prime}aoq , then \mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Cyl}(h))=\mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Cyl}(h^{\prime}))\cdot\pi(\mathsf{obs}(h^{\prime}))(a)\cdot\mathbf{T}(\mathsf{last}(h^{\prime}),a)(o,q)\ . The function \mathbb{P}^{\pi}_{\mathbf{b}} can be uniquely extended to a probability distribution on the full measurable space (\mathsf{Runs}(\mathcal{P}),\mathcal{F}) using Ionescu-Tulcea extension theorem [ 20 , Section 14.3] . We write \mathbb{E}^{\pi}_{\mathbf{b}}\left[\cdot\right] to denote the expectation with respect to the probability distribution \mathbb{P}^{\pi}_{\mathbf{b}} . Value of a POMDP. A reachability objective on \mathcal{P} is specified by a set of target states T\subseteq Q . Formally, it is the measurable set \mathsf{Reach}_{T}=\left\{q_{0}a_{1}o_{1}q_{1}a_{2}o_{2}\ldots\in\mathsf{Runs}(\mathcal{P})\ \middle|\ \exists i\geq 0,q_{i}\in T\right\} . Given an initial (sub-)belief \mathbf{b} , the (reachability) value of \mathcal{P} with respect to T is \mathsf{Val}^{\mathcal{P}}_{T}(\mathbf{b})=\sup_{\pi}\mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Reach}_{T}) where the supremum is taken over all (observation-based) strategies \pi in \mathcal{P} . When \mathcal{P} and T are clear from the context, we simply write \mathsf{Val}(\mathbf{b}) . Observe that \mathsf{Val}(\mathbf{b}) is upper-bounded by \left\lVert\mathbf{b}\right\rVert_{1}=\sum_{q\in Q}\mathbf{b}(q) , which gives a better upper bound than 1 when \mathbf{b} is a sub-belief. We also define the value of a (sub-)belief \mathbf{b} and an action a as \mathsf{Val}(\mathbf{b},a)=\sum_{o\in O}\mathbf{T}(o\mid\mathbf{b},a)\cdot\mathsf{Val}(\mathbf{b}_{a,o})\ , (2) where \mathbf{b}_{a,o} is obtained from \mathbf{b} after taking action a and observing o (see Equation 1 ). Using that randomisation in strategies is not needed in POMDPs to approach the value for measurable objectives [ 9 , Lemma 1] , we have that \mathsf{Val}(\mathbf{b})=\max_{a\in A}\ \mathsf{Val}(\mathbf{b},a)\ . (3) Assumptions. A state is absorbing if, whenever it is reached, the agent remains in that state forever, no matter what actions are taken. A state is observable if, whenever it is reached, the agent always receives a specific observation that uniquely identifies the state, thus collapsing the current belief to a singleton set. We may assume, without loss of generality, that the target set T contains a single state \top and that there is a unique state \bot with value 0 . Moreover, both \top and \bot are absorbing and observable. We assume that all POMDPs we consider later in the paper satisfy these properties. The statement appears to be folklore. For completeness, we include a proof of it in Appendix A . Lemma 1 . Let \mathcal{P} be a POMDP with target set T and initial belief \mathbf{b} . We can, in time linear in the size of \mathcal{P} , build a POMDP \mathcal{P}^{\prime} with two new states \top and \bot , and a belief \mathbf{b}^{\prime} • both \top and \bot are absorbing and observable, • \bot is the only state with value 0 in \mathcal{P}^{\prime} , • the reachability value is preserved, i.e., \mathsf{Val}^{\mathcal{P}}_{T}(\mathbf{b})=\mathsf{Val}^{\mathcal{P}^{\prime}}_{\{\top\}}(\mathbf{b}^{\prime}) . Problem. We focus on the following problem. It is undecidable for general POMDPs [ 23 , 15 ] . Value approximation. Given a POMDP \mathcal{P} , a belief \mathbf{b} , a target state \top , and a tolerance \varepsilon>0 , compute a number v\in[0,1] such that \left|\mathsf{Val}(\mathbf{b})-v\right|\leq\varepsilon. 3 Posterior-deterministic POMDPs We now present the class of POMDPs we call posterior-deterministic . 3.1 POMDPs and automata A finite automaton is a tuple \mathbb{A}=(Q,\Sigma,\Delta) where Q is a finite set of states , \Sigma is a finite alphabet , and \Delta\subseteq Q\times\Sigma\times Q is a transition relation . It is deterministic if for every q\in Q and \sigma\in\Sigma , there is at most one state q^{\prime}\in Q such that (q,\sigma,q^{\prime})\in\Delta . For deterministic finite automata, we replace \Delta by a (partial) transition function \delta\colon Q\times\Sigma\rightharpoonup Q defined as \delta(q,\sigma)=q^{\prime} if (q,\sigma,q^{\prime})\in\Delta . We extend the transition function to words in the usual way and write \delta^{*}(q,w) for the state reachable from q by reading the word w\in\Sigma^{*} . From a POMDP \mathcal{P}=(Q,A,O,\mathbf{T}) , we construct a (possibly non-deterministic) finite automaton \mathbb{A}(\mathcal{P}) on the alphabet A\times O with Q as the set of states and the transition relation \Delta so that (q,(a,o),q^{\prime})\in\Delta if there is a non-zero probability to go from the state q to the state q^{\prime} after taking the action a and receiving the observation o , i.e., if \mathbf{T}(o,q^{\prime}\mid q,a)>0 . We extend the transition relation \Delta of \mathbb{A}(\mathcal{P}) to \mathsf{BeliefSups}(\mathcal{P}) in the natural way: \delta(S,(a,o))=\left\{q^{\prime}\in Q\ \middle|\ q\in S,(q,(a,o),q^{\prime})\in\Delta\right\}=\left\{q^{\prime}\in Q\ \middle|\ q\in S,\mathbf{T}(o,q^{\prime}\mid q,a)>0\right\}\ . For brevity, we write \delta(S,a,o) instead of \delta(S,(a,o)) . We can then define a deterministic finite automaton \mathbb{B}(\mathcal{P}) with set of states \mathsf{BeliefSups}(\mathcal{P}) , alphabet A\times O , and transition function \delta . We also extend the transition function of \mathcal{P} to \mathsf{Beliefs}(\mathcal{P}) in the natural way: \delta(\mathbf{b},a,o)=\mathbf{b}_{a,o}, where \mathbf{b}_{a,o} is defined in Equation 1 . Note that this gives rise to a possibly infinite automaton since the set of beliefs is infinite. 3.2 Posterior-deterministic POMDPs Definition 2 . A POMDP \mathcal{P} is called posterior-deterministic if \mathbb{A}(\mathcal{P}) is deterministic. In other words, a POMDP \mathcal{P}=(Q,A,O,\mathbf{T}) is posterior-deterministic if for every state q\in Q , action a\in A , and observation o\in O , there exists at most one state q^{\prime}\in Q such that \mathbf{T}(o,q^{\prime}\mid q,a)>0 . In a posterior-deterministic POMDP, if the current state q is known, then taking an action a and receiving an observation o leads to at most one possible successor state q^{\prime} . We use \delta\colon Q\times A\times O\to Q to denote the transition function of \mathbb{A}(\mathcal{P}) . A crucial property of posterior-deterministic POMDPs is that, once the current state is known, then it will remain known forever as every subsequent action-observation pair leads to a unique successor state. More generally, the size of the current belief support can never increase when taking actions and receiving observations, as stated in the following lemma. Lemma 3 . Let \mathcal{P}=(Q,A,O,\mathbf{T}) be a posterior-deterministic POMDP. For every belief support S of \mathcal{P} and observable history h\in(A\times O)^{*} we have |\delta^{*}(S,h)|\leq|S|\ . In posterior-deterministic POMDPs, the origin of the partial observability is in the initial belief. However, in contrast to the more strongly constrained (quasi-)deterministic POMDPs [ 22 , 7 , 6 ] , even assuming knowledge of the current state, there may still be randomness in the observation received after taking an action and in the subsequent state. Our main result is that the value-approximation problem is decidable for posterior-deterministic POMDPs with reachability objectives. Theorem 4 . There is an algorithm that solves the value-approximation problem for posterior-deterministic POMDPs. Moreover, given a POMDP \mathcal{P} , a belief \mathbf{b} , a tolerance \varepsilon>0 , and a threshold v\in[0,1] as input, deciding which case applies from (i) \mathsf{Val}(\mathbf{b})\geq v+\varepsilon or (ii) \mathsf{Val}(\mathbf{b})0 ). Indeed, let \mathcal{P} be a POMDP and let \varepsilon>0 . Let \pi be an \frac{\varepsilon}{2} -optimal strategy in \mathcal{P} . Since the value of \mathcal{P} under \pi is the limit of the values of the events \mathsf{Reach}_{\top}^{\leq k}=\left\{q_{0}a_{1}o_{1}q_{1}\ldots\in\mathsf{Runs}(\mathcal{P})\ \middle|\ \text{there exists }0\leq i\leq k\text{ such that }q_{i}=\top\right\}\ , as k goes to infinity, there exists k\in\mathbb{N} such that \mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Reach}_{\top}^{\leq k})\geq\mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Reach}_{\top})-\frac{\varepsilon}{2}\geq\sup_{\pi^{\prime}}\mathbb{P}^{\pi^{\prime}}_{\mathbf{b}}(\mathsf{Reach}_{\top})-\varepsilon\ . This means that a finite-memory strategy that mimics \pi for k steps and then takes arbitrary actions is \varepsilon -optimal. This holds for all POMDPs, not just posterior-deterministic ones. \lipicsEnd 4 Description of the algorithm In this section, we motivate and describe the main features of our algorithm to approximate the reachability value in posterior-deterministic POMDPs. In Section 4.1 , we informally present a reasonable but incomplete algorithm based on a tree unfolding. We then argue for the need for three more sophisticated unfolding operations in Section 4.2 through examples. Finally, we present our complete algorithm in Section 4.3 . This section purposefully omits proofs, which are found in the subsequent sections. Let \mathcal{P}=(Q,A,O,\mathbf{T}) be a posterior-deterministic POMDP for the section. 4.1 A naive tree unfolding A first attempt at an unfolding. Using Lemma 1 , we can assume without loss of generality that the POMDP \mathcal{P} contains a unique absorbing and observable target state \top and a unique absorbing and observable state \bot with value 0 . Then, for any belief \mathbf{b} , \mathsf{Val}(\mathbf{b})=1 if \mathsf{supp}(\mathbf{b})=\left\{\top\right\} , \mathsf{Val}(\mathbf{b})=0 if \mathsf{supp}(\mathbf{b})=\left\{\bot\right\} , and otherwise we apply Equation 2 and Equation 3 to unfold the tree. \mathbf{b} (\mathbf{b},a_{1}) \delta(\mathbf{b},a_{1},o_{1}) \mathbf{T}(o_{1}\mid\mathbf{b},a_{1}) \delta(\mathbf{b},a_{1},o_{2}) \mathbf{T}(o_{2}\mid\mathbf{b},a_{1}) \cdots 1 (\mathbf{b},a_{2}) 1 \cdots Figure 1 : Tree-like depiction of the naive unfolding. q_{1} q_{2} q_{3} a o_{2}:\frac{1}{2} o_{1}:\frac{1}{2} a o_{1}:1 Figure 2 : Posterior-deterministic POMDP with an infinite \mathrm{{T}}(\mathbf{b}) . As depicted in Figure 2 , this can be seen as evaluating a tree whose nodes are labelled with either a belief or a (belief, action) pair. From a belief node \mathbf{b} , there is an edge with weight 1 to child nodes (\mathbf{b},a) for all actions a\in A . From a (belief, action) node (\mathbf{b},a) , there is an edge with weight \mathbf{T}(o\mid\mathbf{b},a) to child nodes \delta(\mathbf{b},a,o) for all observations o\in O such that \mathbf{T}(o\mid\mathbf{b},a)>0 . Let \mathrm{{T}}(\mathbf{b}) denote the tree whose root is labelled by \mathbf{b} and whose nodes and edges are weighted as described above. Note that the tree is finitely branching and its branches correspond to (possibly infinite, see Figure 2 ) observable runs of \mathcal{P} starting from \mathbf{b} . We use \textnormal{{root}}(T) to denote the root of a tree T . Henceforth, we use \mathsf{belief}(x) to denote the belief appearing in the label of x , that is, \mathsf{belief}(x)=\mathbf{b} if the label of x is \mathbf{b} , and \mathsf{belief}(x)=\mathbf{b} if the label of x is (\mathbf{b},a) for some action a . In general, \mathrm{{T}}(\mathbf{b}) is not finite, even if we assume \mathcal{P} to be posterior-deterministic. For example, say the structure in Figure 2 is a part of \mathcal{P} . If we have a belief node x with \mathsf{supp}(\mathsf{belief}(x))=\left\{q_{1},q_{2}\right\} , then the subtree rooted at x has an infinite branch whose nodes alternately have labels of the form \mathbf{b} and (\mathbf{b},a) with \mathsf{supp}(\mathbf{b})=\left\{q_{1},q_{2}\right\} . Bounding the value from below and above. A reasonable idea could then be to approximate the value of \mathbf{b} by taking a finite truncation of \mathrm{{T}}(\mathbf{b}) (say, cut at depth n ). We could then compute a value, later written \textnormal{{tree}-}{\mathsf{val}{}}_{n}(\textnormal{{root}}(\mathrm{{T}}(\mathbf{b}))) , corresponding to the maximal probability to reach \top within n steps , which is a lower bound on \mathsf{Val}(\mathbf{b}) . This value could be obtained by assuming that the value of a leaf node is 1 if its label support is \{\top\} and 0 otherwise, and then evaluating the tree by backward induction (taking the \max of the children for belief nodes and the weighted sum of the children for (belief, action) nodes). Similarly, one could compute an upper bound on \mathsf{Val}(\mathbf{b}) by evaluating the maximal possible “error” made at depth n , later written \textnormal{{tree}-}{\mathsf{err}{}}_{n}(\textnormal{{root}}(\mathrm{{T}}(\mathbf{b}))) . For a leaf x of the truncated tree, we could set this error to 0 if \mathsf{supp}(\mathsf{belief}(x)) is \left\{\top\right\} or \left\{\bot\right\} (because we know the exact value in this case), and to 1 otherwise (an upper bound on the error). We could then define the error of all the inner nodes also using backward induction to obtain \textnormal{{tree}-}{\mathsf{val}{}}_{n}(\textnormal{{root}}(\mathrm{{T}}(\mathbf{b})))\leq\mathsf{Val}(\mathbf{b})\leq\textnormal{{tree}-}{\mathsf{val}{}}_{n}(\textnormal{{root}}(\mathrm{{T}}(\mathbf{b})))+\textnormal{{tree}-}{\mathsf{err}{}}_{n}(\textnormal{{root}}(\mathrm{{T}}(\mathbf{b})))\ . If \textnormal{{tree}-}{\mathsf{err}{}}_{n}(\textnormal{{root}}(\mathrm{{T}}(\mathbf{b}))) goes to 0 as n goes to infinity, we are done. When does this fail? 4.2 The need for more complex operations We present two scenarios that illustrate the need for a more fine-grained approach. Scenario 1: Trapped in a strongly connected component of belief supports. Assume the structure in Figure 4 is part of \mathcal{P} . For any belief \mathbf{b} with \mathsf{supp}(\mathbf{b}) being either \left\{q,q_{1}\right\} or \left\{q,q_{2}\right\} , \mathsf{supp}(\delta(\mathbf{b},a,o_{1})) and \mathsf{supp}(\delta(\mathbf{b},a,o_{2})) are either \left\{q,q_{1}\right\} or \left\{q,q_{2}\right\} . Thus, \mathrm{{T}}(\mathbf{b}) contains an infinite subtree rooted at \textnormal{{root}}(\mathrm{{T}}(\mathbf{b})) and whose nodes x all satisfy that \mathsf{supp}(\mathsf{belief}(x)) is either \left\{q,q_{1}\right\} or \left\{q,q_{2}\right\} . q_{1} q_{2} q a o_{1}:\frac{1}{3} o_{2}:\frac{2}{3} a o_{1}:\frac{1}{2} o_{2}:\frac{1}{2} a o_{1}:\frac{1}{2} o_{2}:\frac{1}{2} Figure 3 : Scenario 1-type gadget with a non-vanishing \textnormal{{tree}-}{\mathsf{err}{}} . q_{1} q_{2} q_{3} a o_{1}:1 a o_{1}:\frac{1}{2} o_{2}:\frac{1}{2} Figure 4 : Scenario 2-type gadget with a non-vanishing \textnormal{{tree}-}{\mathsf{err}{}} . The issue is that, in our unfolding, no matter how deep we go in the tree, there will always be leaves x with \mathsf{supp}(\mathsf{belief}(x)) being either \left\{q,q_{1}\right\} or \left\{q,q_{2}\right\} , whose error will thus be 1 . In this case, the error of the root does not converge to 0 as n goes to infinity. We need to detect that we are trapped in such a strongly connected component of belief supports and treat it with special care in the unfolding. Below, we formalise such scenarios. Proofs of the statements for them are in Section 6 . Definition 6 . For a belief support S and a partial function f\colon\mathsf{BeliefSups}(\mathcal{P})\rightharpoonup 2^{A} , \mathsf{Reach}_{f}(S) is the set of belief supports T s.t. there is an observable history h=a_{1}o_{1}\dots a_{n}o_{n}\in(A\times O)^{*} with \delta^{*}(S,h)=T and a_{k}\in f(\delta^{*}(S,a_{1}o_{1}\dots a_{k-1}o_{k-1})) for all k\in\left\{1,\dots,n\right\} . For a belief \mathbf{b} and a partial function f\colon\mathsf{BeliefSups}(\mathcal{P})\rightharpoonup 2^{A} , we define \mathsf{Reach}_{f}(\mathbf{b}) as the set of beliefs reachable from belief \mathbf{b} similarly. A support end component (SEC) of \mathcal{P} is a partial function f\colon\mathsf{BeliefSups}(\mathcal{P})\rightharpoonup 2^{A} s.t.: 1. for all S\in\mathsf{dom}(f) , the set f(S) is non-empty; 2. for all S\in\mathsf{dom}(f) , a\in f(S) , and o\in O , the belief support \delta(S,a,o) is in \mathsf{dom}(f) ; 3. for all pairs of belief supports S and T in \mathsf{dom}(f) , we have T\in\mathsf{Reach}_{f}(S) . SECs correspond to end components [ 13 ] of the belief-support MDP [ 4 ] of a POMDP. Example 7 . In Figure 4 , there are at least three SECs. Namely, 1. f_{1} with domain \left\{\left\{q,q_{1},q_{2}\right\}\right\} which maps every element in the domain to \left\{a\right\} , 2. f_{2} with domain \left\{\left\{q,q_{1}\right\},\left\{q,q_{2}\right\}\right\} which maps every element in the domain to \left\{a\right\} , and 3. f_{3} with domain \left\{\left\{q_{1},q_{2}\right\}\right\} and which maps every element in the domain to \left\{a\right\} . The partial function f_{4} with domain \left\{\left\{q,q_{1}\right\},\left\{q,q_{2}\right\},\left\{q_{1},q_{2}\right\}\right\} which maps every element in the domain to \left\{a\right\} is not an SEC. \lipicsEnd We say that an SEC f is contained in another SEC f^{\prime} if \mathsf{dom}(f)\subseteq\mathsf{dom}(f^{\prime}) and for all S\in\mathsf{dom}(f) , f(S)\subseteq f^{\prime}(S) . An SEC f is called maximal if for all SECs f^{\prime} , if f is contained in f^{\prime} , then f=f^{\prime} . Lemma 8 . The set \mathsf{BeliefSups}(\mathcal{P}) splits into disjoint maximal SECs and singletons. SECs can be of two kinds. For illustration, consider Figure 4 once more. Note that after taking the action a , we observe o_{1} and o_{2} with same probabilities from q_{1} and q_{2} . These are different from the probabilities with which we observe them from q . In other words, q is distinguishable from both q_{1} and q_{2} , whereas q_{1} and q_{2} are indistinguishable. Definition 9 . Let f be an SEC of \mathcal{P} . Let q,q^{\prime} be two states from a same belief support S\in\mathsf{dom}(f) . We say that q and q^{\prime} are (f,S) -indistinguishable (denoted q\equiv_{(f,S)}q^{\prime} ) if for all observable histories h from S staying in f , if we write S_{h}=\delta^{*}(S,h) , q_{h}=\delta^{*}(q,h) , and q_{h}^{\prime}=\delta^{*}(q^{\prime},h) , then for all actions a\in f(S_{h}) and observations o\in O , \mathbf{T}(o\mid q_{h},a)=\mathbf{T}(o\mid q_{h}^{\prime},a)\ . For all S\in\mathsf{dom}(f) , the (f,S) -indistinguishability relation is an equivalence relation on S . Two states q and q^{\prime} are (f,S) -distinguishable if they are not (f,S) -indistinguishable. Definition 10 . An SEC f is called distinguishing if there exists some belief support S in the domain of f and states q,q^{\prime}\in S such that q and q^{\prime} are (f,S) -distinguishable. In Example 7 , both f_{1} and f_{2} are distinguishing, and f_{3} is not. SECs will be used to unfold the tree in two different ways, depending on whether they are distinguishing or not. Scenario 1.1: Distinguishing SECs. Our main result about distinguishing SECs is that, by staying in such an SEC, it is possible to eventually determine with arbitrarily high confidence the equivalence class of the current state with respect to the indistinguishability relation. In practice, it suffices to take actions remaining in the SEC uniformly at random for a sufficiently long time. If S/{\equiv_{(f,S)}} stands for the set of equivalence classes of \equiv_{(f,S)} , then: Theorem 11 . Let \mathbf{b} be a sub-belief such that S=\mathsf{supp}(\mathbf{b}) belongs to a distinguishing maximal SEC. Then, \mathsf{Val}(\mathbf{b})=\sum_{C\in S/{\equiv_{(f,S)}}}\mathsf{Val}(\left.\mathbf{b}\right|_{C}). In this result, the “ \geq ” direction is the non-trivial one: from a belief \mathbf{b} in a distinguishing SEC, it is possible to obtain a value as if we knew the equivalence class of the current state. This is strictly more information than is contained in the belief \mathbf{b} . Thanks to this result, we can unfold a belief node x with \mathsf{supp}(\mathsf{belief}(x)) in a distinguishing SEC with a split operation : we add one child per equivalence class of the indistinguishability relation. This strictly decreases the size of the belief supports being considered in the subtree. Scenario 1.2: Non-distinguishing SECs. Unfortunately, in non-distinguishing SECs, it is not possible to gain more information about the current state by staying in the SEC. However, they are still amenable to an algorithmic analysis thanks to the following result. Lemma 12 . For all non-distinguishable SECs f of \mathcal{P} and all beliefs \mathbf{b} such that \mathsf{supp}(\mathbf{b})\in\mathsf{dom}(f) , the set \mathsf{Reach}_{f}(\mathbf{b}) is finite. One can thus explore all beliefs reachable from \mathbf{b} while staying in the SEC. To reach the target, one must eventually leave the SEC, but there are only finitely many ways to do so—we just have to find the “best exit”. Thanks to Lemma 1 , such an exit necessarily exists when the SEC is not \{\top\} or \{\bot\} . Theorem 13 . Let \mathbf{b} be a sub-belief such that \mathsf{supp}(\mathbf{b}) belongs to some non-distinguishing maximal SEC f . Then \mathsf{Val}(\mathbf{b})=\max_{\mathbf{b}^{\prime}\in\mathsf{Reach}_{f}(\mathbf{b})}\max_{a\notin f(\mathsf{supp}(\mathbf{b}^{\prime}))}\mathsf{Val}(\mathbf{b}^{\prime},a). Using this result, we can unfold a belief node x with \mathsf{supp}(\mathsf{belief}(x)) being a non-distinguishing SEC into one child per belief in \mathsf{Reach}_{f}(\mathsf{belief}(x)) , these can be enumerated effectively, and per action not in f(\mathsf{supp}(\mathsf{belief}(x))) . We call such unfoldings exit operations . Scenario 2: Positive probability, but non-occurring observations. Assume the structure presented in Figure 4 is a part of \mathcal{P} . The observation o_{1} can be observed from both q_{1} and q_{2} after taking the action a . However, o_{2} can only be observed from q_{2} . Therefore, \mathrm{{T}}(\mathbf{b}) with \mathsf{supp}(\mathbf{b})=\left\{q_{1},q_{2}\right\} contains an infinite branch that alternates between taking the action a and observing o_{1} . The surprising phenomenon here is that, even though o_{2} has a positive probability of being observed from belief support \{q_{1},q_{2}\} after taking action a , there is a branch with positive probability that observes an infinite number of observations of o_{1} and no observation of o_{2} . This would prevent the error of the root to converge to 0 as we go deeper in the tree. Yet, along this branch, the probability to be in q_{2} converges to 0 , without actually reaching 0 , as we go deeper in the tree. This property should intuitively allow us to approximate the value of \mathbf{b} by the value of q_{1} . To tackle this scenario, we simply fix a threshold \theta>0 and truncate beliefs by removing any probability that is smaller than \theta . Definition 14 . Let \mathbf{b} be a sub-belief and \theta>0 be a threshold. Define \mathsf{Cut}_{\theta}(\mathbf{b}) to be the sub-belief such that \mathsf{Cut}_{\theta}(\mathbf{b})(q)=0 if \mathbf{b}(q)<\theta , and \mathsf{Cut}_{\theta}(\mathbf{b})(q)=\mathbf{b}(q) otherwise. The value of \theta will depend on the allowed tolerance \varepsilon>0 specified by the input to the value-approximation algorithm. Indeed, such a cut operation introduces an error but it helps us avoid infinite branches such as the one described above: after a bounded number of steps, the belief will necessarily be truncated, thereby strictly decreasing the size of its support. Fact 15 . If we apply the split, exit, and cut operations whenever possible in an unfolding, these operations can only be applied a bounded number of times along each branch. Split and cut operations can be applied at most |Q|-1 times since they strictly decrease the size of the belief supports. For the exit operation (Scenario 1.2), the situation is more involved: the operation sends a probability mass outside of the current non-distinguishing SEC, but some mass may remain inside it. In Section 5 , we will define a partial order on the SECs of \mathcal{P} for which exit operations do yield strict decrements, with positive probability. It follows that the error introduced by cutting as above can be controlled with the right choice of \theta computed as a function of \varepsilon and the size of \mathcal{P} . 4.3 The smarter tree unfolding Theorem 11 , Theorem 13 , and Definition 14 give us three new rules to unfold the tree. We now use them to describe our main algorithm. First, we assume we are given a tolerance parameter \varepsilon>0 and fix \theta=\frac{\varepsilon}{2\cdot|Q|} . Definition 16 (Rules for unfolding the tree) . A node is unfolded using the first applicable rule amongst the following ones. The cases are split according to the label of the node. Rule 16 - (i) . (Case: (\mathbf{b},a) ) Applying ( 2 ), we create one child per observation o which is labelled by \mathbf{b}_{a,o} , and the edge connecting it to its parent has weight \mathbf{T}(o\mid\mathbf{b},a) . Rule 16 - (ii) . (Case: \mathbf{b} such that \mathsf{supp}(\mathbf{b}) is either \left\{\top\right\} or \left\{\bot\right\} ) In this case, this node is a leaf. Rule 16 - (iii) . (Case: \mathbf{b} such that \min\left\{\mathbf{b}(q)\ \middle|\ q\in Q,\ \mathbf{b}(q)\neq 0\right\}<\theta ) Using Definition 14 , we create a child which is labelled by \mathsf{Cut}_{\theta}(\mathbf{b}) , and the edge connecting it to its parent has weight 1 . Rule 16 - (iv) . (Case: \mathbf{b} such that the maximal SEC f containing \mathsf{supp}(\mathbf{b}) is distinguishing.) Applying Theorem 11 , we create one child per equivalence class [q] of \equiv_{(f,S)} . The child is labelled by \frac{\left\lVert\mathbf{b}\right\rVert_{1}}{\left\lVert\left.\mathbf{b}\right|_{[q]}\right\rVert_{1}}\cdot\left.\mathbf{b}\right|_{[q]} , and the edge connecting to its parent has weight \frac{\left\lVert\left.\mathbf{b}\right|_{[q]}\right\rVert_{1}}{\left\lVert\mathbf{b}\right\rVert_{1}} . Rule 16 - (v) . (Case: \mathbf{b} such that the maximal SEC f containing \mathsf{supp}(\mathbf{b}) is non-distinguishing.) Applying Theorem 13 , we create children labelled by pairs (\mathbf{b}^{\prime},a) for \mathbf{b}^{\prime}\in\mathsf{Reach}_{f}(\mathbf{b}) and a\notin f(\mathsf{supp}(\mathbf{b}^{\prime})) . The edge connecting them to their parent has weight 1 . Rule 16 - (vi) . (Case: All remaining cases.) Applying ( 3 ), for all actions a we create a child labelled by the pair (\mathbf{b},a) . The edge connecting them to their parent has weight 1 . Let \widehat{\mathrm{{T}}}(\mathbf{b}) denote the (possibly infinite) tree whose root is labelled by \mathbf{b} and is unfolded using the above rules. Let \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) denote its truncation at depth n . The value-approximation algorithm consists in computing statistics on \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) for a large value of n (depending on \mathcal{P} and \varepsilon ), which allows to bound the error of the approximation of \mathsf{Val}(\mathbf{b}) . To conclude, we can bound the depth of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) by a double exponential on the size of \mathcal{P} , thus the size of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) is triply exponential. Hence, using Equation 2 and Equation 3 in a backward-induction fashion yields the advertised complexity of 3EXPTIME. 5 Correctness and termination of the algorithm In this section, we complete the description of the algorithm by formalising how we provide concrete bounds from the tree \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) presented in Section 4.3 , and we then prove the correctness and termination of the algorithm. We take here Theorems 11 and 13 as given; their proofs are in Section 6 . Let \mathcal{P}=(Q,A,O,\mathbf{T}) be a posterior-deterministic POMDP and \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) be the tree defined as above from a belief \mathbf{b} . We call inner nodes of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) unfolded using Rule -(i) or Rule -(iv) sum nodes . The inner nodes unfolded using Rule -(iii) are called cut nodes . Finally, the inner nodes unfolded using Rule -(v) or Rule -(vi) are called max nodes . 5.1 Rank and tree statistics Rank. To facilitate the argument, we define a new parameter called the rank . We will show that the rank provides a valid proxy as an “error term” used to upper bound the value ( Theorem 21 ), and importantly that the rank goes to 0 when n goes to infinity ( Theorem 22 ). Definition 17 . Define a quasi-order \preceq on \mathsf{BeliefSups}(\mathcal{P}) as T\preceq S\iff\text{there exists $h\in(A\times O)^{*}$ such that $\delta^{*}(S,h)=T$}\ . This quasi-order induces the equivalence relation \sim defined as: S\sim T\quad\iff\quad S\preceq T\text{ and }T\preceq S\ . (4) The equivalence class of a belief support S is denoted by [S]_{\sim} . The quasi-order \preceq defines a partial order on the equivalence classes of \sim , which is also denoted by \preceq . Lemma 18 . If T\preceq S , then |T|\leq|S| . Proof. Follows from \mathcal{P} being posterior-deterministic and Lemma 3 . ∎ Keeping this lemma in mind, we extend the quasi-order \preceq as follows. Definition 19 . Define a quasi-order \trianglelefteq on \mathsf{BeliefSups}(\mathcal{P}) as S\trianglelefteq T\quad\iff\quad S\preceq T\text{ or }|S|<|T|\ . Lemma 18 implies that, for every S\sim T , we have |S|=|T| . Therefore, \trianglelefteq induces the same equivalence classes as \preceq . Moreover, it induces a partial order on the equivalence classes of \sim that extends \preceq . Definition 20 . The \mathsf{rank} of an equivalence class of \sim is its height in the partial order induced by \trianglelefteq on the equivalence classes of \sim . The \mathsf{rank} of a belief support is the rank of its equivalence class for \sim . The \mathsf{rank} of a belief \mathbf{b} is defined as \left\lVert\mathbf{b}\right\rVert_{1}\cdot\mathsf{rank}(\mathsf{supp}(\mathbf{b})) , i.e., the rank of its support weighted by the total probability mass of the belief. In particular, relying on the assumptions of Lemma 1 , \mathsf{rank}(\mathbf{b})=0 if and only if \mathsf{supp}(\mathbf{b}) is either \left\{\top\right\} or \left\{\bot\right\} . The rank is upper-bounded by the height of the partial order induced by \trianglelefteq , and is thus at most 2^{|Q|}-1 (which is the cardinality of \mathsf{BeliefSups}(\mathcal{P}) ). Tree statistics. We extend the definition of \mathsf{Val} and \mathsf{rank} to the nodes of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) . We define two statistics, \textnormal{{tree}-}{\mathsf{val}{}}_{n} and \textnormal{{tree}-}{\mathsf{rank}{}}_{n} , for all nodes of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) . These are used to lower and upper bound the value of the belief associated with the node (upcoming formal statement in Theorem 21 ). These statistics are defined inductively on the structure of the tree as follows. Recall that nodes in the tree are sometimes labelled by sub- beliefs due to the cut moves, hence the use of \left\lVert\mathsf{belief}(x)\right\rVert_{1} (which is not always 1 ) in the definitions below. For a leaf x in \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) , \displaystyle\textnormal{{tree}-}{\mathsf{val}{}}_{n}(x) \displaystyle=\begin{cases}\left\lVert\mathsf{belief}(x)\right\rVert_{1}&\text{if $\mathsf{supp}(\mathsf{belief}(x))=\left\{\top\right\}$}\\ 0&\text{otherwise,}\end{cases}\quad\text{ and } \displaystyle\textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x) \displaystyle=\mathsf{rank}(\mathsf{belief}(x))\ . Observe that \textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x) is 0 if \mathsf{supp}(\mathsf{belief}(x)) is either \left\{\top\right\} or \left\{\bot\right\} , and is at least \left\lVert\mathsf{belief}(x)\right\rVert_{1} otherwise. For a sum node x , \displaystyle\textnormal{{tree}-}{\mathsf{val}{}}_{n}(x) \displaystyle=\sum_{\text{child $y$ of $x$}}p_{y}\cdot\textnormal{{tree}-}{\mathsf{val}{}}_{n}(y)\quad\text{ and } \displaystyle\textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x) \displaystyle=\sum_{\text{child $y$ of $x$}}p_{y}\cdot\textnormal{{tree}-}{\mathsf{rank}{}}_{n}(y)\ , where p_{y} is the weight of the edge connecting the child y to its parent x . For a cut node x with y being the only child of x , \textnormal{{tree}-}{\mathsf{val}{}}_{n}(x) (resp. \textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x) ) is equal to \textnormal{{tree}-}{\mathsf{val}{}}_{n}(y) (resp. \textnormal{{tree}-}{\mathsf{rank}{}}_{n}(y) ). For a max node x , \displaystyle\textnormal{{tree}-}{\mathsf{val}{}}_{n}(x) \displaystyle=\max_{\text{child $y$ of $x$}}\textnormal{{tree}-}{\mathsf{val}{}}_{n}(y)\quad\text{ and } \displaystyle\textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x) \displaystyle=\max_{\text{child $y$ of $x$}}\textnormal{{tree}-}{\mathsf{rank}{}}_{n}(y)\ . 5.2 Correctness of the algorithm We now prove that we can obtain lower and upper bounds on the value of the belief associated with any node of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) using \textnormal{{tree}-}{\mathsf{val}{}}_{n} and \textnormal{{tree}-}{\mathsf{rank}{}}_{n} , which means our algorithm is sound. Theorem 21 (Correctness) . For all n\in\mathbb{N} and all nodes x of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) , \textnormal{{tree}-}{\mathsf{val}{}}_{n}(x)\leq\mathsf{Val}(\mathsf{belief}(x))\leq\textnormal{{tree}-}{\mathsf{val}{}}_{n}(x)+\textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x)+|\mathsf{supp}(\mathsf{belief}(x))|\cdot\theta\ . Proof. The proof of this theorem is a simple induction on the structure of the tree. Let x be a leaf of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) . If \mathsf{supp}(\mathsf{belief}(x)) is \left\{\top\right\} (resp. \left\{\bot\right\} ), then \textnormal{{tree}-}{\mathsf{val}{}}_{n}(x)=\mathsf{Val}(\mathsf{belief}(x))=\left\lVert\mathsf{belief}(x)\right\rVert_{1} (resp. 0 ), so the claim holds. Otherwise, let \mathbf{b}=\mathsf{belief}(x) . We have \textnormal{{tree}-}{\mathsf{val}{}}_{n}(x)=0 and 0\leq\mathsf{Val}(\mathbf{b})\leq\left\lVert\mathbf{b}\right\rVert_{1}\leq\left\lVert\mathbf{b}\right\rVert_{1}\cdot\mathsf{rank}(\mathsf{supp}(\mathbf{b}))=\textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x) , so the claim holds as well. This covers case Rule -(ii) of Definition 16 . Let x be an inner node of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) . Assume by induction that the claim holds for all children of x . We now distinguish cases according to its type: sum, cut, or max node. • If x is a sum node, it is unfolded using Rule -(i) (resp. Rule -(iv) ). In this case, \textnormal{{tree}-}{\mathsf{val}{}}_{n}(x) , \mathsf{Val}(\mathsf{belief}(x)) , and \textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x) are obtained as weighted sums of the corresponding values of the children of x : by definition for \textnormal{{tree}-}{\mathsf{val}{}}_{n} and \textnormal{{tree}-}{\mathsf{rank}{}}_{n} , and by ( 2 ) (resp. Theorem 11 ) for \mathsf{Val} . Moreover, for all children y of x , we have |\mathsf{supp}(\mathsf{belief}(y))|\leq|\mathsf{supp}(\mathsf{belief}(x))| by Lemma 3 . The claim then follows using the induction hypothesis on all children of x . • If x is a cut node, it is unfolded using Rule -(iii) . Let y be its unique child. Let k be the number of states q\in\mathsf{supp}(\mathsf{belief}(x)) such that \mathsf{belief}(x)(q)<\theta , i.e., the number of states removed by \mathsf{Cut}_{\theta} . We have by definition that \textnormal{{tree}-}{\mathsf{val}{}}_{n}(x)=\textnormal{{tree}-}{\mathsf{val}{}}_{n}(y) and \textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x)=\textnormal{{tree}-}{\mathsf{rank}{}}_{n}(y) . For the left inequality, observe that \mathsf{Val}(\mathsf{belief}(y))\leq\mathsf{Val}(\mathsf{belief}(x)) since \mathsf{belief}(y) is obtained from \mathsf{belief}(x) by removing some probability mass. Hence, by induction hypothesis on y , \textnormal{{tree}-}{\mathsf{val}{}}_{n}(x)=\textnormal{{tree}-}{\mathsf{val}{}}_{n}(y)\leq\mathsf{Val}(\mathsf{belief}(y))\leq\mathsf{Val}(\mathsf{belief}(x))\ . For the right inequality, observe that, by definition of \mathsf{Val} and \mathsf{Cut}_{\theta} , \mathsf{Val}(\mathsf{belief}(x))\leq\mathsf{Val}(\mathsf{belief}(y))+k\cdot\theta . Using the induction hypothesis on y , we thus obtain \displaystyle\mathsf{Val}(\mathsf{belief}(x)) \displaystyle\leq\textnormal{{tree}-}{\mathsf{val}{}}_{n}(y)+\textnormal{{tree}-}{\mathsf{rank}{}}_{n}(y)+|\mathsf{supp}(\mathsf{belief}(y))|\cdot\theta+k\cdot\theta \displaystyle=\textnormal{{tree}-}{\mathsf{val}{}}_{n}(x)+\textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x)+|\mathsf{supp}(\mathsf{belief}(x))|\cdot\theta\ . • If x is a max node, it is unfolded using Rule -(v) or Rule -(vi) . In this case, \textnormal{{tree}-}{\mathsf{val}{}}_{n}(x) , \mathsf{Val}(\mathsf{belief}(x)) , and \textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x) are defined as maxima of the corresponding values of the children of x : by definition for \textnormal{{tree}-}{\mathsf{val}{}}_{n} and \textnormal{{tree}-}{\mathsf{rank}{}}_{n} , and by Theorem 13 (resp. ( 3 )) for \mathsf{Val} . Moreover, for all children y of x , we have |\mathsf{supp}(\mathsf{belief}(y))|\leq|\mathsf{supp}(\mathsf{belief}(x))| by Lemma 3 . The claim then follows using the induction hypothesis on all children of x . ∎ 5.3 Termination of the algorithm We now show that the upper and lower bounds provided by Theorem 21 converge to an \varepsilon -approximation of the actual value of the belief as n goes to infinity. Fix N=2^{|Q|+1} . Let p_{\min}^{\mathcal{P}} be the smallest non-zero probability occurring in the syntactic description of \mathcal{P} , i.e., \min\left\{\mathbf{T}(o,q^{\prime}\mid q,a)\mid\mathbf{T}(o,q^{\prime}\mid q,a)>0\right\} . Take c=\frac{(p_{\min}^{\mathcal{P}}\cdot\theta)^{N}}{2^{|Q|}} . Theorem 22 (Termination) . For all \varepsilon>0 and natural number n_{\varepsilon} such that n_{\varepsilon}\geq\frac{N}{c}\cdot\left((|Q|+1)\cdot\ln(2)+\ln\left(\frac{1}{\varepsilon}\right)\right), we have \textnormal{{tree}-}{\mathsf{val}{}}_{n_{\varepsilon}}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{n_{\varepsilon}}(\mathbf{b})))\leq\mathsf{Val}(\mathbf{b})\leq\textnormal{{tree}-}{\mathsf{val}{}}_{n_{\varepsilon}}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{n_{\varepsilon}}(\mathbf{b})))+\varepsilon\ . To prove this theorem, our main technical tool is the following lemma, which shows that the \textnormal{{tree}-}{\mathsf{rank}{}} of a node always decreases by the multiplicative factor 1-c after N additional steps of the tree unfolding. Lemma 23 . Let \mathbf{b} be a sub-belief of \mathcal{P} . Then, \textnormal{{tree}-}{\mathsf{rank}{}}_{N}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})))\leq(1-c)\cdot\mathsf{rank}(\mathbf{b})\ . We show how to use this lemma to prove Theorem 22 before proving the lemma itself. Proof of Theorem 22 using Lemma 23 . Let r=\textnormal{{root}}(\widehat{\mathrm{{T}}}_{n_{\varepsilon}}(\mathbf{b})) . By Theorem 21 , we know that \textnormal{{tree}-}{\mathsf{val}{}}_{n_{\varepsilon}}(r)\leq\mathsf{Val}(\mathbf{b})\leq\textnormal{{tree}-}{\mathsf{val}{}}_{n_{\varepsilon}}(r)+\textnormal{{tree}-}{\mathsf{rank}{}}_{n_{\varepsilon}}(r)+|\mathsf{supp}(\mathbf{b})|\cdot\theta\ . Recall that we defined \theta=\frac{\varepsilon}{2\cdot|Q|} . Thus, |\mathsf{supp}(\mathbf{b})|\cdot\theta\leq|Q|\cdot\theta\leq\frac{\varepsilon}{2}\ . To obtain Theorem 22 , it now suffices to show that \textnormal{{tree}-}{\mathsf{rank}{}}_{n_{\varepsilon}}(r)\leq\frac{\varepsilon}{2} . For m\leq n , we consider \widehat{\mathrm{{T}}}_{m}(\mathbf{b}) to be a subtree of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) with the same root. Let x be a leaf of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) . Observe that by definition of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) , expanding the tree by N additional steps from a leaf x of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) is equivalent to building \widehat{\mathrm{{T}}}_{N}(\mathsf{belief}(x)) , so \textnormal{{tree}-}{\mathsf{rank}{}}_{n+N}(x)=\textnormal{{tree}-}{\mathsf{rank}{}}_{N}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathsf{belief}(x))))\ . Lemma 23 therefore implies that for all n\in\mathbb{N} and leaves x of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) , \textnormal{{tree}-}{\mathsf{rank}{}}_{n+N}(x)\leq(1-c)\cdot\mathsf{rank}(\mathsf{belief}(x))\ . By definition of \textnormal{{tree}-}{\mathsf{rank}{}} for leaves, we have \textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x)=\mathsf{rank}(\mathsf{belief}(x)) , so \textnormal{{tree}-}{\mathsf{rank}{}}_{n+N}(x)\leq(1-c)\cdot\textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x)\ . By definition of \textnormal{{tree}-}{\mathsf{rank}{}} for inner nodes (obtained using \max or weighted sums of children), observe that if the \textnormal{{tree}-}{\mathsf{rank}{}} of all leaves is multiplied by a factor 1-c (or smaller), then this change is propagated to all nodes in the tree. Hence, one can prove by induction that for all nodes x of \widehat{\mathrm{{T}}}_{n+N}(\mathbf{b}) , we have \textnormal{{tree}-}{\mathsf{rank}{}}_{n+N}(x)\leq(1-c)\cdot\textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x)\ . Thus, for every k\in\mathbb{N} , we have \textnormal{{tree}-}{\mathsf{rank}{}}_{kN}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{kN}(\mathbf{b})))\leq(1-c)^{k}\cdot\mathsf{rank}(\mathbf{b})\leq(1-c)^{k}\cdot 2^{|Q|}\ . Using that 1-c\leq e^{-c} [ 16 , Inequality 142] , we obtain that (1-c)^{k}\cdot 2^{|Q|}\leq e^{-c\cdot k}\cdot 2^{|Q|}\leq\frac{\varepsilon}{2} when k\geq\frac{1}{c}\cdot\left((|Q|+1)\cdot\ln(2)+\ln(\frac{1}{\varepsilon})\right) . ∎ The remainder of this section is dedicated to a proof of Lemma 23 , the only missing piece to prove the termination of our algorithm. Proof of Lemma 23 . We define a contributing subtree of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) to be a subtree T of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) that contains: 1. the root of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) , 2. all children of sum nodes and cut nodes, and 3. exactly one child of every max node. A contributing subtree thus corresponds to fixing the choices of a deterministic strategy up to depth n in the unfolding \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) . The influence \mathsf{infl}(x,y) of a node y on its ancestor x is defined to be the product of all edges in the path from x to y . Definition 24 . For n\in\mathbb{N} and a contributing subtree T of \widehat{\mathrm{{T}}}_{n}(\mathbf{b}) , define \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(x) to be \mathsf{rank}(\mathsf{belief}(x)) when x is a leaf, and otherwise to be the weighted sum \sum_{\text{$y$ is a child of $x$}}\mathsf{infl}(x,y)\cdot\textnormal{{tree}-}{\mathsf{rank}{}}_{T}(y)\ . By bottom-up induction on the trees, one can prove that for a node x\in\widehat{\mathrm{{T}}}_{N}(\mathbf{b}) , \textnormal{{tree}-}{\mathsf{rank}{}}_{n}(x)=\max\left\{\textnormal{{tree}-}{\mathsf{rank}{}}_{T}(x)\ \middle|\ \text{contributing subtree $T$ of $\widehat{\mathrm{{T}}}_{n}(\mathbf{b})$ rooted at $x$}\right\}\ . Therefore, to prove Lemma 23 , we just need to show that, for all contributing subtrees T of \widehat{\mathrm{{T}}}_{N}(\mathbf{b}) , we have \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})))\leq(1-c)\cdot\mathsf{rank}(\mathbf{b}) . Pick an arbitrary contributing subtree T of \widehat{\mathrm{{T}}}_{N}(\mathbf{b}) . Let D(k) be the set of all descendants of \textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})) in T at depth k from \textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})) . From the definition of \textnormal{{tree}-}{\mathsf{rank}{}}_{T} , it follows that \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})))=\sum_{y\in D(k)}\mathsf{infl}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})),y)\cdot\textnormal{{tree}-}{\mathsf{rank}{}}_{T}(y)\ . (5) Observe that, by construction of \widehat{\mathrm{{T}}}_{N}(\mathbf{b}) , the sum of the influences at every fixed depth is 1 , that is, for all k\geq 0 , \sum_{y\in D(k)}\mathsf{infl}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})),y)=1\ . (6) Recall that c=\frac{(p_{\min}^{\mathcal{P}}\cdot\theta)^{N}}{2^{|Q|}} . We prove three claims which we will then combine to conclude the proof of Lemma 23 . Claim 25 . Let x and y be nodes of T such that y is a descendant of x . We have \mathsf{rank}(\mathsf{belief}(y))\leq\mathsf{rank}(\mathsf{belief}(x)) . {claimproof} From the definition of the tree unfolding ( Definition 16 ), it follows that for a child y^{\prime} of x , we have \left\lVert\mathsf{belief}(y^{\prime})\right\rVert_{1}\leq\left\lVert\mathsf{belief}(x)\right\rVert_{1} and \mathsf{rank}(\mathsf{supp}(\mathsf{belief}(y^{\prime})))\leq\mathsf{rank}(\mathsf{supp}(\mathsf{belief}(x))) , so we obtain \mathsf{rank}(\mathsf{belief}(y^{\prime}))\leq\mathsf{rank}(\mathsf{belief}(x)) . By induction, the claim follows for all descendants y of x . Claim 26 . Let x and y be nodes of T such that y is a descendant of x . We have \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(y)\leq\mathsf{rank}(\mathsf{belief}(x)) . Note that we allow x=y in the statement of the claim, which implies that \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(x)\leq\mathsf{rank}(\mathsf{belief}(x)) (7) for all nodes x of T . {claimproof} [Proof of 26 ] For all leaves z of T in the subtree rooted at x , we have by definition that \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z)=\mathsf{rank}(\mathsf{belief}(z)) . Using 25 , we thus have \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z)\leq\mathsf{rank}(\mathsf{belief}(x)) . Using Definition 24 and ( 6 ), we observe that the \textnormal{{tree}-}{\mathsf{rank}{}}_{T} of a node is a convex combination of the \textnormal{{tree}-}{\mathsf{rank}{}}_{T} of the leaves in its subtree. Since y is in the subtree rooted at x and all the leaves z in the subtree rooted at y are such that \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z)\leq\mathsf{rank}(\mathsf{belief}(x)) , we obtain that \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(y)\leq\mathsf{rank}(\mathsf{belief}(x)) . Claim 27 . There is a node z in T such that 1. \mathsf{infl}(\textnormal{{root}}(T),z)\geq(p_{\min}^{\mathcal{P}}\cdot\theta)^{N} , and 2. \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z)\leq\left(1-\frac{1}{2^{|Q|}}\right)\cdot\mathsf{rank}(\mathbf{b}) . {claimproof} We prove a slightly stronger statement. Namely, we show that there is a node z in T such that 1. no cut nodes appear between \textnormal{{root}}(T) and z , and 2. \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z)\leq\mathsf{rank}(\mathbf{b})-\left\lVert\mathbf{b}\right\rVert_{1} . Let us first prove that this statement is indeed stronger than the one of 27 . If there is no cut node between \textnormal{{root}}(T) and z , then for every node x between them we have \left\lVert\mathsf{belief}(x)\right\rVert_{1}=\left\lVert\mathbf{b}\right\rVert_{1} , and for all q\in\mathsf{supp}(\mathsf{belief}(x)) , \mathsf{belief}(x)(q)\geq\theta . Therefore, the weight of every edge between any two nodes between \textnormal{{root}}(T) and z is at least p_{\min}^{\mathcal{P}}\cdot\theta . This implies \mathsf{infl}(\textnormal{{root}}(T),z)\geq(p_{\min}^{\mathcal{P}}\cdot\theta)^{N} , so the first item of 27 is satisfied. By definition, \mathsf{rank}(\mathbf{b})=\left\lVert\mathbf{b}\right\rVert_{1}\cdot\mathsf{rank}(\mathsf{supp}(\mathbf{b})) . The number of equivalence classes of \sim ( Definition 17 ) is at most |\mathsf{BeliefSups}(\mathcal{P})|=2^{|Q|}-1 . Therefore, \mathsf{rank}(\mathsf{supp}(\mathbf{b}))\leq 2^{|Q|} and \left\lVert\mathbf{b}\right\rVert_{1}\geq\frac{\mathsf{rank}(\mathbf{b})}{2^{|Q|}} . Finally, \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z)\leq\mathsf{rank}(\mathbf{b})-\left\lVert\mathbf{b}\right\rVert_{1}\leq\left(1-\frac{1}{2^{|Q|}}\right)\cdot\mathsf{rank}(\mathbf{b}) , so the second item of 27 is satisfied as well. Now we proceed with the main proof. We split cases based on which rules are used to unfold the nodes that appear in T . Case: Rule -(ii) , Rule -(iii) , or Rule -(iv) is used to unfold a node in T If Rule -(iii) (cut) or Rule -(iv) (split) is used in T , let z be a node which is unfolded using a cut or a split operation, and no other node between the root and z is unfolded using any of those rules. We show that \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z) is at most \mathsf{rank}(\mathbf{b})-\left\lVert\mathbf{b}\right\rVert_{1} . Let \mathbf{b}_{z}=\mathsf{belief}(z) . We split cases based on which rule is used to unfold z . Assume Rule -(iii) (the cut operation) is used. Let z^{\prime} be the child of z and \mathbf{b}_{z^{\prime}}=\mathsf{Cut}(\mathbf{b}_{z})=\mathsf{belief}(z^{\prime}) be its label. We have \displaystyle\textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z) \displaystyle=\textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z^{\prime})\quad\text{by definition of $\textnormal{{tree}-}{\mathsf{rank}{}}_{T}$ for cut operations} \displaystyle\leq\mathsf{rank}(\mathbf{b}_{z^{\prime}})\quad\text{by \eqref{eq:erank rank same node}} \displaystyle=\left\lVert\mathbf{b}_{z^{\prime}}\right\rVert_{1}\cdot\mathsf{rank}(\mathsf{supp}(\mathbf{b}_{z^{\prime}})) \displaystyle\leq\left\lVert\mathbf{b}_{z^{\prime}}\right\rVert_{1}\cdot(\mathsf{rank}(\mathsf{supp}(\mathbf{b}_{z}))-1) \displaystyle\leq\left\lVert\mathbf{b}_{z}\right\rVert_{1}\cdot(\mathsf{rank}(\mathsf{supp}(\mathbf{b}_{z}))-1) \displaystyle=\mathsf{rank}(\mathbf{b}_{z})-\left\lVert\mathbf{b}_{z}\right\rVert_{1}\ . Recall that no cut nodes appear between \textnormal{{root}}(T) and z , so \left\lVert\mathbf{b}_{z}\right\rVert_{1}=\left\lVert\mathbf{b}\right\rVert_{1} . Moreover, by 25 , we have \mathsf{rank}(\mathbf{b}_{z})\leq\mathsf{rank}(\mathbf{b}) . Thus, \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z)\leq\mathsf{rank}(\mathbf{b})-\left\lVert\mathbf{b}\right\rVert_{1} . Now, assume Rule -(iv) (the split operation) is used. For all children z^{\prime} of z , let \mathbf{b}_{z^{\prime}}=\mathsf{belief}(z^{\prime}) . We have \mathsf{rank}(\mathsf{supp}(\mathbf{b}_{z^{\prime}}))\leq\mathsf{rank}(\mathsf{supp}(\mathbf{b}_{z}))-1 . By definition of Rule -(iv) , we also have \left\lVert\mathbf{b}_{z^{\prime}}\right\rVert_{1}=\left\lVert\mathbf{b}_{z}\right\rVert_{1} . Thus, for all children z^{\prime} of z , by 26 , we have \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z^{\prime})\leq\left\lVert\mathbf{b}_{z}\right\rVert_{1}\cdot(\mathsf{rank}(\mathsf{supp}(\mathbf{b}_{z}))-1)\ . Since the weights of outgoing edges from z sum up to 1 , we conclude \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z)\leq\left\lVert\mathbf{b}_{z}\right\rVert_{1}\cdot(\mathsf{rank}(\mathsf{supp}(\mathbf{b}_{z}))-1)=\mathsf{rank}(\mathbf{b}_{z})-\left\lVert\mathbf{b}_{z}\right\rVert_{1}\ . We conclude, as for the cut operation, that \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z)\leq\mathsf{rank}(\mathbf{b})-\left\lVert\mathbf{b}\right\rVert_{1} . If neither Rule -(iii) nor Rule -(iv) is used to unfold any node in T but Rule -(ii) is used, then we can pick z to be the node with belief support \left\{\bot\right\} or \left\{\top\right\} , which is a leaf of T . Since Rule -(iii) is not used anywhere in T , there is indeed no cut node between \textnormal{{root}}(T) and z . Since \mathsf{rank}(\left\{\bot\right\})=\mathsf{rank}(\left\{\top\right\})=0 , we have indeed \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z)=0\leq\mathsf{rank}(\mathbf{b})-\left\lVert\mathbf{b}\right\rVert_{1} . Case: Neither Rule -(ii) , Rule -(iii) , nor Rule -(iv) is used Recall the definition of the quasi-order \preceq ( Definition 17 ). Assume there exists a node z in T such that [\mathsf{supp}(\mathsf{belief}(z))]_{\sim}\prec[\mathsf{supp}(\mathbf{b})]_{\sim} . Let \mathbf{b}_{z}=\mathsf{belief}(z) . Then, \mathsf{rank}(\mathsf{supp}(\mathbf{b}_{z}))\leq\mathsf{rank}(\mathsf{supp}(\mathbf{b}))-1 . Since none of the nodes between \textnormal{{root}}(\widehat{\mathrm{{T}}}_{n}(\mathbf{b})) and z is a cut node, we have \left\lVert\mathbf{b}_{z}\right\rVert_{1}=\left\lVert\mathbf{b}\right\rVert_{1} . Therefore, \displaystyle\textnormal{{tree}-}{\mathsf{rank}{}}_{n}(z) \displaystyle\leq\mathsf{rank}(\mathbf{b}_{z})\quad\text{by\penalty\ \eqref{eq:erank rank same node}} \displaystyle=\left\lVert\mathbf{b}_{z}\right\rVert_{1}\cdot(\mathsf{rank}(\mathsf{supp}(\mathbf{b}_{z}))) \displaystyle\leq\left\lVert\mathbf{b}\right\rVert_{1}\cdot(\mathsf{rank}(\mathsf{supp}(\mathbf{b}))-1) \displaystyle=\mathsf{rank}(\mathbf{b})-\left\lVert\mathbf{b}\right\rVert_{1}\ . It now suffices to show that a node z such that [\mathsf{supp}(\mathsf{belief}(z))]_{\sim}\prec[\mathsf{supp}(\mathbf{b})]_{\sim} must exist in T . Assume otherwise. From the tree T , we create an infinite tree T_{\infty} . This infinite tree will be the limit of trees (T_{n})_{n\in\mathbb{N}} defined below. We build T_{0} from T by relabelling its nodes. A node labelled by some belief \mathbf{c} is relabelled with \mathsf{supp}(\mathbf{c}) . Similarly a node labelled by some (belief, action) pair (\mathbf{c},a) is relabelled with (\mathsf{supp}(\mathbf{c}),a) . Recall that since Rule -(ii) is not used on any node in T , the belief support of every node of T_{0} is different from \left\{\bot\right\} and \left\{\top\right\} . In particular, the length of every branch of T_{0} is N=2^{|Q|+1} . For every n\in\mathbb{N} , we construct T_{n+1} from T_{n} in the following way: 1. Pick the leftmost branch of T_{n} that is not longer than any of the other branches of T_{n} (this assumes we fix a linear order on children for each node of T ). 2. Find two distinct belief support nodes x and y on this branch such that \mathsf{supp}(\mathsf{belief}(x))=\mathsf{supp}(\mathsf{belief}(y))=S for some belief support S . If there are many such nodes, pick the (lexicographically) deepest pair. Such two nodes always exist because the nodes in every branch are alternatively labelled with belief supports and (belief support, action) pairs, and the length of every branch is at least N=2^{|Q|+1} , and so every branch contains at least 2^{|Q|} belief support nodes. By the pigeonhole principle, two of these nodes must be labelled by the same belief support since |\mathsf{BeliefSups}(\mathcal{P})|=2^{|Q|}-1 . 3. Assuming without loss of generality that y is deeper than x , replace the subtree of T_{n} rooted at y with the subtree of T_{n} rooted at x . Let T_{\infty} be the tree we get in the limit. For a node x in T_{\infty} , let T^{x}_{\infty} denote the subtree rooted at x . Let \textnormal{{labels}}(T^{x}_{\infty}) denote the set of labels that appear in some node of T^{x}_{\infty} other than x . Let T_{\text{dec}} be the subtree of T_{\infty} containing every node x of T_{\infty} such that x has a descendant y with \textnormal{{labels}}(T^{y}_{\infty})\subsetneq\textnormal{{labels}}(T^{x}_{\infty}) . The tree T_{\text{dec}} is finitely branching (because so is T ) and has finite branches, because every infinite branch must eventually settle on a fixed set of labels. Hence, König’s lemma implies that T_{\text{dec}} is finite. Pick a node x of T_{\infty} that is not in T_{\text{dec}} . Let {\color[rgb]{0.72,0,0}\emph{\mathcal{C}}}=\left\{S\ \middle|\ \text{$(S,a)\in\textnormal{{labels}}(T^{x}_{\infty})$ for some action $a$}\right\}\cup\left\{S\ \middle|\ \text{$S\in\textnormal{{labels}}(T^{x}_{\infty})$}\right\}\ , and {\color[rgb]{0.72,0,0}\emph{$g$}}\colon\mathcal{C}\to 2^{A} as g(S)=\left\{a\in A\ \middle|\ \text{$(S,a)$ in $T^{x}_{\infty}$ for some action $a$}\right\}\ . For every S\in\mathcal{C} , we use f_{S} to denote the maximal SEC containing S . We show that the union g^{\prime} of g and the SECs f_{S} for S\in\mathcal{C} is itself an SEC. This will suffice to obtain a contradiction: observe that, for every (S,a)\in\textnormal{{labels}}(T^{x}_{\infty}) , a\in g(S)\setminus f_{S}(S) because S is not in a distinguishing SEC (otherwise we would have used Rule -(iv) ), and if S was in a non-distinguishing SEC, then action a would exit the SEC with positive probability by construction of the tree ( Rule -(v) ). This contradicts the maximality of f_{S} . Pick an arbitrary S in \mathsf{dom}(g^{\prime}) . We have to prove that 1. for every action a\in g^{\prime}(S) and observation o\in O , \delta(S,a,o)\in\mathsf{dom}(g^{\prime}) , and 2. for all pairs of belief supports S and T in \mathsf{dom}(g^{\prime}) , T\in\mathsf{Reach}_{g^{\prime}}(S) . We start by showing the first condition. Every T in \mathsf{dom}(f_{S}) is already in \mathsf{dom}(g^{\prime}) . Thus we have to show that \delta(S,a,o)\in\mathsf{dom}(g^{\prime}) for a\in g^{\prime}(S)\setminus f_{S}(S) and o\in O . If a\in g^{\prime}(S)\setminus f_{S}(S) , then (S,a) labels some node y in T^{x}_{\infty} . Therefore, for every o\in O such that \delta(S,a,o)\neq\emptyset , there is a child of y labelled by \delta(S,a,o) . Now, we show the second condition. Pick arbitrary S and T in \mathsf{dom}(g^{\prime}) . We use \mathsf{beliefSupp}(y) to denote the belief support appearing in the label of a node of T^{x}_{\infty} . That is, if \mathsf{beliefSupp}(y)=S if y is labelled with S or (S,a) for some action a . There is a node y_{S} in T^{x}_{\infty} with a descendant y_{T} such that \mathsf{beliefSupp}(y_{S})\in\mathsf{Reach}_{f_{S}}(S) and \mathsf{beliefSupp}(y_{T})\in\mathsf{Reach}_{f_{T}}(T) . Since every pair of belief supports in an SEC is reachable from each other, to finish the proof we need to show that \mathsf{beliefSupp}(y_{T})\in\mathsf{Reach}_{g^{\prime}}(\mathsf{beliefSupp}(y_{S})) . We show that for every node y in T^{x}_{\infty} and its descendant z we have \mathsf{beliefSupp}(z)\in\mathsf{Reach}_{g^{\prime}}(\mathsf{beliefSupp}(y))\ . Observe that this holds when z is a child of y . The general case follows by induction. To conclude the proof of Lemma 23 , we use 26 and 27 . Let z be the node given by 27 . Let k be the depth of z in \widehat{\mathrm{{T}}}_{N}(\mathbf{b}) . We have \displaystyle\textnormal{{tree}-}{\mathsf{rank}{}}_{T}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b}))) \displaystyle=\sum_{y\in D(k)}\mathsf{infl}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})),y)\cdot\textnormal{{tree}-}{\mathsf{rank}{}}_{T}(y) \displaystyle=\mathsf{infl}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})),z)\cdot\textnormal{{tree}-}{\mathsf{rank}{}}_{T}(z)+\sum_{\begin{subarray}{c}y\in D(k)\\ y\neq z\end{subarray}}\mathsf{infl}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})),y)\cdot\textnormal{{tree}-}{\mathsf{rank}{}}_{T}(y) \displaystyle\leq\mathsf{infl}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})),z)\cdot\left(1-\frac{1}{2^{|Q|}}\right)\cdot\mathsf{rank}(\mathbf{b})+\mathsf{rank}(\mathbf{b})\cdot\sum_{\begin{subarray}{c}y\in D(k)\\ y\neq z\end{subarray}}\mathsf{infl}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})),y) \displaystyle=\mathsf{rank}(\mathbf{b})-\frac{\mathsf{infl}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})),z)}{2^{|Q|}}\cdot\mathsf{rank}(\mathbf{b}) \displaystyle=\left(1-\frac{\mathsf{infl}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})),z)}{2^{|Q|}}\right)\cdot\mathsf{rank}(\mathbf{b})\ , where the first equality holds by ( 5 ), the second equality is just a splitting of the sum, and the following inequality holds by 27 for z and by 26 for all other y ’s. The following equalities are just rearrangements of the sum and using that the influences at a given level sum to 1 by ( 6 ). Since \mathsf{infl}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})),z)\geq(p_{\min}^{\mathcal{P}}\cdot\theta)^{N} by 27 , we conclude that \textnormal{{tree}-}{\mathsf{rank}{}}_{T}(\textnormal{{root}}(\widehat{\mathrm{{T}}}_{N}(\mathbf{b})))\leq\left(1-\frac{(p_{\min}^{\mathcal{P}}\cdot\theta)^{N}}{2^{|Q|}}\right)\cdot\mathsf{rank}(\mathbf{b})=(1-c)\cdot\mathsf{rank}(\mathbf{b})\ , as desired to prove Lemma 23 . ∎ 6 Support end components in posterior-deterministic POMDPs Recall that we have defined SECs in Definition 6 . In this section, we study the properties of SECs in posterior-deterministic POMDPs. We start by introducing additional terminology and proving basic properties about SECs in Section 6.1 . 6.1 Basic properties of SECs Let \mathcal{P}=(Q,A,O,\mathbf{T}) be a posterior-deterministic POMDP. An observable history h=a_{1}o_{1}a_{2}o_{2}\ldots a_{n}o_{n} is said to be inside an SEC f from a belief \mathbf{b} if a_{k}\in f(\delta^{*}(\mathsf{supp}(\mathbf{b}),a_{1}o_{1}\dots a_{k-1}o_{k-1})) for all k\leq n . Because this definition only depends on the support of \mathbf{b} , we sometimes write that h is inside f from the belief support \mathsf{supp}(\mathbf{b}) for convenience. We extend this definition to runs in the natural way. Lemma 28 . Let f be the SEC of POMDP \mathcal{P} . Then, all belief supports in \mathsf{dom}(f) have the same cardinality. Proof. Follows from Lemma 3 and the strong connectivity of f . ∎ We define the union of two SECs f and f^{\prime} as the partial function g whose domain is the union of the domains of f and f^{\prime} , and for an element S in its domain g(S)=\begin{cases}f(S)&\text{if $S$ is not in the domain of $f^{\prime}$,}\\ f^{\prime}(S)&\text{if $S$ is not in the domain of $f$,}\\ f(S)\cup f^{\prime}(S)&\text{otherwise}.\end{cases} Lemma 29 . The union of two SECs is also an SEC if and only if their domains have a non-empty intersection. With this in mind, we can now prove Lemma 8 (restated here for clarity). See 8 Proof. Follows from Lemma 29 and the finiteness of \mathsf{BeliefSups}(\mathcal{P}) . ∎ We say that an SEC f is contained in another SEC f^{\prime} if \mathsf{dom}(f)\subseteq\mathsf{dom}(f^{\prime}) and for all S\in\mathsf{dom}(f) , f(S)\subseteq f^{\prime}(S) . An SEC f is called maximal if for all SECs f^{\prime} , if f is contained in f^{\prime} , then f=f^{\prime} . An SEC is said to be bottom if, for all S\in\mathsf{dom}(f) , f(S)=A —that is, all actions remain in the SEC. Remark 30 . Thanks to Lemma 1 , we can assume that POMDPs all have two trivial bottom maximal SECs with domains \left\{\left\{\top\right\}\right\} and \left\{\left\{\bot\right\}\right\} respectively, and that no other SEC contains a support containing \top or a state with value 0 . \lipicsEnd When we are in an SEC f , by only taking actions prescribed by function f , we guarantee that we stay in the SEC. In this section, we prove additional properties of SECs in the case of posterior-deterministic POMDPs: we characterise the SECs in which it is possible to eventually gain information (at the limit) about the current state while staying in the SEC. 6.2 Distinguishability in SECs Let \mathcal{P}=(Q,A,O,\mathbf{T}) be a posterior-deterministic POMDP, and let \delta be the deterministic transition function of \mathbb{A}(\mathcal{P}) . We study in more detail the indistinguishability relation defined in Definition 9 . We say that an observable history h inside f from S distinguishes q and q^{\prime} if h=h^{\prime}ao and \mathbf{T}(o\mid q_{h^{\prime}},a)\neq\mathbf{T}(o\mid q_{h^{\prime}}^{\prime},a) . We say that an observable run \rho inside f from S distinguishes q and q^{\prime} infinitely often if there are infinitely many prefixes \rho_{\leq n} of \rho that (f,S) -distinguish q and q^{\prime} . We show that, in posterior-deterministic POMDPs, both indistinguishability and distinguishability are preserved by taking deterministic transitions. The statement of this lemma is illustrated in Figure 5 . Lemma 31 . Let f be an SEC of \mathcal{P} , and let S be a belief support in \mathsf{dom}(f) . Let q,q^{\prime}\in S , a\in f(S) , and o\in O . Let q_{ao}=\delta(q,a,o) , q^{\prime}_{ao}=\delta(q^{\prime},a,o) , and S_{ao}=\delta(S,a,o) . 1. If q and q^{\prime} are (f,S) -indistinguishable, then q_{ao} and q^{\prime}_{ao} are (f,S_{ao}) -indistinguishable. 2. If q and q^{\prime}\in S are (f,S) -distinguishable, then q_{ao} and q^{\prime}_{ao} are (f,S_{ao}) -distinguishable. Proof. Statement ( 1 ) follows directly from the definition of indistinguishability: if q and q^{\prime} are (f,S) -indistinguishable, then for every history h^{\prime} from S_{ao} inside f , the history h=aoh^{\prime} is a history from S inside f that satisfies the indistinguishability condition. q^{\prime} \equiv_{(f,S)} q S \in q^{\prime}_{ao} \equiv_{(f,S_{ao})} q_{ao} S_{ao} \in \Rightarrow (a,o) (a,o) q^{\prime} \not\equiv_{(f,S)} q S \in q^{\prime}_{ao} \not\equiv_{(f,S_{ao})} q_{ao} S_{ao} \in \Rightarrow (a,o) (a,o) Figure 5 : Illustration of the statement of Lemma 31 (( 1 ) on the left and ( 2 ) on the right). For statement ( 2 ), assume that q and q^{\prime} are (f,S) -distinguishable. Let \hat{h} be a history distinguishing q and q^{\prime} . We show that q_{ao} and q^{\prime}_{ao} are (f,S_{ao}) -distinguishable, that is, there exists a history from S_{ao} inside f that distinguishes q_{ao} and q^{\prime}_{ao} . Since f is an SEC, there exists a history h^{\prime} from S_{ao} inside f that leads back to S . Hence, the history h=aoh^{\prime} is a history from S to S inside f . Therefore, h acts as a permutation on the belief support S . This implies that there is k\geq 1 such that \delta^{*}(q,h^{k})=q and \delta^{*}(q^{\prime},h^{k})=q^{\prime} . By construction, the history h^{\prime}h^{k-1}\hat{h} distinguishes q_{ao} and q^{\prime}_{ao} . ∎ Distinguishability is preserved by containment of SECs. Lemma 32 . Let f and f^{\prime} be two SECs such that f is contained in f^{\prime} . If f is distinguishing, then f^{\prime} is distinguishing. Proof. Let S be a belief support in the domain of f and q,q^{\prime}\in S be two states that are (f,S) -distinguishable. Since f is contained in f^{\prime} , we have that S is also in the domain of f^{\prime} . Moreover, any distinguishing history from S inside f is also a distinguishing history from S inside f^{\prime} , as all actions along the history are also available through function f^{\prime} . ∎ In the rest of Section 6 , we will study both distinguishing and non-distinguishing SECs. In Section 6.3 , we study non-distinguishing SECs and show that there is nothing to gain from staying in such SECs for a long time: the best strategy is to find the best action to exit them. In Section 6.5 , we study distinguishing SECs and show that there is something to gain from staying in them for a long time: by staying in the SEC, we can at the limit distinguish in practice between states that are distinguishable. We will frequently use the following strategy in order to “explore” an SEC. Let f be an SEC and \mathbf{b} be an initial belief such that \mathsf{supp}(\mathbf{b})\in\mathsf{dom}(f) . Let \textup{{unif}}(f) be the strategy that tracks the current belief support S (i.e., after observing some history h inside f from \mathbf{b} such that \delta^{*}(\mathsf{supp}(\mathbf{b}),h)=S ) and chooses an action from f(S) uniformly at random. We do not need to define \textup{{unif}}(f) for h\in(A\times O)^{*} such that \delta^{*}(\mathsf{supp}(\mathbf{b}),h)\notin\mathsf{dom}(f) since such histories are never observed as long as we follow \textup{{unif}}(f) starting from \mathbf{b} . A useful lemma is that, by restricting a (possibly distinguishing) SEC to the supports reachable from an equivalence class of indistinguishable states inside the SEC, we obtain a non-distinguishing SEC. Lemma 33 . For q\in S , let \mathsf{Reach}_{q,S}^{f}=\left\{\delta^{*}([q]_{\equiv_{(f,S)}},h)\ \middle|\ \text{$h$ is an observable history inside $f$ from $S$}\right\} be the set of supports reachable from the equivalence class of q inside f from S . Let f_{q,S} be the function such that \mathsf{dom}(f_{q,S})=\mathsf{Reach}_{q,S}^{f} and, for all T\in\mathsf{Reach}_{q,S}^{f} , f_{q,S}(T)=\bigcup\left\{f(S^{\prime})\mid\text{there is $h$ inside $f$ from $S$ s.t.\ $S^{\prime}=\delta^{*}(S,h)\land T=\delta^{*}([q]_{\equiv_{(f,S)}},h)$}\right\}\ . The function f_{q,S} is a non-distinguishing SEC. Proof. We first show that f_{q,S} is an SEC. Let T\in\mathsf{Reach}_{q,S}^{f} and (a,o)\in A\times O such that a\in f_{q,S}(T) . We show that \delta(T,a,o)\in\mathsf{Reach}_{q,S}^{f} . Since a\in f_{q,S}(T) , by definition of f_{q,S} , there exists a belief support S^{\prime} in the domain of f and a history h inside f from S such that S^{\prime}=\delta^{*}(S,h) , T=\delta^{*}([q]_{\equiv_{(f,S)}},h) , and a\in f(S^{\prime}) . Thus, \delta(T,a,o)=\delta^{*}([q]_{\equiv_{(f,S)}},hao) is indeed an element of \mathsf{Reach}_{q,S}^{f} . We now show the strong connectivity property: for T,T^{\prime}\in\mathsf{Reach}_{q,S}^{f} , we show the existence of an observable history inside f_{q,S} from T to T^{\prime} . Let h,h^{\prime} be such that T=\delta^{*}([q]_{\equiv_{(f,S)}},h) and T^{\prime}=\delta^{*}([q]_{\equiv_{(f,S)}},h^{\prime}) . Let S_{h}=\delta^{*}(S,h) . Since f is an SEC, there exists an observable history \hat{h} inside f from S_{h} to S . Hence, the history h\hat{h} is an observable history inside f from S to S . It therefore acts as a permutation on the belief support S . Thus, there exists k\geq 1 such that (h\hat{h})^{k} is the identity on S ; in particular, \delta^{*}([q]_{\equiv_{(f,S)}},(h\hat{h})^{k})=[q]_{\equiv_{(f,S)}} . Therefore, the history \hat{h}(h\hat{h})^{k-1}h^{\prime} is an observable history inside f_{q,S} from T to T^{\prime} . Finally, observe that f_{q,S} is non-distinguishing: by construction, all states in the equivalence class [q]_{\equiv_{(f,S)}} are indistinguishable from each other inside f_{q,S} . ∎ 6.3 Non-distinguishing SECs We show here that, in non-distinguishing SECs, it is not possible to gain information about the current state while staying in the SEC: the best move in such an SEC is to find the best action to exit it. Let \mathcal{P}=(Q,A,O,\mathbf{T}) be a posterior-deterministic POMDP. Lemma 34 . Let f be an SEC of \mathcal{P} . For every belief \mathbf{b} such that \mathsf{supp}(\mathbf{b})\in\mathsf{dom}(f) , action a\in f(\mathsf{supp}(\mathbf{b})) , observation o\in O , and state q\in\mathsf{supp}(\mathbf{b}) , we have \delta(\mathbf{b},a,o)(\delta(q,a,o))=\frac{\mathbf{T}(o\mid q,a)\cdot\mathbf{b}(q)}{\mathbf{T}(o\mid\mathbf{b},a)}\ . Proof. Let \mathbf{b} be a belief such that \mathsf{supp}(\mathbf{b})\in\mathsf{dom}(f) , a\in f(\mathsf{supp}(\mathbf{b})) , and o\in O . Since all belief supports in f have the same cardinality ( Lemma 28 ), we have by injectivity that for every q\neq q^{\prime}\in\mathsf{supp}(\mathbf{b}) , \delta(q,a,o)\neq\delta(q^{\prime},a,o)\ . Hence, for every q\in\mathsf{supp}(\mathbf{b}) , the only way to reach \delta(q,a,o) from \mathbf{b} by taking action a and observing o is to start from q . Thus, \displaystyle\delta(\mathbf{b},a,o)(\delta(q,a,o))\quad \displaystyle=\quad\mathbf{T}(\delta(q,a,o)\mid\mathbf{b},a,o) \displaystyle=\quad\frac{\mathbf{T}(o\mid q,a)\cdot\mathbf{b}(q)}{\mathbf{T}(o\mid\mathbf{b},a)}\ .\qed Lemma 35 . Let f be a non-distinguishing SEC of \mathcal{P} and \mathbf{b} be a belief such that \mathsf{supp}(\mathbf{b})\in\mathsf{dom}(f) , and h be a history inside f from \mathbf{b} . Then, \delta^{*}(\mathbf{b},h)=\sum_{q\in\mathsf{supp}(\mathbf{b})}\mathbf{b}(q)\cdot\delta^{*}(q,h)\ . Proof. We proceed by induction on the length of h . The property is clearly true when \left\lvert h\right\rvert=0 . Now we do the induction step. Let h be a finite history inside f . Let \mathbf{b}_{h}=\delta^{*}(\mathbf{b},h) . For q\in\mathsf{supp}(\mathbf{b}) , let q_{h}=\delta^{*}(q,h) . Let a\in f(\mathsf{supp}(\mathbf{b}_{h})) and o\in O . Assume \mathbf{b}_{h}=\sum_{q\in\mathsf{supp}(\mathbf{b})}\mathbf{b}(q)\cdot q_{h}\ . We want to show that \delta(\mathbf{b}_{h},a,o)=\sum_{q\in\mathsf{supp}(\mathbf{b})}\mathbf{b}(q)\cdot\delta(q_{h},a,o)\ . Using Lemma 34 , we get that for q,q^{\prime}\in\mathsf{supp}(\mathbf{b}) \frac{\delta(\mathbf{b}_{h},a,o)(\delta(q_{h},a,o))}{\delta(\mathbf{b}_{h},a,o)(\delta(q^{\prime}_{h},a,o))}=\frac{\mathbf{T}(o\mid q_{h},a)}{\mathbf{T}(o\mid q^{\prime}_{h},a)}\cdot\frac{\mathbf{b}_{h}(q_{h})}{\mathbf{b}_{h}(q^{\prime}_{h})}\ . Since f is non-distinguishing, \mathbf{T}(o\mid q_{h},a)=\mathbf{T}(o\mid q^{\prime}_{h},a) , which means \frac{\delta(\mathbf{b}_{h},a,o)(\delta(q_{h},a,o))}{\delta(\mathbf{b}_{h},a,o)(\delta(q^{\prime}_{h},a,o))}=\frac{\mathbf{b}_{h}(q_{h})}{\mathbf{b}_{h}(q^{\prime}_{h})} for every q,q^{\prime}\in\mathsf{supp}(\mathbf{b}) . Since additionally \left\lVert\mathbf{b}_{h}\right\rVert_{1}=\left\lVert\delta(\mathbf{b}_{h},a,o)\right\rVert_{1}=1 , this implies for all q\in\mathsf{supp}(\mathbf{b}) \delta(\mathbf{b}_{h},a,o)(\delta(q_{h},a,o))=\mathbf{b}_{h}(q_{h})=\mathbf{b}(q)\ . This finishes the induction step. ∎ We recall that \mathsf{Reach}_{f}(\mathbf{b}) is the set of beliefs reachable inside f from \mathbf{b} ( Definition 6 ). See 12 Proof. Follows from Lemma 35 , since it shows that a belief reachable from \mathbf{b} inside f is the same as \mathbf{b} up to a injective renaming of the states in \mathsf{supp}(\mathbf{b}) . ∎ Lemma 36 . Let f be a non-distingushing SEC and \mathbf{b} be a belief such that \mathsf{supp}(\mathbf{b}) is in the domain of f . All beliefs \mathbf{b}^{\prime}\in\mathsf{Reach}_{f}(\mathbf{b}) are eventually reached with probability 1 by following \textup{{unif}}(f) from \mathbf{b} . Proof. Let x=\left\lVert\mathbf{b}\right\rVert_{1} . We start by observing that for every \mathbf{c}\in\mathsf{Reach}_{f}(\mathbf{b}) we have \left\lVert\mathbf{c}\right\rVert_{1}=x . Therefore, for all \mathbf{c}\in\mathsf{Reach}_{f}(\mathbf{b}) , actions a\in A , and observations o\in O such that \mathbf{T}(o\mid\mathbf{c},a)>0 , since o can be observed from every state in \mathsf{supp}(\mathbf{c}) by taking action a (as f is non-distinguishing), we have \mathbf{T}(o\mid\mathbf{c},a)\geq p_{\min}^{\mathcal{P}}\cdot x\ . Let k=|\mathsf{Reach}_{f}(\mathbf{b})| . Starting from any \mathbf{c} in \mathsf{Reach}_{f}(\mathbf{b}) , the probability of visiting \mathbf{b}^{\prime} within k steps by following the uniform strategy is at least \left(\frac{p_{\min}^{\mathcal{P}}\cdot x}{|A|}\right)^{k}\ . Therefore, the probability of not visiting \mathbf{b}^{\prime} in less than n\cdot k steps by following the uniform strategy from \mathbf{b} is at most \left(1-\left(\frac{p_{\min}^{\mathcal{P}}\cdot x}{|A|}\right)^{k}\right)^{n}\ . This goes to 0 when n goes to infinity. Therefore, we almost surely reach \mathbf{b}^{\prime} by following \textup{{unif}}(f) from \mathbf{b} . ∎ Corollary 37 . For every non-distinguishing SEC f , belief \mathbf{b}\in\mathsf{dom}(f) and \mathbf{b}^{\prime}\in\mathsf{Reach}_{f}(\mathbf{b}) , there exists a history h^{\prime} inside f from \mathbf{b}^{\prime} such that \delta^{*}(\mathbf{b}^{\prime},h^{\prime})=\mathbf{b}\ . Proof. Let h be a history inside f from \mathbf{b} such that \delta^{*}(\mathbf{b},h)=\mathbf{b}^{\prime} . Since f is an SEC, there must exist a history \overline{h} inside f from \mathbf{b}^{\prime} such that \delta^{*}(\mathsf{supp}(\mathbf{b}^{\prime}),\overline{h})=\mathsf{supp}(\mathbf{b}) . Thus, \delta^{*}(\mathsf{supp}(\mathbf{b}),h\overline{h})=\mathsf{supp}(\mathbf{b}) . This means that the function q\in\mathsf{supp}(\mathbf{b})\mapsto\delta^{*}(q,h\overline{h}) acts as a permutation on the finite set \mathsf{supp}(\mathbf{b}) . Hence, there exists k\geq 1 such that \delta^{*}(q,(h\overline{h})^{k})=q for every q\in\mathsf{supp}(\mathbf{b}) . Now we can finish the proof by taking h^{\prime}=\overline{h}(h\overline{h})^{k-1} and using Lemma 35 . ∎ Lemma 38 . For every non-distinguishing SEC f of \mathcal{P} , belief \mathbf{b} such that \mathsf{supp}(\mathbf{b})\in\mathsf{dom}(f) , and \mathbf{b}^{\prime}\in\mathsf{Reach}_{f}(\mathbf{b}) , \mathsf{Val}(\mathbf{b}^{\prime})=\mathsf{Val}(\mathbf{b})\ . Proof. We prove that all the beliefs inside \mathsf{Reach}_{f}(\mathbf{b}) have the same value. Lemma 12 says that \mathsf{Reach}_{f}(\mathbf{b}) is finite, so let \mathbf{b}_{\min}=\argmin_{\mathbf{c}\in\mathsf{Reach}_{f}(\mathbf{b})}\mathsf{Val}(\mathbf{c})\quad\text{and}\quad\mathbf{b}_{\max}=\argmax_{\mathbf{c}\in\mathsf{Reach}_{f}(\mathbf{b})}\mathsf{Val}(\mathbf{c})\ . It suffices to show that \mathsf{Val}(\mathbf{b}_{\min})=\mathsf{Val}(\mathbf{b}_{\max}) . Let h_{\min} (resp. h_{\max} ) be a history inside f from \mathbf{b} such that \delta^{*}(\mathbf{b},h_{\min})=\mathbf{b}_{\min} (resp. \delta^{*}(\mathbf{b},h_{\max})=\mathbf{b}_{\max} ). By Corollary 37 , there exists a history h_{\min}^{\prime} inside f from \mathbf{b}_{\min} such that \delta^{*}(\mathbf{b}_{\min},h_{\min}^{\prime})=\mathbf{b}\ . Hence, the history h=h_{\min}^{\prime}h_{\max} inside f from \mathbf{b}_{\min} is such that \delta^{*}(\mathbf{b}_{\min},h)=\mathbf{b}_{\max}\ . Let n=\left\lvert h\right\rvert . Let \mathsf{Reach}_{f}^{n}(\mathbf{b}_{\min}) be the set of beliefs reachable from \mathbf{b}_{\min} in exactly n steps while staying inside f ; in particular, \mathbf{b}_{\max}\in\mathsf{Reach}_{f}^{n}(\mathbf{b}_{\min}) . For \mathbf{c}\in\mathsf{Reach}_{f}^{n}(\mathbf{b}_{\min}) , let p_{\mathbf{c}} be the probability of reaching \mathbf{c} in exactly n steps from \mathbf{b}_{\min} following \textup{{unif}}(f) . We have \displaystyle\mathsf{Val}(\mathbf{b}_{\min})\quad \displaystyle\geq\quad\sum_{\mathbf{c}\in\mathsf{Reach}_{f}^{n}(\mathbf{b}_{\min})}p_{\mathbf{c}}\cdot\mathsf{Val}(\mathbf{c}) \displaystyle=\quad p_{\mathbf{b}_{\max}}\cdot\mathsf{Val}(\mathbf{b}_{\max})+\sum_{\mathbf{c}\in\mathsf{Reach}_{f}^{n}(\mathbf{b}_{\min})\setminus\left\{\mathbf{b}_{\max}\right\}}p_{\mathbf{c}}\cdot\mathsf{Val}(\mathbf{c}) \displaystyle\geq\quad p_{\mathbf{b}_{\max}}\cdot\mathsf{Val}(\mathbf{b}_{\min})+\sum_{\mathbf{c}\in\mathsf{Reach}_{f}^{n}(\mathbf{b}_{\min})\setminus\left\{\mathbf{b}_{\max}\right\}}p_{\mathbf{c}}\cdot\mathsf{Val}(\mathbf{b}_{\min}) \displaystyle\geq\quad\mathsf{Val}(\mathbf{b}_{\min}). Since \sum_{\mathbf{c}\in\mathsf{Reach}_{f}^{n}(\mathbf{b}_{\min})}p_{\mathbf{c}}=1 and p_{\mathbf{b}_{\max}}>0 , this implies that \mathsf{Val}(\mathbf{b}_{\min})=\mathsf{Val}(\mathbf{b}_{\max}) . ∎ We can now prove Theorem 13 , the main result about non-distinguishing SECs. See 13 Proof. Since f is non-bottom, \mathsf{dom}(f) contains no support that includes \top or \bot ( Remark 30 ). For a belief \mathbf{b}^{\prime} such that \mathsf{supp}(\mathbf{b}^{\prime})\in\mathsf{dom}(f) , we call an exiting action any action a\notin f(\mathsf{supp}(\mathbf{b}^{\prime})) . Since f is non-bottom, there exists at least one exiting action from some belief in \mathsf{Reach}_{f}(\mathbf{b}) . Recall from ( 3 ) that \mathsf{Val}(\mathbf{b})=\max_{a\in A}\mathsf{Val}(\mathbf{b},a) . Since all beliefs in \mathsf{Reach}_{f}(\mathbf{b}) have the same value by Lemma 38 , and all beliefs \mathbf{b}^{\prime}\in\mathsf{Reach}_{f}(\mathbf{b}) can be eventually reached with probability 1 by following \textup{{unif}}(f) from \mathbf{b} ( Lemma 36 ), we even have \mathsf{Val}(\mathbf{b})=\max_{\mathbf{b}^{\prime}\in\mathsf{Reach}_{f}(\mathbf{b})}\max_{a\in A}\mathsf{Val}(\mathbf{b}^{\prime},a)\ . Since exiting the SEC is the only way to reach \top from beliefs in \mathsf{Reach}_{f}(\mathbf{b}) , there must be an exiting action that preserves the value, which concludes the proof: \mathsf{Val}(\mathbf{b})=\max_{\mathbf{b}^{\prime}\in\mathsf{Reach}_{f}(\mathbf{b})}\max_{a\notin f(\mathsf{supp}(\mathbf{b}^{\prime}))}\mathsf{Val}(\mathbf{b}^{\prime},a)\ .\qed 6.4 The posterior probability of starting in a given state Let \mathcal{P}=(Q,A,O,\mathbf{T}) be a POMDP. 1 1 1 Results of Section 6.4 hold for general POMDPs, not only posterior-deterministic ones. However, we will only use them in the posterior-deterministic case. For every n\in\mathbb{N} , we define a \sigma -algebra \mathcal{F}_{n} on \mathsf{Runs}(\mathcal{P}) (which, we recall, is a subset of (Q\times A\times O)^{\omega} ) that corresponds to the information available to the agent after the first n action-observation pairs. We extend the notion of cylinders to observable histories: for an observable history h\in(A\times O)^{*} , the cylinder \mathsf{Cyl}(h) is the set of runs in \mathsf{Runs}(\mathcal{P}) whose projection to (A\times O)^{\left\lvert h\right\rvert} matches h . Formally, for n\in\mathbb{N} , we define \mathcal{F}_{n}=\left\{\mathsf{Cyl}(h)\ \middle|\ \text{$h$ is observable and $\left\lvert h\right\rvert=n$}\right\}\ . The sequence \mathcal{F}_{0}\subseteq\mathcal{F}_{1}\subseteq\mathcal{F}_{2}\subseteq\dots defines a filtration . Let \mathbf{b} be an initial belief, and \pi be a strategy. For every q\in\mathsf{supp}(\mathbf{b}) , define a sequence of random variables (X^{q}_{n})_{n\in\mathbb{N}} that track the probability to have started in q given the first n actions and observations, in addition to the initial belief \mathbf{b} . Formally, consider the event \mathsf{Cyl}(q)\in\mathcal{F} (i.e., “the initial state is q ”). For n\in\mathbb{N} , we define the random variable X^{q}_{n}\colon(A\times O)^{\omega}\to[0,1] as X^{q}_{n}(\rho)=\mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Cyl}(q)\mid\rho_{\leq n})\ , representing the a posteriori probability to have started in q given that we have observed the first n actions and observations of run \rho . In other words, X^{q}_{n}=\mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Cyl}(q)\mid\mathcal{F}_{n})\ . In particular, X^{q}_{n} is \mathcal{F}_{n} -measurable for every n\in\mathbb{N} . Notice that X^{q}_{0}=\mathbf{b}(q) . This sequence of random variables is a martingale [ 14 , Section 4.2] for all possible initial states q . Observe that this value can be computed inductively using Bayes’ rule, and depends on the initial belief \mathbf{b} but not on the strategy \pi (as long as \pi takes the actions along the history with non-zero probability). Lemma 39 . For every q\in\mathsf{supp}(\mathbf{b}) , the sequence (X^{q}_{n})_{n\in\mathbb{N}} defines a martingale with respect to the filtration (\mathcal{F}_{n})_{n\in\mathbb{N}} . Proof. Let q\in\mathsf{supp}(\mathbf{b}) . First of all, for every n\in\mathbb{N} , X^{q}_{n} is \mathcal{F}_{n} -measurable by definition. Moreover, for every n\in\mathbb{N} , it holds that 0\leq X^{q}_{n}\leq 1 . Hence, \mathbb{E}^{\pi}_{\mathbf{b}}\left[|X^{q}_{n}|\right]\leq 1<\infty for every n\in\mathbb{N} . To show that (X^{q}_{n})_{n\in\mathbb{N}} is a martingale with respect to the filtration (\mathcal{F}_{n})_{n\in\mathbb{N}} , it remains to show that for every n\in\mathbb{N} , \mathbb{E}^{\pi}_{\mathbf{b}}\left[X^{q}_{n+1}\mid\mathcal{F}_{n}\right]=X^{q}_{n} . By definition, for every n\in\mathbb{N} , X^{q}_{n}=\mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Cyl}(q)\mid\mathcal{F}_{n})=\mathbb{E}^{\pi}_{\mathbf{b}}\left[\mathbbm{1}_{\mathsf{Cyl}(q)}\mid\mathcal{F}_{n}\right]\ . Hence, for every n\in\mathbb{N} , \displaystyle\mathbb{E}^{\pi}_{\mathbf{b}}\left[X^{q}_{n+1}\mid\mathcal{F}_{n}\right] \displaystyle=\mathbb{E}^{\pi}_{\mathbf{b}}\left[\mathbb{E}^{\pi}_{\mathbf{b}}\left[\mathbbm{1}_{\mathsf{Cyl}(q)}\mid\mathcal{F}_{n+1}\right]\mid\mathcal{F}_{n}\right] \displaystyle=\mathbb{E}^{\pi}_{\mathbf{b}}\left[\mathbbm{1}_{\mathsf{Cyl}(q)}\mid\mathcal{F}_{n}\right]\text{ by the law of iterated expectations} \displaystyle=X^{q}_{n}\ .\qed The following is an obvious but useful corollary of Lemma 39 . Corollary 40 . \mathbb{E}^{\pi}_{\mathbf{b}}\left[X^{q}_{n}\right]=\mathbf{b}(q)\leq 1 for all q\in\mathsf{supp}(\mathbf{b}) and n\in\mathbb{N} . Using Doob’s convergence theorem [ 14 , Theorem 4.6.7] , given that the martingales (X^{q}_{n})_{n\in\mathbb{N}} are bounded and thus uniformly integrable, we get the following. Corollary 41 . For every q\in\mathsf{supp}(\mathbf{b}) , there exists a random variable X^{q}_{\infty} such that the sequence (X^{q}_{n})_{n\in\mathbb{N}} converges almost surely and in L^{1} to X^{q}_{\infty} . 6.5 Distinguishing SECs Theorem 11 is our main result about distinguishing SECs; it shows that in a distinguishing SEC, there is a way to distinguish between states that are distinguishable in practice, by following a strategy staying in the SEC that separates at the limit the belief into disjoint parts. See 11 We fix for this section a posterior-deterministic POMDP \mathcal{P}=(Q,A,O,\mathbf{T}) , a distinguishing maximal SEC f , and a sub-belief \mathbf{b} such that S=\mathsf{supp}(\mathbf{b}) belongs to \mathsf{dom}(f) . We first prove the “ \leq ” inequality of Theorem 11 , which follows directly from the definition of \mathsf{Val} . Lemma 42 . \mathsf{Val}(\mathbf{b})\leq\sum_{C\in S/{\equiv_{(f,S)}}}\mathsf{Val}(\left.\mathbf{b}\right|_{C})\ . Proof. By definition, \mathsf{Val}(\mathbf{b})=\sup_{\pi}\mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Reach}_{\top}) . For a fixed strategy \pi , we have \mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Reach}_{\top})=\sum_{C\in S/{\equiv_{(f,S)}}}\mathbb{P}^{\pi}_{\left.\mathbf{b}\right|_{C}}(\mathsf{Reach}_{\top})\ . We conclude that \displaystyle\mathsf{Val}(\mathbf{b}) \displaystyle=\sup_{\pi}\sum_{C\in S/{\equiv_{(f,S)}}}\mathbb{P}^{\pi}_{\left.\mathbf{b}\right|_{C}}(\mathsf{Reach}_{\top}) \displaystyle\leq\sum_{C\in S/{\equiv_{(f,S)}}}\sup_{\pi}\mathbb{P}^{\pi}_{\left.\mathbf{b}\right|_{C}}(\mathsf{Reach}_{\top}) \displaystyle=\sum_{C\in S/{\equiv_{(f,S)}}}\mathsf{Val}(\left.\mathbf{b}\right|_{C})\ , where the inequality follows from the fact that the supremum of a sum is at most the sum of the suprema, since the strategies maximizing each term may differ. ∎ The rest of Section 6.5 is dedicated to the more involved proof of the “ \geq ” inequality of Theorem 11 , which will be stated in Lemma 53 . We will study the properties of the martingale (X^{q}_{n})_{n\in\mathbb{N}} (from Section 6.4 ) for posterior-deterministic POMDPs. Since \mathcal{P} is posterior-deterministic, for an observable history h inside an SEC, we have X^{q}_{n}(h\rho)=\delta^{*}(\mathbf{b},h)(\delta^{*}(q,h))\quad\text{for all $\rho\in(A\times O)^{\omega}$}\ . (8) Indeed, in a posterior-deterministic POMDP, there is only one possible state \delta^{*}(q,h) after observing h starting from q . Moreover, inside an SEC, the action of h on \mathsf{supp}(\mathbf{b}) is injective ( Lemma 28 ). Therefore, we just have to compute the probability of that state in the belief \delta^{*}(\mathbf{b},h) obtained after observing h starting from \mathbf{b} . We deduce the following. Lemma 43 . For all q\in\mathsf{supp}(\mathbf{b}) , for all n , for all \rho\in(A\times O)^{\omega} that stays inside f , X^{q}_{n}(\rho)\neq 0 . Lemma 44 . For every q,q^{\prime}\in\mathsf{supp}(\mathbf{b}) , n\in\mathbb{N} and run \rho\in(A\times O)^{\omega} that stays inside f , \frac{X^{q}_{n+1}(\rho)}{X^{q^{\prime}}_{n+1}(\rho)}=\frac{X^{q}_{n}(\rho)}{X^{q^{\prime}}_{n}(\rho)}\cdot\frac{\mathbf{T}(o\mid\delta^{*}(q,\rho_{\leq n}),a)}{\mathbf{T}(o\mid\delta^{*}(q^{\prime},\rho_{\leq n}),a)}\ . Proof. Let q,q^{\prime}\in\mathsf{supp}(\mathbf{b}) and \rho\in(A\times O)^{\omega} be a run from \mathbf{b} inside f . Let h=\rho_{\leq n} and (a,o) be the pair following h in \rho . Let \mathbf{b}_{h}=\delta^{*}(\mathbf{b},h) , q_{h}=\delta^{*}(q,h) , and q^{\prime}_{h}=\delta^{*}(q^{\prime},h) . Since \rho is inside f , h is also inside f and a\in f(\mathsf{supp}(\mathbf{b}_{h})) . Then, X^{q}_{n}(\rho)=\mathbf{b}_{h}(q_{h}) and X^{q^{\prime}}_{n}(\rho)=\mathbf{b}_{h}(q^{\prime}_{h}) by ( 8 ). Also, \displaystyle X^{q}_{n+1}(\rho)\quad \displaystyle=\quad\delta(\mathbf{b}_{h},a,o)(\delta(q_{h},a,o)) by ( 8 ) \displaystyle=\quad\frac{\mathbf{T}(o\mid q_{h},a)\cdot\mathbf{b}_{h}(q_{h})}{\mathbf{T}(o\mid\mathbf{b}_{h},a)} ( Lemma 34 ) \displaystyle=\quad\frac{\mathbf{T}(o\mid q_{h},a)\cdot X^{q}_{n}(\rho)}{\mathbf{T}(o\mid\mathbf{b}_{h},a)} \displaystyle\text{by\penalty\ \eqref{eq:dist randv}}. Similarly X^{q^{\prime}}_{n+1}(\rho)\quad=\quad\frac{\mathbf{T}(o\mid q^{\prime}_{h},a)\cdot X^{q^{\prime}}_{n}(\rho)}{\mathbf{T}(o\mid\mathbf{b}_{h},a)}\ . The equality in the statement of the lemma follows from the two above equalities and Lemma 43 . ∎ Corollary 45 . Let q\equiv_{(f,S)}q^{\prime} be two non-distinguishable states in S=\mathsf{supp}(\mathbf{b}) . Let \rho\in(A\times O)^{\omega} be an observable run inside f for which (X^{q}_{n})_{n\in\mathbb{N}} converges to X^{q}_{\infty} and (X^{q^{\prime}}_{n})_{n\in\mathbb{N}} converges to X^{q^{\prime}}_{\infty} . Then, \mathbf{b}(q)\cdot X^{q^{\prime}}_{\infty}(\rho)=\mathbf{b}(q^{\prime})\cdot X^{q}_{\infty}(\rho) . Proof. Let r=\frac{\mathbf{b}(q^{\prime})}{\mathbf{b}(q)} . Recall that X^{q}_{0}(\rho)=\mathbf{b}(q) and X^{q^{\prime}}_{0}(\rho)=\mathbf{b}(q^{\prime}) . Thus, using Lemma 44 and the fact that q and q^{\prime} are not (f,\mathsf{supp}(\mathbf{b})) -distinguishable, we get that X^{q^{\prime}}_{n}(\rho)=r\cdot X^{q}_{n}(\rho) for every n\in\mathbb{N} . Since (X^{q}_{n}(\rho))_{n\in\mathbb{N}} converges to X^{q}_{\infty}(\rho) ( Corollary 41 ), this implies X^{q^{\prime}}_{\infty}(\rho)=r\cdot X^{q}_{\infty}(\rho)\ .\qed Lemma 46 . Consider two distinguishable states q\not\equiv_{(f,S)}q^{\prime} in the support S=\mathsf{supp}(\mathbf{b}) . Let \rho\in(A\times O)^{\omega} be an observable run inside f from \mathbf{b} . If \rho distinguishes q and q^{\prime} infinitely often, then at least one of the values X^{q}_{\infty}(\rho) and X^{q^{\prime}}_{\infty}(\rho) is equal to 0 almost surely. Proof. Let \rho=a_{1}o_{1}a_{2}o_{2}\ldots We prove the contrapositive. Assume X^{q}_{\infty}(\rho) and X^{q^{\prime}}_{\infty}(\rho) are both non-zero—we will show that \rho distinguishes q and q^{\prime} only finitely many times. Let r=\frac{X^{q}_{\infty}(\rho)}{X^{q^{\prime}}_{\infty}(\rho)}\quad\text{and, for $n\in\mathbb{N}$,}\quad r_{n}=\frac{X^{q}_{n}(\rho)}{X^{q^{\prime}}_{n}(\rho)}\ . Note that r_{n} is well-defined due to Lemma 43 . Using Corollary 41 , we get that the sequence (r_{n})_{n\in\mathbb{N}} converges to r almost surely. Let w_{n}=\frac{\mathbf{T}(o_{n}\mid\delta^{*}(q,\rho_{\leq n}),a_{n})}{\mathbf{T}(o_{n}\mid\delta^{*}(q^{\prime},\rho_{\leq n}),a_{n})}\text{ for $n\geq 1$}\ . Then, Lemma 44 implies \frac{r_{n}}{r_{n-1}}=w_{n} for every n\geq 1 . Since (r_{n})_{n\in\mathbb{N}} converges almost surely, we get that the sequence (w_{n})_{n\geq 1} converges to 1 almost surely. Since the sets Q , A , and O are finite, so is the set \left\{w_{n}\ \middle|\ n\geq 1\right\} . Since (w_{n})_{n\geq 1} converges to 1 , this implies w_{n}=1 for all but finitely many n\geq 1 . Observe that w_{n}\neq 1 if and only if \rho_{\leq n} distinguishes q and q^{\prime} . Hence, \rho distinguishes q and q^{\prime} only finitely many times. ∎ Lemma 47 . There exists N\in\mathbb{N} and \beta>0 such that, for all beliefs \mathbf{c} such that \mathsf{supp}(\mathbf{c})\in\mathsf{dom}(f) , for all q\not\equiv_{(f,\mathsf{supp}(\mathbf{c}))}q^{\prime}\in\mathsf{supp}(\mathbf{c}) , there exists an observable history h inside f from \mathbf{c} of length at most N that distinguishes q and q^{\prime} and such that \mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{c}}(\mathsf{Cyl}(h))\geq\beta\ . Proof. By definition of distinguishability, for every q\not\equiv_{(f,S^{\prime})}q^{\prime}\in S^{\prime}\in\mathsf{dom}(f) , there exists a history h_{q,q^{\prime}} that distinguishes q and q^{\prime} . Since there are finitely many pairs of states in the finitely many belief supports of \mathsf{dom}(f) , we can take N to be the maximum length of all histories h_{q,q^{\prime}} . Now, let p_{\min}^{\mathcal{P}}=\min\left\{\mathbf{T}(o,q^{\prime}\mid q,a)\mid\mathbf{T}(o,q^{\prime}\mid q,a)>0\right\} be the smallest non-zero probability occurring in the syntactic description of \mathcal{P} . We take \beta=\left(\frac{p_{\min}^{\mathcal{P}}}{|A|}\right)^{N} . Let \mathbf{c} be a belief such that \mathsf{supp}(\mathbf{c})\in\mathsf{dom}(f) , and let q\not\equiv_{(f,\mathsf{supp}(\mathbf{c}))}q^{\prime} be two states in \mathsf{supp}(\mathbf{c}) . We take h=(a_{1},o_{1})(a_{2},o_{2})\ldots(a_{k},o_{k}) to be any history inside f from \mathbf{c} of length at most N that distinguishes q and q^{\prime} . We give a lower bound on \mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{c}}(\mathsf{Cyl}(h)) by considering every step of h . When an action is chosen at step i , it has probability at least \frac{1}{|A|} to be a_{i} since \textup{{unif}}(f) chooses actions uniformly from a subset of A . The probability to observe o_{i} at step i given that action a_{i} was chosen is then given by \mathbf{T}(o_{i}\mid\mathbf{c}_{i-1},a_{i}) where \mathbf{c}_{i-1} is the belief after observing the prefix of h of length i-1 (in particular, \mathbf{c}_{0}=\mathbf{c} ). Thus, \mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{c}}(\mathsf{Cyl}(h))\quad\geq\quad\frac{1}{|A|^{k}}\cdot\mathbf{T}(o_{1}\mid\mathbf{c}_{0},a_{1})\cdot\mathbf{T}(o_{2}\mid\mathbf{c}_{1},a_{2})\cdot\ldots\cdot\mathbf{T}(o_{k}\mid\mathbf{c}_{k-1},a_{k})\ . Since h is inside f from \mathbf{c} , and the cardinality of the belief supports along the way is constant ( Lemma 28 ), we have that for all 1\leq i\leq k , for all q^{\prime\prime}\in\mathsf{supp}(\mathbf{c}_{i-1}) , \mathbf{T}(o_{i}\mid q^{\prime\prime},a_{i})>0 , and thus \mathbf{T}(o_{i}\mid q^{\prime\prime},a_{i})\geq p_{\min}^{\mathcal{P}} . Hence, \displaystyle\mathbf{T}(o_{i}\mid\mathbf{c}_{i-1},a_{i})\quad \displaystyle=\quad\sum_{q^{\prime\prime}\in\mathsf{supp}(\mathbf{c}_{i-1})}\mathbf{c}_{i-1}(q^{\prime\prime})\cdot\mathbf{T}(o_{i}\mid q^{\prime\prime},a_{i}) \displaystyle\geq\quad p_{\min}^{\mathcal{P}}\cdot\sum_{q^{\prime\prime}\in\mathsf{supp}(\mathbf{c}_{i-1})}\mathbf{c}_{i-1}(q^{\prime\prime}) \displaystyle=\quad p_{\min}^{\mathcal{P}}\ . Therefore, \mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{c}}(\mathsf{Cyl}(h))\quad\geq\quad\frac{1}{|A|^{k}}\cdot(p_{\min}^{\mathcal{P}})^{k}\quad\geq\quad\left(\frac{p_{\min}^{\mathcal{P}}}{|A|}\right)^{N}\quad=\quad\beta\ .\qed Lemma 48 . With respect to the probability measure \mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{b}} , for all pairs q\not\equiv_{(f,S)}q^{\prime} , almost all observable runs distinguish q and q^{\prime} infinitely often. Proof. Let q,q^{\prime}\in S such that q\not\equiv_{(f,S)}q^{\prime} , and let D be the set of observable runs inside f from \mathbf{b} that distinguish q and q^{\prime} infinitely often. We show that \mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{b}}\left(D\right)=1 . Let N\in\mathbb{N} , \beta>0 be the numbers we get from Lemma 47 . For n\in\mathbb{N} , let E_{n} be the set of all \rho\in(A\times O)^{\omega} that distinguish q and q^{\prime} at some k\in\left\{n\cdot N,n\cdot N+1,\dots,(n+1)\cdot N-1\right\} . Let E_{\geq j}=\bigcup_{k\geq j}E_{k} for j\in\mathbb{N} . Then, D=\bigcap_{j\in\mathbb{N}}E_{\geq j}\ . We show that \mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{b}}(E_{\geq j})=1 for every j , which implies \mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{b}}(D)=1 . Let j\in\mathbb{N} . Lemmas 31 and 47 imply that for every observable history h of length k\cdot N , there exists z_{h}\in(A\times O)^{\leq N} such that hz_{h} distinguishes q and q^{\prime} and \mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{b}}(\mathsf{Cyl}(hz_{h})\mid\mathsf{Cyl}(h))=\mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{b}_{h}}(\mathsf{Cyl}(z_{h}))\geq\beta\ . Hence, \mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{b}}(E_{k})\geq\beta . We obtain that \mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{b}}(E_{\geq j}^{c})=\mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{b}}\left(\bigcap_{k\geq j}E_{k}^{c}\right)\leq\lim_{k\to\infty}(1-\beta)^{k-j+1}=0\ . Thus, \mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{b}}(E_{\geq j})=1 , as required. ∎ For an equivalence class C of \equiv_{(f,S)} and n\in\mathbb{N} , let X^{C}_{n} denote the sum of the random variables \sum_{q\in C}X^{q}_{n} . Corollary 49 . With respect to the probability measure \mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{b}} , for almost all observable runs \rho\in(A\times O)^{\omega} inside f from \mathbf{b} , X^{C}_{\infty}(\rho)=1 for exactly one equivalence class C of \equiv_{(f,S)} , and for the remaining equivalence classes D of \equiv_{(f,S)} , X^{D}_{\infty}(\rho)=0 . Proof. Let \rho\in(A\times O)^{\omega} be an observable run inside f from \mathbf{b} that distinguishes every pair of distinguishable states (for \equiv_{(f,S)} ) infinitely often. Such runs happen almost surely under \mathbb{P}^{\textup{{unif}}(f)}_{\mathbf{b}} by Lemma 48 . First, observe that for all n\in\mathbb{N} and runs \rho\in(A\times O)^{\omega} inside f from \mathbf{b} , \sum_{q\in Q}X^{q}_{n}(\rho)=1 . By Corollary 41 , this implies that for almost surely, \sum_{q\in Q}X^{q}_{\infty}=1\ . (9) Hence, for almost all observable runs \rho , we have that X^{q}_{\infty}(\rho) is non-zero for some q\in S . Lemma 46 implies X^{q^{\prime}}_{\infty}(\rho)=0 for every q^{\prime}\not\equiv_{(f,S)}q , and Corollary 45 implies X^{q^{\prime}}_{\infty}(\rho)\neq 0 for every q^{\prime}\equiv_{(f,S)}q . Now, applying ( 9 ), we get that X^{[q]_{\equiv_{(f,S)}}}_{\infty}(\rho)=1 and X^{[q^{\prime}]_{\equiv_{(f,S)}}}_{\infty}(\rho)=0 for every q^{\prime}\not\equiv_{(f,S)}q . ∎ Define a sequence of random variables (\mathbb{V}_{n})_{n\in\mathbb{N}} adapted to the filtration (\mathcal{F}_{n})_{n\in\mathbb{N}} as: \mathbb{V}_{n}(\rho)=\mathsf{Val}(\delta^{*}(\mathbf{b},\rho_{\leq n}))\qquad\text{for $\rho\in(A\times O)^{\omega}$ an observable run inside $f$ from $\mathbf{b}$.} Lemma 50 . The sequence (\mathbb{V}_{n})_{n\in\mathbb{N}} defines a supermartingale. Moreover, \mathbb{E}^{\textup{{unif}}(f)}_{\mathbf{b}}\left[\mathbb{V}_{n}\right]\leq 1 for all n . Proof. To show that (\mathbb{V}_{n})_{n\in\mathbb{N}} is a supermartingale, we must verify that \mathbb{E}^{\textup{{unif}}(f)}_{\mathbf{b}}\left[\mathbb{V}_{n+1}\mid\mathcal{F}_{n}\right]\leq\mathbb{V}_{n} . Let \rho\in(A\times O)^{\omega} be an observable run inside f from \mathbf{b} . Let \mathbf{b}_{n}=\delta^{*}(\mathbf{b},\rho_{\leq n}) be the belief at step n along \rho . By definition of \mathbb{V}_{n} , we have \mathbb{V}_{n}(\rho)=\mathsf{Val}(\mathbf{b}_{n}) . Given that the filtration \mathcal{F}_{n} fixes the history up to step n , and that the strategy is \textup{{unif}}(f) , the expectation of the next value is \mathbb{E}^{\textup{{unif}}(f)}_{\mathbf{b}}\left[\mathbb{V}_{n+1}\mid\mathcal{F}_{n}\right](\rho)=\sum_{a\in f(\mathsf{supp}(\mathbf{b}_{n}))}\frac{1}{|f(\mathsf{supp}(\mathbf{b}_{n}))|}\cdot\mathsf{Val}(\mathbf{b}_{n},a)\ . Given \mathsf{Val}(\mathbf{b}_{n})=\max_{a\in A}\mathsf{Val}(\mathbf{b}_{n},a) by ( 1 ), we have \mathbb{E}^{\textup{{unif}}(f)}_{\mathbf{b}}\left[\mathbb{V}_{n+1}\mid\mathcal{F}_{n}\right](\rho)\leq\mathsf{Val}(\mathbf{b}_{n})\cdot\sum_{a\in f(\mathsf{supp}(\mathbf{b}_{n}))}\frac{1}{|f(\mathsf{supp}(\mathbf{b}_{n}))|}=\mathsf{Val}(\mathbf{b}_{n})=\mathbb{V}_{n}(\rho)\ . For the second part of the lemma, simply observe that the value function \mathsf{Val} is bounded above by 1 for any belief \mathbf{b} , since it represents a probability. Therefore, for all n , we have \mathbb{E}^{\textup{{unif}}(f)}_{\mathbf{b}}\left[\mathbb{V}_{n}\right]\leq 1 . ∎ By Doob’s convergence theorem [ 14 , Theorem 4.6.4] , using that the random variables \mathbb{V}_{n} are bounded and thus uniformly integrable, we obtain the following. Lemma 51 . The sequence \mathbb{V}_{n} converges almost surely and in L^{1} to some integrable random variable \mathbb{V}_{\infty} . For a non-zero sub-belief \mathbf{b} , we use \widehat{b} to denote the normalised belief \frac{1}{\left\lVert\mathbf{b}\right\rVert_{1}}\cdot\mathbf{b} . Lemma 52 . Let \rho\in(A\times O)^{\omega} inside f from \mathbf{b} and C be an equivalence class of \equiv_{(f,S)} . If X^{C}_{n}(\rho) converges to X^{C}_{\infty}(\rho) and X^{C}_{\infty}(\rho)=1 , then \mathbb{V}_{\infty}(\rho)=\mathsf{Val}(\widehat{\left.\mathbf{b}\right|_{C}}) . Proof. First, we prove that the value function \mathsf{Val} is 1 -Lipschitz with respect to the 1 -norm on beliefs, i.e., for all beliefs \mathbf{b},\mathbf{b}^{\prime} , |\mathsf{Val}(\mathbf{b})-\mathsf{Val}(\mathbf{b}^{\prime})|\leq\left\lVert\mathbf{b}-\mathbf{b}^{\prime}\right\rVert_{1}\ . (10) To see this, observe that the value of a strategy \pi is the scalar product of the belief and the vector (\mathbb{P}^{\pi}_{\delta_{q}}(\mathsf{Reach}_{\top}))_{q\in Q} where \delta_{q} is the Dirac belief on state q , i.e., \mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Reach}_{\top})=\mathbf{b}\cdot\mathbb{P}^{\pi}_{\cdot}(\mathsf{Reach}_{\top}) . Let \pi be an \varepsilon -optimal strategy from \mathbf{b} , thus \mathsf{Val}(\mathbf{b})\leq\mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Reach}_{\top})+\varepsilon . Also, \mathsf{Val}(\mathbf{b}^{\prime})\geq\mathbb{P}^{\pi}_{\mathbf{b}^{\prime}}(\mathsf{Reach}_{\top}) by definition. We therefore have \displaystyle\mathsf{Val}(\mathbf{b})-\mathsf{Val}(\mathbf{b}^{\prime}) \displaystyle\leq\mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Reach}_{\top})-\mathbb{P}^{\pi}_{\mathbf{b}^{\prime}}(\mathsf{Reach}_{\top})+\varepsilon \displaystyle\leq(\mathbf{b}-\mathbf{b}^{\prime})\cdot\mathbb{P}^{\pi}_{\cdot}(\mathsf{Reach}_{\top})+\varepsilon\ . Since \left\lVert\mathbb{P}^{\pi}_{\cdot}(\mathsf{Reach}_{\top})\right\rVert_{\infty}\leq 1 , we get by Hölder’s inequality that \mathsf{Val}(\mathbf{b})-\mathsf{Val}(\mathbf{b}^{\prime})\leq\left\lVert\mathbf{b}-\mathbf{b}^{\prime}\right\rVert_{1}\cdot\left\lVert\mathbb{P}^{\pi}_{\cdot}(\mathsf{Reach}_{\top})\right\rVert_{\infty}+\varepsilon\leq\left\lVert\mathbf{b}-\mathbf{b}^{\prime}\right\rVert_{1}+\varepsilon\ . Since this is true for every \varepsilon>0 , and by symmetry of the roles of \mathbf{b} and \mathbf{b}^{\prime} , we obtain ( 10 ). We now focus on the statement of the lemma. Assume X^{C}_{n}(\rho) converges to X^{C}_{\infty}(\rho) and X^{C}_{\infty}(\rho)=1 . For every n\in\mathbb{N} , let \mathbf{b}_{n}=\delta^{*}(\mathbf{b},\rho_{\leq n}) and C_{n}=\delta^{*}(C,\rho_{\leq n}) . Note that \mathbb{V}_{n}=\mathsf{Val}(\mathbf{b}_{n}) . For every \varepsilon>0 , there exists N_{\varepsilon}\in\mathbb{N} such that X^{C}_{n}(\rho_{\leq n})>1-\varepsilon for every n\geq N_{\varepsilon} . By definition of X^{C}_{n} , this implies \left\lVert\mathbf{b}_{n}-\left.\mathbf{b}_{n}\right|_{C_{n}}\right\rVert_{1}<\varepsilon\quad\text{and}\quad\left\lVert\left.\mathbf{b}_{n}\right|_{C_{n}}\right\rVert_{1}>1-\varepsilon (11) for every n\geq N_{\varepsilon} . Using Corollary 45 , we get \widehat{\left.\mathbf{b}_{n}\right|_{C_{n}}}=\delta^{*}(\widehat{\left.\mathbf{b}\right|_{C}},\rho_{\leq n})\ . Lemmas 33 and 38 together imply that \mathsf{Val}(\widehat{\left.\mathbf{b}_{n}\right|_{C_{n}}})=\mathsf{Val}(\widehat{\left.\mathbf{b}\right|_{C}})\ . Now, ( 10 ) and ( 11 ) imply \mathsf{Val}(\left.\mathbf{b}_{n}\right|_{C_{n}})\leq\mathsf{Val}(\mathbf{b}_{n})=\mathbb{V}_{n}(\rho)\leq\mathsf{Val}(\left.\mathbf{b}_{n}\right|_{C_{n}})+\varepsilon when n\geq N_{\varepsilon} . Also, for n\geq N_{\varepsilon} , \mathsf{Val}(\widehat{\left.\mathbf{b}\right|_{C}})=\mathsf{Val}(\widehat{\left.\mathbf{b}_{n}\right|_{C_{n}}})\geq\mathsf{Val}(\left.\mathbf{b}_{n}\right|_{C_{n}})\geq(1-\varepsilon)\cdot\mathsf{Val}(\widehat{\left.\mathbf{b}_{n}\right|_{C_{n}}})=(1-\varepsilon)\cdot\mathsf{Val}(\widehat{\left.\mathbf{b}\right|_{C}})\ . Hence, for n\geq N_{\varepsilon} , (1-\varepsilon)\cdot\mathsf{Val}(\widehat{\left.\mathbf{b}\right|_{C}})\leq\mathbb{V}_{n}(\rho)\leq\mathsf{Val}(\widehat{\left.\mathbf{b}\right|_{C}})+\varepsilon\ . Since (\mathbb{V}_{n}(\rho))_{n\in\mathbb{N}} converges to \mathbb{V}_{\infty}(\rho) , the above inequalities imply \mathbb{V}_{\infty}(\rho)=\mathsf{Val}(\widehat{\left.\mathbf{b}\right|_{C}})\ .\qed Lemma 53 . \mathsf{Val}(\mathbf{b})\quad\geq\quad\sum_{C\in S/{\equiv_{(f,S)}}}\mathsf{Val}(\left.\mathbf{b}\right|_{C})\ . Proof. We write \mathbb{E}[\cdot] for \mathbb{E}^{\textup{{unif}}(f)}_{\mathbf{b}}\left[\cdot\right] for brevity. Recall from Corollary 40 that \mathbb{E}[X^{q}_{n}]=\mathbf{b}(q) for all q\in\mathsf{supp}(\mathbf{b}) and n\in\mathbb{N} . Hence, \mathbb{E}[X^{C}_{n}]=\mathbf{b}(C)=\left\lVert\left.\mathbf{b}\right|_{C}\right\rVert_{1} for every equivalence class C of \equiv_{(f,S)} and n\in\mathbb{N} . By the triangle inequality, we have |\mathbb{E}[X^{C}_{n}]-\mathbb{E}[X^{C}_{\infty}]|\leq\mathbb{E}[|X^{C}_{n}-X^{C}_{\infty}|]\ . Since (X^{C}_{n})_{n\in\mathbb{N}} converges to X^{C}_{\infty} in L^{1} (by Corollary 41 and the linearity of expectations), (\mathbb{E}[|X^{C}_{n}-X^{C}_{\infty}|])_{n\in\mathbb{N}} converges to 0 . Therefore, \mathbb{E}[X^{C}_{\infty}]=\left\lVert\left.\mathbf{b}\right|_{C}\right\rVert_{1} . Corollaries 49 and 52 together imply that \displaystyle\mathbb{E}[\mathbb{V}_{\infty}] \displaystyle=\sum_{C\in S/{\equiv_{(f,S)}}}\mathbb{E}[X^{C}_{\infty}]\cdot\mathsf{Val}(\widehat{\left.\mathbf{b}\right|_{C}}) \displaystyle=\sum_{C\in S/{\equiv_{(f,S)}}}\left\lVert\left.\mathbf{b}\right|_{C}\right\rVert_{1}\cdot\mathsf{Val}(\widehat{\left.\mathbf{b}\right|_{C}}) \displaystyle=\sum_{C\in S/{\equiv_{(f,S)}}}\mathsf{Val}(\left.\mathbf{b}\right|_{C})\ . Since (\mathbb{V}_{n})_{n\in\mathbb{N}} is a supermartingale that converges to \mathbb{V}_{\infty} in L^{1} , \mathsf{Val}(\mathbf{b})=\mathbb{E}[\mathbb{V}_{0}]\geq\lim_{n\to\infty}\mathbb{E}[\mathbb{V}_{n}]=\mathbb{E}[\mathbb{V}_{\infty}]=\sum_{C\in S/{\equiv_{(f,S)}}}\mathsf{Val}(\left.\mathbf{b}\right|_{C})\ .\qed Along with Lemma 42 , this concludes the proof of Theorem 11 . 7 Other related works Beyond the works discussed in the introduction, we mention connections to several related lines of research. Point-based value-iteration methods [ 25 ] and their variants provide practical algorithms for approximate POMDP solving, but without formal approximation guarantees: they are heuristics that work well empirically but may not converge to the true value. To the best of our knowledge, our result provides the first provable \varepsilon -approximation algorithm for a class strictly larger than deterministic POMDPs. The decidability landscape for POMDPs with \omega -regular objectives has been systematically studied [ 8 ] , establishing a detailed map of decidable and undecidable fragments. Our work contributes to this landscape by identifying a new decidable fragment for reachability. On the safety side, recent work [ 5 ] has shown that safety values (the complement of reachability) can be approximated in general POMDPs, contrasting with the undecidability of reachability. Appendix A Proof of Lemma 1 We restate and prove Lemma 1 , about the reduction to POMDPs with a single absorbing observable target state and a single absorbing observable state with value 0 . See 1 Proof. Our proof is in two steps: first, we show how to reduce to the case of a single target state, and then we show how to reduce to the case of a single state with value 0 . These two steps can then be composed to obtain the desired result. We construct a new POMDP \mathcal{P}^{\prime}=(Q^{\prime},A,O^{\prime},\mathbf{T}^{\prime}) with Q^{\prime}=(Q\setminus T)\cup\{\top\} , where \top is a fresh state not in Q , O^{\prime}=O\cup\{o_{\top}\} , where o_{\top} is a fresh observation not in O , and the transition function \mathbf{T}^{\prime} defined as follows: • for all q,q^{\prime}\in Q\setminus T , a\in A , and o\in O , \mathbf{T}^{\prime}(o,q^{\prime}\mid q,a)=\mathbf{T}(o,q^{\prime}\mid q,a), • for all q\in Q\setminus T and a\in A , \mathbf{T}^{\prime}(o_{\top},\top\mid q,a)=\sum_{o\in O,q^{\prime}\in T}\mathbf{T}(o,q^{\prime}\mid q,a), • for all a\in A , \mathbf{T}^{\prime}(o_{\top},\top\mid\top,a)=1. In particular, state \top is absorbing and observable in \mathcal{P}^{\prime} . Moreover, this construction can be done in linear time in the size of \mathcal{P} . We also define the initial belief \mathbf{b}^{\prime} in \mathcal{P}^{\prime} as \mathbf{b}^{\prime}(q)=\mathbf{b}(q) for all q\in Q\setminus T and \mathbf{b}^{\prime}(\top)=\sum_{q\in T}\mathbf{b}(q) . We prove that for any strategy \pi in \mathcal{P} , there is a corresponding strategy \pi^{\prime} in \mathcal{P}^{\prime} such that the probability of reaching T in \mathcal{P} under \pi from \mathbf{b} is equal to the probability of reaching \{\top\} in \mathcal{P}^{\prime} under \pi^{\prime} from \mathbf{b}^{\prime} , and vice versa. This implies in particular that the values of \mathcal{P} and \mathcal{P}^{\prime} with respect to the reachability objectives defined by T and \{\top\} , respectively, are equal (up to a natural change in the initial belief). Let \pi be a strategy in \mathcal{P} . We define a strategy \pi^{\prime} in \mathcal{P}^{\prime} as follows. Let a\in A be an arbitrary action. Intuitively, we make strategy \pi^{\prime} mimic strategy \pi until the target state \top is reached, after which \pi^{\prime} takes the arbitrary action a forever. Notice that if an observable history h^{\prime}\in(A\times O^{\prime})^{*} contains no occurrence of o_{\top} , then it can be seen as an observable history h\in(A\times O)^{*} in \mathcal{P} . We can therefore define \pi^{\prime} as \pi^{\prime}(h^{\prime})=\begin{cases}\pi(h^{\prime})&\text{if $h^{\prime}$ contains no occurrence of $o_{\top}$}\\ \delta_{a}&\text{otherwise,}\end{cases} where \delta_{a} is the Dirac distribution on a . Observe that \mathsf{Reach}_{T} is the disjoint union of the cylinders \mathsf{Cyl}(h) for all histories h\in Q\times(A\times O\times Q)^{*} that visit T a single time at their last state. For such an h , let h^{\prime} be the corresponding history in \mathcal{P}^{\prime} obtained by replacing the last observation with o_{\top} and the last state with \top . By construction, both \pi and \pi^{\prime} coincide exactly up to the first visit of T or \top , hence \mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Cyl}(h))=\mathbb{P}^{\pi^{\prime}}_{\mathbf{b}^{\prime}}(\mathsf{Cyl}(h^{\prime}))\ . Summing over all such disjoint cylinders \mathsf{Cyl}(h) , we obtain \mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Reach}_{T})=\mathbb{P}^{\pi^{\prime}}_{\mathbf{b}^{\prime}}(\mathsf{Reach}_{\{\top\}})\ . Conversely, let \pi^{\prime} be a strategy in \mathcal{P}^{\prime} . We define a strategy \pi in \mathcal{P} as follows. Let a\in A be an arbitrary action. Let h\in(A\times O)^{*} be an observable history in \mathcal{P} . We distinguish whether h is a possible observable history in \mathcal{P}^{\prime} or not. One can show that h is a possible observable history in \mathcal{P}^{\prime} if and only if there is a history \overline{h}\in Q\times(A\times O\times Q)^{*} in \mathcal{P} such that its projection to (A\times O)^{*} is h and none of the states in \overline{h} belong to T . We now define \pi on an observable history h as: • if h is a possible observable history in \mathcal{P}^{\prime} from \mathbf{b}^{\prime} , we define \pi(h)=\pi^{\prime}(h) ; • if not, it means that all histories \overline{h} with projection h have necessarily reached T in \mathcal{P} , so we may define \pi(h)=\delta_{a} . Once again, for every history h\in Q\times(A\times O\times Q)^{*} that visits T a single time at its last state, let h^{\prime} be the corresponding history in \mathcal{P}^{\prime} obtained by replacing the last observation with o_{\top} and the last state with \top . By construction, both \pi and \pi^{\prime} coincide exactly up to the first visit of T or \top , hence \mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Cyl}(h))=\mathbb{P}^{\pi^{\prime}}_{\mathbf{b}^{\prime}}(\mathsf{Cyl}(h^{\prime}))\ . Summing over all such disjoint cylinders \mathsf{Cyl}(h) , we obtain \mathbb{P}^{\pi}_{\mathbf{b}}(\mathsf{Reach}_{T})=\mathbb{P}^{\pi^{\prime}}_{\mathbf{b}^{\prime}}(\mathsf{Reach}_{\{\top\}})\ . We now turn to the second part of the lemma. We prove that we can assume without loss of generality that there is a single state \bot with value 0 , which is absorbing and observable. Let Q_{\bot}=\left\{q\in Q\ \middle|\ \mathsf{Val}^{\mathcal{P}}_{T}(\delta_{q})=0\right\} be the set of states with value 0 . They can be easily identified by standard graph algorithms, since they are the states from which there is no path to T in the underlying graph. We construct a new POMDP \mathcal{P}^{\prime}=(Q^{\prime},A,O^{\prime},\mathbf{T}^{\prime}) with Q^{\prime}=(Q\setminus Q_{\bot})\cup\{\bot\} , where \bot is a fresh state not in Q , O^{\prime}=O\cup\{o_{\bot}\} , where o_{\bot} is a fresh observation not in O , and the transition function \mathbf{T}^{\prime} defined as follows: • for all q,q^{\prime}\in Q\setminus Q_{\bot} , a\in A , and o\in O , \mathbf{T}^{\prime}(o,q^{\prime}\mid q,a)=\mathbf{T}(o,q^{\prime}\mid q,a), • for all q\in Q\setminus Q_{\bot} and a\in A , \mathbf{T}^{\prime}(o_{\bot},\bot\mid q,a)=\sum_{o\in O,q^{\prime}\in Q_{\bot}}\mathbf{T}(o,q^{\prime}\mid q,a), • for all a\in A , \mathbf{T}^{\prime}(o_{\bot},\bot\mid\bot,a)=1. By construction, state \bot is absorbing, observable, and the only state with value 0 in \mathcal{P}^{\prime} . Moreover, this construction can be done in linear time in the size of \mathcal{P} since Q_{\bot} can be identified in linear time (they are the states that cannot reach T in the underlying graph). The constructions are then the same as in the proof for the single target state: we build a correspondence between strategies in \mathcal{P} and strategies in \mathcal{P}^{\prime} that makes them coincide on all observable histories that have not surely reached Q_{\bot} or \bot yet. Since histories that reach Q_{\bot} or \bot have value 0 in both POMDPs, the probabilities of reaching the target sets are preserved. This shows in particular that the values of \mathcal{P} and \mathcal{P}^{\prime} with respect to the reachability objectives defined by T and \{\top\} , respectively, are equal. ∎