Pith. sign in

REVIEW 5 major objections 5 minor 34 references

Lazy Heuristic Search for Solving POMDPs with Expensive-to-Compute Belief Transitions

T0 review · 5 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read POMDP planners that evaluate only the best action converge optimally with conservative Q-value estimates.

desk verdict A genuinely new lazy-evaluation idea for POMDP belief-space search with real speedups, but the theory-proof gap and a biased 'unbiased' estimator need fixing before the guarantees are taken at face value. read the letter →

arxiv 2506.00285 v1 pith:JIW5GZBQ submitted 2025-05-30 cs.RO

Muhammad Suhail Saleem , Rishi Veerapaneni , Maxim Likhachev This is my paper
classification cs.RO
keywords POMDPbeliefMDPlazysearchheuristictransitioncomputationQ-valueestimationrobotplanningunderuncertainty
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

In solving POMDPs as belief MDPs, heuristic search solvers such as RTDP-Bel and LAO* compute belief transitions for every action at every visited belief, even though the search only follows the successor beliefs of the single best action. The paper's central claim is that most of those transition computations are wasted, and that replacing the one-step lookahead with a fast Q-value estimator, then evaluating only the currently best action, lets the same search reach the same solution at much lower planning cost. To that end it introduces Lazy RTDP-Bel and Lazy LAO*, which defer all other action evaluations until a belief-state update changes the minimizing action. If the Q-value estimator never overestimates the optimal Q-value, the lazy planners are guaranteed to converge to the optimal policy. The idea is demonstrated on contact-rich manipulation, indoor 1D LiDAR navigation, and outdoor rough-terrain navigation, where planning-time savings range from roughly 40 percent to an order of magnitude while solution costs stay close to the vanilla planners.

What carries the argument

