Multi-Armed Bandits und Thompson Sampling

Auf einen Blick

1. Ein Bandit-Algorithmus verteilt Versuche schon während des Lernens um: Vielversprechende Optionen bekommen mehr Verkehr, schwache weniger. Den Preis des Lernens misst der Regret.
2. Thompson Sampling wählt jede Option mit der Wahrscheinlichkeit, mit der sie nach aktuellem Wissen die beste ist – umgesetzt durch eine einzige Zufallsziehung aus jedem Posterior.
3. Bandits optimieren den Ertrag während des Experiments, klassische A/B-Tests die Qualität der Schlussfolgerung. Welche Methode passt, hängt vom Ziel ab.

Stellen Sie sich eine Reihe von Spielautomaten vor, sogenannten einarmigen Banditen. Jeder zahlt mit einer anderen, unbekannten Wahrscheinlichkeit aus. Sie haben eine begrenzte Zahl von Spielen. Welchen Automaten spielen Sie? Den, der bisher am besten lief – oder einen anderen, über den Sie noch wenig wissen? Dieses Bild hat dem Multi-Armed Bandit seinen Namen gegeben. Hinter der Metapher steckt eine der grundlegenden Fragen jedes lernenden Systems: das Verhältnis von Exploration und Exploitation.

Im Alltag von Produkten und Prozessen taucht das Problem ständig auf: Welche von fünf Überschriften zeigt man, welches Angebot, welche Reihenfolge von Empfehlungen? Jede Wahl liefert eine Beobachtung, und jede Beobachtung verbessert das Wissen für die nächste Wahl.

Das Problem in einer Formel

Es gibt $K$ Arme. Arm $i$ liefert bei jedem Zug eine zufällige Belohnung mit unbekanntem Mittelwert $\mu_i$; im einfachsten Fall ist die Belohnung 1 (Klick, Kauf) oder 0. In jeder Runde $t = 1, \dots, T$ wählt ein Algorithmus einen Arm und sieht nur dessen Ergebnis. Ziel ist, die Summe der Belohnungen zu maximieren.

Wie gut ein Algorithmus das schafft, misst der Regret: der Abstand zu einem Orakel, das den besten Arm mit Mittelwert $\mu^* = \max_i \mu_i$ von Anfang an kennt.

Dabei ist $N_i(T)$ die Zahl der Züge an Arm $i$ bis Runde $T$. Die rechte Seite zeigt, worum es geht: Jeder Zug an einem schlechteren Arm kostet dessen Abstand $\Delta_i$ zum besten. Ein Algorithmus mit gutem Regret spielt schlechte Arme selten – aber nicht so selten, dass er einen unterschätzten guten Arm übersieht.

Eine feste Gleichverteilung, wie im klassischen A/B-Test, gibt jedem Arm $T/K$ Züge. Ihr Regret wächst deshalb linear mit $T$: Die Lernkosten laufen weiter, solange das Experiment dauert.

Wie gut kann es überhaupt werden?

Tze Leung Lai und Herbert Robbins haben 1985 gezeigt, dass kein vernünftiger Algorithmus schneller als logarithmisch lernen kann (Lai & Robbins 1985). Für jeden schlechteren Arm $i$ gilt asymptotisch

mit der Kullback-Leibler-Divergenz, die für Ja/Nein-Belohnungen $\mathrm{KL}(p, q) = p \ln\frac{p}{q} + (1-p)\ln\frac{1-p}{1-q}$ lautet. Die Schranke sagt zweierlei: Der Regret wächst mindestens wie $\ln T$, und Arme, die dem besten sehr ähnlich sind, brauchen mehr Züge, um ausgeschlossen zu werden. Liegt der beste Arm bei 15 %, ist $\mathrm{KL}(0{,}12;\,0{,}15) \approx 0{,}0037$, aber $\mathrm{KL}(0{,}10;\,0{,}15) \approx 0{,}011$ – ein Arm mit 12 % braucht nach dieser Schranke etwa dreimal so viele Züge wie einer mit 10 %.

Drei Strategien

ε-greedy: meistens das Beste, manchmal Zufall

Die einfachste Strategie spielt mit Wahrscheinlichkeit $1 - \varepsilon$ den Arm mit der bisher höchsten beobachteten Rate und mit Wahrscheinlichkeit $\varepsilon$ einen zufälligen Arm (Sutton & Barto 2018). Epsilon-greedy ist leicht zu verstehen und zu implementieren. Zwei Schwächen hat es: Mit festem $\varepsilon$ exploriert es für immer im gleichen Umfang, der Regret wächst also linear. Und die Exploration ist blind – ein Arm, der offensichtlich schlecht ist, wird genauso oft ausprobiert wie ein vielversprechender, über den man wenig weiß.

