Near-Optimal BRL using Optimistic Local Transitions (Extended Version) - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2012

Near-Optimal BRL using Optimistic Local Transitions (Extended Version)

Mauricio Araya
  • Fonction : Auteur
  • PersonId : 881106
Vincent Thomas
Olivier Buffet

Résumé

Model-based Bayesian Reinforcement Learning (BRL) allows a sound formalization of the problem of acting optimally while facing an unknown environment, i.e., avoiding the exploration-exploitation dilemma. However, algorithms explicitly addressing BRL suffer from such a combinatorial explosion that a large body of work relies on heuristic algorithms. This paper introduces bolt, a simple and (almost) deterministic heuristic algorithm for BRL which is optimistic about the transition function. We analyze bolt's sample complexity, and show that under certain parameters, the algorithm is near-optimal in the Bayesian sense with high probability. Then, experimental results highlight the key differences of this method compared to previous work.
L'apprentissage par renforcement bayésien basé modèle (BRL) permet une formalisation saine du problème consistant à agir optimalement face à un environnement inconnu, c'est-à-dire en évitant le dilemme exploration-exploitation. Toutefois, les algorithmes s'attaquant explicitement au BRL souffrent d'une telle explosion combinatoire qu'un grand nombre de travaux repose sur des algorithmes heuristiques. Cet article introduit bolt, un algorithme heuristique simple et (presque) déterministe pour le BRL qui est optimiste vis à vis de la fonction de transition. Nous analysons la complexité d'échantillon de bolt et montrons que, pour certains paramètres, l'algorithme est quasi-optimal au sens bayésien avec une grande probabilité. Puis, des résultats expérimentaux mettent en valeur les principales différences entre cette méthode et des travaux antérieurs.
Fichier principal
Vignette du fichier
RR-7965.pdf (1.03 Mo) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00702243 , version 1 (29-05-2012)

Identifiants

  • HAL Id : hal-00702243 , version 1

Citer

Mauricio Araya, Vincent Thomas, Olivier Buffet. Near-Optimal BRL using Optimistic Local Transitions (Extended Version). [Research Report] RR-7965, INRIA. 2012. ⟨hal-00702243⟩
135 Consultations
584 Téléchargements

Partager

Gmail Facebook X LinkedIn More