{"id":"c9240722-1838-4b78-b4a1-0fb178560b35","arxiv_id":"2411.09731","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Subgraph Bellman operators give a policy evaluation estimator whose finite-sample error nearly matches TD's optimal asymptotic variance while retaining MC's occupancy-adaptive sample complexity.","lead":"Reinforcement learning methods usually either estimate future rewards recursively (bootstrapping) or average full rollouts (Monte Carlo). This paper constructs estimators that mix the two according to a chosen subset of states, and proves a near-optimal balance between low variance and low sample need.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Restart/burn-in budget in Eq (17) demands more trajectories than the theorem's sample size supplies, so Algorithm 2 cannot run as stated; the stated upper bound is not yet established.","rationale":"Read in good faith: the paper's contribution is a new subgraph Bellman operator and a claimed finite-sample guarantee combining TD variance and MC adaptivity. For that guarantee to hold, Algorithm 2 must actually be runnable with the stated parameter choices and must satisfy the contraction condition (47). The restart budget arithmetic shows the algorithm as stated is not executable when h log^2(n/δ) is non-negligible, which is the typical regime; and the nA schedule is insufficient for (47). Both are internal inconsistencies, not disagreements with consensus. The reader's weakest_assumption focused on (47) and the auxiliary sample size; the reader's rationale also flagged the restart burn-in budget, so our agreement is partial. We do not see a deeper flaw in the subgraph Bellman construction or the variance decomposition; the asymptotic analysis (Lemma 1, Proposition 5) and lower bound (Theorem 3) are coherent and appear to support the claimed qualitative trade-off. The problems are in the stochastic-approximation implementation and its proof, which are repairable by rescheduling nA and restart consumption (or by reusing data with a fresh independence argument). Hence the reader's CONDITIONAL verdict is appropriate; we would not move it to ACCEPT or REJECT. Credit: the paper has detailed proofs, explicit parameter choices, and the lower bound is a real addition; no machine-checked proofs or experiments, consistent with a theory paper.","tokens_in":58874,"tokens_out":11627,"duration_ms":110837,"concrete_test":"Instantiating h = 2, ν_min = 1, log(n/δ) = 10, |G| = 1 in Eq (17), compute 2B0mK_restart and compare with n; show it exceeds n. Then re-derive Theorem 2 after changing the schedule to nA = c h^3 ν_min^{-1} log(n/δ) and with restart consumption capped at n/2, and check whether the leading variance term and the sample complexity n/log^4(n/δ) ≥ c h^3/ν_min survive. If they do not, the abstract's claim of 'sample complexity depending only on the occupancy measure' must be weakened.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Algorithm 2's Step 5 consumes 2B0m fresh trajectories per restart and repeats K_restart = 3 log n times, then Step 8 uses the remaining n - 2B0mK_restart trajectories. Under the schedule in Eq (17), B0 = c1 h/η log(n/δ) and η = cm/n, so B0 = c1 ν_min n/c^2. Therefore 2B0m = (2c1/c) h n log(n/δ), and the total restart consumption is 2B0mK_restart = Ω(h n log^2(n/δ)). This exceeds the available n whenever h log^2(n/δ) is larger than a universal constant. The theorem's sample-size condition Eq (12) only ensures n ≥ c1 h^3 ν_min^{-1} log^4(n/δ); nothing prevents h log^2(n/δ) from being large (e.g., h = 2, log(n/δ) = 10). Thus for standard parameter regimes Algorithm 2 requests more trajectories than it is given, making Theorem 2's guarantee vacuous for the stated algorithm. A related but independent gap: the proof of Eq (47) needs nA ≥ c h^3 ν_min^{-1} log(|G|/δ), while Eq (17) sets nA = c h ν_min^{-1} log(n/δ), a factor h^2 smaller; so the contraction condition used for Lemma 9 and the ROOT-SA analysis is not guaranteed under the stated schedule.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":59153,"tokens_out":9531,"duration_ms":92079,"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":[{"comment":"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":"Section 6.4, proof of Eq. (47), vs. Eq. (17)"},{"comment":"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.","section":"Section 4.3, Algorithm 2 and Eq. (17)"}],"minor_comments":[{"comment":"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.","section":"Section 6.4, Eq. (48)"},{"comment":"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.","section":"Abstract and Section 4.3, Eq. (12)"},{"comment":"The proof invokes 'Theorem 5.39 of ?' with an unresolved citation placeholder; the reference should be supplied.","section":"Appendix C, proof of Proposition 8"},{"comment":"There are several typos and minor wording issues, e.g., 'vaiance', 'cooreponding', 'unavaoidable', and 'asymptotical in distribution'; these should be corrected in a revision.","section":"Throughout"}],"recommendation":"major_revision","confidential_remarks":"The paper's conceptual framework and lower-bound analysis are solid and likely repairable, but the two parameter-schedule inconsistencies in Theorem 2 are central: they concern the sample budget of the stated algorithm and the contraction condition on which the ROOT-SA guarantee rests. I would like to see the authors either revise the parameter schedule and prove the corresponding conditions, or state a version of Theorem 2 under explicit conditions that include the data-budget inequality and the n_A condition needed for Eq. (47)."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here is the short version: the subgraph Bellman operator is a genuinely new construction, and pairing it with an instance-dependent lower bound is a real contribution. But the main finite-sample theorem for the ROOT-SA algorithm has a load-bearing parameter scheduling bug. As written, Algorithm 2 can ask for more trajectories than the theorem's sample size supplies, and the weight vector w is not guaranteed to satisfy the contraction condition under the stated sample sizes.\n\nThe construction itself is nice. Indexing the Bellman fixed-point equation by a subset G, with Monte Carlo rollouts on exit, is a clean way to interpolate between TD and MC. The asymptotic variance analysis (Lemma 1 and Proposition 5) makes the trade-off quantitative and is, as far as I can tell, correct. Theorem 1's plug-in analysis is detailed and looks sound. The lower bound in Theorem 3 is a useful complement: it correctly separates the occupancy-based term from the TD variance, and it does not rely on the problematic SA argument.\n\nThe trouble is Theorem 2. The proof of the key contraction condition (47) requires nA >= c h^3 / nu_min log(|G|/delta), but the schedule in Equation (17) only allocates nA = c h / nu_min log(n/delta), a factor h^2 smaller. Without (47), Lemma 9 and the entire ROOT-SA analysis do not fire. Independent of that, the restart budget in Algorithm 2 does not close. Each restart consumes 2B0m fresh trajectories, and K_restart = 3 log n, giving an overall restart consumption of order h n log^2(n/delta). That exceeds the available n whenever h log^2(n/delta) is large, which the sample size condition in Equation (12) does not prevent. So, for many perfectly legal parameter regimes, the algorithm cannot actually be run with the stated guarantees.\n\nBoth issues may be repairable by changing the schedule, but at the price of a worse dependence on h or on logarithmic factors. The authors mention they do not optimize the h-dependence, but that does not address the budget mismatch. I think this paper deserves a serious referee, but the referee should insist on a revised schedule and a careful accounting of the data budget. If Theorem 2 is fixed, the paper becomes an important contribution. As it stands, the advertised best-of-both-worlds guarantee for the SA algorithm is not yet supported.\n\nWho is this for? Anyone working on policy evaluation theory, finite-sample stochastic approximation, or the TD/MC trade-off. The subgraph operator and the lower bound are worth engaging with now; the ROOT-SA part should be treated skeptically until patched.","headline":"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.","tokens_in":59708,"tokens_out":3052,"would_cite":true,"duration_ms":29843,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Subgraph Bellman estimators match TD's variance while keeping Monte Carlo's occupancy-based sample complexity.","keywords":["policy evaluation","temporal difference learning","Monte Carlo estimation","subgraph Bellman operator","finite-sample bounds","minimax lower bound","stochastic approximation","Markov reward process"],"falsifier":"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.","tokens_in":58629,"feed_emoji":"🎯","tokens_out":9122,"duration_ms":84233,"temperature":0.7,"pith_summary":"Reinforcement learning has two classical ways to estimate a value function: bootstrapping, which solves a Bellman fixed-point equation and enjoys low variance (TD), and rollout, which averages entire trajectories and adapts to how often a state is visited (Monte Carlo). This paper proposes a family of subgraph Bellman operators that interpolate between the two by choosing a subset G of states: inside G the estimator bootstraps, while outside G it averages rollout rewards. The main claim is that the fixed-point estimator inherits the low, asymptotically optimal TD variance up to an additive term governed by the probability of exiting G, while needing only a sample size roughly $h^3/\\nu_{\\min}(G)$ — set by the occupancy of G, not by the size of the whole state space. An information-theoretic lower bound proves the additive exit-probability term is unavoidable unless the sample size grows polynomially with the state space. Together these results identify an optimal and adaptive interpolation, with an implementable algorithm based on variance-reduced stochastic approximation.","feed_headline":"Subgraph Bellman operator claims TD variance with MC sample sizes","feed_subtitle":"Frequently visited states get near-optimal accuracy even when the state space is enormous.","key_machinery":"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)$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the closed-form asymptotic variances of TD and MC and the trajectory-pooling gap that motivates the interpolation; its Corollary B.6 appears as Proposition 1 and its Proposition B.4 drives the transient-subgraph variance simplification.","marker":"Cheikhi and Russo (2023)"},{"why":"Provides the ROOT-SA variance-reduced stochastic approximation algorithm and the finite-sample guarantees (Corollaries 3 and 4) that Theorem 2 applies to the subgraph fixed point.","marker":"Mou et al. (2022a)"},{"why":"Defines temporal-difference learning and the TD($\\lambda$) family that the paper positions as an alternative, non-optimal interpolation baseline.","marker":"Sutton (1988)"},{"why":"Supplies the local asymptotic minimax theorem used in Proposition 8 to certify that TD's asymptotic variance is optimal in the infinite-sample limit.","marker":"Hájek (1972)"},{"why":"Provides the vector-valued Bernstein inequality used in the proof of Lemma 8 to control the additive noise term in finite samples.","marker":"Minsker (2017)"},{"why":"Supplies the multi-fold sample-splitting variance-estimation technique behind Proposition 7 and the data-driven subgraph selection algorithm.","marker":"Xia et al. (2023)"}],"fun_headline_variants":["Subgraph Bellman operator: TD variance, MC adaptivity","Bootstrapping and rollout, optimally reconciled","Exit-probability term proven unavoidable for policy eval","New Bellman fixed point balances TD and MC trade-offs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Subgraph Bellman operator: TD variance, MC adaptivity","Bootstrapping and rollout, optimally reconciled","Exit-probability term proven unavoidable for policy eval","New Bellman fixed point balances TD and MC trade-offs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000255,"raw_usage":{"total_tokens":1632,"prompt_tokens":1068,"completion_tokens":564,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":684,"completion_tokens_details":{"reasoning_tokens":500}},"tokens_in":684,"tokens_out":564,"duration_ms":6371,"temperature":1.0,"reasoning_tokens":500,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T20:23:02.546368+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}