A l'origine du A/B testing : le "multi-armed bandit"

Publié le 04 janvier 2021

6 minutes de lecture

Machine à sous de casino - Image de Carl Rax sur Unsplash

Nous avons présenté dans un précédent article les principes du A/B testing qui consiste à proposer différentes versions d’un objet aux consommateurs en ne modifiant qu’un seul paramètre. Nous allons maintenant étudier plus en détail l’origine du A/B Testing et en particulier la théorie des bandits Manchots.

A l’origine du A/B testing : les problèmes dits de « Bandit Manchot » (multi-armed bandit)

Imaginons que nous sommes dans un casino, en face d’une rangée de machines à sous (historiquement appelées « bandits manchots », à cause de leur levier rappelant un bras et de leur propension à voler l’argent). Chaque machine est différente : certaines donnent fréquemment des petits gains, et certaines donnent rarement un énorme jackpot. Comment savoir quelle machine est la plus rentable ? Il va falloir au début répartir ses jetons pour se faire une idée du profil de gain de chaque machine, puis, au fur et à mesure que la connaissance se fait plus précise, réduire les paris les moins rentables.

En face de ces trois machines, comment savoir laquelle est la plus rentable ? Dans cette figure, nous jouons cinq jetons dans chaque machine. La machine marron semble donner fréquemment des petits gains, la machine rouge rarement des gros gains, et la machine bleue semble avoir un comportement intermédiaire. Nous avons donc déjà une idée du profil de gain de chaque machine, mais aucune certitude statistique. Evidemment, si nous connaissions déjà la meilleure machine, nous ne parierions que sur celle ci. Malheureusement, ce n’est pas le cas, et nous allons devoir dépenser des jetons pour savoir laquelle est la meilleure. C’est le prix de la connaissance.

Exploration et exploitation

Ce problème est très similaire à la question du A/B testing : en présentant deux traitements différents aux utilisateurs, on prend le risque que l’un des traitements soit moins efficaces, et donc de réduire notre gain total (pour être exact, on ne réduit pas le gain total, on réduit le gain par rapport à l’espérance de gain optimale, c’est à dire le gain que l’on aurait eu si dès le début tous les utilisateurs avaient vu la meilleure branche.) Dans le jargon des sciences des données, nous nommons celà la recherche de l’équilibre entre l’exploration et l’exploitation. L’exploration sert à améliorer la connaissance du problème, et l’exploitation consiste à utiliser les « méthodes qui marchent ».

Cette figure symbolise le profil de gain des différentes machines. Si l’on insère dans chaque machine un grand nombre de jetons, on peut représenter la fréquence des gains (courbes colorées). Ici, on ne représente pas les gains nuls (on insère un jeton et l’on ne gagne rien). Une fois la fréquence des gains établi, il est facile de déterminer quelle machine est la plus rentable : il suffit de sommer tous les gains.

Formalisation des problèmes de bandits manchots multiples (Multi-armed bandits)

Nous allons maintenant commencer à mathématiser notre approche. Les problèmes de multiples bandits manchots sont des problèmes simples d’apprentissage par renforcement (reinforcement learning). Nous avons un agent (le joueur) qui choisit des actions, et chaque action implique une récompense (possiblement nulle). Ces récompenses dépendent de distributions de probabilités sous-jacentes, inconnues au début de l’exploration du problème. Une partie se joue sur un grand nombre d’épisodes, que nous appèlerons $N$ (dans notre cas, un épisode est équivalent à une action.) Le but est tout simplement de maximiser la récompense sur le long de la partie.

Une première ébauche de stratégie

Nous allons considérer ici que nous somme face à k machines. Notre première stratégie, que l’on appelle classiquement une stratégie « avide » (greedy, dans la littérature anglo-saxonne). Les $k$ premières actions de notre agent vont consister à insérer une pièce dans chaque machine, et a observer la récompense obtenue. C’est la phase d’exploration de l’environnement. Ensuite, il utilisera ses actions jusqu’à la fin de la partie sur la machine qui a donnée la meilleure récompense lors de la phase d’exploration, sans plus se soucier des autres machines. Il effectuera donc $N - k$ fois la même action durant cette phase (phase d’exploitation). Cette approche est intéressante, mais elle a un problème majeur : si la récompense donnée par une machine lors de la phase d’exploration n’est pas représentative de la distribution sous-jacente à cette machine, l’agent va alors parier tous ses jetons sur la mauvaise machine.

