On Convergence Rate of Adaptive Multiscale Value Function Approximation For Reinforcement Learning

Quanyan Zhu; Tao Li

REVIEW 2 major objections 5 minor 16 references

On Convergence Rate of Adaptive Multiscale Value Function Approximation For Reinforcement Learning

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Adaptive tree-based wavelet bases approximate value functions at rate $N^{-s/d}$, independent of basis regularity.

desk verdict 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. read the letter →

arxiv 1908.08578 v1 pith:YCUQS4KI submitted 2019-08-22 cs.LG stat.ML

Tao Li , Quanyan Zhu This is my paper · ORCID

classification cs.LGstat.ML MSC 41A4642C4065T60

keywords adaptivemultiscaleapproximationmultiresolutionanalysistreewaveletsn-termBesovspacesvaluefunctionreinforcementlearning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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<q<\infty$ and $s=(2-\lambda)d/(2\lambda)$, the approximation $S(f,\eta)$ that keeps the smallest proper subtree of dyadic cubes whose wavelet blocks have norm at least $\eta$ satisfies $\|f-S(f,\eta)\|\le C |f|_{B_s^q} N^{-s/d}$, where $N=\#T(f,\eta)$. The proof embeds Besov spaces into a tree-size class $B_\lambda(L_2(S))$ where $\#T(f,\eta)\le C\eta^{-\lambda}$, then bounds the leftover by summing level errors; the exponent $N^{-s/d}$ is exactly the $n$-term approximation rate for Besov functions. The paper's key remark is that nothing in the argument uses smoothness of the scaling or wavelet function, only refinability and orthonormality, so the rate is a property of the value function, not of the chosen basis.

Load-bearing premise

The convergence-rate proof assumes the wavelet coefficients are known exactly when the tree is built, but Algorithm 1 estimates them from sampled rewards; the paper does not prove the estimates produce the same tree or preserve the rate.

Editorial extensions

If this is right

Adaptive multiscale value function approximation converges with error $O(N^{-s/d})$ when the value function has Besov smoothness $s$, so the approximation error is governed by the value function's own structure.
The asymptotic rate is independent of the regularity of the basis functions, so the simplest refinable basis, Haar wavelets, is asymptotically as good as smoother wavelet systems.
Adaptive tile coding, which uses a piecewise-constant basis, is a special case of the proposed framework and inherits the same convergence rate.
Refining only where wavelet coefficients are large gives a principled alternative to uniform-resolution discretization, with a rate guarantee to justify the adaptivity.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The theorem is proven for the ideal approximation built from exact coefficients; the paper does not show that the coefficients estimated by TD($\lambda$) in Algorithm 1 produce the same tree. Closing that gap would turn the rate into an end-to-end guarantee for the learning algorithm.
Because $N^{-s/d}$ is the standard $n$-term approximation rate for Besov spaces, the tree scheme is plausibly near-optimal among adaptive linear approximation methods, though the paper does not state an optimality result.
A testable refinement would replace coefficient thresholding with thresholding of local Bellman residuals or value criteria; whether that preserves the rate is open.
For MDPs with smooth transition and reward kernels, the value function's Besov smoothness can be estimated empirically, which would let a practitioner predict the achievable error from a measured smoothness exponent.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

What 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.

The 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.

There 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.

The 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.

I 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.

Referee Report

2 major / 5 minor

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.

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 (2)

[Section 3.2 vs. Section 3.3, Theorems 1 and 2] 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 2.3 and Theorem 2, Eq. (4)] 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.

minor comments (5)

[Theorem 2 proof, after Eq. (6)] 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.
[Algorithm 1, line 17] 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 2.3, Eq. (4)] 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 4, Figure 1] 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.
[General] There are several typos and presentation issues: 'reﬁnale' in Definition 1, 'Ne York University' in the author affiliation, 'Arcobot' in Section 4, and 'speical' in Section 5.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the rate claims are derived from external tree-approximation results, not from the target conclusion; the paper's serious issues are correctness gaps, not circular reasoning.

full rationale

The derivation chain is not circular. Theorem 1's rate for the tree approximation S(f,eta) is proved from Temlyakov's Lemma 1 (an external cited result) and the definition of the class B_lambda; the class is defined by the number of tree terms, and the error bound is an implication, not an assumption of the conclusion. Theorem 2 connects B_s^q(L2) to B_lambda through the wavelet-coefficient characterization in Eq. (4), which is an external characterization, not a restatement of the convergence claim. The only self-citation is [9] (Han, Li, Zhuang), cited merely as an example of more complicated orthogonal wavelets; it is not load-bearing. The experimental section fits no constants used in the theorems. Two substantive gaps exist but are not circularity: (i) Eq. (4) is applied to the Haar basis used in GMSA, for which the Besov characterization fails for s >= 1/2, so Theorem 2's conclusion is not justified for s > 1/2; (ii) Algorithm 1's coefficients are obtained by TD(lambda) updates and refinement by 'value criterion' and 'lowest Bellman error,' yet Theorem 2 assumes exact coefficients A_I(f) when forming T(f,eta) and S(f,eta) (Section 3.3). These are missing hypotheses or incorrect assumptions, not self-referential derivations. The paper does not rename a fitted parameter as a prediction, import a uniqueness theorem from the authors' prior work, or smuggle an ansatz via citation. Therefore the circularity score is minimal.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

