Échantillonnage de Thompson

Soit un ensemble de contextes ${\displaystyle {\mathcal {X}}}$, un ensemble d'actions ${\displaystyle {\mathcal {A}}}$, et des récompenses dans ${\displaystyle \mathbb {R} }$. A chaque tour, le joueur reçoit un contexte ${\displaystyle x\in {\mathcal {X}}}$, effectue une action ${\displaystyle a\in {\mathcal {A}}}$ et reçoit une récompense ${\displaystyle 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 ${\displaystyle P(r|\theta ,a,x)}$;
2. un ensemble ${\displaystyle \Theta }$ de paramètres ${\displaystyle \theta }$ de la distribution de ${\displaystyle r}$;
3. une distribution à priori ${\displaystyle P(\theta )}$;
4. des observations ${\displaystyle {\mathcal {D}}=\{(x;a;r)\}}$;
5. une distribution a posteriori ${\displaystyle P(\theta |{\mathcal {D}})\propto P({\mathcal {D}}|\theta )P(\theta )}$, où${\displaystyle P({\mathcal {D}}|\theta )}$ est la fonction de vraisemblance.

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

${\displaystyle \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ù ${\displaystyle \mathbb {I} }$ est la fonction indicatrice.

En pratique, cette règle est implémenté par échantillonnage, à chaque tour, des paramètres ${\displaystyle \theta ^{\ast }}$ à partir de la distribution a posteriori ${\displaystyle P(\theta |{\mathcal {D}})}$, et en choisissant l'action ${\displaystyle a^{\ast }}$qui maximise ${\displaystyle \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[2].

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

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[9]. L'échantillonnage de Thompson sert de base à l'apprentissage accéléré dans la prise de décision décentralisée[10].