Timezone: »

Poster
Optimistic Planning in Markov Decision Processes Using a Generative Model
Balázs Szörényi · Gunnar Kedenburg · Remi Munos

Tue Dec 09 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D #None
We consider the problem of online planning in a Markov decision process with discounted rewards for any given initial state. We consider the PAC sample complexity problem of computing, with probability $1-\delta$, an $\epsilon$-optimal action using the smallest possible number of calls to the generative model (which provides reward and next-state samples). We design an algorithm, called StOP (for Stochastic-Optimistic Planning), based on the "optimism in the face of uncertainty" principle. StOP can be used in the general setting, requires only a generative model, and enjoys a complexity bound that only depends on the local structure of the MDP.