Comment prendre une décision dans un monde incertain ? (Approfondissement)

Écriture : Alexandre Fauquette
Relecture de contenu : Thomas Merly-Alpa
Relecture de forme : Alexandre This

Temps de lecture : environ 10 minutes.
Thématiques : Statistique & Probabilités (Mathématiques) ; Intelligence artificielle (Informatique et Sciences cognitives)

Publication originale : Auer P. et al., Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 2020 DOI : 10.1023/A:1013689704352

Version curiosité

Prendre une décision est un problème complexe, mais il y a pire encore : prendre une décision sans en connaître à l’avance les conséquences. Pourtant notre monde est rempli d’incertitudes, et une intelligence artificielle digne de ce nom devra en être capable. L’article dont on parle ici présente l’un des principaux résultats théoriques sur la prise de décision dans un environnement incertain.

Comment prendre une bonne décision ?

Notre histoire commence par un défi. Vous vous trouvez avec une mathématicienne dans un casino un peu particulier, il contient 3 machines différentes. Votre amie vous tend 1000 jetons d’un air malicieux et vous met au défi de gagner le plus d’argent possible avec ces 1000 jetons. Les machines de ce casino sont différentes : pour un jeton joué, le gain moyen n’est pas le même partout. Évidemment, le gain moyen de chaque machine est top secret ! Et votre amie ne vous a évidemment pas dit quelle machine est la plus généreuse en moyenne.

Pour répondre à ce défi, une stratégie consiste à chercher la meilleure machine. Il faut donc commencer par toutes les tester. Mais combien de jetons faut-il consacrer à ces tests ? Si vous passez trop de temps à tester les machines, vous gaspillez vos jetons. Mais si vous ne testez pas assez, vous risquez de tout miser sur la mauvaise machine. Explorer les différentes machines ou exploiter celle que vous pensez être la meilleure, voilà un dilemme compliqué !

Cette histoire de casino vous semble tirée par les cheveux ? Remplacez les machines à sous par des playlists musicales, et le jackpot par le fait qu’un utilisateur écoute plus de 30 secondes la musique, et vous obtenez la base du moteur de recommandation de Spotify. De nombreux systèmes de recommandations correspondent à ce problème : on doit choisir entre plusieurs options (les machines) pour maximiser une récompense (une interaction avec l’utilisateur). Les comportements humains ne sont pas entièrement prévisibles ; cela correspond au côté aléatoire des machines à sous.

Sans plus attendre : la solution

Vous voulez la solution du problème ? Avant cela, il faut se demander à partir de quand on considère qu’une solution est bonne. Est-ce que l’on sera content si l’on ne s’est trompé de machine que 10 fois, 100 fois ou 200 fois ? En 1985, T.L Lai et Herbert Robbins ont démontré que lorsque le nombre de jetons tend vers l’infini, on va se tromper de machine au moins un nombre logarithmique de fois [1]. Autrement dit, pour un nombre de jetons T grand, on est obligé d’en utiliser un certain nombre pour tester les différentes machines. Ce nombre d’erreurs grandit comme log(T) que l’on note habituellement \mathcal{O}(log(T)). Pour être précis, si vous trouvez une stratégie qui fait moins de log(T) essais, il existe au moins un casino dans lequel elle se trompera royalement. En plus de ce résultat, ils donnent une méthode qui, lorsque T tend vers l’infini, se trompe au plus \mathcal{O}(log(T)) fois.

Génial ! ces deux chercheurs ont réussi à prouver que pour T tendant vers l’infini, on ne peut pas faire moins que \mathcal{O}(log(T)) erreurs. Et ils proposent une méthode qui garanti un nombre d’erreur lui aussi en \mathcal{O}(log(T)). On sait donc qu’une bonne solution doit faire asymptotiquement \mathcal{O}(log(T)) erreurs. Cependant, votre amie vous a donné 1000 jetons. C’est beaucoup, mais pas une infinité. De plus, je ne vous l’ai pas dit, mais la solution qu’ils proposent est un peu complexe à calculer. Heureusement pour vous, en 2002, P. Auer, N. Cesa-Bianchi et P. Fisher ont proposé une méthode avec un résultat garanti pour un nombre de jetons T fini, qui donne aussi un nombre d’erreurs en \mathcal{O}(log(T)). En plus leur méthode est nettement plus simple à mettre en place !

