Technical Summary: A Single Stepsize Suffices for Unprojected Linear TD(0)

Problem Statement

The paper addresses the finite-time, high-probability convergence analysis of linear Temporal Difference learning with zero-bias (TD(0)) under Markovian sampling. In this setting, data is generated along a single trajectory of a Markov chain rather than as independent and identically distributed (i.i.d.) samples.

The core challenge lies in the fact that TD(0) is not a standard stochastic gradient method; its updates are biased, non-symmetric, and the noise is temporally correlated. Furthermore, the magnitude of the update depends on the magnitude of the current iterates. Existing non-asymptotic analyses typically rely on one of two restrictive approaches:

1. Projections: Enforcing boundedness by projecting iterates onto a known ball. This simplifies concentration arguments but alters the algorithm and requires prior knowledge of a suitable radius (often tied to the problem's curvature).
2. Curvature-Dependent Stability: Exploiting the contractive nature of the mean dynamics to argue stability without projections. However, this typically yields stepsize conditions or stability bounds that depend on an unknown curvature parameter ($\omega$). When $\omega$ is small, these bounds become arbitrarily slow, and the stepsize cannot be chosen independently of $\omega$.

The authors aim to establish a single stepsize schedule that is independent of the curvature parameter $\omega$ and requires no projections, yet simultaneously guarantees:

• Robustness: A convergence rate of $\tilde{O}(1/\sqrt{T})$ that holds regardless of $\omega$.
• Fastness: A convergence rate of $\tilde{O}(1/(\omega T))$ that exploits favorable curvature when it exists.

Methodology

1. Self-Bounding Argument via Poisson Equations

The central technical novelty is a new "self-bounding" inductive argument that controls the pathwise boundedness of the iterates $\theta_t$ without relying on curvature $\omega$ or artificial projections.

• The Loop: A naive concentration analysis is circular: bounding the error requires bounded updates, but bounded updates require bounded iterates.
• The Solution: The authors decompose the Markovian noise using the Poisson equation associated with the geometrically mixing Markov chain. For a centered forcing term $h$, they solve $u - P_Z u = \tilde{h}$.
• Decomposition: This allows the accumulation of Markov noise terms to be decomposed into a martingale term ($M_t$) and a controlled remainder term ($R_t$).
• Induction: They establish an inductive hypothesis where boundedness of iterates up to time $t-1$ implies boundedness at time $t$. By controlling the martingale term via Pinelis' inequality and the remainder term via the Lipschitz properties of the Poisson solution, they prove that the iterates remain uniformly bounded with high probability, independent of $\omega$.

2. Polyak–Ruppert (PR) Averaging

The paper analyzes the Polyak–Ruppert averaged iterate $\bar{\theta}_T = \frac{1}{S_T} \sum_{t=1}^T \eta_{t-1} \theta_{t-1}$, where $S_T = \sum \eta_{t-1}$.

• Once the uniform boundedness of $\theta_t$ is established, the authors can control the quadratic variation of the martingale terms and the bias terms in the convergence analysis.
• They derive two distinct upper bounds for the potential function error $f(\bar{\theta}_T) - f(\theta^*)$:
  • A robust bound derived from a classic averaged stochastic gradient descent analysis, yielding $\tilde{O}(1/\sqrt{T})$.
  • A fast bound derived by analyzing the evolution of the error $e_t = \theta_t - \theta^*$ and leveraging the positive definiteness of the symmetric part of the TD matrix (curvature $\omega$), yielding $\tilde{O}(1/(\omega T))$.

3. Stepsize Schedule

The proposed stepsize is:
$$\eta_t = \frac{1}{c \tau_{\text{mix}} \phi_\infty^2} \cdot \frac{1}{\sqrt{t+1} \log(t+3)}$$
where $c$ is a numerical constant, $\tau_{\text{mix}}$ is the mixing time, and $\phi_\infty$ bounds the feature norms. Crucially, this schedule depends on the mixing time but not on the curvature $\omega$.

Key Results

1. High-Probability Boundedness (Theorem 4.1)

Under standard assumptions (ergodic MRP, full-rank features), the unprojected TD(0) iterates are uniformly bounded with high probability ($1-\delta$):
$$\sup_{t \ge 0} \|\theta_t\|^2 \le \rho R_{\text{base}}$$
where $R_{\text{base}}$ depends on the initial error, the optimal solution norm, and problem constants, but is independent of $\omega$. This is the first result to show such boundedness for unprojected TD(0) under Markovian sampling without using $\omega$ in the stepsize or stability argument.

2. Simultaneous Convergence Rates (Theorem 4.2)

Using the same stepsize and PR averaging, the algorithm achieves a high-probability convergence rate for the potential function error:
$$f(\bar{\theta}_T) - f(\theta^*) \le \min \left\{ \frac{C_{\text{fast}}}{\omega S_T^2}, \frac{C_{\text{robust}}}{S_T} \right\}$$
Substituting the stepsize schedule, this translates to:

• Robust Rate: $\tilde{O}\left( \frac{\tau_{\text{mix}} R_{\text{base}}^2}{\sqrt{T}} \right)$
• Fast Rate: $\tilde{O}\left( \frac{\tau_{\text{mix}}^2 R_{\text{base}}^2}{\omega T} \right)$

The bound automatically adapts to the minimum of these two rates without prior knowledge of $\omega$.

3. Mixing-Free Variant (Appendix E)

The authors also propose a modified stepsize $\eta_t \propto \frac{1}{\sqrt{t} \log^2 t}$ that does not require knowledge of $\tau_{\text{mix}}$. However, this comes at the cost of a doubly exponential dependence on $\tau_{\text{mix}}$ in the constants of the convergence bound, specifically through the initial prefix bound $B_{m^*}$.

Significance and Claims

The paper claims to be the first to establish that linear TD(0) with Markovian sampling can achieve both robust and fast high-probability convergence rates using a single stepsize that is:

1. Independent of the curvature parameter $\omega$.
2. Projection-free.

The authors emphasize that previous works either required projections (changing the algorithm), relied on curvature-dependent stepsizes (failing when $\omega$ is small), or only provided expectation bounds (e.g., Lee and Orabona [2025]) rather than high-probability guarantees.

The significance lies in the self-bounding argument via Poisson equations, which breaks the circular dependency between iterate boundedness and update magnitude without appealing to the contractive properties of the mean dynamics. This allows the algorithm to remain stable and converge rapidly even when the curvature is arbitrarily small, a scenario where previous projection-free analyses typically failed or required data-dropping strategies.

The paper remains modest regarding the dependence on mixing time $\tau_{\text{mix}}$. While the fast rate has a $\tau_{\text{mix}}^2$ dependence (worse than the linear $\tau_{\text{mix}}$ dependence in some prior projection-based or data-dropping works), the authors note that the optimal dependence on $\tau_{\text{mix}}$ in the absence of projections and data dropping remains an open question. They also acknowledge that their initial error term decays at a $1/T$ rate rather than exponentially, a consequence of avoiding contraction-based arguments.