On the Complexity Gap Between POMDPs and Multi-Environment POMDPs
Authors: Eline M. Bovy, Caleb Probine, Marnix Suilen, Ufuk Topcu, Nils Jansen
Organizations: Radboud University Nijmegen, The Netherlands · The University of Texas at Austin Austin, USA · University of Antwerp Antwerp, Belgium · Ruhr-University Bochum Bochum, Germany
Multi-environment POMDPs (ME-POMDPs) generalize POMDPs by encoding a finite set of possible environments, capturing model uncertainty. The finite-horizon robust reward maximization problem for a ME-POMDP asks for a policy that maximizes reward in the worst environment, and recent work has shown this problem to be PSPACE-complete. We expand the complexity landscape of ME-POMDPs by identifying which subclasses retain this PSPACE-completeness. In particular, we take subclasses of POMDPs that are tractable in the single-environment case, and investigate the computational complexity of these classes when extended to the multi-environment setting. We first prove the NP-completeness of multi-environment blind MDPs and deterministic POMDPs using a certain closure-under-mixture condition. We then prove PSPACE-completeness for a range of subclasses that do not satisfy that closure condition, yielding new complexity results for multi-observation POMDPs. Finally, we show existential theory of the reals (∃R)-completeness for numerous ME-POMDP problems under time-dependent Markovian policies or finite-state controllers that are NP-complete for standard POMDPs. These results reveal a subtle relationship between POMDP and ME-POMDP complexity that depends heavily on the subclasses involved.
Figures & tables
Figure 1. Known complexity results for finite-horizon ME-POMDPs. Dark blue and red lines correspond to problems with deterministic dynamics and Markovian policies, respectively, while bright blue lines correspond to problems with no dynamics or policy restrictions. An annotation “ X -hard” atop a line encodes that problems above that line are hard for the complexity class X . An annotation “in X ” below a line encodes that problems below the line are decidable in X .
Figure 2. Overview of ME-POMDP complexity including results we present. Dark blue and red lines correspond to problems with deterministic dynamics and Markovian policies, respectively, while bright blue lines correspond to problems with no dynamics or policy restrictions. An annotation “ X -hard” atop a line encodes that problems above that line are hard for the complexity class X . An annotation “in X ” below a line encodes that problems below the line are decidable in X .
Figure 3. Overview of the models considered in this paper.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4. Overview of the complexity results no restrictions
Figure 5. Overview of the complexity results determinsitic models
Figure 6. Overview of the complexity results memoryless policies
Figure 7. A fragment of an environment corresponding to the clause (x1∨¬x2) for the MO-SOMDP constructed in the proof of Proposition 6.2 . Lines leaving nodes correspond to actions, and small dots encode stochastic resolution of the transition dynamics. When an arrow leaves a node without a label, then all actions induce the same dynamics. Blue nodes correspond to satisfaction of the clause, while red nodes correspond to the clause not being satisfied yet.
Figure 8. A fragment of an environment in the MO-SOMDP constructed during the “splitting” procedure described in Remark 1 .
Figure 9. A component one can add to the start of a POMDP to increase the reward by 2m18n1 . The agent gets a reward of 1 with small probability. From the states in the set {s−,n,s+,n} , the agent transitions to the component shown in Figure 8 .