Multi-step Off-policy Learning Without Importance Sampling Ratios

By A. Mahmood, Huizhen Yu, Richard S. Sutton. 2017

56 citations recorded by the source corpus.

To estimate the value functions of policies from exploratory data, most model-free off-policy algorithms rely on importance sampling, where the use of importance sampling ratios often leads to estimates with severe variance. It is thus desirable to learn off-policy without using the ratios. However, such an algorithm does not exist for multi-step learning with function approximation. In this paper, we introduce the first such algorithm based on temporal-difference (TD) learning updates. We show that an explicit use of importance sampling ratios can be eliminated by varying the amount of bootstrapping in TD updates in an action-dependent manner. Our new algorithm achieves stability using a two-timescale gradient-based TD update. A prior algorithm based on lookup table representation called Tree Backup can also be retrieved using action-dependent bootstrapping, becoming a special case of our algorithm. In two challenging off-policy tasks, we demonstrate that our algorithm is stable, effectively avoids the large variance issue, and can perform substantially better than its state-of-the-art counterpart.

Subfields: Artificial Intelligence, 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 Artificial Intelligence

In Reinforcement Learning

Citations in the corpus

Addressing Function Approximation Error in Actor-Critic Methods (2018, methodology): “Methods with multi-step returns, which tradeoff environment and policy variance with accumulated estimation error and bias, have been shown to be an effective approach, through importance sampling (Munos et al., 2016; Mahmood et al., 2017), distributed methods (Mnih et al.”
Two-Timescale Networks for Nonlinear Value Function Approximation (2019, background): “Additionally, there have been a variety of algorithms derived for the linear setting, both for on-policy and off-policy learning (Sutton et al., 2009; Maei, 2011; van Seijen and Sutton, 2014; van Hasselt et al., 2014; Mahadevan et al., 2014; Sutton et al., 2016; Mahmood et al., 2017).”
Evolution-Guided Policy Gradient in Reinforcement Learning (2018, background): “Offpolicy multi-step learning [34, 48] have been demonstrated to be stable in recent works but require complementary correction mechanisms like importance sampling, Retrace [37, 59] and V-trace [14] which can be computationally expensive and limiting.”
Incremental Off-policy Reinforcement Learning Algorithms (2017, background): “McCloskey and Cohen (1989) demonstrated that after only a moderate amount of learning on the second task, the network forgets almost completely about the first task.”
Online Off-policy Prediction (2018, background): “For explicit theoretical results, see Mahmood et al. (2017) for ABQ with gradient correction and Touati et al. (2018) for convergent versions of Retrace and Tree Backup.”
Convergent Tree-Backup and Retrace with Function Approximation (2017, methodology): “Our experiments ﬁ-nally suggest that the proposed GTB( λ ) and GR ETRACE ( λ ) are robust to step-size selection and have less variance than both GQ( λ ) (Maei, 2011) and AB-T RACE ( λ ) (Mahmood et al., 2017).”