[Submitted on 30 Sep 2026 (v1), last revised 9 Oct 2026 (this version, v2)]
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 $pi$ covered by $b$ is evaluated with action importance ratios bounded by $varrho$. Write $H=(1-gamma)^{-1}$, with $mu_{min}$ the minimum stationary probability and $mathfrak h_star$ the largest expected hitting time of the reverse behavior state chain. We prove that the last iterate achieves sup-norm error at most $varepsilon$ with high probability after $widetilde O(varrho H^3/(mu_{min}varepsilon^2)+mathfrak h_star)$ transitions for $0
Submission history
From: Yang Peng [view email]
[v1] Wed, 30 Sep 2026 03:31:05 UTC (44 KB)
[v2] Fri, 9 Oct 2026 17:16:04 UTC (61 KB)