Problème du bandit manchot

Une rangée de machines à sous à Las Vegas.

En mathématiques, plus précisément en théorie des probabilités, le problème du bandit manchot[1],[2] (généralisable en problème du bandit à K bras[3] ou problème du bandit à N bras[4]) se formule de manière imagée de la façon suivante : un utilisateur (un agent), face à des machines à sous, doit décider quelles machines jouer. Chaque machine donne une récompense moyenne que l'utilisateur ne connait pas a priori. L'objectif est de maximiser le gain cumulé de l'utilisateur.

C'est un exemple d'apprentissage par renforcement. Typiquement, la politique de l'utilisateur oscille entre exploitation (utiliser la machine dont il a appris qu'elle récompense beaucoup) et exploration (tester une autre machine pour espérer gagner plus)[5]. Le problème de bandit manchot peut être vu comme un processus de décision markovien avec un seul état[6].

Formalisation du problème

Dans cette section, nous formalisons le problème en reprenant quelques notations de l'article d'Auer et al[3].

Entrée du problème

Considérons K machines à sous. L'entrée du problème est donnée par des variables aléatoires X_i,n pour tout 1 ≤ i ≤ K, et n ≥ 1, où l'indice i représente une des K machines (ou un « bras » du bandit) et l'indice n représente un tour de jeu. On suppose toutes ces variables aléatoires indépendantes et que les variables d'une même machine i, c'est-à-dire les variables X_i,1, X_i,2, etc., suivent la même distribution de probabilité inconnue de l'agent, d'espérance μ_i.

Au tour numéro n, l'utilisateur va recevoir une récompense qui dépend de la machine qu'il choisit. Un exemple classique de bandit manchot est le cas où la machine i apporte une récompense de 1 avec une probabilité p_i et 0 avec la probabilité 1-p_i.

Sortie du problème : calcul d'une politique

L'utilisateur essaye de trouver la machine à sous qui apporte la plus grande récompense moyenne. Une politique ou stratégie pour le problème du manchot est un algorithme qui choisit la machine suivante à jouer, en se basant sur les choix précédents et sur les récompenses obtenues[7]. L'objectif est de fournir des politiques qui minimisent le regret, c'est-à-dire la quantité qui exprime ce que la politique a fait perdre par rapport au choix de la meilleure machine.

Regret

Dans un problème de bandit manchot, le regret après n essais est défini comme la différence entre la récompense que l'on obtiendrait en utilisant n fois la meilleure machine et l'espérance de la récompense après n essais effectués conformément à la politique[3],[8]. Formellement, ce regret vaut :

${\displaystyle r_{n}=n\mu ^{*}-\sum _{k=1}^{n}\mathbb {E} (\mu _{I_{k}})}$

où ${\displaystyle \mu ^{*}}$est la récompense moyenne de la meilleure machine et ${\displaystyle \mu _{I_{k}}}$ désigne la récompense que l'on obtient avec la stratégie proposée à l'instant ${\displaystyle k}$.

Différents algorithmes

Des algorithmes d'apprentissage par renforcement ont donc été proposés pour résoudre le problème du bandit manchot.

Algorithme de bandit

L'algorithme de bandit tient son nom des machines à sous (multi-armed bandit) face auxquelles le joueur cherche à maximiser son gain[9]. Ils ont été introduits dans les années 1960 en vue d’applications aux tests cliniques[10].

Le principe d’un algorithme de bandit peut être défini de la manière suivante : on dispose de 2 sources A et B (ayant respectivement une probabilité p_A et p_B d’être satisfaisante lorsqu’elle est utilisée) et on souhaite déterminer laquelle des deux est la plus performante.

Approche gloutonne

Une approche gloutonne[11] consiste à ne faire que de l'exploitation, mais pas d'exploration. Ainsi, on calcule la valeur d'un bras a d'une machine (a pour action) de la façon suivante :

${\displaystyle Q_{t}(a):={\frac {{\text{somme des récompenses reçues par l'action }}a{\text{ avant le temps }}t}{{\text{nombre de fois que l'action }}a{\text{ a été tirée avant le temps }}t}}}$

