{"id":"79175c61-895f-4ffd-8482-6c4312ca6092","arxiv_id":"2412.19299","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"The Markov Recombining Scenario Tree method approximates multistage stochastic programs from two historical trajectories and is claimed to achieve poly(T) sample complexity, avoiding the exponential-in-T sample requirement of SAA.","lead":"This paper proposes a scenario-tree method for multistage stochastic programming under Markovian uncertainty that uses only two historical trajectories and claims a sample complexity polynomial in the time horizon. If the proof held, it would offer a practical route around the exponential sample growth of standard sample-average approximation for long-horizon problems.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 1's Bernstein step conditions on the trajectory, making all but the last summand deterministic, so the stated exponential bound—and hence Theorem 1—is unproven.","rationale":"Proposition 1 is the only place where Markov dependence is converted into a concentration statement; removing it collapses the cascade. The invalid conditioning is not a minor typo: conditional on γ[1:N], for i<N the value Qt+1(xt, γ_{i+1}) is a number, so the claimed independent centered summands do not exist. And ζ_{i+1} are not independent of the conditioning event. This directly contradicts the text 'we can treat the terms ... as independent random variables, since eζ_2,...,eζ_{N+1} are independent.' The proof of the paper's headline sample complexity therefore does not go through as written. A martingale-based repair may be possible because the same expression is a martingale difference sequence with predictable weights; if so, the theorem might survive with essentially the same rate. But the paper does not provide that argument, and the current proof is invalid. The numerical LQG section compounds the issue: Gaussian noise violates bounded support A3 unless truncated, and hyperparameters are missing, so it provides no independent support. These secondary points reinforce but do not replace the main concern. The reader's rationale flags the same Proposition 1 issue, though the reader's formal weakest_assumption focuses on A3, hence partial agreement.","tokens_in":24480,"tokens_out":9733,"duration_ms":89893,"concrete_test":"Independently re-derive Eq. (15) from Proposition 1 using the martingale difference sequence V_i = E_{eγ_i}[Q(xt,eγ_{i+1})] − Q(xt,eγ_{i+1}) with predictable weights w_i = k(∥γ−eγ_i∥)I(∥γ−eγ_i∥≤h), applying Freedman's inequality and bounding ∑_i E[V_i²|F_{i-1}]w_i² by k²N(σ²+3Mh). If the resulting tail is exp(−c N h^p ε²) with constants comparable to (15), the flaw is a repairable proof gap; if the correct rate is slower or requires a mixing-time factor, the sample complexity claim fails. Alternatively, simulate a one-dimensional Doeblin chain with a bounded discontinuous Q, estimate the empirical probability of the event in (14) for N=10^3,...,10^5 and h=N^{-1/3}, and check whether the failure probability matches (15).","verdict_should_be":"REJECT","load_bearing_attack":"Proposition 1 is the key engine: Eq. (15) is used by Corollary 1, Proposition 2, Theorem 2, and Corollary 2 to obtain Theorem 1. Its proof fails at the step from Eq. (25) to Eq. (29). The summands are [E_{eγ_i}Q(xt,eξ_{t+1}) − Q(xt,eγ_{i+1})] with kernel weights. The authors condition on eγ_i=γ_i for all i∈[N] and claim the terms are independent via the Kallenberg representation eγ_{i+1}=φ(eγ_i,ζ_{i+1}). But conditioning on the whole trajectory fixes eγ_2,...,eγ_N. Hence for i<N the second factor Q(xt,eγ_{i+1}) is deterministic, and ζ_2,...,ζ_N are constrained by φ(eγ_i,ζ_{i+1})=eγ_{i+1}; only the i=N term is random. The expression is an affine function of one random variable, not a sum of N independent centered variables, so Bernstein's inequality cannot be applied. The deterministic offset ∑_{i<N} w_i(E_{eγ_i}Q−Q(eγ_{i+1})) is not analyzed. Because all later results invoke Proposition 1, Theorem 1's polynomial-in-T sample complexity is not established by the proof as written. The bound may be repairable with a martingale/Freedman inequality, but that replacement is absent and is exactly where Markov dependence must be handled.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a Markov Recombining Scenario Tree (MRST) method for multistage stochastic programming under an unknown continuous-state Markov process. The method uses two independent historical trajectories and kernel-weighted conditional expectations to build an approximate dynamic program. The main claimed contribution is a non-asymptotic sample complexity of eO(T^{p+3} eps^{-p-2}) for an eps-optimal first-stage solution, in contrast to the exponential-in-T complexity of SAA. The theoretical argument is built on Proposition 1, a concentration inequality for a kernel estimator along a single Markovian trajectory; this proposition is then used to derive uniform generalization bounds, a recursive generalization bound for the approximate value functions, and a suboptimality bound. Numerical experiments on a Linear Quadratic Gaussian control problem compare MRST with SAA.","tokens_in":24762,"tokens_out":9057,"duration_ms":94296,"significance":"If the main theorem were correct, the result would be significant: it would provide the first non-asymptotic sample-complexity guarantee for data-driven multistage stochastic programming under Markovian uncertainty that is polynomial in the horizon, and the proposed estimator is simple and computationally attractive. The paper is well organized, the regularity assumptions are explicit, and the derivations are not circular: the bandwidth h and net width eta are proof parameters rather than quantities fitted to data. The claimed eO(T^{p+3} eps^{-p-2}) bound would address a well-known open challenge. However, the central concentration proof contains a load-bearing error, and the numerical experiments are run under assumptions that the theoretical part does not cover. As it stands, the main claim is not established.","major_comments":[{"comment":"The proof of Proposition 1 is invalid at the Bernstein step. The summands in Eq. (25) are D_i = E_{gamma_i}[Q(x_t, phi(gamma_i, zeta_{i+1}))] - Q(x_t, phi(gamma_i, zeta_{i+1})) with kernel weights. The proof conditions on gamma_i = gamma_i for all i in [N] and then claims that the D_i are independent because zeta_2, ..., zeta_{N+1} are i.i.d. But conditioning on the whole trajectory gamma_1, ..., gamma_N fixes gamma_2, ..., gamma_N, and hence, through gamma_{i+1} = phi(gamma_i, zeta_{i+1}), it fixes zeta_{i+1} for i < N; only zeta_{N+1} remains random. The conditioned expression is therefore an affine function of one random variable plus the deterministic offset sum_{i<N} w_i (E_{gamma_i}[Q] - Q(gamma_i, gamma_{i+1})), not a sum of N independent centered random variables. Consequently, Bernstein's inequality cannot be applied as in Eqs. (27)-(29). Since Corollary 1, Proposition 2, Theorem 2, Corollary 2, and Theorem 1 all invoke Proposition 1, the polynomial sample complexity claim is not supported by the submitted proof.","section":"Section 3, Proposition 1, Eqs. (21)-(23) and (35)"},{"comment":"The proof uses the estimate integral_{Xi_h(gamma)} f(xi | gamma') dxi >= C_p h^p f for every gamma' in Xi, where Xi_h(gamma) = Xi cap B(gamma, h). A uniform lower bound on the transition density f(xi | gamma) over the bounded set Xi does not imply this estimate: for states gamma near the boundary of Xi, the intersection Xi cap B(gamma, h) can have volume much smaller than C_p h^p. The same issue affects the exponential moment bound in Eq. (35). The paper would need an additional assumption, for example a uniform lower bound on the transition mass into every h-ball or a restriction that gamma is bounded away from the boundary of Xi. As written, Proposition 1 fails even setting aside the independence problem in Eqs. (25)-(29).","section":"Section 3, Assumption A3, Eqs. (21)-(23), (35)"},{"comment":"The numerical experiments do not operate under the assumptions of Theorem 1. The LQG specification uses additive Gaussian noise, so the state process has unbounded support and violates the bounded-support and uniform lower-density conditions in Assumption A3, and the quadratic cost is not scaled to lie in [0,1] as required by Assumption A2. No truncation or rescaling is reported. The favorable numerical comparison with SAA therefore cannot be used as evidence for the theoretical sample-complexity claim, and the experiments do not test the theorem's hypotheses.","section":"Section 4, Eqs. (55)-(56), Figure 2"}],"minor_comments":[{"comment":"Theorem 1 states 'with high probability' without specifying the failure probability; it should state explicitly that for every delta in (0,1], the claimed bound holds with probability at least 1-delta when N is at least the stated order.","section":"Theorem 1"},{"comment":"The same symbol f is used for the transition density and for its lower bound in the statement '0 < f <= f(xi | gamma)'. This is confusing and should be disambiguated, for example by writing f_lower for the lower bound.","section":"Assumption A3"},{"comment":"The x-axis of Figure 2 is labeled as the number of nodes in the scenario tree, but MRST and SAA consume data in different ways: MRST uses only two trajectories of length N+1, while the SAA tree size is not the same as a data sample count. The comparison would be clearer if the paper reported the actual number of historical observations used by each method.","section":"Figure 2 and Section 4"}],"recommendation":"reject","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The MRST construction is genuinely clever, and the paper asks the right question. The idea of alternating two historical trajectories to build a recombining tree, then estimating conditional expectations with kernel weights, is a fresh way to get an implementable policy without knowing the transition. The claimed rate eO(T^{p+3} ε^{-p-2}) would be a real answer to a known open problem, and the paper is honest about what prior SAA bounds give.\n\nThe problem is Proposition 1. In Eq. (25), after conditioning on the first N states of the trajectory, all but the last term in the deviation sum are deterministic. The ζ's that drive \\tildeγ_{i+1} are fixed for i=1..N-1 by the conditioning; only the i=N term retains randomness. So the sum is a deterministic offset plus one random variable, not a sum of N independent centered variables. Bernstein cannot be applied the way they do. Since Corollary 1, Proposition 2, Theorem 2, and Corollary 2 all invoke Proposition 1, the polynomial sample complexity in Theorem 1 does not follow from the proof. This looks repairable with a martingale/Freedman inequality — Markov dependence is exactly where a direct Bernstein application needs care — but the repair is absent.\n\nThe other soft spots are smaller. Assumption A3 (density bounded below on bounded support) is violated by the Gaussian LQG experiments unless the noise is truncated, and boundary effects near the support edge are hand-waved. The numerical section does not report the matrices or parameter values, so it is not reproducible even as a stylized study.\n\nWho this is for: anyone working on data-driven multistage stochastic programming or SDDP would be interested in the MRST scheme itself, and the paper frames the gap with SAA well. A serious referee could help fix the proof. This is the kind of paper that deserves referee time despite the flaw, because the idea is novel and the claimed result is important.\n\nRecommendation: send it to peer review, but tell the authors the current Proposition 1 proof does not establish Theorem 1. My guess is the result can be salvaged, but not without a real martingale argument.","headline":"Clever and important idea, but the polynomial-in-T sample-complexity claim is not proven — the Bernstein step in Proposition 1 collapses under conditioning.","tokens_in":25314,"tokens_out":4324,"would_cite":false,"duration_ms":38569,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C15","90C39"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims a polynomial sample bound for multistage stochastic programs under Markovian uncertainty, replacing SAA's exponential dependence on the horizon.","keywords":["multistage stochastic programming","sample complexity","Markovian uncertainty","Markov recombining scenario tree","sample average approximation","kernel estimator","curse of dimensionality"],"falsifier":"Take a Markov process that satisfies all assumptions except the uniform lower bound on the transition density, for example a transition density that vanishes as the state approaches the boundary of the bounded support, and measure the probability that the kernel estimator finds no neighbor within bandwidth $h$ as $N$ grows; if that probability does not decay exponentially in $N$, the claimed sample complexity fails. Equivalently, simulate Proposition 1 with a truncated Gaussian transition and check directly whether the bias term exceeds $M_{t+1}h+\\epsilon$ at the documented rate.","tokens_in":24249,"feed_emoji":"🎲","tokens_out":7594,"duration_ms":64126,"temperature":0.7,"pith_summary":"This paper proposes the Markov Recombining Scenario Tree (MRST), an approximation to a multistage stochastic program whose random data follow a continuous-state Markov process with an unknown transition distribution. The method needs only two independent historical trajectories: it alternates between them across stages and estimates each conditional expectation with a kernel-weighted average over nearby observed states. The central claim is a non-asymptotic suboptimality bound: with $N \\geq \\widetilde{O}(T^{p+3}\\epsilon^{-p-2})$ samples, the first-stage cost of the MRST solution is within $\\epsilon$ of the true optimal value with high probability. Because this bound is polynomial in the horizon $T$, the method is claimed to break the curse of dimensionality that makes sample average approximation need $\\widetilde{O}(T^{T}\\epsilon^{-2T})$ samples. A sympathetic reader should care because this is a provable polynomial-in-$T$ guarantee for data-driven multistage decisions under Markovian noise.","feed_headline":"Two trajectories beat the exponential tree in multistage planning","feed_subtitle":"The MRST method needs only polynomially many samples in the horizon, unlike SAA's exponential tree.","key_machinery":"The load-bearing object is the Markov Recombining Scenario Tree: a tree assembled from two independent trajectories $\\gamma^{(a)}_{[1:N+1]}$ and $\\gamma^{(b)}_{[1:N+1]}$, using nodes from the first trajectory at odd stages and from the second at even stages. Conditional expectations are replaced by kernel estimators $\\widehat{\\mathbb{E}}_{\\xi_t}[\\cdot] = \\sum_i Q_{t+1}(x_t,\\gamma^{(a)}_{i+1}) K_h(\\xi_t-\\gamma^{(a)}_i)/\\sum_j K_h(\\xi_t-\\gamma^{(a)}_j)$ (and the analogous formula with $\\gamma^{(b)}$), with a bounded-support kernel $K_h$. The proof's key move is to represent the Markov process as $\\tilde{\\xi}_{t+1}=\\phi(\\tilde{\\xi}_t,\\tilde{\\zeta}_{t+1})$ with i.i.d. uniforms $\\tilde{\\zeta}_t$, so that, conditional on the observed trajectory, the sum inside the estimator is a sum of independent random variables and Bernstein's inequality applies. This converts the non-i.i.d. Markov dependence into a tractable concentration problem, and the recursion in the probability of an empty neighborhood uses the uniform lower bound $f$ on the transition density.","core_discovery":"On its own terms, the paper establishes Theorem 1: for any fixed $\\epsilon \\in [0,1]$, the optimal first-stage decision of the MRST problem satisfies $c_1(x_1^*,\\xi_1)+\\mathbb{E}_{\\xi_1}[Q_2(x_1^*,\\tilde{\\xi}_2)] \\leq c_1(\\hat{x}_1,\\xi_1)+\\mathbb{E}_{\\xi_1}[Q_2(\\hat{x}_1,\\tilde{\\xi}_2)]+\\epsilon$ with high probability once $N \\geq \\widetilde{O}(T^{p+3}\\epsilon^{-p-2})$. The argument proceeds by bounding the error of the kernel estimator for a single conditional expectation (Proposition 1), extending the bound uniformly over the feasible set with an $\\eta$-net (Proposition 2), and then propagating the errors backward through the dynamic program (Theorem 2). The final suboptimality bound scales like $\\widetilde{O}(T^{(p+3)/(p+2)} N^{-1/(p+2)})$, which is what yields the polynomial sample complexity in $T$.","pith_inferences":["If the bound holds, MRST-style recombining trees could become a default fallback for data-limited multistage optimization, for instance by feeding MRST stage problems into SDDP-type solvers.","The uniform lower bound on the transition density is probably not satisfied by the Gaussian noise used in the LQG experiments unless truncated; testing on a state-dependent or unbounded transition law would reveal how far the guarantee extends beyond Assumption A3.","A natural next question is whether the polynomial-in-$T$ rate can be improved by using more than two trajectories or by replacing the kernel step with a regression estimator, since the $p$-dependence looks like a smoothing cost rather than an inherent horizon curse.","The alternating-trajectory construction implicitly exploits stationarity of the Markov chain; re-proving the bound under mixing coefficients instead of a uniform density lower bound would connect these guarantees to a wider class of dependent data."],"forward_implications":["For fixed accuracy $\\epsilon$, the sample count grows polynomially with horizon $T$ (power $p+3$), so the method remains tractable for long planning horizons where SAA does not.","The MRST value functions are defined on observed states, and the same kernel estimator extends the policy to unseen data, so the output is an implementable decision rule rather than a tree-dependent policy.","The suboptimality bound degrades only polynomially in the state dimension $p$, and the bandwidth formula $h^\\star$ derived from the bound gives an explicit tuning recipe.","Under the paper's regularity assumptions, two trajectories suffice for a non-asymptotic guarantee, so the method applies where history data is scarce."],"supporting_citations":[{"why":"Supplies the SAA suboptimality rate $\\widetilde{O}(T^{1/2}N^{-1/(2T)})$ and the exponential sample complexity that MRST is compared against.","marker":"[21]"},{"why":"Gives the $\\eta$-net cardinality $O(1)(D/\\eta)^d$ used to make the generalization bound uniform over feasible decisions.","marker":"[24]"},{"why":"Establishes the SAA suboptimality framework for stochastic discrete optimization that motivates the sample-complexity comparison.","marker":"[11]"},{"why":"Provides the feedback representation $\\tilde{\\xi}_{t+1}=\\phi(\\tilde{\\xi}_t,\\tilde{\\zeta}_{t+1})$ of a Markov process, the step that turns dependent samples into independent ones conditionally.","marker":"[10]"},{"why":"Supplies the bounded-support kernel examples (uniform, Epanechnikov) used in the estimator and the bandwidth discussion.","marker":"[27]"},{"why":"Is the source of the Bernstein inequality used to control the deviation of the kernel estimator.","marker":"[28]"},{"why":"Defines the conditional Monte Carlo scenario-tree construction of SAA that MRST is meant to replace.","marker":"[23]"},{"why":"Provides Stirling's approximation used to simplify the optimal bandwidth formula and close the sample-complexity expression.","marker":"[19]"}],"fun_headline_variants":["Polynomial samples break the horizon curse","Two history paths beat SAA's exponential tree","MRST tames time horizon with polynomial samples","Data-driven multistage: from exponential to polynomial","Surpassing SAA: two trajectories, polynomial complexity"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The transition density must stay bounded below by a positive constant everywhere on a bounded support, so every state has a nontrivial chance of producing a neighbor within the kernel bandwidth; if the density has thin regions or unbounded support, the kernel estimate can return zero and the error bound collapses.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial samples break the horizon curse","Two history paths beat SAA's exponential tree","MRST tames time horizon with polynomial samples","Data-driven multistage: from exponential to polynomial","Surpassing SAA: two trajectories, polynomial complexity"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000622,"raw_usage":{"total_tokens":2877,"prompt_tokens":935,"completion_tokens":1942,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":551,"completion_tokens_details":{"reasoning_tokens":1870}},"tokens_in":551,"tokens_out":1942,"duration_ms":14074,"temperature":1.0,"reasoning_tokens":1870,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T00:46:07.105961+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a Markov process that satisfies all assumptions except the uniform lower bound on the transition density, for example a transition density that vanishes as the state approaches the boundary of the bounded support, and measure the probability that the kernel estimator finds no neighbor within bandwidth $h$ as $N$ grows; if that probability does not decay exponentially in $N$, the claimed sample complexity fails. Equivalently, simulate Proposition 1 with a truncated Gaussian transition and check directly whether the bias term exceeds $M_{t+1}h+\\epsilon$ at the documented rate.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the SAA suboptimality rate $\\widetilde{O}(T^{1/2}N^{-1/(2T)})$ and the exponential sample complexity that MRST is compared against."},{"cited_title":"and Nemirovski, A","cited_arxiv_id":null,"evidence_quote":"Gives the $\\eta$-net cardinality $O(1)(D/\\eta)^d$ used to make the generalization bound uniform over feasible decisions."},{"cited_title":"J., Shapiro, A., and Homem-de Mello, T","cited_arxiv_id":null,"evidence_quote":"Establishes the SAA suboptimality framework for stochastic discrete optimization that motivates the sample-complexity comparison."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the feedback representation $\\tilde{\\xi}_{t+1}=\\phi(\\tilde{\\xi}_t,\\tilde{\\zeta}_{t+1})$ of a Markov process, the step that turns dependent samples into independent ones conditionally."},{"cited_title":"and Wasserman, L","cited_arxiv_id":null,"evidence_quote":"Supplies the bounded-support kernel examples (uniform, Epanechnikov) used in the estimator and the bandwidth discussion."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the conditional Monte Carlo scenario-tree construction of SAA that MRST is meant to replace."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides Stirling's approximation used to simplify the optimal bandwidth formula and close the sample-complexity expression."}],"review_version":1}