PSPACE-Completeness of Multi-Environment POMDPs

A new paper establishes that computing optimal values and policies in multi-environment partially observable Markov decision processes (MEPOMDPs) with finite-horizon objectives is PSPACE-complete. This extends the known PSPACE-completeness result for standard POMDPs to the more general MEPOMDP setting, where the initial state is unknown and adversarially chosen. The authors also present a practical algorithm that significantly outperforms the only previously known algorithm on classical benchmarks. The work is published on arXiv under the Computer Science > Artificial Intelligence category.