REVIEW 2 major objections 4 minor 13 references
To bootstrap or to rollout? An optimal and adaptive interpolation
T0 review · 2 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read Subgraph Bellman estimators match TD's variance while keeping Monte Carlo's occupancy-based sample complexity.
desk verdict The subgraph Bellman operator is a genuinely new idea and the lower bound is solid, but Theorem 2's parameter schedule has a data-budget bug that makes Algorithm 2 non-executable as stated. 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 central object is the subgraph Bellman operator: for a chosen subset G of states, the value function is characterized as the fixed point of $V(s) = r(s) + P_G V(s) + \mathbb{E}[1_{S_1 \notin G} \sum_{t\ge 1} r(S_t) \mid S_0=s]$, where $P_G$ is the transition kernel restricted to G. The empirical version plugs in sample-average estimates of $r$, $P_G$, and the outside-G rollout return, producing a low-dimensional fixed-point equation. The engine that makes the finite-sample theorem work is a preconditioning weight vector $w(s) \approx 1/(2\nu(s))$, estimated from an auxiliary trajectory set; under the uniform closeness condition $|w(s)\nu(s)-1/2| \le 1/(36h)$ for all $s\in G$, the population operator becomes a multi-step $\ell^\infty$ contraction — its $3h$-fold composition contracts by factor $1/2$ — which lets the ROOT-SA stochastic-approximation scheme solve the empirical fixed point with per-state accuracy governed by $\nu_{\min}(G)$.
What would settle it
Run the ROOT-SA algorithm on a small Markov reward process with G chosen so that the sample-size condition holds, using exactly the auxiliary sample size prescribed by the paper's parameter schedule, and directly measure $\max_{s\in G}|w(s)\nu(s)-1/2|$ from the auxiliary data; if the observed maximum systematically exceeds $1/(36h)$, or if the empirical error at the predicted sample size does not follow the leading variance term, the core contraction lemma — and the theorem resting on it — is falsified for that instance.
Extended reading notes
Core claim
On its own terms, the paper establishes that for any subset G of the state space containing the target state, the estimator $\hat V_G$ obtained by solving the empirical subgraph Bellman fixed point satisfies, for every $\ell^1$-bounded functional $a_0$, a high-probability bound of the form $|a_0^\top (\hat V_G - V^*)| \le c\, (a_0^\top (I-P_G)^{-1} \Sigma_G (I-P_G)^{-\top} a_0)^{1/2} \sqrt{\log(1/\delta)/n}$ plus lower-order terms, as soon as $n/\log^4(n/\delta) \ge c h^3/\nu_{\min}(G)$. The covariance $\Sigma_G$ decomposes into the one-step TD variance $\sigma^2_{V^*}(s)/\nu(s)$ and a Monte Carlo term multiplied by the probability of leaving G; for a transient subgraph the variance takes the exact closed form $\sum_{s'\in G} \mathbb{E}[N(s') \mid S_0=s]^2\,(\sigma^2_{V^*}(s') + P(S_1\notin G\mid S_0=s')\sigma^2_{\mathrm{out}}(s'))/\nu(s')$. A minimax lower bound over Markov reward processes whose transitions can move to small-occupancy states shows that a term of order $q/\nu(s_0)$ is unavoidable for any estimator whenever $n$ is polynomially smaller than $|S|$, so the exit-probability term in the upper bound is a genuine sample-complexity requirement rather than a proof artifact.
Load-bearing premise
The proof requires that the data-based weights used to speed up updates be almost exactly proportional to the inverse of how often each state is visited, on every state of the chosen subset; if even one state violates this closeness condition, the contraction that drives the theorem may fail.
Editorial extensions
If this is right
- Choosing G to be the whole state space recovers TD-like behavior with optimal asymptotic variance, while choosing G to be a single target state recovers MC-like adaptivity, so the subgraph family genuinely spans the two classical estimators.
- For any $\ell^1$-bounded functional — such as the value of a single state or the advantage of one action over another — the estimator achieves the TD covariance as its leading-order risk, with sample complexity depending only on the occupancy of G, not the cardinality of the state space.
- When G is transient, the variance has an exact closed form in which each state's contribution is its one-step variance plus the exit probability times the outside rollout variance, divided by occupancy; this makes the interpolation trade-off explicit and calculable.
- The minimax lower bound implies the exit-probability term is not removable: for sample sizes polynomially smaller than the state-space size, every estimator must pay $q/\nu(s_0)$, so the upper bound describes the true difficulty of the problem.
- The data-driven greedy subgraph selection, backed by a non-asymptotic variance estimator, gives a practical route to choosing G without prior knowledge of the transition kernel.
Reading between the lines
- The preconditioning mechanism suggests a direct extension the authors leave open: a fully online scheme that updates the subgraph G and the weights w as occupancy estimates improve; the current analysis treats G as fixed and chosen with a holdout set.
- Because the lower bound is stated in terms of occupancy and exit probability rather than state-space dimension alone, a natural testable prediction is that the same variance-versus-adaptivity trade-off governs off-policy evaluation whenever one can choose a subgraph with high-occupancy exits; the paper does not analyze that setting.
- The coarse dependence on the effective horizon h in the upper bounds likely understates the algorithm's performance on problems with large horizon; tightening the horizon factors could connect the result to average-reward and infinite-horizon reinforcement learning, where the paper's variance formulas would need re-derivation.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces subgraph Bellman operators, a family of Bellman operators indexed by a subset G of the state space that interpolates between TD bootstrapping and Monte Carlo rollout for policy evaluation in a tabular Markov reward process. The main theoretical claims are an asymptotic normality result for the subgraph Bellman estimator (Lemma 1), an ℓ2(ν(G)) non-asymptotic bound for a plug-in estimator (Theorem 1), a per-functional non-asymptotic bound for a ROOT-SA-based solver (Theorem 2), a data-driven variance estimator and subgraph selection procedure (Proposition 7 and Algorithm 3), and an instance-dependent minimax lower bound showing that an exit-probability term is unavoidable (Theorem 3). The central advertised message is that the estimator can approach the asymptotic variance of TD while maintaining finite-sample adaptivity to the occupancy measure of a selected subgraph.
Significance. If the advertised guarantees were fully established, this would be a valuable contribution: it provides a concrete operator-level interpolation between TD and MC, gives finite-sample per-functional bounds whose leading variance matches the asymptotic covariance of the subgraph estimator, and complements these with an information-theoretic lower bound that identifies the exit probability as an unavoidable complexity term. The asymptotic analysis (Lemma 1, Corollary 1, Proposition 5) and the finite-sample lower-bound construction (Theorem 3) are detailed and appear coherent. The paper also gives a nontrivial plug-in analysis in Theorem 1 with explicit concentration arguments. However, the main functional-estimation guarantee, Theorem 2, is not currently established as stated because its proof relies on two parameter-schedule conditions that are inconsistent with Eq. (17); these issues are load-bearing rather than cosmetic.
major comments (2)
- [Section 6.4, proof of Eq. (47), vs. Eq. (17)] The proof of Eq. (47) requires the auxiliary occupancy estimate to satisfy |ν(s)/pνA(s) - 1| ≤ 1/(18h), and the displayed concentration bound forces n_A ≥ c h^3 ν_min^{-1} log(|G|/δ). But Eq. (17) schedules n_A = c h ν_min^{-1} log(n/δ), which is a factor h^2 smaller for general instances. Since h is an instance-dependent quantity that can be arbitrarily large (e.g., h = 1/(1-γ) for discounted MRPs), no universal constant c can close this gap. Eq. (47) is the exact condition used by Lemma 9 to prove the multi-step ℓ∞ contraction that powers the ROOT-SA analysis, so Theorem 2 is not guaranteed under the stated parameter schedule.
- [Section 4.3, Algorithm 2 and Eq. (17)] Algorithm 2's restart loop consumes 2B0m fresh trajectories per restart and repeats K_restart = 3 log n times; Step 8 then uses the remaining n - 2B0mK_restart trajectories. Substituting the schedule in Eq. (17), with η = c m/n and m = c h ν_min^{-1} log(n/δ), gives 2B0m = (2c1/c) h n log(n/δ), so the total restart consumption is (6c1/c) h n log^2(n/δ). This exceeds the available n whenever h log^2(n/δ) is larger than a universal constant. Eq. (12) only ensures n ≥ c1 h^3 ν_min^{-1} log^4(n/δ), which does not prevent h log^2(n/δ) from being large; for example h = 2 and log(n/δ) = 10 already violate the budget. Thus Algorithm 2 as stated is not guaranteed to have enough data to run, and the probability statement of Theorem 2 applies to an object that may be undefined. This also affects Proposition 7 and Algorithm 3, both of which call Algorithm 2.
minor comments (4)
- [Section 6.4, Eq. (48)] The displayed bound in Eq. (48) writes Σ^* rather than Σ^*_G in the leading variance term; the statement of Theorem 2 and Lemma 11 use Σ^*_G, so this appears to be a typo.
- [Abstract and Section 4.3, Eq. (12)] The abstract says the sample complexity depends only on the occupancy measure of the subset, but Eq. (12) also depends on the effective horizon h and on log^4(n/δ); the body is more careful, and the abstract should be qualified accordingly.
- [Appendix C, proof of Proposition 8] The proof invokes 'Theorem 5.39 of ?' with an unresolved citation placeholder; the reference should be supplied.
- [Throughout] There are several typos and minor wording issues, e.g., 'vaiance', 'cooreponding', 'unavaoidable', and 'asymptotical in distribution'; these should be corrected in a revision.
Circularity Check
No significant circularity: the subgraph Bellman bounds are derived by verifying independent ROOT-SA contraction conditions, not by restating inputs.
full rationale
The paper's central upper bound (Theorem 2) is not circular: it constructs an empirical subgraph Bellman operator and reduces its finite-sample analysis to the ROOT-SA stochastic-approximation theory of Mou et al. (2022a). The cited ROOT-SA corollaries are general contraction theorems whose stated assumptions (Eqs. 13-14, linear multi-step contractive operator, Lipschitz and noise bounds) do not include the subgraph Bellman result; the paper verifies these assumptions independently in Lemmas 9-11, via Eq. (47), Eq. (51), and the covariance identity in Lemma 11. The asymptotic benchmark (Lemma 1) is derived from first principles by CLT/Slutsky arguments, and the lower bounds (Proposition 8, Theorem 3) are separate minimax constructions rather than consequences of the upper bound. No fitted parameter is renamed a prediction: the preconditioning weights w are estimated on an auxiliary dataset (Eq. 16), while the main ROOT-SA run uses the remaining trajectories, and the sample-size condition Eq. (12) is stated for a fixed subgraph rather than derived from the target error. The exit-probability term is not definitionally forced; it is bounded in Proposition 5 and shown unavoidable in Theorem 3 by a two-point construction over a class defined independently of the estimator. I did flag two non-circular correctness gaps: the proof of Eq. (47) requires n_A >= c h^3/ν_min log(|G|/δ), while the stated schedule Eq. (17) sets n_A = c h/ν_min log(n/δ), and Algorithm 2's restart consumption 2B_0 m K_restart can exceed the available n. These affect the validity of the stated guarantee but are not instances of equivalence-by-construction or fitted-input-as-prediction. The self-citations to Mou et al. (2022a, 2023, 2024) are load-bearing for the ROOT-SA machinery, but they are prior-work theorems with independent hypotheses, so they do not make the derivation circular.
Assumptions & free parameters
assumptions (5)
- domain assumption Assumption (Eff(h)): for every state, E[T_H^p] ≤ p! h^p for all p ≥ 1.
- domain assumption Rewards are bounded, |R_t| ≤ 1 almost surely (Eq (2)).
- domain assumption Trajectories are i.i.d. from a tabular MRP with terminal state H hit almost surely, and occupancy ν(s) > 0 on reachable states.
- standard math ROOT-SA oracle results from Mou et al. (2022a) are applied to the constructed operator f.
- standard math Cheikhi and Russo (2023) asymptotic TD variance formula is taken as input for Proposition 1.
Cite this review
Pith. "Pith review of To bootstrap or to rollout? An optimal and adaptive interpolation." pith.science (2026). https://pith.science/paper/KXWIDXKA
@misc{pith2026241109731,
author = {Pith},
title = {Pith review of: To bootstrap or to rollout? An optimal and adaptive interpolation},
year = {2026},
howpublished = {\url{https://pith.science/paper/KXWIDXKA}},
note = {Machine review of arXiv:2411.09731}
}
read the original abstract
Bootstrapping and rollout are two fundamental principles for value function estimation in reinforcement learning (RL). We introduce a novel class of Bellman operators, called subgraph Bellman operators, that interpolate between bootstrapping and rollout methods. Our estimator, derived by solving the fixed point of the empirical subgraph Bellman operator, combines the strengths of the bootstrapping-based temporal difference (TD) estimator and the rollout-based Monte Carlo (MC) methods. Specifically, the error upper bound of our estimator approaches the optimal variance achieved by TD, with an additional term depending on the exit probability of a selected subset of the state space. At the same time, the estimator exhibits the finite-sample adaptivity of MC, with sample complexity depending only on the occupancy measure of this subset. We complement the upper bound with an information-theoretic lower bound, showing that the additional term is unavoidable given a reasonable sample size. Together, these results establish subgraph Bellman estimators as an optimal and adaptive framework for reconciling TD and MC methods in policy evaluation.
Reference graph
Works this paper leans on
-
[1]
TD or not TD: Analyzing the Role of Temporal Differencing in Deep Reinforcement Learning
A. Amiranashvili, A. Dosovitskiy, V. Koltun, and T. Brox. TD or not TD : Analyzing the role of temporal differencing in deep reinforcement learning. arXiv preprint arXiv:1806.01175 ,
-
[9]
(Cited on page 15.) J. Peng and R. J. Williams. Incremental multi-step Q-learning. In Machine Learning Proceedings 1994, pages 226–232. Elsevier,
work page 1994
-
[13]
The value function of interest takes the form V ˚ :“ ψpϑq :“ pI ´P q´1r. Let the loss function be ℓpV1,V 2q “ pV1ps0q ´V2ps0qq2. According to the local asymptotic minimax theorem ( H´ ajek, 1972; ?), we have sup ∆ ą0 lim inf nÑ`8 sup P PNtranpP0,∆ {?nq rPNrwdpr0,∆ {?nq n ¨ E ”ˇ ˇ ˇpVnps0q ´V ˚ P,rps0q ˇ ˇ ˇ 2ı ě “ ∇ψpϑ0qJ ¨J : ϑ0 ¨ ∇ψpϑ0q ‰ s0,s0 , (66) w...
work page 1972
-
[1954]
Demystifying the Recency Heuristic in Temporal-Difference Learning
(Cited on page 1.) B. Daley, M. C. Machado, and M. White. Demystifying the recency he uristic in temporal-difference learning. arXiv preprint arXiv:2406.12284 ,
-
[1992]
(Cited on page 2.) M. White and A. White. A greedy approach to adapting the trace par ameter for temporal difference learning. In Proceedings of the 2016 International Conference on Autono mous Agents & Multiagent Systems, pages 557–565,
work page 2016
- [1994]
-
[1997]
Effective Multi-step Temporal-Difference Learning for Non-Linear Function Approximation
(Cited on page 4.) H. van Seijen. Effective multi-step temporal-difference learning for non-linear function approximation. arXiv preprint arXiv:1608.05151 ,
-
[2000]
(Cited on page 4.) K. Khamaru, A. Pananjady, F. Ruan, M. J. Wainwright, and M. I. Jo rdan. Is temporal difference learning optimal? An instance-dependent analysis. arXiv preprint arXiv:2003.07337 ,
arXiv 2003
Show all 13 references
-
[2009]
(Cited on page 2.) T. A. Mann, H. Penedones, S. Mannor, and T. Hester. Adaptive lam bda least-squares temporal difference learning. arXiv preprint arXiv:1612.09465 ,
-
[2014]
Cheikhi and D
(Cited on page 4.) D. Cheikhi and D. Russo. On the statistical benefits of temporal d ifference learning. arXiv preprint arXiv:2301.13289,
-
[2017]
(Cited on page 37.) W. Mou, K. Khamaru, M. J. Wainwright, P. L. Bartlett, and M. I. Jor dan. Optimal variance-reduced stochastic approximation in banach spaces. arXiv preprint arXiv:2201.08518, 2022a. (Cited on pages 4, 13, 14, 15, and 39.) W. Mou, M. J. Wainwright, and P. L. ...
-
[2020]
(Cited on page 4.) Z. Chen, S. Maguluri, S. Shakkottai, and K. Shanmugam. A Lyapuno v theory for finite-sample guaran- tees of asynchronous Q-learning and TD-learning variants. arXiv preprint arXiv:2102.01567 ,
-
[2024]
Murthy, I
(Cited on pages 4 and 16.) Y. Murthy, I. Grosof, S. Th. Maguluri, and R. Srikant. Performan ce of NPG in countable state-space average-cost RL. arXiv preprint arXiv:2405.20467 ,
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.