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

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

Temps de lecture : environ 13 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 approfondissement

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. Votre amie vous tend deux pièces pour jouer à pile ou face, une bleue et une rouge. Les règles sont les suivantes. Vous avez le droit à 1000 lancers. Pour chaque lancer vous pouvez choisir entre la pièce rouge et la pièce bleue. Si vous faites pile, vous gagnez un point ; si c’est face, vous ne gagnez rien. Votre défi : gagner le plus de points possible avec ces 1000 lancers.

Évidemment ces pièces sont truquées ! L’une donne plus souvent pile que l’autre, mais vous ne savez pas laquelle.

Pour réussir ce défi, il va vous falloir trouver la pièce qui fait le plus souvent pile. On va donc tester la pièce rouge et la pièce bleue pour compter le nombre moyen de fois où ces pièces font pile. Mais combien de lancers doit-on utiliser pour trouver la meilleure pièce ? Si l’on teste trop, on va gaspiller des lancers. Mais si l’on ne teste pas assez, on risque de lancer la mauvaise pièce et de faire un score ridiculement bas ! Explorer les différentes pièces ou exploiter celle que vous pensez être la meilleure, voilà un dilemme compliqué !

Ce défi vous semble inutile ? À la place de nos pièces, imaginez des playlists de rap et de pop. Et remplacez l’événement « la pièce fait pile » par « l’utilisateur écoute la musique plus de 30 secondes » : vous obtenez la base du système de recommandation de Spotify. De nombreux systèmes de recommandations correspondent à ce problème. On doit choisir entre plusieurs options pour maximiser une récompense. Cela peut être : proposer des playlists, des publicités, ou encore envoyer un mail de rappel. La récompense sera alors le temps d’écoute, un achat ou une réponse. Les comportements humains ne sont pas entièrement prévisibles. C’est cet aspect imprévisible que l’on veut modéliser par l’aléatoire du jeu pile ou face.

Trouver la bonne pièce

Revenons à notre jeu. On cherche à obtenir la plus grosse récompense. Une fois que l’on a choisi si l’on souhaite jouer avec la pièce rouge ou bleue, on a deux possibilités : soit on obtient « pile » et on gagne un point, soit on obtient « face » et on n’obtient aucun point supplémentaire. 1 point et 0 point sont les gains de chacune des pièces. Imaginons que vous lanciez une pièce équilibrée deux fois. La première fois vous obtenez pile, vous avez un point. La seconde fois vous obtenez face, vous n’avez pas de point. En moyenne, vous avez donc 1 point sur 2 lancers, soit un gain moyen de 1/2 = 0,5. De même, si vous faite trois fois pile et deux fois face, vous obtenez 3 points sur 5 lancers, soit un gain moyen de 3/5 = 0,6.

À partir de là, on peut calculer le gain que l’on attend en moyenne après un très grand nombre de lancers, que l’on appelle l’espérance du gain d’une pièce.

Commençons par poser les notations mathématiques :

  • E[Gain] est l’espérance du gain de la pièce, c’est ce que l’on cherche à connaître.
  • P(pile) représente la probabilité que le lancer de la pièce donne un pile.
  • P(face) représente la probabilité que le lancer de la pièce donne un face.
  • Gainpile est la valeur gagnée lorsque le lancer donne pile. Il vaut 1 point.
  • Gainface est la valeur gagnée lorsque le lancer donne face. Il vaut 0 point.

La formule s’écrit alors :

E[\mathrm{Gain}]
\, \, = P(\mathrm{pile}) \times \mathrm{Gain}_{\mathrm{pile}} + P(\mathrm{face})\times \mathrm{Gain}_{\mathrm{face}}
\, \, = P(\mathrm{pile}) \times 1 + P(\mathrm{face}) \times 0
\, \, = P(\mathrm{pile}) \times 1

C’est-à-dire que l’espérance du gain de chaque pièce est égal à la probabilité de faire pile avec cette pièce.

Ben voilà, on a résolu le problème ! Il suffit de regarder la moyenne de chaque pièce et d’utiliser celle qui a la plus grande moyenne.

Séparer théorie et réalité

