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 par rapport à la pour des lois de probabilité dans .
Problème du bandit manchot Le problème du bandit manchot est un jeu séquentiel où un joueur doit choisir à chaque tour entre actions (bras). Derrière chaque action il y a une loi de probabilité inconnue qui appartient à un ensemble de lois de probabilité connu du joueur (par exemple, peut être l'ensemble des lois normales ou celui des lois de Bernoulli).
A chaque tour , le joueur choisit (tire) un bras . Il reçoit ensuite une réalisation de la loi de probabilité .
Minimisation du regret Le but est de minimiser le regret au temps , défini par :
où : est la moyenne du bras , la plus grande moyenne, , le nombre de tirages du bras au tour .
Le joueur doit trouver un algorithme qui à chaque tour choisit quel bras tirer en se basant sur les actions et réalisations observées aux tours précédents pour minimiser le regret .
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.
Applications Les algorithmes de bandit manchot sont utilisés dans plusieurs domaines : test cliniques, système de recommandations, télécommunications, agriculture
L'algorithme L'algorithme calcule un indice à chaque tour pour chaque bras. Ensuite il tire le bras avec le plus petit indice.
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 d'un bras au tour est défini comme :
où : , est la divergence de Kullback-Leibler, est l'ensemble des lois de probabilité sur est la loi empirique du bras au tour , est la plus grande moyenne empirique au tour .
Remarque : pour chaque bras qui vérifie , on a . Son indice vaut donc .
Pseudocode 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
Résultats mathématiques Les algorithmes de résolution du problème du bandit manchot sont soumis à la borne inférieure asymptotique de Lai-Robbins sur le regret. L'algorithme IMED est le premier à atteindre cette borne inférieure pour des lois de probabilités dans 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.
Borne inférieure de Lai-Robbins 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é.
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. Elle dit que pour tout algorithme consistent sur l'ensemble des lois de — c'est-à-dire un algorithme tel que pour tout , le regret est sous-polynomial ( pour tout ) — on a :
Cette borne est asymptotique () : elle donne le premier terme multiplié par la constante optimale, et donne ensuite le terme du second ordre en .
Borne sur le regret de IMED Si les lois de tous les bras sont dans (c'est-à-dire ), alors le regret de IMED vérifie :
Si de plus toutes les lois sont bornées, alors il existe une constante telle que pour assez grand, le regret de IMED est bornée supérieurement par :
Temps de calcul L'algorithme ne nécessite de calculer que pour les bras sous-optimaux, qui vont être tirés 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 au premier ordre.
Notes et références
Articles connexes Problème du bandit manchot Algorithme KL-UCB Divergence de Kullback-Leibler
Catégorie:Processus stochastique Catégorie:Statistiques