Pour chaque machine a, vous devez connaître na qui est le nombre de jetons déjà joués avec cette machine, et \overline{X}_a la moyenne empirique des récompenses de cette même machine. À chaque fois que vous jouez la machine a, il faudra augmenter na de 1 et mettre à jour \overline{X}_a pour prendre en compte la récompense obtenue. Dernière information à connaître : t le nombre de jetons déjà utilisés sur l’ensemble des machines. Vous connaissez les ingrédients (\overline{X}_a, na et t). Il ne manque plus que la recette.

Pour maximiser votre récompense, vous devez :

  1. Calculer pour chaque machine a son indice donné par la formule suivante : \overline{X}_a + \sqrt{\frac{2\mathrm{log} (t)}{n_a}}
  2. Jouer la machine qui a le plus grand indice.
  3. Utiliser la récompense obtenue pour mettre à jour vos valeurs (\overline{X}_a et na) puis recommencer.

Une solution optimiste

Le terme de gauche \overline{X}_a ne devrait pas vous surprendre. On cherche la machine qui donne le meilleur résultat en moyenne. Il est donc logique de calculer la moyenne de ses résultats. Le problème c’est qu’avec la moyenne seule nous n’avons pas assez d’informations. Tentons de comprendre pourquoi.

Imaginez que je lance un dé pour vérifier qu’il n’est pas truqué. La moyenne des points obtenus devrait être de 3,5 (l’espérance d’un dé classique non truqué). Pourtant au début je ne pas vais pas forcément trouver cette valeur. La Figure 1 montre l’évolution de la moyenne empirique calculée sur 1000 lancers de dé. On voit qu’il faut attendre un certain nombre de lancers avant de s’approcher des 3,5 attendus. On a donc d’un côté la moyenne théorique du dé que l’on appelle espérance \mu_{\text{d\'e}}= 3,5 et de l’autre la moyenne mesurée \overline{X}_{\text{d\'e}}(t) qui est aléatoire mais se rapproche de \mu_{\text{d\'e}}= 3,5 quand t grandit.

Figure 1. Évolution de la moyenne empirique d’un dé non truqué sur 1000 lancers.

On a répété cette expérience 100 fois sur la Figure 2. On voit que toutes les moyennes se rapprochent de l’espérance quand le nombre de lancers augmente, un peu comme si elles entraient dans un goulot d’étranglement. On est capable de mesurer ce rapprochement, grâce aux inégalités de concentration. L’inégalité que l’on va utiliser ici est celle de Chernoff-Hoeffding qui dit (sous certaines conditions) que :

P\left(\overline{X}_a + \sqrt{\frac{x}{n_a}} \leq \mu_a\right) \leq \mathrm{e}^{-2x} et P\left(\overline{X}_a - \sqrt{\frac{x}{n_a}} \geq \mu_a\right) \leq \mathrm{e}^{-2x}

Figure 2. Évolution de la moyenne d’un dé non truqué sur 1000 lancers. L’expérience est répétée 100 fois.

On peut regrouper ces deux inégalités pour obtenir :

P\left(\overline{X}_a - \sqrt{\frac{x}{n_a}} < \mu_a < \overline{X}_a + \sqrt{\frac{x}{n_a}} \right) \geq 1- 2 \mathrm{e}^{-2x}

On parle alors d’un intervalle de confiance. Mais une valeur pour approximer l’espérance \mu_{a}, ce n’est pas assez informatif. En complément, on propose l’intervalle \left[\overline{X}_a-\sqrt{\frac{x}{n_a}}\ ,\ \overline{X}_a+\sqrt{\frac{x}{n_a}}\right] qui va nous donner le niveau de confiance la valeur \overline{X}_a. Cet intervalle est construit pour être suffisamment étroit, tout en garantissant que la probabilité qu’il contienne \mu_a soit plus grande que 1-2\mathrm{e}^{-2x}. Évidemment, plus l’intervalle est grand, plus il est facile d’avoir un niveau de confiance élevé. Le cas extrême étant de dire que \mu_a est compris entre -\infty et +\infty avec une probabilité de 1. Le niveau de confiance est maximal, mais l’intervalle est infiniment trop large pour apporter une information utile.

Vous avez sans doute remarqué le lien avec notre formule de départ : \overline{X}_a + \sqrt{\frac{2\mathrm{log} (t)}{n_a}}. En prenant x = 2 log(t), on retrouve effectivement la formule de l’indice. De plus, on obtient que la probabilité que \mu_a soit supérieur à \overline{X}_a + \sqrt{\frac{2\mathrm{log} (t)}{n_a}} est inférieure à t^{-4}. Le choix d’utiliser x = 2 log(t) peut vous sembler arbitraire. Mais quand on rédige la preuve, on réalise que les événements ayant une probabilité de l’ordre de t^{-4} peuvent être négligé. C’est donc pour pouvoir négliger ces situations que l’on prend comme indice \overline{X}_a + \sqrt{\frac{2\mathrm{log} (t)}{n_a}}.

Pour information, cet algorithme s’appelle UCB pour Upper Confidence Bound, qui peut se traduire par « borne supérieure de l’intervalle de confiance ». Il porte bien son nom, car on compare les machines en utilisant la borne supérieure de leur intervalle de confiance. Si vous voulez une interprétation plus humaine, sachez que l’on parle de stratégie optimiste. Avec cette stratégie, vous ne jouez pas la machine avec la meilleure moyenne. Vous jouez celle qui pourrait avoir la meilleure moyenne pour un niveau de confiance fixé. En effet, dans cette situation, un optimiste va se dire « avec un peu de chance, l’espérance est tout en haut de cet intervalle de confiance ».

Pour vous convaincre de l’intérêt d’être optimiste, prenez l’évolution présentée à la Figure 3. On a une machine bleue et une machine rouge dont l’espérance des gains est respectivement 0,5 (bleue) et 0,6 (rouge). Sur la figure, vous pouvez voir l’évolution des moyennes empiriques de ces deux machines. Pendant les 50 premiers essais, on pourrait penser que la machine bleue est meilleure que la rouge, et il faut attendre environ 200 essais avant que l’on puisse clairement voir une distinction entre les machines bleue et rouge.

Figure 3. Évolution des moyennes empiriques et leurs espérances respectives. Le choix de tester la machine bleue ou rouge est pris en suivant la stratégie présentée : UCB.

Dans cet exemple, si vous vous fiez uniquement à la moyenne au début, c’est la catastrophe ! La moyenne de la machine bleue est surestimée, et celle de la machine rouge rouge sous-estimée. Heureusement, l’indice qui correspond à la borne supérieure de l’intervalle de confiance permet de prendre en compte la part d’erreur contenue dans le hasard des premiers coups.

Figure 4. Expérience identique à celle de la Figure 3 avec en plus l’évolution de l’indice justifiant le choix de tester la machine rouge ou bleu. On note que lorsque l’indice de la machine bleue est plus petit que celui de la rouge, sa moyenne ne varie pas, car c’est la machine rouge et non la bleue qui est choisie.

Si maintenant on regarde l’évolution de notre stratégie sur la Figure 5, on peut voir que malgré le manque de chance que nous avons eu au début, la machine rouge devient rapidement la plus utilisée. La machine bleue est quand même testée de temps en temps pour s’assurer que sa moyenne est bien estimée. Cette vérification se fait de moins en moins souvent, car on gagne en confiance sur notre estimation. On peut voir deux régimes sur ce graphique. Au début, les machines rouge et bleue sont testées toutes deux un nombre de fois similaires. Puis au bout d’un moment (200 essais) le nombre d’essais avec la machine bleue ralenti. On rentre dans un régime où le nombre d’erreurs suit une croissance logarithmique.

Figure 5. Évolution du nombre d’essais effectués sur les deux machines. Après 200 essais équitablement répartis entre les machines bleue et rouge, UCB abandonne la machine bleue pour privilégier la rouge.

L’avantage des stratégies optimistes, c’est que soit vous jouez la bonne machine et c’est super ! Soit vous vous trompez et cela va réduire l’intervalle de confiance : vous choisirez alors mieux votre machine au tour suivant. Vous êtes gagnant dans les deux cas.

Et la preuve dans tout ça ?

Vous vous demandez sans doute comment on peut prouver qu’à tout moment le nombre d’erreurs de l’algorithme UCB est en \mathcal{O}(log(T)). L’idée générale, c’est de majorer le nombre de fois où l’on teste une machine a qui n’est pas optimale. Par convention, on note la meilleure machine avec une étoile.

Si vous avez joué la machine a à un instant t, c’est qu’à ce moment, l’indice de la machine a : \overline{X}_a + \sqrt{\frac{2\mathrm{log} (t)}{n_a}} était plus grand que l’indice de toutes les autres machines. Et donc il était plus grand que celui de la meilleure machine. Pour simplifier le problème, on ne va pas compter le nombre de fois où l’on a joué la machine a mais le nombre de fois où on aurait préféré jouer la machine a au lieu de étoile (la meilleure machine). Ce qui correspond à trouver le nombre de fois où :

\overline{X}_a + \sqrt{\frac{2\mathrm{log} (t)}{n_a}} > \overline{X}_* + \sqrt{\frac{2\mathrm{log} (t)}{n_*}}

La suite de la preuve consiste à décomposer cette inégalité en trois. Si notre inégalité est vraie, alors au moins l’une des inégalités suivantes est vraie :

  • \overline{X}_a \geq \mu_a +\sqrt{\frac{2\mathrm{log} (t)}{n_a}}
  • \overline{X}_* \leq \mu_* -\sqrt{\frac{2\mathrm{log} (t)}{n_*}}
  • \mu_* \leq \mu_a +2\sqrt{\frac{2\mathrm{log} (t)}{n_a}}

C’est un résultat classique sur les inégalités : si A < B alors vous pouvez prendre n’importe quels nombres C et D et vous aurez A < C ou D < B ou C < D. Pour obtenir le triplet ci-dessus, il faut prendre C = \mu et D = \mu_a + 2\sqrt{\frac{2\mathrm{log} (t)}{n_a}}

Comme l’inégalité qui nous intéresse implique au moins l’une des trois inégalités précédentes, on peut majorer la probabilité de préférer la machine a à la meilleur machine comme ceci :

P\left(\overline{X}_a + \sqrt{\frac{2\mathrm{log} (t)}{n_a}} >  \overline{X}_* + \sqrt{\frac{2\mathrm{log} (t)}{n_*}}\right) \leq P\left(\overline{X}_a \geq \mu_a + \sqrt{\frac{2\mathrm{log} (t)}{n_a}}\right)  + P\left(\overline{X}_* \leq \mu_* - \sqrt{\frac{2\mathrm{log} (t)}{n_*}}\right) + P\left( \mu_* \leq \mu_a+ 2 \sqrt{\frac{2\mathrm{log} (t)}{n_a}}  \right)

La probabilité que la première inégalité soit vraie est inférieure à t^{-4} grâce à l’inégalité de concentration de Chernoff-Hoeffding dont on a parlé précédemment. C’est exactement la même chose pour la deuxième inégalité. Il ne nous reste plus que la troisième. Cette inégalité est fausse lorsque n_a \geq \frac{8 \mathrm{log}(t)}{(\mu_*-\mu_a)^2}.

Comme par définition t \leq T, on peut simplifier l’inéquation par n_a \geq \frac{8 \mathrm{log}(T)}{(\mu_*-\mu_a)^2} \geq \frac{8 \mathrm{log}(t)}{(\mu_*-\mu_a)^2}. Donc pour n_a \geq \frac{8 \mathrm{log}(T)}{(\mu_*-\mu_a)^2} la troisième probabilité est nulle. On obtient alors :

n_a \geq \frac{8 \mathrm{log}(T)}{(\mu_*-\mu_a)^2} \Rightarrow P\left(\overline{X}_a + \sqrt{\frac{2\mathrm{log} (t)}{n_a}} > \overline{X}. + \sqrt{\frac{2\mathrm{log} (t)}{n_*}}\right) \leq t^{-4} + t^{-4} + 0

Cette implication nous dit que quand n_a dépasse \frac{8 \mathrm{log}(T)}{(\mu_*-\mu_a)^2}, la probabilité de préférer la machine a est négligeable. On a donc bien un nombre d’erreurs en \mathcal{O}(log(T)). En fait, l’inégalité exacte est la suivante, mais les calculs qui permettent d’y arriver ne présentent pas d’intérêt. Si cela vous intéresse, vous pouvez aller lire la preuve dans la publication originale [2] .

\mathrm{E}[n_a(T)] \leq \frac{8}{(\mu_*-\mu_a)^2}\mathrm{log}(T) + 1 + \frac{\pi^2}{3} = \mathcal{O}(\mathrm{log}(T))

Conclusion : si vous suivez la stratégie UCB que l’on vient de présenter qui, pour rappel, vous demande de calculer à chaque fois l’indice \overline{X}_a + \sqrt{\frac{2\mathrm{log} (t)}{n_a}} pour toutes les machines et de jouer un jeton dans la machine ayant le plus grand indice, alors vous avez la garantie (en espérance) que le nombre de fois où vous jouerez une mauvaise machine a ne peut pas dépasser :

\frac{8}{(\mu_*-\mu_a)^2}\mathrm{log}(1000) + 1 + \frac{\pi^2}{3}

Fini de jouer au petit bonheur la chance : vous avez maintenant une stratégie dont l’efficacité est prouvée !

Pour aller plus loin

Cette méthode est la première d’une longue série. Il y a eu des améliorations de l’algorithme, comme KL-UCB dont les garanties sont encore plus proches de la limite théorique que UCB [3]. En effet, on sait que asymptotiquement, le nombre d’erreurs est un \mathcal{O}(log(T)). Le résultat est plus précis que cela, car on connaît le coefficient devant le logarithme. Et bien KL-UCB obtient une garantie avec exactement ce coefficient.

Le fonctionnement de KL-UCB est très proche de UCB. Dans les deux cas, on regarde toutes les configurations de machines crédibles et on va jouer sur la machine qui pourrait avoir la meilleure récompense parmi toutes les possibilités crédibles

La différence, c’est la définition de ce qui est crédible. Dans UCB, on considère comme crédibles toutes les configurations dont la moyenne est dans l’intervalle de confiance. Alors que dans KL-UCB, on utilise la divergence de Kullback-Leibler (notée KL) pour quantifier l’écart entre nos observations et une configuration de machines.

Les chercheur·e·s ont aussi créé plein de variantes du problème : que se passe-t-il si l’on sait que des machines proches donnent des récompenses similaires ? Comment agir si l’on sait que les machines sont truquées ? Comment faire face à une infinité de machines ? Que se passe-t-il si l’on est plusieurs à jouer dans le casino ? 

Les variations de ce problème sont nombreuses, mais c’est toujours la même idée : contrôler l’incertitude pour prendre une bonne décision. Si vous voulez en savoir plus sur le sujet, Emilie Kaufmann, chercheuse à l’Inria, a présenté un excellent exposé Math Park que vous pouvez retrouver ici.

Petit rappel avant de se quitter, les jeux d’argent sont d’excellents moyens de parler de probabilités. Mais dans la vraie vie, toutes les machines sont perdantes en moyenne. Jouer comporte des risques, ne les négligeons pas. Pour plus d’informations, rendez-vous sur https://www.joueurs-info-service.fr/.

_________

[1] L’article historique sur la borne minimale : Lai T.L. & Robbins H., Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics, 1985. DOI : 10.1016/0196-8858(85)90002-8

[2] La preuve complète d’UCB est accessible dans la publication originale. Il s’agit du théorème 1 et de la preuve associée.

[3] L’article d’origine sur KL-UCB : Garivier A. & Cappé O., The KL-UCB Algorithm for Bounded Stochastic Bandits and Beyond. Conference On Learning Theory, 2011.

_________

Creative Commons License
Alexandre Fauquette/Papier-Mâché/CC BY 4.0

Votre commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.