Que de précipitation ! L’espérance et la moyenne, ça se ressemble, mais ce n’est pas la même chose. L’espérance et les probabilités sont des valeurs théoriques que l’on ne peut voir que sur le long terme, avec un très grand nombre de lancers . Si vous avez déjà joué à pile ou face, vous savez que jouer deux fois ne garantit pas d’avoir une fois pile et une fois face. Pour renforcer la distinction entre la moyenne théorique qu’est l’espérance, et la moyenne que l’on peut mesurer par l’expérience, on parle de moyenne empirique pour désigner cette dernière.

Sur la Figure 1, on a tracé la moyenne empirique d’une pièce équilibrée sur 1000 lancers. On voit clairement que la moyenne empirique (représentée par le trait bleu plein) n’est pas égale à l’espérance (représentée par les pointillés noirs). Même après 1000 lancers, il reste un écart.

Figure 1. Évolution de la moyenne empirique et de l’intervalle de confiance sur 1000 lancers, comparée à l’espérance d’une pièce équilibrée. L’intervalle de confiance représenté à un niveau de confiance à 90%.

La moyenne empirique ne nous permet pas de trouver la valeur de l’espérance. Au lieu de chercher à donner une valeur exacte à l’espérance, on va plutôt donner un intervalle où l’espérance devrait se trouver. Pour être plus précis, sur la Figure 1, la probabilité que l’espérance soit dans l’intervalle en bleu clair est supérieure à 90%. Cette probabilité de contenir la vraie valeur s’appelle le niveau de confiance. On parle alors d’un intervalle de confiance.

Vous pouvez constater que plus on fait de lancers, plus l’intervalle de confiance se rétrécit, et se rapproche de la moyenne empirique. Cela signifie que plus vous faites de lancers, plus vous avez confiance dans votre moyenne empirique. La bande de valeurs nécessaire pour avoir une confiance à 90% dans la valeur de l’espérance peut donc être encore plus petite si vous faites plus de lancers.

On a donc maintenant un outil (l’intervalle de confiance) qui nous permet de savoir à quel point on est sûr de notre estimation. Ce qui peut être très utile comme information avant de tout miser sur la pièce rouge ou bleue. Il ne reste plus qu’à trouver comment utiliser cette information.

Des stratégies qui ne fonctionnent pas

Commençons par une stratégie simple, voire trop simple : décider à l’avance du nombre d’essais avant de choisir quelle pièce jouer. Vous avez pu le remarquer, plus on utilise de lancers pour calculer la moyenne empirique, plus l’intervalle de confiance est petit. Il faudrait donc utiliser assez de lancers de la pièce rouge et de la pièce bleue pour décider quelle est la meilleure pièce avec une grande confiance.

Utiliser l’intervalle de confiance est une superbe idée, mais ce niveau de confiance va dépendre des pièces. Prenons deux exemples extrêmes. Si l’espérance (théorique, donc) du gain de la pièce rouge est de 0,7 et celle de la pièce bleue 0,3, vous devriez assez vite déterminer que la pièce rouge est plus intéressante. Par contre, si l’espérance de la pièce rouge est de 0,6 et celle de la pièce bleue 0,5, il va falloir beaucoup plus de lancers pour vous apercevoir que la pièce rouge est meilleure que la pièce bleue.

C’est ce dilemme qui est représenté Figure 2 : la situation 1 présente le cas où les espérances des pièces rouge et bleue sont bien distinctes (0,7 et 0,3, respectivement). On peut alors se contenter de larges intervalles de confiance pour distinguer le gain de chaque pièce, et on a donc besoin de peu d’essais. La situation 2 présente des espérances plus proches (pièce rouge : 0,6 ; pièce bleue : 0,5). Avec le même intervalle de confiance que dans la situation 1, il devient impossible de départager les deux pièces pour comprendre laquelle est la meilleure. Pour réussir à les distinguer, il faudra donc réduire davantage l’intervalle de confiance pour éviter qu’ils ne se superposent, c’est ce qui est illustré à la situation 3. Réduire un intervalle de confiance, comme on l’a vu sur la Figure 1, nécessite de faire davantage de lancers.

Figure 2. Espérance du gain et intervalles de confiance associés pour diverses situations.

