# Convergent Tree Backup and Retrace with Function Approximation

arXiv: https://arxiv.org/abs/1705.09322 · HTML: https://mlsanity.com/paper/1705.09322/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 May 2017.

## Built on by (most cited first, 11 of 11)

- [Generalizable Episodic Memory for Deep Reinforcement Learning](https://mlsanity.com/paper/2103.06469/) (2021)
- [Truncated Emphatic Temporal Difference Methods for Prediction and Control](https://mlsanity.com/paper/2108.05338/) (2021)
- [Convergent and Efficient Deep Q Network Algorithm](https://mlsanity.com/paper/2106.15419/) (2021)
- [Trajectory-Aware Eligibility Traces for Off-Policy Reinforcement Learning](https://mlsanity.com/paper/2301.11321/) (2023)
- [An Improved Finite-time Analysis of Temporal Difference Learning with Deep Neural Networks](https://mlsanity.com/paper/2405.04017/) (2024)
- [An Empirical Comparison of Off-policy Prediction Learning Algorithms in the Four Rooms Environment](https://mlsanity.com/paper/2109.05110/) (2021)
- [An Empirical Comparison of Off-policy Prediction Learning Algorithms on the Collision Task](https://mlsanity.com/paper/2106.00922/) (2021)
- [Importance Sampling Placement in Off-Policy Temporal-Difference Methods](https://mlsanity.com/paper/2203.10172/) (2022)
- [Graph Backup: Data Efficient Backup Exploiting Markovian Transitions](https://mlsanity.com/paper/2205.15824/) (2022)
- [Closing the gap between SVRG and TD-SVRG with Gradient Splitting](https://mlsanity.com/paper/2211.16237/) (2022)
- [Control of Continuous Quantum Systems with Many Degrees of Freedom based on Convergent Reinforcement Learning](https://mlsanity.com/paper/2212.10705/) (2022)

## Abstract (arXiv)

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 textscTree Backup and textscRetrace 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 textscTree Backup and textscRetrace and allows us to provide new convergence rates for the GTD and GTD2 algorithms without having recourse to projections or Polyak averaging.