Introduction aux bandits à plusieurs bras

Copyright 2021 Les auteurs TF-Agents.

introduction

Multi-Armed Bandit (MAB) est un cadre d'apprentissage automatique dans lequel un agent doit sélectionner des actions (armes) afin de maximiser sa récompense cumulative à long terme. À chaque tour, l'agent reçoit des informations sur l'état actuel (contexte), puis il choisit une action en fonction de ces informations et de l'expérience acquise lors des tours précédents. A la fin de chaque manche, l'agent reçoit la récompense associée à l'action choisie.

Peut-être l'exemple le plus pur est le problème qui a donné son nom à MAB: imaginons que nous sommes confrontés à k machines à sous (bandits manchot), et nous avons besoin de savoir que l' on a le meilleur gain, tout en ne perdant pas trop d' argent.

Essayer chaque machine une fois, puis choisir celle qui rapporte le plus ne serait pas une bonne stratégie : l'agent pourrait tomber dans le choix d'une machine qui a eu un résultat heureux au début mais qui est en général sous-optimale. Au lieu de cela, l'agent doit revenir à plusieurs reprises sur le choix des machines qui ne sont pas si belles, afin de collecter plus d'informations à leur sujet. C'est le principal défi des Multi-Armed Bandits : l'agent doit trouver le bon mélange entre l'exploitation des connaissances antérieures et l'exploration afin d'éviter de négliger les actions optimales.

Des exemples plus pratiques de MAB impliquent une information secondaire chaque fois que l'apprenant prend une décision. Nous appelons cette information complémentaire « contexte » ou « observation ».

Bandits à plusieurs bras et apprentissage par renforcement

Pourquoi y a-t-il une suite MAB dans la bibliothèque TF-Agents ? Quel est le lien entre RL et MAB ? Les bandits à plusieurs bras peuvent être considérés comme un cas particulier d'apprentissage par renforcement. Pour citer l' introduction à RL :

A chaque pas de temps, l'agent effectue une action sur l'environnement sur la base de sa politique \(\pi(a_t|s_t)\), où \(s_t\) est l'observation courante à partir de l'environnement, et reçoit une récompense \(r_{t+1}\) et l'observation suivante \(s_{t+1}\) de l'environnement . L'objectif est d'améliorer la politique de manière à maximiser la somme des récompenses (retour).

Dans le cas général RL, l'observation suivante \(s_{t+1}\) dépend de l'état précédent \(s_t\) et l'action \(a_t\) prise par la politique. Cette dernière partie est ce qui sépare le MAB du RL : dans le MAB, l'état suivant, qui est l'observation, ne dépend pas de l'action choisie par l'agent.

Cette similitude nous permet de réutiliser tous les concepts qui existent dans TF-Agents.

• Un environnement émet des observations, et répond à des actions avec des récompenses.
• Une politique génère une action fondée sur une observation, et
• Un agent met à jour à plusieurs reprises la politique basée sur l' observation précédente tuples-action-récompense.

L'environnement champignon

À des fins d'illustration, nous utilisons un exemple de jouet appelé « environnement champignon ». L'ensemble de données de champignon ( Schlimmer, 1981 ) est constitué d'exemples marqués de champignons comestibles et toxiques. Les caractéristiques incluent les formes, les couleurs, les tailles des différentes parties du champignon, ainsi que l'odeur et bien d'autres.

L'ensemble de données champignon, comme tous les ensembles de données d'apprentissage supervisé, peut être transformé en un problème MAB contextuel. Nous utilisons la méthode également utilisée par Riquelme et al. (2018) . Dans cette conversion, l'agent reçoit les caractéristiques d'un champignon, décide de le manger ou non. Manger un champignon comestible donne une récompense de +5, tandis que manger un champignon vénéneux donnera +5 ou -35 avec une probabilité égale. Ne pas manger de champignon donne 0 récompense, indépendamment du type de champignon. Le tableau suivant résume les attributions de récompenses :

           | edible | poisonous
-----------|--------|----------
eating it  |     +5 | -35 / +5
leaving it |      0 |        0

L'agent LinUCB

Bien performer dans un environnement de bandit contextuel nécessite une bonne estimation de la fonction de récompense de chaque action, compte tenu de l'observation. Une possibilité consiste à estimer la fonction de récompense avec des fonctions linéaires. Ainsi, pour chaque action \(i\), nous essayons de trouver le paramètre \(\theta_i\in\mathbb R^d\) pour lequel les estimations

\(r_{t, i} \sim \langle v_t, \theta_i\rangle\)

sont aussi proches que possible de la réalité. Ici \(v_t\in\mathbb R^d\) est le contexte reçu à l' étape de temps \(t\). Ensuite, si l'agent est très confiant dans ses estimations, il peut choisir \(\arg\max_{1, ..., K}\langle v_t, \theta_k\rangle\) pour obtenir la plus haute récompense attendue.

Comme expliqué ci-dessus, le simple fait de choisir le bras avec la meilleure récompense estimée ne conduit pas à une bonne stratégie. Il existe de nombreuses façons de mélanger l' exploitation et l' exploration des agents d'estimateur linéaire, et l' un des plus célèbres est l'algorithme confiance linéaire Limite supérieure (LinUCB) (voir par exemple Li et al. , 2010 ). LinUCB a deux blocs de construction principaux (avec quelques détails omis) :

1. Elle maintient des estimations pour les paramètres de chaque bras avec linéaire des moindres carrés: \(\hat\theta_i\sim X^+_i r_i\), où \(X_i\) et \(r_i\) sont les contextes empilés et les récompenses des tours où bras \(i\) a été choisi, et \(()^+\) est l'inverse pseudo .
2. Elle maintient ellipsoïdes de confiance définis par l'inverse covariance \(X_i^\top X_i\) pour les estimations ci - dessus.

L'idée principale de LinUCB est celle de « l'Optimisme face à l'incertitude ». L'agent intègre l'exploration en augmentant les estimations d'un montant qui correspond à la variance de ces estimations. C'est là ellipsoïdes de confiance entrent en scène: pour chaque bras, l'estimation optimiste est \(\hat r_i = \max_{\theta\in E_i}\langle v_t, \theta\rangle\), où \(E_i\) est l'ellipsoïde autour \(\hat\theta_i\). Les agent choisit le bras plus beau \(\arg\max_i\hat r_i\).

Bien sûr, la description ci-dessus n'est qu'un résumé intuitif mais superficiel de ce que fait LinUCB. Une mise en œuvre peut être trouvé dans notre base de code ici

Et après?

Si vous voulez avoir un tutoriel plus détaillé sur notre bibliothèque Bandits jeter un oeil à notre tutoriel pour Bandits . Si, au contraire, vous voulez commencer à explorer notre bibliothèque tout de suite, vous pouvez le trouver ici . Si vous êtes encore plus impatient de commencer la formation, regardez certains de nos exemples de bout en bout ici , y compris l'environnement de champignon décrit ci - dessus avec LinUCB ici .