Conclusion sur cette stratégie : fixer à l’avance le nombre d’essais n’est pas possible, car le nombre de lancers nécessaires pour distinguer les deux pièces dépend de la valeur de leur espérance. Or, c’est justement cette valeur-là que l’on cherche. C’est un serpent qui se mord la queue ! Il nous faut donc une stratégie un peu plus complexe !

La stratégie UCB

Voici la solution proposée par les chercheurs dans la publication qui nous intéresse aujourd’hui. Les auteurs l’ont baptisée UCB pour Upper Confidence Bound (ou borne supérieure de l’intervalle de confiance, en français) qui est une stratégie dite optimiste. Regardons comment elle fonctionne. 

La Figure 3 représente deux autres situations. Vous pouvez voir que la moyenne empirique de la pièce rouge est dans les deux cas plus élevée que celle de la bleue (0,8 pour la rouge et 0,6 pour la bleue). De plus, la pièce bleue a un intervalle de confiance plus large dans les deux situations. Ce qui signifie que l’on a moins testé la pièce bleue que la pièce rouge. Dans ces situations, vaut-il mieux jouer la pièce rouge ou la pièce bleue ? La rouge semble plus intéressante, car sa moyenne empirique est plus haute que celle de bleue. Mais la pièce bleue a une forte incertitude. Il se pourrait alors que l’espérance de la pièce bleue soit en réalité plus grande que celle de la rouge. Il faudrait alors lancer la pièce bleue pour réduire son incertitude.

Figure 3. Deux situations représentées par la moyenne empirique et l’intervalle de confiance des pièces.

La première possibilité revient à faire confiance aux moyennes empiriques, en exploitant la pièce qui semble être la plus rentable, soit la rouge. La deuxième possibilité est d’explorer la pièce bleue, même si elle n’a pas la meilleur moyenne. Cette exploration nous permettrait d’éviter de choisir la mauvaise pièce.

Pour choisir entre exploration et exploitation, la stratégie UCB vous conseille de ne pas regarder la moyenne empirique pour prendre votre décision, ni la taille de l’intervalle de confiance, mais plutôt de vous intéresser à la borne supérieure de l’intervalle de confiance. En effet, un optimiste ne va pas se dire « l’espérance est comprise dans cet intervalle ». Un optimiste va se dire « avec un peu de chance, l’espérance est tout en haut de cet intervalle ».

Prenons la situation 4 de la Figure 3. L’intervalle de confiance bleu va plus haut que l’intervalle de confiance rouge. Notre optimiste va donc choisir la pièce bleue, car c’est cette pièce qui peut potentiellement donner le plus gros gain. En lançant cette pièce plusieurs fois, il réduit son intervalle de confiance. Il se retrouve alors dans la situation 5. L’intervalle de confiance de la pièce bleue est réduit, et la moyenne était probablement bien évaluée, car elle n’a pas bougé avec ces lancers. Maintenant que l’on a confirmé que jouer la pièce bleue n’était pas si intéressant que ça, et que la borne supérieure la plus haute est désormais celle de la pièce rouge, c’est elle que l’on va jouer, jusqu’à ce que la borne supérieure de son intervalle de confiance passe à nouveau sous celle de la pièce bleue. À ce moment-là, on confirmera en jouant la pièce bleue que la moyenne de bleue n’est pas tout en haut de l’intervalle de confiance (ce qui en ferait le choix privilégié), et ainsi de suite.

Et voilà, ce n’est pas plus compliqué que cela : calculer l’intervalle de confiance, jouer la pièce dont l’intervalle de confiance a la borne supérieure la plus haute, et recommencer. Cette stratégie, UCB, est intéressante car simple à calculer. Mais surtout, on peut démontrer que le nombre de fois où vous allez lancer la mauvaise pièce est très faible.

Garanties

Cette stratégie apporte une garantie assez forte : sur N (un nombre entier quelconque) lancers, le nombre de fois où vous allez choisir la mauvais pièce est très faible. Il est de l’ordre de log(N), c’est à dire qu’il suit une croissance logarithmique. Vous ne savez pas ce qu’est une croissance logarithmique ? En voici un exemple :

