Speeding Up Q(lambda)-learning

Abstract

Q(lambda)-learning uses TD(lambda)-methods to accelerate Q learning. The worst case complexity for a single update step of previous online Q(lambda)implementations based on lookup tables is bounded by the size of the state action space. Our faster algorithm's worst case complexity is bounded by the number of actions. The algorithm is based on the observation that Q value updates may be postponed until they are needed.