Le choix glouton consiste à choisir une des actions a qui maximise ${\displaystyle Q_{t}(a)}$. Avec cette approche, l'optimal n'est pas atteint. On montre qu'on améliore la politique calculée si l'agent choisit une action arbitraire avec une probabilité ε > 0. L'algorithme suivant est un algorithme simple pour le problème des bandits manchots, que l'on appelle ε-glouton.

initialiser pour tout bras a:
     Q(a) := 0
     N(a) := 0

boucle pour toujours:
      avec une probabilité ε:
               a := un bras au hasard
      sinon:
               a := une action qui maximise Q(a)

      R := récompense obtenue en tirant a

      N(a) := N(a) + 1
      Q(a) := Q(a) + (R - Q(a)) / N(a)

On stocke la valeur courante de ${\displaystyle Q_{t}(a)}$ dans Q(a).

On remarquera la similitude de cette approche ε-glouton avec le processus darwinien classique de mutations et sélections.

Algorithmes de Lai et Robbins

Tze Leung Lai et Herbert Robbins[12] ont donné des algorithmes d'apprentissage par renforcement qui permettent d'obtenir un regret borné par une fonction logarithme, pour des familles spécifiques de distribution de probabilités pour les récompenses : ${\displaystyle r_{n}<O(\log(n))}$. En autres termes, cela signifie que la machine optimale est jouée exponentiellement plus souvent que les autres machines[13].

Échantillonnage de Thompson

L'algorithme d'échantillonnage de Thompson est le premier à avoir été proposé pour résoudre ce problème [14].

À chaque fois, l'utilisateur choisit la machine qui a l'index le plus élevé. Cet index étant une variable aléatoire suivant une loi bêta. Pour chaque machine, l'utilisateur tire un index suivant une loi bêta ${\displaystyle \beta (a_{j},b_{j})}$ dont les paramètres ${\displaystyle a_{j}}$ et ${\displaystyle b_{j}}$ sont initialisés à 1. À chaque fois que l'utilisateur utilise une des machines, ${\displaystyle a_{j}=a_{j}+1}$ s'il obtient la récompense et ${\displaystyle b_{j}=b_{j}+1}$ sinon.

UCB

L'algorithme UCB (pour Upper Confidence Bounds) a été proposé par P. Auer en 2002 [15]. Avec cet algorithme, l'utilisateur calcule la moyenne empirique de la récompense pour chacune des machines.

${\displaystyle X_{j}={\frac {1}{T_{j}}}\sum _{i=1}^{t}r_{i}\chi _{a_{j}=i}}$

Dans cette équation, ${\displaystyle t}$ désigne le nombre d'essais réalisés par l'utilisateur, ${\displaystyle T_{j}}$ le nombre d'essais fait par l'utilisateur sur la machine ${\displaystyle j}$, ${\displaystyle r_{i}}$ désigne la récompense obtenue lors de l'essai ${\displaystyle i}$. ${\displaystyle \chi }$ désigne la fonction indicatrice qui indique que la machine ${\displaystyle j}$ a été choisie pour l'essai ${\displaystyle i}$.

Pour calculer l'index dans chaque canal, on ajoute un biais qui permet à l'algorithme d'explorer les différentes machines.

${\displaystyle B_{j}=X_{j}+A_{j}}$

Le biais ${\displaystyle A_{j}}$ doit être choisi pour avoir une décroissance logarithmique du regret. Le biais :

${\displaystyle A_{j}={\sqrt {\frac {2\log(t)}{T_{j}}}}}$

permet de borner le regret de manière logarithmique.

De nombreuses améliorations de cet algorithme existent[16].

Application pratique

L'application la plus typique^[réf. nécessaire] du problème du bandit manchot est celui du choix entre une ancienne et une nouvelle posologie d'un vaccin ou médicament (ou entre deux différents) : il faut déterminer le plus vite possible si le nouveau produit doit être adopté ou l'ancien maintenu. Toute erreur se traduirait en vies humaines perdues (ou, au minimum, en personnes souffrant de troubles consécutifs soit à un traitement incomplet, soit à des effets secondaires excessifs). On ne peut pour cette raison utiliser de protocoles des statistiques classiques (Fisher), qui ne sont pertinents que quand la collecte de l'information est peu coûteuse et son traitement onéreux, et on s'oriente plutôt vers un plan d'expérience en utilisant des méthodes bayésiennes qui utilisent immédiatement l'information au fil de l'eau.

