Research map / Reinforcement learning / MDPs and planning
Multi-Environment POMDPs: Discrete Model Uncertainty Under Partial Observability
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.
Introduces adversarial-belief POMDPs and shows multi-environment POMDPs reduce to them and to restricted subclasses, then proposes AB-HSVI, a point-based value-iteration method with LP-based worst-case belief selection, for robust policies over discrete model sets.
Problem
Computing a single policy for a POMDP whose transition, observation, and reward models are uncertain within a finite discrete set, maximizing worst-case reward across the candidate POMDPs, where existing robust POMDP methods assume convex/rectangular uncertainty and are overly conservative.
Approach
Model ME-POMDPs as adversarial-belief POMDPs (adversary picks the initial belief from a set), show equivalence to one-sided POSGs, reduce general ME-POMDPs to PO-MEMDPs or MO-POMDPs while preserving optimal policies, and solve AB-POMDPs by combining alpha-vector value functions with LPs for the worst-case belief and agent mixing, embedded in HSVI (AB-HSVI).
Key results
- AB-HSVI computes robust values for multi-environment Bird and RockSample instances, with convergence time and gap increasing with the number of environments.
- AB-HSVI converges faster and returns higher values for MO-POMDP formulations than for PO-MEMDP formulations of the Bird problem, indicating uncertain observations are easier to handle than uncertain transitions.
- AB-POMDP formulations converge faster than ME-POMDP formulations in all but two RockSample instances, with values differing by less than epsilon.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase the number of environments | AB-HSVI · Bird problem and RockSample | convergence time | Hurt |
| Increase the number of environments | AB-HSVI · Bird problem and RockSample | convergence gap | Hurt |
| Fix transitions across environments instead of fixing observation functions | AB-HSVI on Bird problem · Bird problem | convergence time | Helped |
| Fix transitions across environments instead of fixing observation functions | AB-HSVI on Bird problem · Bird problem | robust value | Helped |
| Use the AB-POMDP formulation instead of the ME-POMDP formulation | AB-HSVI · RockSample | convergence time | Helped |
| Use the AB-POMDP formulation instead of the ME-POMDP formulation | AB-HSVI · RockSample | robust value | No clear effect |
| Compute a robust policy instead of solving individual environments separately | AB-HSVI · RockSample | computation time | Hurt |
| Use a robust policy instead of the optimal policy for an incorrectly assumed environment | AB-HSVI · RockSample | worst-case reward | Helped |
| Use a robust policy instead of solving individual environments separately | AB-HSVI · RockSample | expected reward | No clear effect |
Surprising findings
- Uncertain observation functions are easier to handle than uncertain transitions for AB-HSVI.
- Only 35 of 100 randomly generated 3-state, 3-action, 3-expert Bird PO-MEMDPs were non-trivial (solvable in over 30 seconds).
Limitations
- Scalability of AB-HSVI degrades substantially as the number of environments grows.
- Convergence time depends strongly on environment structure and is not monotone in problem size.
- Evaluation is limited to randomly generated and extended benchmarks; no existing ME-POMDP benchmarks exist.
Experimental setup
Datasets: Bird problem (randomized, extended from endangered bird preservation case study) RockSample (extended to multi-environment)
Benchmarks: Bird problem (BP) RockSample (RS) RockSample with fixed rock positions (RS^c)
Metrics: worst-case expected reward (value) convergence time upper-lower bound gap
Baselines: solving individual POMDPs naively (non-robust baseline) ME-POMDP formulation of AB-POMDP
Builds on: HSVI MEMDP one-sided POSG robust POMDP
Closest papers by meaning
- Multi-Environment POMDPs with Finite-Horizon Objectives (NeurIPS 2026 · similarity 0.91)
- Sequential Monte Carlo for Policy Optimization in Continuous POMDPs (NeurIPS 2025 · similarity 0.87)
- Learning POMDP World Models from Observations with Language-Model Priors (NeurIPS 2026 · similarity 0.87)
- Risk-Averse Online POMDP Planning via CVaR of the Immediate Cost with Performance Guarantees (NeurIPS 2026 · similarity 0.87)
- Simplifying Complex Observation Models in Continuous POMDP Planning with Probabilistic Guarantees and Practice (AAAI 2024 · similarity 0.87)
- Sample-Efficient Learning of POMDPs with Multiple Observations In Hindsight (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.