This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via Google Scholar Google Scholar Articles by Kunnumkal, S. Articles by Topaloglu, H. Search for Related Content

Exploiting the Structural Properties of the Underlying Markov Decision Problem in the Q-Learning Algorithm

Indian School of Business, Gachibowli, Hyderabad 500032, India
School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
sumit_kunnumkal{at}isb.edu
topaloglu{at}orie.cornell.edu

This paper shows how to exploit the structural properties of the underlying Markov decision problem to improve the convergence behavior of the Q-learning algorithm. In particular, we consider infinite-horizon discounted-cost Markov decision problems where there is a natural ordering between the states of the system and the value function is known to be monotone in the state. We propose a new variant of the Q-learning algorithm that ensures that the value function approximations obtained during the intermediate iterations are also monotone in the state. We establish the convergence of the proposed algorithm and experimentally show that it significantly improves the convergence behavior of the standard version of the Q-learning algorithm.

Key words: Markov decision processes; Q-learning; stochastic approximation methods
History: received July 2005; revised May 2007; accepted September 2007.