Finite Sample Analysis of the GTD Policy Evaluation Algorithms in Markov Setting

Yue Wang, Wei Chen, Yuting Liu, Zhi-Ming Ma, Tie-Yan Liu

Abstract

Policy evaluation is a cornerstone of reinforcement learning (RL), yet its theoretical foundations often rely on the unrealistic assumption of independent and identically distributed (i.i.d.) data. In practice, RL data is generated by Markov processes, introducing temporal dependencies that complicate convergence analysis. This paper provides the first finite sample analysis for Gradient-based Temporal Difference (GTD) algorithms in a realistic Markovian setting. By reframing GTD as a stochastic convex-concave saddle point problem, we derive convergence bounds that explicitly incorporate the environment's "mixing time." Our results offer a theoretical justification for the effectiveness of experience replay and demonstrate convergence across various step-size regimes.

The Gap Between Theory and Practice

In RL, estimating the value function—the expected long-term reward of a policy—is critical for finding optimal strategies. For large or continuous state spaces, GTD algorithms with linear function approximation are the standard choice due to their computational efficiency.

However, a significant gap has existed between theoretical proofs and practical application. Most existing finite sample analyses for GTD assume i.i.d. data. In reality, an agent’s state at time $t+1$ is highly dependent on its state at time $t$. This Markovian nature breaks standard i.i.d. proofs, leaving practitioners without a clear understanding of how many samples are required for convergence or how environment dynamics affect learning speed.

Theoretical Framework: Mixing Time and Saddle Points

The authors bridge this gap by treating GTD as a stochastic convex-concave saddle point problem. To handle Markovian dependencies, they introduced several key innovations:

  1. Mixing Time ($\tau$): They incorporated the time it takes for a Markov process to settle into its long-term distribution.
  2. Error Decomposition: A novel method to separate Markovian "noise" from the true gradient signal.
  3. Auxiliary Variables: Sequences designed to bridge biased Markovian gradients with the unbiased requirements of optimization theory.
  4. High-Probability Bounds: Using Azuma’s inequality to provide performance guarantees that hold with high confidence.

Key Insights: The "Mixing Time Tax"

The analysis reveals that the convergence rate is directly tied to the environment's mixing time. If an environment "mixes" slowly—meaning it takes a long time to explore diverse states—the algorithm requires significantly more samples. The derived convergence rate is approximately $O\left(\sqrt{\frac{\tau(\eta) \log(1/\delta)}{T}}\right)$, where $T$ is the number of samples and $\delta$ is the confidence level.

Figure (b): Convergence of GTD with $\alpha_t = \mathcal{O}(1/\sqrt{t})$ across different mixing times. Larger mixing times ($\tau$) significantly slow down convergence compared to the i.i.d. baseline.

Why Experience Replay Works

A major contribution of this work is the theoretical explanation for experience replay. By storing transitions and sampling them uniformly, the "trick" effectively forces the mixing time of the training data toward zero. This transforms a difficult Markovian learning problem into a simpler i.i.d.-like problem.

Figure (e): Convergence with the experience replay "trick" for $\alpha_t = \mathcal{O}(1/\sqrt{t})$. The trick mitigates the impact of mixing time, bringing Markovian performance closer to the i.i.d. ideal.

Empirical Validation

The authors validated their derivations using synthetic MCMC simulations. They tested two Markov chains with identical stationary distributions but different mixing times. The results confirmed their theoretical upper bounds: data with smaller mixing times converged faster, and the experience replay trick consistently improved performance by reducing the dependency on environment dynamics.

Conclusion and Future Directions

This work provides a foundational theoretical understanding of GTD algorithms in realistic settings. While currently limited to linear function approximation, the authors suggest that "localization techniques" could extend these results to non-linear neural networks. Future research may also focus on tightening these upper bounds to better reflect the peak performance observed in practice.

Summary updated

Abstract

In reinforcement learning (RL) , one of the key components is policy evaluation, which aims to estimate the value function (i.e., expected long-term accumulated reward) of a policy. With a good policy evaluation method, the RL algorithms will estimate the value function more accurately and find a better policy. When the state space is large or continuous \emph{Gradient-based Temporal Difference(GTD)} policy evaluation algorithms with linear function approximation are widely used. Considering that the collection of the evaluation data is both time and reward consuming, a clear understanding of the finite sample performance of the policy evaluation algorithms is very important to reinforcement learning. Under the assumption that data are i.i.d. generated, previous work provided the finite sample analysis of the GTD algorithms with constant step size by converting them into convex-concave saddle point problems. However, it is well-known that, the data are generated from Markov processes rather than i.i.d. in RL problems.. In this paper, in the realistic Markov setting, we derive the finite sample bounds for the general convex-concave saddle point problems, and hence for the GTD algorithms. We have the following discussions based on our bounds. (1) With variants of step size, GTD algorithms converge. (2) The convergence rate is determined by the step size, with the mixing time of the Markov process as the coefficient. The faster the Markov processes mix, the faster the convergence. (3) We explain that the experience replay trick is effective by improving the mixing property of the Markov process. To the best of our knowledge, our analysis is the first to provide finite sample bounds for the GTD algorithms in Markov setting.
BibTeX
@inproceedings{wang2017finite,
  author = {Yue Wang and Wei Chen and Yuting Liu and Zhi-Ming Ma and Tie-Yan Liu},
  title = {{Finite Sample Analysis of the GTD Policy Evaluation Algorithms in Markov Setting}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=Hy4X-t-OZH},
}
Figure