On Convergence of Emphatic Temporal-Difference Learning

Abstract

We consider emphatic temporal-difference learning algorithms for policy evaluation in discounted Markov decision processes with finite spaces. Such algorithms were recently proposed by Sutton, Mahmood, and White (2015) as an improved solution to the problem of divergence of off-policy temporal-difference learning with linear function approximation. We present in this paper the first convergence proofs for two emphatic algorithms, ETD($\lambda$) and ELSTD($\lambda$). We prove, under general off-policy conditions, the convergence in $L^1$ for ELSTD($\lambda$) iterates, and the almost sure convergence of the approximate value functions calculated by both algorithms using a single infinitely long trajectory. Our analysis involves new techniques with applications beyond emphatic algorithms leading, for example, to the first proof that standard TD($\lambda$) also converges under off-policy training for $\lambda$ sufficiently large.

A minor correction is made (see page 1 for details). 45 pages. A shorter 28-page article based on the first version appeared at the 28th Annual Conference on Learning Theory (COLT), 2015

References in corpus (2)

• Emphatic Temporal-Difference Learning
• An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning

Cited by in corpus (17)

• Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems
• Multi-step Off-policy Learning Without Importance Sampling Ratios
• Unifying task specification in reinforcement learning
• Generalized Emphatic Temporal Difference Learning: Bias-Variance Analysis
• Online Off-policy Prediction
• A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learning
• Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation
• Generalized Off-Policy Actor-Critic
• An Off-policy Policy Gradient Theorem Using Emphatic Weightings
• Truncated Emphatic Temporal Difference Methods for Prediction and Control
• Learning Retrospective Knowledge with Reverse Reinforcement Learning
• PER-ETD: A Polynomially Efficient Emphatic Temporal Difference Learning Method
• Emphatic TD Bellman Operator is a Contraction
• Off-Policy Actor-Critic with Emphatic Weightings
• On Generalized Bellman Equations and Temporal-Difference Learning
• Expected Sarsa($\lambda$) with Control Variate for Variance Reduction
• Stable and Efficient Policy Evaluation