Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize

Abstract

We consider the emphatic temporal-difference (TD) algorithm, ETD($\lambda$), for learning the value functions of stationary policies in a discounted, finite state and action Markov decision process. The ETD($\lambda$) algorithm was recently proposed by Sutton, Mahmood, and White to solve a long-standing divergence problem of the standard TD algorithm when it is applied to off-policy training, where data from an exploratory policy are used to evaluate other policies of interest. The almost sure convergence of ETD($\lambda$) has been proved in our recent work under general off-policy training conditions, but for a narrow range of diminishing stepsize. In this paper we present convergence results for constrained versions of ETD($\lambda$) with constant stepsize and with diminishing stepsize from a broad range. Our results characterize the asymptotic behavior of the trajectory of iterates produced by those algorithms, and are derived by combining key properties of ETD($\lambda$) with powerful convergence theorems from the weak convergence methods in stochastic approximation theory. For the case of constant stepsize, in addition to analyzing the behavior of the algorithms in the limit as the stepsize parameter approaches zero, we also analyze their behavior for a fixed stepsize and bound the deviations of their averaged iterates from the desired solution. These results are obtained by exploiting the weak Feller property of the Markov chains associated with the algorithms, and by using ergodic theorems for weak Feller Markov chains, in conjunction with the convergence results we get from the weak convergence methods. Besides ETD($\lambda$), our analysis also applies to the off-policy TD($\lambda$) algorithm, when the divergence issue is avoided by setting $\lambda$ sufficiently large.

Minor edits; 53 pages. Longer and more proof details than the journal version

References in corpus (5)

• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces
• Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize
• Emphatic Temporal-Difference Learning
• Some Simulation Results for Emphatic Temporal-Difference Learning Algorithms

Cited by in corpus (8)

• Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize
• On Convergence of some Gradient-based Temporal-Differences Algorithms for Off-Policy Learning
• Multi-step Off-policy Learning Without Importance Sampling Ratios
• Online Off-policy Prediction
• Some Simulation Results for Emphatic Temporal-Difference Learning Algorithms
• O${}^2$TD: (Near)-Optimal Off-Policy TD Learning
• On Generalized Bellman Equations and Temporal-Difference Learning
• On a convergent off -policy temporal difference learning algorithm in on-line learning environment