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
in Poster Session »
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.
[ PDF] 

Author Information

Balázs Szörényi (The Technion / University of Szeged)
Gunnar Kedenburg
Remi Munos (Google DeepMind)

More from the Same Authors