The load-bearing object is the Q-value estimator $\hat Q_{\mathrm{init}}(b,a)$, a cheap proxy for the one-step lookahead $Q_{\mathrm{init}}(b,a)=C(b,a)+\sum_{z\in Z}P(z|b,a)\,\mathrm{heur}(b^z_a)$, whose role is to rank actions without computing successor beliefs. The paper uses two practical estimators: the subsampling estimator $\hat Q_{\mathrm{init}}(b,a)=Q_{\mathrm{init}}(\hat b,a)$, where $\hat b$ keeps 15 percent of the particles of $b$ (with a bias-correction factor when the heuristic depends on belief entropy), and a QMDP-inspired estimator $\hat Q^{\mathrm{QMDP}}_{\mathrm{init}}(b,a)=\sum_s b(s)\left(c(s,a)+\sum_{s'}T(s,a,s')\mathrm{heur}(s')\right)$ for domains where the observation model dominates transition cost. The algorithmic mechanism is the lazy evaluation loop: initialize all actions with the estimator, evaluate only the minimizing action, update its Q-value, and repeat until the argmin stabilizes. A full-horizon lazy variant defers action-validity checks until a complete policy is computed, for domains where the expensive part is verifying feasibility rather than computing successor beliefs.

What would settle it

A reader could test Theorem 1 directly on a small two-action POMDP with a known optimal value, running Lazy LAO* with the conservative QMDP estimator; if the returned policy's expected cost exceeds $V^*(b_0)$ by any positive amount, the claimed convergence-to-optimality guarantee is false.

Watch

Extended reading notes

Core claim

The central discovery is that laziness in POMDP heuristic search can be organized around Q-value estimation. At a belief $b$, Lazy RTDP-Bel initializes $Q(b,a)=\hat Q_{\mathrm{init}}(b,a)$ for every action, evaluates only $a^*=\arg\min_a Q(b,a)$, and computes the expensive belief transitions for that action alone. If the resulting update changes the minimizing action, the newly best action is evaluated next, and the loop repeats until the best action is stable. Lazy LAO* incorporates the same loop into its solution-graph expansion, redefining a non-terminal tip state to include a belief whose best action is unevaluated, and stopping backups if a best action changes to an unevaluated one. Theorem 1 states that whenever $\hat Q_{\mathrm{init}}(b,a)\le Q^*(b,a)$ for all belief-action pairs, both lazy algorithms converge to the optimal policy, because backups only raise underestimated values toward $Q^*$ and eventually expose any suboptimal action that initially looked best.

Load-bearing premise

The optimality guarantee holds only if the fast Q-value guess never overestimates the true optimal Q-value, yet the fast estimator used in the main experiments is explicitly not guaranteed to have that property, so the measured speedups and solution quality rest on the guess ranking actions well in practice.

Editorial extensions

If this is right

  • Lazy RTDP-Bel and Lazy LAO* evaluate fewer belief transitions per visited belief and can match the solution cost of the vanilla solvers; in indoor navigation with stochastic transitions, planning time drops by roughly a factor of five.
  • In contact-rich pose estimation, the lazy planners solve all 100 runs within the timeout while the vanilla planners solve 87 to 93 percent, at nearly identical expected cost, and the savings grow with initial pose uncertainty.
  • In outdoor rough-terrain navigation, full-horizon lazy variants raise success rates from below 10 percent to roughly 80 to 90 percent and cut planning time by about an order of magnitude relative to the one-step lazy planners.
  • When $\hat Q_{\mathrm{init}}$ is a lower bound on $Q^*$, both lazy planners inherit the optimality guarantee of the vanilla algorithms (Theorem 1); the conservative QMDP estimator satisfies this condition when the underlying state heuristic is admissible.
  • The deferral mechanism applies to other heuristic search solvers for POMDPs and to MDPs, so the same principle can be reused wherever action evaluation is expensive.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because the main experiments use the non-conservative subsampling estimator, the reported speedups demonstrate what an approximate estimator can do in practice rather than exercising the Theorem 1 guarantee; the appendix's probabilistically conservative estimator shows a modest speedup loss, suggesting a tunable trade-off between guarantee and speed.
  • The benefit of laziness should grow with the number of actions that never enter the final policy and with the support size of beliefs; the manipulation results, where speedups increase with pose uncertainty, are consistent with this prediction.
  • A testable extension is to replace the hand-built estimators with learned Q-value predictors: use the learned ranking to select the one action to evaluate, and only query the expensive model for that action, which could extend the method to problems where subsampling is biased.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

Summary. This paper proposes Lazy RTDP-Bel and Lazy LAO*, modifications of two heuristic-search POMDP solvers that defer computing belief transitions for non-best actions. The algorithms initialize Q-values with a cheap estimator \hat Q_init, evaluate only the action with minimal Q, and re-evaluate actions only when the minimizer changes. Theorem 1 states that convergence to an optimal policy is guaranteed when \hat Q_init is a conservative underestimate of Q*. The authors describe subsampling and QMDP-based estimators and report experiments on manipulation for pose estimation, indoor navigation, and outdoor rough-terrain navigation, where lazy planners reduce planning time while maintaining similar solution cost.

Significance. The lazy-deferral idea addresses a real bottleneck for POMDPs with expensive transition and observation models, and the paper gives a useful catalogue of Q-estimators, including a full-horizon lazy variant for feasibility-dominated problems. The algorithms are clearly described and the domain experiments are nontrivial. However, the central optimality result is conditional and, as the paper itself acknowledges, the primary estimator used in the experiments does not satisfy the required condition; the experimental section also does not isolate the effect of laziness from the effect of belief subsampling. These issues are fixable but currently prevent the reported speedups from being interpreted as validated by the theory.

major comments (5)
  1. [Section 4 (Theorem 1); Section 4.3; Appendix] Theorem 1's optimality guarantee requires \hat Q_init(b,a) ≤ Q*(b,a) for all b,a, but the experiments that claim optimal-quality maintenance do not meet this precondition. Section 4.3 states that the subsampled estimator is 'not guaranteed to be conservative,' and the manipulation domain uses a scaled belief-entropy heuristic that the appendix itself describes as inadmissible. Consequently, Tables 1 and 5 are not covered by the theorem. Please either use a provably conservative estimator in the optimality experiments or relabel the results as heuristic/approximate and state that Theorem 1 is not invoked.
  2. [Appendix, Eq. (8)] The claim that Eq. (8) is an unbiased estimator of Q_init is mathematically incorrect. Because the term (n/k)^2 |\hat H_z^a|^2 enters nonlinearly, E[(n/k)^2 |\hat H_z^a|^2] = (n/k)^2 (Var(|\hat H_z^a|) + |H_z^a|^2), which is strictly larger than |H_z^a|^2 whenever the sampled count has positive variance. The estimator therefore has a positive bias and can exceed Q*, violating the conservativeness assumption of Theorem 1. This affects the manipulation-domain results in Tables 1 and 5, which use this estimator.
  3. [Appendix, Eqs. (11)-(13)] The 'probabilistically conservative' estimator uses Hoeffding's inequality separately for each observation z and then claims 95% confidence that \hat Q_init ≤ Q_init. Without a union bound over observations, the simultaneous confidence is at least 1 - 0.05|Z|, which is below 95% whenever |Z|>1. The construction should replace the constant 1.22 with a value that accounts for the number of observations (e.g., via a union bound) or otherwise establish simultaneous control.
  4. [Section 5, Tables 1-5] The experiments do not separate the contribution of laziness from the contribution of the 15% belief-subsampling approximation. Since the lazy planners use \hat Q_init with only 15% of particles while the vanilla baselines compute exact transitions, reductions in planning time could be due largely to the cheaper approximation rather than to deferred evaluations. Please add ablations that hold the estimator fixed (e.g., lazy with exact Q_init, and vanilla with the same subsampled estimator), and report error bars or confidence intervals for the averages in Tables 1-5.
  5. [Theorem 1] The proof of Theorem 1 is only a sketch and does not establish the key lemmas needed for the lazy algorithms: that the do-while loop terminates, that previously evaluated actions are always re-backed-up when successor values change, and that the value estimates converge to V* from below under the conservative-estimator assumption. As the theorem is the paper's main theoretical claim, a complete proof should be provided or the theorem should be stated with clearly listed assumptions and a reference to a full proof.
minor comments (5)
  1. [Section 4.3 and Section 5] The notation \hat Q_init is used both for a general estimator and for the specific subsampled estimator, and the same symbol denotes different estimators across domains; please define each instance explicitly when it first appears in the experiments.
  2. [Section 5] The statement that the framework 'assume[s] perfect observations' is confusing because the evaluated domains are POMDPs with observation models; please clarify what 'perfect observations' means in this context.
  3. [Abstract and Section 4.3] The abstract's claim that Q-value estimates are 'equivalent to heuristic functions' is stronger than what Section 4.3 establishes, which is an analogy; consider rewording to avoid overclaiming.
  4. [Appendix, Eq. (7)] The derivation of Eq. (7) treats particle selection as independent sampling, but the algorithm samples a subset without replacement; the distinction should be addressed because it affects the variance and unbiasedness statements.
  5. [Tables 2-4] The tables would benefit from reporting the number of belief-transition evaluations, which is the direct measure of the savings claimed by lazy search, alongside planning time.

Circularity Check

0 steps flagged · score 2.0 of 10

No circular derivation: the lazy-search optimality guarantee is conditional on a conservative Q-estimator, and the estimators are built from externally supplied heuristics and POMDP model structure. The Appendix's statistical claims are correctness risks, not circularity.

full rationale

The derivation chain is not circular. Theorem 1 is explicitly conditional: "If the estimator Qhat_init is an underestimate, i.e., Qhat_init(b,a) <= Q*(b,a) ... then both Lazy RTDP-Bel and Lazy LAO* will converge to the optimal policy." The lazy algorithms do not fit their Q-estimators to the target value function; Qhat_init is constructed from the POMDP's own cost, transition, and observation models plus an externally supplied heuristic (e.g., QMDP, distance-to-go, or scaled particle count). No equation in Section 4 or the Appendix reduces the reported speedups or solution costs to a fitted parameter. The paper explicitly acknowledges that the main subsampling estimator is not conservative: "Although effective, the subsampled estimates are not guaranteed to be conservative," so the main experiments are presented as a heuristic application rather than as a claim that Theorem 1 covers them. The self-citations to Saleem et al. 2023/2024 (manipulation problem formulation), Veerapaneni et al. 2023 (learned heuristics as a possible extension), and Kim et al. 2019 (heuristic inflation) are not load-bearing for the central lazy-search result. The Appendix's claims that Eq. 8 is unbiased and that Eq. 13 is conservative with 95% confidence are mathematically questionable (Jensen bias in the squared term and no union bound over observations), but these are correctness risks rather than circularity and do not make the derivation equivalent to its inputs. Score 2 reflects only minor, non-load-bearing self-citations; the central derivation has independent content.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

The central claim rests on the assumption that a fast Q-value estimator can correctly prioritize actions, and that the underlying search algorithms retain their convergence properties under lazy evaluation. The main free parameters are the heuristic scaling alpha and the sub-sampling ratio, both set by hand without sensitivity analysis.

free parameters (3)
  • alpha (heuristic scaling) = not reported
    Active localization heuristic heur(b)=alpha |H| uses an unspecified scaling factor; it appears in Qinit and the subsampled estimator, and its value affects estimator quality.
  • subsampling ratio Delta = 15% of belief support
    The estimator samples beliefs down to 15% of particles; this threshold is chosen by hand and controls the trade-off between estimator speed and accuracy.
  • Hoeffding confidence level = 95%
    The probabilistically conservative estimator uses a 95% confidence bound; not a scientific constant but a chosen parameter.
assumptions (4)
  • standard math RTDP-Bel and LAO* converge to optimal policies with admissible heuristics
    Stated in background, used as the foundation for Theorem 1.
  • ad hoc to paper Qhat(b,a) <= Q*(b,a) for all b,a (conservativeness)
    Theorem 1 assumes this; the authors note it is not satisfied by the main subsampling estimator.
  • domain assumption heur(b)=E_{s~b} heur(s)
    Required for the vanilla subsampling estimator to be effective; the authors state this property holds for many robotics heuristics but not all.
  • domain assumption Observations are perfect (deterministic given state and action)
    Stated in Section 5; simplifies belief updates, and the paper claims it is not a limitation but all experiments use it.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Lazy Heuristic Search for Solving POMDPs with Expensive-to-Compute Belief Transitions." pith.science (2026). https://pith.science/paper/JIW5GZBQ

@misc{pith2026250600285,
  author       = {Pith},
  title        = {Pith review of: Lazy Heuristic Search for Solving POMDPs with Expensive-to-Compute Belief Transitions},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/JIW5GZBQ}},
  note         = {Machine review of arXiv:2506.00285}
}
read the original abstract

