acceptodds
Under review as a conference paper at ICLR 2027

A Finite-Sample Analysis of Quantile Temporal-Difference Learning

Abstract

Quantile temporal-difference learning (QTD) is an effective method for learning return distributions through quantile approximation, yet its finite-time behavior remains poorly understood. Its update is nonlinear and nonsmooth, and the stability needed for a sharp convergence rate holds only near the target. We establish a global high-probability last-iterate guarantee for synchronous tabular QTD under general positive, nonincreasing step-size sequences and arbitrary initialization in the natural parameter range. For polynomially decaying step sizes with exponent , the last iterate converges to the target at rate in the infinity norm, up to logarithmic and lower-order terms. A suitably tuned harmonic schedule recovers the statistical rate up to logarithmic factors. For the -quantile representation, its -Wasserstein error scales as up to logarithmic factors, matching the leading polynomial dependence on the quantile resolution and sample size of the corresponding model-based estimator. The proof uses a two-stage global-to-local argument. From arbitrary initialization, Bellman contraction and CDF monotonicity first bring the iterate close to the target, after which, a novel variance–drift matching argument sharpens the control of accumulated noise and local contraction reduces the remaining errors, yielding the sharp rate. Simulations verify the predicted polynomial decay and assess the finite-time entrance bound.

Primary area:
reinforcement learning
Keywords:
distributional reinforcement learning, quantile temporal difference learning, sample complexity

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 4.00 over 3 reviews, above 99% of the others.
Reviewer_pCiCOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies finite-sample convergence of quantile temporal-difference learning (QTD) for policy evaluation in a finite Markov decision process. At each iteration, a generative model supplies one transition per state. QTD updates m quantile locations towards the fixed point of the quantile-projected Bellman operator.

The analysis assumes positive, bounded, Lipschitz reward densities, controlled behavior at the reward boundaries, and the absence of certain boundary alignments. The proof has two stages. A global drift argument brings the iterates into a neighborhood of the target from any initialization within the return range. A local analysis then controls contraction, accumulated noise, and the risk of leaving this neighborhood. Relating quantile noise variance to the strength of the local drift gives a sharper bound than treating the noise uniformly.

The results cover constant, polynomial, and harmonic step sizes. A sufficiently large harmonic gain gives a leading error of order sqrt(m/T), up to logarithmic factors, after burn-in. The appendix states the constants and sufficient burn-in requirements. One-state simulations illustrate convergence over time. The bounds concern the projected target; error relative to the full return distribution also includes a separate approximation term.

Critical strengths
  1. Relating noise variance to the restoring drift is the strongest technical contribution. This gives a sharper dependence on the number of quantiles than a uniform noise bound. The argument also allows the dependence caused by sharing the same sampled transition across quantile updates.

  2. The global entrance argument and the local capture argument form a coherent finite-time analysis. They explain how the iterates reach the region where the sharper rate applies and remain there despite sampling noise. The treatment of the random entrance time is explicit. The results give quantitative guarantees for the last iterate, complementing earlier asymptotic convergence and inference results. The appendix provides explicit constants and sufficient burn-in bounds, making the conditions and limitations of the guarantees possible to examine.

