td(0) Converges Provably Faster than the Residual Gradient Algorithm

Proceedings of the Twentieth International Conference on Machine Learning

Volume

Proceedings of the Twentieth International Conference on Machine Learning

Contents

In Reinforcement Learning (RL) there has been some experimental evidence that the residual gradient algorithm converges slower than the td(0) algorithm. In this paper, we use the concept of asymptotic convergence rate to prove that under certain conditions the synchronous off-policy td(0) algorithm converges faster than the synchronous off-policy residual gradient algorithm if the value function is represented in tabular form. This is the first theoretical result comparing the convergence behaviour of two RL algorithms. We also show that as soon as linear function approximation is involved no general statement concerning the superiority of one of the algorithms can be made.