On Convergence of Emphatic Temporal-Difference Learning

By Huizhen Yu. 2015

85 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research, Reinforcement Learning, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

In Reinforcement Learning

In Statistical Learning Theory

Citations in the corpus

Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (2020, methodology): “Only recently have practical methods for estimating the marginalized importance ratio been introduced (Sutton et al., 2016; Yu, 2015; Hallak et al., 2015, 2016; Hallak and Mannor, 2017; Nachum et al., 2019a; Zhang et al., 2020; Nachum et al., 2019b).”
Generalized Off-Policy Actor-Critic (2019, methodology): “Implementation: Although emphatic algorithms have enjoyed great theoretical success (Yu, 2015; Hallak et al., 2016; Sutton et al., 2016; Imani et al., 2018), their empirical success is still limited to simple domains (e.”
An Off-policy Policy Gradient Theorem Using Emphatic Weightings (2018, methodology): “For a ﬁxed policy π , and with the conditions on the MDP from [Yu, 2015], Proof.”
Consistent On-Line Off-Policy Evaluation (2017, neutral): “As mentioned before, ETD(λ, β) converges to the fixed point of ΠfT λ π (Yu, 2015), where f = E [Ft|st] = (I − βPπ) dμ.”
Emphatic TD Bellman Operator is a Contraction (2015, methodology): “Recently, Sutton et al. (2015) proposed theemphatic TD (ETD) algorithm: a modification of the TD idea that can be shown to converge off-policy (Yu, 2015).”
An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning (2015, background): “Demonstrations that the linear TD(λ) is not stable under off-policy training have been the focus of previous counterexamples (Baird 1995, Tsitsiklis & Van Roy 1996, 1997, see Sutton & Barto 1998).”
Emphatic Temporal-Difference Learning (2015, background): “These extensions are based on both our understanding of how the weighting scheme (10)-(13) is designed (Sutton et al. 2015) and the special structure of the matrix M(I − Pλπ) revealed in the proof of (Yu 2015, Prop.”
Multi-step Off-policy Learning Without Importance Sampling Ratios (2017, methodology): “The convergence of this algorithm can be analyzed similarly to the work by Karmakar and Bhatnagar (2015) for diminishing step sizes and Yu (2015) for constant step sizes, by using properties of the eligibility traces and stochastic approximation theory.”
Provably Convergent Off-Policy Actor-Critic with Function Approximation (2019, methodology): “, νt, converges (Yu, 2015) and we bootstrap via this approximation.”
A review of cooperative multi-agent deep reinforcement learning (2019, methodology): “Following the analysis provided for ET D ( λ ) in [160], the authors proved the convergence of the proposed method for the distributed actor-critic method when linear function approximation is utilized.”
Investigating Practical Linear Temporal Difference Learning (2016, unknown): “They derive the Emphatic TD (ETD) algorithm that surprisingly achieves convergence [27] without the need for a second set of weights, like those used by gradient TD methods.”
Two-Timescale Networks for Nonlinear Value Function Approximation (2019, methodology): “These linear methods have also been well-explored theoretically (Tsitsiklis and Van Roy, 1997; Maei, 2011; Mahmood and Sutton, 2015; Yu, 2015) and empirically (Dann et al., 2014; White and White, 2016), with some insights into improvements from gradient methods (Sutton et al., 2009), true-online…”
A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learning (2019, methodology): “In the following description, we rely heavily on [27].”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “By incorporating the analysis of ETD(λ) (Yu, 2015) into Zhang et al.”
True Online Emphatic TD(λ): Quick Reference and Implementation Guide (2015, background): “The emphasis idea is to dynamically rescale the updates made by temporaldifference algorithms such that convergence is ensured under off-policy training (Yu 2015) and such that asymptotic accuracy of the approximation is improved.”