Near-Minimax-Optimal Rates for Asynchronous TD Learning with Markovian Data
Abstract
We study the last iterate of standard importance-weighted temporal-difference (TD) learning from a single trajectory of a finite Markov decision process. The trajectory follows a behavior policy b with an irreducible, possibly periodic state chain; a target policy π covered by b is evaluated with action importance ratios bounded by ϱ. Write H=(1−γ)−1, with μmin the minimum stationary probability and h⋆ the largest expected hitting time of the reverse behavior state chain. We prove that the last iterate achieves sup-norm error at most ε with high probability after Õ(ϱ H3/(μminε2)+h⋆) transitions for 0<ε≤1. The statistical term retains the cubic effective-horizon dependence of synchronous TD, while the initialization cost is additive in h⋆. Setting b=π and ϱ=1 recovers the on-policy rate. For aperiodic behavior chains, h⋆=Õ(tmix/μmin) recovers a mixing-time bound. The proof combines an anchored local Poisson equation in reverse time to control fluctuations without a mixing-time factor, a compensation argument for successive hitting costs, and an expected cumulative propagation mass bound for decreasing step sizes. Given the policy ratios and their bound, an empirical state-count rule attains the same rate without prior knowledge of model parameters. The framework covers nonnegative affine importance-weighted prediction updates, including successor features, transition-dependent discounting, and coupled finite-mode predictions. A perturbation estimate yields a time-uniform guarantee for online return-variance estimation. A three-state, two-action construction gives matching minimax lower bounds for both terms up to logarithmic factors on the considered parameter classes.
Related
- Reinforcement Learning for Hierarchical Reasoning Rewards: Minimax-Optimal Rates with Transformers
- Minimax rates for learning spectral Barron functions by deep ReLU neural networks
- Minimax Rates for Conditional Generative Learning under Wasserstein Loss
- Minimax Rates for Learning Smooth Populations of Parameters
- Minimax-optimal Scaling Laws in Ridge Regression via Transfer Learning
BibTeX
@misc{peng2026nearminimaxoptimal,
title = {{Near-Minimax-Optimal Rates for Asynchronous TD Learning with Markovian Data}},
author = {Yang Peng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.38880},
eprint = {2609.38880},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.38880},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Near-Minimax-Optimal Rates for Asynchronous TD Learning with Markovian Data
AU - Yang Peng
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2609.38880
UR - https://arxiv.org/abs/2609.38880
AB - We study the last iterate of standard importance-weighted temporal-difference (TD) learning from a single trajectory of a finite Markov decision process. The trajectory follows a behavior policy b with an irreducible, possibly periodic state chain; a target policy π covered by b is evaluated with action importance ratios bounded by ϱ. Write H=(1−γ)^−1, with μ_min the minimum stationary probability and h_⋆ the largest expected hitting time of the reverse behavior state chain. We prove that the last iterate achieves sup-norm error at most ε with high probability after Õ(ϱ H^3/(μ_minε^2)+h_⋆) transitions for 0<ε≤1. The statistical term retains the cubic effective-horizon dependence of synchronous TD, while the initialization cost is additive in h_⋆. Setting b=π and ϱ=1 recovers the on-policy rate. For aperiodic behavior chains, h_⋆=Õ(t_mix/μ_min) recovers a mixing-time bound. The proof combines an anchored local Poisson equation in reverse time to control fluctuations without a mixing-time factor, a compensation argument for successive hitting costs, and an expected cumulative propagation mass bound for decreasing step sizes. Given the policy ratios and their bound, an empirical state-count rule attains the same rate without prior knowledge of model parameters. The framework covers nonnegative affine importance-weighted prediction updates, including successor features, transition-dependent discounting, and coupled finite-mode predictions. A perturbation estimate yields a time-uniform guarantee for online return-variance estimation. A three-state, two-action construction gives matching minimax lower bounds for both terms up to logarithmic factors on the considered parameter classes.
ER -