REVIEW 4 major objections 6 minor 25 references
Model Predictive Trees: Sample-Efficient Receding Horizon Planning with Reusable Tree Search
T0 review · 4 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read The paper establishes that reusing the whole selected search tree from the previous planning round, rather than just the best trajectory, improves planning quality and sample efficiency, with a proven error bound when dynamics drift slowly.
desk verdict Subtree reuse is a real step forward for receding-horizon tree search, and the paper earns a serious review despite the theory being only loosely tied to the hardware regime. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The machinery pairs UCT tree search with a contraction-theoretic tracking controller. UCT builds a decision tree by $L$ fixed-depth rollouts, selecting child nodes with the upper-confidence-bound score $c.V/c.N + \varepsilon\sqrt{\log(p.N)/c.N}$. The novel piece is the trimming operation that makes the previous iteration's best child the next root, preserving the whole subtree. Stability is supplied by a discrete-time Riccati feedback law $u_{k+1}=u^d_{k+1}-K(x_k-x^d_k)$ whose gain $K=(R+B^\top M B)^{-1}B^\top M A$ solves a Discrete Algebraic Riccati Equation; contraction of the closed loop gives the error bound that ties reuse depth $K$ to the disturbance drift rate $\eta$. The tree reset threshold $\tau$ is the safety valve that discards the reused tree when simulated and physical states diverge beyond a set tolerance.
What would settle it
Take a testbed where the per-step disturbance drift $\eta$ can be set externally, hold the tree depth $K$ fixed, and measure whether the steady-state tracking error follows $\sqrt{\bar{m}/m}\,((K+1)\eta+\epsilon)/(1-\alpha)$; a second check is to replace the reused subtree with a compact summary of its node values and see whether the reported $29.9\%$ advantage over hotstarting disappears.
Extended reading notes
Core claim
The central claim is that tree reuse should be structural rather than summary-based. Existing sampling-based receding-horizon solvers such as cross-entropy motion planning keep only the best trajectory (or the mean of elite samples) from the previous solve; MPT instead carries over the entire optimal subtree, so the next UCT search starts with a rich set of evaluated nodes. The paper proves (Theorem 4) that this reuse does not destabilize the closed loop: under the assumption that the disturbance changes by at most $\eta$ per time step and the dynamics estimate is within $\epsilon$, the steady-state tracking error is at most $\sqrt{\bar{m}/m}\,((K+1)\eta+\epsilon)/(1-\alpha)$, where $K$ is the search depth and $\alpha$ is the contraction rate of a Riccati feedback controller. The bound makes the limitation explicit: the deeper the reused tree, the more out-of-date the dynamics estimates inside it, so depth must be chosen relative to how fast the dynamics drift. In the nonprehensile pushing experiments, the reuse policy yields a $29.9\%$ higher average value than the best hotstarting baseline and reaches a value of 80 with $L=180$ simulations, versus more than 3000 for the hotstarting cross-entropy baseline.
Load-bearing premise
The load-bearing premise is that the unknown gap between model and reality changes slowly and is estimated accurately, because if either fails the tracking bound grows and, as in the hardware contact experiment, the tree-reset threshold rather than the theory is what prevents divergence.
Editorial extensions
If this is right
- At a representative initial condition, MPT reaches a cumulative value of 80 with about $L=180$ simulations per iteration, whereas the hotstarting cross-entropy baseline needs about $L=3000$ and plain UCT does not catch up within 30,000, so the reuse rule is what buys sample efficiency.
- The bound in Eq. (10) is a tuning rule: given a desired steady-state error, the admissible search depth $K$ shrinks as the disturbance drift rate $\eta$ grows, so a planner can set depth from an online estimate of dynamics drift.
- Because the entire subtree is kept, the next search inherits both high-value branches to refine and low-value branches to avoid, which concentrates the simulation budget and explains the much lower variance in value estimates seen in Fig. 4.
- The tree reset threshold $\tau$ is the practical complement to the theory: when simulated and physical states diverge, discarding the tree restores consistency, bounding the damage from unmodeled dynamics at the cost of lost reuse.
Reading between the lines
- An extension the paper leaves implicit is to make search depth adaptive: because Eq. (10) links admissible $K$ to the drift rate $\eta$, a planner that shortens its tree when the dynamics are changing fast and lengthens it when they are quiet would directly exploit the tradeoff.
- The same reuse logic could apply to learned dynamics or value models: the $\epsilon$ term already accounts for estimation error, so replacing the fixed dynamics estimate with an online learner would change the shape of the bound without removing the need for it.
- The reported advantage is over a baseline that summarizes the previous solution; the paper does not test whether a cheaper summary, such as keeping a handful of elite trajectories, would capture much of the same benefit, so the marginal value of full subtree reuse versus partial reuse is not yet isolated.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces Model Predictive Trees (MPT), a receding-horizon tree search planner that reuses the entire selected subtree from the previous planning iteration rather than only the best trajectory. The authors provide a contraction-theoretic analysis (Theorem 3 and Theorem 4) intended to bound the steady-state tracking error of the closed-loop system when the dynamics estimate is stale, and they report numerical experiments against UCT, CEM, and CEM-Reuse, as well as a hardware demonstration on an autonomous vehicle pushing a barrel. The central claims are that subtree reuse improves sample efficiency and solution quality, and that the induced tracking error is bounded under slowly time-varying disturbances.
Significance. If the theoretical guarantee and the experimental results hold, the paper makes a useful contribution to receding-horizon planning: the idea of reusing an entire subtree, including low-value branches, is a sensible and potentially important extension of hotstarting. The sample-efficiency results are striking (e.g., MPT reaching value 80 with L=180 versus 3000+ for CEM-Reuse), and the hardware demonstration adds credibility to the practical relevance. The contraction-based stability analysis is a reasonable framework, and the proof of Theorem 3 appears sound under its assumptions. However, the main theoretical result (Theorem 4) has a gap concerning the mismatch between the model used by the controller and the model used to build the reused tree, and the theory does not account for the reset mechanism that is active in the hardware experiment. These issues prevent the paper from fully establishing both the stability guarantee and its empirical validation in the slow-dynamics regime.
major comments (4)
- [Sec. III-B, Theorem 4 and Algorithm 1] The proof of Theorem 4 assumes that the desired trajectory satisfies the dynamics with the past estimate \hat{d}_i, but the controller in Algorithm 1, line 10, uses the current estimate \hat{F}_k (i.e., \hat{d}_k). Consequently, the desired trajectory is not a solution of the nominal system used in the feedback law, and the perturbation relative to that system includes the term \hat{d}_k(x^d_k,u^d_{k+1}) - \hat{d}_i(x^d_k,u^d_{k+1}), which is not accounted for in the bound (K+1)η+ε. Without an additional assumption that the controller uses the same old estimate \hat{d}_i, or a bound on the drift of the estimates themselves, Eq. (10) does not bound the tracking error of the implemented algorithm. This is load-bearing for the claimed stability guarantee.
- [Sec. IV-E and Algorithm 1, lines 14-16] The reset threshold τ is not present in the theoretical analysis. The hardware experiment reports three tree resets when the simulated and physical states diverge, and the paper acknowledges that Assumption 2 is violated due to friction, deformation, and other unmodeled effects. Thus, in the most challenging demonstrated setting, the stability is attributable to the reset heuristic rather than to the reuse analysis, and Theorem 4 provides no condition under which resets are needed or a bound on their effect. The authors should either extend the theory to incorporate the reset mechanism or explicitly state that Theorem 4 applies only in the no-reset regime, and provide a separate experimental validation of that regime.
- [Sec. IV-C, IV-D, and Theorem 4] The numerical experiments appear to use the same contact model for both the planner and the simulator, with no time-varying disturbance injected. If η=ε=0, then Theorem 4's bound becomes trivial and the experiments do not exercise the slowly-varying-dynamics regime that the theory addresses. The hardware experiment, by contrast, violates Assumption 2. To support the theoretical claim, the paper should include a simulation study with a deliberately time-varying disturbance that satisfies Assumption 2 and show that the observed tracking error respects the predicted (K+1)η+ε dependence.
- [Sec. IV-E] The statement that 'state-of-the-art baselines are either too sample-inefficient or unable to plan through the dynamics' is not supported by any experiment: no baseline is run on the hardware testbed and no quantitative comparison is provided for the hardware task. This claim exceeds the evidence presented and should be removed or backed by comparative data.
minor comments (6)
- [Sec. III, notation] The notation for the uniform bounds of the contraction metric is unclear: the text writes 'm In ⪯ M ⪯ mIn' with the same symbol m for both bounds, which makes the factor sqrt(m/m) in Eq. (10) appear to be 1. Please use distinct symbols, e.g., \underline{m} and \overline{m}, throughout.
- [Algorithm 1 and Sec. II-B] The search depth K is defined as the depth of the tree, but the UCT search loop runs for j = k, ..., K+k, which creates K+1 levels of nodes. This off-by-one inconsistency makes the timing argument in the proof of Theorem 4 harder to follow; please align the pseudocode and the theorem's indexing.
- [Fig. 4 and Sec. IV-D] The x-axis range of Fig. 4 is not specified, and the claim that UCT requires '>30000' simulations to reach V=80 is only meaningful if the reader knows the extent of the tested range. Please provide the axis limits or state that UCT did not reach V=80 within the range considered.
- [Table 1] The row 'Reuse % Improvement' reports 124% for MPT, but the comparison baseline is not stated in the table caption. It is presumably UCT, but this should be made explicit to avoid confusion.
- [Sec. I-A] The reference [1] for UCT is cited as guaranteeing convergence to the optimal trajectory as runtime increases; the precise conditions under which this guarantee holds should be stated or cited more carefully.
- [Abstract and Sec. V] The code link states that code 'will be made available'; the paper would be stronger if the code were already available at the time of submission, or if the statement indicated the planned release date.
Circularity Check
No significant circularity: the theoretical bound is derived from explicit assumptions, and the performance claims are validated against external baselines.
full rationale
The central theoretical result, Theorem 4 (Eq. 10), is a derived bound, not an assumed one: under Assumption 2 (slowly varying disturbance d and eps-accurate estimate hat-d), the proof uses the triangle inequality to obtain ||d(.,i+K+1)-hat-d_i|| <= (K+1)eta+eps, then applies Lemma 1 from contraction theory to convert this disturbance mismatch into the stated tracking-error bound. The constants eta and eps are input assumptions, not parameters fitted to the experiments that measure performance. The empirical claims—29.9% higher average value than CEM-Reuse, and L=180 versus 3000+ simulations to reach value 80—are comparisons against external baselines under the same reward evaluation, with UCT serving as an explicit ablation that differs only by disabling subtree reuse. The hardware section openly states that Assumption 2 is violated by friction, deformation, and other unmodeled dynamics, and that tree resets with tau=0.5 occur; this is a genuine scope limitation on the validation of Theorem 4, but it is not circularity because the theorem is neither fitted to nor used to define the reset mechanism. Self-citations ([8], [9], [23], [24]) appear in related work, estimator options, and the contraction-theory toolkit; the cited contraction theorems are standard results with stated assumptions that do not include MPT's target claim, so under the review rules they count as independent support and do not raise the circularity score. No step was found in which a prediction reduces to its input by construction.
Assumptions & free parameters
free parameters (6)
- K (search depth) =
10
- tau (tree reset threshold) =
0.5
- epsilon (UCT exploration constant) =
not reported
- gamma (discount factor) =
not reported
- Q, R (DARE cost matrices) =
not reported
- D (reward normalizing constant) =
not reported
assumptions (5)
- standard math Contraction theory: existence of a metric M satisfying (4) is necessary and sufficient for exponential convergence to a single trajectory (Theorem 1/2 from [24]).
- standard math Discrete Algebraic Riccati Equation has a unique positive definite solution under stabilizability and observability of (A,B) and (A,Q^(1/2)) (Assumption 1, [25]).
- domain assumption The DARE solution M is uniformly bounded over the state space: m I <= M <= mbar I (Assumption 1).
- domain assumption The disturbance d is slowly changing and the estimate is eps-accurate: ||d(x,u,k+1)-d(x,u,k)|| <= eta and ||d(x,u,k)-d_hat_k(x,u)|| <= eps (Assumption 2).
- standard math UCT converges to the optimal trajectory as the number of rollouts grows [1].
Cite this review
Pith. "Pith review of Model Predictive Trees: Sample-Efficient Receding Horizon Planning with Reusable Tree Search." pith.science (2026). https://pith.science/paper/VOXB54DV
@misc{pith2026241115651,
author = {Pith},
title = {Pith review of: Model Predictive Trees: Sample-Efficient Receding Horizon Planning with Reusable Tree Search},
year = {2026},
howpublished = {\url{https://pith.science/paper/VOXB54DV}},
note = {Machine review of arXiv:2411.15651}
}
read the original abstract
We present Model Predictive Trees (MPT), a receding horizon tree search algorithm that improves its performance by reusing information efficiently. Whereas existing solvers reuse only the highest-quality trajectory from the previous iteration as a "hotstart", our method reuses the entire optimal subtree, enabling the search to be simultaneously guided away from the low-quality areas and towards the high-quality areas. We characterize the restrictions on tree reuse by analyzing the induced tracking error under time-varying dynamics, revealing a tradeoff between the search depth and the timescale of the changing dynamics. In numerical studies, our algorithm outperforms state-of-the-art sampling-based cross-entropy methods with hotstarting. We demonstrate our planner on an autonomous vehicle testbed performing a nonprehensile manipulation task: pushing a target object through an obstacle field. Code associated with this work will be made available at https://github.com/jplathrop/mpt.
Figures
Reference graph
Works this paper leans on
-
[1]
L. Kocsis, C. Szepesv ´ari, and J. Willemson, “Improved monte-carlo search,” Univ. Tartu, Estonia, Tech. Rep , vol. 1, pp. 1–22, 2006
work page 2006
-
[2]
Rapidly-exploring random trees: A new tool for path planning,
S. LaValle, “Rapidly-exploring random trees: A new tool for path planning,” Research Report 9811 , 1998
1998
-
[3]
Sampling-based algorithms for optimal motion planning,
S. Karaman and E. Frazzoli, “Sampling-based algorithms for optimal motion planning,” Int. J. Robot. Res. , vol. 30, no. 7, pp. 846–894, 2011
2011
-
[4]
Rrtx: Asymptotically optimal single-query sampling-based motion planning with quick replanning,
M. Otte and E. Frazzoli, “Rrtx: Asymptotically optimal single-query sampling-based motion planning with quick replanning,” Int. J. Robot. Res., vol. 35, no. 7, pp. 797–822, 2016
work page 2016
-
[5]
Prob- abilistic roadmaps for path planning in high-dimensional configuration spaces,
L. E. Kavraki, P. Svestka, J.-C. Latombe, and M. H. Overmars, “Prob- abilistic roadmaps for path planning in high-dimensional configuration spaces,” IEEE Trans. Robot. Autom., vol. 12, no. 4, pp. 566–580, 1996
work page 1996
-
[6]
Sparse methods for effi- cient asymptotically optimal kinodynamic planning,
Y . Li, Z. Littlefield, and K. E. Bekris, “Sparse methods for effi- cient asymptotically optimal kinodynamic planning,” in Algorithmic Foundations of Robotics XI: Selected Contributions of the Eleventh International Workshop on the Algorithmic Foundations of Robotics , pp. 263–282, Springer, 2015
work page 2015
-
[7]
Monte-carlo tree search for efficient visually guided rearrangement planning,
Y . Labb ´e, S. Zagoruyko, I. Kalevatykh, I. Laptev, J. Carpentier, M. Aubry, and J. Sivic, “Monte-carlo tree search for efficient visually guided rearrangement planning,” IEEE Robot. Autom. Lett. , vol. 5, no. 2, pp. 3715–3722, 2020
work page 2020
-
[8]
Neural tree expansion for multi-robot planning in non-cooperative environments,
B. Riviere, W. H ¨onig, M. Anderson, and S.-J. Chung, “Neural tree expansion for multi-robot planning in non-cooperative environments,” IEEE Robot. Autom. Lett. , vol. 6, no. 4, pp. 6868–6875, 2021
work page 2021
Show all 25 references
-
[9]
Bayesian active sensing for fault estimation with belief space tree search,
J. Ragan, B. Riviere, and S.-J. Chung, “Bayesian active sensing for fault estimation with belief space tree search,” in AIAA Scitech Forum, p. 0874, 2023
2023
-
[10]
Cross-entropy motion planning,
M. Kobilarov, “Cross-entropy motion planning,” Int. J. Robot. Res. , vol. 31, no. 7, pp. 855–871, 2012
2012
-
[11]
Aggressive driving with model predictive path integral control,
G. Williams, P. Drews, B. Goldfain, J. M. Rehg, and E. A. Theodorou, “Aggressive driving with model predictive path integral control,” in IEEE Int. Conf. Robot. Automat. , pp. 1433–1440, 2016
2016
-
[12]
Real-time optimization and nonlinear model predic- tive control of processes governed by differential-algebraic equations,
M. Diehl et al., “Real-time optimization and nonlinear model predic- tive control of processes governed by differential-algebraic equations,” J. Process Control, vol. 12, no. 4, pp. 577–585, 2002
2002
-
[13]
Receding-horizon planning using recursive monte carlo tree search with sparse action sampling for continuous state and action spaces,
M. Schneider, “Receding-horizon planning using recursive monte carlo tree search with sparse action sampling for continuous state and action spaces,” in Amer. Control Conf., pp. 5401–5406, 2016
2016
-
[14]
Global planning for contact-rich manipulation via local smoothing of quasi-dynamic contact models,
T. Pang, H. T. Suh, L. Yang, and R. Tedrake, “Global planning for contact-rich manipulation via local smoothing of quasi-dynamic contact models,” IEEE Trans. Robot. , 2023
2023
-
[15]
Linear time-varying MPC for nonprehensile object manipulation with a nonholonomic mobile robot,
F. Bertoncelli, F. Ruggiero, and L. Sabattini, “Linear time-varying MPC for nonprehensile object manipulation with a nonholonomic mobile robot,” in IEEE Int. Conf. Robot. Automat. , pp. 11032–11038, 2020
2020
-
[16]
A motion planning approach for nonprehensile manipulation and locomotion tasks of a legged robot,
G. Zhang, S. Ma, Y . Shen, and Y . Li, “A motion planning approach for nonprehensile manipulation and locomotion tasks of a legged robot,” IEEE Trans. Robot. , vol. 36, no. 3, pp. 855–874, 2020
2020
-
[17]
Non-prehensile object transportation via model predictive non-sliding manipulation control,
M. Selvaggio, A. Garg, F. Ruggiero, G. Oriolo, and B. Siciliano, “Non-prehensile object transportation via model predictive non-sliding manipulation control,” IEEE Trans. Control Syst. Tech. , 2023
2023
-
[18]
Rear- rangement with nonprehensile manipulation using deep reinforcement learning,
W. Yuan, J. A. Stork, D. Kragic, M. Y . Wang, and K. Hang, “Rear- rangement with nonprehensile manipulation using deep reinforcement learning,” in IEEE Int. Conf. Robot. Automat. , pp. 270–277, 2018
2018
-
[19]
B. V . Mirtich, Impulse-based dynamic simulation of rigid body sys- tems. University of California, Berkeley, 1996
1996
-
[20]
J.-J. E. Slotine and W. Li, Applied nonlinear control . Englewood Cliffs, N.J: Prentice Hall, 1991
1991
-
[21]
Safe active dynamics learning and control: A sequential exploration–exploitation framework,
T. Lew, A. Sharma, J. Harrison, A. Bylard, and M. Pavone, “Safe active dynamics learning and control: A sequential exploration–exploitation framework,” IEEE Trans. Robot., vol. 38, no. 5, pp. 2888–2907, 2022
2022
-
[22]
Robust online motion planning via contraction theory and convex optimization,
S. Singh, A. Majumdar, J.-J. Slotine, and M. Pavone, “Robust online motion planning via contraction theory and convex optimization,” in IEEE Int. Conf. Robot. Automat. , pp. 5883–5890, 2017
2017
-
[23]
Learning-based robust motion plan- ning with guaranteed stability: A contraction theory approach,
H. Tsukamoto and S.-J. Chung, “Learning-based robust motion plan- ning with guaranteed stability: A contraction theory approach,” IEEE Robotics and Automation Letters , vol. 6, no. 4, pp. 6164–6171, 2021
2021
-
[24]
Contraction theory for nonlinear stability analysis and learning-based control: A tutorial overview,
H. Tsukamoto, S.-J. Chung, and J.-J. E. Slotine, “Contraction theory for nonlinear stability analysis and learning-based control: A tutorial overview,” Annual Rev. Control, vol. 52, pp. 135–169, 2021
2021
-
[25]
Existence condition on solutions to the algebraic riccati equation,
N. Mao-Lin, “Existence condition on solutions to the algebraic riccati equation,” Acta Autom. Sinica , vol. 34, no. 1, pp. 85–87, 2008
2008
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.