The central theorem itself has no fitted parameters: the rate follows from standard nonlinear approximation theory. The hand-chosen experimental hyperparameters (eta, alpha, p, gamma) do not enter the convergence proof. The load-bearing axioms are the smoothness/sparsity of the value function and the unproven assumption that TD-estimated coefficients can be used in place of exact coefficients when constructing the adaptive tree.

free parameters (4)

Tolerance eta = 0.001
Threshold for stopping refinement in Algorithm 1 and numerical experiments (Section 4); chosen by hand, not fitted.
TD learning rate alpha = 0.001
Step size used in Cartpole/Acrobot runs (Section 4); chosen by hand, independent of the theorem.
Patience p = 50
Number of consecutive low-error steps before basis refinement (Algorithm 1, Section 4); chosen by hand.
Discount factor gamma = 0.8
Discount for the experimental tasks (Section 4); chosen by hand.

assumptions (6)

domain assumption The state space is a bounded set, taken as [0,1]^d, and the value function lies in L2(S).
Section 2.1 and Section 3 set S as a unit cube; the L2 wavelet machinery requires this.
domain assumption The value function f belongs to B_lambda(L2(S)) with lambda in (0,2), or equivalently to a Besov space B_s^q(L2(S)).
Definition 5 and Theorem 1; the claimed rate O(N^{-s/d}) exists only for functions in this sparsity/smoothness class.
standard math An orthonormal wavelet basis generated by refinable functions exists on the state space; Haar wavelets are used.
Section 2.3 invokes standard multiresolution analysis; existence is a classical result.
standard math Temlyakov's Lemma 1 (Eq. (2)) and the tree approximation results of Cohen et al. hold as quoted.
Theorem 1's proof applies these external results without modification; they are accepted as given.
standard math TD(lambda) with linear function approximation converges to the fixed point for a fixed basis.
Section 2.2 cites [2,3]; used to justify weight updates, but not extended to the adaptive case.
ad hoc to paper The wavelet coefficients used for thresholding in the convergence proof are the true coefficients A_I(f).
Algorithm 1 actually uses coefficients estimated during TD learning; no error bound connects the estimates to the true coefficients, so this is an unstated assumption for the RL claim.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Convergence Rate of Adaptive Multiscale Value Function Approximation For Reinforcement Learning." pith.science (2026). https://pith.science/paper/YCUQS4KI

@misc{pith2026190808578,
  author       = {Pith},
  title        = {Pith review of: On Convergence Rate of Adaptive Multiscale Value Function Approximation For Reinforcement Learning},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/YCUQS4KI}},
  note         = {Machine review of arXiv:1908.08578}
}

read the original abstract

In this paper, we propose a generic framework for devising an adaptive approximation scheme for value function approximation in reinforcement learning, which introduces multiscale approximation. The two basic ingredients are multiresolution analysis as well as tree approximation. Starting from simple refinable functions, multiresolution analysis enables us to construct a wavelet system from which the basis functions are selected adaptively, resulting in a tree structure. Furthermore, we present the convergence rate of our multiscale approximation which does not depend on the regularity of basis functions.

Figures

Figures reproduced from arXiv: 1908.08578 by the authors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages

[1]

R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction, MIT press, 2018

work page 2018
[2]

Analysis of temporal-diffference learning with function approximation,

J. N. Tsitsiklis and B. Van Roy, “Analysis of temporal-diffference learning with function approximation,” in Advances in neural information processing systems, 1997, pp. 1075–1081

work page 1997
[3]

Learning to predict by the methods of temporal differences,

R. S. Sutton, “Learning to predict by the methods of temporal differences,” Machine Learning, vol. 3, no. 1, pp. 9–44, Aug. 1988

work page 1988
[4]

Least-squares policy iteration,

M. G. Lagoudakis and R. Parr, “Least-squares policy iteration,” Journal of machine learning research, vol. 4, pp. 1107–1149, Dec. 2003

work page 2003
[5]

Value function approximation in reinforcement learning using the fourier basis,

G. Konidaris, S. Osentoski, and P. Thomas, “Value function approximation in reinforcement learning using the fourier basis,” in Twenty-ﬁfth AAAI conference on artiﬁcial intelligence, 2011

