Das Multi-Armed-Bandit-Problem ist eines der klassischen Modelle der Entscheidungstheorie: Ein Spieler steht vor mehreren einarmigen Banditen (Spielautomaten, „Arme"), deren Gewinnwahrscheinlichkeiten unbekannt sind. Er muss entscheiden, welche Arme er wie oft zieht, um über viele Runden die Gesamtbelohnung zu maximieren. Dabei gilt es, Exploration und Exploitation auszubalancieren.
Die Grundidee
Jeder Arm liefert bei jedem Zug eine Belohnung aus einer festen, aber unbekannten Wahrscheinlichkeitsverteilung. Der Spieler lernt die Arme nur durch Ausprobieren kennen. Zieht er immer nur den bisher besten Arm, weiß er nicht, ob ein anderer Arm nicht doch besser wäre. Das Problem ist die einfachste Form sequenzieller Entscheidungsfindung und ein Sonderfall eines Markov-Entscheidungsprozesses ohne Zustandsübergänge.
Als Qualitätsmaß dient der Regret: die Differenz zwischen der Belohnung der optimalen Strategie und der tatsächlich erzielten Belohnung. Gute Bandit-Algorithmen halten den Regret möglichst klein.
Bekannte Lösungsverfahren
- Epsilon-Greedy: mit Wahrscheinlichkeit ε zufällig ziehen, sonst den aktuell besten Arm.
- UCB1 (Upper Confidence Bound): wählt den Arm mit der besten oberen Konfidenzgrenze — je unsicherer ein Arm ist, desto attraktiver wird er.
- Thompson Sampling: bayesianisches Verfahren (Idee von William R. Thompson, 1933), zieht aus Posterior-Verteilungen und gilt in der Praxis oft als sehr effektiv.
- Exp3: für gegnerische (adversariale) Umgebungen geeignet.
Anwendungen
Bandit-Modelle stecken in A/B-Tests, Online-Werbung und Empfehlungssystemen (dort oft als kontextuelle Banditen mit Zusatzmerkmalen), in der klinischen Forschung bei der Zuteilung von Behandlungen sowie bei dynamischer Preisgestaltung. In der Werbeausspielung entscheidet der Algorithmus etwa, welche Anzeige einem Nutzer gezeigt wird, um Klickraten zu maximieren.
Verwandte Grundlagen: Exploration vs. Exploitation, Epsilon-Greedy, Reinforcement Learning, Markov-Entscheidungsprozess.