Modèles de « bandits » : Cette famille d’algorithmes propose des stratégies optimales pour maximiser l’espérance d’un gain lors d’une succession de choix entre plusieurs actions aux récompenses inconnues (on parle aussi de maximiser le rendement et de minimiser le regret).
Les modèles de bandits sont inspirés du problème de l’optimisation des gains du jeu des « bandits manchots », ces machines à sous que l’on appelle aussi des « bras ». Dans ce jeu, il s’agit de miser puis d’actionner un bras articulé pour voir le gain (ou la perte) conséquente. Le joueur a le choix entre plusieurs machines à sous, chacune occasionnant un gain aléatoire selon une distribution inconnue mais fixée à l’avance. Il cherche à accumuler le plus de gains possible, ce qui lui impose un arbitrage entre deux stratégies : l’exploration qui consiste à évaluer chacun des bras afin de déterminer celui de rendement maximal, et l’exploitation qui consiste à jouer le bras considéré comme le meilleur à un instant donné.
Les algorithmes de bandits permettent de résoudre ce problème avec de bonnes garanties théoriques. L’algorithme le plus connu est Upper Confidence Bound (UCB) [1], fondé sur les inégalités de concentration (inégalité d’Azuma-Hoeffding). Il permet d’obtenir un « regret » minimal, c’est-à-dire une espérance de gain très proche de l’espérance de gain maximale théorique.
Les algorithmes de bandits ont de nombreuses applications, par exemple dans les systèmes de recommandations, la publicité en ligne (voir notre article sur l’apprentissage séquentiel) ou encore l’optimisation non paramétrique. Dans plusieurs domaines comme les essais cliniques, ils sont utilisés comme alternative à l’AB test, un test statique pour déterminer la meilleure de deux solutions.
On dénombre de nombreuses extensions et variantes de ce problème. Dans le modèle des bandits linéaires par exemple, l’espérance de gain dépend linéairement d’un paramètre qui change au cours du temps. Dans les bandits adversariaux, le joueur joue contre un adversaire qui détermine les gains des bras à chaque instant. La stratégie du joueur ne sera donc plus de trouver le meilleur bras, mais de s’adapter dynamiquement à la stratégie de l’adversaire pour maximiser son gain.
[1] : Peter Auer, Using confidence bounds for exploitation-exploration trade-offs, The Journal of Machine Learning Research, 3:397-422, 2002.
+ Retour à l'index
