Exploration in metric state spaces
Sham M. Kakade, Michael J. Kearns, John C. Langford · ScholarlyCommons (University of Pennsylvania) · 2003
We present a provably near-optimal algorithm for reinforcement learn-ing in Markov decision processes in which there is a natural metric on the state space that allows the construction of accurate local models. Our algorithm is a generalization of the E3 algorithm of Kearns and Singh, and assumes a black box for approximate planning. Unlike the original E 3, our algorithm finds a near optimal policy in an amount of time that does not directly depend on the size of the state space, but instead de-pends on the covering numbers of the state space, which are informally the number of neighborhoods in the state space required for accurate lo-cal modeling at a chosen resolution. 1 Introduction, Motivation