Bandits à plusieurs bras : la meilleure solution d'apprentissage par renforcement pour votre tâche

Les bandits multi-armés (MAB) constituent une pierre angulaire dans le monde de l'apprentissage par renforcement, offrant un mécanisme puissant pour négocier des scénarios qui nécessitent un équilibre optimal entre l'exploration et l'exploitation. L'exploration consiste à essayer de nouvelles options, tandis que l'exploitation signifie s'en tenir à la meilleure option actuelle. Dans de telles circonstances, les MAB s'avèrent souvent être un choix stellaire en raison de leurs mécanismes d'apprentissage intelligents.

Tout d'abord, démêlons le concept derrière les MAB. Imaginez un joueur entouré d'un ensemble de machines à sous, chacune connue sous le nom de "bandit manchot". Les décisions critiques à prendre ici impliquent de déterminer quelles machines jouer, l'ordre de jeu et la fréquence de jeu. Le hic, c'est que chaque machine offre une récompense différente et incertaine. Le but ultime est d'amasser la récompense cumulée la plus élevée sur une séquence de jeux.

Qu'est-ce qu'un bandit multi-armé ?

Le nom "bandit à plusieurs bras" vient d'une expérience de pensée impliquant un joueur sur une rangée de machines à sous (souvent appelées "bandits à un bras"). Le joueur doit décider quelles machines jouer, combien de fois jouer à chaque machine et dans quel ordre, dans le but de maximiser sa récompense totale.

Dans une définition plus formelle, un problème MAB est un tuple (A, R)

L'objectif du problème MAB est de trouver une politique π (un mappage des données historiques aux actions) qui maximise la récompense totale attendue Q sur un nombre donné de tours.

Le dilemme clé du MAB est le compromis entre "exploration" et "exploitation":

1. L'exploration consiste à essayer différentes armes pour en savoir plus sur la récompense qu'elles pourraient rapporter. Cela peut impliquer de tirer des bras sous-optimaux, mais cela aide à recueillir des informations sur le système.
2. L'exploitation consiste à tirer sur le bras que l'agent croit actuellement avoir la récompense attendue la plus élevée, sur la base des informations qu'il a recueillies jusqu'à présent.

Équilibrer l'exploration et l'exploitation est un défi central dans l'apprentissage par renforcement et les problèmes MAB.

Pour résoudre ce problème, une multitude d'algorithmes ont été développés, notamment les stratégies Epsilon-Greedy, Upper Confidence Bound (UCB) et Thompson Sampling.

L'examen détaillé des bandits contextuels en tant qu'extension du MAB sera couvert dans les prochains articles.

L'Epsilon(ε) - Gourmand

La stratégie Epsilon(ε)-Greedy adhère à un principe simple. La plupart du temps, quantifié par (1 - ε), il opte pour l'action donnant la récompense estimée la plus élevée, exploitant ainsi la meilleure option connue. Cependant, le reste du temps, quantifié en ε, il choisit une action aléatoire, explorant ainsi de nouvelles possibilités. L'ingéniosité de cette stratégie réside dans sa simplicité et son efficacité, malgré la mise en garde qu'elle pourrait sélectionner des actions moins gratifiantes avec la même probabilité que les plus gratifiantes lors de sa phase d'exploration et la valeur de ε détermine l'équilibre entre l'exploration et l'exploitation.

Mathématiquement, il peut être défini comme suit :

Cela peut être défini par le pseudo-code suivant :

 Initialize Q(a) for all a Repeat: Generate a random number p between 0 and 1 If p < epsilon: Select a random action a Else: Select action a with the highest Q(a) Execute action a and observe reward r Update Q(a) = Q(a) + alpha * (r - Q(a))

