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
| CREATOR | Léonard Brice, Filip Cano, Krishnendu Chatterjee, Thomas A. Henzinger, Stefanie Muroya |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 76 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.07537