Multi-Environment POMDPs with Finite-Horizon Objectives

Léonard Brice, Filip Cano, Krishnendu Chatterjee, Thomas A. Henzinger, Stefanie Muroya · 2026

Read Multi-Environment POMDPs with Finite-Horizon Objectives by Léonard Brice, Filip Cano, Krishnendu Chatterjee, Thomas A. Henzinger, Stefanie Muroya (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-07537.txt.

Description

Brice and four colleagues study decision making under uncertainty when the agent cannot see the full state of its world. Their setting is multi environment partially observable Markov decision processes, where the starting environment is unknown and chosen adversarially. The paper focuses on finite horizon goals, asking for the optimal value and policy over a fixed number of steps.

Computing the optimal value and policy was already known to be PSPACE complete for ordinary partially observable processes. The authors prove the same PSPACE completeness holds in the broader multi environment setting. They also present a practical algorithm for the problem and test it on classical benchmarks. It significantly outperforms the only previously known algorithm for this setting. The result pins down the problem difficulty while giving practitioners a working method that beats the prior state of the art.

Catalog record

CREATORLéonard Brice, Filip Cano, Krishnendu Chatterjee, Thomas A. Henzinger, Stefanie Muroya
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE76 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.07537

Browse the full library · About the Tower of Babel