🤖 machine learning

A Broader View of Thompson Sampling

Ce papier élucide le mécanisme sous-jacent au succès de l'échantillonnage de Thompson en le reformulant comme un algorithme d'optimisation en ligne qui imite une politique stationnaire optimale au sens de Bellman, où l'avidité est régularisée par l'incertitude résiduelle, offrant ainsi un nouveau cadre pour comprendre sa dynamique et améliorer les politiques.

Auteurs originaux : Yanlin Qu, Hongseok Namkoong, Assaf Zeevi

Publié 2026-05-28

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Yanlin Qu, Hongseok Namkoong, Assaf Zeevi

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

La Vue d'Ensemble : Résoudre le « Mystère » d'un Algorithme Célèbre

Imaginez que vous êtes un chef essayant de trouver la meilleure recette pour un nouveau plat. Vous avez deux ingrédients (appelons-les Bras 1 et Bras 2), mais vous ne savez pas lequel a le meilleur goût. Vous devez continuer à cuisiner pour apprendre, mais vous voulez aussi servir le meilleur plat à vos clients dès maintenant. C'est le problème classique du « Bandit Multi-Arme » : équilibrer l'exploration (essayer de nouvelles choses pour apprendre) et l'exploitation (utiliser ce que l'on sait fonctionner le mieux).

Pendant des décennies, une méthode spécifique appelée Échantillonnage de Thompson a été la référence absolue. Elle est célèbre car elle fonctionne incroyablement bien en pratique. Cependant, contrairement à d'autres méthodes où les règles sont claires (comme « choisissez toujours l'option avec le score de confiance le plus élevé »), l'Échantillonnage de Thompson semblait un peu magique. Cela fonctionne, mais personne ne pouvait vraiment expliquer pourquoi il équilibre si parfaitement l'apprentissage et le gain.

Ce document tire le rideau. Les auteurs montrent que l'Échantillonnage de Thompson n'est pas un simple coup de chance ; c'est en réalité un algorithme sophistiqué d'optimisation en ligne. Ils ont découvert qu'il fonctionne en essayant de minimiser un type spécifique de « regret » (la différence entre ce que vous avez obtenu et ce que vous auriez pu obtenir) tout en étant « régularisé » (guidé) par une mesure d'incertitude.

L'Idée Centrale : Une Nouvelle Façon de Mesurer le « Regret »

Pour comprendre le document, nous devons examiner comment ils mesurent le succès.

L'Ancienne Façon (Récompenses Décotées) :
Imaginez que vous jouez à un jeu vidéo où les points que vous obtenez maintenant valent 100 %, mais les points que vous obtenez plus tard ne valent que 90 %, puis 81 %, et ainsi de suite. C'est ce qu'on appelle le « décotage ». La célèbre politique de l'Indice de Gittins utilise cela. C'est excellent pour le jeu, mais elle présente un défaut : elle peut arrêter d'explorer une option potentiellement meilleure trop tôt, car les points futurs ne semblent pas valoir le risque. Dans le monde réel, où nous voulons apprendre tout ce qui est possible sur le long terme, cela peut être une erreur.

La Nouvelle Façon du Document (Regret au Carré) :
Les auteurs proposent une nouvelle façon de voir le problème. Au lieu de décoter le futur, ils regardent le carré du regret.

Analogie : Imaginez que vous conduisez une voiture.
- Regret Linéaire : Si vous déviez de 1 mile de votre trajectoire, vous êtes à 1 mile de la route. Si vous déviez de 10 miles, vous êtes à 10 miles de la route.
- Regret au Carré : Si vous déviez de 1 mile, vous êtes à 1 mile de la route. Mais si vous déviez de 10 miles, vous êtes maintenant à 100 « unités » de mauvaise conduite.
- Pourquoi cela compte : En mettant l'erreur au carré, l'algorithme devient très sensible aux grosses erreurs. Il force le système à éviter les erreurs énormes, ce qui conduit naturellement à une stratégie qui explore suffisamment pour éviter de rester bloqué sur un mauvais chemin, mais pas au point de perdre du temps.

