inria-00164033, version 1
Change Point Detection and Meta-Bandits for Online Learning in Dynamic Environments
Cédric Hartland
1, 2Nicolas Baskiotis 1, 2Sylvain Gelly 1, 2Michèle Sebag
1, 2Olivier Teytaud 1, 2
CAp (2007) 237-250
Résumé : Motivated by realtime website optimization, this paper is about online learning in abruptly changing environments. Two extensions of the UCBT algorithm are combined in order to handle dynamic multi-armed bandits, and specifically to cope with fast variations in the rewards. Firstly, a change point detection test based on Page-Hinkley statistics is used to overcome the limitations due to the UCBT inertia. Secondly, a controlled forgetting strategy dubbed Meta-Bandit is proposed to take care of the Exploration vs Exploitation trade-off when the PH test is triggered. Extensive empirical validation shows significant improvements compared to the baseline algorithms. The paper also investigates the sensitivity of the proposed algorithm with respect to the number of available options.
- 1 : TAO (INRIA Futurs)
- INRIA – CNRS : UMR8623 – Université Paris XI - Paris Sud
- 2 : Laboratoire de Recherche en Informatique (LRI)
- CNRS : UMR8623 – Université Paris XI - Paris Sud
- Domaine : Informatique/Intelligence artificielle
Informatique/Apprentissage
Mathématiques/Statistiques
Statistiques/Théorie - Mots-clés : online learning – meta bandits – ucb – dynamic environments
- inria-00164033, version 1
- http://hal.inria.fr/inria-00164033
- oai:hal.inria.fr:inria-00164033
- Contributeur : Cédric Hartland
- Soumis le : Lundi 5 Novembre 2007, 10:18:05
- Dernière modification le : Lundi 5 Novembre 2007, 10:52:36






Documents associés
Exporter