From Q(lambda) to Average Q-learning: Efficient Implementation of an Asymptotic Approximation

Abstract

Q( ) is a reinforcement learning algorithm that combines Q-learning and TD( ). Online implementations of Q( ) that use eligibility traces have been shown to speed basic Q-learning. In this paper we present an asymptotic analysis of Watkins’ Q( ) with accumulative eligibility traces. We first introduce an asymptotic approximation of Q( ) that appears to be a gain matrix variant of basic Qlearning. Using the ODE method, we then determine an optimal gain matrix for Q-learning that maximizes its rate of convergence toward the optimal value function   . The similarity between this optimal gain and the asymptotic gain of Q( ) explains the relative efficiency of the latter for  . Furthermore, by minimizing the difference between these two gains, optimal values for the  parameter and the decreasing learning rates can be determined. This optimal  strongly depends on the exploration policy during learning. A robust approximation of these learning parameters leads to the definition of a new efficient algorithm called AQ-learning (Average Q-learning), that shows a close resemblance to Schwartz’ R-learning. Our results have been demonstrated through numerical simulations.