Dans notre société, il nous est souvent reproché de ne pas oser sortir des sentiers battus. Allant parfois jusqu’à parler de moutons de Panurge, il est mal vu de suivre une tendance qui fonctionne plutôt que d’essayer d’en créer une nouvelle qui pourrait avoir encore plus d’effets positifs.
Ces accusations vont même toucher le monde scientifique: on reproche aux chercheurs de choisir des sujets plus simples, qui mèneront donc à une publication certaine (n’allez surtout pas penser que j’ai choisi ce sujet afin d’être sûr de publier un article …), plutôt qu’à des recherches plus difficiles mais qui pourraient être révolutionnaires. Mais cela vaut-il vraiment la peine d’innover ?
Le dilemme exploitation-exploration
Le principal problème que soulève cette question relève de la distinction entre l’intérêt collectif et l’intérêt personnel. Nous sommes des humains, dotés d’intérêts personnels (dans le cas du chercheur, il faut qu’il gagne sa vie et conserve son emploi), au sein d’un grand tout qu’est la société qui a pour intérêt principal son développement (qui se fait donc grâce à de nouvelles découvertes).
Exploiter, c’est donc s’assurer une certaine pérennité quant à son intérêt personnel. En revanche, on ne peut plus contribuer à l’intérêt collectif ainsi. Explorer, c’est faire primer l’intérêt collectif avant le sien: on prend alors un grand risque (la société n’ayant pas besoin de nous, l’échec est synonyme de rejet par celle-ci).
Mais c’est alors ici que se pose le principal problème: s’il n’y a que des suiveurs, qui suivre ? Les bénéfices personnels ne pourront plus naître, n’ayant pas de modèle à exploiter. S’il n’y a que des explorateurs, la collectivité ne récolte plus assez de ces découvertes: on part dans tous les sens, sans tirer profit des nouveautés. C’est donc ici qu’intervient la notion primordial d’équilibre collectif.
Un exemple concret: le dilemme du bandit manchot
Une illustration classique de ce problème est le dilemme du bandit manchot. Contextualisons un peu la situation: vous êtes, avec une centaine d’autres personnes, face à cent machines à sous (appelées bandit manchot). Vous n’avez le droit qu’à un nombre fixé d’essais et vous souhaitez bien évidemment gagner le plus possible.
Deux types de de stratégies (généralement appelées politiques) s’offrent à vous : explorez différentes machines, en espérant en trouver une qui vous rapporte gros (vous seriez donc un peu explorateur), ou alors vous concentrez sur une machine qui attire beaucoup d’autres personnes, et qui semble donc garantir une récompense moyenne plus que satisfaisante (vous seriez donc un rusé exploiteur).
Alors, que feriez-vous ? Risquer gros pour possiblement toucher gros, ou limiter les dégâts, limitant donc les revenus ?Nous, chez la revue IA, nous sommes près de nos sous. Nous souhaitons laisser le hasard le plus à l’écart possible de nos économies. Après tout, le dilemme du bandit manchot reste un problème mathématiques, et les plus assidus d’entre vous se souviendront peut-être qu’Ilyes a déjà mentionné le dilemme d’exploration-exploitation dans son très bon article sur l’apprentissage par renforcement.
Une résolution possible: l’algorithme ucb
Pour ce genre de problème, il convient tout d’abord de définir ce que serait une politique satisfaisante. Dans le problème du bandit manchot, il nous faut donc introduire la notion de regret: celui-ci se traduit comme étant la différence entre le revenu maximal que nous aurions obtenu en utilisant à chaque fois la machine la plus généreuse et le revenu obtenu en appliquant la stratégie choisie. Vous l’aurez compris : une politique satisfaisante ici minimisera ce regret (il est à noter que celui-ci ne pourra jamais être nul: l’algorithme solution doit pouvoir être efficace sur n’importe quelle situation de bandit manchot, ce qui force l’exploration et donc un regret minimum).
Et ne dit-on pas que l’on apprend de ses erreurs ? Nul regret donc pour nous, qui userons avec astuce de l’apprentissage par renforcement. En effet, c’est même ainsi que s’améliorera notre algorithme, notamment grâce au learning rate décrit dans l’article sur l’apprentissage par renforcement: on explore différentes options, en choisissant finalement la plus judicieuse. Ainsi, plusieurs algorithmes s’offrent à nous: j’ai pour ma part choisi de m’attarder sur le « Upper confidence bounds ». Celui-ci porte bien son nom: il s’agit ici de construire, à chaque tour et pour chaque machine, un intervalle de confiance quant au résultat que l’on risque d’obtenir, basé sur les résultats obtenus aux précédents tours. Il suffit alors de choisir le bandit manchot présentant la meilleure borne supérieure.
On dit qu’il s’agit d’un algorithme « optimiste », car il choisit la machine présentant le meilleur résultat dans le cas idéal. Cette méthode permet alors de borner le regret, afin que celui-ci soit logarithmique en le nombre de tours.
Et il se trouve que ce résultat est fort intéressant: en 1985, Lai et Robbins ont en effet prouvé qu’une telle borne est optimale: on ne pourra trouver un algorithme significativement plus performant pour gérer le problème du bandit manchot ! Toutefois, certaines améliorations ont vu le jour depuis, je vous en laisse quelques-unes en référence en bas de cet article.
Ainsi donc, en se basant sur l’expérience et les statistiques plutôt que sur une politique fixe, on peut obtenir un meilleur équilibre collectif qui permet de maximiser les profits. Bien que l’aspect illustratif du bandit manchot puisse vous faire penser qu’il s’agit d’un problème mathématique divertissant (tout du moins, j’espère que l’article a su vous captiver !), il trouve de réelles applications. C’est notamment le cas pour la posologie (créer de nouveaux médicaments plus incertains ou conserver les anciens), ou même dans un cadre marketing plus global. Alors, inutile d’aller vous ruiner dans des casinos pour mettre en oeuvre la politique qui vous semble la plus judicieuse: appliquez-la dans votre vie courante, et faites les meilleurs choix (que ce soit en suivant ou en innovant) pour avoir le moins de regrets possibles !
Références intéressantes :
http://researchers.lille.inria.fr/~munos/mastermva/lecture03.pdfhttp://www.scoste.fr/bandits.pdf
https://hal.archives-ouvertes.fr/hal-01671320/document
Leave a Comment