Les auteurs appellent cela la « Stationnarisation Fidèle ». C'est une façon élégante de dire : « Nous avons trouvé une règle mathématique qui reste la même dans le temps (stationnaire) mais qui capture parfaitement l'objectif de minimiser les erreurs à long terme (fidèle). »

Le « Secret » : Incertitude vs Tension

Le document révèle que l'Échantillonnage de Thompson fonctionne en résolvant un problème mathématique qui ressemble à ceci :

Minimiser (Erreur) + (Pénalité d'Incertitude)

Les auteurs décomposent cela en deux forces concurrentes :

Avidité (Exploitation) : Vous voulez choisir le bras qui semble le meilleur maintenant pour obtenir la récompense la plus élevée.
Régularisation (Exploration) : Vous avez besoin d'une « pénalité » pour vous empêcher d'être trop avide. Cette pénalité est basée sur la quantité de ce que vous ne savez pas.

La Découverte :
Les auteurs ont découvert que l'Échantillonnage de Thompson utilise un type spécifique de pénalité appelé Covariance Bisérielle.

La Métaphore : Imaginez que vous pariez sur une course de chevaux.
- Logique de l'Échantillonnage de Thompson : « Je ne suis pas sûr de quel cheval va gagner. Plus je suis incertain (plus les chevaux se ressemblent), plus je devrais parier sur le outsider pour voir s'il peut gagner. » Il mesure l'Incertitude.
- Logique « Bellman-Optimale » (L'Idéal) : Les auteurs ont calculé ce que ferait l'algorithme parfait. Ils ont découvert que l'algorithme parfait ne regarde pas seulement l'incertitude ; il regarde la Tension.
- La Métaphore : « Je suis incertain, mais est-ce que cela vaut le risque de changer ? Si le cheval de tête est en réalité très fort et l'outsider faible, même si je suis un peu incertain, je ne devrais pas changer. Mais si le cheval de tête est fragile et l'outsider fort, la tension est élevée, et je dois changer. »

Le Problème :
L'Échantillonnage de Thompson devient parfois « trop curieux ». Il continue d'explorer une option sous-performante simplement parce qu'il y a une certaine incertitude, même lorsque la « tension » (le bénéfice du changement) est en réalité faible. C'est comme vérifier le four toutes les 30 secondes parce que vous êtes nerveux, même si la recette dit que le gâteau va bien.

La Solution : Une Correction « En Une Étape »

Le document ne se contente pas de critiquer l'Échantillonnage de Thompson ; il propose un moyen de le corriger en utilisant la même logique qui alimente l'algorithme « parfait ».

Ils proposent une étape d'Amélioration de la Politique.

Analogie : Imaginez que vous êtes un étudiant passant un examen.
- Échantillonnage de Thompson : Vous répondez aux questions en vous basant sur votre intuition actuelle.
- L'Amélioration : Avant de rendre votre copie, vous prenez un moment pour examiner vos réponses et vous demandez : « Si j'avais su ce que je sais après avoir répondu à cette question, aurais-je changé ma réponse ? »
- Le Résultat : Les auteurs montrent que faire cette seule étape de « regard vers l'avant » corrige presque tous les défauts de l'Échantillonnage de Thompson. Cela transforme l'algorithme, passant d'une logique pilotée par l'« incertitude » à une logique pilotée par la « tension ».

Dans leurs expériences, ce simple ajustement a comblé 90 % de l'écart de performance entre le célèbre Échantillonnage de Thompson et leur algorithme théorique « parfait ».

Résumé des Points Clés

L'Échantillonnage de Thompson est un Optimiseur : Ce n'est pas seulement une heuristique ; c'est un algorithme qui minimise un type spécifique d'erreur quadratique.
Le Défaut : Il repose sur l'« Incertitude » (à quel point je suis confus) plutôt que sur la « Tension » (cela vaut-il la peine de faire l'effort de changer ?). Cela le fait parfois explorer trop.
La Correction : En appliquant une étape standard d'« amélioration de la politique » (regarder une étape en avant), nous pouvons modifier l'algorithme pour qu'il se concentre sur la « Tension ».
Le Résultat : Cet ajustement simple rend l'algorithme presque parfait, performant presque aussi bien que la meilleure stratégie théorique possible, sans avoir besoin de mathématiques complexes nouvelles.

Le document dit essentiellement : « Nous avons trouvé la recette secrète de l'Échantillonnage de Thompson. C'est formidable, mais si vous ajustez un peu l'assaisonnement (la régularisation) pour vous concentrer sur le bon type de tension, cela devient encore meilleur. »

Résumé Technique : Une Vue Plus Large de Thompson Sampling

Énoncé du Problème
Thompson Sampling (TS) est une heuristique largement utilisée pour le problème du Bandit Multi-Arme (MAB), connue pour son succès empirique et ses bornes de regret théoriques. Cependant, contrairement aux politiques Upper Confidence Bound (UCB) ou à l'indice de Gittins, le principe d'optimisation explicite régissant l'équilibre de TS entre exploration et exploitation reste opaque. Alors que Gittins (1979) a formulé le MAB bayésien comme un Processus de Décision Markovien (MDP) pour dériver une politique optimale, cette approche repose sur des récompenses à horizon infini avec actualisation. Cette formulation conduit à un « apprentissage incomplet » (échec à identifier le bras optimal infiniment souvent), ce qui contredit l'objectif de minimisation du regret à horizon fini central dans la littérature sur les MAB (Robbins 1952 ; Lai et Robbins 1985). L'article comble le déficit de compréhension de TS en cherchant une formulation stationnaire « fidèle » qui s'aligne sur la minimisation du regret à horizon fini tout en conservant la faisabilité de la programmation dynamique.

Méthodologie
Les auteurs proposent un cadre de stationnarisation fidèle pour reformuler le problème de minimisation du regret non stationnaire à horizon fini en un problème d'optimisation en ligne stationnaire.

Objectif de Regret Quadratique : Au lieu de minimiser directement le regret cumulatif $R_T$ ou d'utiliser des récompenses actualisées, les auteurs introduisent la minimisation du regret quadratique cumulatif $R_2$ . Ils établissent une borne $R_T \leq \sqrt{R_2 \cdot T}$ . La minimisation de la somme à horizon infini des regrets quadratiques $R_2(Q; \pi_0) = \mathbb{E}[\sum r^2(q_t; \pi_t)]$ garantit que la politique atteint le taux de regret optimal $O(\sqrt{T})$ tout en fournissant un objectif stationnaire.
Équation de Bellman Stationnaire : Cet nouvel objectif produit une équation de Bellman stationnaire pour la fonction de valeur $V(\pi_t)$ (le regret quadratique futur minimal) :
$V(\pi_t) = \min_{q_t} \left[ r^2(q_t; \pi_t) + q_t \cdot \mathbb{E}_{\pi_t}[V(\pi_{t+1}) | A_t = \cdot] \right]$
Contrairement à l'indice de Gittins (qui maximise la récompense actualisée linéaire), cette minimisation est quadratique par rapport aux probabilités d'action, conduisant à une politique optimale randomisée plutôt que déterministe.
Forme d'Optimisation en Ligne : Par un changement de variables se concentrant sur la récompense attendue du prochain tour $x_t$ , les auteurs déduisent que la politique optimale en $R_2$ ( $Q_{R2}$ ) prend la forme d'un problème d'optimisation en ligne :
$x_{R2}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{R2}(\pi_t) x_t \right]$
Ici, le premier terme représente l'exploitation instantanée (avidité), et le second terme est une régularisation linéaire représentant l'exploration. Le régularisateur $\nu_{R2}(\pi_t)$ est dérivé de l'équation de Bellman et mesure la tension entre exploration et exploitation (la différence de valeur future entre le tirage des bras).
Réinterprétation de Thompson Sampling : Les auteurs démontrent que Thompson Sampling admet exactement la même forme d'optimisation en ligne :
$x_{TS}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{TS}(\pi_t) x_t \right]$
Cependant, son régularisateur $\nu_{TS}(\pi_t)$ est la covariance bisérielle entre l'écart de récompense ( $\theta_1 - \theta_2$ ) et l'identité du bras optimal ( $\text{sign}(\theta_1 - \theta_2)$ ). Ce régularisateur mesure l'incertitude quant auquel des bras est meilleur, plutôt que la tension entre la récompense immédiate et la valeur future.

