Complexity differences found between single and multi-environment decision models
On the Complexity Gap Between POMDPs and Multi-Environment POMDPs
Artificial Intelligence
Summary
Planning in uncertain settings can be very hard, especially when there are multiple possible worlds to consider. The authors studied mathematical decision models called POMDPs and their extensions to multiple environments (ME-POMDPs). They showed that some simpler problems become much harder when you consider multiple environments, with complexity jumping from easier classes like NP to much tougher classes like PSPACE and the existential theory of the reals. This means that solving these problems efficiently depends a lot on the exact type of uncertainties and model restrictions involved.
What this means in practice
- •For robotics engineers: Understand which robot decision-making models become computationally harder when accounting for uncertain environments to better design planning algorithms.
- •For autonomous system developers: Identify when robust policy computation in uncertain multi-environment settings escalates in computational difficulty, guiding algorithm choice for safety-critical systems.
A theory result. No direct application yet.
Authors
Eline M. Bovy, Caleb Probine, Marnix Suilen, Ufuk Topcu, Nils Jansen
Abstract
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 $\mathsf{PSPACE}$-complete. We expand the complexity landscape of ME-POMDPs by identifying which subclasses retain this $\mathsf{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 $\mathsf{NP}$-completeness of multi-environment blind MDPs and deterministic POMDPs using a certain closure-under-mixture condition. We then prove $\mathsf{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 ($\exists \mathbb{R}$)-completeness for numerous ME-POMDP problems under time-dependent Markovian policies or finite-state controllers that are $\mathsf{NP}$-complete for standard POMDPs. These results reveal a subtle relationship between POMDP and ME-POMDP complexity that depends heavily on the subclasses involved.