Research map / Reinforcement learning / MDPs and planning

Multi-Environment POMDPs with Finite-Horizon Objectives

NeurIPS 2026 · Reinforcement learning › MDPs and planning · approach: POMDP policy optimization · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Shows that finite-horizon value computation in multi-environment POMDPs is PSPACE-complete, gives a deterministic polynomial-space algorithm, and a practical pruning-based algorithm that outperforms the prior tool on RockSample, Robot Navigation and Identification benchmarks.

Problem

Computing the optimal value and policy of multi-environment POMDPs (adversarially chosen initial state among n environments) under finite-horizon objectives, where deterministic policies are insufficient and prior algorithms are slow and complexity was unknown.

Approach

Shows the problem is PSPACE-complete by proving a policy of degree at most n (mixture of n deterministic policies) suffices via Carathéodory, guesses multi-expected payoffs instead of policies, and gives a practical algorithm that builds and prunes the convex frontier of multi-expected payoffs bottom-up over horizons.

Key results

• The proposed practical algorithm solves e.g. RS_{4,1,2} (horizon 7) in 154.2 s where the baseline times out, and RN_{CIT,3} (horizon 2) in 0.0223 s vs 304.2 s for the baseline.
• Finite-horizon MEPOMDP threshold and approximate value problems are shown PSPACE-complete, even with n=1 for the approximate case.
• The practical algorithm solves instances with up to hundreds of states (e.g. 574 states in RS_{3,4,7}) at horizons up to 5-6, where the baseline times out on most.

Surprising findings

• Randomised (mixed) policies are strictly more powerful than deterministic ones in MEPOMDPs, unlike in single-environment POMDPs.
• The baseline tool's gap/tolerance parameter had almost no effect on its runtime or result in the experiments.

Limitations

• The pruning-based algorithm uses exponential space in the worst case.
• Scalability is limited mainly by horizon; longest solved horizon is 7.
• The space-efficient algorithm is asymptotically optimal but practically infeasible.

Experimental setup

Datasets: RockSample benchmark Robot Navigation maps (CIT, MIT, Pentagon, SUNYSB) Identification Friend or Foe benchmark

Benchmarks: RockSample Robot Navigation Identification (Friend or Foe)

Metrics: computation time (s) timeouts at 3600s

Baselines: Bovy et al. MEPOMDP tool

Builds on: POMDP belief updates multi-environment MDPs Bovy et al. MEPOMDP algorithm

Closest papers by meaning

• Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability (NeurIPS 2025 · similarity 0.91)
• Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives (AAAI 2025 · similarity 0.90)
• Sequential Monte Carlo for Policy Optimization in Continuous POMDPs (NeurIPS 2025 · similarity 0.89)
• Provable Representation with Efficient Planning for Partially Observable Reinforcement Learning (ICML 2024 · similarity 0.89)
• A Policy Gradient Method for Confounded POMDPs (ICLR 2024 · similarity 0.89)
• Belief-State Query Policies for User-Aligned POMDPs (NeurIPS 2024 · similarity 0.88)