Convergent Tree-Backup and Retrace with Function Approximation

By Ahmed Touati, Pierre-Luc Bacon, Doina Precup, Pascal Vincent. 2017

42 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Management Science and Operations Research

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 Management Science and Operations Research

Citations in the corpus

Maximum a Posteriori Policy Optimisation (2018, background): “(2)We note that, despite this empirical finding, Retrace may not be guaranteed to be stable with function approximation (Touati et al., 2017).”
Ranking Policy Gradient (2019, methodology): “It has been found that the estimation step using Retrace (Munos et al., 2016) can be unstable even with a linear function approximation (Touati et al., 2017).”
A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation (2018, methodology): “Instead, many papers have studied such algorithms under the simpler i.i.d noise model mentioned earlier [Sutton et al., 2009b,a, Liu et al., 2015, Touati et al., 2018, Dalal et al., 2018b, Lakshminarayanan and Szepesv´ari, 2018].”