UCB1: Optimismus bei Unsicherheit

UCB-Verfahren (Upper Confidence Bound) behandeln jeden Arm so, als wäre er so gut, wie es die Daten gerade noch plausibel erscheinen lassen. UCB1 spielt in jeder Runde den Arm mit dem größten Index

aus beobachteter Rate $\hat\mu_i$ und einem Bonus, der mit der Zahl $n_i$ der bisherigen Züge schrumpft. Selten gespielte Arme bekommen einen großen Bonus und werden deshalb überprüft. Auer, Cesa-Bianchi und Fischer haben gezeigt, dass der Regret von UCB1 für Belohnungen im Intervall $[0, 1]$ nach jeder Rundenzahl logarithmisch beschränkt bleibt (Auer et al. 2002). UCB1 ist deterministisch: Bei gleichen Daten trifft es immer dieselbe Wahl.

Thompson Sampling: mit der Wahrscheinlichkeit wählen, die Beste zu sein

William R. Thompson hat die Idee 1933 im Zusammenhang mit der Frage formuliert, welche von zwei Behandlungen besser ist (Thompson 1933). Sie ist bestechend einfach: Man wählt jeden Arm mit genau der Wahrscheinlichkeit, mit der er nach aktuellem Wissen der beste ist. Diese Wahrscheinlichkeit muss man nicht einmal ausrechnen – eine einzige Zufallsziehung aus jedem Posterior genügt.

Für Ja/Nein-Belohnungen verwendet man pro Arm eine Beta-Verteilung, genau wie im Bayes A/B-Test:

Für jeden Arm i:  α_i = 1,  β_i = 1            (flacher Prior)
Für jede Runde t = 1, …, T:
  1. Für jeden Arm i ziehe θ_i aus Beta(α_i, β_i)
  2. Spiele den Arm a mit dem größten θ_a
  3. Beobachte die Belohnung r ∈ {0, 1}
  4. α_a ← α_a + r,   β_a ← β_a + (1 − r)

Thompson Sampling wurde lange kaum beachtet. Anfang der 2010er-Jahre zeigten empirische Vergleiche, dass es in praktischen Aufgaben wie Anzeigen- und Nachrichtenauswahl mit etablierten Verfahren mithält oder sie übertrifft und robust mit verzögertem Feedback umgeht (Chapelle & Li 2011). Kurz darauf folgten die ersten Regret-Garantien für endliche Laufzeiten (Agrawal & Goyal 2012). Für Ja/Nein-Belohnungen erreicht Thompson Sampling die Schranke von Lai und Robbins sogar asymptotisch (Kaufmann et al. 2012); einen gut lesbaren Überblick über Theorie und Varianten gibt das Tutorial von Russo und Kollegen (Russo et al. 2018).

Thompson Sampling jenseits von Ja/Nein

Nicht jede Belohnung ist ein Klick. Für Umsätze oder Bearbeitungszeiten ersetzt man die Beta-Verteilung durch ein passendes Modell, etwa eine Normalverteilung für den Mittelwert jedes Arms. Das Prinzip bleibt gleich: aus jedem Posterior ziehen, den größten Wert spielen, den Posterior des gespielten Arms aktualisieren (Russo et al. 2018). Bei schiefen Größen wie Umsatz pro Besucher lohnt es sich, das Modell zu prüfen, statt blind eine Normalverteilung anzunehmen – wenige Großbestellungen können den geschätzten Mittelwert eines Arms sonst stark verschieben.

Auch der Prior verdient Aufmerksamkeit. Der flache Prior Beta(1, 1) ist ein neutraler Start. Weiß man aus Erfahrung, dass Klickraten meist zwischen 1 und 5 % liegen, beschleunigt ein schwach informativer Prior wie Beta(1, 30) – Mittelwert rund 3 %, 95-%-Intervall von unter 0,1 % bis knapp 12 % – das Lernen in den ersten Runden, ohne die Daten später zu überstimmen. Wie beim A/B-Test gilt: Alle Arme bekommen denselben Prior, damit keine Option bevorzugt startet.

Ein Schritt zum Nachrechnen

Drei Arme haben nach 90 Runden folgende Bilanz; alle starten mit dem flachen Prior Beta(1, 1). Wie entscheiden die drei Strategien über Runde 91?

Die Wahrscheinlichkeiten in der Thompson-Spalte sind $P(\text{Arm } i \text{ ist der beste} \mid \text{Daten}) = \int f_i(x) \prod_{j \ne i} F_j(x)\,\d x$, numerisch integriert und mit 400.000 simulierten Runden bestätigt. Die drei Strategien haben erkennbar verschiedene Charaktere:

