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 a∈(0,1), the last iterate converges to the target at rate T−a/2 in the infinity norm, up to logarithmic and lower-order terms. A suitably tuned harmonic schedule recovers the T−1/2 statistical rate up to logarithmic factors. For the m-quantile representation, its ∞-Wasserstein error scales as √(m/T) 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.
Related
- A Sharp Finite-Iteration Theory for Asynchronous Categorical Distributional Temporal-Difference Learning
- Finite-Sample Distribution Theory and Efficient Large-Scale Inference for Online Quantile Regression
- Beyond Source-Level Transfer: Sample-Level Learning for High-Dimensional Quantile Regression
- Online Inference in Distributional Temporal-Difference Learning
- On Convergence of Gradient Temporal-Difference Learning with Regularized Corrections and Eligibility Traces
BibTeX
@misc{cheng2026finitesample,
title = {{A Finite-Sample Analysis of Quantile Temporal-Difference Learning}},
author = {Zijie Cheng and Xiang Li and Yang Peng and Zhihua Zhang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.27313},
eprint = {2608.27313},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.27313},
}
RIS
TY - UNPB
TI - A Finite-Sample Analysis of Quantile Temporal-Difference Learning
AU - Zijie Cheng
AU - Xiang Li
AU - Yang Peng
AU - Zhihua Zhang
PY - 2026
DA - 2026/09/17
PB - arXiv
DO - 10.48550/arxiv.2608.27313
UR - https://arxiv.org/abs/2608.27313
AB - 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 a∈(0,1), the last iterate converges to the target at rate T^−a/2 in the infinity norm, up to logarithmic and lower-order terms. A suitably tuned harmonic schedule recovers the T^−1/2 statistical rate up to logarithmic factors. For the m-quantile representation, its ∞-Wasserstein error scales as √(m/T) 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.
ER -