Competing with an Infinite Set of Models in Reinforcement Learning

Phuong Nguyen 1 Odalric-Ambrym Maillard 2 Daniil Ryabko 3 Ronald Ortner 4
3 SEQUEL - Sequential Learning
LIFL - Laboratoire d'Informatique Fondamentale de Lille, LAGIS - Laboratoire d'Automatique, Génie Informatique et Signal, Inria Lille - Nord Europe
Abstract : We consider a reinforcement learning setting where the learner also has to deal with the problem of finding a suitable state-representation function from a given set of models. This has to be done while interacting with the environment in an online fashion (no resets), and the goal is to have small regret with respect to any Markov model in the set. For this setting, recently the \BLB~algorithm has been proposed, which achieves regret of order $T^{2/3}$, provided that the given set of models is finite. Our first contribution is to extend this result to a countably infinite set of models. Moreover, the \BLB~regret bound suffers from an additive term that can be exponential in the diameter of the MDP involved, since the diameter has to be guessed. The algorithm we propose avoids guessing the diameter, thus improving the regret bound.
Type de document :
Communication dans un congrès
AISTATS, 2013, Arizona, United States. 31, pp.463-471, 2013, JMLR W&CP
Liste complète des métadonnées

https://hal.inria.fr/hal-00823230
Contributeur : Daniil Ryabko <>
Soumis le : jeudi 16 mai 2013 - 13:45:47
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Identifiants

  • HAL Id : hal-00823230, version 1

Citation

Phuong Nguyen, Odalric-Ambrym Maillard, Daniil Ryabko, Ronald Ortner. Competing with an Infinite Set of Models in Reinforcement Learning. AISTATS, 2013, Arizona, United States. 31, pp.463-471, 2013, JMLR W&CP. 〈hal-00823230〉

Partager

Métriques

Consultations de la notice

268