Technical Summary: Statistical Inference for Policy Evaluation with Temporal Difference Learning

Problem Statement

The paper addresses the challenge of performing rigorous statistical inference for the parameters of the optimal linear approximation to the value function in Reinforcement Learning (RL). Specifically, it focuses on Temporal Difference (TD) learning with Polyak-Ruppert averaging, a widely used algorithm for policy evaluation.

While previous work has established finite-sample consistency rates and asymptotic Gaussian convergence for TD learning, these results often lack quantitative guarantees necessary for practical statistical inference (e.g., constructing confidence intervals or hypothesis testing). Existing Central Limit Theorem (CLT) results are typically asymptotic, holding only in fixed dimensions as the sample size goes to infinity, and do not explicitly capture dependencies on the dimensionality $d$ or the sample size $T$. Furthermore, existing methods for estimating the asymptotic covariance matrix often suffer from high computational complexity or lack finite-sample error bounds.

The authors investigate the statistical properties of TD learning under the assumption of independent and identically distributed (i.i.d.) samples, aiming to bridge the gap between theoretical consistency and practical, finite-sample statistical inference in high-dimensional settings.

Methodology

The paper employs a combination of high-dimensional probability theory, stochastic approximation analysis, and online estimation techniques.

1. Algorithm Setup: The study considers the TD learning update rule with Polyak-Ruppert averaging:
   $$\theta_t = \theta_{t-1} - \eta_t (A_t \theta_{t-1} - b_t)$$
   $$\bar{\theta}_T = \frac{1}{T} \sum_{t=1}^T \theta_t$$
   where $\{ (s_t, a_t, s'_t, r_t) \}$ are i.i.d. samples, $A_t$ and $b_t$ are the instantaneous matrices and vectors derived from the Bellman equation, and $\eta_t = \eta_0 t^{-\alpha}$ is a polynomially decaying stepsize with $\alpha \in (1/2, 1)$.

2. High-Dimensional Berry-Esseen Bounds: The authors derive non-asymptotic bounds on the convex distance between the distribution of the scaled estimation error $\sqrt{T}(\bar{\theta}_T - \theta^*)$ and a Gaussian distribution. They utilize general non-linear Berry-Esseen bounds (Shao & Zhang, 2022) but refine the analysis specifically for the structure of TD learning matrices ($A_t$ and $A$) to achieve tighter rates.

3. Online Variance Estimation: A novel, computationally efficient online plug-in estimator $\hat{\Lambda}_T$ for the asymptotic covariance matrix $\Lambda^*$ is proposed. This estimator updates recursively without storing the full trajectory of samples, utilizing weights that increase with the iteration count to reflect the improving accuracy of $\theta_t$.

4. High-Probability Convergence: The paper derives high-probability bounds for the Euclidean norm of the estimation error, explicitly depending on the trace of the asymptotic variance and the dimensionality, without requiring projection steps to control the trajectory.

Key Contributions

1. Sharper High-Dimensional Berry-Esseen Bounds

The authors establish a new Berry-Esseen bound over the class of convex sets for the TD estimation error.

• Rate: They achieve a convergence rate of $O(T^{-1/3})$ by selecting the stepsize decay parameter $\alpha = 2/3$.
• Improvement: This improves upon the best-known rate of $O(T^{-1/4})$ derived by Samsonov et al. (2024a) for similar settings. The improvement is achieved through a more targeted decomposition of the TD error and refined handling of specific matrix terms arising from the TD update structure.
• Variance Estimation: The bound holds even when the true asymptotic variance is replaced by the proposed online estimator, with the total variation distance between the estimated and true Gaussian distributions vanishing at the same $O(T^{-1/3})$ rate.

2. Novel Online Covariance Estimator

The paper proposes a computationally efficient online algorithm to estimate the asymptotic covariance matrix $\Lambda^*$.

• Complexity: The estimator requires $O(Td^2 + d^3)$ time and $O(d^2)$ space, avoiding the need to store the entire sample trajectory (unlike bootstrap methods which may require $O(T)$ space and $O(T^{3/2})$ time).
• Accuracy: The estimator $\hat{\Lambda}_T$ converges to $\Lambda^*$ such that the Total Variation (TV) distance between $N(0, \hat{\Lambda}_T)$ and $N(0, \Lambda^*)$ vanishes at rate $O(T^{-1/3})$. This ensures that using the estimated variance for inference does not degrade the convergence rate.

3. Sharper High-Probability Convergence Guarantees

The authors derive high-probability bounds for the estimation error $\|\bar{\theta}_T - \theta^*\|_2$ that:

• Match the asymptotic variance up to logarithmic factors.
• Hold under weaker conditions than prior literature (e.g., no projection step required).
• Explicitly depend on the trace of the asymptotic variance matrix $\text{Tr}(\Lambda^*)$.
• Note: The initial stepsize $\eta_0$ must depend on the confidence level $\delta$ (specifically $\eta_0 \sqrt{\log(1/(\delta \eta_0))} \leq C$), a constraint shown to be necessary for Chernoff-style guarantees in this setting.

4. Finite-Sample Statistical Inference

Combining the refined Berry-Esseen bounds and the online variance estimator, the paper constructs:

• Confidence Regions: Convex sets (e.g., ellipsoids) for $\theta^*$.
• Simultaneous Confidence Intervals: Hyper-rectangles for individual components of $\theta^*$.
• Guarantee: These regions provide guaranteed finite-sample coverage that converges to the target level $1-\delta$ at a rate of $O(T^{-1/3})$. To the authors' knowledge, this is the first procedure for formal statistical inference on TD model parameters with such finite-sample coverage guarantees.

Results

The theoretical findings are corroborated by numerical experiments on a family of MDPs designed to be difficult to distinguish.

• Convergence Rates: Simulations confirm that the choice of $\alpha = 2/3$ yields the fastest convergence for both the estimation error and the distributional approximation, outperforming $\alpha = 1/2$ (often used in prior work) and $\alpha = 1$.
• Distributional Approximation: The empirical distribution of the scaled error $\sqrt{T}\bar{\Delta}_T$ converges to the Gaussian limit $N(0, \Lambda^*)$ as predicted, with the distance decreasing at the theoretical rate.
• Coverage: The constructed confidence intervals achieve the target 95% coverage rate as $T$ increases, validating the finite-sample inference framework.
• Error Decomposition: Experiments decompose the error into initialization, sampling, and iterative components, showing that the sampling error dominates asymptotically and aligns with the derived variance.

Significance and Claims

The paper claims to provide the sharpest known theoretical rates for the statistical inference of TD learning with Polyak-Ruppert averaging under i.i.d. assumptions. Its primary significance lies in:

1. Bridging Theory and Practice: It moves beyond asymptotic justifications to provide finite-sample, non-asymptotic guarantees for constructing confidence intervals, a critical requirement for reliable policy evaluation in safety-critical or high-stakes applications.
2. Computational Efficiency: By introducing an online variance estimator that avoids the high computational and memory costs of bootstrap methods, the proposed methodology is practically scalable to high-dimensional problems.
3. Optimality of Rates: The $O(T^{-1/3})$ rate for the Berry-Esseen bound and the matching rate for the variance estimator represent a state-of-the-art improvement over existing literature, with the authors noting that this rate appears tight for the chosen stepsize schedule.

The authors acknowledge that their results are derived under the i.i.d. assumption, which simplifies the analysis compared to the more challenging Markovian data setting, but argue that this simplified scenario is a necessary and challenging theoretical step that provides state-of-the-art rates and insights for the broader field.