Déjouer le hasard à Las Vegas
À CONDITION DE DISPOSER DE FONDS ILLIMITÉS, VOUS POUVEZ METTRE EN PLACE UNE STRATÉGIE OPTIMALE
Las Vegas, Nevada. Vous posez vos valises pour les vacances dans l’enfer du jeu (ou le paradis des joueurs) ! Vos connaissances en probabilités si chèrement acquises vont enfin vous être utiles. Toutefois, dès la porte du casino passée, vous êtes frappé par la démesure des lieux : des dizaines de machines à sous alignées devant vous, toutes différentes et en même temps toutes un peu semblables. Comment choisir celle qui vous apportera le jackpot ? Vous sentant sous un bon jour, vous optez pour une machine, puis jouez continuellement avec elle. Comme vous n’avez aucune certitude que cette machine soit la meilleure, vous comprenez que cette stratégie ne maximisera sans doute pas vos gains.
CHANGER DE MACHINE À
SOUS au hasard après chaque coup est donc une autre idée. Cette exploration permanente des possibles n’est pas non plus optimale, puisque, d’après la loi des grands nombres, votre gain approche le gain moyen des machines. Alors faut-il plutôt changer régulièrement de machine et s’arrêter sur celle qui vous donne la meilleure moyenne de gain ? L’exploitation des résultats déjà obtenus est en apparence convaincante, mais les calculs dénient encore le caractère optimal. Une meilleure conduite serait de consacrer vos premiers jetons à explorer toutes les machines pour trouver la meilleure, puis de ne jouer que sur cette dernière. La sagesse consiste donc à privilégier l’exploration pure avant de passer à l’exploitation. Encore faut-il savoir quand basculer d’une phase à l’autre ! Vous pourriez décider de consacrer une somme donnée (dix jetons par machine, par exemple), calculer les gains collectés sur chaque machine et choisir la plus généreuse. Hélas, rien n’empêche une machine qui possède une faible probabilité de gain de sortir une bonne série… Aussi pourrait-on décider de s’arrêter quand le gain sur une machine devient « significativement » supérieur au gain sur les autres machines. Mais là encore, les calculs le montrent : on n’est toujours pas à l’abri d’une série trop favorable sur une mauvaise machine.
POUR METTRE TOUTES LES CHANCES de votre côté, vous pouvez alors dégainer un outil efficace : les intervalles de confiance. Calculés à partir des résultats, ils contiennent la probabilité de gain sur une machine donnée avec une grande certitude (fixée au préalable). Grâce à cet outil, le temps d’arrêt de la première phase est calculé comme le moment où l’intervalle de confiance de la machine la plus rentable (c’est-à-dire sa borne inférieure) est au-dessus des intervalles de confiance des autres (c’est-à-dire de leurs bornes supérieures). En choisissant convenablement la méthode de construction de l’intervalle de confiance, on obtient l’algorithme Kullback-Leibler UCB (pour Upper Confidence Bound). L’équipe internationale d’Olivier Cappé a montré en 2013 que cet algorithme était optimal au bout d’un temps asymptotiquement long (1). Autrement dit, à condition de disposer de fonds illimités, vous pouvez mettre en place une stratégie optimale. Cela semble bien compliqué pour des vacances ! Il faut alors comprendre que la machine à sous n’est qu’un analogue commode pour de nombreuses situations où ce type de statistique en milieu aléatoire intervient : la prescription d’un médicament à un malade, l’affichage d’une publicité dans votre navigateur, etc. De tels algorithmes ont certainement déjà été utilisés pour des prises de décision vous concernant. Mais à votre insu ! (1) O. Cappé et al., Ann. Statist., 41 , 1516, 2013.