Ce modèle est parfois utilisé en apprentissage automatique, par exemple pour effectuer des choix de publicité à présenter en fonction de ce qui est déjà connu[17], à ceci près que le refus de cliquer sur un lien publicitaire apporte lui-même à son tour une information exploitable.

En radio intelligente, ce modèle est souvent utilisé pour la prise de décision pour l'accès opportuniste au spectre [18].

Notes et références

1. « Statistiquement vôtre - Choix aléatoire de sujets autour de la statistique », sur Statistiquement vôtre (consulté le 21 septembre 2018)
2. « Cours à l'université de Lille "Introduction aux algorithmes de bandit" »
3. P. Auer, N. Cesa-Bianchi et P. Fischer, « Finite-time Analysis of the Multiarmed Bandit Problem », Machine Learning, vol. 47, n^os 2/3,‎ 2002, p. 235–256 (DOI 10.1023/A:1013689704352)
4. M. N. Katehakis et A. F. Veinott, « The Multi-Armed Bandit Problem: Decomposition and Computation », Mathematics of Operations Research, vol. 12, n^o 2,‎ 1987, p. 262–268 (DOI 10.1287/moor.12.2.262)
5. (en) « Exploration–exploitation tradeoff using variance estimates in multi-armed bandits », Theoretical Computer Science, vol. 410, n^o 19,‎ 28 avril 2009, p. 1876–1902 (ISSN 0304-3975, DOI 10.1016/j.tcs.2009.01.016, lire en ligne, consulté le 21 septembre 2018)
6. « Cours à l'université de Washington (cf. premier paragraphe) »
7. « HOW TO INCREASE YOUR CHANCES OF WINNING AT POKIES? », Pokiestar,‎ 4 mai 2019 (lire en ligne, consulté le 5 juillet 2019)
8. Agrawal, R. (1995). Sample mean based index policies by O(log n) regret for the multi-armed bandit problem. Advances in Applied Probability, 27(4), 1054-1078.
9. Maureen Clerc, Laurent Bougrain et Fabien Lotte, Les interfaces cerveau-ordinateur 1 : fondements et méthodes, Volume 1, ISTE Group, 1^er juillet 2016, 310 p., p. 228
10. « Étude du regret associé aux algorithmes de bandit de type Narendra-Shapiro », sur INSTITUT DE MATHÉMATIQUES DE MARSEILLE (consulté le 1^er octobre 2020)
11. (en) The MIT Press, « Reinforcement Learning, Second Edition | The MIT Press », sur mitpress.mit.edu (consulté le 9 février 2020), Chapter 2. Algorithme donnée p. 32
12. (en) « Asymptotically efficient adaptive allocation rules », Advances in Applied Mathematics, vol. 6, n^o 1,‎ 1^er mars 1985, p. 4–22 (ISSN 0196-8858, DOI 10.1016/0196-8858(85)90002-8, lire en ligne, consulté le 21 septembre 2018)
13. « Cours sur les bandits (voir transparent 12) »
14. W. R. Thompson, "On the likelihood that one unknown probability exceeds another in view of the evidence of two samples", Biometrika, 25:285–294, 1933.
15. Auer, P., Cesa-Bianchi, N. & Fischer, P. Machine Learning (2002) 47: 235.
16. On Bayesian Upper Confidence Bounds for Bandit Problems, Émilie Kaufmann, Olivier Cappé, Aurelien Garivier ; JMLR W&CP 22: 592-600, 2012.
17. « Online Machine Learning - Application à la publicité sur le web », sur OCTO Talks !, 1^er octobre 2013 (consulté le 17 avril 2023).
18. L. Lai, H. Jiang and H. V. Poor, "Medium access in cognitive radio networks: A competitive multi-armed bandit framework", 2008 42nd Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, 2008, p. 98-102.

Voir aussi

• Inférence bayésienne
• Théorème de Bayes
• Plan d'expérience