Critical weaknesses
  1. The complete sample cost and scope need clarification. The published sufficient burn-in can be large. Under Assumption 1(ii), with fixed MDP constants and the proposed harmonic tuning, Appendix C.7 gives a sufficient burn-in of O~(m13/3)\widetilde O(m^{13/3}). Under Assumption 1(i), a small boundary margin can increase it further. The comparison with the model-based estimator therefore concerns the leading statistical term. The paper acknowledges this distinction, but a single bound on the total number of transitions needed for error ε\varepsilon would make the comparison easier to assess. The harmonic gain also depends on unknown MDP constants.

    The experimental MDP does not satisfy Assumption 2 as written. This assumption applies to every integer mm. For the one-state MDP with uniform rewards and γ=1/2\gamma=1/2, the exact projected fixed point at m=3m=3 is (2/3,1,4/3)(2/3,1,4/3). The first and third coordinates then give boundary alignments at 0 and 1. The resolution m=7m=7 used in the experiments has a positive boundary margin, so this concerns the scope of the assumption rather than a counterexample to the conditional theorem. A result stated for fixed mm would address this issue.

  2. The experiments provide limited quantitative validation of the theory. The harmonic experiment uses a gain outside the sufficient tuning given in the proof. Appendix C.1 provides Charm=8C_{\mathrm{harm}}=8, requiring c≥8/μc\geq8/\mu. Definition (2) implies cM≤1−γc_{\mathcal M}\leq1-\gamma, by considering the upper quantile and a displacement of (1−γ)−1(1-\gamma)^{-1}. For m=7m=7 and γ=1/2\gamma=1/2, the explicit sufficient condition therefore requires c≥896c\geq896, whereas Figure 1(b) uses c=20c=20. The condition may be conservative, and this does not imply that the experimental algorithm should fail. It does mean that the figure illustrates behavior outside the tuning guaranteed by the published proof.

    Using the constants in Appendix E, the entrance bound in Figure 1(c) remains equal to 1 until approximately 419,188 iterations. All reported trajectories have already entered by iteration 25,945, and the simulation horizon is 200,000. The figure is consistent with the bound but does not assess its precision where empirical non-entrance is observed. The capture condition is also far from satisfied in the polynomial experiment: at T=105T=10^5 and δ=0.05\delta=0.05, the formulas give bT≥1.00b_T\geq1.00, while rout/16≤7.45×10−4r_{\mathrm{out}}/16\leq7.45\times10^{-4}. These are sufficient conditions, so their failure does not contradict the observed convergence.

    The numerical settings test only a small part of the theory. The rate experiments use one state, uniform rewards and a fixed number of quantiles. They do not test the dependence on mm, polynomial exponents a≤1/2a\leq1/2, or the local curvature and coupling between states. A few targeted experiments would strengthen the empirical support.

Questions for authors
  1. Please state a sufficient total transition count for error ε\varepsilon relative to the projected target, including burn-in, MDP constants and the boundary margin.

  2. Can the main result be stated for fixed mm, extending the refinement in Appendix C.3 to the local analysis? This would clarify its applicability to the experimental MDP.

  3. Please clarify which experimental settings satisfy the theoretical gain and burn-in conditions. Could you include a case where the probability bound is informative while some trajectories have not yet entered the target neighborhood?

5 comments

We thank the reviewer for the careful and technically detailed assessment. We have expanded the theoretical results and numerical experiments to clarify the total sample complexity, the scope of Assumption 2, and the practical implications of our sufficient conditions.

1. Please state a sufficient total transition count for error ε\varepsilon relative to the projected target, including burn-in, MDP constants and the boundary margin.

We have added Appendix C.8, "Parameter Dependence and Sample Complexity," which provides sufficient total transition counts for both polynomial and harmonic step-size schedules.

For polynomial steps αt=c(t+1)−a\alpha_t=c(t+1)^{-a}, define \rho_\varepsilon=\min\left\\{\frac{r_{\mathrm{out}}}{16},\frac{\mu}{64L_h},\frac{15\varepsilon}{31}\right\\}, and B_p=\max\left\\{1,\frac{\beta c}{c_g},\frac{c}{c_{\mathcal M}(1-\gamma)\rho_\varepsilon^2},\frac{c}{\rho_\varepsilon}\right\\}. Appendix C.8 shows that a sufficient number of iterations is T=\widetilde O\left(\max\left\\{\left(\frac{D_g}{c_gc}+\frac{1}{\mu c}\right)^{1/(1-a)},\frac{1}{c_g^2},\left(\frac{B_p}{a}\right)^{1/a}\right\\}\right). For the harmonic schedule αt=c/(t+t0)\alpha_t=c/(t+t_0) satisfying the gain condition in Corollary 3.3, let B_h=\max\left\\{1,\frac{c}{c_{\mathcal M}(1-\gamma)\varepsilon^2},\frac{c}{\varepsilon}\right\\}. A sufficient total number of transitions is |\mathcal S|\max\left\\{T_{\mathrm{harm}}(\delta),CB_h\log\left(\frac{C|\mathcal S|mB_h}{\delta}\right)\right\\}, where CC is a sufficiently large universal constant and Tharm(δ)T_{\mathrm{harm}}(\delta) is the deterministic burn-in specified in Equation (33).

These bounds guarantee ∣θ(T)−θm∣∞≤ε\\|\theta^{(T)}-\theta_m\\|_\infty\le\varepsilon with probability at least 1−δ1-\delta. Since synchronous QTD uses one transition per state per iteration, the total transition count is T∣S∣T|\mathcal S|.

