{"id":"1a02b7de-618f-49c6-87c4-5ce8fffb8bf4","arxiv_id":"2607.14555","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"The variance of MCTS Q-estimators decomposes into reward, transition, and successor-value uncertainty; a new recursive estimator corrects the asymptotically biased i.i.d. sample-variance formula.","lead":"This paper shows that the standard sample-variance formula for Q-function estimates in Monte Carlo tree search is biased and stays biased even after many samples, because it ignores uncertainty shared through successor value estimates. The authors derive the correct variance decomposition, propose a recursive estimator with an efficient node-local update, and report faster optimal-action selection on inventory and kidney-donation benchmarks.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (12c)-(12d) replace Var(V̂(s'_i))—the variance of a max over actions—with Var(Q̂(s'_i,a*)), an unproven and generally false identity; Theorem 5's assumption (iii) is therefore not satisfied by the implemented estimator, so the central consistency claim is unsupported even under the paper's ideal","rationale":"The reader's weakest assumption focused on the independence assumption underlying Theorem 1, which the paper explicitly acknowledges as an idealization. That is a real limitation, but the more direct threat to the central claim is the unexamined substitution in Eqs. (12c)–(12d): the recursive estimator needs Var(V̂(s'_i)) but supplies Var(Q̂(s'_i,a*)). This is not a missing proof step that can be patched by citing independence; it is a mismatch between the quantity required by the variance decomposition and the quantity the algorithm actually computes. Assumption (iii) of Theorem 5 essentially requires the recursive estimator to converge to Var(V̂(s'_i)), so the proof is circular unless the identity Var(max_a Q̂_a)=Var(Q̂_{a*}) holds, which is generally false. The reader's rationale did mention 'ignoring the max-operator variance' as one of several gaps, so our concern partially overlaps with the reader's analysis, but the reader's stated weakest assumption was the independence condition. We therefore mark agreement as partial. Because the concern is addressable in revision (either by proving the needed identity under additional assumptions or by modifying the estimator to track Var(V̂(s')) directly), the existing CONDITIONAL verdict remains appropriate; our read does not change it.","tokens_in":19006,"tokens_out":6525,"duration_ms":70574,"concrete_test":"Construct a depth-2 MDP with one root action leading to a single successor state s' that has two actions A and B. Let the rewards for A and B be drawn from known distributions with equal means (so true Q(s',A)=Q(s',B)) but different variances, and allocate different sample sizes to A and B. Compute the true Var(V̂(s'))=Var(max(Q̂_A,Q̂_B)) either analytically (e.g., Gaussian rewards) or by many independent Monte Carlo repetitions. Compare this with Var(Q̂(s',a*)) for a* the empirical best action, which is what Eq. (12c) uses. Then compute the true Var(Q̂(s₀,a)) at the root by simulation and compare with the recursive estimator ζ̂²(s₀,a) from Eq. (12). If the gap does not vanish as sample sizes grow, the substitution in Eq. (12c) is invalid and the consistency claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The recursive estimator in Eq. (12) is claimed to be consistent for ζ²(s,a)=Var(Q̂(s,a)). In the Bellman recursion, the successor value is V̂(s'_i)=max_a Q̂(s'_i,a), so Theorem 1's decomposition (Eq. 4) requires Var(V̂(s'_i)). But the implemented estimator sets ζ̂²(s'_i)=ζ̂²(s'_i,a*) with a*=argmax Q̂(s'_i,a) (Eqs. 12c–12d). This substitutes the variance of the Q-estimator at the empirical best action for the variance of the max of correlated Q-estimators. These are not equal in general: the max operator introduces covariance terms and randomness of the argmax, so Var(max_a Q̂_a) ≠ Var(Q̂_{a*}) for a fixed or empirical a*. Theorem 5's assumption (iii) explicitly requires convergence of ζ̂²(s'_i) to Var(V̂(s'_i)), but no argument or condition connects ζ̂²(s'_i,a*) to Var(V̂(s'_i)). Thus the consistency proof assumes what the estimator must deliver. The numerical section (Section VI) measures only the local component N(s₀,a*)ζ̂²_iid, not the recursive ζ̂²(s₀,a*), so the experiments cannot detect this mismatch. Even under the idealized two-stage independence assumption stated before Theorem 1, the central claim is not established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies variance estimation for Q-function estimators in finite-horizon MDP tree search. It derives a variance decomposition for \\hat Q(s,a) (Theorem 1), shows that the standard i.i.d. sample variance is asymptotically biased (Theorems 2 and 3), and introduces a recursive variance estimator (Eq. (12)) claimed to be consistent (Theorem 5). To make the estimator practical, the paper develops a node-local statistics update that is shown to be algebraically equivalent to exact updating (Theorem 6), and integrates the estimator into OCBA and UCB1-Tuned selection rules. Numerical experiments on inventory control and kidney paired donation problems report improved empirical probability of correct selection relative to a baseline that uses the approximate variance estimator.","tokens_in":19374,"tokens_out":8285,"duration_ms":87048,"significance":"If fully established, the variance decomposition and a genuinely consistent recursive estimator would be valuable contributions to variance-aware MCTS, particularly for OCBA-style sample allocation. The node-local implementation (Theorem 6) is a strong and verifiable computational contribution: it exactly reproduces the full-history update with per-node statistics. The numerical results are suggestive and the paper is clearly written. However, the central theoretical claim—consistency of the implemented estimator—is not currently supported, because the recursive definition substitutes a different quantity from the one appearing in the variance decomposition, and the consistency proof relies on an unverified rate condition. The paper's own caveats in Sections II-B, V, and VI acknowledge parts of this gap, but the abstract and conclusion state the consistency result without those qualifications.","major_comments":[{"comment":"The recursive estimator sets \\hat\\zeta^2(s'_i) = \\hat\\zeta^2(s'_i, a^*) with a^* = argmax Q(s'_i, a) (Eqs. (12c)-(12d)). However, Theorem 1's decomposition (Eq. (4)) requires Var(\\hat V(s'_i)), where \\hat V(s'_i) = max_a \\hat Q(s'_i,a). The variance of a maximum of correlated estimators is not generally equal to the variance of the estimator at the empirical best action; the max operator introduces covariance terms and randomness of the argmax. No condition or argument is provided under which the two coincide. Consequently, \\hat\\zeta^2(s,a) as implemented is not an estimator of the \\zeta^2(s,a) defined in Eq. (2), and Theorem 5's conclusion does not apply to the algorithm used in Section V. The numerical section does not remedy this: Section VI explicitly measures only the local component N(s_0,a^*)\\hat\\zeta^2_{iid}(s_0,a^*), not the recursive \\hat\\zeta^2(s_0,a^*).","section":"Section III-B, Eqs. (12a)-(12d)"},{"comment":"The consistency proof assumes a rate condition, N(s,a) \\sum_i |\\hat p_i^2 \\hat\\zeta^2(s'_i) - p_i^2 Var(\\hat V(s'_i))| \\xrightarrow{p} 0, which is essentially the inductive conclusion one would need at successor nodes. The update rules in Algorithm 1 do not guarantee this rate: sample counts N(s',i) are random and may be of the same order as N(s,a), so the scaled difference need not vanish from the recurrence alone. The paragraph following Theorem 5 acknowledges that the condition can fail if successor estimates are noisy, but the paper does not supply a separate proof that the proposed updates satisfy (iii). Thus the central consistency claim is conditional on an unverified assumption that is as strong as the theorem itself.","section":"Theorem 5, assumption (iii)"},{"comment":"The variance decomposition assumes that the successor estimators {\\hat V(s'_i)} are independent across i and jointly independent of the current-period transitions and rewards. The paper correctly states that this is an 'idealized two-stage sampling scheme' and that in online MCTS the samples used to update \\hat V and \\hat Q are intertwined. Because both the decomposition (4) and the recursive estimator (12) rely on this assumption, the unqualified statement in the abstract that the proposed estimator is consistent is not supported for the actual algorithms in Section V. The manuscript should either develop a formal analysis for the shared-sample setting or explicitly restrict the consistency claim to the idealized scheme; the current presentation leaves the practical claim unproven.","section":"Section II-B, paragraph before Theorem 1"},{"comment":"The statement of Theorem 4 is internally inconsistent as written. It says 'the true mean, variance, and transition probability are used, i.e., \\hat V(s'_i)=E[\\hat V(s'_i)], \\hat\\zeta^2(s'_i)=Var(\\hat V(s'_i)), \\hat p_i=p_i.' If \\hat V(s'_i) is set equal to its expectation, then the estimator is deterministic and Var(\\hat V(s'_i))=0, contradicting the nonzero successor variance appearing in the same sentence and in the conclusion. The proof's invocation of Theorem 3 also conditions on a realization of \\hat V, not on its mean. The intended meaning is presumably that the estimator correctly uses the population moments, but as written the theorem and its proof are not coherent and should be rewritten.","section":"Theorem 4"}],"minor_comments":[{"comment":"The notation '− →' is garbled; it should be a standard convergence arrow (e.g., '\\xrightarrow{p}' or '\\to'). Please correct throughout.","section":"Theorems 2 and 3"},{"comment":"In the random-transition example of Fig. 4, the values used for \\hat V(s_1) and \\hat V(s_2) (implicitly 1 and 2) are not stated. The reader must infer them from the computation \\hat Q = 0.5(1.5+1) + 0.5(3.5+2). Please make these values explicit.","section":"Section IV-C, example"},{"comment":"The variance-estimation error metric is defined as the MAPE of N(s_0,a^*)\\hat\\zeta^2_{iid}(s_0,a^*) — i.e., the local component. The paper should state more prominently that this metric does not evaluate the recursive estimator \\hat\\zeta^2(s,a), and that the empirical improvements in PCS do not by themselves validate the consistency claim.","section":"Section VI"},{"comment":"The author biographies contain 'PLACE PHOTO HERE' placeholders; these should be removed before submission.","section":"Author biographies"}],"recommendation":"major_revision","confidential_remarks":"The gap in the consistency proof is load-bearing and is acknowledged, at least partly, in the manuscript itself (Section II-B, the paragraph after Theorem 5, and the metric definition in Section VI). I do not see this as a case for immediate rejection: the node-local update is exact and the numerical results are promising. However, the authors need to either (a) revise the estimator so it actually estimates Var(\\hat V(s'_i)) in the recursion, or (b) state and prove a concrete set of conditions under which the current substitution is asymptotically valid, and then provide a proof of assumption (iii) under those conditions. If such a proof is not possible, the claims should be downgraded from 'consistent' to a heuristic, and the abstract/conclusion revised accordingly. The appeal of the paper for an IEEE journal will depend on whether the central theoretical claim can be made rigorous."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper identifies a real bias in the i.i.d. sample variance for Q-estimators in finite-horizon MCTS and gives an exact, inexpensive node-local update for that variance component. But the central claim—that the recursive estimator is consistent—is not supported. Eq. (12) replaces Var(V̂(s')), the variance of a max over actions, with Var(Q̂(s',a*)) at the empirical best action. Those are not equal in general, and no argument connects them. So Theorem 5's assumption (iii) is not satisfied by the implemented estimator; the consistency proof assumes successor variance estimates converge to the quantity the theorem must deliver.\n\nWhat's solid: Theorem 1's decomposition is correct under the stated two-stage independence, and the authors are upfront that online MCTS violates it. Theorem 2's bias limit is right. The node-local statistics of Section IV—storing reward mean/variance per successor and reconstructing the sample variance—is genuinely useful and provably equivalent to the full-history update. That part is clean.\n\nSoft spots, in proportion: the main one is the consistency gap above. A second: the numerical section deliberately tracks only the local component N ζ̂²_iid, not the recursive ζ̂², so the experiments cannot validate the headline claim. They do show the node-local update removes the bias in the local component, and PCS improves, but the improvement could be coming from the node-local update rather than the recursive correction. A third, acknowledged by the authors: the independence assumption is violated in the actual algorithm, so the decomposition describes an idealized scheme.\n\nIf the authors redefine ζ̂²(s') to estimate Var(V̂(s'))—or prove convergence of the max estimator's variance—and report the full recursive estimator in experiments, this becomes a solid paper. As it stands it is a good heuristic with a clean partial theory.\n\nRecommendation: send to peer review. The core idea is worth a serious referee, but expect major revision. I would want to see the consistency claim either proven or explicitly downgraded.","headline":"Real bias result and a clean node-local variance update, but the recursive estimator's consistency claim is load-bearing and unproven; deserves a serious referee, not acceptance as-is.","tokens_in":19870,"tokens_out":2769,"would_cite":true,"duration_ms":32104,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C40","62F12","62L20"],"pacs":[],"model":"deepseek-v4-flash","headline":"The usual sample-variance formula for Q-function estimates in tree search is biased downward even at infinite sample size; a recursive estimator that propagates successor-state variance is consistent and practical.","keywords":["Monte Carlo tree search","Q-function estimation","variance estimation","Markov decision process","finite-horizon MDP","OCBA","UCB1-Tuned","consistency"],"falsifier":"Construct a small finite-horizon MDP with one state, one action, a deterministic transition to a single successor, and random rewards. Compute the true replication variance of Q̂ at the root by many independent full-tree runs, and compare it with (a) the i.i.d. sample variance formula and (b) the recursive estimator as N grows. If the i.i.d. estimate's bias does not converge to the variance of the successor value estimate, or if the recursive estimate's scaled error N(ζ̂²−ζ²) does not converge in probability to zero, the paper's central consistency claim is false.","tokens_in":18823,"feed_emoji":"🌳","tokens_out":9681,"duration_ms":88142,"temperature":0.7,"pith_summary":"This paper targets a persistent blind spot in Monte Carlo tree search (MCTS) for finite-horizon Markov decision processes: the uncertainty of a state-action (Q-function) estimate is normally computed as if each simulated path were an independent draw, but paths that reach the same successor state share the same value estimate, so the usual sample variance undercounts the true uncertainty—and the undercount does not vanish as more simulations are collected. The paper proves a variance decomposition, identifies the missing term as the probability-weighted variance of successor value estimates, and builds a recursive estimator that adds that term back. It then gives an implementation that stores only local reward statistics per successor, matching the exact computation without storing full histories. Embedded in two common selection rules (OCBA and UCB1-Tuned), the estimator improves the probability of selecting the optimal first action in inventory-control and kidney-donation test problems.","feed_headline":"Standard MCTS variance estimate stays biased at the limit","feed_subtitle":"A recursive, node-local estimator fixes the bias; inventory and kidney-donation tests find right first action faster.","key_machinery":"The load-bearing object is the recursive variance estimator of Eq. (12): ζ̂²(s,a) = ζ̂²_iid(s,a) + Σ_i p̂_i² ζ̂²(s'_i), where ζ̂²_iid is the ordinary sample variance of augmented path returns and p̂_i is the empirical transition frequency. The correction term adds back the variance of the successor value estimates, weighted by squared transition probabilities—precisely the component that survives in the limit and that the i.i.d. formula omits. To make the estimator practical, the paper derives a node-local statistics scheme (Eqs. 14–17) that keeps per-successor reward mean, reward variance, and transition counts, and reconstructs the same Q̂ and sample variance as the exact stored-history co","core_discovery":"The paper's central claim is that the sample variance estimator built on i.i.d. path returns, ζ̂²_iid(s,a) in Eq. (3), is biased for the variance of the Q-function estimator Q̂(s,a), with the bias converging to Σ p_i² Var(V̂(s'_i)) rather than zero when successor value estimates are uncertain (Theorem 2). In its place the paper defines a recursive estimator, ζ̂²(s,a) = ζ̂²_iid(s,a) + Σ p̂_i² ζ̂²(s'_i) (Eq. 12), and proves (Theorem 5) that under convergence of the value estimates, vanishing successor variance, and convergence of the successor variance estimates at a suitable rate, N(s,a)(ζ̂²(s,a) − ζ²(s,a)) converges in probability to zero. The supporting decomposition (Theorem 1) separates t","pith_inferences":["Editorial inference: the consistency proof relies on an idealized two-stage sampling setup in which successor value estimates are independent of current-node samples; in a live MCTS the samples are shared, so a direct comparison of the recursive estimator against an exact stored-history computation under the identical sample stream would reveal whether the correction stays calibrated outside the i","Editorial inference: the same correction principle—adding the probability-weighted variance of the bootstrapped target—could apply to other reinforcement-learning estimators in which a shared value estimate enters many samples, e.g., off-policy value learning, where the target's own uncertainty is usually ignored.","Editorial inference: the recursive variance could drive adaptive branching or early stopping decisions; a node whose variance is dominated by successor uncertainty is a candidate for deeper expansion rather than additional samples at the current node, a direction the paper mentions as future work."],"forward_implications":["If the recursive estimator is correct, MCTS selection rules that consume variance estimates (OCBA and UCB1-Tuned) will allocate samples according to the true variance of Q̂, raising the empirical probability of selecting the optimal first action at a fixed simulation budget.","Because the estimator is recursive, variance information propagates through the tree period by period; the bias correction does not fade as the horizon grows, which matters for long-horizon problems like the H=10 inventory and kidney-donation tests.","The node-local implementation makes the consistent estimator usable inside online backpropagation loops without storing full path histories or recomputing from scratch, so the consistency result is not just asymptotic but implementable.","The i.i.d. estimator's bias is nonzero in the limit whenever successor value estimates carry uncertainty, so any variance-aware tree policy built on the old estimator will systematically under-explore actions whose successors are still uncertain."],"fun_headline_variants":["MCTS variance: i.i.d. bias persists, recursive estimator fixes","Bias in MCTS Q-variance won't vanish; recursive method solves","Node-local recursive estimator beats i.i.d. variance bias in MCTS","Recursive variance estimator repairs biased MCTS Q-functions","For MCTS Q-estimators, i.i.d. variance bias is here to stay"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing assumption is that the successor value estimators V̂(s'_i) are independent of each other and of the current node's transition and reward samples; the paper itself notes that online MCTS intertwines the samples, so if the real correlation structure differs from that idealization, the recursive correction may be miscalibrated and the consistency proof does not directly cover the implemented algorithm.","fun_headline_variants_meta":{"raw":{"variants":["MCTS variance: i.i.d. bias persists, recursive estimator fixes","Bias in MCTS Q-variance won't vanish; recursive method solves","Node-local recursive estimator beats i.i.d. variance bias in MCTS","Recursive variance estimator repairs biased MCTS Q-functions","For MCTS Q-estimators, i.i.d. variance bias is here to stay"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000223,"raw_usage":{"total_tokens":1297,"prompt_tokens":750,"completion_tokens":547,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":494,"completion_tokens_details":{"reasoning_tokens":449}},"tokens_in":494,"tokens_out":547,"duration_ms":5719,"temperature":1.0,"reasoning_tokens":449,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T01:45:39.132702+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a small finite-horizon MDP with one state, one action, a deterministic transition to a single successor, and random rewards. Compute the true replication variance of Q̂ at the root by many independent full-tree runs, and compare it with (a) the i.i.d. sample variance formula and (b) the recursive estimator as N grows. If the i.i.d. estimate's bias does not converge to the variance of the successor value estimate, or if the recursive estimate's scaled error N(ζ̂²−ζ²) does not converge in probability to zero, the paper's central consistency claim is false.","supporting_citations":[],"review_version":1}