Off-policy learning with eligibility traces: a survey

By Matthieu Geist, Bruno Scherrer. 2013

100 citations recorded by the source corpus.

In the framework of Markov Decision Processes, we consider linear off-policy learning, that is the problem of learning a linear approximation of the value function of some fixed policy from one trajectory possibly generated by some other policy. We briefly review on-policy learning algorithms of the literature (gradient-based and least-squares-based), adopting a unified algorithmic view. Then, we highlight a systematic approach for adapting them to off-policy learning with eligibility traces. This leads to some known algorithms-- off-policy LSTD(λ), LSPE(λ), TD(λ), TDC/GQ(λ)--and suggests new extensions--off-policy FPKF(λ), BRM(λ), gBRM(λ), GTD2(λ). We describe a comprehensive algorithmic derivation of all algorithms in a recursive and memory-efficent form, discuss their known convergence properties and illustrate their relative empirical behavior on Garnet problems. Our experiments suggest that the most standard algorithms on and off-policy LSTD(λ)/LSPE(λ)--and TD(λ) if the feature space dimension is too large for a least-squares approach--perform the best.

Subfields: Environmental Engineering, Statistics and Probability, Reinforcement Learning

How researchers see this paper

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

In Environmental Engineering

In Statistics and Probability

In Reinforcement Learning

Citations in the corpus

IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures (2018, methodology): “Related previous work on off-policy RL include (Precup et al., 2000; 2001; Wawrzynski, 2009; Geist & Scherrer, 2014) and (Harutyunyan et al., 2016).”
Safe and Efficient Off-Policy Reinforcement Learning (2016, background): “Importance sampling is the simplest way to correct for the discrepancy between μ and π when learning from off-policy returns (Precup et al., 2000, 2001; Geist and Scherrer, 2014).”
AlgaeDICE: Policy Gradient from Arbitrary Experience (2019, methodology): “One common method is to re-weight off-policy samples by considering eligibility traces (Precup et al., 2000; Geist and Scherrer, 2014), i.e., compute weights by taking the product of per-action importance weights over a trajectory.”
More Robust Doubly Robust Off-policy Evaluation (2018, methodology): “…in Gruslys et al. 2017), where one can view the gradient estimation part as an off-policy value evaluation problem, the DM state-action value function model is learned by minimizing the Bellman residual in an off-policy setting (Precup et al., 2000b; Munos et al., 2016; Geist & Scherrer, 2014).”
On Convergence of Emphatic Temporal-Difference Learning (2015, background): “See e.g., (Maei, 2011; Bertsekas and Yu, 2009; Geist and Scherrer, 2014; Dann et al., 2014).”
An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning (2015, background): “The studies by White (in preparation), Geist and Scherrer (2014), and Dann, Neumann, and Peters (2014) represent our best experience with gradient-TD and related methods.”
Online Off-policy Prediction (2018, methodology): “Prior studies have provided useful insights into some of these methods (Dann et al., 2014; Geist & Scherrer, 2014; White & White, 2016).”
Off-policy learning based on weighted importance sampling with linear computational complexity (2015, methodology): “A Monte Carlo technique known as importance sampling (Kahn & Marshall 1953, Rubinstein 1981) is often used to resolve this mismatch in policies (Sutton & Barto 1998, Dann, Neumann & Peters 2014, Geist & Scherrer 2014).”
Incremental Off-policy Reinforcement Learning Algorithms (2017, background): “The former approach is known as the residual approach whereas the latter is known as the projected fixed point approach (Geist and Scherrer 2014).”
Multi-step Off-policy Learning Without Importance Sampling Ratios (2017, background): “A number of computationally scalable algorithms have been proposed that can learn oﬀ-policy without requiring to access or estimate the model of the environment and in that sense are model-free (Precup et al. 2000, 2001, Maei & Sutton 2010, Maei 2011, Yu 2012, Geist & Scherrer 2014, Dann et al. 2014”
Approximate modified policy iteration and its application to the game of Tetris (2015, methodology): “…we have is a set of trajectories of size m generated by a behavior policy π b that is assumed to choose all actions a in each state s with a positive probability (i.e., π b (a|s) > Scherrer, Ghavamzadeh, Gabillon, Lesner and Geist 0, ∀s, ∀a) (Precup et al., 2000, 2001; Geist and Scherrer, 2014).”
Encouraging Physical Activity in Patients With Diabetes: Intervention Using a Reinforcement Learning System (2016, unknown): “This leads to several problems such as large variance and bias since exploration cannot be done where it matters most [11].”
Exponentially Weighted Imitation Learning for Batched Historical Data (2018, methodology): “We note that the explicit value π(at|st) is crucial for the correction used by most off-policy policy iteration methods [Sutton and Barto, 1998], including [Munos et al., 2016, Wang et al., 2016, Schulman et al., 2017, Wu et al., 2017] and many other works [Geist and Scherrer, 2014].”
Weighted importance sampling for off-policy learning with linear function approximation (2014, methodology): “The existing methods for off-policy value-function approximation either use OIS (Maei & Sutton 2010, Yu 2010, Sutton et al. 2014, Geist & Scherrer 2014, Dann et al. 2014) or use WIS but are limited to the tabular or non-parametric case (Precup et al. 2000, Shelton 2001).”
Policy evaluation with temporal differences: a survey and comparison (2015, methodology): “As FPKF is a second order method, it typically converges with fewer iterations than TD but comes with additional price of estimating H−1t .”
Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize (2015, background): “(See the surveys [13, 10] for other algorithm examples.”