Multi-Armed Bandit

Das fundamentale Lern-Dilemma der KI: Erkunden oder Ausnutzen? — der einfachste Reinforcement-Learning-Algorithmus, am Casino erklärt

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).

Analogie:

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.

AlphaGo & AlphaZero (Spielagenten)Wenn AlphaGo entscheidet, welchen nächsten Zug es im Spielbaum erkunden soll, benutzt es im Kern eine Variante von UCB (Upper Confidence Bound — die zweite Strategie in dieser Demo). Der Algorithmus, den du gleich an Slot-Maschinen ausprobierst, ist also derselbe Baustein, der den weltbesten Go-Spieler geschlagen hat.

ChatGPT & moderne SprachmodelleWenn ein LLM via RLHF (Reinforcement Learning from Human Feedback) trainiert wird, muss das System lernen, welche Antwort-Varianten Menschen bevorzugen. Auch hier: Erkunden (neue Formulierungen testen) oder Ausnutzen (bei der bewährten Formulierung bleiben). Das Bandit-Dilemma in Reinform.

Netflix, Spotify, Online-WerbungWelches Cover bekommst du angezeigt? Welcher Song wird als nächstes empfohlen? Welche Anzeige wird ausgespielt? Thompson-Sampling (die dritte Strategie hier) läuft genau jetzt produktiv in Empfehlungssystemen großer Plattformen — A/B-Tests sind im Grunde ein Bandit-Problem in Echtzeit.

Robotik & autonomes FahrenEin Roboter, der greifen lernt, muss bei jedem Versuch entscheiden: "die Bewegung wiederholen, die bisher am besten geklappt hat" oder "eine leicht andere ausprobieren, weil sie vielleicht noch besser ist". Selbe Frage wie an deinen Slot-Maschinen — nur mit deutlich mehr Hebeln.

💡 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ängerMit 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 OptimumWä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ösungHalte 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ß.

Szenarien:

👉 Drück Start, um die Strategie laufen zu lassen — oder klick Alle vergleichen, um die vier Algorithmen nebeneinander zu sehen.

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.

Balken = SchätzungGlocke = Thompson-Verteilung

Regret-Kurve

kumulierter Verlust gegenüber der idealen Strategie

Aktuell: 0.0/ 0 Pulls

Strategie

ε (Erkundungs-Rate): 0.10

0 = nur Ausnutzen, 1 = nur Würfeln. Klassisch: 0.05–0.20.

Geschwindigkeit: 5×

Anzahl Maschinen: 5

🔒 Es gibt versteckte Werte — willst du sie sehen?

Verstecktes enthüllen

Bandit #1–5

Klassische Banditen-Notation: #1, #2, … #5

Erweiterte Modi

Budget-Modus aus

Begrenzt auf 100 Pulls. Danach Auto-Pause + Score-Karte.

Welt stabil

Wahre Werte ändern sich alle 25 Pulls leicht — UCB1 mit fixem c bekommt Probleme.

Live-Statistik

Pulls insgesamt0

Reward insgesamt0

Meistgespielt#1 (0×)

% Treffer auf beste MaschineAktiviere "Verstecktes enthüllen", um zu sehen, welche Maschine wirklich die beste ist.

Theorie

Pseudocode

Schritt für Schritt

Flussdiagramm

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.

Deutsch

                      
                        
                          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]

1 / 6

⚙️ 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]

Was misst der "Regret" in dieser Demo?

Wie schnell ein Algorithmus konvergiert — niedriger = schneller.

Wie viel Belohnung du im Vergleich zur idealen Strategie verloren hast, kumuliert über alle Züge.

Die Anzahl der Züge auf die schlechteste Maschine.

Wie oft der Algorithmus seine Entscheidung "bereut" und sie ändert.

1. Was misst der "Regret" in dieser Demo?

☐ A) Wie schnell ein Algorithmus konvergiert — niedriger = schneller.
☐ B) Wie viel Belohnung du im Vergleich zur idealen Strategie verloren hast, kumuliert über alle Züge.
☐ C) Die Anzahl der Züge auf die schlechteste Maschine.
☐ D) Wie oft der Algorithmus seine Entscheidung "bereut" und sie ändert.

2. Warum gewinnt UCB1 langfristig gegen ε-greedy mit konstantem ε?

☐ A) UCB1 hat Zugriff auf die wahren Wahrscheinlichkeiten, ε-greedy nicht.
☐ B) UCB1 ist schneller berechenbar — pro Zug weniger Rechenzeit.
☐ C) UCB1 reduziert die Erkundung automatisch, wenn die Schätzungen sicher werden — ε-greedy explored mit fixem ε auch dann noch zufällig, wenn klar ist, welche Maschine die beste ist.
☐ D) UCB1 funktioniert nur mit Bernoulli-Belohnungen, ε-greedy bricht da zusammen.

3. Was repräsentiert die Beta-Verteilung im Thompson-Sampling?

☐ A) Eine vorab definierte Lookup-Tabelle mit den optimalen Aktionen pro Zustand.
☐ B) Die Wahrscheinlichkeits-Verteilung über mögliche "wahre Werte" einer Maschine, gegeben die bisherigen Beobachtungen.
☐ C) Die durchschnittliche Belohnung pro Maschine, geglättet mit einem Moving Average.
☐ D) Eine Lernrate, die mit jedem Pull abnimmt.

4. Wo begegnet uns das Multi-Armed-Bandit-Problem im echten Leben?

☐ A) Ausschließlich in Casinos und beim Glücksspiel — daher der Name.
☐ B) Nur in akademischen Reinforcement-Learning-Papern, aber kaum in der Praxis.
☐ C) Bei A/B-Tests, Online-Werbung, Empfehlungssystemen, klinischen Studien und überall, wo man unter Unsicherheit aus mehreren Optionen wählt.
☐ D) Nur bei Spielen mit endlichem Zustandsraum wie Schach oder Go.

Auflösung: 1) B · 2) C · 3) B · 4) C

Was wäre, wenn die Maschinen sich je nach Zustand ändern?

Genau dann wird aus dem Bandit-Problem ein Q-Learning-Problem: Aktionen haben Folgen, der Zustand wechselt, und der Agent muss eine Politik für jede Situation lernen.

Multi-Armed Bandit

Was ist ein Multi-Armed Bandit?

Analogie:

Definition:

Was hat das mit Künstlicher Intelligenz zu tun?

Drei Strategien für das Erkundungs-Dilemma

Casino-Sandbox

Was dieses Schaubild zeigt

Regret-Kurve