Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize
By Huizhen Yu. 2015
31 citations recorded by the source corpus.
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.
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
- Huizhen Yu
- Dimitri P. Bertsekas
- A. Mahmood
- Richard S. Sutton
- Shangtong Zhang
- Assaf Hallak
- Matthieu Geist
- Martha White
Citations in the corpus
- Multi-step Off-policy Learning Without Importance Sampling Ratios (2017, methodology): “Equivalence for online updating could also be achieved by following the approach taken by van Seijen et al. (2014, 2016), but we leave that out for simplicity.”
- Online Off-policy Prediction (2018, unknown): “Several variants of Gradient and Emphatic-TD have asymptotic performance guarantees (Mahadevan et al., 2014; Yu 2015, 2016, and 2017), and most of the methods discussed above (besides Tree Backup, V-trace) achieve the slightly weaker standard of convergence in expectation.”