work page 2011
[6]

Whiteson, Adaptive Representations for Reinforcement Learning, vol

S. Whiteson, Adaptive Representations for Reinforcement Learning, vol. 291 of Studies in Computational Intel- ligence, Springer, Berlin, Germany, 2010. 9 A PREPRINT - AUGUST 26, 2019

work page 2010
[7]

Meyer, Wavelets and operators, vol

Y . Meyer, Wavelets and operators, vol. 1, Cambridge university press, 1995

work page 1995
[8]

Tree approximation and optimal encoding,

A. Cohen, W. Dahmen, I. Daubechies, and R. DeV ore, “Tree approximation and optimal encoding,”Applied and Computational Harmonic Analysis, vol. 11, no. 2, pp. 192 – 226, 2001

work page 2001

Show all 16 references

[9]

Directional compactly supported box spline tight framelets with simple geometric structure,

B. Han, T. Li, and X. Zhuang, “Directional compactly supported box spline tight framelets with simple geometric structure,” Applied Mathematics Letters, vol. 91, pp. 213–219, 2019

2019
[10]

The best m-term approximation and greedy algorithms,

V . N. Temlyakov, “The best m-term approximation and greedy algorithms,”Advances in Computational Mathe- matics, vol. 8, no. 3, pp. 249–265, 1998

1998
[11]

Nonlinear approximation,

R. A. DeV ore, “Nonlinear approximation,” Acta numerica, vol. 7, pp. 51–150, 1998

1998
[12]

Convergence rates of multiscale and wavelet expansions,

M. A. Kon and L. A. Raphael, “Convergence rates of multiscale and wavelet expansions,” inWavelet Transforms and Time-Frequency Signal Analysis, pp. 37–65. Springer, 2001

2001
[13]

Han, Framelets and wavelets: algorithms, analysis, and applications, Birkh ¨auser Basel, 2018

B. Han, Framelets and wavelets: algorithms, analysis, and applications, Birkh ¨auser Basel, 2018

2018
[14]

Neuronlike adaptive elements that can solve difﬁcult learning control problems,

A. G. Barto, R. S. Sutton, and C. W. Anderson, “Neuronlike adaptive elements that can solve difﬁcult learning control problems,” IEEE Transactions on Systems, Man, and Cybernetics , vol. SMC-13, no. 5, pp. 834–846, Sep. 1983

1983
[15]

Generalization in reinforcement learning: Successful examples using sparse coarse coding,

R. S. Sutton, “Generalization in reinforcement learning: Successful examples using sparse coarse coding,” in Advances in neural information processing systems, 1996, pp. 1038–1044

1996
[16]

Variable resolution discretization in optimal control,

R. Munos and A. Moore, “Variable resolution discretization in optimal control,” Machine learning, vol. 49, no. 2-3, pp. 291–323, 2002. 10

2002

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

R. S. Sutton and A. G. Barto, Reinforcement learning: An introduction, MIT press, 2018

work page 2018

[2] [2]

Analysis of temporal-diffference learning with function approximation,

J. N. Tsitsiklis and B. Van Roy, “Analysis of temporal-diffference learning with function approximation,” in Advances in neural information processing systems, 1997, pp. 1075–1081

work page 1997

[3] [3]

Learning to predict by the methods of temporal differences,

R. S. Sutton, “Learning to predict by the methods of temporal differences,” Machine Learning, vol. 3, no. 1, pp. 9–44, Aug. 1988

work page 1988

[4] [4]

Least-squares policy iteration,

M. G. Lagoudakis and R. Parr, “Least-squares policy iteration,” Journal of machine learning research, vol. 4, pp. 1107–1149, Dec. 2003

work page 2003

[5] [5]

Value function approximation in reinforcement learning using the fourier basis,

G. Konidaris, S. Osentoski, and P. Thomas, “Value function approximation in reinforcement learning using the fourier basis,” in Twenty-ﬁfth AAAI conference on artiﬁcial intelligence, 2011

work page 2011

[6] [6]

Whiteson, Adaptive Representations for Reinforcement Learning, vol

S. Whiteson, Adaptive Representations for Reinforcement Learning, vol. 291 of Studies in Computational Intel- ligence, Springer, Berlin, Germany, 2010. 9 A PREPRINT - AUGUST 26, 2019

work page 2010

[7] [7]

Meyer, Wavelets and operators, vol

Y . Meyer, Wavelets and operators, vol. 1, Cambridge university press, 1995

work page 1995

[8] [8]

Tree approximation and optimal encoding,

A. Cohen, W. Dahmen, I. Daubechies, and R. DeV ore, “Tree approximation and optimal encoding,”Applied and Computational Harmonic Analysis, vol. 11, no. 2, pp. 192 – 226, 2001

work page 2001