- 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
-
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.
-
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
-
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 . 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 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 . For the one-state MDP with uniform rewards and , the exact projected fixed point at is . The first and third coordinates then give boundary alignments at 0 and 1. The resolution 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 would address this issue.
-
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 , requiring . Definition (2) implies , by considering the upper quantile and a displacement of . For and , the explicit sufficient condition therefore requires , whereas Figure 1(b) uses . 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 and , the formulas give , while . 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 , polynomial exponents , or the local curvature and coupling between states. A few targeted experiments would strengthen the empirical support.
Questions for authors
-
Please state a sufficient total transition count for error relative to the projected target, including burn-in, MDP constants and the boundary margin.
-
Can the main result be stated for fixed , extending the refinement in Appendix C.3 to the local analysis? This would clarify its applicability to the experimental MDP.
-
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.
4. Can the main result be stated for fixed , 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 . Indeed, at , the projected fixed point is 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 at a fixed , Theorem 3.1 and Corollaries 3.2–3.3 remain valid with replacing , and with the derived constants and sufficient conditions updated accordingly.
For the uniform-reward experiment, the fixed-resolution condition holds at , including the original experimental resolution . Proposition C.1 therefore resolves the assumption-scope issue for these settings, as clarified in Section 5 and Appendix E.2. At , 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 to obtain an MDP-dependent constant that is independent of , 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 from gains that perform well in practice.
For the uniform-reward model with and , 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 under a common polynomial schedule. The squared-error curves nearly coincide and decay approximately as . Appendix E.3 and Table 1 further examine the harmonic schedule with . For , the final squared error grows approximately linearly with , with a fitted log-log slope of , consistent with the leading dependence.
-
Figure 1(c) tests polynomial exponents , including the nonsquare-summable regime . The fitted squared-error slopes are close to , consistent with the predicted decay.
-
To examine local curvature beyond the uniform-reward setting, Appendix E.4 and Figure 3(a) use the linear reward density and Beta$(2,2)$ rewards. The fitted squared-error slopes are and , respectively, close to the predicted value of .
-
To examine coupling between states, Figure 3(b) uses a two-state MDP with different reward distributions at the two states and switching probabilities . The fitted slopes are , , and , again close to . 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 rate with optimal dependence on 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.
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 ε 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, 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) 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 C is a sufficiently large universal constant and Tharm(δ) is the deterministic burn-in specified in Equation (33).
These bounds guarantee ∣θ(T)−θm∣∞≤ε with probability at least 1−δ. Since synchronous QTD uses one transition per state per iteration, the total transition count is T∣S∣.
The MDP-dependent constants are specified in Appendix C.1. In particular, under Assumption 1(i), the boundary margin Δm enters the local radius rout and therefore the sufficient burn-in.
Under Assumption 1(ii), with c≍μ−1 and t0≍c, the harmonic result simplifies, up to logarithmic factors, to OM(∣S∣maxm13/3,mε−2). The same polynomial dependence holds under Assumption 1(i) when Δm≳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 m. Specifically, the sufficient burn-in is independent of the target accuracy ε, so for fixed m and MDP, the total transition cost is governed by OM(∣S∣mε−2) for sufficiently small ε. How small ε must be depends on the sufficient burn-in, whose dependence on m 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 cM, but its exact value is not required for convergence. A known positive lower bound on cM, together with an upper bound on C0, suffices to choose a conservative gain c and offset t0 satisfying the tuning conditions in Corollary 3.3.
Our polynomial-step results offer a different trade-off, establishing the rate T−a/2 up to logarithmic factors for every a∈(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/2 rate up to logarithmic factors without prior bounds on cM is an interesting direction for future work.