Heuristic search solvers like RTDP-Bel and LAO* have proven effective for computing optimal and bounded sub-optimal solutions for Partially Observable Markov Decision Processes (POMDPs), which are typically formulated as belief MDPs. A belief represents a probability distribution over possible system states. Given a parent belief and an action, computing belief state transitions involves Bayesian updates that combine the transition and observation models of the POMDP to determine successor beliefs and their transition probabilities. However, there is a class of problems, specifically in robotics, where computing these transitions can be prohibitively expensive due to costly physics simulations, raycasting, or expensive collision checks required by the underlying transition and observation models, leading to long planning times. To address this challenge, we propose Lazy RTDP-Bel and Lazy LAO*, which defer computing expensive belief state transitions by leveraging Q-value estimation, significantly reducing planning time. We demonstrate the superior performance of the proposed lazy planners in domains such as contact-rich manipulation for pose estimation, outdoor navigation in rough terrain, and indoor navigation with a 1-D LiDAR sensor. Additionally, we discuss practical Q-value estimation techniques for commonly encountered problem classes that our lazy planners can leverage. Our results show that lazy heuristic search methods dramatically improve planning speed by postponing expensive belief transition evaluations while maintaining solution quality.

Figures

Figures reproduced from arXiv: 2506.00285 by the authors.

