Le dilemme exploration-exploitation, également connu sous le nom de compromis exploration-exploitation, est un concept central de la prise de décision qui apparaît dans des domaines allant de l'économie à l'intelligence artificielle. Il implique d'équilibrer deux stratégies opposées : l'exploitation, qui consiste à sélectionner la meilleure option en fonction des connaissances actuelles (qui peuvent être incomplètes ou trompeuses), et l'exploration, qui consiste à essayer de nouvelles options pouvant conduire à de meilleurs résultats futurs au prix de renoncer à une opportunité d'exploitation. L'objectif d'optimiser les récompenses à long terme nécessite de résoudre efficacement cet équilibre.
En apprentissage automatique, le compromis est fondamental pour l'apprentissage par renforcement (RL), un type d'apprentissage où un agent prend des décisions en fonction des retours d'un environnement, qui peuvent être retardés ou épars. L'agent doit décider s'il doit exploiter une politique actuellement connue comme étant la meilleure ou explorer de nouvelles politiques pour améliorer les performances futures. Le dilemme apparaît dans des domaines tels que la conduite autonome, les systèmes de recommandation et l'IA de jeu.
Méthodes de bandit manchot multi-bras
Le problème du bandit manchot multi-bras (MAB) est un exemple classique du compromis, et de nombreuses méthodes ont été développées pour celui-ci. Epsilon-greedy est une approche simple où l'agent exploite la meilleure action connue la plupart du temps mais choisit une action aléatoire avec une probabilité epsilon. L'échantillonnage de Thompson équilibre l'exploration et l'exploitation en maintenant des distributions a posteriori sur les récompenses et en les échantillonnant. Les algorithmes de borne de confiance supérieure (UCB) sélectionnent les actions en comparant les récompenses moyennes avec des bonus d'incertitude.
Dans des contextes plus complexes, un agent peut traiter chaque point de décision comme un MAB où le gain est la récompense future attendue. Par exemple, la recherche arborescente Monte Carlo utilise une variante de l'UCB pour guider l'exploration de l'arbre de jeu, comme on le voit dans des programmes tels que les moteurs d'échecs.
Problèmes d'exploration
Certains environnements créent des défis spécifiques pour le compromis.
Récompense éparse : si les récompenses n'apparaissent que rarement, les agents peuvent ne pas persister dans l'exploration. Un exemple standard est le jeu Atari Montezuma's Revenge, où les récompenses claires sont rares.
Récompense trompeuse : lorsque certaines actions précoces donnent des récompenses immédiates mais petites, et que d'autres donnent des récompenses plus importantes mais retardées, les agents peuvent se retrouver piégés en exploitant les petites récompenses précoces.
Problème de télévision bruyante : si certaines observations sont irréductiblement bruyantes, comme une télévision avec des images aléatoires, un agent peut rester bloqué en observant à plusieurs reprises ces états imprévisibles.
Ces problèmes rendent difficile l'obtention d'un équilibre optimal, nécessitant des techniques supplémentaires pour guider l'exploration.
Méthodes de récompense d'exploration
Les méthodes de récompense d'exploration convertissent le dilemme en un problème purement exploitant en traitant l'exploration comme une forme de récompense intrinsèque. L'agent vise alors à maximiser la somme de la récompense extrinsèque de l'environnement et du bonus d'exploration intrinsèque. Les récompenses intrinsèques et extrinsèques sont écrites comme r_t^e et r_t^i à l'étape de temps t.
Cette approche diffère de l'exploitation de deux manières clés : premièrement, la récompense d'exploration est librement conçue par le chercheur, tandis que les récompenses externes sont données par l'environnement ; deuxièmement, alors que les récompenses extrinsèques sont généralement stationnaires, les récompenses intrinsèques sont non stationnaires, ce qui signifie que la même action donne de moins en moins de bonus à mesure qu'elle devient familière.
L'exploration basée sur le comptage mesure la fréquence à laquelle un état est visité et récompense les états moins visités, mais cela n'est réalisable que dans des espaces d'états petits et discrets. L'exploration basée sur la densité étend cela en utilisant un modèle de densité, où la visite d'un état donne également un crédit partiel aux états voisins.
L'exploration par entropie maximale ajoute l'entropie de la politique de l'agent comme terme intrinsèque, encourageant une politique qui favorise des actions aléatoires ou diverses.
Exploration basée sur la prédiction
Un modèle de dynamique directe prédit l'état suivant à partir de l'état et de l'action actuels : f : (s_t, a_t) mappé à s_{t+1}. À mesure que l'agent interagit avec l'environnement, il entraîne ce modèle à mieux prédire les transitions d'état pour les chemins familiers. Un bonus d'exploration basé sur la prédiction définit la récompense intrinsèque comme l'erreur entre les prédictions du modèle et les états suivants réels. Lorsqu'un état est nouveau, l'erreur du modèle est élevée, rendant cette action attrayante.
L'exploration par prédiction est particulièrement utile dans les espaces d'états de haute dimension où les comptages ne peuvent pas être utilisés. Les erreurs du modèle servent d'estimation de la surprise, ce qui encourage l'agent à rechercher des états plus difficiles à prédire, favorisant une exploration plus large sans guidage externe. Cette méthode est largement utilisée dans les systèmes récents de apprentissage par renforcement profond.