RUcore Resource Object
RUcore Resource Object
PDF-1(621.73 KB)
Uniform TitleProbably Approximately Correct (PAC) exploration in reinforcement learning
NameStrehl, Alexander L. (author), Littman, Michael (chair), Hirsh, Haym (internal member), Szegedy, Mario (internal member), Kearns, Michael (outside member), Rutgers University, Graduate School - New Brunswick,
Degree Date2007
Date Created2007
SubjectComputer Science,
Learning models (Stochastic processes),
Learning--Mathematical models,
Machine learning
DescriptionReinforcement Learning (RL) in finite state and action Markov Decision Processes is studied with an emphasis on the well-studied exploration problem. We provide a general RL framework that applies to all results in this thesis and to other results in RL that generalize the finite MDP assumption. We present two new versions of the Model-Based Interval Estimation (MBIE) algorithm and prove that they are both PAC-MDP. These algorithms are provably more efficient any than previously studied RL algorithms. We prove that many model-based algorithms (including R-MAX and MBIE) can be modified so that their worst-case per-step computational complexity is vastly improved without sacrificing their attractive theoretical guarantees. We show that it is possible to obtain PAC-MDP bounds with a model-free algorithm called Delayed Q-learning.
NotePh.D.
NoteIncludes bibliographical references (p. 133-136).
Genretheses
Persistent URLhttp://hdl.rutgers.edu/1782.2/rucore10001600001.ETD.16785
LanguageEnglish
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.