[PDF] Analysis of bayesian and frequentist strategies for sequential

View - Download Analysis of bayesian and frequentist strategies for sequential

Previous PDF

Next PDF

2014-ENST-0056

EDITE - ED 130

Doctorat ParisTech

T H ¨ S E

pour obtenir le grade de docteur délivré par

TELECOM ParisTech

Spécialité " Signal et Images »

présentée et soutenue publiquement par

Emilie KAUFMANN

le 1er octobre 2014 Analyse de stratégies bayésiennes et fréquentistes pour l"allocation séquentielle de ressources

Directeur de thèse :Olivier CAPPE

Co-encadrement de la thèse :Aurélien GARIVIERetRémi MUNOS Jury M. Gérard BIAU,Professeur, LSTA, Université Pierre et Marie CurieExaminateur M. Thomas BONALD,Professeur, LTCI, Telecom ParisTechExaminateur M. Olivier CAPPE,Directeur de recherche, LTCI, CNRS & Telecom ParisTechCo-directeur de thèse M. Olivier CATONI,Directeur de recherche, DMA, CNRS & Ecole Normale SupérieureRapporteur M. Nicolò CESA-BIANCHI,Professeur, Università degli Studi di MilanoRapporteur M. Aurélien GARIVIER,Professeur, IMT, Université Paul SabatierCo-directeur de thèse M. Jean-Michel MARIN,Professeur, I3M, Université de Montpellier IIExaminateur M. Rémi MUNOS,Directeur de recherche, INRIA, Equipe SequelCo-directeur de thèse

TELECOM ParisTech

école de l"Institut Mines-Télécom - membre de ParisTech

46 rue Barrault 75013 Paris - (+33) 1 45 81 77 77 - www.telecom-paristech.fr

2

Remerciements

L"heure est venue de mettre la touche finale

`a ce manuscrit, en remerciant toutes les personnes sans qui ce dernier n"existerait pas, et qui ont fait de ces trois ann

´ees de th`ese une exp´erience inoubliable.

Tout d"abord un grand merci

`a mes directeurs de th`ese. Vous avez su me proposer un sujet passion- nant, et doser avec justesse encadrement et libert ´e de recherche tout au long de ces trois ans. Aur´elien, merci d"avoir pu me consacrer des journ ´ees enti`eres lors de nos s´eances de travail`a Toulouse. Merci

pour ton accueil chaleureux et pour tous tes conseils, qu"ils soient scientifiques ou non. Olivier, merci

pour toutes nos discussions face `a un tableau, un bon repas ou mˆeme une cam´era, et ton aide au quotidien (m

ˆeme informatique) malgr´e ton emploi du temps charg´e. Merci`a vous deux pour vos encouragements,

votre disponibilit

´e et vos relectures attentives. R´emi, merci pour ton accueil fr´equent`a Lille lors de mes

deux premi `eres ann´ees de th`ese, et pour notre travail sur le Thompson Sampling. Tu m"a aussi permis de collaborer avec Nathan, que je remercie dans ces lignes pour nos

´echanges nombreux et fructueux. I

also want to thank Shivaram for pointing a new problem to me at ICML in 2012. It was great working with you, even from far, and I hope we will see each other again at some other conference! Nicol `o and Olivier, I am really honored that you accepted to review this manuscript and I warmly thankyouforyourcarefulreading. Merci ´egalement`aG´erard, ThomasetJean-Micheldes"ˆetreint´eress´es a mon travail, et d"avoir pris le temps d"assister`a cette soutenance.

Le chemin de l"apprenti chercheur est fait de grandes joies (finir une preuve !) mais aussi de grandes

frustrations (elle ´etait fausse...). Pendant ces trois ans, cela aura´et´e un plaisir de les partager (ou de les oublier) avec mes coll `egues doctorants et jeunes docteurs du 37, rue Dareau. Un merci tout partic- ulier `a mes co-bureau du DA320 pour leur bonne humeur. Certains sont maintenant docteurs (Joffrey, Alexandre, Sylvain, Yao), d"autres le seront bient ˆot (Adrien, Yasir et Andr´es) et`a Claire`a qui je passe le flambeau, je souhaite trois belles ann ´ees. Il me serait difficile de citer, sans oublier personne, tous ceux avec qui j"ai partag

´e pauses caf´e, puis pauses th´e, gˆateaux ou autres bi`eres post-s´eminaire, soir´ees

gastronomiques ou encore un week-end incroyable en Roumanie. Ils se reconna

ˆıtront, et sauront comme

tout cela aura

´et´e pr´ecieux pour moi ! Une mention sp´eciale`a Cristina, pour avoir´et´e une colloc" g´eniale

en plus d"une coll `egue formidable. A Amandine, qui m"a fait d´ecouvrir des th´es d´elicieux (tout comme

Ruocong), re-d

