We introduce posterior-deterministic POMDPs, and we show that for this class of 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. In particular, once the current state is known, it remains known forever. The class contains, for instance, multiple-environment MDPs equipped with a prior distribution over the environments, quasi-deterministic POMDPs, and the episodic version of the classical Tiger POMDP (Kaelbling et al. 1998).
Figures & tables
Figure 1Figure 2
Figure 5. Illustration of the statement of Lemma 6.3 (( 1 ) on the left and ( 2 ) on the right).
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge · Department of Electrical and Computer Engineering, University of British Columbia