Multi-step Off-policy Learning Without Importance Sampling Ratios

Abstract

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.

24 pages, 4 figures

References in corpus (6)

• Doubly Robust Policy Evaluation and Learning
• Doubly Robust Off-policy Value Evaluation for Reinforcement Learning
• Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning
• On Convergence of Emphatic Temporal-Difference Learning
• Weak Convergence Properties of Constrained Emphatic Temporal-difference Learning with Constant and Slowly Diminishing Stepsize
• Adaptive Lambda Least-Squares Temporal Difference Learning

Cited by in corpus (12)

• On Convergence of some Gradient-based Temporal-Differences Algorithms for Off-Policy Learning
• Policy Certificates: Towards Accountable Reinforcement Learning
• Online Off-policy Prediction
• Self-Imitation Learning via Generalized Lower Bound Q-learning
• Adaptive Trade-Offs in Off-Policy Learning
• Importance Resampling for Off-policy Prediction
• A Generalized Projected Bellman Error for Off-policy Value Estimation in Reinforcement Learning
• Importance Sampling based Exploration in Q Learning
• On Generalized Bellman Equations and Temporal-Difference Learning
• An Empirical Comparison of Off-policy Prediction Learning Algorithms on the Collision Task
• Expected Sarsa($\lambda$) with Control Variate for Variance Reduction
• An Empirical Comparison of Off-policy Prediction Learning Algorithms in the Four Rooms Environment