The MDP-dependent constants are specified in Appendix C.1. In particular, under Assumption 1(i), the boundary margin Δm\Delta_m enters the local radius routr_{\mathrm{out}} and therefore the sufficient burn-in.

Under Assumption 1(ii), with c≍μ−1c\asymp\mu^{-1} and t0≍ct_0\asymp c, the harmonic result simplifies, up to logarithmic factors, to O~M(∣S∣max⁡m13/3,mε−2).\widetilde O_{\mathcal M}\left(|\mathcal S|\max\\{m^{13/3},m\varepsilon^{-2}\\}\right). The same polynomial dependence holds under Assumption 1(i) when Δm≳m−1\Delta_m\gtrsim m^{-1}. A smaller boundary margin can increase the required burn-in.

2. The comparison with the model-based estimator therefore concerns the leading statistical term.

Our comparison with the model-based estimator concerns the leading statistical term, rather than the full sample complexity in mm. Specifically, the sufficient burn-in is independent of the target accuracy ε\varepsilon, so for fixed mm and MDP, the total transition cost is governed by O~M(∣S∣mε−2)\widetilde O_{\mathcal M}(|\mathcal S|m\varepsilon^{-2}) for sufficiently small ε\varepsilon. How small ε\varepsilon must be depends on the sufficient burn-in, whose dependence on mm is beyond our consideration in this work.

3. The harmonic gain also depends on unknown MDP constants.

We agree that the sufficient harmonic gain condition depends on cMc_{\mathcal M}, but its exact value is not required for convergence. A known positive lower bound on cMc_{\mathcal M}, together with an upper bound on C0C_0, suffices to choose a conservative gain cc and offset t0t_0 satisfying the tuning conditions in Corollary 3.3.

Our polynomial-step results offer a different trade-off, establishing the rate T−a/2T^{-a/2} up to logarithmic factors for every a∈(0,1)a\in(0,1) without this drift-dependent lower bound on the gain. In practice, the results in (the newly added) Figure 4 suggest that for harmonic stepsizes, a suitably chosen gain below the sufficient theoretical threshold can yield an empirical convergence rate similar to that obtained with a gain satisfying the condition. Developing a tuning rule that retains the T−1/2T^{-1/2} rate up to logarithmic factors without prior bounds on cMc_{\mathcal M} is an interesting direction for future work.

We thank the reviewer for the careful and technically detailed assessment. We have expanded the theoretical results and numerical experiments to clarify the total sample complexity, the scope of Assumption 2, and the practical implications of our sufficient conditions.

4. Can the main result be stated for fixed mm, extending the refinement in Appendix C.3 to the local analysis?

We agree that the one-state uniform-reward MDP does not satisfy Assumption 2 simultaneously for all mm. Indeed, at m=3m=3, the projected fixed point is θ3=(2/3,1,4/3),\theta_3=(2/3,1,4/3), which violates Assumption 2.

However, QTD operates at a fixed quantile resolution, for which the all-resolution condition can be relaxed. We have added Proposition C.1 in Appendix C.7, showing that if Δm>0\Delta_m>0 at a fixed mm, Theorem 3.1 and Corollaries 3.2–3.3 remain valid with cM,mc_{\mathcal M,m} replacing cMc_{\mathcal M}, and with the derived constants and sufficient conditions updated accordingly.

For the uniform-reward experiment, the fixed-resolution condition holds at m=1,7,15,31m=1,7,15,31, including the original experimental resolution m=7m=7. Proposition C.1 therefore resolves the assumption-scope issue for these settings, as clarified in Section 5 and Appendix E.2. At m=3m=3, the condition fails, but the same empirical convergence rate is still observed, suggesting that the condition may be relaxed through an improved analysis. We leave the development of such an analysis to future work.

As explained in Section 3, we impose Assumption 2 for all mm to obtain an MDP-dependent constant cMc_{\mathcal M} that is independent of mm, allowing us to characterize the dependence of our bounds on the quantile resolution. Appendix C.8 further discusses uniform lower bounds for the fixed-resolution constants.

5. The harmonic experiment uses a gain outside the sufficient tuning given in the proof.

We have clarified the sufficient harmonic tuning condition and added experiments that distinguish the theoretically sufficient gain parameter cc from gains that perform well in practice.

