PER-ETD: A Polynomially Efficient Emphatic Temporal Difference Learning Method
arXiv:2110.06906
Abstract
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.
Published as a conference paper at ICLR 2022
References in corpus (10)
- Deep Reinforcement Learning and the Deadly Triad
- On Convergence of Emphatic Temporal-Difference Learning
- GenDICE: Generalized Offline Estimation of Stationary Values
- Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samples
- Finite Sample Analysis of Two-Timescale Stochastic Approximation with Applications to Reinforcement Learning
- Finite Sample Analysis of the GTD Policy Evaluation Algorithms in Markov Setting
- Emphatic Temporal-Difference Learning
- Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learning
- A First Empirical Study of Emphatic Temporal Difference Learning
- Truncated Emphatic Temporal Difference Methods for Prediction and Control