L'implémentation Pythonic de la stratégie Epsilon-Greedy est assez simple :

 import numpy as np class EpsilonGreedy: def __init__(self, epsilon, counts, values): self.epsilon = epsilon self.counts = counts self.values = values def select_arm(self): if np.random.random() < self.epsilon: return np.random.choice(len(self.values)) else: return np.argmax(self.values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

L'algorithme ε-gourmand a l'avantage de la simplicité et la garantie qu'il continuera à explorer (un peu) même après de nombreuses étapes. Cependant, il ne tient pas compte de ce que l'on sait de chaque action lorsqu'il explore, contrairement à UCB ou à Thompson Sampling.

UCB

À l'inverse, la stratégie UCB tient compte à la fois de la récompense estimée et de l'incertitude ou de la variance associée au moment de décider d'une action. Il manifeste une préférence pour les actions à forte incertitude, cherchant à la diminuer et assurant une phase d'exploration plus productive. La stratégie UCB est mathématiquement définie comme suit :

Son implémentation Python est la suivante :

 class UCB: def __init__(self, counts, values): self.counts = counts self.values = values def select_arm(self): n_arms = len(self.counts) for arm in range(n_arms): if self.counts[arm] == 0: return arm ucb_values = [0.0 for arm in range(n_arms)] total_counts = sum(self.counts) for arm in range(n_arms): bonus = sqrt((2 * log(total_counts)) / float(self.counts[arm])) ucb_values[arm] = self.values[arm] + bonus return np.argmax(ucb_values) def update(self, chosen_arm, reward): self.counts[chosen_arm] += 1 n = self.counts[chosen_arm] value = self.values[chosen_arm] new_value = ((n-1) / float(n)) * value + (1 / float(n)) * reward self.values[chosen_arm] = new_value

L'équilibre entre l'exploration et l'exploitation dans UCB provient de sa formule : la valeur estimée d'une action plus un terme qui diminue avec le temps (à mesure que l'on en apprend davantage sur l'action) mais qui augmente avec l'incertitude sur cette action. Ainsi, l'algorithme a tendance à explorer les bras avec une incertitude élevée et une récompense potentielle élevée.

Échantillonnage de Thompson

Thompson Sampling est un algorithme d'inspiration bayésienne pour le problème des bandits multi-armés. Il attribue une distribution a priori aux probabilités de récompense de chaque bandit (ou de chaque action), puis met à jour ces a priori au fur et à mesure que les récompenses sont observées. La sélection des actions est probabiliste, selon la distribution a posteriori sur la meilleure action.

Dans un cadre Beta-Bernoulli, nous considérons la distribution des récompenses de chaque bandit comme une distribution de Bernoulli (c'est-à-dire, des récompenses binaires 0 ou 1). Nous attribuons ensuite une bêta avant la probabilité d'obtenir une récompense. La distribution bêta est l'a priori conjugué de la distribution de Bernoulli, ce qui permet une mise à jour a posteriori facile.

Logique:

1. Attribuez à chaque bandit une distribution bêta avec les paramètres α = 1, β = 1 (uniform prior).

2. Pour chaque tour :

   1. Échantillonnez un nombre aléatoire de la distribution bêta actuelle de chaque bandit.
   2. Sélectionnez le bandit avec le numéro échantillonné le plus élevé et tirez sur ce bandit.
   3. Observez la récompense du bandit tiré. Si c'est un succès (1), augmentez l'α du bandit de un ; si c'est un échec (0), augmentez le β du bandit de un.
   4. Répétez les étapes 2 et 3.

 import numpy as np from scipy.stats import beta class Bandit: def __init__(self, true_probability): self.true_probability = true_probability self.alpha = 1 self.beta = 1 def pull(self): return np.random.random() < self.true_probability def sample(self): return np.random.beta(self.alpha, self.beta) def update(self, reward): self.alpha += reward self.beta += (1 - reward) def Thompson(bandits, num_trials): rewards = np.zeros(num_trials) for i in range(num_trials): # Thompson sampling j = np.argmax([b.sample() for b in bandits]) # Pull the arm for the bandit with the largest sample reward = bandits[j].pull() # Update rewards log rewards[i] = reward # Update the distribution for the bandit whose arm we just pulled bandits[j].update(reward) return rewards # Suppose we have 3 bandits with these true probabilities true_probabilities = [0.2, 0.5, 0.75] bandits = [Bandit(p) for p in true_probabilities] # Run experiment rewards = Thompson(bandits, num_trials=10000) # Print the total reward print("Total reward earned:", rewards.sum()) print("Overall win rate:", rewards.sum() / len(rewards))

Thompson Sampling "explore" ainsi les actions dont il est incertain (celles pour lesquelles la distribution des valeurs est étalée) et "exploite" les actions qu'il estime pouvoir avoir une valeur élevée (celles pour lesquelles la distribution est biaisée vers les valeurs élevées).

Au fil du temps, à mesure que l'on en apprend davantage sur chaque action, les distributions deviennent plus pointues et les actions choisies par l'algorithme ont tendance à converger vers celle avec la valeur attendue la plus élevée.

L'équilibre exploration/exploitation dans Thompson Sampling provient naturellement de la forme des distributions. Cette méthode est assez efficace, mais peut être plus complexe à mettre en œuvre que UCB ou ε-greedy, en particulier pour les problèmes avec des espaces d'action larges ou continus, ou des structures de récompense complexes.

Pourquoi les bandits multi-armés sont-ils le meilleur RL pour votre tâche ?

1. Simplicité : les algorithmes MAB sont plus simples et plus efficaces en termes de calcul que les algorithmes RL à part entière, qui nécessitent de maintenir et de mettre à jour une table ou un approximateur de valeurs d'état-action potentiellement volumineux.
2. Équilibre entre exploration et exploitation : les algorithmes MAB fournissent des méthodes robustes pour gérer le compromis entre essayer de nouvelles actions et s'en tenir aux bonnes actions connues.
3. Adaptabilité en temps réel : les algorithmes MAB peuvent s'adapter en temps réel aux changements dans la distribution des récompenses des actions.
4. Intégration facile : La simplicité et l'efficacité des MAB permettent une intégration facile dans les systèmes existants, offrant des avantages immédiats avec un minimum de perturbations.
5. Large applicabilité : les MAB ont été appliqués avec succès dans divers domaines, notamment la publicité (choix de l'annonce à afficher pour maximiser le taux de clics), la santé (personnalisation des stratégies de traitement) et l'optimisation des pages Web (test A/B).

Applications des MAB

Les bandits multi-armés (MAB) ont un large éventail d'applications dans divers secteurs et domaines. Voici quelques exemples de la façon dont ils peuvent être utilisés :

1. Publicité en ligne : les MAB peuvent être utilisés pour ajuster dynamiquement la sélection de publicités à afficher aux utilisateurs en fonction de leurs interactions. Cela permet de maximiser les taux de clics ou les conversions au fil du temps.
2. Essais cliniques : Dans la recherche médicale, les algorithmes MAB peuvent être utilisés pour affecter dynamiquement des patients à différents traitements. Cela garantit que davantage de patients reçoivent les traitements les plus efficaces, réduisant ainsi le regret, c'est-à-dire la perte subie en raison du fait de ne pas toujours choisir le meilleur traitement.
3. Recommandation d'articles d'actualités : les sites Web d'actualités peuvent utiliser les MAB pour personnaliser les articles présentés à chaque utilisateur. L'algorithme MAB peut apprendre au fil du temps quels types d'articles intéressent chaque utilisateur et ajuster les recommandations en conséquence.
4. Tarification dynamique : les plates-formes de commerce électronique ou les compagnies aériennes peuvent utiliser les algorithmes MAB pour optimiser leurs stratégies de tarification en temps réel, en maximisant les revenus en fonction du comportement des clients et de la dynamique du marché.
5. Routage réseau : Dans les réseaux informatiques, les algorithmes MAB peuvent être utilisés pour gérer la congestion et optimiser le routage des paquets. Chaque route peut être traitée comme un bras, et l'algorithme peut sélectionner dynamiquement des routes pour minimiser la perte de paquets ou la latence.
6. Réglage des hyperparamètres d'apprentissage automatique : les MAB peuvent également être utilisés pour optimiser la sélection des hyperparamètres dans les modèles d'apprentissage automatique. Chaque ensemble d'hyperparamètres peut être traité comme un bras, et l'algorithme peut affiner de manière itérative la sélection pour trouver la configuration de modèle optimale.

Essentiellement, l'utilité des MAB s'étend bien au-delà des tâches d'apprentissage par renforcement conventionnelles. Ils symbolisent un cadre efficace pour améliorer les processus de prise de décision dans des environnements d'incertitude, fournissant des solutions pratiques aux problèmes du monde réel dans divers domaines. Par conséquent, lorsque la tâche à accomplir consiste à équilibrer l'exploration et l'exploitation, les MAB apparaissent souvent comme l'option de choix, offrant une solution polyvalente, robuste et adaptative aux énigmes de la prise de décision.

Conclusion

Les bandits multi-armés, avec leur capacité à équilibrer efficacement l'exploration et l'exploitation, fournissent une solution robuste à de nombreux problèmes de prise de décision dans le monde réel. Leur adaptabilité et leur polyvalence inhérentes en font un outil précieux, non seulement dans le domaine de l'apprentissage par renforcement, mais également dans un large éventail d'applications, des soins de santé à la publicité en ligne. Que vous soyez un scientifique des données, un passionné d'apprentissage automatique ou un professionnel cherchant à améliorer vos processus de prise de décision, comprendre et mettre en œuvre des stratégies MAB peut être une expérience enrichissante et enrichissante.