{"id":"6a18fd63-81b9-47c4-b186-43da8436df92","arxiv_id":"1908.08578","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":3.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Adaptive multiscale value function approximation via tree-structured wavelets is shown to have an O(N^{-s/d}) approximation rate, but the result mostly restates known nonlinear approximation theory and does not cover the TD learning process.","lead":"This paper reworks a known wavelet tree approximation method into a framework for value function approximation in reinforcement learning, and states an approximation rate that depends on the smoothness of the value function rather than the smoothness of the basis. The result is mathematically sound in the narrow setting of approximating a known function, but the paper does not prove that its learning algorithm achieves this rate.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The central rate theorem is not valid for the Haar basis used in Algorithm 1: Eq. (4)'s Besov characterization fails for s≥1/2, and for f(x)=x² the Haar tree rate is N^{-1}, not the claimed N^{-2}.","rationale":"The reader's identified gap — that Theorem 2 assumes exact wavelet coefficients while Algorithm 1 uses TD estimates — is real and would already justify REJECT. However, the more fundamental problem is that the approximation theorem itself is not valid for the basis actually used in the paper. Section 2.3 explicitly restricts the GMSA implementation to Haar wavelets, and Theorem 2's proof uses Eq. (4) as a Besov norm in terms of wavelet coefficients. Haar wavelets do not characterize B_s^q(L2) for s ≥ 1/2, and the concrete example f(x)=x² shows the claimed N^{-2} rate cannot hold for the Haar-based tree approximation; the actual rate is N^{-1}. This means the paper's central mathematical claim, not just its RL implementation bridge, is overbroad. The theorem could perhaps be repaired by restricting to basis-compatible smoothness ranges or by switching to sufficiently smooth wavelets, but that would also undercut the 'basis regularity does not matter' narrative. Because this strengthens rather than weakens the case for REJECT, the reader's verdict remains unchanged, but the load-bearing concern is shifted from the algorithm-to-theory bridge to the validity of Eq. (6) itself for the implemented basis.","tokens_in":34,"tokens_out":24151,"duration_ms":514684,"concrete_test":"Derive the exact Haar tree approximation of f(x)=x² on [0,1]: compute A_I(f), count N = #T(f,η), and evaluate ||f − S(f,η)|| as η→0. Eq. (6) with s=2 predicts error = O(N^{-2}); the direct Haar-coefficient calculation gives level energy Σ_{I∈D_j} ||A_I(f)||² ≈ 2^{-2j}, N ≈ 2^J, and tail error ≈ 2^{-J} = N^{-1}, so the rate is N^{-1}, not N^{-2}. Repeating this check with a spline wavelet of regularity 2 should yield N^{-2}, confirming that basis regularity enters the achievable rate.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central assertion fails already in the exact-coefficient setting, before any TD-estimation gap. Section 2.3 fixes Haar as the GMSA basis, and Theorem 2's proof relies on Eq. (4) as the Besov quasi-norm |f|_{B_s^q(L2)} = (Σ_j 2^{jsq}(Σ_{I∈D_j} ||A_I(f)||²)^{q/2})^{1/q}. This is a characterization of Besov spaces only for wavelets with sufficient regularity and vanishing moments; for the Haar system it fails for s ≥ 1/2 when p=2. A concrete witness is f(x)=x² on [0,1], which lies in H² = B₂²(L2). Its Haar detail energy satisfies Σ_{I∈D_j} ||A_I(f)||² ≈ 2^{-2j}; inserting this into Eq. (4) with s=2, q=2 gives level contributions 2^{2jq}(2^{-2j})^{q/2} = 2^{jq}, which diverge. Correspondingly, the Haar tree approximation of x² has error ≈ N^{-1}, not N^{-2}: keeping all levels up to J costs N ≈ 2^J terms and leaves orthogonal tail energy (Σ_{j>J} 2^{-2j})^{1/2} ≈ 2^{-J} = N^{-1}. Thus Eq. (6), as applied to the Haar-based GMSA, is not correct for standard Besov functions with s > 1, and the advertised conclusion that the convergence rate does not depend on the regularity of basis functions is not a theorem: the basis regularity and vanishing moments determine the range of Besov smoothness s for which Eq. (4), and hence the rate, is available.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a framework called generalized multiscale approximation (GMSA) for linear value function approximation in reinforcement learning. It combines multiresolution analysis with tree approximation: starting from a refinable function (Haar in the implementation), wavelet basis functions are selected adaptively according to a coefficient-thresholding rule, producing a tree-structured basis. The authors state convergence-rate results: Theorem 1 bounds the L2 error of a tree-based wavelet approximation in terms of a cardinality-based quasi-norm, and Theorem 2 claims that for functions in a Besov space B_s^q(L2), the approximation error is O(N^{-s/d}) with N the number of retained tree nodes, with the rate stated to be independent of the regularity of the basis functions. Algorithm 1 computes the approximation online using TD(lambda) and refines the basis according to a heuristic 'value criterion.' Numerical experiments on Cartpole and Acrobot compare GMSA with adaptive tile coding and fixed tile coding.","tokens_in":10824,"tokens_out":11613,"duration_ms":124199,"significance":"If the stated rate were established for the actual RL algorithm, the contribution would be significant: it would provide a principled convergence-rate guarantee for adaptive discretization methods in value function approximation and would unify several adaptive representation schemes under one framework. The mathematical skeleton of Theorem 1 is coherent in the idealized exact-coefficient setting, and the paper correctly identifies tree approximation and Besov regularity as the relevant tools. However, the advertised result currently has two load-bearing gaps: the proof never connects the TD-estimated coefficients and the refinement heuristic of Algorithm 1 to the exact tree T(f,eta) used in the theorems, and the Besov coefficient characterization underlying Theorem 2 is not valid for the Haar basis at the claimed smoothness range. The paper is therefore best viewed as an interesting proposal with a partially valid approximation-theoretic core, not as an established convergence-rate theorem.","major_comments":[{"comment":"The convergence analysis is carried out entirely in the exact-coefficient setting: T(f,eta) is defined from the true wavelet coefficients A_I(f), and S(f,eta) uses those exact coefficients. Algorithm 1, in contrast, obtains coefficients through TD(lambda) updates on the currently selected basis and decides refinement using the 'value criterion' and 'lowest Bellman error,' which are not defined mathematically in the paper. No lemma or theorem bounds the distance between the tree produced by Algorithm 1 and T(f,eta), nor the estimation error of the TD coefficients. Consequently, Eqs. (3) and (6) do not imply any convergence rate for the algorithm that is actually proposed; the central claim of the paper is not established.","section":"Section 3.2 vs. Section 3.3, Theorems 1 and 2"},{"comment":"Equation (4) treats the expression (sum_j 2^{jsq} (sum_{I in D_j} ||A_I(f)||^2)^{q/2})^{1/q} as the Besov quasi-norm. This characterization is valid only for wavelets with sufficient regularity and vanishing moments; for the Haar system used throughout the paper it fails for s >= 1/2 when p=2. A concrete witness is f(x)=x^2 on [0,1], which lies in H^2 = B_{2,2}^2 but whose Haar detail coefficients satisfy sum_{I in D_j} ||A_I(f)||^2 ~ 2^{-4j}, making the s=2 term in Eq. (4) of order 1 for every j and hence divergent. Thus Theorem 2 cannot be applied to standard Besov spaces with s >= 1/2, and the paper's advertised conclusion that the convergence rate does not depend on the regularity of basis functions is not a theorem as stated. The discussion in Section 5 extending the result to piecewise-constant ATC inherits the same problem.","section":"Section 2.3 and Theorem 2, Eq. (4)"}],"minor_comments":[{"comment":"The assertion that for I in T_j(f,eta)\\Lambda_j(f,eta) 'its sibling must be in Lambda_j(f,eta)' is false: a parent with ||A_P(f)|| >= eta contributes all its children to the tree, and both children can have coefficients below eta. The count should be bounded as #T_j <= #Lambda_j + 2^d #Lambda_{j-1}. The conclusion survives up to a constant, but the argument as written is incorrect.","section":"Theorem 2 proof, after Eq. (6)"},{"comment":"The line 'V <- V - theta_j^T phi_j' is unclear: V denotes the value function and theta_j^T phi_j is a scalar, so the displayed update is not well defined. Please specify how the piecewise approximation is assembled from the refined basis.","section":"Algorithm 1, line 17"},{"comment":"The conditions under which Eq. (4) characterizes a Besov space should be stated explicitly, including the required smoothness and vanishing moments of the wavelet, rather than only citing [12,13,11].","section":"Section 2.3, Eq. (4)"},{"comment":"The numerical comparison reports single learning curves without error bars, repeated runs, or statistical tests, so the claim that GMSA outperforms ATC and fixed tile coding is not quantitatively supported.","section":"Section 4, Figure 1"},{"comment":"There are several typos and presentation issues: 'refinale' in Definition 1, 'Ne York University' in the author affiliation, 'Arcobot' in Section 4, and 'speical' in Section 5.","section":"General"}],"recommendation":"reject","confidential_remarks":"The paper's central theoretical claim is not supported by the arguments given: the analysis never bridges the TD-based adaptive selection in Algorithm 1 to the exact tree approximation analyzed in Theorems 1 and 2, and the Haar-based Besov characterization in Eq. (4) is invalid for standard Besov spaces with s >= 1/2. These are not local presentation issues; repairing them would require either a full stochastic-approximation analysis of adaptive basis selection or a switch to smoother wavelets with a corresponding revision of the main claims. The numerical evidence is also not strong enough to compensate for the theoretical gaps."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the paper applies known tree-approximation results to value function approximation and correctly observes that adaptive tile coding is a special case. The main theorem, however, overreaches: the advertised rate that is independent of basis regularity is not true for the Haar basis used in the algorithm, and the proof never connects the TD-learned coefficients to the exact coefficient tree used in the theorems.\n\nWhat is genuinely useful here is the framing: GMSA ties multiresolution analysis and tree approximation together, and showing ATC as a special case is a nice observation. Theorem 1 is a clean consequence of Temlyakov's lemma and is fine. For wavelets with sufficient regularity and vanishing moments, the embedding in Theorem 2 is standard and the rate estimate is correct. The references are appropriate.\n\nThe load-bearing problem is that Section 2.3 fixes Haar as the basis, but Eq. (4) is not a valid Besov characterization for Haar once s >= 1/2. A concrete witness: f(x)=x^2 on [0,1] is in H^2, but its Haar detail energy per level behaves like 2^{-2j}, which makes the right-hand side of Eq. (4) diverge for s=2. The actual Haar tree approximation error for x^2 is about N^{-1}, not N^{-2}. So the claim that the convergence rate does not depend on basis regularity is false as stated; regularity and vanishing moments of the basis determine the range of s for which the rate holds. This is a central flaw, not a technicality.\n\nThere is also a missing link in the RL part. The theorems assume exact wavelet coefficients and the tree T(f, eta). Algorithm 1 refines using TD(lambda) estimates and a 'lowest Bellman error' criterion, and no result bounds the gap between what the algorithm learns and the ideal tree. Even if the approximation theorem were correct, it would not apply to the algorithm as implemented.\n\nThe experiments are illustrative only—no error bars, no code, and the comparison is not deeply tuned. That is a minor issue relative to the above.\n\nI would send this to a referee rather than desk reject: the framework and the approximation-theoretic core deserve scrutiny, and the error is subtle enough that a reviewer could usefully point the authors to the missing hypotheses. But as it stands the abstract's promise is not supported. For me the verdict is reject, with some hope for a revised version that restricts the rate to the valid Besov range and either proves or explicitly drops the TD-estimation claim.","headline":"The central rate claim is not valid for the Haar basis the algorithm actually uses, and the proof never connects the TD-based refinement to the exact-coefficient tree; the framework itself is a competent but standard application of tree approximation.","tokens_in":11317,"tokens_out":7400,"would_cite":false,"duration_ms":70383,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["41A46","42C40","65T60"],"pacs":[],"model":"deepseek-v4-flash","headline":"Adaptive tree-based wavelet bases approximate value functions at rate $N^{-s/d}$, independent of basis regularity.","keywords":["adaptive multiscale approximation","multiresolution analysis","tree approximation","wavelets","n-term approximation","Besov spaces","value function approximation","reinforcement learning"],"falsifier":"On a known target with Besov smoothness $s$, compute all wavelet coefficients exactly, build $T(f,\\eta)$, and plot $\\|f-S(f,\\eta)\\|$ against $N=\\#T(f,\\eta)$ on log-log axes; the theorem predicts slope $-s/d$. A consistently worse slope, or a slope that changes when the Haar basis is replaced by a smoother wavelet basis, would refute the central claim.","tokens_in":10222,"feed_emoji":"🧠","tokens_out":9116,"duration_ms":82749,"temperature":0.7,"pith_summary":"This paper proposes an adaptive, multiscale way to approximate value functions in reinforcement learning: instead of committing to a fixed set of basis functions, it builds a wavelet basis one dyadic cube at a time, refining only where the value function needs resolution. The central theoretical result is a convergence-rate guarantee: if the true value function has Besov smoothness $s$ on a $d$-dimensional state space, the tree-based approximation using $N$ selected wavelet terms has error at most $C |f|_{B_s^q} N^{-s/d}$. The rate does not depend on the regularity of the basis functions, so even the simplest piecewise-constant Haar basis gets the same asymptotic rate as smoother wavelets. This matters because value-based RL typically relies on hand-designed fixed representations; the theorem says a simple adaptive tree can match the intrinsic difficulty of the value function itself.","feed_headline":"Adaptive wavelets approximate value functions at rate $N^{-s/d}$","feed_subtitle":"The guarantee holds for any refinable basis, so simple Haar wavelets suffice asymptotically.","key_machinery":"The carrying object is the proper subtree $T(f,\\eta)$: the smallest rooted dyadic tree containing every cube $I$ whose wavelet coefficient block $A_I(f)$ has $\\|A_I(f)\\|\\ge \\eta$, together with the approximation $S(f,\\eta)=\\sum_{I\\in T(f,\\eta)}A_I(f)$. The contraction mechanism is a norm comparison for sums of wavelet blocks: on any set $\\Lambda$ of dyadic cubes, the $L_2$ norm of $\\sum_{I\\in\\Lambda}A_I(f)$ is bounded below by a constant times $\\min_{I\\in\\Lambda}\\|A_I(f)\\|\\,\\#\\Lambda^{1/2}$. That inequality converts a coefficient threshold into a bound on each scale's leftover, and the Besov embedding in Theorem 2 converts the resulting tree-count bound into the clean $N^{-s/d}$ rate.","core_discovery":"The paper's claim is that thresholded tree-based wavelet approximation is a sound basis for value function approximation with a quantifiable rate. For $f$ in $B_s^q(L_2(S))$ with $0