3  Bandits manchots

Ce problème met en évidence le compromis Exploration / Exploitation : il faut tirer le plus possible le bras que l’on pense être le meilleur (exploitation) tout en tirant suffisamment les autres pour améliorer notre connaissance des probabilités de gagner (exploration).

3.1 Modélisation probabiliste

Un problème de bandits manchots à K bras est modélisé par :

  • les K variables aléatoires X_{i} représentant le gain du bras i, de loi inconnue P_i et de moyenne (espérance) \mathbb{E}[X_i]=\mu(i) ;
  • le meilleur bras i^* qui a la plus grande moyenne de gains : i^* =\arg\max_{i=1,\dots,K} \mu(i)
  • un algorithme/une politique A:t\mapsto i qui choisit un bras i à chaque étape t.

Ainsi, si on tire T fois le bras i, on gagne \sum_{t=1}^T X_{i,t} où X_{i,t} est une copie indépendante de X_i, c’est-à-dire une variable aléatoire avec exactement les mêmes propriétés.1

Donc on peut espérer gagner au mieux (en tirant sur le meilleur bras) : Gain^*(T) =\mathbb{E}\left[ \sum_{t=1}^T X_{i^*,t} \right] = \sum_{t=1}^T \mathbb{E}[ X_{i^*,t} ] = \sum_{t=1}^T\mu(i^*) = T\mu(i^*)
En pratique, si A est un algorithme déterministe et indépendant des X_{i,t}, on espère gagner Gain(T) =\mathbb{E}\left[ \sum_{t=1}^T X_{A(t),t} \right] = \sum_{t=1}^T\mu(A(t))

Ceci nous permet de définir le regret comme la somme de ce qu’on aurait pu espérer gagner en plus : Regret(T) = \mathbb{E}\left[ Gain^*(T) - Gain(T)\right] = \mathbb{E}\left[ \sum_{t=1}^T (\mu(i^*) - \mu(A(t)) ) \right]

Note

Le regret est défini avec une espérance supplémentaire car en pratique tous les algorithmes intéressants, même s’ils sont déterministes, prennent des décisions aléatoires : la décision prise à l’instant t dépend des résultats aléatoires X_{i,t-1}, X_{i,t-2},\dots précédents, et donc devient aléatoire.

Concrètement, si j’applique le même algorithme chaque jour où je vais au casino, les bras qu’il me conseille de tirer ne sont pas les mêmes d’un jour à l’autre car mes gains sont différents.

La question est donc maintenant : comment choisir quel bras tirer pour minimiser le regret ?

Au début, on peut choisir n’importe lequel, car aucune information nous permet de choisir. Mais ensuite, différentes stratégies/algorithmes peuvent être mis en place.

Pour donner une indication, on peut reformuler le regret en fonction du nombre N_T(i) d’essais de chaque bras parmi T tirages et des différences \Delta_i = \mu(i^*) - \mu(i) entre les bras : \begin{align*} Regret(T) &=\mathbb{E}\left[ \sum_{t=1}^T (\mu(i^*) - \mu(A(t)) ) \right] \\ &= \mathbb{E}\left[ \sum_{i=1}^K N_T(i) (\mu(i^*) - \mu(i)) \right]\\ &= \sum_{i=1}^K \mathbb{E}\left[ N_T(i)\Delta_i \right] \end{align*} et, puisque les moyennes \mu(i) et les différences \Delta_i sont constantes (les réglages des machines à sous sont supposés ne pas changer), Regret(T) = \sum_{i=1}^K \mathbb{E}\left[ N_T(i) \right] \Delta_i \tag{3.1} Ainsi, on voit que les choix de l’algorithme devrait conduire à des petits N_T(i) pour les grands \Delta_i, et donc tirer rarement sur les bras très différents du meilleur bras.

3.2 Algorithme glouton (exploiter au maximum)

L’algorithme glouton applique les étapes suivantes :

  • Jouer au moins une fois chaque bras pour observer les gains x_{i,j}
  • Estimer \mu(i) par la moyenne des gains sur les tirages du bras i : \hat{\mu}(i) = \frac{1}{N_t(i)}\sum_{j=1}^t x_{i,j}\mathbf{1}(A(j)=i)
  • Choisir ensuite le bras qui maximise \hat{\mu}(i) : A(t) = \arg\max_{i=1,\dots,K} \hat{\mu}(i)

Cet algorithme semble pertinent et peut réussir à minimiser le regret si le bras optimal est rapidement trouvé.

Cependant, l’algorithme glouton risque de toujours choisir le même bras i sous-optimal, et donc d’accumuler un \Delta_i=\mu(i^*) - \mu(i) dans le regret à chaque itération, ce qui conduit à un regret linéaire en T.

