Algorithm-Directed Exploration for Model-Based Reinforcement Learning in Factored MDPs
- Carlos Guestrin, Department of Computer Science, Stanford University
- Relu Patrascu, Department of Computer Science, University of Toronto
- Dale Schuurmans, AICML
One of the central challenges in reinforcement learning is to balance the exploration/exploitation tradeoff while scaling up to large problems. Al though modelbased reinforcement learning has been less prominent than valuebased methods in addressing these challenges, recent progress has generated renewed interest in pursuing model based approaches: Theoretical work on the ex ploration/exploitation tradeoff has yielded provably sound modelbased algorithms such as E 3 and Rmax , while work on factored MDP representa tions has yielded modelbased algorithms that can scale up to large problems. Recently the benefits of both achievements have been combined in the Factored E 3 algorithm of Kearns and Koller. In this paper, we address a significant shortcoming of Factored E 3 : namely that it requires an oracle planner that cannot be feasibly implemented. We propose an alternative approach that uses a prac tical approximate planner, approximate linear pro gramming, that maintains desirable properties. Fur ther, we develop an exploration strategy that is tar geted toward improving the performance of the lin ear programming algorithm, rather than an oracle planner. This leads to a simple exploration strategy that visits states relevant to tightening the LP solu tion, and achieves sample efficiency logarithmic in the size of the problem description. Our experimen tal results show that the targeted approach performs better than using approximate planning for imple menting either Factored E 3 or Factored Rmax .
Citation
C. Guestrin, R. Patrascu, D. Schuurmans. "Algorithm-Directed Exploration for Model-Based Reinforcement Learning in Factored MDPs". International Conference on Machine Learning (ICML), Sydney Australia, July 2002.| Keywords: | algorithm, factored MDPs, machine learning |
| Category: | In Conference |
BibTeX
@incollection{Guestrin+al:ICML02,
author = {Carlos Guestrin and Relu Patrascu and Dale Schuurmans},
title = {Algorithm-Directed Exploration for Model-Based Reinforcement
Learning in Factored MDPs},
booktitle = {International Conference on Machine Learning (ICML)},
year = 2002,
}Last Updated: June 01, 2007Submitted by Staurt H. Johnson
