Le problème du bandit manchot à plusieurs bras, parfois appelé problème du bandit manchot à K ou N bras, est un concept fondamental de la théorie des probabilités et de l'apprentissage automatique. Il doit son nom à un joueur confronté à une rangée de machines à sous, souvent appelées « bandits manchots », qui doit décider quelles machines jouer, combien de fois jouer chacune, et dans quel ordre, tout en décidant s'il doit rester sur une machine actuelle ou en essayer une autre. Plus généralement, il décrit un décideur qui sélectionne itérativement l'une de plusieurs options fixes, appelées bras ou actions, lorsque les propriétés de chaque choix ne sont que partiellement connues au moment de l'allocation et peuvent être mieux comprises au fil du temps. Un aspect clé est que le choix d'un bras n'affecte pas les propriétés de ce bras ni d'aucun autre bras, ce qui le distingue des problèmes d'apprentissage par renforcement plus larges où les actions peuvent modifier les états futurs et les distributions de récompenses.
Le problème illustre le compromis exploration-exploitation, un dilemme central dans l'apprentissage automatique. Le joueur doit équilibrer « l'exploitation » de la machine ayant le gain attendu le plus élevé connu contre « l'exploration » pour recueillir plus d'informations sur les autres machines. L'objectif est de maximiser la récompense totale obtenue à travers une séquence de tirages de leviers. Ce compromis apparaît dans de nombreuses applications pratiques, notamment les essais cliniques, le routage réseau adaptatif, la conception de portefeuilles financiers et l'allocation des ressources dans les organisations de recherche.
Le problème du bandit manchot à plusieurs bras a été initialement considéré par les scientifiques alliés pendant la Seconde Guerre mondiale, mais il s'est avéré si insoluble que, selon Peter Whittle, il a été proposé de le larguer au-dessus de l'Allemagne afin que les scientifiques allemands puissent également perdre leur temps dessus. La version désormais couramment analysée a été formulée par Herbert Robbins en 1952, qui a construit des stratégies de sélection de population convergentes dans son article « Some Aspects of the Sequential Design of Experiments ». Un résultat théorique notable est l'indice de Gittins, publié pour la première fois par John C. Gittins, qui fournit une politique optimale pour maximiser la récompense actualisée attendue.
Modèle formel
Le bandit manchot à plusieurs bras peut être modélisé comme un ensemble de distributions réelles \(B = \{R_1, \dots, R_K\}\), où chaque distribution est associée aux récompenses délivrées par l'un des \(K\) leviers, avec \(K \in \mathbb{N}^+\). Soient \(\mu_1, \dots, \mu_K\) les valeurs moyennes de ces distributions de récompenses. Le joueur joue itérativement un levier par tour et observe la récompense associée, avec pour objectif de maximiser la somme des récompenses collectées sur un horizon \(H\), qui est le nombre de tours restants. Le problème du bandit est formellement équivalent à un processus de décision markovien à un état.
Le regret, noté \(\rho\), mesure la différence attendue entre la somme des récompenses d'une stratégie optimale et les récompenses collectées après \(T\) tours. Il est défini comme \(\rho = T\mu^ - \sum_{t=1}^T \hat{r}_t\), où \(\mu^\) est la moyenne de récompense maximale et \(\hat{r}_t\) est la récompense obtenue au tour \(t\). Minimiser le regret est un objectif principal dans les algorithmes de bandit.
Exploration vs. Exploitation
Le compromis exploration-exploitation est le défi central dans les problèmes de bandit manchot à plusieurs bras. L'exploitation consiste à choisir le bras ayant la récompense estimée la plus élevée sur la base des connaissances actuelles, tandis que l'exploration consiste à essayer d'autres bras pour réduire l'incertitude sur leurs récompenses potentielles. Des stratégies efficaces doivent équilibrer ces objectifs concurrents pour maximiser la récompense cumulative à long terme. Ce compromis n'est pas unique aux bandits ; il apparaît dans tout le Machine learning, y compris dans le Reinforcement learning et les systèmes d'Artificial intelligence qui doivent décider entre utiliser des stratégies connues et en découvrir de nouvelles.
En pratique, les bandits manchots à plusieurs bras ont été utilisés pour modéliser des problèmes tels que la gestion de projets de recherche dans de grandes organisations, comme une fondation scientifique ou une entreprise pharmaceutique. Par exemple, un responsable de recherche doit décider quels projets financer, en équilibrant l'exploitation de projets au potentiel connu contre l'exploration de nouvelles idées incertaines. Le modèle a également été appliqué au routage adaptatif pour minimiser les délais réseau et à la conception de portefeuilles financiers, où le choix des actifs implique des compromis similaires.
Algorithmes et stratégies
Plusieurs algorithmes ont été développés pour résoudre le problème du bandit manchot à plusieurs bras. L'un des plus anciens est la stratégie epsilon-greedy, où l'agent choisit un bras aléatoire avec une probabilité \(\epsilon\) (exploration) et sélectionne sinon le bras ayant la récompense estimée la plus élevée (exploitation). Une autre approche populaire est l'algorithme de la borne supérieure de confiance (UCB), qui sélectionne les bras en fonction à la fois de leur récompense moyenne et de l'incertitude de cette estimation, équilibrant efficacement exploration et exploitation de manière fondée. L'échantillonnage de Thompson, une méthode bayésienne, maintient une distribution a posteriori pour la récompense de chaque bras et échantillonne ces distributions pour décider quel bras jouer.
L'indice de Gittins, introduit par John C. Gittins, fournit une politique optimale pour maximiser la récompense actualisée attendue dans certains contextes de bandit. Il attribue un indice à chaque bras en fonction de son état, et la stratégie optimale est de jouer le bras ayant l'indice le plus élevé. Ce résultat a été influent dans la recherche opérationnelle et l'économie.
Applications et preuves empiriques
Le cadre du bandit manchot à plusieurs bras a de nombreuses applications pratiques. Dans les essais cliniques, il peut être utilisé pour allouer des patients à différents traitements, minimisant les pertes de patients tout en recueillant des informations sur l'efficacité des traitements. Dans le routage adaptatif, il aide à minimiser les délais en sélectionnant dynamiquement les chemins réseau. Dans la conception de portefeuilles financiers, il guide l'allocation des ressources parmi des options d'investissement concurrentes.
Une étude de 2024 utilisant des registres de jeux de casino a traité les choix répétés des joueurs parmi des machines à sous aux cotes inconnues comme un problème de bandit manchot à plusieurs bras à grande échelle. L'étude a constaté que les joueurs plus expérimentés avaient tendance à sélectionner des machines avec de meilleures cotes et montraient une plus grande cohérence dans leurs choix de machines au fil du temps, des schémas cohérents avec l'apprentissage et une plus grande exploitation des options mieux connues. Cette preuve empirique soutient la pertinence des modèles de bandit pour la prise de décision dans le monde réel.
Le modèle a également été utilisé pour contrôler l'allocation dynamique des ressources à différents projets, répondant à la question de savoir sur quel projet travailler compte tenu de l'incertitude sur la difficulté et le gain. Cette application est particulièrement pertinente dans la recherche et le développement, où les organisations doivent décider comment allouer des ressources limitées parmi des initiatives concurrentes.
Relation avec l'apprentissage par renforcement
Le problème du bandit manchot à plusieurs bras est un problème classique de Reinforcement learning qui illustre le compromis exploration-exploitation. Cependant, il est plus simple que l'apprentissage par renforcement général car les actions sélectionnées n'affectent pas la distribution des récompenses des bras. En revanche, dans l'apprentissage par renforcement général, les actions peuvent changer l'état de l'environnement, influençant les récompenses futures. Cette distinction fait des bandits un point de départ traitable pour étudier les dilemmes d'exploration-exploitation, et de nombreux algorithmes développés pour les bandits ont été étendus à des contextes d'apprentissage par renforcement plus complexes.
Le problème relève également de la catégorie large de l'ordonnancement stochastique, où des décisions doivent être prises sous incertitude quant aux résultats de différentes actions. Cette connexion souligne la large applicabilité des modèles de bandit à travers divers domaines, de la recherche opérationnelle à l'Artificial intelligence.
En résumé, le problème du bandit manchot à plusieurs bras est un modèle fondamental pour la prise de décision sous incertitude, avec des racines théoriques profondes et une pertinence pratique large. Son étude a produit des algorithmes élégants et des perspectives qui continuent d'informer la recherche en Machine learning et au-delà.