Thompson Sampling, Thompson Sampling, Thompson Sampling, Thompson Sampling, Thompson Sampling

Introduction

Dans de nombreux scénarios d’apprentissage automatique, les algorithmes doivent prendre des décisions en temps réel tout en apprenant de leur environnement. Ce problème est connu sous le nom de dilemme exploration-exploitation, et il est particulièrement présent dans le cadre des bandits manchots (multi-armed bandit problems). Parmi les nombreuses stratégies proposées, Thompson Sampling est l’une des plus élégantes et efficaces.

Cette méthode combine les principes du raisonnement bayésien avec une stratégie probabiliste pour résoudre les problèmes de décision séquentielle de manière optimale.

Le problème des bandits manchots

Le problème des bandits manchots est une analogie célèbre en apprentissage par renforcement. Imaginez une machine à sous avec plusieurs leviers (ou « bras »), chacun ayant une probabilité différente de récompense. Le but est de maximiser la somme des gains en tirant sur les bons leviers.

Cependant, ces probabilités sont inconnues. L’algorithme doit donc choisir entre :

• Explorer : essayer différents bras pour apprendre leurs probabilités de gain.
• Exploiter : jouer le bras actuellement le plus prometteur.

Qu’est-ce que Thompson Sampling ?

Thompson Sampling est une méthode de prise de décision probabiliste qui résout ce dilemme. Elle repose sur une approche bayésienne : à chaque pas de temps, on tire un échantillon de la distribution de probabilité associée à chaque bras, et on joue celui qui a l’échantillon le plus élevé.

Étapes générales :

1. On maintient une distribution de croyance (a priori bayésien) sur la probabilité de succès de chaque bras.
2. À chaque itération, on échantillonne une probabilité de réussite pour chaque bras à partir de sa distribution actuelle.
3. On choisit le bras avec la probabilité échantillonnée la plus élevée.
4. On met à jour la distribution du bras choisi en fonction du résultat obtenu (succès ou échec).

Illustration simple (cas binaire)

Supposons que chaque bras donne soit un succès (1) soit un échec (0). On peut alors modéliser la probabilité de succès de chaque bras avec une distribution Bêta (Beta), qui est la conjugée de la loi de Bernoulli.

• Pour chaque bras, on initialise une Beta(1,1) (équivalent à un uniforme sur [0,1])
• Après chaque tentative :
  • Si succès → incrémenter le paramètre alpha
  • Si échec → incrémenter le paramètre beta

pythonCopierModifier# Exemple Python
import numpy as np

# Initialisation pour 2 bras
alphas = [1, 1]
betas = [1, 1]

def thompson_sampling():
    samples = [np.random.beta(a, b) for a, b in zip(alphas, betas)]
    return np.argmax(samples)

# Mise à jour
def update(chosen_arm, reward):
    if reward == 1:
        alphas[chosen_arm] += 1
    else:
        betas[chosen_arm] += 1

Avantages de Thompson Sampling

1. Très efficace : souvent aussi bon, voire meilleur que des stratégies comme UCB (Upper Confidence Bound).
2. Exploration naturelle : pas besoin de heuristiques ; l’incertitude intrinsèque guide l’exploration.
3. Facile à implémenter : quelques lignes suffisent.
4. Généralisable : fonctionne avec des récompenses continues, bruitées ou non stationnaires.

Limites et inconvénients

1. Approche bayésienne : nécessite un modèle probabiliste a priori, ce qui peut ne pas convenir à toutes les situations.
2. Complexité computationnelle : l’échantillonnage peut devenir coûteux pour des modèles complexes.
3. Mise à l’échelle : avec un très grand nombre de bras, la gestion des distributions devient difficile.

Comparaison avec d’autres stratégies

Cas d’usage réels

• A/B Testing dynamique : sélectionner la meilleure version d’un site en temps réel.
• Recommandation de contenu : choisir les articles à afficher en fonction des taux de clics.
• Publicité en ligne : optimiser quelles annonces montrer pour maximiser les conversions.
• Applications médicales : tester des traitements de manière éthique (plus de patients reçoivent le traitement qui fonctionne le mieux).

Étendre Thompson Sampling

Thompson Sampling n’est pas limité à des problèmes binaires. Il existe des variantes pour :

• Récompenses continues (modélisées par des distributions normales)
• Bandits contextuels : le choix dépend du contexte (caractéristiques de l’utilisateur, moment de la journée, etc.)
• Environnements non stationnaires (adaptation dynamique des croyances)

Implémentation avec bandits contextuels (simplifiée)

pythonCopierModifierimport numpy as np

class ContextualBandit:
    def __init__(self, n_arms):
        self.alphas = np.ones(n_arms)
        self.betas = np.ones(n_arms)

    def select_arm(self):
        return np.argmax([np.random.beta(a, b) for a, b in zip(self.alphas, self.betas)])

    def update(self, chosen_arm, reward):
        if reward == 1:
            self.alphas[chosen_arm] += 1
        else:
            self.betas[chosen_arm] += 1

Conclusion

Thompson Sampling est une solution élégante et performante au dilemme exploration/exploitation. Grâce à une approche probabiliste bayésienne, il permet d’équilibrer intelligemment l’apprentissage de nouvelles informations avec l’utilisation des connaissances déjà acquises. Adapté à de nombreux cas d’usage en machine learning, il fait partie des outils incontournables du data scientist moderne.