Imaginons que les moyennes des bras soient \mu(1) = 0.5, \mu(2)=0.2 et \mu(3) = 0.6. Le meilleur bras est donc i^* = 3.

Après 1 tirage sur chaque bras, on obtient x_{1,1}=0.67, x_{2,2} = 0.15, x_{3,3} = 0.4, et donc les estimations des moyennes \hat{\mu}(1)=0.67, \hat{\mu}(2) = 0.15, \hat{\mu}(3) = 0.4. L’algorithme glouton va donc choisir au prochain tirage pour t=4, A(t) = 1 car le 1er bras paraît meilleur que les autres. Les tirages suivants pourront être plus faibles que le premier et la moyenne va tendre vers la vraie valeur : \hat{\mu}(1)\to \mu(1)=0.5. Cependant, si la moyenne estimée converge vers \mu(1) sans jamais repasser en-dessous de \mu(3)=0.4, alors l’algorithme glouton se vérouillera sur le 1er bras et ne découvrira jamais le bras optimal.

3.3 Algorithme \epsilon-glouton (explorer à l’infini)

À chaque étape,

  • avec une probabilité 1-\epsilon, appliquer l’algorithme glouton ;
  • avec une probabilité \epsilon, tirer un bras aléatoirement.

Cela force l’algorithme à explorer suffisamment tous les bras pour finir par déterminer le bras optimal. En effet, si le nombre de tirages T est suffisamment grand, alors tous les bras auront été tirés suffisamment de fois pour que les moyennes estimées \hat{\mu}(i) convergent vers les vraies moyennes \mu(i), et donc pour que l’algorithme glouton choisisse le bras optimal.

Mais à chaque étape, le regret instantané est \begin{align*} \mathbb{E}[\mu(i^*) - \mu(A(t))] &= \sum_{i=1}^K \mathbb{E}\left[(\mu(i^*)-\mu(i))\mathbf{1}(A(t)=i) \right] =\sum_{i=1}^K \Delta_i P(A(t)=i)\\ &\geq \frac{\epsilon}{K}\sum_{i=1}^K \Delta_i = constante \end{align*} et le regret est donc linéaire en T, comme pour l’algorithme glouton classique.

Cela est dû au fait que l’algorithme \epsilon-glouton explore aléatoirement à l’infini, y compris lorsque le bras optimal a déjà été identifié, et donc que la probabilité P(A(t)=i) pour les mauvais bras vaut toujours au moins \epsilon/K.

\begin{align*} P(A(t)=i) &= P\left(algo\ glouton,\ glouton\ choisit\ i \bigcup\ algo\ aleatoire,\ aleatoire\ choisit\ i\right)\\ &=P(algo\ glouton,\ glouton\ choisit\ i ) + P( algo\ aleatoire,\ aleatoire\ choisit\ i)\\ \end{align*} avec P(algo\ glouton,\ glouton\ choisit\ i ) \geq 0. Donc \begin{align*} P(A(t)=i) & \geq P( algo\ aleatoire,\ aleatoire\ choisit\ i) \\ &= P( algo\ aleatoire ) P(aleatoire\ choisit\ i)\\ & = \epsilon \cdot \frac{1}{K} . \end{align*}

Pour éviter cela, il suffirait de toujours appliquer l’algorithme glouton à partir de l’instant où le bras optimal est identifié, mais il est impossible de prédire à quel instant cela correspond.

Remarque : en faisant décroître \epsilon avec t, on peut obtenir un regret logarithmique, mais cela requiert la connaissance des \Delta_i sensés être inconnus.

3.4 Algorithme UCB

Imaginons que l’on dispose non seulement d’une estimation \hat{\mu}(i) de \mu(i) mais aussi d’un semi-intervalle de confiance C(i) tel que : \mu(i) \leq \hat{\mu}(i) + C(i) = B(i) Alors, on pourrait choisir le bras qui maximise B(i) pour

  • favoriser les bras que l’on croit bons (grand \hat{\mu}(i)) ;
  • sans oublier les bras qui pourraient être meilleurs (grand C(i)).

Cette idée repose sur l’optimisme face à l’incertitude : on « fera confiance » aux bras en considérant qu’ils peuvent donner le meilleur d’eux-mêmes plutôt que de se concentrer uniquement sur leur performance moyenne observée.

L’algorithme UCB (Upper Confidence Bound) applique cette idée ainsi (pour des gains X_i\in[0,1]) :

Tirer chaque bras une fois pour t\leq K, puis le bras i qui maximise B_t(i) = \hat{\mu}_{N_t(i)}(i) + \sqrt{\frac{3\ln t }{2 N_t(i) }} où

  • \hat{\mu}_{n}(i) = \frac{1}{n} \sum_{j=1}^n x_{i,j} est l’estimation de \mu(i) à partir de n observations x_{i,j} des gains du bras i ;
  • N_t(i) est le nombre de tirages du bras i sur les t premiers coups.

