# PER-ETD: A Polynomially Efficient Emphatic Temporal Difference Learning Method

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 36 references that are in the map.
- First posted on arXiv 13 Oct 2021.

## Builds on (most cited first, 19 of 19)

- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [Deep Reinforcement Learning and the Deadly Triad](https://mlsanity.com/paper/1812.02648/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [GenDICE: Generalized Offline Estimation of Stationary Values](https://mlsanity.com/paper/2002.09072/) (2020)
- [An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning](https://mlsanity.com/paper/1503.04269/) (2015)
- [Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noise](https://mlsanity.com/paper/2002.01268/) (2020)
- [Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning](https://mlsanity.com/paper/1907.06290/) (2019)
- [An Off-policy Policy Gradient Theorem Using Emphatic Weightings](https://mlsanity.com/paper/1811.09013/) (2018)
- [Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples](https://mlsanity.com/paper/1909.11907/) (2019)
- [Simple and optimal methods for stochastic variational inequalities, II: Markovian noise and policy evaluation in reinforcement learning](https://mlsanity.com/paper/2011.08434/) (2020)
- [On Convergence of Emphatic Temporal-Difference Learning](https://mlsanity.com/paper/1506.02582/) (2015)
- [Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithms](https://mlsanity.com/paper/2011.05053/) (2020)
- [Generalized Emphatic Temporal Difference Learning: Bias-Variance Analysis](https://mlsanity.com/paper/1509.05172/) (2015)
- [Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theory](https://mlsanity.com/paper/1906.06781/) (2019)
- [Emphatic Temporal-Difference Learning](https://mlsanity.com/paper/1507.01569/) (2015)
- [Finite Sample Analysis of the GTD Policy Evaluation Algorithms in Markov Setting](https://mlsanity.com/paper/1809.08926/) (2018)
- [Truncated Emphatic Temporal Difference Methods for Prediction and Control](https://mlsanity.com/paper/2108.05338/) (2021)
- [A First Empirical Study of Emphatic Temporal Difference Learning](https://mlsanity.com/paper/1705.04185/) (2017)
- [Learning Expected Emphatic Traces for Deep RL](https://mlsanity.com/paper/2107.05405/) (2021)

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

- [Regularized Centered Emphatic Temporal Difference Learning](https://mlsanity.com/paper/2605.04100/) (2026)
- [Regularized Emphatic Temporal-Difference Learning: Stability under Constant Stepsizes](https://mlsanity.com/paper/2609.19170/) (2026)

## Abstract (arXiv)

Emphatic temporal difference (ETD) learning (Sutton et al., 2016) is a successful method to conduct the off-policy value function evaluation with function approximation. Although ETD has been shown to converge asymptotically to a desirable value function, it is well-known that ETD often encounters a large variance so that its sample complexity can increase exponentially fast with the number of iterations. In this work, we propose a new ETD method, called PER-ETD (i.e., PEriodically Restarted-ETD), which restarts and updates the follow-on trace only for a finite period for each iteration of the evaluation parameter. Further, PER-ETD features a design of the logarithmical increase of the restart period with the number of iterations, which guarantees the best trade-off between the variance and bias and keeps both vanishing sublinearly. We show that PER-ETD converges to the same desirable fixed point as ETD, but improves the exponential sample complexity of ETD to be polynomials. Our experiments validate the superior performance of PER-ETD and its advantage over ETD.