Research map / Probabilistic and scientific modeling / Variational and generative sampling
What type of inference is planning?
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 via variational inference that planning corresponds to a distinct entropy weighting, and develops value belief propagation (VBP), a loopy-BP analogue for approximate planning in factored MDPs.
Problem
Planning-as-inference is used inconsistently in the literature (marginal, MAP, MMAP), and its adequacy for planning is entangled with specific approximations; exact planning in factored MDPs is intractable due to exponential state spaces.
Approach
Using a variational framework, planning inference is shown to be exactly a different weighting of entropy terms (conditional entropy of next state given state and action); this yields a concave bound, a linear program for the additive-reward limit, and an approximate loopy-BP-style algorithm (VBP) for factored MDPs. Analysis shows MAP/MMAP are adequate only under low stochasticity.
Key results
- On IPPC 2011 domains, VBP is more consistent across stochasticity levels, matching the best method on each dataset, and outperforms SOGBOFA-LC in Game of Life and SysAdmin (average normalized entropy 0.18 and 0.23).
- On synthetic factored MDPs, VBP dominates all other inference types at high stochasticity, while exact MAP and MMAP dominate VBP at low stochasticity.
- Reactivity avoidance task: VBP achieves reward 1 while SOGBOFA-LC achieves 0.33.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use VBP instead of SOGBOFA-LC | Planning in the reactivity avoidance MDP · Reactivity avoidance MDP | reward: 0.33 -> 1 | Helped |
| use VBP rather than other inference types | Factored MDP planning · Synthetic MDPs with high stochasticity | utility estimation | Helped |
| use exact MAP or MMAP rather than VBP | Factored MDP planning · Synthetic MDPs with low stochasticity | utility estimation | Hurt |
| use planning inference rather than SOGBOFA-LC | Factored MDP planning · Game of Life and SysAdmin IPPC2011 domains | cumulative reward | Helped |
| use VBP rather than VI LP | Proposed planning framework · IPPC2011 domains | cumulative reward | Helped |
| use VBP across domains with varying stochasticity | Factored MDP planning · IPPC2011 domains | cumulative reward | Mixed |
Surprising findings
- MMAP, the tightest lower bound among common inference types, can be suboptimal under stochastic dynamics due to lack of reactivity to the environment.
Limitations
- VBP message updates are not guaranteed to converge; convergence relies on damping and annealing.
- Exact MMAP is intractable and the tractable bound may suffer local minima in non-concave optimization.
- Lambda must be set to a small nonzero value to avoid degeneracy in VBP.
Experimental setup
Datasets: ICAPS 2011 International Probabilistic Planning Competition (IPPC) domains 5,000 synthetic factored MDPs
Benchmarks: ICAPS 2011 IPPC domains synthetic factored MDPs
Metrics: cumulative reward utility estimation error advantage of next action vs optimal planning
Baselines: MFVI-Bwd CSVI-Bwd ARollout SOGBOFA-LC value iteration exact MAP exact MMAP
Builds on: loopy belief propagation Bethe free energy maximum entropy reinforcement learning RL as probabilistic inference determinization
Closest papers by meaning
- A Variational Perturbative Approach to Planning in Graph-Based Markov Decision Processes (AAAI 2020 · similarity 0.88)
- Rethinking Variational Inference for Probabilistic Programs with Stochastic Support (NeurIPS 2022 · similarity 0.87)
- From Stochastic Planning to Marginal MAP (NeurIPS 2018 · similarity 0.85)
- Probabilistic Inference in Reinforcement Learning Done Right (NeurIPS 2023 · similarity 0.85)
- A Bayesian Approach to Online Planning (ICML 2024 · similarity 0.84)
- Latent Plan Transformer for Trajectory Abstraction: Planning as Latent Space Inference (NeurIPS 2024 · similarity 0.83)
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.