Figure 4. Représentation de la fonction logarithmique y = log(x). Notez la différence entre l’axe des x qui va de 0 à 1000, et l’axe des y qui va de seulement 0 à 10. 

C’est l’une des fonctions les plus lentes. Et c’est très bien dans notre cas, car cela veut dire que quand on continue à jouer (que l’on augmente N le nombre de lancers), le nombre d’erreurs n’augmente presque pas. D’ailleurs, il a été montré que le nombre d’erreurs théoriques ne pourrait dans tous les cas pas être plus faible que log(N). Cette stratégie est donc très performante [1] !

Intuition de la preuve

Pour vous convaincre que cette stratégie fonctionne vraiment bien, je ne peux pas vous faire la démonstration complète qui demande des notions plus approfondies de mathématiques, mais je peux vous donner une idée de comment démontrer ce genre de résultat.

Pour simplifier le problème, imaginons que l’on a le choix entre une pièce dorée et une pièce argentée, la pièce dorée ayant une espérance de gain plus grande que la pièce argentée. La question est donc : sur N lancers, quel est le nombre maximal de fois où la pièce argentée sera choisie ?

Comme on utilise UCB, cela revient à compter le nombre de fois où le maximum de l’intervalle de confiance associé à la pièce argentée est supérieur à celui de la pièce dorée. Si l’on pose l’équation, on peut montrer qu’il faut au moins qu’une des trois conditions suivantes soit vérifiée pour que UCB préfère la pièce argentée à la dorée :

  • la moyenne empirique de la pièce dorée sous-estime largement la vraie moyenne ;
  • la moyenne empirique de la pièce argentée surestime largement la vraie moyenne ;
  • l’intervalle de confiance associé à la pièce argentée est beaucoup trop grand.

Les deux premiers cas correspondent aux moments où, par chance ou malchance, les gains obtenus sont très différents que ce que l’on aurait pu espérer (par exemple, on avait 1 chance sur deux de gagner, mais en fait on a gagné 5 fois d’affilée). Dans ces cas, la moyenne empirique sort de l’intervalle de confiance. Or, l’intervalle de confiance est conçu, par définition, pour que la probabilité d’en sortir diminue très vite. Tellement vite que ces deux premiers cas sont négligeables : ils n’arrivent que très rarement, trop rarement pour que notre stratégie les prenne en compte.

Il reste donc le cas où l’on choisit la mauvaise pièce car l’intervalle de confiance est trop grand. Vous l’aurez deviné, c’est ce dernier cas qui est responsable de la croissance logarithmique log(N) du nombre d’erreurs. Si vous vous rappelez de la Figure 3, on a dû jouer la pièce bleue pour diminuer son intervalle de confiance et s’assurer que la pièce rouge était bien la meilleure. Sur N lancers, il faudra donc utiliser log(N) lancers de la mauvaise pièce pour diminuer suffisamment son intervalle de confiance. Ce qui est aussi peu que l’on puisse espérer.

Conclusion

Vous avez maintenant une stratégie dont vous pouvez prouver que le nombre d’erreurs que vous ferez sera proche de la limite théorique. Pour jouer à pile ou face, ce n’est peut être pas très utile, mais le publicitaire ou les systèmes de recommandations ont un grand intérêt à avoir des stratégies qui font le moins d’erreurs possibles.

Évidemment, les chercheurs ne se sont pas arrêtés à ce problème de pile ou face à deux pièces. Habituellement l’image utilisée est celle des machines à sous. Le problème est le même : trouver la machine qui a la meilleure espérance. Mais on n’a plus que deux machines, et surtout les événements possibles sont plus variés que pile/face.

À partir de ce problème, des chercheuses et chercheurs se sont demandés comment faire si l’espérance des machines dépend de leur position dans le casino. Ou que faire si l’espérance des gains évolue au cours du temps. Il y a de nombreuses variantes que l’on réunit sous le nom de problème des bandits manchots, car les machines à sous dans les casinos s’appellent des bandits manchots. Elles vous volent votre argent et n’ont qu’un seul bras, le levier à tirer pour la faire fonctionner. Ces variantes sont nombreuses, mais c’est toujours la même idée : contrôler l’incertitude pour prendre une bonne décision.

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

_________

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

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.