Finite-Sample Convergence Rates for Q-Learning and Indirect Algorithms

Abstract

Abstract In this paper, we address two issues of long-standing interest in the reinforcement learning literature. First, what kinds of performance guarantees can be made for Q-learning after only a finite number of actions? Second, what quantitative comparisons can be made between Q-learning and model-based (indirect) approaches, which use experience to estimate next-state distributions for off-line value iteration? We first show that both Q-learning and the indirect approach enjoy rather rapid convergence to the optimal policy as a function of the number of state transitions observed. In particular, on the order of only (N log(1=ffl)=ffl2)(log(N) + log log(1=ffl)) transitions are sufficient for both algorithms to come within ffl of the optimal policy, in an idealized model that assumes the observed transitions are "well-mixed " throughout an N-state MDP. Thus, the two approaches have roughly the same sample complexity. Perhaps surprisingly, this sample complexity is far less than what is required for the model-based approach to actually construct a good approximation to the next-state distribution. The result also shows that the amount of memory required by the model-based approach is closer to N than to N2. For either approach, to remove the assumption that the observed transitions are well-mixed, we consider a model in which the transitions are determined by a fixed, arbitrary exploration policy. Bounds on the number of transitions required in order to achieve a desired level of performance are then related to the stationary distribution and mixing time of this policy. 1 Introduction There are at least two different approaches to learning in Markov decision processes: indirect approaches, which use control experience (observed transitions and payoffs) to estimate a model, and then apply dynamic programming to compute policies from the estimated model; and direct approaches such as Q-learning [2], which use control experience to directly learn policies (through value functions) without ever explicitly estimating a model. Both are known to converge asymptotically to the optimal policy [1, 3]. However, little is known about the performance of these two approaches after only a finite amount of experience.