Generalized Emphatic Temporal Difference Learning: Bias-Variance Analysis

By Assaf Hallak, Aviv Tamar, R´emi Munos, Shie Mannor. 2015

61 citations recorded by the source corpus.

We consider the off-policy evaluation problem in Markov decision processes with function approximation. We propose a generalization of the recently introduced emphatic temporal differences (ETD) algorithm, which encompasses the original ETD(λ), as well as several other off-policy evaluation algorithms as special cases. We call this framework ETD(λ, β), where our introduced parameter β controls the decay rate of an importance-sampling term. We study conditions under which the projected fixed-point equation underlying ETD(λ, β) involves a contraction operator, allowing us to present the first asymptotic error bounds (bias) for ETD(λ, β). Our results show that the original ETD algorithm always involves a contraction operator, and its bias is bounded. Moreover, by controlling β, our proposed generalization allows trading-off bias for variance reduction, thereby achieving a lower total error.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Control and Systems Engineering, 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 Computational Theory and Mathematics

In Control and Systems Engineering

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).”
Accelerating Online Reinforcement Learning with Offline Datasets (2020, methodology): “due to error accumulation with distribution shift [8, 21]. Ofﬂine RL methods aim to address this issue, often by constraining the actor updates to avoid excessive deviation from the data distribution [23, 41, 13, 14, 12, 21, 8, 22, 38, 26, 47]. One class of these methods utilize importance sampling ”
Generalized Off-Policy Actor-Critic (2019, background): “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.”
Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation (2018, background): “Our off-policy setting is related to, but different from, off-policy value-function learning [12, 21, 25, 29, 30, 37].”
Consistent On-Line Off-Policy Evaluation (2017, methodology): “Their algorithm was later on extended by Hallak et al. (2015) and renamed ETD(λ, β), which was shown to perform extremely well empirically by White & White (2016).”
An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning (2015, background): “Asymptotic bounds on the error of emphatic TD(λ) have been obtained by Hallak et al. (2015). Two additional ideas for future work deserve special mention. First, note that the present work has focused on ways of ensuring that the key matrix is positive definite, which implies positive definiteness o”
Q(λ) with Off-Policy Corrections (2016, background): “There are several (recent) off-policy algorithms that reduce the variance of IS methods, at the cost of added bias [5, 6, 3].”
Unifying Task Specification in Reinforcement Learning (2016, methodology): “For example, ETD was introduced with state-based γ s ; however, (Hallak et al., 2015) analyzed approximation error bounds of ETD using a constant discount γ c .”
Investigating Practical Linear Temporal Difference Learning (2016, methodology): “[7] introduced a variant ETD that utilizes a scaling parameter β, which is meant to reduce the magnitude of the follow-on trace.”
Provably Convergent Off-Policy Actor-Critic with Function Approximation (2019, methodology): “ETD(0) is the simplest emphatic algorithm and is a special case of ETD(λ, β) (Hallak et al., 2016), where λ and β are used for bias-variance trade-off.”
Q( λ ) with Oﬀ-Policy Corrections (background): “There are several (recent) oﬀ-policy algorithms that reduce the variance of IS methods, at the cost of added bias [5, 6, 3].”
Provably Convergent Two-Timescale Off-Policy Actor-Critic with Function Approximation (2019, methodology): “ETD(0) is a special case of ETD( λ, β ) (Hallak et al., 2016), where λ and β are used for bias-variance trade-off.”
Multi-step Off-policy Learning Without Importance Sampling Ratios (2017, methodology): “Due to performing model estimation in addition to value function estimation, these algorithms tend to be computationally more complex (Dud´ık et al. 2011, Paduraru 2013, Hallak et al. 2015b, Li et al. 2015, Jiang & Li 2015, Thomas & Brunskill 2016).”
Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize (2015, background): “[15], when the parameter β is set in an appropriate range.”
Using Options and Covariance Testing for Long Horizon Off-Policy Policy Evaluation (2017, background): “Other recent efforts that estimate a value function using off-policy data rather than just the performance of a policy [6, 11, 19] also suffer from bias if the input state description is not Markovian (such as if the domain description induces partial observability).”
Safe and Efficient Off-Policy Reinforcement Learning (2016, methodology): “It is well known that IS estimates can suffer from large – even possibly infinite – variance (mainly due to the variance of the product π(a1|x1) μ(a1|x1) · · · π(at|xt) μ(at|xt) ), which has motivated further variance reduction techniques such as in (Mahmood and Sutton, 2015; Mahmood et al., 2015; H”