• ε-greedy setzt fast alles auf B, weil B die höchste beobachtete Rate hat, und verteilt den Rest gleichmäßig.
• UCB1 wählt C, obwohl C die niedrigste beobachtete Rate hat: Nach nur zehn Zügen ist der Unsicherheitsbonus so groß, dass C der optimistischste Kandidat ist.
• Thompson Sampling gibt B die Hälfte der Wahrscheinlichkeit, C aber immerhin gut ein Drittel. Der Posterior von C ist breit: Mit rund 20 % Wahrscheinlichkeit liegt seine Rate über 25 %, bei A sind es knapp 2 %. Exploriert wird dort, wo sich das Lernen lohnt.

Interaktiv

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

Die Simulation benötigt JavaScript. Sie vergleicht Thompson Sampling, ε-greedy und UCB1 auf denselben drei Armen und zeigt den kumulierten Regret über die Zeit.

Bandit oder A/B-Test?

Beide Verfahren vergleichen Varianten, verfolgen aber verschiedene Ziele. Ein A/B-Test mit fester Aufteilung optimiert die Qualität der Schlussfolgerung: Am Ende steht eine möglichst genaue, gut dokumentierbare Schätzung des Effekts. Ein Bandit optimiert den Ertrag während der Laufzeit: Er nimmt eine weniger präzise Schätzung für schwächere Varianten in Kauf, um weniger Verkehr an sie zu verlieren.

Kontextuelle Bandits

Oft hängt die beste Option von der Situation ab: Eine Überschrift wirkt morgens anders als abends, auf dem Smartphone anders als am Desktop. Kontextuelle Bandits beobachten vor jeder Wahl einen Kontext – etwa Gerät, Tageszeit oder Interessen – und lernen, welcher Arm in welchem Kontext am besten ist. Ein bekanntes Beispiel ist LinUCB, mit dem Li und Kollegen die Auswahl von Nachrichtenartikeln personalisiert haben (Li et al. 2010). Auch Thompson Sampling lässt sich auf solche Modelle übertragen, etwa mit einer bayesschen Regression pro Arm (Russo et al. 2018).

Kontextuelle Bandits sind ein Zwischenschritt zum Reinforcement Learning. Beim Bandit verändert die Wahl nur die aktuelle Belohnung. Beim Reinforcement Learning verändert sie zusätzlich den Zustand der Welt und damit alle künftigen Möglichkeiten. Das umfassende Lehrbuch zu beiden Richtungen der Bandit-Theorie ist das Werk von Lattimore und Szepesvári (Lattimore & Szepesvári 2020).

Worauf man in der Praxis achten muss

• Verzögertes Feedback: Käufe treffen oft Stunden nach dem Klick ein. Aktualisiert man in Stapeln, ist Thompson Sampling durch seine Zufälligkeit robuster als deterministische Verfahren, die bis zum nächsten Update immer denselben Arm spielen (Chapelle & Li 2011).
• Veränderliche Umgebungen: Raten schwanken mit Saison, Wetter oder Kampagnen. Ein Bandit, der alte Daten nie vergisst, reagiert zu träge. Abhilfe schaffen gleitende Fenster oder das Abwerten älterer Beobachtungen.
• Auswertung nach adaptiver Zuteilung: Weil gute Arme mehr Daten bekommen, sind naive Schätzungen der Effekte verzerrt und klassische Konfidenzintervalle nicht mehr gültig. Wer am Ende einen belastbaren Effekt berichten will, plant eine unverzerrte Vergleichsgruppe ein.
• Die richtige Belohnung: Ein Bandit optimiert genau das, was man ihm als Belohnung gibt. Klicks sind leicht zu messen, sagen aber wenig über langfristigen Wert. Eine schlecht gewählte Belohnung wird zuverlässig maximiert – mit allen Nebenwirkungen.
• Leitplanken: Mindestanteile pro Arm, Obergrenzen für Exploration und eine menschliche Freigabe für neue Arme verhindern, dass ein Algorithmus Kundschaft mit ungeprüften Varianten überrascht.

Fazit

Multi-Armed Bandits machen den Konflikt zwischen Lernen und Nutzen rechenbar. Der Regret beziffert, was Lernen kostet, und die Schranke von Lai und Robbins zeigt, wie schnell es bestenfalls gehen kann. ε-greedy ist einfach, verschenkt aber durch blinde Exploration Ertrag. UCB1 exploriert gezielt mit einem Optimismusbonus. Thompson Sampling wählt jede Option mit der Wahrscheinlichkeit, die Beste zu sein – eine Idee aus dem Jahr 1933, die heute zu den stärksten und zugleich einfachsten Verfahren zählt. Welche Strategie passt, hängt davon ab, ob man möglichst gut entscheiden oder möglichst sicher belegen will.

