Bandit manchot (mathématiques)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour l’article homonyme, voir Bandit manchot

Dans le problème dit du bandit manchot, un utilisateur fait face à machines à sou. Chacune donnant une récompense moyenne que l'utilisateur ne connait pas à priori. A chacune de ces actions, il va donc sélectionner une machine permettant de maximiser son gain[1].

Dégrossir le problème[modifier | modifier le code]

A chacun de ses essais , l'utilisateur va recevoir une récompense qui dépend de la machine choisie. Dans un cas classique de bandit manchot, chacune des machines apporte une récompense de avec une probabilité . Dans ce cas, chacune des manchines apporte une récompense moyenne égale à la probabilité . L'utilisateur essaye de trouver la machine à sous qui apporte la plus grande récompense moyenne.

Résolution du problème[modifier | modifier le code]

A chacune de ses actions, l'utilisateur acquiert de l'expérience. Des algorithmes d'apprentissage par renforcement ont donc été proposés pour résoudre le problème du bandit manchot.

Regret[modifier | modifier le code]

Dans un problème de bandit manchot, le regret après essais est défini comme la différence entre la récompense que l'on obtiendrait en utilisant fois la meilleur machine et l'espérance de la récompense après essais [2]:

Dans cette équation, est la récompense moyenne avec la meilleure machine et désigne la récompense que l'on obtient avec la stratégie proposée à l'instant .

Des algorithmes d'apprentissage par renforcement permettent d'obtenir un regret borné par une fonction logarithme.

Thompson Sampling.[modifier | modifier le code]

L'algorithme de Thompson Sampling est le premier à avoir été proposé pour résoudre ce problème [3].

À chaque fois, l'utilisateur choisit la machine qui a l'index le plus élevé. Cet index étant une variable aléatoire suivant une loi bêta. Pour chaque machine, l'utilisateur calcule une loi bêta dont les paramètres et sont initialisés à 1. À chaque fois que l'utilisateur utilise une des machines, s'il obtient la récompense et sinon.

UCB[modifier | modifier le code]

L'algorithme UCB a été propose par P. Auer en 2002 [4]. Avec cet algorithme, l'utilisateur calcule la moyenne empirique de la récompense dans chacun des cannaux.

Dans cette équation désigne le nombre d'essais réalisés par l'utilisateur. le nombre d'essais fait par l'utilisateur sur la machine . désigne la récompense obtenue lors de l'essaie . désigne la fonction indicatrice qui indique que la machine a été choisie pour l'essai .

Pour calculer l'index dans chaque canal, on ajoute un biais qui permet à l'algorithme d'explorer les différents cannaux.

Le biais doit être choisi pour avoir une décroissance logarithmique du regret. Le biais :

Permet de borner le regret de manière logarithmes.

De nombreuses améliorations de cet algorithme existent[5].

Application pratique[modifier | modifier le code]

L'application la plus typique du problème du bandit manchot est celui du choix entre une ancienne et une nouvelle posologie d'un vaccin ou médicament (ou entre deux différents) : il faut déterminer le plus vite possible si le nouveau produit doit être adopté ou l'ancien maintenu. Toute erreur se traduirait en vies humaines perdues (ou, au minimum, en personnes souffrant de troubles consécutifs soit à un traitement incomplet, soit à des effets secondaires excessifs).

Ce modèle est parfois utilisé en apprentissage automatique, par exemple pour effectuer des choix de publicité à présenter en fonction de ce qui est déjà connu[6], à ceci près que le refus de cliquer sur lien publicitaire apporte lui-même à son tour une information exploitable.

En radio intelligente, ce modèle est souvent utilisé pour la prise de décision pour l'accès opportuniste au spectre [7].

Notes et références[modifier | modifier le code]

  1. http://statistique.blogs.sciencesetavenir.fr/archive/2015/04/24/du-casino-aux-essais-therapeutiques-le-bandit-manchot-23247.html
  2. Agrawal, R. (1995). Sample mean based index policies by O(log n) regret for the multi-armed bandit problem. Advances in Applied Probability, 27(4), 1054-1078.
  3. W. R. Thompson, "On the likelihood that one unknown probability exceeds another in view of the evidence of two samples", Biometrika, 25:285–294, 1933.
  4. Auer, P., Cesa-Bianchi, N. & Fischer, P. Machine Learning (2002) 47: 235.
  5. On Bayesian Upper Confidence Bounds for Bandit Problems, Emilie Kaufmann, Olivier Cappe, Aurelien Garivier ; JMLR W&CP 22: 592-600, 2012.
  6. http://blog.octo.com/online-machine-learning-application-a-la-publicite-sur-le-web/
  7. L. Lai, H. Jiang and H. V. Poor, "Medium access in cognitive radio networks: A competitive multi-armed bandit framework," 2008 42nd Asilomar Conference on Signals, Systems and Computers, Pacific Grove, CA, 2008, p. 98-102.

Voir aussi[modifier | modifier le code]