Referee report — Second-Order Smooth Planning with Optimal-Transport Bellman Smoothing

Summary

This paper studies planning with a generative model and asks how the order of the local Taylor remainder of a smooth Bellman aggregator controls oracle-call complexity. The unifying observation — Assumption 4.1 plus Theorem 4.3 — is that any SmoothCruiser-type planner whose backup $F_s$ admits a Taylor approximation with remainder $O(\|Q-\hat Q\|_2^{\beta})$ inherits a total oracle-call complexity $\tilde O(\varepsilon^{-(2+2/(\beta-1))})$, recovering SmoothCruiser at $\beta=2$ and identifying $\beta=3$ as the first genuinely improved regime with $\tilde O(\varepsilon^{-3})$. To realise $\beta=3$, the paper proposes an OT-smoothed Bellman backup over action distributions with an entropically regularised Wasserstein cost. Proposition 5.3 gives a $\mu_s$-mixture-of-LogSumExp closed form on cost-shifted scores, Proposition 5.4 identifies the gradient policy and Hessian, and Lemma 5.6 establishes a Lipschitz Hessian and hence the cubic remainder. The algorithmic payoff is a second-order Taylor correction that never requires forming the Hessian: Lemma 6.1 rewrites the quadratic form as a variance under the columnwise softmax, and a cross-product identity turns two independent-in-conditioning trajectories into an unbiased estimator. SECONDORDERSMOOTHCRUISER (Algorithms 1–3) plugs this into a SmoothCruiser recursion and Theorem 7.2 asserts the $\tilde O(\varepsilon^{-3})$ worst-case rate. The paper also gives gap-dependent variants, OT-GapE (bandit-optimal $(\Delta\vee\varepsilon)^{-2}$) and OT-GapCruiser (curvature-controlled $(\Delta\vee\varepsilon)^{-p}$ with $p\in(2,4)$). The curvature–complexity abstraction is a real conceptual contribution and the OT construction is well motivated. The main methodological limitation is that the improvement is realised for fixed smoothing parameters $(\tau,\lambda)$ and the constants that convert this into an unregularised-planning guarantee — in particular the Lipschitz-Hessian $M=O(1/(\tau^2\lambda^2))\cdot\mathrm{poly}(K,\mu_{\min}^{-1})$ — are never made explicit in the main text, so the practical reach of the $\varepsilon^{-3}$ result is hard to judge. Presentation issues (dropped negations, garbled displays, undefined subroutine names) also make several key steps harder to reconstruct than they should be.

Strengths

• Conceptual contribution. The curvature–complexity principle in Theorem 4.3 — reading off the planning exponent from the Taylor-remainder order $\beta$ — is a clean and portable idea that unifies SmoothCruiser and the OT construction in a single template.
• Well-designed regularizer. The OT-smoothed backup has a closed form as a $\mu_s$-weighted mixture of LogSumExp on cost-shifted scores (Proposition 5.3), a gradient that is itself a policy in the simplex (Proposition 5.4), a Lipschitz Hessian (Lemma 5.6), and reduces to entropy regularization at $C\equiv 0$ (Proposition 5.5). This makes it a genuinely usable higher-order instantiation rather than a purely formal one.
• Avoiding the Hessian. The variance identity in Lemma 6.1 combined with the cross-product debiasing (Equation 6.2) gives a Hessian-free unbiased estimator of the quadratic Taylor term at $O(1)$ extra samples — this is what actually delivers the improved exponent, and it is a satisfying algorithmic idea.
• Clean regularization-bias bookkeeping. Proposition 5.5 gives $|\bar F_s^{OT}(Q)-F_\eta^{\mathrm{ent}}(Q)|\leq\tau C_{\max}$ and a corresponding hardmax bound $\tau C_{\max}+\eta\log K$, which is a useful budget for linking the OT, entropic, and unregularised objectives.
• Complementary gap-dependent story. OT-GapE (Algorithm 4, Theorem 8.1) elegantly propagates confidence bounds through the smooth aggregator using its monotonicity, and the soft-optimistic policy $\propto\nabla F_s(U_{Q,h}^t)$ is a natural exploration rule aligned with the regularization.

