2009 · 204 citations · 43 references
ComputingComputer ScienceAlgorithmsMachine LearningMarkov Decision ProcessesPolicy IterationPolicy LearningReinforcement LearningReinforcement Learning FoundationsFinite-horizon Decision MakingLower BoundsModel-free AlgorithmsModel-free Reinforcement LearningQ-learningReinforcement Learning TheoryState-of-the-art Review
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 wellknown 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.
43
Reinforcement Learning: An Introduction
IEEE Transactions on Neural Networks · 2005 · 25.8K citations
Artificial intelligence: a modern approach
Choice Reviews Online · 1995 · 22.2K citations · Full text
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
Christopher J. Watkins, Peter Dayan · Machine Learning · 1992 · 9K citations · Full text