Research map / Reinforcement learning / MDPs and planning
Belief-State Query Policies for User-Aligned POMDPs
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 parameterized belief-state query (BSQ) policies for user-aligned planning in goal-oriented POMDPs, proves the expected cost is piecewise constant over a finite set of braid partitions, and proposes Partition Refinement Search (PRS) to optimize the parameters.
Problem
Specifying user requirements and preferences over agent behavior in partially observable settings without error-prone reward engineering or wireheading, and optimizing the threshold parameters of such rules.
Approach
Express user constraints as if-then-else rules over queries on the belief state with tunable thresholds; show the expected cost over threshold parameters is piecewise constant with finitely many braid partitions for finite horizons, and search these partitions with PRS.
Key results
- On Spaceship Repair, PRS-Bolt policies had 15.68% lower expected cost and 3.47% higher goal achievement than RCompliant.
- On Graph Rock Sample and Store Visit, RCompliant policies had more than triple the expected cost and about half the success rate of PRS policies.
- DESPOT achieved the goal only 0.5% of the time on Graph Rock Sample and matched user requirements only 7.3% of the time on Spaceship Repair.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| optimize BSQ parameters with PRS-Bolt instead of selecting random parameter values | user-aligned BSQ policies · Spaceship Repair | expected cost: 15.68% lower | Helped |
| optimize BSQ parameters with PRS-Bolt instead of selecting random parameter values | user-aligned BSQ policies · Spaceship Repair | goal achievement rate: 3.47% higher | Helped |
| optimize BSQ parameters with Nelder-Mead instead of PRS-Epsilon | BSQ policy search · Spaceship Repair | expected cost: 7.73% higher | Hurt |
| optimize BSQ parameters with Nelder-Mead instead of PRS-Epsilon | BSQ policy search · Spaceship Repair | goal achievement rate: 18.31% higher | Helped |
| optimize BSQ parameters with Particle Swarm instead of PRS-Epsilon | BSQ policy search · Spaceship Repair | expected cost: 7.73% higher | Hurt |
| optimize BSQ parameters with Particle Swarm instead of PRS-Epsilon | BSQ policy search · Spaceship Repair | goal achievement rate: 18.31% higher | Helped |
| use PRS-Bolt rather than random parameter selection | user-aligned BSQ policies · Graph Rock Sample | expected cost: more than triple | Helped |
| use PRS-Bolt rather than random parameter selection | user-aligned BSQ policies · Graph Rock Sample | success rate: only half | Helped |
| use PRS-Bolt rather than random parameter selection | user-aligned BSQ policies · Store Visit | expected cost: more than triple | Helped |
| use PRS-Bolt rather than random parameter selection | user-aligned BSQ policies · Store Visit | success rate: only half | Helped |
| use DESPOT without guidance from the parameterized BSQ policy | POMDP planning · Graph Rock Sample | goal achievement rate: 0.5% | Hurt |
| use DESPOT rather than the BSQ-guided approach | POMDP planning · Spaceship Repair variation | expected cost: lower expected cost of 20.0% | Helped |
Surprising findings
- Expected cost of parameterized BSQ policies is non-convex in its parameters despite being piecewise constant.
- DESPOT achieved lower expected cost on some problems but its policies often violated the user's requirements.
Limitations
- Belief updates are expensive; the approach relies on exact belief tracking and is not scaled to large problems without belief-state approximation.
- Each belief maps to a single action and the framework only handles state-based BSQs without deterministic functions or temporally extended requirements.
- Results are reported only for finite horizons (e.g., 12 and 100).
Experimental setup
Benchmarks: Lane Merger Spaceship Repair Graph Rock Sample Store Visit
Metrics: expected cost goal achievement rate user-alignment of trajectories
Baselines: RCompliant Nelder-Mead Particle Swarm DESPOT SARSOP
Builds on: POMDP DESPOT SARSOP Nelder-Mead Particle Swarm
Closest papers by meaning
- Revelations: A Decidable Class of POMDPs with Omega-Regular Objectives (AAAI 2025 · similarity 0.88)
- Multi-Environment POMDPs with Finite-Horizon Objectives (NeurIPS 2026 · similarity 0.88)
- Provable Representation with Efficient Planning for Partially Observable Reinforcement Learning (ICML 2024 · similarity 0.88)
- Factored Online Planning in Many-Agent POMDPs (AAAI 2024 · similarity 0.87)
- Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach (AAAI 2025 · similarity 0.87)
- Sequential Monte Carlo for Policy Optimization in Continuous POMDPs (NeurIPS 2025 · 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.