Dans cette section, nous présentons différents résultats numériques illustrant les perfor- mances de l’algorithme GLM-UCB. Nous nous plaçons d’abord dans le cadre favorable à notre algorithme que sont des environnements simulés où la distribution des récompenses reçues ap- partient à la famille exponentielle canonique. Un tel environnement permet de comprendre plus précisément le comportement de l’algorithme. Ensuite, pour tester la robustesse de l’al- gorithme, nous nous confrontons à des applications réelles. A notre connaissance, il n’existe
pas de système de référence disponible pour tester des méthodes de bandits paramétriques sur des données réelles. Nous avons donc mis en oeuvre deux expériences à partir de données réelles.
Dans chacun des cas, l’algorithme GLM-UCB sera comparé à l’algorithme UCB, connu pour équilibrer de manière optimale exploration et exploitation dans des problèmes de bandit. L’algorithme UCB n’étant pas dédié aux bandits paramétriques, il ne prend pas en compte l’information associée à chacun des bras. Il semblerait donc normal que, lorsque le modèle est réellement paramétrique, le regret soit plus faible sous l’algorithme GLM-UCB que sous l’algorithme UCB. En revanche, si le modèle paramétrique que l’on a conjecturé décrit trop mal les récompenses reçues, alors l’algorithme UCB est vraisemblablement plus performant que l’algorithme GLM-UCB, au moins sur le long terme. En plus de l’algorithme UCB, nous comparons notre algorithme à un algorithme-glouton connaissant les vecteurs de caractéris- tique de chaque bras et jouant, avec probabilté1−, le meilleur bras par rapport au paramètre estimé
At= argmax a
µ(m0aˆθt)
et avec probabilité un bras tiré au hasard.
3.6.1 Données simulées
Pour illustrer le comportement de l’algorithme, nous nous plaçons dans un environnement simulé à2 dimensions dans lequel les récompenses sont des variables de Bernoulli de paramètre µ(m0aθ∗) où θ∗ = (−1, 1)0. Les informations caractérisant chaque bras sont générées de manière
à être équiréparties et sont telles que, pour tout a, kmak2 = 1. La fonction de lien étant
la fonction logistique, on a kµ = 1/4 et, cµ ' 0.1 ; on prend alors ρ(t) = 3 log(t). Pour
estimer le paramètre ˆθt, nous utilisons quelques itérations de l’algorithme de Newton [Boyd
and Vandenberghe, 2004].
Nous appliquons les algorithmes GLM-UCB et UCB sur 20 trajectoires indépendantes pour un horizonn = 1000 et différents nombres |A| de bras. Le regret moyen reçu en fonction du nombre de bras est affiché sur la figure 3.1. Comme prévu, on observe que, contrairement à ce qu’il se passe pour l’algorithme UCB, augmenter le nombre de bras ne dégrade pas la performance de l’algorithme GLM-UCB.
De plus, nous représentons sur la figure 3.2 le nombre de fois où chaque bras est joué en suivant chacun des deux algorithmes. Les bras sont classés par ordre croissant de récompense moyenne. Contrairement à l’algorithme UCB qui nécessite de jouer plusieurs fois tous les bras -les bras ayant une récompense moyenne grande étant joués plus souvent que les autres- , on remarque que sous l’algorithme GLM-UCB peu de bras distincts sont tirés. En effet, l’algorithme utilise les vecteurs de caractéristiques pour estimer la moyenne des récompenses associées aux bras non joués.
Nous profitons de cet environnement simulé pour analyser le comportement de l’estimateur du maximum de quasi-vraisemblance en suivant l’algorithme GLM-UCB. Pour cela, nous considérons un environnement à3 dimensions dans lequel 30 vecteurs de caractéristiques de norme 1 sont générés de manière à être équirépartis dans un plan contenant le paramètre θ∗ = (1, −1, 0)0. On ajoute un vecteur de caractéristique orthogonal à ce plan. Notons que, dans un tel environnement, plusieurs bras sont très proches de l’optimal. Représentons, sur la figure 3.3, l’évolution de l’estimateur ˆθtpour10 trajectoires indépendantes. On remarque que,
au bout d’un horizonn = 20000, les deux premières composantes du paramètre sont estimées de manière plus précise que la troisième composante.
On représente sur la figure 3.4 le nombre de fois où, en suivant l’algorithme GLM-UCB, l’agent joue respectivement un bras très largement sous-optimal dont le vecteur de caracté- ristique est dans le même plan que le paramètre θ∗, un bras proche de l’optimal (dont le
0
5
10
15
20
25
30
0
50
100
150
200
|A|
Regret
UCB
GLM−UCB
Figure 3.1 – Regret des algorithmes UCB et GLM-UCB pour n = 1000 en fonction du nombre de bras. 0 5 10 15 20 25 30 0 500 1000 1500 2000 2500 3000 3500 4000
bras numérotés par ordre croissant de récompense moyenne
Nombre de fois où chaque bras est joué
GLM−UCB UCB
Figure 3.2 – Nombre de fois où chaque bras a été joué en suivant respectivement les algo- rithmes UCB et GLM-UCB sur une trajectoire et un horizon n = 10000.
0
0.5
1
1.5
2
x 10
4−1.5
−1
−0.5
0
0.5
1
1.5
temps
estimateur de
θ
Figure 3.3 – Estimateur ˆθt en fonction du tempst.
vecteur de caractéristique se trouve aussi dans le plan) et le bras orthogonalao. On remarque
que le bras orthogonal est joué un nombre proportionnel à log(t) de fois. En effet, ce bras doit être suffisamment joué pour s’assurer que le bras optimal ne se trouve pas dans cette direction. Parmi les bras qui se trouvent dans le même plan queθ∗, certains ne sont jamais
joués, d’autres très peu souvent. Les bras proches de l’optimal sont quant à eux joués de plus en plus souvent. Ceci peut être observé sur la figure 3.4 : le bras proche de l’optimal est peu joué au début puis est ensuite joué de l’ordre det fois.
3.6.2 Données réelles publiques
Pour évaluer la robustesse de notre méthode, nous avons choisi dans un premier temps d’utiliser une base de donnée publique. La base de donnée « Forest CoverType dataset » du répertoire de données UCI est issu de l’inventaire des arbres de forêts des Etats-Unis. Elle contient une liste d’arbres de6 espèces différentes accompagnés de leurs caractéristiques (lon- gueur, aspect, éloignement de la source d’eau la plus proche...). Une fois centrés, réduits et après l’ajout d’une covariable (et lorsque l’on ignore toutes les variables catégorielles), ces vecteurs de caractéristiques sont de dimension 11. Ce nuage de points dans l’espace R11 a été partitionné en |A|= 32 clusters à l’aide d’une méthode non-supervisée de quantification vectorielle (k-means).
On considère chaque cluster comme étant un bras. Les valeurs des variables de réponse, c’est-à-dire l’espèce des arbres, pour les données associées à chaque cluster sont vues comme les récompenses associées à ce bras. Les centroïdes des clusters sont considérés comme étant les vecteurs de caractéristique de chaque bras. Pour rendre le problème similaire au cas pré- cédent, chaque variable cible est rendue binaire en associant les points de la première classe (l’espèce « Spruce/Fir ») à la récompenseR = 1 et ceux de toutes les autres classes à R = 0. Les proportions de réponses égales à1 dans chaque cluster (en d’autres termes, la récompense espérée associée à chaque bras) varient de 0.354 à 0.992, tandis que la proportion sur l’en- semble des 581 012 points vaut 0.367. Nous cherchons donc à localiser le plus vite possible
0 0.5 1 1.5 2 x 104 0 500 1000 1500 2000 2500 3000 3500 t bras sous−optimal dans le plan bras orthogonal
bras proche de optimal
Figure 3.4 – Nombre de fois où le bras orthogonal ao, un bras sous-optimal dans le plan et
un bras proche de l’optimal dans le plan sont joués le long de l’algorithme GLM-UCB.
le bras/cluster qui contient la plus grande proportion d’arbres d’une espèce donnée. Ce pro- blème est clairement un « problème jouet », mais il ressemble, par exemple, aux applications mentionnées en introduction, comme l’évaluation d’un médicament ou le problème d’optimi- sation de l’affichage des publicités sur internet. L’agent est donc confronté à un problème de bandit à 32 bras ayant des vecteurs de caractéristique dans un espace de dimension 11 avec des récompenses binaires. Le modèle de régression logistique n’est pas exactement satisfait puisque les données sont réelles. Cependant, nous espérons certaines régularités par rapport à la position du centroïde du cluster puisque, par exemple, la régression logistique entraînée sur la totalité des données atteint un taux d’erreur de 0.293 (donc inférieur à la performance par défaut de 0.367).
Nous appliquons les algorithmes GLM-UCB, UCB et -glouton sur 10 trajectoires indé- pendantes. On observe sur la figure 3.5 que l’algorithme GLM-UCB obtient le plus petit regret moyen. Quand le paramètre est bien estimé, l’algorithme glouton peut trouver un bras optimal en très peu de temps et conduit donc à un faible regret. Cependant, par manque d’explora- tion, l’algorithme glouton obtient parfois des regrets qui sont considérablement grands (ce phénomène est étudié dans [Audibert et al., 2007]).
3.6.3 Données de publicité sur internet
Pour cette troisième expérience, nous avons utilisé l’enregistrement de l’activité des utilisa- teurs internet durant une semaine fournie par Orange. Il s’agit d’un fichier contenant environ 5.108 visites de1222 pages internet. Pour chaque visite, le fichier permet de déterminer si l’uti-
lisateur a cliqué ou non sur la publicité qui lui a été présentée. Nous nous sommes restreints à un sous-ensemble de 208 publicités et de 3.105 utilisateurs. Les ensembles des pages et des publicités ont été partitionnés respectivement en 10 et 8 catégories en utilisant l’algorithme LDA (Latent Dirichlet Allocation [Blei et al., 2002]) appliqué au contenu textuel des pages et
0 2000 4000 6000 8000 10000 0 200 400 600 800 1000 1200 1400 1600 t Regret t UCB GLM−UCB Glouton
Figure 3.5 – Comparaison du regret obtenu en suivant les algorithmes UCB, GLM-UCB et -gloutons sur les données « Forest CoverType dataset ».
des annonces publicitaires (dans ce dernier cas, il s’agit du contenu textuel de la page vers la quelle le lien publicitaire pointe).
L’espace d’action est composé de80 paires de catégories de page et catégories de publicité. Quand un couple page-publicité est choisi, il est présenté à un groupe de50 utilisateurs de la base de donnée, et la récompense est le nombre de personnes ayant cliqué sur la publicité. La récompense moyenne étant typiquement de l’ordre de 0.15, on utilise une fonction logarith- mique correspondant à une régression poissonnienne. Le vecteur de covariables pour chaque couple est de dimension 19 : il est composé d’une constante suivie de la concaténation de deux vecteurs de dimensions 10 et 8 représentant respectivement les catégories des pages et des publicités. Dans ce cas, les vecteurs de covariables n’engendrent pas l’espace entier. Pour résoudre ce problème, il est suffisant de considérer la pseudo-inverse deMtau lieu de l’inverse.
Sur ces données, nous avons comparé l’algorithme GLM-UCB avec les deux algorithmes alternatifs décrits ci-dessus. La figure 3.6 montre que l’algorithme GLM-UCB surpasse une fois de plus les deux autres même si l’écart entre l’algorithme UCB et l’algorithme GLM- UCB est moins important que dans l’exemple précédent. Étant donné le pouvoir peu prédictif des covariables dans cet exemple, il permet d’illustrer le potentiel de notre algorithme pour des applications de la vie réelle. Cependant, cette première expérience étant assez naïve et artificielle pour l’optimisation des ressources sur internet, nous considérons ci-dessous un modèle mieux adapté à ces données.