Optimistic planning in Markov decision processes using a generative model

Balázs Szörényi 1, 2 Gunnar Kedenburg 1 Rémi Munos 1
1 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal
Abstract : 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 com-plexity problem of computing, with probability 1−δ, an -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" princi-ple. 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.
Type de document :
Communication dans un congrès
Advances in Neural Information Processing Systems 27, Dec 2014, Montréal, Canada
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01079366
Contributeur : Balazs Szorenyi <>
Soumis le : samedi 1 novembre 2014 - 11:24:24
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : lundi 2 février 2015 - 16:51:50

Fichier

StOP_nips.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01079366, version 1

Citation

Balázs Szörényi, Gunnar Kedenburg, Rémi Munos. Optimistic planning in Markov decision processes using a generative model. Advances in Neural Information Processing Systems 27, Dec 2014, Montréal, Canada. 〈hal-01079366〉

Partager

Métriques

Consultations de la notice

240

Téléchargements de fichiers

184