Bandit-Simulation: Thompson Sampling im Vergleich

Interaktiv

Bandit-Simulation: Thompson Sampling, ε-greedy und UCB im Vergleich

Dieser Explainer benötigt JavaScript. Er simuliert drei Arme mit verborgenen Erfolgsraten und vergleicht Thompson Sampling, ε-greedy und UCB1 anhand ihres kumulierten Regrets.

So funktioniert der Explainer

Jeder der drei Arme liefert bei einem Zug mit seiner verborgenen Rate $\mu_k$ einen Erfolg. Eine Strategie soll in $T$ Zügen möglichst viele Erfolge sammeln, muss dafür aber erst herausfinden, welcher Arm der beste ist. Der Regret misst, was das Lernen kostet:

Drei Strategien treten gegeneinander an:

• Thompson Sampling (Thompson 1933) führt für jeden Arm einen Posterior $\Beta(1 + s_k,\, 1 + f_k)$ mit $s_k$ Erfolgen und $f_k$ Misserfolgen. In jedem Schritt zieht es aus jedem Posterior einen Wert und spielt den Arm mit dem größten Wert.
• ε-greedy spielt jeden Arm einmal, danach mit Wahrscheinlichkeit $\varepsilon$ einen zufälligen Arm und sonst den Arm mit der besten bisherigen Quote.
• UCB1 (Auer et al. 2002) spielt jeden Arm einmal und danach den Arm mit dem größten Wert von $\hat\mu_k + \sqrt{2 \ln t / n_k}$ – optimistisch gegenüber wenig erprobten Armen.

Der Tab „Live“ zeigt einen einzelnen Lauf von Thompson Sampling Schritt für Schritt. Der Tab „Vergleich“ wiederholt das Experiment für alle drei Strategien 100- bis 500-mal mit reproduzierbarem Zufall und zeigt den mittleren Regret.

Drei Dinge zum Ausprobieren

1. Live zuschauen. Starten Sie den Live-Lauf langsam: Anfangs streuen die Ziehungen breit, und alle Arme kommen dran. Nach einigen Hundert Zügen ist der Posterior des besten Arms schmal, und die anderen werden nur noch selten gespielt.
2. Knappe Unterschiede. Wechseln Sie auf „Knapp“. Alle Strategien brauchen länger; der Regret wächst, weil sich 12 % und 15 % nur mit vielen Beobachtungen unterscheiden lassen.
3. ε verändern. Mit großem $\varepsilon$ erkundet ε-greedy dauerhaft und sammelt linear wachsenden Regret; mit sehr kleinem $\varepsilon$ bleibt es manchmal lange am falschen Arm hängen – erkennbar an der großen Streuung zwischen den Läufen.

Hintergründe, Formeln und die Grenzen von Bandits im Vergleich zu A/B-Tests erklärt der Artikel Multi-Armed Bandits und Thompson Sampling.

Quellen und weiterführende Literatur

1. PaperThompson, W. R. (1933): On the Likelihood that One Unknown Probability Exceeds Another in View of the Evidence of Two Samples. Biometrika 25(3/4), 285–294.
2. PaperAuer, P., Cesa-Bianchi, N. und Fischer, P. (2002): Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning 47, 235–256.