´ecouvrir Hermann (et d"autres recettes), et aura toujours´et´e d"une grande aide dans les formalit

´es administratives. A Andr´es pour une s´eance shopping m´emorable (et d"autres`a venir). A Em-

ilie, pour ses astuces LaTeX et une s ´eance de bricolage fort amusante rue Dareau. Au club des fans de

Question Pour Un Champion (Sylvain

2et Olivier). A Eric: non il n"y aura pas de concours de pot de

th

`ese ! En plus de mes coll`egues, je souhaiterais remercier Janique et Laurence, interlocutrices toujours

agr

´eables et efficaces pour les ordres de mission, Fabrice et Sophie-Charlotte pour leur aide informatique

(ainsi que Nicolas !), et Florence pour son aide dans tous les domaines ainsi que son soutien aux activit

´es

du Bureau des Doctorants. Un clin d"oeil `a Georges, Simon, Dong-Bach et tous les autres pour cette belle aventure associative. 4

Ces trois ann

´ees ont´et´e enrichissantes en terme de rencontres et de voyages. D"abord au travers des s

´eminaires et autres conf´erences (souvent) au soleil, o`u j"ai eu la chance de rencontrer des jeunes

chercheurs fort sympatiques. Je pense en particulier aux doctorants et post-doc de l"

´equipe Sequel, aux

randonneurs d"Aussois (et `a ceux desˆıles Canaries), aux skieurs de Grenade, aux compagnons de tapas

a Barcelone ou aux organisateurs d"YSP toujours motiv´es. J"ai aussi eu la chance de passer trois mois

a l"Universit´e de Princeton, ce qui m"a donn´e l"occasion de prendre la mesure de la recherche outre-

Atlantique. Merci

`a S´ebastien de m"avoir accueillie. J"ai beaucoup appr´eci´e nos discussions et j"esp`ere que nous aurons l"occasion de travailler ensemble dans le futur. Merci `a tous les amis "am´ericains" (qui ne le sont pas pour la plupart) qui ont rendu ce s ´ejour agr´eable. Thanks to Rofoldo and Theo for making me feel at home during these three months. Thanks Aga for having been such a great office mate, but

also Andrew, Flavia and Tana for our little Princeton gang. Thanks to the welcoming "Frenchies" I met

there and also to some graduate students at ORFE with whom we shared nice moments.

Mes remerciements vont bien s

ˆur aussi`a mes amis "parisiens" (qui ne le sont pas pour la plupart) et alsaciens (qui le sont pour la plupart) qui m"ont cotoy ´ee et soutenue pendant cette aventure. Je pense notamment `a Camille, Arthur et Sonia, Timon et Tiphaine (et Elise qui nous a rejoints en cours de

route), Nina, Laure, Vincent, Elsa, Guillaume, Sarah (C.) et son Cricri, Pierre, Jean, et les autres amis

rencontr

´es pendant les ann´ees Cachanaises, avec qui discuter de sa th`ese est presque un passage oblig´e.

Aux collocs, Evelyne et Yacine, pour les bons moments au 13, rue Bellier Dedouvre. A Sarah (L.), une

autre alsacienne conquise par la capitale. A mes amis d"enfance (ou presque) pour qui la lecture d"une

page au hasard de ce document est hilarante (et qui me croient d

´esormais membre de la mafia avec tous

ces bandits...), merci d" ˆetre toujours pr´esents quand je rentre en Alsace ! Les "filles": Agn`es, Marie-

Madeleine, Martine, Marion, Marie, C

´eline, et tous ceux qui se sont rajout´es avec bonheur`a notre petit groupe, c"est toujours un plaisir de vous retrouver !

Je ne serais pas arriv

´ee jusqu"ici sans l"appui de ma famille. A mon papa, qui m"a familiaris´ee d`es mon plus jeune ˆage avec les probl`emes de remplissage de baignoires qui fuient ou autres croisements de trains, et `a ma maman, qui a toujours eu peur que ses enfants d´etestent l"´ecole, je veux dire un grand merci. Merci pour tout ce que vous m"avez transmis, pour votre soutien durant ces longues ann

´ees

d"

´etudes, et pour votre pr´esence dans ce moment important. Merci`a St´ephane pour cette complicit´e

que nous partageons, et pour ta capacit ´e`a toujours croire en ta grande soeur. Tu as avant moi fait l"exp

´erience de l"´ecriture d"un manuscrit qui int´eressera`a coup sˆur de plus nombreux lecteurs que celui-

ci ([

Kaufmann, 2014

]). Longue vie `a l"imaginaire du roi Barry, et`a ta muse Ombline. Plus largement, merci

`a tous les membres de ma famille pour tous ces bons moments partag´es, autour d"une tarte flamb´ee,

d"une partie de carte ou autre, et pour tous ceux `a venir. Un merci´emu`a P´ep´e et M´em´e.

Romain, c"est

`a toi que s"adressent ces derniers mots. Quand nous nous sommes rencontr´es tu achevais l"

´ecriture de ta th`ese, et une autre th`ese plus tard -la mienne cette fois- ta pr´esence`a mes cˆot´es

est devenue une ´evidence. Merci pour tous ces beaux moments et pour ton soutien de chaque instant.

Contents

Introduction et pr

´esentation des r´esultats(in French)9

1 Pr

´esentation des probl`emes de bandit´etudi´es . . . . . . . . . . . . . . . . . . . . . . . . .10

1.1 Maximisation des r

´ecompenses : mesure de performance et objectifs . . . . . . .12

1.2 Identification des meilleurs bras : mesure de performance et objectifs . . . . . . .

13

2 Des algorithmes bay

´esiens pour la maximisation des r´ecompenses . . . . . . . . . . . . .15

2.1 Deux approches probabilistes d"un probl

`eme de bandit . . . . . . . . . . . . . . .15

2.2 Les algorithmes Bayes-UCB et Thompson Sampling . . . . . . . . . . . . . . . .

18

2.3 Des algorithmes bay

´esiens pour des mod`eles plus g´en´eraux . . . . . . . . . . . .24

3 Vers des algorithmes fr

´equentistes optimaux pour l"identification des meilleurs bras . . .27

3.1 Une borne inf

´erieure sur la complexit´e`a niveau de confiance fix´e . . . . . . . . .28

3.2 Deux algorithmes : KL-LUCB et KL-Racing . . . . . . . . . . . . . . . . . . . . .

28

3.3 Caract

´erisation de la complexit´e pour des mod`eles de bandit`a deux bras . . . . .31

4 Organisation du document . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

33

1 Two probabilistic views on rewards maximization in bandit models 35

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

1.2 The frequentist approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

38

1.2.1 Lower bounds on the regret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

1.2.2 Examples of bandit models and associated tools to build bandit algorithms . . .

42

1.2.3 Asymptotically optimal algorithms . . . . . . . . . . . . . . . . . . . . . . . . . .

45

1.3 The Bayesian approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

49

1.3.1 Some examples of Bayesian bandit models. . . . . . . . . . . . . . . . . . . . . .

51

1.3.2 Discounted and Finite-Horizon Gittins indices . . . . . . . . . . . . . . . . . . .

53

1.3.3 Index policies using Gittins indices . . . . . . . . . . . . . . . . . . . . . . . . . .

56

1.3.4 Approximation of the FH-Gittins indices . . . . . . . . . . . . . . . . . . . . . . .

58

1.3.5 Asymptotically optimal algorithms with respect to the Bayes risk . . . . . . . . .

60

1.4 Numerical study and conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

63

1.5 Elements of proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

65

1.5.1 Changes of distribution: proof of Lemma 1.3 . . . . . . . . . . . . . . . . . . . .

65

1.5.2 On Gittins" theorem: proof of Theorem 1.13 . . . . . . . . . . . . . . . . . . . . .

66

1.5.3 Proofs of Bayes risk bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

2 Bayes-UCB73

2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

74

2.2 The Bayes-UCB algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

75

6CONTENTS2.3 Analysis of the Bayes-UCB algorithm for binary rewards . . . . . . . . . . . . . . . . . .78

2.3.1 Asymptotic optimality and links with frequentist algorithms . . . . . . . . . . . .

79

2.3.2 Bayes-UCB beyond Bernoulli distributions . . . . . . . . . . . . . . . . . . . . . .

80

2.3.3 Finite-time analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

2.4 Numerical experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

2.4.1 Binary bandits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

2.4.2 Gaussian rewards with unknown means and variances . . . . . . . . . . . . . . .

83

2.4.3 Sparse linear bandits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

84

2.5 Elements of proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85
quotesdbs_dbs25.pdfusesText_31

[PDF] BAndIt 650 n/S 09/10 - Anciens Et Réunions

[PDF] Bando di concorso - France

[PDF] bando ING IND 17 BERTOLINI - Università degli Studi di Parma

[PDF] Bandol - Anciens Et Réunions

[PDF] Bandol - ANGDM

[PDF] Bandonéon / Enseignant - Gestion De Projet

[PDF] Bandprofil … wir stellen uns vor…

[PDF] Bandscheibenvorfall der Halswirbelsäule

[PDF] Bandschleifer Belt Sander

[PDF] Bandtrockner in Holzpelletindustrie

[PDF] Bangkok - Deux heures de massage thaï traditionnel - Anciens Et Réunions

[PDF] Bangkok -? Kanchanaburi -? Ayutthaya -? Sukhothai -?Chiang Rai - France

[PDF] bangkok 21 - Katja Dombrowski

[PDF] Bangkok Andrew Burke pdf

[PDF] Bangkok Autrement OCT14 - Les Comptoirs du Monde - France