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

arXiv: https://arxiv.org/abs/1809.08926 · HTML: https://mlsanity.com/paper/1809.08926/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Sep 2018.

## Built on by (most cited first, 12 of 12)

- [Learning to Optimize Multi-Objective Alignment Through Dynamic Reward Weighting](https://mlsanity.com/paper/2509.11452/) (2025)
- [Tight Finite Time Bounds of Two-Time-Scale Linear Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2401.00364/) (2023)
- [Non-Asymptotic Analysis for Two Time-scale TDC with General Smooth Function Approximation](https://mlsanity.com/paper/2104.02836/) (2021)
- [Greedy-GQ with Variance Reduction: Finite-time Analysis and Improved Complexity](https://mlsanity.com/paper/2103.16377/) (2021)
- [Revisiting a Design Choice in Gradient Temporal Difference Learning](https://mlsanity.com/paper/2308.01170/) (2023)
- [Finite-Time Error Bounds for Greedy-GQ](https://mlsanity.com/paper/2209.02555/) (2022)
- [PER-ETD: A Polynomially Efficient Emphatic Temporal Difference Learning Method](https://mlsanity.com/paper/2110.06906/) (2021)
- [Stochastic Gradient Descent with Dependent Data for Offline Reinforcement Learning](https://mlsanity.com/paper/2202.02850/) (2022)
- [APEX: Learning Adaptive Priorities for Multi-Objective Alignment in Vision-Language Generation](https://mlsanity.com/paper/2601.06574/) (2026)
- [Almost Sure Convergence of Differential Temporal Difference Learning for Average Reward Markov Decision Processes](https://mlsanity.com/paper/2602.16629/) (2026)
- [Finite-Time Error Bounds for Distributed Linear Stochastic Approximation](https://mlsanity.com/paper/2111.12665/) (2021)
- [STOPS: Short-Term-based Volatility-controlled Policy Search and its Global Convergence](https://mlsanity.com/paper/2201.09857/) (2022)

## Abstract (arXiv)

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 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.