Reinforcement Learning in Finite MDPs: PAC Analysis

Alexander L. Strehl, Lihong Li, Michael L. Littman

Abstract

We study the problem of learning near-optimal behavior in finite Markov Decision Processes (MDPs) with a polynomial number of samples. These "PAC-MDP" algorithms include the well-known E3 and R-MAX algorithms as well as the more recent Delayed Q-learning algorithm. We summarize the current state-of-the-art by presenting bounds for the problem in a unified theoretical framework. A more refined analysis for upper and lower bounds is presented to yield insight into the differences between the model-free Delayed Q-learning and the model-based R-MAX.
BibTeX
@article{strehl2009reinforcement,
  author = {Alexander L. Strehl and Lihong Li and Michael L. Littman},
  title = {{Reinforcement Learning in Finite MDPs: PAC Analysis}},
  journal = {J. Mach. Learn. Res.},
  year = {2009},
}

Loading related content...

Figure