For the uniform-reward model with m=7m=7 and γ=0.5\gamma=0.5, the sufficient gain condition is

=\frac{64m}{c_{\mathcal M,7}},$$ using the fixed-resolution extension and $C_{\mathrm{harm}}=8$. Since $c_{\mathcal M,7}\approx0.538$, the original choice $c=20$ indeed does not satisfy this sufficient condition, but $c=1792$ does. To address the concern, we added **Figure 4** comparing $c=20$ with $c=1792$. Both choices exhibit squared-error slopes close to $-1$, consistent with the predicted $T^{-1}$ decay, while the smaller gain achieves substantially lower finite-time errors. Thus, the predicted rate is also observed under a sufficient gain, although smaller gains can perform better in practice. # 6. Please clarify which experimental settings satisfy the theoretical gain and burn-in conditions. At $m=7$, the harmonic gain $c=1792$ in Figure 4 satisfies the sufficient gain condition, whereas $c=20$ in Figure 1(a) does not, as detailed above. The full sufficient burn-in conditions are not met within the iteration ranges used in our rate experiments. In particular, Appendix E.5 shows that the capture condition for the polynomial schedule in Figure 1 would require $T$ of order $10^{15}$, whereas those experiments run for $10^5$ iterations. Nevertheless, the predicted convergence rates are already visible after $10^4$ to $10^5$ iterations. These results support the predicted decay rates while quantifying the conservativeness of the sufficient burn-in. The conditions guarantee entrance into the local region and subsequent capture with high probability; they are sufficient bounds rather than estimates of the earliest time at which the predicted convergence behavior appears in practice. # 7. Could you include a case where the probability bound is informative while some trajectories have not yet entered the target neighborhood? For the entrance bound, we have added **Figure 5(b)**, which starts just outside the target neighborhood and compares the general upper bound, empirical non-entrance probabilities, and an exact probability computed by the recursion proved in Lemma E.1. At iteration $100$, the theoretical upper bound is $0.998878$, while $2{,}290$ of $200{,}000$ trajectories have not yet entered, corresponding to an empirical probability of $0.01145$. The bound is therefore nontrivial while non-entrance is still observed, although it remains conservative. Interestingly, in this simple example used in our experiment, the exact probabilities can be computed via a simple recursion in Lemma E.1. The theoretical result agrees closely with the Monte Carlo estimates.

We thank the reviewer for the careful and technically detailed assessment. We have expanded the theoretical results and numerical experiments to clarify the total sample complexity, the scope of Assumption 2, and the practical implications of our sufficient conditions.

8. The numerical settings test only a small part of the theory.

We have expanded the experiments to address each of these aspects.

  • Figure 1(b) compares m∈1,3,7,15,31m\in\\{1,3,7,15,31\\} under a common polynomial schedule. The squared-error curves nearly coincide and decay approximately as T−0.75T^{-0.75}. Appendix E.3 and Table 1 further examine the harmonic schedule with c=256mc=256m. For m∈{7,15,31}m\in\{7,15,31\}, the final squared error grows approximately linearly with mm, with a fitted log-log slope of 1.071.07, consistent with the leading m/Tm/T dependence.

  • Figure 1(c) tests polynomial exponents a∈0.25,0.4,0.5,0.6,0.75,0.9a\in\\{0.25,0.4,0.5,0.6,0.75,0.9\\}, including the nonsquare-summable regime a≤1/2a\le1/2. The fitted squared-error slopes are close to −a-a, consistent with the predicted T−aT^{-a} decay.

  • To examine local curvature beyond the uniform-reward setting, Appendix E.4 and Figure 3(a) use the linear reward density p(r)=0.5+rp(r)=0.5+r and Beta$(2,2)$ rewards. The fitted squared-error slopes are −0.747-0.747 and −0.780-0.780, respectively, close to the predicted value of −0.75-0.75.

  • To examine coupling between states, Figure 3(b) uses a two-state MDP with different reward distributions at the two states and switching probabilities p∈0.05,0.3,0.5p\in\\{0.05,0.3,0.5\\}. The fitted slopes are −0.752-0.752, −0.761-0.761, and −0.738-0.738, again close to −0.75-0.75. These experiments directly test the predicted dependence on quantile resolution and step-size exponent and support the convergence rates beyond the original one-state uniform-reward setting.