Figure 1
Figure 1. Planning times as a function of object pose uncer [PITH_FULL_IMAGE:figures/full_fig_p007_1.png] view at source ↗
Figure 2
Figure 2. The robot utilizing contact observations from different actions to reduce uncertainty about the pose of the object of [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Visualization of the indoor (left) and outdoor nav [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

34 extracted references · 27 canonical work pages

  1. [1]

    G.; Bradtke, S

    Barto, A. G.; Bradtke, S. J.; and Singh, S. P. 1995. Learning to act using real-time dynamic programming. Artificial intelligence, 72(1-2): 81--138

    1995

  2. [2]

    Bertsekas, D. 2012. Dynamic programming and optimal control: Volume I, volume 4. Athena scientific

    work page 2012

  3. [3]

    Bhardwaj, M.; Choudhury, S.; Boots, B.; and Srinivasa, S. 2021. Leveraging experience in lazy search. Autonomous Robots, 45(7): 979--996

    work page 2021

  4. [4]

    Bonet, B.; and Geffner, H. 2009. Solving POMDPs: RTDP-Bel vs. Point-based Algorithms. In IJCAI, 1641--1646

    work page 2009

  5. [5]

    Brechtel, S.; Gindele, T.; and Dillmann, R. 2014. Probabilistic decision-making under uncertainty for autonomous driving using continuous POMDPs. In 17th international IEEE conference on intelligent transportation systems (ITSC)

    work page 2014

  6. [6]

    Cohen, B.; Phillips, M.; and Likhachev, M. 2015. Planning single-arm manipulations with n-arm robots. In Proceedings of the International Symposium on Combinatorial Search, volume 6, 226--227

    work page 2015

  7. [7]

    Dellin, C.; and Srinivasa, S. 2016. A unifying formalism for shortest path problems with expensive edge evaluations via lazy best-first search over paths with edge selectors. In Proceedings of the international conference on automated planning and scheduling, volume 26, 459--467

    work page 2016

  8. [8]

    A.; and Zilberstein, S

    Hansen, E. A.; and Zilberstein, S. 2001. LAO*: A heuristic search algorithm that finds solutions with loops. Artificial Intelligence, 129(1-2): 35--62

    work page 2001

Show all 34 references
  1. [9]

    Hauskrecht, M. 2000. Value-function approximations for partially observable Markov decision processes. Journal of artificial intelligence research, 13: 33--94

    2000

  2. [10]

    P.; Littman, M

    Kaelbling, L. P.; Littman, M. L.; and Cassandra, A. R. 1998. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2): 99--134

    1998

  3. [11]

    Kim, S.-K.; Salzman, O.; and Likhachev, M. 2019. POMHDP: Search-based belief space planning using multiple heuristics. In Proceedings of the international conference on automated planning and scheduling, volume 29

    2019

  4. [12]

    Kurniawati, H.; Hsu, D.; and Lee, W. S. 2008. Sarsop: Efficient point-based pomdp planning by approximating optimally reachable belief spaces. In Robotics: Science and systems, volume 2008. Citeseer

    2008

  5. [13]

    Kurniawati, H.; and Yadav, V. 2016. An online POMDP solver for uncertainty planning in dynamic environment. In Robotics Research: The 16th International Symposium ISRR, 611--629. Springer

    2016

  6. [14]

    Lee, J.; Kim, G.-H.; Poupart, P.; and Kim, K.-E. 2018. Monte-Carlo tree search for constrained POMDPs. Advances in Neural Information Processing Systems, 31

    2018

  7. [15]

    Mandalika, A.; Choudhury, S.; Salzman, O.; and Srinivasa, S. 2019. Generalized lazy search for robot motion planning: Interleaving search and edge evaluation via event-based toggles. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 29...

    2019

  8. [16]

    Mandalika, A.; Salzman, O.; and Srinivasa, S. 2018. Lazy receding horizon A* for efficient path planning in graphs with expensive-to-evaluate edges. In Proceedings of the international conference on automated planning and scheduling, volume 28, 476--484

    2018

  9. [17]

    Nilsson, N. J. 2014. Principles of artificial intelligence. Morgan Kaufmann

    2014

  10. [18]

    Pajarinen, J.; and Kyrki, V. 2017. Robotic manipulation of multiple objects as a POMDP. Artificial Intelligence, 247

    2017

  11. [19]

    Pineau, J.; Gordon, G.; Thrun, S.; et al. 2003. Point-based value iteration: An anytime algorithm for POMDPs. In Ijcai, volume 3, 1025--1032

    2003

  12. [20]

    Ross, S.; Chaib-Draa, B.; et al. 2007. AEMS: An anytime online search algorithm for approximate policy refinement in large POMDPs. In IJCAI, 2592--2598

    2007

  13. [21]

    S.; Veerapaneni, R.; and Likhachev, M

    Saleem, M. S.; Veerapaneni, R.; and Likhachev, M. 2023. Preprocessing-based planning for utilizing contacts in semi-structured high-precision insertion tasks. IEEE Robotics and Automation Letters, 8(11): 6947--6954

    2023

  14. [22]

    S.; Veerapaneni, R.; and Likhachev, M

    Saleem, M. S.; Veerapaneni, R.; and Likhachev, M. 2024. A POMDP-based hierarchical planning framework for manipulation under pose uncertainty. arXiv preprint arXiv:2409.18775

    2024 arXiv

  15. [23]

    Satia, J.; and Lave, R. 1973. Markovian decision processes with probabilistic observation of states. Management Science, 20(1): 1--13

    1973

  16. [24]

    Shani, G.; Pineau, J.; and Kaplow, R. 2013. A survey of point-based POMDP solvers. Autonomous Agents and Multi-Agent Systems, 27: 1--51

    2013

  17. [25]

    Silver, D.; and Veness, J. 2010. Monte-Carlo planning in large POMDPs. Advances in neural information processing systems, 23

    2010

  18. [26]

    Smith, T.; and Simmons, R. 2012. Heuristic search value iteration for POMDPs. arXiv preprint arXiv:1207.4166

    2012 arXiv

  19. [27]

    Somani, A.; Ye, N.; Hsu, D.; and Lee, W. S. 2013. DESPOT: Online POMDP planning with regularization. Advances in neural information processing systems, 26

    2013

  20. [28]

    Spaan, M. T. 2008. Cooperative active perception using POMDPs. In AAAI 2008 workshop on advancements in POMDP solvers

    2008

  21. [29]

    Takahashi, T.; Sun, H.; Tian, D.; and Wang, Y. 2019. Learning heuristic functions for mobile robot path planning using deep neural networks. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 29, 764--772

    2019

  22. [30]

    S.; and Likhachev, M

    Veerapaneni, R.; Saleem, M. S.; and Likhachev, M. 2023. Learning local heuristics for search-based navigation planning. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 33, 634--638

    2023

  23. [31]

    Warnquist, H.; Kvarnstr \"o m, J.; and Doherty, P. 2010. Iterative Bounding LAO. In ECAI 2010, 341--346. IOS Press

    2010

  24. [32]

    Washington, R. 1997. BI-POMDP: Bounded, incremental partially-observable Markov-model planning. In European Conference on Planning, 440--451. Springer

    1997

  25. [33]

    , " * write output.state after.block = add.period write newline

    ENTRY address archivePrefix author booktitle chapter edition editor eid eprint howpublished institution isbn journal key month note number organization pages publisher school series title type volume year label extra.label sort.label short.list INTEGERS output.state before.all...

  26. [34]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 gl...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.