Échantillonnage de Thompson

Exemple d'utilisation de l'échantillonnage de Thompson.

L'échantillonnage de Thompson nommé d'après William R. Thompson, est un algorithme heuristique permettant de choisir des actions qui résolvent le dilemme exploration-exploitation dans le problème des bandits à K bras. Elle consiste à choisir l'action qui maximise la récompense attendue par rapport à une croyance tirée au hasard.

La description

Soit un ensemble de contextes ${\mathcal {X}}$, un ensemble d'actions ${\mathcal {A}}$, et des récompenses dans $\mathbb {R}$. A chaque tour, le joueur reçoit un contexte $x\in {\mathcal {X}}$, effectue une action $a\in {\mathcal {A}}$ et reçoit une récompense $r\in \mathbb {R}$ suivant une distribution qui dépend du contexte et de l'action effectuée. L'objectif du joueur est d'effectuer les actions qui maximisent les gains cumulés.

Les éléments de l'échantillonnage de Thompson sont les suivants:

1. une fonction de vraisemblance $P(r|\theta ,a,x)$;
2. un ensemble $\Theta$ de paramètres $\theta$ de la distribution de $r$;
3. une distribution à priori $P(\theta )$;
4. des observations ${\mathcal {D}}=\{(x;a;r)\}$;
5. une distribution a posteriori $P(\theta |{\mathcal {D}})\propto P({\mathcal {D}}|\theta )P(\theta )$, où$P({\mathcal {D}}|\theta )$ est la fonction de vraisemblance.

L’échantillonnage de Thompson consiste à jouer $a^{\ast }\in {\mathcal {A}}$ qui maximise l'espérance du gain attendu:

$\int \mathbb {I} \left[\mathbb {E} (r|a^{\ast },x,\theta )=\max _{a'}\mathbb {E} (r|a',x,\theta )\right]P(\theta |{\mathcal {D}})d\theta ,$

où $\mathbb {I}$ est la fonction indicatrice.

En pratique, cette règle est implémenté par échantillonnage, à chaque tour, des paramètres $\theta ^{\ast }$ à partir de la distribution a posteriori $P(\theta |{\mathcal {D}})$, et en choisissant l'action $a^{\ast }$qui maximise $\mathbb {E} [r|\theta ^{\ast },a^{\ast },x]$, l'espérance du gain attendu prenant en compte le paramètre échantillonné, l'action et le contexte actuel. Conceptuellement, cela signifie que le joueur instancie aléatoirement ses croyances à chaque tour et agit optimalement à partir de ces informations. Dans la plupart des applications pratiques, il est informatiquement coûteux de maintenir en mémoire et d'échantillonner à partir des distributions a posteriori exactes. L'échantillonnage de Thompson est souvent utilisé avec des techniques d'échantillonnage approximative.

Histoire

L'échantillonnage de Thompson a été décrit par Thompson en 1933 . Il a par la suite été redécouvert de nombreuses fois indépendamment dans le contexte de problèmes de bandits à K bras. Une première preuve de convergence pour dans l'application aux bandits a été présentée en 1997. La première application à des processus de décision markovien remonte à l'an 2000 . Une approche connexe a été publiée en 2010. En 2010, il a également été démontré que l'échantillonnage de Thompson se corrige automatiquement de manière instantanée . Des résultats montrant la convergence asymptotique pour les bandits à information contextuelle ont été publiés en 2011.

Aujourd'hui, l'échantillonnage de Thompson est largement utilisé dans de nombreux problèmes d'apprentissage en ligne: l’échantillonnage de Thompson a également été appliqué aux tests A / B dans la conception de sites Web et la publicité en ligne. L'échantillonnage de Thompson sert de base à l'apprentissage accéléré dans la prise de décision décentralisée.

Liens avec d'autres approches

Correspondance de probabilité

La correspondance de probabilité (Probability matching) est une stratégie de décision dans laquelle les prévisions d'appartenance à une classe sont proportionnelles aux taux de base de la classe. L'échantillonnage de Thompson est une application de ce principe général au problème de bandits.

Ainsi, si, à l’entraînement, des tirages positifs sont observés dans 60% des cas et des tirages négatifs dans 40% des cas, l’observateur qui utilise une stratégie de correspondance des probabilités prédira (pour les exemples non étiquetés) un résultat "positif" dans 60% des cas, et un résultat "négatif" sur 40% des cas.

Algorithmes de borne supérieure de confiance (UCB)

Les algorithmes d'échantillonnage de Thompson et les algorithmes liés à la borne supérieure de confiance sont tous deux des algorithmes "optimistes": ils prennent en compte l'incertitude sur l'estimation des paramètres et explorent des actions ayant une probabilité non nulle d'être optimales.

En exploitant cette propriété, il est possible de traduire les limites de regret établies pour les algorithmes UCB en limites de regret bayésiennes pour l'échantillonnage de Thompson ou d'unifier l'analyse de regret entre ces algorithmes et d'autres classes de problèmes.