Thompson Sampling

Thompson Sampling est une méthode probabiliste utilisée dans les problèmes de bandits manchots (multi-armed bandit). Contrairement à l’algorithme UCB qui utilise une borne de confiance pour chaque action, Thompson Sampling échantillonne une récompense possible pour chaque action à partir de la distribution de probabilité des récompenses, puis choisit l’action avec la plus grande récompense échantillonnée. C’est une méthode de probabilistic exploration-exploitation qui tend à être plus efficace dans certains contextes.

Le principe de Thompson Sampling repose sur l’idée que les récompenses suivent une distribution probabiliste (par exemple, une distribution Beta pour les récompenses binaires), et au lieu de déterminer une seule estimation de la récompense (comme avec la moyenne dans UCB), il échantillonne cette récompense pour chaque bras. Cette approche permet de mieux gérer l’exploration et l’exploitation dans des environnements plus complexes.

Formule de Thompson Sampling :

1. À chaque tour $t$, on met à jour la distribution de probabilité (par exemple, une Beta) des récompenses pour chaque bras.

2. On échantillonne une récompense à partir de cette distribution.

3. On choisit le bras avec la plus grande valeur échantillonnée.