Valeur d’une action et regret cumulé

Nous allons définir un estimateur $Q_t(a)$ :

Q_t(a) = \mathbb{E}[R_n | A_n = a]

Avec $Q_t(a)$ l’estimateur, R_n la récompense attendue et $A_n$ l’action choisie à l’épisode $n$ . L’équation si dessus se lit donc de la façon suivante : on construit un estimateur $Q_t(a)$ de la qualité d’une action à partir de l’espérance mathématique (l’équivalent de la moyenne en probabilité) de la récompense $R_n$ obtenue sachant que l’on a choisi l’action $A_n$ parmi toutes les actions $a$ possibles.

A gauche : on représente en rouge la récompense que l’agent obtiendrait s’il choisissait la meilleure action à chaque épisode. En bleu, on représente les gains obtenu par un agent n’ayant a priori aucune connaissance sur les machines. Cet agent est d’abord dans une phase d’exploration, durant laquelle les gains sont inférieurs à l’espérance de gains sous l’action optimale. Ceci se traduit par une pente pour la courbe bleue inférieure à celle de la courbe rouge. Petit a petit, l’agent acquiert une meilleure connaissance des distributions sous-jacentes. Il entre alors en phase d’exploitation, durant laquelle il se met à choisir de plus en plus les actions qu’il estime rentables. Au bout d’un certain temps, la connaissance devient parfaite, et l’agent ne choisit plus que l’action optimale. On voit que les pentes des courbes rouge et bleue s’égalisent. La différence entre les pentes des courbes rouges et bleue correspond au manque à gagner à un épisode n. On l’appelle le regret instantané.
A droite : La courbe bleue représente le regret cumulé, c’est à dire la somme cumulative des différences entre les pentes des courbes bleue et rouge.

Le regret cumulé est une métrique nous permettant d’évaluer la performance de notre stratégie sur le long terme : il correspond à la somme des différences entre les espérances associée à l’action optimale et l’action choisie, sur toute la durée de la partie. Il représente donc la différence entre ce que l’agent aurait pu gagner en jouant parfaitement, et ce qu’il a effectivement gagné. Il est donc aisé de comprendre que le but d’une stratégie est de minimiser le regret cumulé.

L’approche ϵ-Greedy (Epsilon-Greedy)

Nous avons parlé des méthodes « avides » (greedy). Comment rendre une méthode moins avide, afin qu’elle laisse à l’agent la possibilité de mieux explorer les distributions de récompenses sous-jacentes ? La version la plus simple de l’algorithme peut se formuler ainsi :

1) Fixer une valeur ϵ entre zéro et un
2) Jusqu’a la fin du jeu :
a) Tirer au sort un nombre v entre 0 et 1
b) Si $v>\epsilon$ , on exploite (on choisit l’action qui rapporte le plus dans notre état actuel de connaissance). Si v<ϵ, on explore (on choisit au hasard une des branches suboptimales.)
c) Actualiser $Q_t(a)$

Cet algorithme très simple donne cependant de bons résultats. Si ϵ est petit, il aura tendance à être frileux, si ϵ est grand il explorera beaucoup l’espace des possibles (jusqu’à jouer complètement au hasard si $\epsilon=1$ ). Certaines variantes de cet algorithme impliquent de diminuer ϵ à chaque itération. Le choix de la branche explorée peut se faire au hasard, ou avec des méthodes plus raffinées. L’échantillonnage de Thompson permet par exemple de sélectionner la branche qui nous apportera le plus d’information (dont la distribution est la moins connue.

En Conclusion

Il existe de nombreuses autres façons de résoudre les problèmes dits de bandit manchots. Cependant, toutes on un point commun : trouver l’équilibre entre exploration et exploitation. Aujourd’hui, une variante de ces problème, l’apprentissage par renforcement, révolutionne de nombreux domaines de l’intellignece artificielle. Avec une extension des problèmes de bandits manchots, on peut donc créer des IA capables de gagner à starcraft ou conduire des voitures autonomes.

Dans le cas du A/B testing, cette approche permet de mener des expériences sur les paramètres à optimiser d’un site web, tout en minimisant le cout de ces expérience par une allocation intelligente des ressources.