3.4.1 Interprétation du choix basé sur B_t(i)

Les décisions de l’algorithme UCB visent à équilibrer le compromis Exploitation/Exploration :

  • prendre \hat{\mu}_{N_t(i)}(i) en compte signifie exploiter l’information gagnée sur les précédents tirages ;
  • alors que le terme \sqrt{\frac{3\ln t }{2 N_t(i) }} favorise l’exploration :
    • il augmente pour les bras qui ne sont pas assez souvent sélectionnés : N_t(i) est constant et t augmente à chaque tirage dans lequel i n’a pas été choisi ;
    • il décroît pour le bras sélectionné car N_t(i) augmente plus rapidement que \ln t

Donc si un bras paraît bon sur la base de \hat{\mu}_{N_t(i)}(i), l’algorithme le sélectionnera mais il finira aussi par sélectionner un autre bras après de nombreuses sélections concentrées sur le même bras.

3.4.2 Explication de la formule de B_t(i)

La formule de B_t(i) provient de la quantification de l’intervalle de confiance dans l’estimation de la moyenne. Celle-ci est obtenue par l’inégalité de Hoeffding qui garantie que pour une moyenne \mu=\mathbb{E}X estimée à partir de n observations X_j par \hat{\mu} = \frac{1}{n} \sum_{j=1}^n X_j, P\left\{\mu > \hat{\mu} + \epsilon\right\} \leq e^{-2n \epsilon^2} dans le cas où X\in[0,1].

Pour l’algorithme UCB, on souhaite être de plus en plus sûr de l’intervalle de confiance \epsilon utilisé au cours du temps, ce qui implique une probabilité de plus en plus faible que \mu sorte de l’intervalle de confiance est soit supérieur à \hat{\mu}+\epsilon.

Soit \delta_t une borne que l’on se fixe sur cette probabilité à l’instant t, on pose e^{-2n \epsilon_t^2} = \delta_t et on impose \delta_t = t^{-3} pour s’assurer que cette borne diminue au cours du temps.

On en déduit le (semi)-intervalle de confiance \epsilon_t = \sqrt{\frac{3\ln t }{2n}}
qui correspond au second terme de B_t(i).

Avec ce choix, plus t est grand, plus on est sûr que \mu \leq \hat{\mu} + \epsilon_t. Cependant, pour pouvoir assurer cela, l’intervalle de confiance \epsilon_t augmente, mais de façon raisonnable (logarithmique).

3.4.3 Regret de l’algorithme UCB

Le regret de la politique UCB sur T tirages est logarithmique en T : Regret(T) \leq \left[\sum_{\Delta_i \neq 0} \frac{6}{\Delta_i}\right]\ln T + K\left(1+\frac{\pi^2}{3}\right) = O(\ln T)

Étant donné l’Équation 3.1, il suffit de montrer que \mathbb{E}\left[ N_T(i) \right] \leq \frac{6\ln T}{\Delta_i^2}+ 1 + \frac{\pi^2}{3} pour tout \Delta_i \neq 0 pour obtenir le résultat souhaité.

Calculons le nombre de tirages du bras i\neq i^* à l’aide de l’indicatrice: N_T(i) = \sum_{t=1}^T \mathbf{1}(A(t)=i). Mais ajoutons une petite astuce : nous ne compterons que les tirages après les n premiers tirages du bras. C’est-à-dire que si l’on tire moins de n fois le bras i, nous nous contenterons de noter que N_T(i) \leq n. Cela donne : \begin{align*} N_T(i) &\leq n + \sum_{t=n+1}^T \mathbf{1}(A(t)=i ,\ N_{t-1}(i)\geq n )\\ &\leq n + \sum_{t=n+1}^T \mathbf{1}( \underbrace{\hat{\mu}_{t-1}(i^*) + C_{t-1,N_{t-1}(i^*)} \leq \hat{\mu}_{t-1}(i) + C_{t-1,N_{t-1}(i)}}_{\text{nécessaire pour avoir $A(t)=i$}} ,\ N_{t-1}(i)\geq n ) \\ &\leq n + \sum_{t=n}^{T-1} \mathbf{1}( \hat{\mu}_{t}(i^*) + C_{t,N_{t}(i^*)} \leq \hat{\mu}_{t}(i) + C_{t,N_{t}(i)} ,\ N_{t}(i)\geq n ) \end{align*} Avec C_{t,N} = \sqrt{\frac{ 3 \ln t }{2N}} l’intervalle de confiance utilisé par UCB.

