# An Empirical Comparison of Off-policy Prediction Learning Algorithms in the Four Rooms Environment

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 36 references that are in the map.
- First posted on arXiv 10 Sep 2021.

## Builds on (most cited first, 15 of 15)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures](https://mlsanity.com/paper/1802.01561/) (2018)
- [Rainbow: Combining Improvements in Deep Reinforcement Learning](https://mlsanity.com/paper/1710.02298/) (2017)
- [Reinforcement Learning with Unsupervised Auxiliary Tasks](https://mlsanity.com/paper/1611.05397/) (2016)
- [An Emphatic Approach to the Problem of Off-policy Temporal-Difference Learning](https://mlsanity.com/paper/1503.04269/) (2015)
- [Finite-Sample Analysis of Proximal Gradient TD Algorithms](https://mlsanity.com/paper/2006.14364/) (2020)
- [Proximal Reinforcement Learning: A New Theory of Sequential Decision Making in Primal-Dual Spaces](https://mlsanity.com/paper/1405.6757/) (2014)
- [Multi-step Off-policy Learning Without Importance Sampling Ratios](https://mlsanity.com/paper/1702.03006/) (2017)
- [Generalized Emphatic Temporal Difference Learning: Bias-Variance Analysis](https://mlsanity.com/paper/1509.05172/) (2015)
- [Investigating practical linear temporal difference learning](https://mlsanity.com/paper/1602.08771/) (2016)
- [Off-policy Learning with Eligibility Traces: A Survey](https://mlsanity.com/paper/1304.3999/) (2013)
- [Emphatic Algorithms for Deep Reinforcement Learning](https://mlsanity.com/paper/2106.11779/) (2021)
- [Convergent Tree Backup and Retrace with Function Approximation](https://mlsanity.com/paper/1705.09322/) (2017)
- [An Empirical Comparison of Off-policy Prediction Learning Algorithms on the Collision Task](https://mlsanity.com/paper/2106.00922/) (2021)

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

- [Revisiting a Design Choice in Gradient Temporal Difference Learning](https://mlsanity.com/paper/2308.01170/) (2023)
- [Toward Efficient Gradient-Based Value Estimation](https://mlsanity.com/paper/2301.13757/) (2023)
- [A new Gradient TD Algorithm with only One Step-size: Convergence Rate Analysis using L-λ Smoothness](https://mlsanity.com/paper/2307.15892/) (2023)

## Abstract (arXiv)

Many off-policy prediction learning algorithms have been proposed in the past decade, but it remains unclear which algorithms learn faster than others. We empirically compare 11 off-policy prediction learning algorithms with linear function approximation on two small tasks: the Rooms task, and the High Variance Rooms task. The tasks are designed such that learning fast in them is challenging. In the Rooms task, the product of importance sampling ratios can be as large as 214 and can sometimes be two. To control the high variance caused by the product of the importance sampling ratios, step size should be set small, which in turn slows down learning. The High Variance Rooms task is more extreme in that the product of the ratios can become as large as 214× 25. This paper builds upon the empirical study of off-policy prediction learning algorithms by Ghiassian and Sutton (2021). We consider the same set of algorithms as theirs and employ the same experimental methodology. The algorithms considered are: Off-policy TD(λ), five Gradient-TD algorithms, two Emphatic-TD algorithms, Tree Backup(λ), Vtrace(λ), and ABTD(zeta). We found that the algorithms' performance is highly affected by the variance induced by the importance sampling ratios. The data shows that Tree Backup(λ), Vtrace(λ), and ABTD(zeta) are not affected by the high variance as much as other algorithms but they restrict the effective bootstrapping parameter in a way that is too limiting for tasks where high variance is not present. We observed that Emphatic TD(λ) tends to have lower asymptotic error than other algorithms, but might learn more slowly in some cases. We suggest algorithms for practitioners based on their problem of interest, and suggest approaches that can be applied to specific algorithms that might result in substantially improved algorithms.