An Empirical Comparison of Off-policy Prediction Learning Algorithms on
  the Collision Task
  Off-policy prediction -- learning the value function for one policy from data
generated while following another policy -- is one of the most challenging
subproblems in reinforcement learning. This paper presents empirical results
with eleven prominent off-policy learning algorithms that use linear function
approximation: five Gradient-TD methods, two Emphatic-TD methods, Off-policy
TD($\lambda$), Vtrace, and versions of Tree Backup and ABQ modified to apply to
a prediction setting. Our experiments used the Collision task, a small
idealized off-policy problem analogous to that of an autonomous car trying to
predict whether it will collide with an obstacle. We assessed the performance
of the algorithms according to their learning rate, asymptotic error level, and
sensitivity to step-size and bootstrapping parameters. By these measures, the
eleven algorithms can be partially ordered on the Collision task. In the top
tier, the two Emphatic-TD algorithms learned the fastest, reached the lowest
errors, and were robust to parameter settings. In the middle tier, the five
Gradient-TD algorithms and Off-policy TD($\lambda$) were more sensitive to the
bootstrapping parameter. The bottom tier comprised Vtrace, Tree Backup, and
ABQ; these algorithms were no faster and had higher asymptotic error than the
others. Our results are definitive for this task, though of course experiments
with more tasks are needed before an overall assessment of the algorithms'
merits can be made.
