Mais qui sont ces “bandits” qu’affectionne l’apprentissage par renforcement ?
⏱ 4 minLes algorithmes de bandit constituent une classe de stratégies utilisées en apprentissage automatique. Leur histoire a commencé il y a près d’un siècle, mais ils n’ont pas dit leur dernier mot.
Au générique de l’intelligence artificielle, on découvre parfois d’étranges créatures. Comme ces « bandits à K bras », au casting de l’apprentissage par renforcement. Ils doivent leur étrange sobriquet à la machine à sous des casinos, que la langue de Shakespeare nomme slot machine ou plus vertement one-armed bandit, rappelant, comme le français « bandit manchot », qu’avec un seul bras, elle sait parfaitement vider les poches de celui qui a le malheur de s’en approcher.
Un « problème de bandit » est une situation similaire à celle du quidam qui se retrouve, à Las Vegas ou ailleurs, devant une batterie de machines à sous et aimerait savoir laquelle aura le meilleur taux de retour. Au départ, il ne sait rien. Le seul moyen d’obtenir de l’information est de jouer, et donc de perdre de l’argent. Chaque fois qu’il tire le bras d’une machine, notre joueur apprend un petit quelque chose sur cette machine, et après l’avoir fait plusieurs fois il commence à la cerner en termes statistiques. En jouant sur différentes machines, il se donne les moyens de les comparer et donc de choisir. Mais celle qui a payé le plus jusqu’à l’instant t n’est pas forcément la meilleure : vaut-il mieux persévérer avec elle ou tester encore les autres ? Des fois que… On met le doigt sur le dilemme central qui caractérise les problèmes de bandit : explorer pour en savoir plus ou exploiter ce que l’on sait déjà ? Tout comme monsieur Jourdain faisait de la prose sans le savoir, notre parieur hypothétique fait de l’apprentissage par renforcement.
En 1933, William Thompson (1887-1972), un biologiste versé dans le calcul des probabilités, étudiait déjà la question et publiait1 des solutions. Il a laissé son nom à un algorithme de bandit, appelé « échantillonnage de Thompson » (Thompson Sampling). Dès cette époque, on a réalisé que de nombreux problèmes s’apparentaient à cette situation de casino, comme les politiques d’investissements dans la recherche ou les stratégies d’essais cliniques. C’est ainsi qu’en 1952 le mathématicien et statisticien états-unien Herbert Robbins (1915-2001) en est venu à publier2 ses travaux avec ce type d’application en tête.
UNE KYRIELLE D’ALGORITHMES
« Avec les essais cliniques, on est souvent dans un cas particulier de problème de bandit, appelé “A/B test”, explique Vianney Perchet, professeur et chercheur au Centre de Recherche en Économie et Statistique (CREST) de l’ENSAE. On veut savoir si la solution A est plus efficace que la solution B ou l’inverse, le seul moyen de le savoir étant de traiter des patients, et on veut bien entendu minimiser les conséquences pour eux. » Il peut s’agir de médicaments, gestes chirurgicaux, thérapies de toutes sortes ou même d’outils diagnostics. « Mais de nos jours, l’application phare des algorithmes de bandit est le choix de publicités diffusées sur Internet », ajoute le chercheur, qui est également Principal Researcher à temps partiel chez Criteo, un ténor du ciblage publicitaire sur Internet. « Dans un cas comme dans l’autre, le problème n’est pas seulement de choisir au bout du compte le bon traitement ou la bonne pub. Il s’agit aussi de minimiser un coût, et le temps nécessaire pour arriver à une conclusion. »
Une kyrielle d’algorithmes de bandit ont été publiés, surtout depuis que l’apprentissage automatique est revenu sur le devant de la scène ces dix ou quinze dernières années. Intuitivement, la première attitude qui vient à l’esprit consiste à tester systématiquement toutes les machines puis à progressivement laisser de côté celles qui semblent avoir le moins bon retour. « C’est sur ce principe que reposent les stratégies dites “Explore-Then-Commit” (ETC), indique Vianney Perchet. Ce n’est pas une mauvaise idée, mais il faut le faire proprement. On peut éliminer, mais il faut que ce soit “data-driven”, basé sur les données. Il faut refaire les évaluations statistiques après chaque tirage. Ces algorithmes sont naturels, simples, plutôt stables… mais ce ne sont pas les plus performants. »
Toutes sortes d’algorithmes plus malins ont été proposés, à commencer par l’échantillonnage de Thompson, qui repose sur une approche bayésienne, explore un peu plus et est plus performant. « Il y a aussi par exemple les stratégies ”Upper Confidence Bound” (optimisme face à l’incertitude) ou UCB, ajoute Vianney Perchet. Et bien d’autres… » Chacune ayant ses avantages et inconvénients et étant plus ou moins adaptée à des situations différentes.
DES APPLICATIONS MULTIPLES
« On s’écarte du schéma initial quand on se rend compte que dans la vraie vie, on dispose en fait souvent d’information initiale, avant de tirer le premier bras, explique Vianney Perchet. Par exemple, il y a des statistiques, voire des réglementations sur le taux de retour des machines à sous. » En France, la loi fixe à 85% ce taux de retour au joueur de casino. En matière de publicité sur Internet, les annonceurs ont accès à des statistiques sur le click-through rate, moyen d’observation pour chaque catégorie de service ou de produit. « Les différents algorithmes de bandit peuvent exploiter plus ou moins bien ces informations supplémentaires, poursuit le chercheur. C’est plus facile avec certains algorithmes, comme le Thomson sampling, moins facile avec d’autres, comme le Explore-Then-Commit. »
Les applications de l’apprentissage par renforcement à l’aide d’algorithmes de bandit sont variées. De nos jours, le ciblage publicitaire est la plus visible et les essais cliniques restent un secteur d’actualité. Mais on les retrouve aussi dans le domaine de la finance, les systèmes de recommandation, la tarification dynamique, ou pour maximiser l’influence sur les réseaux sociaux. Et dans un domaine plus technique, il y a la sélection des canaux dans les systèmes de télécommunication. « Enfin, indique Vianney Perchet, les bandits sont efficaces dans des domaines où il s’agit de choisir le meilleur chemin dans un graphe. Un système d’assistance à la navigation reposant sur le crowdsourcing qui hésite entre deux chemins pour rejoindre une destination est comme devant deux machines à sous : il hésite entre “exploiter“ les informations récoltées récemment en aiguillant les véhicules dans la direction qui semble la plus rapide, et continuer à “explorer“ en aiguillant également des véhicules dans l’autre direction. » Waze fait-il appel à des bandits de grand chemin ?
Pierre Vandeginste
1. William Thompson. « On the likelihood that one unknown probability exceeds another in view of the evidence of two samples ». Biometrika, 1933. doi.org
2. Herbert Robbins. « Some aspects of the sequential design of experiments ». Bulletin of the American Mathematical Society, 1952. doi.org
