Convergent Tree Backup and Retrace with Function Approximation

Abstract

Off-policy learning is key to scaling up reinforcement learning as it allows to learn about a target policy from the experience generated by a different behavior policy. Unfortunately, it has been challenging to combine off-policy learning with function approximation and multi-step bootstrapping in a way that leads to both stable and efficient algorithms. In this work, we show that the \textsc{Tree Backup} and \textsc{Retrace} algorithms are unstable with linear function approximation, both in theory and in practice with specific examples. Based on our analysis, we then derive stable and efficient gradient-based algorithms using a quadratic convex-concave saddle-point formulation. By exploiting the problem structure proper to these algorithms, we are able to provide convergence guarantees and finite-sample bounds. The applicability of our new analysis also goes beyond \textsc{Tree Backup} and \textsc{Retrace} and allows us to provide new convergence rates for the GTD and GTD2 algorithms without having recourse to projections or Polyak averaging.

Cited by in corpus (15)

• Maximum a Posteriori Policy Optimisation
• Generalizable Episodic Memory for Deep Reinforcement Learning
• Online Off-policy Prediction
• Neural Temporal-Difference and Q-Learning Provably Converge to Global Optima
• Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization
• Convergent and Efficient Deep Q Network Algorithm
• A Generalized Projected Bellman Error for Off-policy Value Estimation in Reinforcement Learning
• SVRG for Policy Evaluation with Fewer Gradient Evaluations
• Gradient Q$(\sigma ,\lambda )$: A Unified Algorithm with Function Approximation for Reinforcement Learning
• On Convergence of Gradient Expected Sarsa($\lambda$)
• An Empirical Comparison of Off-policy Prediction Learning Algorithms in the Four Rooms Environment
• An Empirical Comparison of Off-policy Prediction Learning Algorithms on the Collision Task
• Sharp Analysis of Smoothed Bellman Error Embedding
• Ranking Policy Gradient
• Expected Sarsa($\lambda$) with Control Variate for Variance Reduction