These revisions clarify both the scope of our theoretical guarantees and their relation to the observed behavior of QTD. Our work establishes the first global, high-probability finite-sample convergence rates for the last iterate of QTD, covering entrance from arbitrary initialization, subsequent local capture, and the canonical T−1/2T^{-1/2} rate with optimal dependence on mm up to logarithmic factors. The explicit sufficient conditions make these guarantees quantitative, although optimizing their numerical constants is not the focus of this work. The expanded experiments support the predicted rates and show that they can emerge well before the sufficient burn-in conditions are met.

Reviewer_SUqmOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper completes a finite-sample analysis of quantile gradient descent (QTD), applied specifically to learn the return distribution in a reinforcement learning setup. Specifically, their main result is a concentration inequality for QTD stopped at a finite time T. This is proven using two stages: first, they prove that beginning from any rough estimate, it enters the vicinity of the true estimate fairly quickly with high probability. Then, they prove that, once the estimate reaches the region, it is "captured" there for the rest of the iterates with high probability.

Critical strengths
  1. The paper is written very well: the central question is explained at length, the proof of the main result is elaborated on sufficiently, and finally the spacing and usage of the nine available pages is good.

  2. The paper answers an important question and has ensured to demonstrate this sufficiently in its literature review and introduction (more on this, though).

  3. The paper's appendices are organized as well as the main article, and in general it was extremely easy on the eye to read and work with. No mathematical gaps were found.

Critical weaknesses
  1. There is insufficient discussion on the strength of the assumptions: in particular I think some of them might be too strong.

  2. I think some of the novelty claims for the lemmas are overstated. The result is novel, but in particular I would retract novelty claims about some of the accompanying lemmas.

These concerns are invalid post author comments

Questions for authors

I have the following questions in mind.

a) Describing variance–drift matching as a novel principle, is what I think is overstated. It gives the feel of something relatively standard in the field of variance inequalities. Your thoughts are welcome.

b) Minor point; through scaling your framework extends to bounded rewards (provided the assumptions work out for the resulting transformed random variable). This is worth a mention.

c) Assumption 1 is really strong. I believe that it excludes a number of MDPs in common literature. For example, those whose rewards are in fact deterministic are excluded. Similarly, discrete reward distributions are also excluded, as are those which are mixtures (e.g. R = U[0,1] with probability 1/2 and R = U[2,3] with probability 1/2 are excluded : even with a rescaling, you cannot accommodate such rewards). This really needs main body discussion.

These questions have now been addressed in the comments, and I have upgraded my rating

d) Assumption 2 sounds extremely weak: just by perturbing the MDP ever so slightly one can easily obtain the condition. This is worth mentioning (and correct me if I'm wrong!)

e) The quantity cMc_{\mathcal{M}} is too abstract to be left alone. Some elaboration on precisely what its size is for typical MDPs of interest is important. Note that if this quantity is small, the burn-in assumption (number 2 of the main theorem) becomes harder to satisfy, so this should be clarified.

f) Your experiments are thin in the appendix (not that much in the main body, given the rest of the content). For the breadth of results under which you have obtained your bounds, your experiments could really explore the breath of those assumptions a lot more.

g) Also, I understand that your paper used the bounded nature of the rewards strongly, but I believe you should consider unbounded rewards; there might be some good extensions there.

4 comments
AuthorsOpenReview ↗

Answers to Questions (a) and (c)

We thank the reviewer for the careful reading and constructive suggestions. We have expanded the discussion of the assumptions, added theoretical counterexamples, and substantially strengthened the experiments. We address the questions in order.

(a) Novelty of variance–drift matching.

We thank the reviewer for this comment. We agree that variance-sensitive concentration and the variance properties of quantile scores are classical. Our novelty claim concerns a specific argument on bounding the quadratic variation of the propagated noise for the coupled QTD dynamics, not a new general principle of variance inequalities. The contribution is to identify and exploit a relationship that a separate worst-case treatment of variance and contraction would miss.

Intuitively, weak restoring drift allows stochastic fluctuations to persist longer. In QTD, however, the conditional variance of the quantile score is controlled by the same density weights that determine the restoring drift. Our analysis preserves this compensation as noise propagates across coupled quantile coordinates, even though these coordinates share the same transition sample.

