Bandit manchot (mathématiques)

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.

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.

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}$.

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.

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.

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].

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.

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].