Häufige Fragen

Was ist ein Multi-Armed Bandit?

Ein Entscheidungsproblem, bei dem man wiederholt eine von mehreren Optionen („Armen“) wählt, deren Erfolgsraten unbekannt sind, und nach jeder Wahl eine Belohnung beobachtet. Ziel ist, über alle Runden möglichst viel Belohnung zu sammeln – man muss also gleichzeitig lernen und nutzen.

Wie funktioniert Thompson Sampling?

Für jeden Arm führt man eine Posterior-Verteilung seiner Erfolgsrate, bei Ja/Nein-Belohnungen eine Beta-Verteilung. In jeder Runde zieht man aus jedem Posterior einen Zufallswert und spielt den Arm mit dem größten Wert. Danach wird der Posterior des gespielten Arms mit dem Ergebnis aktualisiert.

Wann ist ein Bandit besser als ein A/B-Test?

Wenn es vor allem darauf ankommt, während der Laufzeit wenig Ertrag zu verschenken: bei vielen kurzlebigen Varianten wie Überschriften oder Angeboten, bei hohen Kosten schlechter Varianten oder bei laufender Optimierung. Soll dagegen ein Effekt sauber geschätzt und dokumentiert werden, ist ein A/B-Test mit fester Aufteilung meist die bessere Wahl.

Was bedeutet Regret?

Regret ist die Differenz zwischen der Belohnung, die man mit der von Anfang an bekannten besten Option erzielt hätte, und der tatsächlich erzielten erwarteten Belohnung. Er misst also, was das Lernen kostet. Gute Bandit-Algorithmen lassen den Regret nur logarithmisch mit der Zahl der Runden wachsen.

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. PaperLai, T. L. und Robbins, H. (1985): Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics 6(1), 4–22.
3. PaperAuer, P., Cesa-Bianchi, N. und Fischer, P. (2002): Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning 47, 235–256.
4. PaperChapelle, O. und Li, L. (2011): An Empirical Evaluation of Thompson Sampling. Advances in Neural Information Processing Systems 24 (NIPS 2011).
5. PaperAgrawal, S. und Goyal, N. (2012): Analysis of Thompson Sampling for the Multi-armed Bandit Problem. Proceedings of the 25th Annual Conference on Learning Theory (COLT).
6. PaperKaufmann, E., Korda, N. und Munos, R. (2012): Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis. Algorithmic Learning Theory (ALT 2012), Springer.
7. PaperRusso, D. J., Van Roy, B., Kazerouni, A., Osband, I. und Wen, Z. (2018): A Tutorial on Thompson Sampling. Foundations and Trends in Machine Learning 11(1), 1–96.Gut lesbare Einführung mit vielen Beispielen und Hinweisen zur Theorie.
8. PaperLi, L., Chu, W., Langford, J. und Schapire, R. E. (2010): A Contextual-Bandit Approach to Personalized News Article Recommendation. Proceedings of the 19th International Conference on World Wide Web (WWW).
9. BuchLattimore, T. und Szepesvári, C. (2020): Bandit Algorithms. Cambridge University Press.Das umfassende Lehrbuch zur Theorie; die Autoren stellen eine frei lesbare Fassung online bereit.
10. BuchSutton, R. S. und Barto, A. G. (2018): Reinforcement Learning: An Introduction (2. Auflage). MIT Press.Kapitel 2 behandelt Bandits als einfachsten Fall des Reinforcement Learning.

Zuletzt fachlich geprüft am 25. September 2026. Hinweise auf Fehler nehmen wir gern entgegen: impressum@nyxai.com.

Weiterlesen

Bayes & Statistik

Bayes A/B-Test

Wie wahrscheinlich ist B besser – und was kostet ein Irrtum? Beta-Posteriors, erwarteter Verlust, Uplift-Intervall und ehrliche Regeln fürs Stoppen.

10 Min. Lesezeit· mit interaktivem Explainer

Lernen aus Feedback

Reinforcement Learning einfach erklärt

Wie ein Agent durch Handeln und Rückmeldung lernt: Belohnungen, Markov-Entscheidungsprozesse, Bellman-Gleichung, Value Iteration und Q-Learning – mit Rechenbeispiel.

9 Min. Lesezeit· mit interaktivem Explainer

Bayes & Statistik

Bayessche Statistik einfach erklärt

Satz von Bayes, Prior, Likelihood und Posterior – mit dem klassischen Testbeispiel, der Beta-Binomial-Rechnung und einem ehrlichen Vergleich mit frequentistischen Verfahren.

9 Min. Lesezeit· mit interaktivem Explainer