En problème du bandit manchot, KL-UCB (pour Kullback–Leibler Upper Confidence Bound) est un algorithme type UCB (borne supérieure de confiance) qui est asymptotiquement optimal dans le sens où il atteint la borne inférieure problème-dépendante démontrée par Lai et Robbins.

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é connues du joueur (par exemple, peut être l'ensemble des lois normales ou celle des lois de Bernoulli).

À 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

where la moyenne du bras la plus grande moyenne

le nombre de tirages 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.

Applications

Les algorithmes de bandit manchot sont utilisés dans plusieurs domaines. Quelques exemples : tests cliniques, système de recommandations, télécommunications, agriculture.

Algorithme KL-UCB

L'algorithme est un UCB basé sur l'optimisme. C'est à dire qu'à chaque tour on va calculer une borne supérieure de confiance(UCB) sur la moyenne de chaque bras ; on va ensuite tirer le bras avec la plus grande UCB.

La différence avec KL-UCB c'est qu'on va utiliser une estimation de la lower bound de Lai–Robbins pour calculer la borne supérieure de confiance.

Histoire

L'algorithme KL-UCB a été introduit pour la première fois en 2011 pour des lois de Bernoulli. Il a ensuite été étendu pour des familles exponentielles de dimension 1 et des lois de probabilité bornée en 2013. Une adaptation de l'algorithme appelée KL-UCB-Switch qui utilise un mix entre MOSS et KL-UCB a été créée pour obtenir l'optimalité asymptotique problème-dépendante et indépendante en 2022. L'algorithme a aussi été étendu dans le cas de bandit Lipschitz en 2014.

Algorithme mathématique

Au début, l'algorithme tire chaque bras une fois. Ensuite, à chaque tour , pour chaque bras , on calcule:

la Divergence de Kullback-Leibler est la loi empirique du bras au tour c'est une suite positive bien choisie, souvent égale à avec .

Ensuite on tire le bras avec le plus grand index

On remarquera que l'algorithme n'a pas besoin de connaître .

Exemple

Dans le cas où les lois sont des lois normales avec variance fixée , on a:

avec la moyenne empirique du bras au tour .

Pseudocode

Pour chaque bras i faire: n[i] ← 1; nu[i] ← Rien; d ← ln(K) Pour t allant de 1 à K faire: tirer le bras t observer la réalisation r n[t] ← n[t] + 1 nu[t] ← mettre à jour la loi empirique Pour t allant de K+1 à T faire: Pour chaque bras i faire: index[i] ← calcul_index(n[i], nu[i], D, d) tirer le bras avec le plus grand index[a] observer la réalisation r n[a] ← n[a] + 1 nu[a] ← mettre à jour la loi empirique d ← ln(t+1)

Résultats mathématiques

En bandit on a la borne inférieure asymptotique sur le regret de Lai–Robbins. l'algorithme KL-UCB atteint cette borne inférieure pour des familles exponentielles de dimension 1 avec et les lois bornées dans avec .

Borne inférieure de Lai–Robbins

En 1952 Lai et Robbins ont démontré une borne inférieure asymptotique et problème-dépendante sur le regret.

Cette borne dit que pour tout algorithme consistent sur l'ensemble des lois de probabilité de — c'est à dire un algorithme qui vérifie pour tout , que le regret est sous-polynomial (c'est à dire pour tout ) — on a:

Cette borne est asymptotique avec et donne le premier ordre en et donne la constante optimale devant le .

Borne sur le Regret de KL-UCB

L'algorithme atteint la borne de Lai–Robbins pour les familles exponentielles de dimension 1 et pour les lois bornées dans .

Famille exponentielle de dimension 1

Pour un ensemble de familles exponentielles de dimension 1, avec on a la borne supérieure sur le regret de l'algorithme KL-UCB suivante:

Loi de probabilité dans [0,1]

Pour (L'ensemble des lois de probabilité à support dans ), et avec , on a la borne supérieure sur le regret de l'algorithme KL-UCB suivante:

Temps de calcul

Pour , le temps de calcul pour chaque tour pour un bras avec réalisations est de . Ce temps est plus grand que celui d'autres algorithmes optimaux comme NPTS avec , MED avec et IMED avec .

La lenteur de KL-UCB est due à la double optimale : pour chaque bras et chaque candidat pour la moyenne , l'algorithme calcule et maximise en sous la contrainte . Pour des lois de probabilités bornées dans la quantité n'a pas de forme close, c'est un problème d'optimisation, ce qui augmente le temps de calcul global.

Voir aussi

Problème du bandit manchot Intervalle de confiance

Références

Catégorie:Processus stochastique Catégorie:Statistiques