É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ée 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].