Multi-Armed Bandit

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

🎰 Mission: Vor dir stehen Slot-Maschinen. Jede hat eine versteckte Gewinn-Chance. Finde mit möglichst wenig Zügen heraus, welche die beste ist — ohne zu viele Münzen an die schlechten zu verschwenden.
Interaktiver Canvas. Mit Pfeiltasten navigierst du zwischen den Maschinen, mit Enter oder Leertaste spielst du die fokussierte Maschine im Manuell-Modus. Mit Zifferntasten 1 bis 9 spielst du direkt. Mit R wechselst du den Reveal-Modus.
Klick auf eine Maschine
Balken = SchätzungLeuchten = Unsicherheit● Gewinn · ○ Niete

Regret-Kurve Regret = wie viel Belohnung du im Vergleich zur perfekten Wahl verloren hast. Flach = clever, linear = naiv.

kumulierter Verlust gegenüber der idealen Strategie
Aktuell: 0.0 / 0 Pulls
Szenarien:
👉 Drück Start, um die Strategie laufen zu lassen — oder klick Alle vergleichen, um die vier Algorithmen nebeneinander zu sehen.
Steuerung
StrategieBestimmt, wie der Automat die nächste Maschine wählt. "Manuell" überlässt dir die Wahl, die anderen erkunden und nutzen automatisch.
Pulls insgesamt0Reward insgesamt0Meistgespielt#1 (0×)% Treffer auf beste MaschineAktiviere "Verstecktes enthüllen", um zu sehen, welche Maschine wirklich die beste ist.
Ablauf
Parameter
Anteil rein zufälliger Züge. Höheres ε erkundet mehr, verschenkt aber auch mehr Münzen an schlechte Maschinen.
0 = nur Ausnutzen, 1 = nur Würfeln. Klassisch: 0.05–0.20.
Versteckte Werte
🔒 Es gibt versteckte Werte — willst du sie sehen?
Verstecktes enthüllen
Anzeige
Bandit #1–5
Klassische Banditen-Notation: #1, #2, … #5
Erweiterte Modi
Budget-Modus ausBegrenzt auf 100 Pulls. Danach Auto-Pause + Score-Karte.
Welt stabilWahre Werte ändern sich alle 25 Pulls leicht — wer nicht mehr erkundet, merkt es nicht.

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

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 Sprachmodelle Wenn 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-Werbung Welches 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 Fahren Ein 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".

  1. ε-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.
  2. 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.
  3. 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ß.

TheoriePseudocodeSchritt für SchrittFlussdiagramm

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.

Prüfen

Teste dein Verständnis

Was misst der "Regret" in dieser Demo?

Wähle eine Antwort

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.

Einfache Sprache

Diese Vorschau ist in Einfacher Sprache. Das ganze Portal gibt es auch in Einfacher Sprache. Du kannst oben die Sprache wechseln. Oder nutze den Knopf unten. Unsere Texte in Einfacher Sprache entstehen KI-gestützt und werden redaktionell begleitet. Sie orientieren sich an den Grundprinzipien der Leichten Sprache, sind aber keine geprüfte Leichte Sprache: Eine Prüfgruppe von Menschen mit Lernschwierigkeiten prüft sie nicht.

Vorschau: Demo: Spiel-Automat mit Köpfchen

Was zeigt die Demo?

Diese Demo zeigt Spiel-Automaten. Es gibt 5 Automaten zur Auswahl. Jeder Automat zahlt anders gut. Aber: Du weißt nicht welcher der beste ist. Du musst es heraus-finden. Mit wenig Versuchen.

Wie du die Demo benutzt

Du kannst selbst spielen. Klicke einen Automaten an. Du gewinnst oder verlierst. Oder du wählst eine Strategie aus. Die Strategie spielt für dich. Du siehst wie schnell sie lernt.

Das große Problem

Sollst du den besten Automaten spielen? Oder einen neuen probieren? Das heißt: Exploration oder Exploitation. Exploration heißt: Neues entdecken. Exploitation heißt: Bekanntes nutzen. Beides ist wichtig.

Was du lernst

Du lernst: KIs müssen oft entscheiden. Sicher sein oder neugierig sein? Dieses Problem gibt es überall. Bei Empfehlungen im Internet. Bei Werbung. Und beim Lernen.