Paper published in a book (Scientific congresses and symposiums)
Automatic discovery of ranking formulas for playing with multi-armed bandits
Maes, Francis; Wehenkel, Louis; Ernst, Damien
2011In Proceedings of the 9th European Workshop on Reinforcement Learning (EWRL 2011)
Peer reviewed
 

Files


Full Text
bandits.pdf
Publisher postprint (307.44 kB)
Download
Annexes
BestPaperAwardEWRL2011.jpg
Publisher postprint (1.87 MB)
This paper won the Best Paper Award at EWRL 2011.
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
multi-armed bandits; exploration vs exploitation; automatic formula discovery
Abstract :
[en] We propose an approach for discovering in an automatic way formulas for ranking arms while playing with multi-armed bandits. The approach works by de ning a grammar made of basic elements such as for example addition, subtraction, the max operator, the average values of rewards collected by an arm, their standard deviation etc., and by exploiting this grammar to generate and test a large number of formulas. The systematic search for good candidate formulas is carried out by a built-on-purpose optimization algorithm used to navigate inside this large set of candidate formulas towards those that give high performances when using them on some multi-armed bandit problems. We have applied this approach on a set of bandit problems made of Bernoulli, Gaussian and truncated Gaussian distributions and have identi ed a few simple ranking formulas that provide interesting results on every problem of this set. In particular, they clearly outperform several reference policies previously introduced in the literature. We argue that these newly found formulas as well as the procedure for generating them may suggest new directions for studying bandit problems.
Disciplines :
Computer science
Author, co-author :
Maes, Francis ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Wehenkel, Louis  ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Ernst, Damien  ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Systèmes et modélisation
Language :
English
Title :
Automatic discovery of ranking formulas for playing with multi-armed bandits
Publication date :
2011
Event name :
9th European Workshop on Reinforcement Learning (EWRL 2011)
Event place :
Athens, Greece
Event date :
September 9-11, 2011
Audience :
International
Main work title :
Proceedings of the 9th European Workshop on Reinforcement Learning (EWRL 2011)
Peer reviewed :
Peer reviewed
Funders :
F.R.S.-FNRS - Fonds de la Recherche Scientifique [BE]
Available on ORBi :
since 06 August 2011

Statistics


Number of views
104 (20 by ULiège)
Number of downloads
432 (15 by ULiège)

Scopus citations®
 
8
Scopus citations®
without self-citations
3

Bibliography


Similar publications



Contact ORBi