Specifically, Lemma 4.4 identifies the common factor v⊤Dm1v^\top D_m\mathbf 1 in the conditional variance bound and the decrease in propagation weight. Using the nonnegative propagation matrices, Lemma D.3 converts this relationship into a telescoping bound. The accumulated conditional variance Vr,k\mathcal V_{r,k} of the stopped, propagated noise over [r,k)[r,k) then satisfies

\le \frac{2\alpha_r}{c_{\mathcal M}(1-\gamma)},$$ where $c_{\mathcal M}$ quantifies the strength of this variance–drift relationship, as further explained in our response to point (e). In contrast, controlling the conditional variance and contraction separately through uniform worst-case bounds gives $$\mathcal V_{r,k} =O\left(\frac{\alpha_r}{\mu}\right),\quad \mu=\frac{c_{\mathcal M}(1-\gamma)}{4m}.$$ The matching argument therefore **removes an additional factor of $m$ from the accumulated variance bound**. With the harmonic tuning $c\asymp\mu^{-1}$ and other problem parameters fixed, this improves the leading post-burn-in stochastic error from $$\widetilde O\left(\frac{m}{\sqrt T}\right) \ \text{to}\ \widetilde O\left(\sqrt{\frac mT}\right).$$ The improved rate matches the local asymptotic minimax lower bound for estimating $\theta_m$ established by Cheng and Zhang (2026), *Near Minimax Rates for Quantile Distributional Reinforcement Learning*, giving optimal dependence on $m$ up to logarithmic factors. To the best of our knowledge, this is the first work to identify and exploit this matching within the finite-sample analysis of QTD. Its significance lies both in the structural insight into the coupled recursion and in its essential role in obtaining the optimal dependence on quantile resolution. The same approach may also be useful for analyzing other quantile-based Bellman learning schemes in which the drift and noise admit analogous relationships. # (c) Strength of Assumption 1. We agree that Assumption 1 excludes important reward models, including deterministic and discrete rewards and distributions with gaps in their support. These conditions in Assumption 1 ensure that the return distributions have continuous densities that are strictly positive in the interiors of their supports (Cheng et al., 2026b, Proposition 2.2). Such positivity is a fundamental regularity condition in quantile analysis. In our setting, it provides the local restoring drift needed to establish the finite-sample convergence rates. Without suitable regularity assumptions on the reward distributions, the stated convergence rates **cannot be guaranteed in general**, even when QTD converges almost surely. We have added two counterexamples in **Appendix F (Proposition F.1)** to establish this point. Both examples are one-state, one-action MDPs with deterministic self-transition and $\gamma=1/2$. In the first example, rewards have a countably supported discrete distribution: $$\mathbb P\left(R=\frac12\pm2^{-k-2}\right) =\frac7{16}8^{-k},\qquad k\ge0,$$ where each sign has the stated probability. In the second example, rewards have the smooth density $$p_R(r)=12\left(r-\frac12\right)^2, \qquad r\in[0,1].$$ For $m=1$, both examples have the unique quantile-projected Bellman fixed point $\theta_1=1$, and QTD converges to it almost surely. However, starting from $\theta^{(0)}=5/4$ and using $\alpha_t=c(t+1)^{-3/4}$ for sufficiently small $c>0$, Proposition F.1 proves that $$\mathbb P\left( |\theta^{(t)}-\theta_1| \ge\frac1{16}(t+1)^{-1/8} \text{ for all }t\ge0 \right)>0.$$ Consequently, the $T^{-3/8}$ rate does not hold in general. The key mechanism is that in both examples, the mean field satisfies $0<h(e)\le4e^3$ for $0<e\le1/2$. We have also cited these results in Section 2.3. We thank the reviewer for motivating this addition, which strengthens the theoretical justification for Assumption 1.
AuthorsOpenReview ↗

Answers to Questions (b), (d), (e), (f), (g)

We thank the reviewer for the careful reading and constructive suggestions. We address the questions in order.

(b) Extension to other bounded reward intervals.

We agree. We have added a footnote in Section 2.1 explaining that rewards supported on any bounded interval can be normalized to [0,1][0,1] by an affine transformation. The corresponding density assumptions are imposed after this normalization.

(d) Assumption 2 and perturbations.

