Comparing Value-Function Estimation Algorithms in Undiscounted Problems
Ferenc Beleznay · 2012
We compare scaling properties of several value-function estimation algorithms. In particular, we prove that Q-learning can scale exponentially slowly with the number of states. We identify the reasons of the slow convergence and show that both TD() and learning with a fixed learning-rate enjoy rather fast convergence, just like the model-based method. 1 Introduction Recently, there was some discussion about if the indirect (model-based) or the direct (model-free) methods of reinforcement learning are more advantageous. Of course, the asnwer is affected by many factors. One such factor is the learning-speed measured in terms of the number of samples required to learn a good approximation of the optimal Q-function (with a given tolerance and with high probability). In this article we take this number as the basis of our measure of convergence rate. In their recent paper Kearns and Singh argued that Q-learning is not much slower than modelbased learning [2], namely that their sample...