NeurIPS 2026Model-based RL Institute of Science and Technol Institute of Science and Technol IST Austria

Multi-Environment POMDPs with Finite-Horizon Objectives

Finite-horizon multi-environment POMDP optimization is PSPACE-complete, and a new practical algorithm significantly outperforms prior methods on benchmarks.

Léonard Brice, Filip Cano, Krishnendu Chatterjee, Thomas Henzinger, Stefanie Muroya

Published 2026Paris Poster Session 2 · Wed, Dec 9, 5:00 PM–7:00 PM local time · Paris Poster HallarXiv ↗OpenReview ↗

70%

OverallHighly rated

OverallHighly ratedVote to see the scoreThe exact score shows once you've voted, so every vote is your own call. The first half of each home page shelf shows its scores.

Readers

–

Only vote on papers you've read. Sign in with GitHub to vote.

AI panel5/20reviewers recommend it

lenient 1/5

medium 3/10

strict 1/5

AI panel?Vote to see what the 20 AI reviewers said

Panel consensus

A rigorous, practical algorithm for adversarial POMDPs earns praise, though its PSPACE-complete result and benchmark-only validation leave real-world impact unproven.

Abstract

Partially Observable Markov Decision Processes (POMDPs) are systems in which one agent interacts with a stochastic environment, and receives only partial information about the current state. In a multi-environment POMDP (MEPOMDP), the initial state is unknown, and assumed to be adversarially chosen. In this work we focus on computing the optimal value and policy in MEPOMDPs with finite-horizon objectives. That problem is known to be PSPACE-complete in POMDPs. Our main results are as follows: (1) we establish that it is also PSPACE-complete in the more general setting of MEPOMDPs; (2) we present a practical algorithm and evaluate it on classical benchmarks, significantly outperforming the only previously known algorithm.