We agree with the reviewer's intuition that Assumption 2 is a mild noncoincidence condition. For any fixed mm, it excludes only finitely many exact boundary alignments. Even when imposed simultaneously for all mm, the condition involves only countably many such restrictions, and a perturbation argument can be considered in an appropriate topological setting. Formulating a rigorous genericity statement would require specifying the class of MDPs and the admissible perturbations, so we do not pursue this technical question in this paper.

(e) Interpretation and size of cMc_{\mathcal M}.

The constant cMc_{\mathcal M}, which is used in our variance–drift matching argument, quantifies how strongly a displacement from a target quantile changes the corresponding Bellman-target CDF. Thus, smaller values correspond to weaker restoring drift and can lead to longer sufficient burn-in times.

We have expanded the discussion in Section 3 and explicitly discuss the size of cMc_{\mathcal M} in Appendix C.8. In particular, the proof of the corresponding result in Cheng et al. (2026b) gives, for all sufficiently large mm, c_{\mathcal M,m}\ge\frac14\min\left\\{1-\gamma,\inf_{s\in\mathcal S,x\in[x_0,(1-\gamma)^{-1}-x_0]}p_{\eta^\pi(s)}(x)\right\\}, where x0>0x_0>0 depends only on the MDP. The finitely many smaller resolutions satisfying the fixed-resolution no-boundary-quantile condition also have positive cM,mc_{\mathcal M,m}, yielding a common positive lower bound over the admissible resolutions.

As a concrete example, for the one-state uniform-reward MDP used in the experiments, the fixed-resolution constant at m=7m=7 is approximately cM,7≈0.538c_{\mathcal M,7}\approx0.538. Appendix C.1 specifies how this constant enters the local radius, contraction coefficient, and global entrance condition, while Appendix C.8 gives the resulting sample-complexity bounds.

(f) Experimental coverage.

In response to this concern, we have substantially expanded the numerical experiments to examine the dependence on quantile resolution and step-size exponents, as well as the effects of local nonlinearity and coupling between states. We have also added experiments to assess the sufficient conditions on harmonic gain cc and burn-in conditions and to evaluate the entrance probability bound.

  • Figure 1(b) now studies the number of quantiles, and Figure 1(c) tests polynomial exponents a∈{0.25,0.4,0.5,0.6,0.75,0.9}a\in\{0.25,0.4,0.5,0.6,0.75,0.9\}, including the nonsquare-summable regime a≤1/2a\le1/2. The fitted squared-error slopes are close to the predicted values −a-a.

  • Appendix E.3 and Table 1 examine how errors scale with mm under harmonic step sizes with c∝mc\propto m. Appendix E.4 and Figure 3 further consider nonuniform reward densities, including Beta$(2,2)$ rewards, as well as a two-state MDP with different transition probabilities. The observed squared-error slopes remain close to the predicted value of −0.75-0.75.

  • Appendix E.5 examines the conservativeness of the sufficient gain and burn-in conditions and provides a more detailed evaluation of the entrance probability bound, including an exact probability calculation for a one-state model.

Together, these experiments directly examine the predicted dependence on the step-size exponent and quantile resolution, and show that the predicted convergence rates persist with nonuniform rewards and coupled state dynamics. They provide further numerical support for the rate guarantees beyond the original one-state uniform-reward setting.

(g) Unbounded rewards.

Bounded reward support is a substantive assumption of our local entrance and variance–drift matching arguments in our current two-stage proof. Specifically, in Stage I, Lemma D.1 gives a deterministic bound on the iterates, which controls the error at the start of the entrance block. With unbounded rewards, this bound is no longer available. In Stage II, bounded support, together with our regularity assumptions, ensures that cMc_{\mathcal M} is strictly positive and independent of mm. For unbounded rewards, it is not straightforward to extend our current assumptions to ensure a strictly positive constant cMc_{\mathcal M} independent of mm.

An extension therefore requires new finite-sample control of the iterates and suitable density conditions to retain the stated dependence on mm. As noted in Section 2.1, truncation provides a bounded approximation, but extending the guarantees to the original unbounded-reward problem requires further analysis.

Reviewer_SUqmOpenReview ↗

Response to author comments

Respected Authors,

Noting the requested changes, I shall be upgrading my rating to 4 from 3. Thank you very much for your excellent addressal of my comments.

We sincerely thank the reviewer for the positive feedback and for taking the time to reconsider our work. We appreciate the thoughtful comments and encouragement.

