Multi-Armed Bandit
Das fundamentale Lern-Dilemma der KI: Erkunden oder Ausnutzen? — der einfachste Reinforcement-Learning-Algorithmus, am Casino erklärt
Regret-Kurve Regret = wie viel Belohnung du im Vergleich zur perfekten Wahl verloren hast. Flach = clever, linear = naiv.
Was dieses Schaubild zeigt
Mehrere Spielautomaten stehen nebeneinander, jeder mit einer unbekannten Gewinnchance. Zug um Zug tastet sich das Verfahren an den besten heran — und du siehst live, wie sich seine Wahl formt.
- Was du siehst
- Eine Reihe von Automaten nebeneinander. Im Fenster jedes Automaten steht das letzte Ergebnis, darunter reihen sich die letzten Züge als Punkte (● Gewinn, ○ Niete). Darunter ein Schacht: Seine Füllung ist die geschätzte Chance, ein Leuchten zeigt, wie unsicher sie noch ist.
- Was passiert
- Bei jedem Zug leuchtet genau ein Automat kurz auf — der gerade gespielte. Sein Fenster zeigt Gewinn oder Niete, die Füllung rückt auf die neue Schätzung, und je öfter er dran war, desto schwächer leuchtet die Unsicherheit. Mit der Zeit fällt die Wahl immer öfter auf denselben, starken Automaten.
- Was du tun kannst
- Oben eine Strategie wählen, dann Start oder Schritt drücken und zusehen. Im Manuell-Modus tippst du selbst einen Automaten an. Über die Regler änderst du Tempo und Anzahl der Automaten oder deckst die versteckten Chancen auf.
- Worauf du achtest
- Das Ringen zwischen Erkunden und Ausnutzen: Das Verfahren muss genug Neues probieren, um den besten Automaten überhaupt zu finden — darf aber nicht zu lange an einem schwachen kleben bleiben.
Definition
Was ist ein Multi-Armed Bandit?
Analogie
Du stehst in einem Casino mit fünf Slot-Maschinen. Jede zahlt unterschiedlich oft — du weißt aber nicht welche wie. Spielst du immer die, die gerade am besten aussieht? Oder testest du auch die anderen, weil eine vielleicht doch häufiger zahlt?
Genau dieses Dilemma haben Algorithmen ständig: Welche Anzeige bringt mehr Klicks? Welche Behandlung wirkt besser? Welche Empfehlung wird gekauft? Jede Entscheidung ist ein Trade-off zwischen Ausnutzen (was scheinbar funktioniert) und Erkunden (was vielleicht noch besser ist).
Definition
Formal ist das K-armed-Bandit-Problem: Es gibt K Aktionen mit unbekannten Belohnungs-Verteilungen. Ziel ist, nach n Zügen den kumulativen Reward zu maximieren — äquivalent: den Regret zu minimieren.
Regret(n) = n · μ* − Σᵢ μ_aᵢ — die Differenz zwischen dem theoretischen Optimum (n·μ*) und dem, was du tatsächlich eingesammelt hast. Ein guter Algorithmus erreicht sublinearen Regret (z.B. O(log n)) — er macht zwar weiter Fehler, aber pro Zug immer seltener.
Auf den ersten Blick wirkt das Casino-Beispiel wie ein Glücksspiel-Problem — aber es ist tatsächlich der einfachste Lernalgorithmus der modernen KI. Das Multi-Armed-Bandit-Problem ist die Einstiegs-Aufgabe einer Disziplin namens Reinforcement Learning (kurz RL, deutsch: "bestärkendes Lernen") — derselben Disziplin, mit der DeepMind sein AlphaGo trainiert hat und mit der OpenAI ChatGPT auf menschliche Antworten ausgerichtet hat.
Maschinelles Lernen (Machine Learning) kennt drei Hauptparadigmen: Überwachtes Lernen (Beispiele mit Lösungen — "das ist eine Katze"), Unüberwachtes Lernen (Muster in Daten finden — "diese Bilder gehören irgendwie zusammen") und Reinforcement Learning (durch Belohnung und Bestrafung lernen — "diese Aktion hat funktioniert, mach das wieder"). Der Bandit hier ist die denkbar einfachste RL-Aufgabe: keine Zustände, keine Folgewirkungen — nur Aktionen wählen und Belohnung kassieren. Genau deshalb ist sie der perfekte Einstieg.
💡 Merksatz: Wann immer ein KI-System unter Unsicherheit zwischen Optionen wählen muss — und dabei selbst lernen soll, welche Option die beste ist — steckt im Kern ein Multi-Armed-Bandit-Problem (oder eine Erweiterung davon). Was du gleich an Slot-Maschinen siehst, ist kein Casino-Spielzeug. Es ist ein Grundbaustein der heutigen KI.
Es gibt nicht die eine richtige Antwort. Aber es gibt drei klassische Strategien, die sich didaktisch wunderbar voneinander absetzen — von "naiv mit Würfel" bis "mathematisch optimal".
- ε-greedy — der ehrliche Anfänger Mit Wahrscheinlichkeit (1−ε) spiele die aktuell beste Maschine. Mit Wahrscheinlichkeit ε probiere irgendeine zufällige aus. Einfach, schnell — aber: ε bleibt konstant, du verschwendest auch nach 10 000 Zügen noch ε-Prozent deiner Münzen rein zufällig.
- UCB1 — das selbst-korrigierende Optimum Wähle die Maschine mit dem höchsten <em>Upper Confidence Bound</em>: Schätzwert plus Unsicherheits-Bonus. Wenig getestete Maschinen kriegen einen großen Bonus und werden zwangsläufig irgendwann ausprobiert. Beweisbar logarithmischer Regret — perfekt aus der Theorie.
- Thompson-Sampling — die elegante Bayes-Lösung Halte pro Maschine eine Beta-Verteilung (siehe Sparkline im Demo). Pro Zug ziehst du aus jeder Verteilung ein Sample und spielst die Maschine mit dem höchsten Sample. Probabilistisch — exploriert automatisch, wenn die Schätzungen unsicher sind, und exploitiert, wenn sie scharf werden.
Die zentrale Beobachtung: ε-greedy bleibt linear in der Regret-Kurve, weil das konstante ε nie aufhört zu würfeln. UCB1 und Thompson flachen logarithmisch ab, weil sie mit wachsender Sicherheit aufhören zu explorieren. Drück "Alle vergleichen" — du siehst es in 500 Pulls schwarz auf weiß.
Das Dilemma: Erkunden oder Ausnutzen?
Im Multi-Armed-Bandit-Problem stehen K Aktionen mit unbekannten Belohnungs-Verteilungen zur Auswahl. In jedem Schritt entscheidet ein Algorithmus, welchen Arm er zieht — bekommt eine Belohnung — und muss daraus lernen. Das Ziel: nach n Schritten den kumulativen Reward maximieren, äquivalent dazu den Regret minimieren.
Regret(n) = n · μ* − E[Σᵢ μ_aᵢ] — die Differenz zwischen dem theoretischen Optimum (alle Züge auf den besten Arm) und dem, was der Algorithmus tatsächlich einsammelt.
Drei klassische Strategien
- ε-greedy: Mit Wahrscheinlichkeit (1−ε) den aktuell besten Arm spielen, mit ε zufällig erkunden. Einfach — aber linearer Regret durch konstantes Würfeln.
- UCB1: Den Arm mit dem höchsten Upper Confidence Bound wählen: Schätzwert + c·√(ln t / Nᵢ). Beweisbar O(log n) Regret.
- Thompson-Sampling: Pro Arm eine Beta(α, β)-Verteilung führen. Aus jeder ein Sample ziehen, den Arm mit höchstem Sample spielen. Bayes'sch elegant.
Vergleich auf einen Blick
Vier Algorithmen, drei Achsen: Auswahl-Regel · Regret-Schranke · Verteilungs-Annahme.
- ε-greedy — Auswahl: mit ε zufällig, sonst argmax μ̂ᵢ. Regret: linear O(n·ε). Annahme: keine — verteilungs-agnostisch.
- ε-decay — Auswahl: wie ε-greedy, aber ε(t) = max(0.02, 1/√t). Regret: sublinear O(√n). Annahme: stationäre Welt.
- UCB1 — Auswahl: argmaxᵢ (μ̂ᵢ + c·√(ln t / Nᵢ)). Regret: optimal O(log n). Annahme: beschränkte Belohnung [0,1].
- Thompson — Auswahl: argmaxᵢ Beta(αᵢ, βᵢ).sample(). Regret: optimal O(log n). Annahme: Bernoulli-Belohnung (allg. konjugierte Familie).
Warum konvergieren UCB1 und Thompson?
Bei UCB1 schrumpft der Unsicherheits-Bonus c·√(ln t / Nᵢ) mit zunehmenden Pulls — er exploriert immer seltener, je sicherer die Schätzungen werden. Bei Thompson werden die Beta-Verteilungen mit jedem Pull schmaler — die Samples konzentrieren sich um den wahren Wert, und der Algorithmus exploitiert automatisch.
ε-greedy hat dieses Selbst-Reduktions-Verhalten nicht. Mit konstantem ε exploriert es für immer mit Wahrscheinlichkeit ε — daher der lineare Regret-Anteil, den es nie loswird. Lösung in der Praxis: ε über die Zeit absenken (decaying ε-greedy).
Wo trifft man Bandits in der Praxis?
- A/B-Testing: Adaptive Tests, die schlechte Varianten früh aussortieren
- Empfehlungssysteme: Netflix, Spotify — neue Inhalte explorieren ohne den User zu nerven
- Online-Werbung: Welche Anzeige bringt mehr Klicks bei begrenztem Budget?
- Klinische Studien: Multi-Arm-Bandit-Trials weisen mehr Patienten der bisher besten Behandlung zu
- News-Feed-Ranking: Welcher Artikel wird wie oft angezeigt?
Spiele in der Demo! Drücke "Alle vergleichen" — du siehst in 500 Pulls, wie ε-greedy linear bleibt, während UCB1 und Thompson logarithmisch abflachen.
1
# Multi-Armed Bandit — generischer Strategie-Loop
2
funktion spiele(strategie, K, N):
3
# 1. K Banditen mit Bayes-Prior init (α=β=1)
4
banditen = [{pulls:0, rewards:0, α:1, β:1} für _ in 1..K]
5
6
für t in 1..N:
7
8
# 2. Arm auswählen — je nach Strategie
9
wenn strategie == „ε-greedy":
10
wenn rand() < ε: arm = zufälliger arm
11
sonst: arm = argmax(rewardsᵢ / pullsᵢ)
12
13
sonst wenn strategie == „UCB1":
14
arm = argmaxᵢ( meanᵢ + c · √(ln t / Nᵢ) )
15
16
sonst wenn strategie == „Thompson":
17
samples = [Beta(αᵢ, βᵢ).sample() für i in 1..K]
18
arm = argmax(samples)
19
20
# 3. Arm ziehen + Statistiken updaten
21
reward = Bernoulli(wahre_mittelwerte[arm]).sample()
22
banditen[arm].update(reward) # α += 1 wenn reward sonst β += 1
23
24
# 4. Regret gegen das theoretische Optimum tracken
25
regret += max(wahre_mittelwerte) − wahre_mittelwerte[arm]
⚙️ Initialisierung
Für jeden der K Banditen wird eine Beta(α=1, β=1)-Verteilung angelegt (Uniform-Prior — alles möglich), dazu Pull-Counter und Reward-Counter. Die wahren Gewinn-Wahrscheinlichkeiten kennt der Algorithmus nicht.
# 1. K Banditen mit Bayes-Prior init (α=β=1)
banditen = [{pulls:0, rewards:0, α:1, β:1} für _ in 1..K]
⚙️ Init
K Banditen mit Beta(1,1) initialisieren.
🎛 Arm wählen
Strategie-Dispatch: ε-greedy, UCB1 oder Thompson.
🎯 Pull
Arm ziehen, Bernoulli-Belohnung erhalten.
🔄 Update
Pulls, Rewards, α/β für Arm aktualisieren.
🚩 Regret
Verlust gegenüber Optimum kumulieren.
Prüfen
Teste dein Verständnis
Was misst der "Regret" in dieser Demo?
Wähle eine Antwort
1. Was misst der "Regret" in dieser Demo?
2. Warum gewinnt UCB1 langfristig gegen ε-greedy mit konstantem ε?
3. Was repräsentiert die Beta-Verteilung im Thompson-Sampling?
4. Wo begegnet uns das Multi-Armed-Bandit-Problem im echten Leben?