Weaknesses

• Recursion-bias analysis for products of estimates. The central complexity result rests on Lemma 7.1, which the main text states with an unnamed "(recursion bias)" term and then asserts $O(\varepsilon)$ unconditional bias via analogy to Grill et al. (2019). The SmoothCruiser argument does not transfer directly: the quadratic correction depends on the product $\Delta_1\Delta_2$ of two recursively estimated differences, so child biases $b_j$ contribute $b_1 b_2$ to the product's bias, not $b_1+b_2$. The main text neither states nor even hints at the multiplicative composition, deferring the whole point to Appendix D.2 — this is the paper's load-bearing claim and it deserves visible treatment.
• Constants that grow toward the interesting regime. Lemma 5.6 records $M=O(1/(\tau^2\lambda^2))\cdot\mathrm{poly}(K,\mu_{\min}^{-1})$, and $M$ enters both the tolerance schedule $\rho(\varepsilon)=(6\varepsilon/M)^{1/3}$ and the base-case threshold $\kappa$. The transfer to unregularised planning proposes $(\tau,\lambda)$ small enough that the bias is $\leq(1-\gamma)\varepsilon_{\mathrm{bias}}$, but this makes $M$ blow up polynomially. The paper acknowledges the trade-off in words, but never surfaces the effective exponent (or hidden multiplicative factor) as a function of $\varepsilon$, so the reader cannot judge how meaningful the $\varepsilon^{-3}$ improvement is beyond the entropy-regularized setting.
• Ambiguous recursion schedule between proof and algorithm. Section A.2 uses $\varepsilon_+=\Theta(\varepsilon^{1/\beta})$ for the child accuracy, while Algorithms 2–3 and Lemma 7.1 use $\varepsilon/\sqrt\gamma$. The two are usually reconciled by calling children at tolerance $\rho(\varepsilon)/\sqrt\gamma$ (the algorithm's setup line does call ESTIMATEQ at $\rho(\varepsilon)$), but the correspondence is never spelled out. This is exactly the schedule that drives the exponent from 4 to 3.
• Theorem 9.1 with an undetermined exponent. The gap-dependent result is labelled a theorem but pins its exponent only to an open interval, $p\in(2,4)$ with $p\approx 3$ for $\beta=3$; the paper subsequently admits that "the precise value of $p$ ... depend[s] on how aggressively we schedule accuracies $\varepsilon_t$". A theorem should not have a free parameter of this kind. In addition, the derivation later writes $p=2+\alpha\in(2,4)$ and simultaneously "recovers $p=4$" at $\beta=2$ — an endpoint outside its own declared open interval.
• Two clashing definitions of the root gap. Section 9 uses $\Delta(a)=V^\star-Q_0(a)$ where $V^\star$ is the regularised value, while Section 8 uses the standard best-vs-suboptimal $Q_1^\star(s_0,a^\star)-Q_1^\star(s_0,a)$. In a regularised MDP the regularised value strictly exceeds $\max_a Q_0(a)$, so every gap under the first definition is inflated by the regularization bias and even $a^\star$ has a positive gap. This substantively changes the meaning of $(\Delta\vee\varepsilon)^{-p}$.
• Cross-product estimator's "independence" is only conditional. The main text advertises "independent unbiased estimates $\widehat\Delta^{(1)},\widehat\Delta^{(2)}$". In Algorithm 3 the action pair $(A,A')$ is drawn once before the $m$-loop and shared between the two estimates; only the oracle draws and recursive calls are refreshed. The unbiasedness argument therefore relies on the tower property with conditioning on $(J,A,A')$, not on marginal independence. This is fine substantively but easy to misimplement.
• Undetermined and unrendered ingredients. The main text uses several quantities without defining them: the parameter $\xi$ in the robust reference-distribution mixture ("guarantees $\mu_{\min}\geq\xi/K$"), the base-case threshold $\kappa$ in SAMPLEV2, the challenger $c^t$ / stopping-rule display (8.11) for OT-GapE, and the $1/(4\tau\lambda)$ normalization for the quadratic Taylor estimator (whose derivation is not sketched anywhere near Algorithm 3).
• Presentation issues in the proofs. The correctness proof of Theorem 8.1 (and the analogous parts of 9.1) contains at least five "either $b_t=a^\star$ or $a^\star=b_t$"-style case labels where the second disjunct has clearly lost its inequality slash. Algorithm 2 calls an undefined ORACLEV2 (the intended name is SAMPLEV2). Algorithm 3 has two lines labelled 19 and an OCR-mangled tolerance argument. The description of SmoothCruiser's per-action and cascade counts (Section 3) swaps $\varepsilon^{-1}$ and $\varepsilon^{-2}$ between per-level and per-action. Sparse Sampling is cited as Kearns et al. 1999 in the running text and Kearns et al. 2002 in Table 1. Each is small individually but together they make the technical parts of the paper harder to verify than necessary.
• Overstated auxiliary claims. The parenthetical "any additional variance reduction ... can only decrease $\alpha$" conflates curvature and variance; $\alpha=2/(\beta-1)$ is fixed by curvature. The "bandit-optimal exponent 2" tagline in Theorem 8.1 is fair for the $\varepsilon$/gap slot but should not be read as bandit-optimal overall, since the total scales as $H\sum_a\mathcal C(H,K,\gamma)/(\Delta(a)\vee\varepsilon)^2$.

Reproducibility & code

The manuscript does not release code, data, or a reference implementation, and no test MDP or empirical curve is supplied; the released materials effectively stop at the pseudocode. Given the paper's fully theoretical claim, this is legitimate, but several quantities that a reproducer would need are also missing from the main-text mathematics.

• No reference implementation for $F_s^{OT}$ or Algorithms 1–3. Even a minimal numerical check would substantially raise confidence in the constants that the $\tilde O(\varepsilon^{-3})$ bound hides: (a) the Lipschitz-Hessian bound $M$ against random $Q,\hat Q$ using Proposition 5.3, (b) the variance identity in Lemma 6.1 by Monte Carlo, (c) unbiasedness of $\widehat{\mathrm{Quad}}=\Delta_1\Delta_2/(4\tau\lambda)$ against ground-truth $\tfrac12\Delta^\top\nabla^2 F\Delta$. None of these are attempted.
• Load-bearing constants left implicit. $M=O(1/(\tau^2\lambda^2))\cdot\mathrm{poly}(K,\mu_{\min}^{-1})$ is used in the tolerance schedule, in $\kappa$, and in the hidden constant of Theorem 7.2, yet the polynomial dependence on $K,\mu_{\min}^{-1}$ is deferred to Appendix B.4 and never written out in the main text — a reader cannot check even the $K$-scaling of the bound.
• Base-case threshold $\kappa$ unspecified. SAMPLEV2 uses $\kappa$ to switch between the coarse and second-order regimes, and its proof says $\kappa$ depends only on $M$, but the value or scaling ($\kappa=c/M$ for what $c$?) is never given. This determines the range of $\varepsilon$ over which the paper's advertised improvement is realised.
• Undefined subroutine name and mangled pseudocode. Algorithm 2 recurses via a routine called ORACLEV2 that is never defined; SAMPLEV2 (Algorithm 3) has two lines numbered 19 and an OCR-mangled tolerance argument. Both make the pseudocode ambiguous exactly where the recursive coupling with tolerance $\varepsilon/\sqrt\gamma$ should be.
• $\delta$-splitting described qualitatively. The failure-probability accounting is repeatedly deferred as "appropriate distribution across recursive calls and clipping". The concrete pseudocode splits $\delta$ as $\delta/8,\delta/16,\delta/64,\ldots$ but the invariant these enforce is never stated; the appendix additionally uses a flat $\delta/(4KN)$ split, and the two together read as double-counting.
• OT-GapCruiser has no pseudocode and an unspecified schedule $\varepsilon_t$. Section 9 sketches OT-GapCruiser as four abstract steps and openly says the exponent depends on the (unspecified) $\varepsilon_t$; this makes the theorem's sample-complexity claim not reproducible even in principle. Contrast Algorithm 4 for OT-GapE, which is written out in detail.
• OT-GapE stopping display (8.11) not visible. The best-guess/challenger construction $(b^t,c^t)$ referenced from Algorithm 4 line 5 and reused in the correctness proof is defined by an equation that is not rendered in the main text; the natural UGapE reading of "$a^\star$ is among the maximization set defining $c_t$" contradicts the standard convention $c_t\in\arg\max_{a\neq b_t}(\cdot)$ without (8.11) to disambiguate it.

Recommended Changes

Essential

• Make the recursion-bias analysis for products visible. In the main text, sketch how the product structure $\Delta_1\Delta_2$ in the quadratic-term estimator is handled by the $\varepsilon/\sqrt\gamma$ contraction — the argument that carries SmoothCruiser does not transfer to a second-order method by analogy. This addresses the "Recursion-bias analysis for products of estimates" weakness.
• Reconcile the recursion tolerance $\varepsilon^{1/\beta}$ (proof of Theorem 4.3) with $\varepsilon/\sqrt\gamma$ (Algorithms 2–3, Lemma 7.1) in one displayed line, e.g. by writing the algorithm's tolerance as $\rho(\varepsilon)/\sqrt\gamma$ and showing this matches $\Theta(\varepsilon^{1/\beta})$. Addresses "Ambiguous recursion schedule".
• Sharpen or downgrade Theorem 9.1. Either commit to a specific $\varepsilon_t$ schedule and prove a specific $p$ (fixing the $p\in(2,4)$ / $p=4$ endpoint inconsistency), or restate the result as a proposition / informal discussion. Addresses "Theorem 9.1 with an undetermined exponent" and the interval-vs-endpoint issue.
• Unify the definition of the root gap. Use the standard $\Delta(a)=Q^\star(s_0,a^\star)-Q^\star(s_0,a)$ consistently across Sections 8 and 9, or explicitly state (and justify) that Section 9's $\Delta(a)=V^\star-Q_0(a)$ uses the regularised value and quantify the resulting inflation. Addresses "Two clashing definitions of the root gap".
• Surface the constants $M$ and $\kappa$ in the main text. Give the explicit polynomial dependence of $M$ on $K,\mu_{\min}^{-1}$ (currently only in Appendix B.4) and a scaling for $\kappa$. Addresses "Constants that grow toward the interesting regime", "poly(K, µ_min^{-1}) factor in M is not written out anywhere" and "Base-case threshold $\kappa$ unspecified".
• Release a minimal reference implementation. A short script that (i) computes $F_s^{OT}(Q)$ and its Hessian from the closed form, (ii) empirically checks the Lipschitz-Hessian bound, (iii) verifies Lemma 6.1's variance identity, and (iv) checks unbiasedness of the cross-product estimator on a toy MDP, would remove essentially all the "reproducibility" concerns and would take only a few dozen lines. Addresses "No reference implementation".
• Reproduce (8.11) inline and disambiguate the OT-GapE case analysis. Include the best-guess/challenger definition in the main body and fix the systematic "$b_t=a^\star$ or $a^\star=b_t$" case labels (dropped negations) throughout the proofs of Theorems 8.1 and 9.1. Addresses "OT-GapE stopping-rule and challenger definition are not spelled out" and "Case-analysis case labels have systematic dropped negations".

Suggested

• Fix the typographical contradiction "reduces to entropy regularization when $C\equiv 0$ and incorporates action geometry when $C=0$" (the second clause should be $C\neq 0$), and add the offset caveat inline whenever the paper says "reduces exactly to the entropy backup". Addresses "Internal contradiction ..." and "'Reduces exactly to the entropy backup' needs the offset caveat inline".
• Rewrite the SmoothCruiser cost sentence in Section 3 so that per-action ($\varepsilon^{-1}$) and cascade ($\varepsilon^{-2}$) factors are not swapped, and align with Table 1. Addresses "SmoothCruiser cost description is garbled".
• Repair the pseudocode. Rename ORACLEV2 to SAMPLEV2 in Algorithm 2, re-typeset Algorithm 3 with unique line numbers and legible tolerance arguments, and derive the $1/(4\tau\lambda)$ normalization in one or two lines near the algorithm box. Addresses "Algorithm 2 references an undefined subroutine name", "Two lines both numbered 19 in Algorithm 3" and "Quadratic estimator normalization 1/(4τλ) not derived".
• Define $\xi$ where it is used. Restore the missing display for the robust full-support mixture (something like $\mu_s=\xi\cdot\mathrm{unif}+(1-\xi)\pi_s^{\mathrm{prior}}$) and state the range of $\xi$. Addresses "Robust reference-distribution guarantee uses undefined symbol $\xi$".
• State the failure-probability split precisely. Give a single explicit $\delta$-allocation rule (depth × breadth) with the union-bound check in place of the "appropriate distribution" language and the overlapping $\delta/(4KN)$ + $\delta/8,\delta/16,\ldots$ description. Addresses "Overlapping $\delta/(4KN)$ and geometric $\delta/8,\delta/16$ budgets" and "The $\delta$-splitting scheme is described qualitatively".
• Rename $C_h^t$ in Algorithm 4 (e.g. $\mathcal C_h^t$ or $\Xi_h^t$) so C is not overloaded with the OT cost matrix, and align its case with $L_{Q,h}^t,U_{Q,h}^t$ used in Theorem 8.1. Addresses "Notation collision".
• Add an explicit adaptive-accuracy schedule for OT-GapCruiser (e.g. "at round $t$ call SECONDORDERSMOOTHCRUISER at accuracy $c\cdot(\Delta_t(a)\vee\varepsilon)$") and pseudocode. Addresses "Per-sample accuracy scale $r$ for OT-GapCruiser is asserted" and "OT-GapCruiser has no pseudocode".
• Soften the auxiliary overclaims: remove or replace "any additional variance reduction ... can only decrease $\alpha$" with an accurate statement, and drop the standalone "bandit-optimal exponent 2" label in Theorem 8.1 in favour of the qualified "matches the bandit-optimal exponent in $\varepsilon$ and gaps". Addresses "'Variance reduction can only decrease α' conflates curvature and variance" and "'Bandit-optimal exponent 2' underplays $H$ and branching factors".
• Reconcile the Kearns citation. Choose either 1999 or 2002 consistently in the running text, Table 1, and reference list. Addresses "Citation inconsistency for Sparse Sampling".
• State the scope of the "tight" per-action lower bound. Make explicit that $\Omega(\varepsilon^{-2/\beta})$ is a lower bound on per-level averaging, not on end-to-end planning $n_\beta$. Addresses "Scope of 'tight' lower bound".
• One-line domination for the $+1$ tail in the proof of Theorem 4.3, and one sentence in Part VI of Theorem 7.2's proof bridging $T(\eta)=\tilde O(\eta^{-1})$ (single sample) to $\tilde O(\varepsilon^{-3})$ (outer $\varepsilon^{-2}$ concentration). Addresses "The +1 additive tail is dismissed rather than dominated" and "Composition of the $T(\eta)=\eta^{-1}$ single-sample bound".