Reviewer_4vV9OpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proves finite-time and high-probability convergence rates for quantile temporal-difference learning, which previously only had asymptotic convergence guarantees. Specifically, this paper proves that the last iterate error shrinks as Tα/2T^{\alpha/2} for polynomially decaying step sizes. This gives m/T\sqrt{m/T} error for m quantiles. Constant steps level off at a \sqrt{n} noise floor.

Critical strengths
  • The theory covers constant, polynomial and harmonic decaying step sizes, notably, it does not require square summability of step sizes
  • Novel techniques (two-stage global-to-local argument) in derivation and new insights (e.g. variance-drift property) are introduced,
  • The theory is supported by experimental results
Critical weaknesses
  • It appears that the m-scaling is not tested in the experiments. Specifically, the errors under different values of m are not tested
  • The bound appears to be loose in practice; in figure 1(c) the bound stays vacuous from ~10^4 to ~10^5
Questions for authors

Are the bounds tight in big-O with respect to m and 1-\gamma? For instance, can the scaling \sqrt{m/T} be shown to be tight?

1 comment

We thank the reviewer for the positive assessment and the helpful questions. We have expanded the experiments and clarified the dependence of our bounds on the quantile resolution and the discount factor.

Weakness 1. It appears that the m-scaling is not tested in the experiments. Specifically, the errors under different values of m are not tested.

Thanks for this question. To address it, we added new experiments. Specifically, we added Figure 1(b), which compares m∈1,3,7,15,31m\in\\{1,3,7,15,31\\} under a common polynomial step-size schedule. The error curves are nearly coincident and exhibit the predicted squared-error decay rate T−aT^{-a}. For resolutions satisfying the no-boundary-quantile condition (Assumption 2), this agrees with Corollary 3.2(ii), Proposition C.1, and (newly added) Appendix C.8, whose leading noise term depends on mm very mildly (logarithmically).

Moreover, we also added Appendix E.3 and Table 1 to examine the harmonic schedule with c=256mc=256m. For m∈7,15,31m\in\\{7,15,31\\}, the final squared error grows approximately linearly with mm, with a fitted log-log slope of about 1.071.07. This agrees with the m/Tm/T scaling of the squared leading term in Corollary 3.3.

Weakness 2. The bound appears to be loose in practice; in figure 1(c) the bound stays vacuous from 10410^4 to 10510^5.

We agree that the original experiment did not assess the bound where a nonzero fraction of trajectories had yet to enter the target region. We have moved and expanded this analysis in Appendix E.5 (Figure 5).

The new experiment includes a setting in which the theoretical upper bound is strictly below one while some trajectories have not entered. At iteration 100100, the upper bound is 0.9988780.998878, whereas the empirical non-entrance probability is 0.011450.01145 over 200,000200{,}000 trajectories. We also compute the exact probability for this one-state example, which agrees with the Monte Carlo estimates.

Although numerically conservative, the entrance bound is sufficiently strong to establish the stated finite-sample convergence rates from arbitrary initialization. Our focus is on the order of these rates rather than optimizing the constants in the sufficient burn-in conditions, so these conditions can substantially overestimate the time needed in practice.

Question 1. Are the bounds tight in big-O with respect to mm and 1−γ1-\gamma? For instance, can the scaling m/T\sqrt{m/T} be shown to be tight?

Thanks for this insightful question. The m/T\sqrt{m/T} dependence in Corollary 3.3 is optimal up to logarithmic factors. Cheng and Zhang (2026), Near Minimax Rates for Quantile Distributional Reinforcement Learning, establish a matching local asymptotic minimax lower bound for estimating the quantile-projected Bellman fixed point θm\theta_m under ∥⋅∥∞\|\cdot\|_\infty norm. We have added this comparison to Section 3.

Regarding the dependence on 1−γ1-\gamma, we introduce cM,mc_{\mathcal M,m} in Appendix C.7 and Appendix C.8 provides the following lower bound for all sufficiently large mm:

c_{\mathcal M,m}\ge\frac14\min\left\\{1-\gamma,\inf_{s\in\mathcal S, x\in[x_0,(1-\gamma)^{-1}-x_0]}p_{\eta^\pi(s)}(x)\right\\},

where x0>0x_0>0 depends only on the MDP. This bound captures both explicit dependence on 1−γ1-\gamma and implicit dependence through the return densities. Whether this dependence on 1−γ1-\gamma is optimal is left as future work.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.