La question est de savoir quand l’algorithme peut choisir le bras i au lieu du bras i^*. Cela arrive lorsque B_t(i^*) = \hat{\mu}_{N_{t}(i^*)}(i^*) + C_{t,N_{t}(i^*)} \leq \hat{\mu}_{N_{t}(i)}(i) + C_{t,N_{t}(i)}=B_t(i) qui nécessite soit \mu(i^*) très sous-estimé, soit \mu(i) très sur-estimé, soit une petite différence \Delta_i : \hat{\mu}_{N_{t}(i^*)}(i^*) \leq \mu(i^*) - C_{t,N_{t}(i^*)} \tag{3.2} \hat{\mu}_{N_{t}(i)}(i) \geq \mu(i) + C_{t,N_{t}(i)} \tag{3.3} \Delta_i = \mu(i^*) - \mu(i) < 2 C_{t,N_{t}(i)} \tag{3.4} On peut vérifier qu’au moins une de ces trois condition doit être remplie, par exemple, si on n’a ni Équation 3.2 ni Équation 3.4, \hat{\mu}_{N_{t}(i^*)}(i^*) + C_{t,N_{t}(i^*)} > \mu(i^*)\geq \mu(i)+2C_{t,N_{t}(i)} et il faut \hat{\mu}_{N_{t}(i)}(i) + C_{t,N_{t}(i)} \geq \mu(i)+2C_{t,N_{t}(i)} \Leftrightarrow Équation 3.3, et ainsi de suite…

Regardons l’Équation 3.4 : elle implique N_{t}(i) < 6\ln t /\Delta_i^2\leq 6\ln T /\Delta_i^2, donc avec N_{t}(i)\geq n = 6\ln T /\Delta_i^2 + 1, il faut Équation 3.2 ou Équation 3.3 pour avoir A(t+1) = i et tirer sur le bras i.

C’est pour cela que l’on ne compte pas les tirages avant n : pour simplifier les conditions et ne considérer les 2 premières.

Avec la linéarité de l’espérance et la propriété de l’indicatrice \mathbb{E}[\mathbf{1}(E)] = P(E), on a \begin{align*} \mathbb{E}[ N_T(i) ] &\leq \mathbb{E}\left[n + \sum_{t=n}^{T-1} \mathbf{1}\left( (3.2)\ ou\ (3.3) \right) \right] \\ &\leq n+\sum_{t=n}^{T-1} \mathbb{E}\left[\mathbf{1}\left((3.2)\ ou\ (3.3) \right) \right]\\ & \leq n + \sum_{t=n}^{T-1} P\left((3.2)\ ou\ (3.3) \right) \end{align*} Par la borne de l’union (Équation B.1) : P\left((3.2)\ ou\ (3.3) \right) \leq P (3.2)+ P(3.3)
La probabilité de Équation 3.2 est la probabilité de sortie d’un intervalle de confiance, qui peut être bornée par l’inégalité de Hoeffding. Cependant, celle-ci requiert que le nombre d’observations N soit fixé à l’avance et ne dépende pas des tirages aléatoires, comme c’est le cas avec N_t(i^*). Pour contourner ce problème, on utilise le fait que l’Équation 3.2 n’intervient si elle est valide pour au moins une valeur de N entre 1 et t (l’instant courant) : P(3.2) \leq P\left(\bigcup_{N=1}^t \{(3.2), N_t(i^*) = N\}\right) = \sum_{N=1}^t P\left((3.2), N_t(i^*) = N\right) L’inégalité de Hoeffding donne alors P\left((3.2), N_t(i^*) = N\right) \leq e^{-2N C_{t,N}^2 } et \begin{align*} \Rightarrow \quad P(3.2) &\leq \sum_{N=1}^t e^{-2N C_{t,N}^2 } = \sum_{N=1}^t e^{-3\ln t} =\sum_{N=1}^t t^{-3} = t^{-2} \end{align*} De même, la probabilité de l’Équation 3.3 est \leq t^{-2}, donc \mathbb{E}[ N_T(i) ] \leq n + \sum_{t=n}^{T-1} P((3.2)\ or\ (3.3)) \leq \frac{6\ln T}{\Delta_i^2} +1 + \sum_{t=n}^{T-1} 2t^{-2} La somme peut être bornée par une constante (grâce au problème de Bâle) : \sum_{t=n}^{T-1}2t^{-2} \leq 2\sum_{t=1}^{\infty} \frac{1}{t^2} = \frac{\pi^2}{3} Donc \mathbb{E}[ N_T(i) ] \leq \frac{6\ln T}{\Delta_i^2} + 1 + \frac{\pi^2}{3} = O\left(\frac{6\ln T}{\Delta_i^2}\right) = O\left( \ln T \right)

  1. Ces nouvelles variables aléatoires sont nécessaires pour modéliser le fait que l’on tire plusieurs fois sur le même bras mais que les gains sont à chaque fois indépendants. Sans elles, écrire \sum_{t=1}^T X_{i} = T X_i ne corresponderait pas à la bonne expérience.↩︎