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

In this paper, we address two issues of long-standing interest in the re(cid:173) inforcement learning literature. First, what kinds of performance guar(cid:173) antees 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 num(cid:173) ber of state transitions observed. In particular, on the order of only (Nlog(1/c)/c2)(log(N) loglog(l/c)) transitions are sufficient for both algorithms to come within c of the optimal policy, in an idealized model that assumes the observed transitions are "well-mixed" throughout an N-state MDP.