{"id":"b6bd357b-0525-4f90-8616-f9b8d4cb7450","arxiv_id":"2412.11270","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"SETS uses the eigenvectors of the local controllability Gramian as tree branches in Monte Carlo Tree Search, giving a real-time planner with a proved error bound for continuous deterministic robot MDPs.","lead":"A new planning algorithm, SETS, builds a search tree from the natural motions of a robot's linearized dynamics and proves the tree search converges to within a bounded error of the optimal continuous-space solution. It runs in real time on drones, ground vehicles and spacecraft, and discovers behaviors such as riding wind thermals and capturing debris.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Algorithm 1's exploration constants (c2=0.5, c3=1) violate the regime required by Theorem 2; the central convergence guarantee does not cover the deployed algorithm unless this is a typo.","rationale":"In good faith, the paper has substantial independent support: the spectral expansion idea is well-motivated, the hardware and simulation experiments are demanding, and the theoretical supplement is self-contained and unusually detailed. The reader's conditional verdict is appropriate. I considered other possible concerns: the quadrotor experiment uses a ReLU DNN wind model and indicator rewards, which violate the C^2 and Lipschitz assumptions, and the tracked-vehicle experiment uses gamma=1, which the analysis excludes. These are real but partially acknowledged and secondary. The exploration-constant mismatch is the most direct internal inconsistency because Theorem 3's convergence term is explicitly computed under constants the algorithm does not use. If the Algorithm 1 listing is a typo, the fix is minor; if it is not, the main finite-time guarantee does not apply to the deployed system. No other candidate concern undermines the central claim more directly. The recommended verdict remains CONDITIONAL: the paper should be accepted only after the constants are corrected or the proof is extended to the implemented exploration law.","tokens_in":51640,"tokens_out":12523,"duration_ms":118876,"concrete_test":"Run the released SETS code (linked in the paper) to confirm the exploration constants actually used in the quadrotor and glider experiments. Then independently re-derive Lemma 9 with those constants: if the code uses c2=0.5, c3=1, evaluate c_d3+c_{d+1}_6-c_d2=1+(-1)-0.5<0, which violates the proof's constraint and leaves Theorem 2 inapplicable; if the code uses c2=1, c3=0.5 (or c3=0.49, c2=0.98), the Algorithm 1 listing is a typo and Theorem 2's coverage is restored.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of Theorem 3 combines Theorem 1 and Theorem 2; Theorem 2 supplies the 1/sqrt(l) convergence term. The Supplemental 'Constants Discussion' proves that rate only under c3 in [1/4,1/2) and c2=2c3, giving c_d5=c_d6=1-c_d3/c_d2=1/2. Algorithm 1 Line 6, however, states c1=1, c2=0.5, c3=1. Under those values c_d5=1-1/0.5=-1, so c_d6=-1. The inductive step in Lemma 9 explicitly requires c_d3+c_{d+1}_6-c_d2>0, the condition used in Equations (165)-(169); substituting c_d3=1, c_d2=0.5, c_{d+1}_6=-1 gives 1-1-0.5=-0.5<0, so the visit-count bound and hence Theorem 2 fail to hold for the implemented exploration law. The statement 'In practice... c3 closer to 1/2... and we used exactly those values in our experiments' suggests the Algorithm 1 listing may have transposed c2 and c3, but as written the deployed algorithm is outside the proven regime. Because the paper's real-time optimality guarantee depends on this rate, the mismatch is load-bearing; it is also easily repaired, which is why the appropriate verdict is conditional rather than rejection.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes Spectral Expansion Tree Search (SETS), a real-time MCTS planner for continuous, deterministic, differentiable MDPs. Instead of uniformly discretizing state or action spaces, SETS expands tree nodes along the dominant modes of the locally linearized controllability Gramian, generates reference trajectories to those modes, and tracks them with a DARE-based feedback controller. The theoretical core is threefold: Theorem 1 bounds the optimal-value error caused by replacing the continuous reachable set with the finite set of spectral modes; Theorem 2 provides a finite-time concentration bound for MCTS with polynomial exploration on finite-action MDPs; and Theorem 3 combines these into a bound of the form kappa4/sqrt(l) plus a steady-state error term. The paper reports hardware and simulation demonstrations on a quadrotor, a tracked vehicle, two tethered spacecraft, and a glider.","tokens_in":52015,"tokens_out":10789,"duration_ms":105711,"significance":"If the theorems hold for the algorithm as actually implemented, this is a notable contribution: it is one of the few real-time kinodynamic planners with a non-asymptotic global-optimality bound, and it targets a broad problem class rather than a narrowly specialized motion-planning formulation. The theoretical development is a genuine derivation from stated Lipschitz, contraction, and reachability assumptions, not a fit of constants to a target result, and the modular decomposition (reachable-set approximation in Theorem 1, MCTS value convergence in Theorem 2) is likely to be useful beyond this specific planner. The release of code and video links and the breadth of hardware experiments strengthen the reproducibility of the empirical claims. However, the paper's central guarantee is currently separated from its deployed algorithm by two concrete gaps: the exploration constants in Algorithm 1 are outside the regime proved in the supplement, and the mode-pruning heuristic used in all reported experiments removes modes that Theorem 1's covering argument requires. These gaps are fixable, but they make the significance contingent until the manuscript is corrected.","major_comments":[{"comment":"The exploration constants used in Algorithm 1 are outside the regime in which Theorem 2 is proved. Algorithm 1 Line 6 and the Methods text specify c1=1, c2=0.5, c3=1, whereas the Supplemental 'Constants Discussion' proves the 1/sqrt(tau) rate only for c3 in [1/4,1/2) with c2=2c3. Substituting the implemented values gives cd5=cd6=1-c3/c2=-1, and Lemma 9's inductive condition cd3+c_{d+1}6-cd2>0 evaluates to 1-1-0.5=-0.5, so Equations (165)-(169) and the visit-count bound that feeds Theorem 2 no longer hold. Since Theorem 3's convergence term is exactly Theorem 2's rate, the central real-time optimality guarantee does not cover the deployed algorithm as written. The supplement's final sentence ('we used exactly those values in our experiments') suggests a transposition between c2 and c3 in the pseudocode; if so, the pseudocode and the Methods text must be corrected, and otherwise Theorem 2 must be reproved for the actual exploration law.","section":"Methods (Algorithm 1, Line 6; Methods paragraph) and Supplemental 'Constants Discussion'"},{"comment":"The Heuristics paragraph states that the authors 'apply [the mode-pruning heuristic] in all of our experiments,' yet Theorem 1 and Lemma 3 use all 2n controllability-Gramian modes to bound dS(R_L^H(x0,U^H), {z_i^H}_{i=1}^{2n}) <= 2 sigma_max(C). Once only a subset of modes is expanded, the finite representation need not cover the linear reachable set in the sense required by the proof, and the steady-state error term in Theorem 3 is not certified for the reported implementations. The authors should either report at least one experiment using the full expansion or provide a supplementary argument showing that the omitted modes are unnecessary for the reward and constraint class considered; without this, the experimental validation is outside the proven algorithm.","section":"Methods, 'Heuristics'"}],"minor_comments":[{"comment":"The factor sqrt(m)/m appearing in Lemma 4 and in Equation (89) appears to be a typo for sqrt(m)/m (or a consistent bound involving sqrt(m)); as written, the factor is ambiguous and should be cleaned up.","section":"Supplemental 'Lemma 4' and 'Lemma 2'"},{"comment":"Assumption 1 restricts rewards to state-only Lipschitz functions, but the tracked vehicle reward in Supplemental Equation (12) depends on the action (vd, omega_d). The paper already notes that the tracked-vehicle demonstration uses gamma=1 outside the theory; it should similarly state that the action-dependent reward is outside Assumption 1.","section":"Supplemental 'Supplemental Tracked Vehicle'"},{"comment":"The proof divides by Delta(j) and uses Delta_min(i) in the constants, but neither Theorem 2 nor Assumption 2 states that every node has a unique strictly optimal child with positive gap. Please add an explicit strict-gap assumption or explain how ties are handled so that arms with Delta(j)=0 do not make the bounds vacuous.","section":"Supplemental 'Theorem 2' proof"},{"comment":"The sentence 'we return the maximum valued trajectory ... This practice maintains theoretical guarantees' is too terse. Because Theorem 2 and Theorem 3 bound the average estimator E[V(i,l)], the manuscript should spell out why the returned maximum-valued trajectory inherits the bound, for example by noting that all sampled values are bounded above by V*(i), so the maximum estimator lies between the average estimator and V*(i).","section":"Methods, 'Heuristics' and 'Theoretical Results'"}],"recommendation":"major_revision","confidential_remarks":"The likely explanation for the exploration-constant mismatch is a transposition in the pseudocode, but as printed the central theorem does not cover the printed algorithm. The mode-pruning issue is a second, more substantive gap between theory and the experimental validation. I recommend major revision with the expectation that both gaps can be closed in a careful revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nSETS is a real step forward for real-time planning under continuous dynamics. The core idea—using eigenvectors of the local controllability Gramian to generate tree branches instead of uniform sampling—is genuinely new relative to DFMT, which uses the Gramian only for reachability checks. The paper backs it with serious formal analysis: Theorem 1 bounds discretization error via reachable-set distance, Theorem 2 proves MCTS convergence for deterministic rewards without needing the gap, and Theorem 3 combines them. The experiments are broad and credible: three hardware platforms plus a glider simulation, with the thermal case providing a clean empirical check of the H-dependent tradeoff. Code is linked. This deserves a serious referee.\n\nThe soft spot is real, but it looks like a typo. Algorithm 1 and the Methods text set c1=1, c2=0.5, c3=1. The Supplemental Constants Discussion proves the convergence rate c5=c6=1/2 only under c3 in [1/4,1/2) and c2=2c3, and then says \"in practice ... c3 closer to 1/2 (and consequently c2 near 1)\". So the listing transposes c2 and c3. As written, the inductive step in Lemma 9 requires c3+c6-c2>0; with the declared values c6=1-c3/c2=-1, that condition becomes 1-1-0.5=-0.5, so the proof does not cover the deployed algorithm. This is load-bearing for Theorem 3's 1/sqrt(l) rate. It is also trivially fixable: swap c2 and c3 in the pseudocode, or state the actual constants used. I would not reject over this, but I would require the correction before publication.\n\nTwo smaller notes. The tracked vehicle experiment uses gamma=1, which the paper flags as outside assumptions; that is honest, but it means that experiment is not a direct validation of the theorem. The quadrotor uses a ReLU DNN for wind, which is not C^2; this is not flagged. Both are easily addressed with a sentence saying these are demonstrations beyond the theorem's assumptions.\n\nOverall: the math is substantial, the experiments are real, and the central argument holds up once the constant typo is fixed. The related work is careful—the DFMT distinction is accurate and self-citations are not load-bearing. This is a paper worth engaging with seriously.","headline":"SETS is a strong, genuinely new spectral MCTS planner whose central convergence guarantee is currently disconnected from the implementation by a likely c2/c3 typo; with that fixed, the paper is a solid advance.","tokens_in":52499,"tokens_out":3041,"would_cite":true,"duration_ms":26995,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"SETS, a Monte Carlo tree search that branches along natural motion modes, converges to a bounded-error approximation of the globally optimal plan for continuous deterministic differentiable MDPs.","keywords":["Monte Carlo Tree Search","spectral expansion","controllability Gramian","continuous-space planning","model-predictive control","autonomous robots","kinodynamic planning","global optimality bounds"],"falsifier":"Run Algorithm 1 exactly as published, with $c_1=1$, $c_2=0.5$, $c_3=1$, on a small continuous MDP whose optimal value can be computed by fine-grid value iteration, and measure $|V^*(x_0) - E[V(x_0,\\ell)]|$ as $\\ell$ grows. If the decay is not of order $\\ell^{-1/2}$ or the estimate violates the Theorem 3 bound, then the stated exploration-law hypotheses are not satisfied by the delivered algorithm.","tokens_in":1603,"feed_emoji":"🤖","tokens_out":2410,"duration_ms":69233,"temperature":0.7,"pith_summary":"This paper introduces Spectral Expansion Tree Search (SETS), a Monte Carlo Tree Search planner for continuous, deterministic, differentiable dynamical systems. SETS replaces the usual spatial discretization of a robot's state and action space with a tree whose branches follow the natural motion modes obtained from the spectrum of the locally linearized controllability Gramian. The authors prove that this discretization has bounded error: the difference between the continuous optimal value and SETS's estimate goes to a problem-dependent steady-state term as simulations grow. They demonstrate on quadrotor, tracked-vehicle, tethered-spacecraft, and glider experiments that this planner discovers non-trivial behaviors in real time. The central engineering claim is that a general, offline-training-free planner can handle high-dimensional, underactuated, non-convex robotics problems while still carrying an optimality guarantee.","feed_headline":"Tree search reaches near-optimal plans for continuous robot dynamics","feed_subtitle":"SETS branches along the system's natural motion modes, giving real-time planners a global-optimality guarantee.","key_machinery":"The Spectral Expansion operator is the load-bearing mechanism. At each node it linearizes the dynamics over a horizon $H$, computes the eigendecomposition of the controllability Gramian $CC^\\top$, and launches $2n$ branches along the plus and minus singular vectors (the natural motion modes). A Discrete Algebraic Riccati Equation feedback controller steers the nonlinear system onto each linear reference trajectory, and the resulting reachable-set covering is bounded via Hausdorff distance lemmas. This discrete representation is what converts the continuous MDP into a finite tree whose value error can be analyzed by an MCTS convergence theorem.","core_discovery":"SETS converges to a bound of the globally optimal solution for continuous Markov Decision Processes with twice-differentiable dynamics, Lipschitz state-dependent rewards, and bounded continuous action sets. Quantitatively, Theorem 3 bounds the value error by a convergence term plus a steady-state term: the estimate approaches within a problem-dependent constant of the continuous optimum as the number of tree rollouts grows. The mechanism is spectral expansion: at each node, linearize the dynamics, form the input-normalized controllability matrix, take its eigendecomposition, and branch along plus and minus each mode; a discrete Riccati feedback controller tracks the linear reference trajectory with the nonlinear system. This yields a branching factor linear in state dimension and a tree depth reduced by a factor of the branch length, dramatically shrinking the action-sequence count relative to uniform discretization. A separate MCTS convergence theorem achieves a $1/\\sqrt{\\tau}$ rate without knowing the reward gap, and combining the two results gives the overall convergence-to-a-bound guarantee.","pith_inferences":["As an extension the authors mention but do not develop, the spectral modes could serve as learned features for offline policy learning, model-predictive path integral control, or kinodynamic RRT-style planners, potentially reducing their search complexity.","The glider baseline study suggests that the spectral representation contributes more than the exploration strategy: a simpler predictive-sampling rollout on top of spectral expansion performed competitively, so representation and exploration can be decoupled and mixed.","If the exploration-constant mismatch flagged in the Supplemental Constants Discussion is not a typo, the deployed Algorithm 1 with $c_2=0.5$, $c_3=1$ falls outside the conditions of Theorem 2, and the real-time optimality guarantee would need an extended proof or a constants correction to cover the published implementation.","The steady-state error depends on linearization error and on the contraction rate of the Riccati tracking controller, so systems with poor local linearizations will need tighter tracking or shorter branches to keep the bound meaningful."],"forward_implications":["For any twice-differentiable deterministic dynamics with Lipschitz rewards, a robot can replan from a never-before-seen state in real time and the value of its plan approaches a bounded neighborhood of the continuous optimum as computation increases.","Branch length $H$ tunes the trade-off directly: larger $H$ converges faster but with larger asymptotic error, while smaller $H$ converges slower but tighter, giving a principled parameter design rule for receding-horizon operation.","Tree width scales linearly in state dimension ($2n$ modes) rather than exponentially in control dimension, so the method extends to high-dimensional platforms such as a 12-dimensional quadrotor with learned wind effects and a multi-spacecraft tether network.","The guarantee applies to value, not just feasibility, so SETS can be paired with local optimization in a search-then-optimize loop that keeps global exploration while refining the output trajectory.","The MCTS convergence result, which holds for deterministic rewards without knowing the gap between children, may transfer to discrete game-playing and other tree search settings that use polynomial exploration."],"supporting_citations":[{"why":"Supplies the non-asymptotic MCTS analysis with backwards induction and non-stationary bandits that Theorem 2 adapts to the deterministic-reward setting.","marker":"[87]"},{"why":"Defines the UCB-style MCTS tree policy that SETS's polynomial exploration rule extends.","marker":"[18]"},{"why":"Provides the controllability matrix and Gramian theory, including the reachable-ellipsoid property used to select the spectral modes.","marker":"[89]"},{"why":"Prior kinodynamic planner that uses the controllability Gramian for reachability, which the spectral expansion generalizes to nonlinear local Gramians.","marker":"[48]"},{"why":"Surveys MCTS terminology and procedure, framing the algorithmic structure that SETS builds on.","marker":"[20]"},{"why":"Provides the continuous UCT baseline with progressive widening used in the glider comparisons.","marker":"[26]"}],"fun_headline_variants":["Spectral tree search achieves near-optimal continuous planning","SETS: real-time tree planning with global-optimality bound","Spectral expansion enables tree search for continuous dynamics","Tree search finds optimal motions via spectral linearization","Near-optimal robot plans via spectral MCTS in real time"],"cache_read_input_tokens":54656,"weakest_assumption_plain":"The finite-time convergence rate relies on the exploration constants satisfying $c_3 \\in [1/4,1/2)$ and $c_2=2c_3$, as stated in the Supplemental Constants Discussion, but the implemented Algorithm 1 and Methods use $c_2=0.5$, $c_3=1$; if that mismatch is real rather than a typo, Theorem 2's $1/\\sqrt{\\tau}$ rate does not apply to the deployed algorithm.","fun_headline_variants_meta":{"raw":{"variants":["Spectral tree search achieves near-optimal continuous planning","SETS: real-time tree planning with global-optimality bound","Spectral expansion enables tree search for continuous dynamics","Tree search finds optimal motions via spectral linearization","Near-optimal robot plans via spectral MCTS in real time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000197,"raw_usage":{"total_tokens":1359,"prompt_tokens":935,"completion_tokens":424,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":551,"completion_tokens_details":{"reasoning_tokens":359}},"tokens_in":551,"tokens_out":424,"duration_ms":4247,"temperature":1.0,"reasoning_tokens":359,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:07:49.389583+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 exactly as published, with $c_1=1$, $c_2=0.5$, $c_3=1$, on a small continuous MDP whose optimal value can be computed by fine-grid value iteration, and measure $|V^*(x_0) - E[V(x_0,\\ell)]|$ as $\\ell$ grows. If the decay is not of order $\\ell^{-1/2}$ or the estimate violates the Theorem 3 bound, then the stated exploration-law hypotheses are not satisfied by the delivered algorithm.","supporting_citations":[{"cited_title":"Non-asymptotic analysis of monte carlo tree search,","cited_arxiv_id":null,"evidence_quote":"Supplies the non-asymptotic MCTS analysis with backwards induction and non-stationary bandits that Theorem 2 adapts to the deterministic-reward setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the controllability matrix and Gramian theory, including the reachable-ellipsoid property used to select the spectral modes."},{"cited_title":"Optimal sampling-based motion planning under differential con- straints: the drift case with linear affine dynamics,","cited_arxiv_id":null,"evidence_quote":"Prior kinodynamic planner that uses the controllability Gramian for reachability, which the spectral expansion generalizes to nonlinear local Gramians."}],"review_version":1}