Technical Summary: A Robust $O(1/\sqrt{T})$ Rate for Unprojected TD Learning with Linear Function Approximation

Problem Statement

Temporal Difference (TD) learning with linear function approximation is a fundamental algorithm in reinforcement learning for policy evaluation. While asymptotic convergence is well-understood, establishing finite-time convergence rates under realistic conditions—specifically when data is generated by a Markov chain (Markovian noise) rather than independent samples—remains challenging.

A critical theoretical gap exists regarding the "robust" convergence rate of $O(1/\sqrt{T})$. Prior work establishing this rate (e.g., Bhandari et al., 2018) relied on an artificial projection step, where iterates are forced onto a bounded set to prevent divergence. This projection is rarely used in practice and requires knowledge of a bound on the optimal solution $\theta^*$, which is often unavailable. Conversely, "fast" convergence rates of $O(1/T)$ exist for unprojected TD learning, but they depend on the inverse square of the potential function's minimal curvature ($\omega$). Since $\omega$ can be arbitrarily small (ill-conditioned problems), the fast rate can degrade significantly in non-asymptotic regimes.

The open problem, posed by Bhandari et al. (2018), is whether unprojected TD(0) can achieve the robust $O(1/\sqrt{T})$ rate without additional regularity conditions or artificial projections.

Methodology

The authors analyze the standard unprojected TD(0) algorithm with linear function approximation under Markovian sampling. Their approach diverges fundamentally from prior analyses that rely on contraction properties or artificial projections.

1. Potential Function Selection

Instead of using the standard $D$-norm distance $\|V_{\bar{\theta}_T} - V_{\theta^*}\|_D^2$, the authors utilize the potential function proposed by Liu and Olshevsky (2021):
$$f(\theta) := (1 - \gamma) \|V_\theta - V_{\theta^*}\|_D^2 + \gamma \|V_\theta - V_{\theta^*}\|_{\text{Dir}}^2$$
This potential is advantageous because:

• It remains well-behaved even as the discount factor $\gamma \to 1$.
• The stationary update field $\bar{g}(\theta)$ satisfies the equality $\langle -\bar{g}(\theta), \theta - \theta^* \rangle = f(\theta) - f(\theta^*)$, which simplifies the analysis compared to inequalities used in other works.

2. Self-Bounding Property via Induction

The core technical contribution is a novel self-bounding property of the TD updates. The authors prove that, without projecting the iterates, the sequence $\{\theta_t\}$ remains bounded in expectation around the optimal solution $\theta^*$, provided the stepsize is chosen carefully.

• Stepsize Design: The stepsize is defined as $\eta_t = \frac{1}{c \phi_\infty^2 \log(T) \log(t+3) \sqrt{t+1}}$, where $c$ is a constant satisfying $c > 15 + 18\sqrt{2}$.
• Inductive Argument: The proof proceeds by induction. Assuming iterates are bounded up to time $t-1$, the authors show that the update at time $t$ remains bounded. This relies on decomposing the update into a martingale difference sequence (noise) and a bias term.
• Handling Markovian Noise: To address the bias introduced by Markovian correlations (where $E[g(\theta, Z_t) | \mathcal{F}_{t-1}] \neq \bar{g}(\theta)$), the authors leverage the geometric mixing of the underlying Markov chain (Theorem 3.2). They bound the bias by relating the current state distribution to the stationary distribution over a lag $k'$, utilizing the decay rate $\alpha^k$.

3. Boundedness Analysis

The authors demonstrate that the iterates satisfy:
$$E[\|\theta_t\|^2] \leq \rho_c^2 \max\left(\frac{r_\infty^2}{\phi_\infty^2}, \|\theta^*\|^2\right)$$
where $\rho_c$ is a constant depending on the stepsize parameter $c$. This boundedness is achieved without projecting the iterates, effectively closing the induction loop.

Key Results

Theoretical Guarantees

Theorem 4.2: For the weighted average iterate $\bar{\theta}_T$ generated by unprojected TD(0) with the specified stepsize, the expected squared norm of the iterates is bounded by a constant independent of the mixing time and the curvature $\omega$.

Corollary 4.3: The algorithm achieves a convergence rate of:
$$f(\bar{\theta}_T) - f(\theta^*) = \tilde{O}\left( \frac{c \rho_c^2 \max\{r_\infty^2, \phi_\infty^2 \|\theta^*\|^2\}}{\sqrt{T}} \right)$$
Crucially, the hidden constants in the $\tilde{O}$ notation depend on $\|\theta^*\|$ and feature bounds but do not depend on the minimal curvature $\omega$ or the mixing time $\alpha$ (except for a minor polylogarithmic correction in the stepsize condition).

Comparison with Prior Work

• Vs. Projected Robust Rates: Unlike Bhandari et al. (2018), this result removes the projection step and the requirement to know a priori bounds on $\theta^*$. The rate is comparable ($\tilde{O}(1/\sqrt{T})$) but achieved without artificial constraints.
• Vs. Unprojected Fast Rates: Unlike Srikant and Ying (2019) and subsequent works achieving $O(1/T)$, this result does not depend on the unknown curvature parameter $\omega$. The authors show via a counter-example that $\omega$ can be arbitrarily small, making fast rates potentially arbitrarily slow in practice, whereas the robust rate remains stable.

Significance and Claims

The paper claims to solve a specific open problem identified by Bhandari et al. (2018): providing a finite-time analysis of unprojected TD(0) with linear function approximation that achieves a robust convergence rate.

• Removal of Artificial Assumptions: The work demonstrates that the projection step, previously deemed necessary for robust analysis, is not required. The boundedness of iterates emerges naturally from the algorithm's dynamics when the stepsize is appropriately scaled with logarithmic factors.
• No Additional Regularity: The result holds without assuming additional regularity conditions on the problem structure beyond standard assumptions (irreducibility, aperiodicity, full column rank of features).
• Practical Relevance: The authors emphasize that while projections are used in theory to simplify proofs, they are not used in practice. This analysis bridges the gap between theoretical guarantees and practical algorithm design.
• Stability Threshold: The paper identifies a threshold for the stepsize constant $c$ (specifically $c > 15 + 18\sqrt{2}$) as a sufficient condition for stability. Experimental results on synthetic data suggest this threshold captures a genuine finite-time stability effect; if $c$ is too small, iterates can diverge.

The authors note that the threshold on $c$ is a conservative sufficient condition derived from the proof constants (triangle inequality, Cauchy-Schwarz, integral tests) and is not necessarily a tight practical tuning rule. Furthermore, the requirement for $T$ to be sufficiently large relative to the mixing time $\alpha$ is acknowledged as a limitation shared by the broader literature on robust bounds, though the authors prefer an executable presentation of assumptions over an "anytime" formulation that would require knowledge of unknown mixing parameters.