Contributions Clés

Stationnarisation Fidèle : L'article introduit une formulation stationnaire (minimisation du regret quadratique) qui préserve l'essence de la minimisation du regret à horizon fini, comblant le fossé entre l'échantillonnage heuristique et la programmation dynamique fondée sur des principes.
Unification Structurelle : Il révèle que Thompson Sampling et la politique optimale de Bellman ( $Q_{R2}$ ) sont tous deux des instances d'algorithmes d'optimisation en ligne qui arbitrent entre l'avidité et un régularisateur.
Identification du Mécanisme : L'article identifie le mécanisme spécifique qui pilote TS : il régularise l'avidité en fonction de l'incertitude (covariance bisérielle), tandis que la politique optimale régularise en fonction de la tension (différence de valeur future).
Amélioration de la Politique : En exploitant le cadre de Bellman, les auteurs proposent une étape standard d'amélioration de politique pour TS. En évaluant la fonction de valeur de TS et en la réinjectant dans l'équation de Bellman, ils dérivent une politique améliorée ( $Q_{TS'}$ ) qui utilise un régularisateur basé sur la tension.

Résultats

Écart de Performance : Des expériences numériques sur des bandits gaussiens et de Bernoulli montrent que la politique optimale en $R_2$ ( $Q_{R2}$ ) atteint un regret cumulatif significativement inférieur à celui de Thompson Sampling. Cet écart est attribué au fait que le régularisateur de TS est une mesure d'incertitude qui échoue à capturer la « tension » lorsque le bras leader est incertain mais que le bras sous-optimal est surexploité.
Échantillonnage Orienté Information (IDS) : L'article constate que l'IDS, une autre heuristique, partage la même structure de régularisateur basée sur la tension que $Q_{R2}$ et performe de manière presque identique à la politique optimale de Bellman, comblant ainsi les perspectives de la théorie de l'information et de la programmation dynamique.
Amélioration en Une Étape : Une seule étape d'amélioration de politique appliquée à Thompson Sampling comble environ 90 % de l'écart de performance entre TS et la référence optimale de Bellman. Cette amélioration transforme efficacement le régularisateur de TS d'une mesure d'incertitude en une mesure de tension.
Propriété Structurelle dans le Cas K-Armé : Dans le cadre à $K$ bras, la politique optimale de Bellman (et la TS améliorée) assigne une probabilité positive à au plus deux bras à n'importe quel tour, tandis que la TS standard peut assigner une probabilité positive à tous les bras. L'étape d'amélioration de politique confère à TS cette parcimonie structurelle.

Signification
L'article prétend fournir une « vue plus large » de Thompson Sampling en le reformulant comme un algorithme d'optimisation en ligne. Ce prisme :

Explique l'Heuristique : Il clarifie que TS équilibre exploration et exploitation en régularisant l'avidité avec une mesure d'incertitude résiduelle.
Identifie les Limites : Il pointe du doigt que la dépendance de TS à l'incertitude plutôt qu'à la tension conduit à un comportement sous-optimal dans des régimes spécifiques (par exemple, lorsque le bras optimal est incertain mais que le bras sous-optimal est clairement surexploité).
Permet une Amélioration Principée : Il offre un cadre rigoureux pour améliorer les algorithmes d'échantillonnage posterior. En alignant le régularisateur sur la mesure de tension optimale de Bellman, les auteurs démontrent que TS peut être considérablement amélioré avec une surcharge computationnelle minimale (une seule itération de politique), le rapprochant de l'optimum théorique sans abandonner sa nature basée sur l'échantillonnage.