L'algorithme ETC (Explore then commit, « Explorer puis s'engager ») est un algorithme de résolution du problème du bandit manchot, un problème de compromis entre exploration et exploitation.
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 qui est défini comme
où : est la moyenne du bras ; est la plus grande moyenne ;
est le nombre de tirage du bras au tour .
Le joueur doit trouver un algorithme qui choisit à chaque tour 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.
Algorithme ETC
L'idée de l'algorithme est d'explorer chaque bras fois. Ensuite pour le reste du jeu on exploite le bras avec la plus grande moyenne empirique. Si l'horizon est connu, alors le nombre d'explorations peut dépendre de .
Des adaptations de l'algorithme existent et peuvent être utilisées pour des problèmes connexes.
Pseudocode Le joueur choisit M pour chaque bras i faire: tirer le bras i M fois mettre à jour la moyenne empirique mu[i] pour t allant de MK+1 à T faire: tirer le bras a avec le plus grand mu[a]
Résultats mathématiques
Quand tous les bras sont 1-sous-gaussiens, en explorant chaque bras fois, le regret au temps vérifie :
Le premier terme est le coût d'exploration :
Le deuxième terme est le coût de n'avoir pas exploré suffisamment, ce qui augmente la probabilité de ne pas avoir le bras optimal avec la plus grande moyenne empirique :
Augmenter augmente le premier terme tout en diminuant le deuxième terme. Le meilleur doit dépendre des qui sont inconnus du joueur.
Pour deux bras suivant des lois normales de variance 1, il a été prouvé que ETC ne peut pas atteindre la borne inférieure optimale de Lai-Robbins.
Notes et références
Articles connexes Problème du bandit manchot Intervalle de confiance Algorithme KL-UCB
Catégorie:Processus stochastique Catégorie:Statistiques