L'algorithme IMED (Indexed minimum empirical divergence, « Divergence empirique minimale indexée ») est un algorithme de résolution du problème du bandit manchot. Développé en 2015 par Junya Honda et Akimichi Takemura, c'est le premier algorithme dont on a démontré qu'il est asymptotiquement optimal (en) par rapport à la borne inférieure de Lai–Robbins (en)^[1] pour des lois de probabilité dans ${\displaystyle (-\infty ,1]}$^[2].

Le problème du bandit manchot est un jeu séquentiel où un joueur doit choisir à chaque tour entre ${\displaystyle K}$ actions (bras). Derrière chaque action ${\displaystyle a}$ il y a une loi de probabilité inconnue ${\displaystyle \nu _{a}}$ qui appartient à un ensemble de lois de probabilité ${\displaystyle {\mathcal {D}}}$ connu du joueur (par exemple, ${\displaystyle {\mathcal {D}}}$ peut être l'ensemble des lois normales ou celui des lois de Bernoulli).

A chaque tour ${\displaystyle t}$, le joueur choisit (tire) un bras ${\displaystyle a_{t}}$. Il reçoit ensuite une réalisation ${\displaystyle X_{t}}$ de la loi de probabilité ${\displaystyle \nu _{a_{t}}}$.

Le but est de minimiser le regret au temps ${\displaystyle T}$, défini par :

${\displaystyle R_{T}:=\sum _{a=1}^{K}\Delta _{a}\mathbb {E} [N_{a}(T)]}$

où :

${\displaystyle \mu _{a}:=\mathbb {E} [\nu _{a}]}$ est la moyenne du bras ${\displaystyle a}$,

${\displaystyle \mu ^{*}:=\max _{a}\mu _{a}}$ la plus grande moyenne,

${\displaystyle \Delta _{a}:=\mu ^{*}-\mu _{a}}$,

${\displaystyle N_{a}(t)}$ le nombre de tirages du bras ${\displaystyle a}$ au tour ${\displaystyle t}$.

Le joueur doit trouver un algorithme qui à chaque tour ${\displaystyle t}$ choisit quel bras tirer en se basant sur les actions et réalisations observées aux tours précédents ${\displaystyle (a_{s},X_{s})_{s<t}}$ pour minimiser le regret ${\displaystyle R_{T}}$.

C'est un jeu de compromis entre exploration pour trouver le bras optimal (le bras avec la plus grande moyenne) et exploitation en jouant le bras qu'on pense être optimal^[3].

Les algorithmes de bandit manchot sont utilisés dans plusieurs domaines : test cliniques, système de recommandations^[4], télécommunications, agriculture^[5], etc.

L'algorithme calcule un indice à chaque tour pour chaque bras. Ensuite il tire le bras avec le plus petit indice^[2].

L'indice est la somme de deux termes. Le premier est le « coût de transport » de la loi empirique vers une loi telle que ce bras devienne optimal. Le second est le coût d'avoir été tiré beaucoup de fois.

Mathématiquement, l'indice ${\displaystyle I_{a}(t)}$ d'un bras ${\displaystyle a}$ au tour ${\displaystyle t}$ est défini comme :

${\displaystyle I_{a}(t):=N_{a}(t)K_{inf}({\hat {\nu }}_{a}(t),{\hat {\mu }}^{*}(t))+\ln(N_{a}(t))}$

où :

${\displaystyle {\mathcal {K}}_{inf}(\nu ,\mu ,{\mathcal {D}}):=\inf \left\{\mathrm {KL} (\nu ,{\tilde {\nu }})\ |\ {\tilde {\nu }}\in {\mathcal {P}}([-\infty ,1]),\ \mathbb {E} [{\tilde {\nu }}]>\mu \right\}}$,

${\displaystyle \mathrm {KL} }$ est la divergence de Kullback-Leibler,

${\displaystyle {\mathcal {P}}([-\infty ,1])}$ est l'ensemble des lois de probabilité sur ${\displaystyle [-\infty ,1]}$

${\displaystyle {\hat {\nu }}_{a}(t)}$ est la loi empirique du bras ${\displaystyle a}$ au tour ${\displaystyle t}$,

${\displaystyle {\hat {\mu }}^{*}(t)}$ est la plus grande moyenne empirique au tour ${\displaystyle t}$.

Remarque : pour chaque bras ${\displaystyle a}$ qui vérifie ${\displaystyle {\hat {\mu }}_{a}(t)={\hat {\mu }}^{*}(t)}$, on a ${\displaystyle K_{inf}({\hat {\nu }}_{a}(t),{\hat {\mu }}^{*}(t))=0}$. Son indice vaut donc ${\displaystyle \ln(N_{a}(t))}$.

pour chaque bras i faire:
    n[i] ← 1; nu[i] ← Rien; mu[i] ← Rien
pour t allant de 1 à K faire:
    tirer le bras t
    recevoir r
    n[t] ← n[t] + 1
    nu[t] ← mettre à jour
    mu[t] ← mettre à jour
pour t allant de K+1 à T faire:
    mu* ← plus grand mu
    pour chaque bras i faire:
        scoreK[i] ← n[i] K_inf(nu[i],mu*)
        scoreN[i] ← ln(n[i])
        indice[i] ← scoreK[i] + scoreN[i]
    tirer a avec le plus petit indice[a]
    recevoir r
    n[a] ← n[a] + 1
    nu[a] ← mettre à jour
    mu[a] ← mettre à jour

Les algorithmes de résolution du problème du bandit manchot sont soumis à la borne inférieure asymptotique de Lai-Robbins sur le regret^[1]. L'algorithme IMED est le premier à atteindre cette borne inférieure pour des lois de probabilités dans ${\displaystyle (-\infty ,1]}$ au premier ordre. Si les lois sont de plus bornées, alors il atteint aussi le second ordre. C'est le premier algorithme qui atteint le second ordre de la borne inférieure^[2].

En 1985, Lai et Robbins ont démontré l'existence d'une borne inférieure asymptotique sur le regret, dépendante du problème considéré^[1].

En 2018, Aurélien Garivier, Pierre Menard et Gilles Stoltz ont démontré une version plus fine de la borne inférieure, donnant le second ordre^[6]. Elle dit que pour tout algorithme consistent sur l'ensemble des lois de ${\displaystyle {\mathcal {P}}([-\infty ,1])}$ — c'est-à-dire un algorithme tel que pour tout ${\displaystyle (\nu _{1},\dots ,\nu _{K})\in {\mathcal {P}}([-\infty ,1])^{K}}$, le regret ${\displaystyle R_{T}}$ est sous-polynomial (${\displaystyle R_{T}=o_{T\to +\infty }(T^{\alpha })}$ pour tout ${\displaystyle \alpha >0}$) — on a :

${\displaystyle R_{T}\geq \left(\sum _{a:\mu _{a}<\mu ^{*}}{\frac {\Delta _{a}}{{\mathcal {K}}_{\inf }(\nu _{a},\mu ^{*})}}\right)\ln T-\Omega _{T\to +\infty }(\ln \ln T).}$

Cette borne est asymptotique (${\displaystyle T\to +\infty }$) : elle donne le premier terme ${\displaystyle \ln T}$ multiplié par la constante optimale, et donne ensuite le terme du second ordre en ${\displaystyle -\Omega (\ln \ln T)}$.

Si les lois de tous les bras ${\displaystyle a}$ sont dans ${\displaystyle (-\infty ,1]}$ (c'est-à-dire ${\displaystyle \nu _{a}\in {\mathcal {P}}([-\infty ,1])}$), alors le regret de IMED vérifie :

${\displaystyle R_{T}\leq \left(\sum _{a:\mu _{a}<\mu ^{*}}{\frac {\Delta _{a}}{{\mathcal {K}}_{\inf }(\nu _{a},\mu ^{*})}}\right)\ln T+O(1)}$^[2]

Si de plus toutes les lois ${\displaystyle \nu _{a}}$ sont bornées, alors il existe une constante ${\displaystyle C>0}$ telle que pour ${\displaystyle T}$ assez grand, le regret de IMED est bornée supérieurement par :

${\displaystyle R_{T}\leq \left(\sum _{a:\mu _{a}<\mu ^{*}}{\frac {\Delta _{a}}{{\mathcal {K}}_{\inf }(\nu _{a},\mu ^{*})}}\right)\ln T-C\ln \ln T}$^[2]

L'algorithme ne nécessite de calculer ${\displaystyle K_{inf}}$ que pour les bras sous-optimaux, qui vont être tirés ${\displaystyle O(\ln T)}$ fois, ce qui rend l'algorithme plus rapide que l'algorithme KL-UCB. Une version plus rapide Fast-IMED a été développée en 2023 pour le rendre encore plus rapide en utilisant un développement de Taylor de ${\displaystyle K_{inf}}$ au premier ordre^[7].

• Problème du bandit manchot
• Algorithme KL-UCB
• Divergence de Kullback-Leibler

• Portail des probabilités et de la statistique