🤖 machine learning

A Broader View of Thompson Sampling

Dieses Papier erläutert den Mechanismus hinter dem Erfolg von Thompson Sampling, indem es es als einen Online-Optimierungsalgorithmus neu fasst, der eine stationäre Bellman-optimale Politik nachahmt, wobei die Gier durch verbleibende Unsicherheit regularisiert wird, und bietet dadurch einen neuen Rahmen für das Verständnis ihrer Dynamik und zur Verbesserung von Politiken.

Ursprüngliche Autoren: Yanlin Qu, Hongseok Namkoong, Assaf Zeevi

Veröffentlicht 2026-05-28

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Yanlin Qu, Hongseok Namkoong, Assaf Zeevi

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Die „Mystery" eines berühmten Algorithmus lösen

Stellen Sie sich vor, Sie sind ein Koch, der das beste Rezept für ein neues Gericht sucht. Sie haben zwei Zutaten (nennen wir sie Arm 1 und Arm 2), wissen aber nicht, welche besser schmeckt. Sie müssen weiterkochen, um zu lernen, wollen aber gleichzeitig Ihren Kunden jetzt das beste Gericht servieren. Dies ist das klassische Problem des „Multi-Armed Bandit": die Balance zwischen Exploration (neue Dinge ausprobieren, um zu lernen) und Exploitation (das nutzen, von dem man weiß, dass es am besten funktioniert).

Seit Jahrzehnten ist eine bestimmte Methode namens Thompson Sampling der Goldstandard. Sie ist berühmt, weil sie in der Praxis unglaublich gut funktioniert. Im Gegensatz zu anderen Methoden, bei denen die Regeln klar sind (wie „wähle immer die Option mit dem höchsten Konfidenzwert"), fühlte sich Thompson Sampling ein wenig wie Magie an. Es funktioniert, aber niemand konnte wirklich erklären, warum es Lernen und Verdienen so perfekt ausbalanciert.

Dieses Papier lüftet das Geheimnis. Die Autoren zeigen, dass Thompson Sampling nicht nur ein glücklicher Zufallstreffer ist, sondern tatsächlich ein ausgeklügelter Online-Optimierungsalgorithmus. Sie entdeckten, dass es funktioniert, indem es versucht, eine bestimmte Art von „Reue" (die Differenz zwischen dem, was man erhalten hat, und dem, was man hätte erhalten können) zu minimieren, während es durch ein Maß an Unsicherheit „regularisiert" (geleitet) wird.

Die Kernidee: Eine neue Art, „Reue" zu messen

Um das Papier zu verstehen, müssen wir uns ansehen, wie sie Erfolg messen.

Der alte Weg (diskontierte Belohnungen):
Stellen Sie sich vor, Sie spielen ein Videospiel, bei dem Punkte, die Sie jetzt erhalten, 100 % wert sind, Punkte, die Sie später erhalten, aber nur noch 90 %, dann 81 % und so weiter. Dies nennt man „Diskontierung". Die berühmte Gittins-Index-Politik nutzt dies. Sie ist großartig für das Spiel, hat aber einen Fehler: Sie könnte eine potenziell bessere Option zu früh aufgeben, weil die zukünftigen Punkte das Risiko nicht wert zu sein scheinen. In der realen Welt, in der wir über lange Zeit alles Mögliche lernen wollen, kann dies ein Fehler sein.

Der neue Weg des Papiers (quadratische Reue):
Die Autoren schlagen eine neue Art vor, das Problem zu betrachten. Anstatt die Zukunft zu diskontieren, betrachten sie das Quadrat der Reue.

Analogie: Stellen Sie sich vor, Sie fahren ein Auto.
- Lineare Reue: Wenn Sie 1 Meile vom Kurs abweichen, sind Sie 1 Meile abgekommen. Wenn Sie 10 Meilen abweichen, sind Sie 10 Meilen abgekommen.
- Quadratische Reue: Wenn Sie 1 Meile abweichen, sind Sie 1 Meile abgekommen. Aber wenn Sie 10 Meilen abweichen, sind Sie nun 100 „Einheiten" schlechter Fahrweise.
- Warum das wichtig ist: Durch das Quadrieren des Fehlers wird der Algorithmus sehr empfindlich gegenüber großen Fehlern. Er zwingt das System, große Fehler zu vermeiden, was natürlich zu einer Strategie führt, die genug erkundet, um nicht auf einem schlechten Weg stecken zu bleiben, aber nicht so viel, dass sie Zeit verschwendet.

Die Autoren nennen dies „Faithful Stationarization". Das ist eine ausgefallene Art zu sagen: „Wir haben eine mathematische Regel gefunden, die über die Zeit hinweg gleich bleibt (stationär), aber dennoch das Ziel der Minimierung langfristiger Fehler perfekt erfasst (faithful)."

Die „Geheimzutat": Unsicherheit vs. Spannung

Das Papier enthüllt, dass Thompson Sampling funktioniert, indem es ein mathematisches Problem löst, das so aussieht:

Minimiere (Fehler) + (Unsicherheits-Strafe)

Die Autoren zerlegen dies in zwei konkurrierende Kräfte:

Gierigkeit (Exploitation): Sie wollen den Arm wählen, der gerade am besten aussieht, um die höchste Belohnung zu erhalten.
Regularisierung (Exploration): Sie benötigen eine „Strafe", um Sie daran zu hindern, zu gierig zu sein. Diese Strafe basiert darauf, wie viel Sie nicht wissen.

Die Entdeckung:
Die Autoren fanden heraus, dass Thompson Sampling eine bestimmte Art von Strafe verwendet, die Biserial Covariance genannt wird.

Die Metapher: Stellen Sie sich vor, Sie wetten auf ein Pferderennen.
- Die Logik von Thompson Sampling: „Ich bin unsicher, welches Pferd gewinnen wird. Je unsicherer ich bin (je ähnlicher die Pferde aussehen), desto mehr sollte ich auf den Außenseiter setzen, um zu sehen, ob sie gewinnen können." Es misst Unsicherheit.
- Die „Bellman-Optimale" Logik (Das Ideal): Die Autoren berechneten, was der perfekte Algorithmus tun würde. Sie stellten fest, dass der perfekte Algorithmus nicht nur auf Unsicherheit schaut, sondern auf Spannung.
- Die Metapher: „Ich bin unsicher, aber lohnt sich das Risiko zu wechseln? Wenn das führende Pferd tatsächlich sehr stark ist und der Außenseiter schwach, sollte ich nicht wechseln, selbst wenn ich ein wenig unsicher bin. Aber wenn das führende Pferd wackelig ist und der Außenseiter stark, ist die Spannung hoch, und ich muss wechseln."

Das Problem:
Thompson Sampling wird manchmal „zu neugierig". Es erkundet eine unterperformende Option weiter, nur weil es einige Unsicherheit gibt, selbst wenn die „Spannung" (der Nutzen eines Wechsels) tatsächlich gering ist. Es ist, als würde man den Ofen alle 30 Sekunden überprüfen, weil man nervös ist, obwohl das Rezept sagt, dass der Kuchen in Ordnung ist.

Die Lösung: Eine „Ein-Schritt"-Fixierung

Das Papier kritisiert Thompson Sampling nicht nur; es bietet eine Möglichkeit, es mit derselben Logik zu beheben, die den „perfekten" Algorithmus antreibt.

Sie schlagen einen Policy Improvement-Schritt vor.

Analogie: Stellen Sie sich vor, Sie sind ein Schüler, der eine Prüfung schreibt.
- Thompson Sampling: Sie beantworten die Fragen basierend auf Ihrem aktuellen Bauchgefühl.
- Die Verbesserung: Bevor Sie den Aufsatz abgeben, nehmen Sie einen Moment Zeit, um Ihre Antworten zu überprüfen und sich zu fragen: „Wenn ich gewusst hätte, was ich nach der Beantwortung dieser Frage weiß, hätte ich meine Antwort geändert?"
- Das Ergebnis: Die Autoren zeigen, dass dieser einzelne Schritt des „Vorausschauens" fast alle Mängel von Thompson Sampling behebt. Er verwandelt den Algorithmus von einem, der rein von „Unsicherheit" getrieben wird, in einen, der von „Spannung" getrieben wird.

In ihren Experimenten schloss diese einzige Anpassung 90 % der Leistungslücke zwischen dem berühmten Thompson Sampling und ihrem theoretischen „perfekten" Algorithmus.

Zusammenfassung der wichtigsten Erkenntnisse

Thompson Sampling ist ein Optimierer: Es ist nicht nur eine Heuristik; es ist ein Algorithmus, der eine bestimmte Art von quadratischem Fehler minimiert.
Der Fehler: Er verlässt sich auf „Unsicherheit" (wie verwirrt ich bin) statt auf „Spannung" (lohnt sich der Aufwand zu wechseln?). Dies führt dazu, dass er manchmal zu viel erkundet.
Die Lösung: Durch Anwendung eines standardmäßigen „Policy Improvement"-Schritts (einen Schritt vorausschauend zu schauen) können wir den Algorithmus so ändern, dass er sich auf „Spannung" konzentriert.
Das Ergebnis: Diese einfache Anpassung macht den Algorithmus nahezu perfekt und er funktioniert fast so gut wie die theoretisch beste mögliche Strategie, ohne dass komplexe neue Mathematik erforderlich ist.

Das Papier sagt im Wesentlichen: „Wir haben das geheime Rezept für Thompson Sampling herausgefunden. Es ist großartig, aber wenn Sie das Gewürz (die Regularisierung) ein wenig anpassen, um sich auf die richtige Art von Spannung zu konzentrieren, wird es noch besser."

Technisches Fazit: Ein umfassenderer Blick auf Thompson Sampling

Problemstellung
Thompson Sampling (TS) ist eine weit verbreitete Heuristik für das Multi-Armed Bandit (MAB)-Problem, bekannt für ihren empirischen Erfolg und theoretischen Regret-Schranken. Im Gegensatz zu Upper Confidence Bound (UCB) oder Gittins-Index-Policies bleibt das explizite Optimierungsprinzip, das die Balance von TS zwischen Exploration und Exploitation steuert, jedoch undurchsichtig. Während Gittins (1979) das Bayessche MAB als Markov-Entscheidungsprozess (MDP) formulierte, um eine optimale Policy abzuleiten, stützt sich dieser Ansatz auf unendlich-horizontige, diskontierte Belohnungen. Diese Formulierung führt zu „unvollständigem Lernen" (das Versagen, den optimalen Arm unendlich oft zu identifizieren), was dem Ziel der Minimierung des Regrets über einen endlichen Horizont widerspricht, das in der MAB-Literatur zentral ist (Robbins 1952; Lai und Robbins 1985). Der Artikel schließt die Lücke im Verständnis von TS, indem er nach einer „treuen" stationären Formulierung sucht, die mit der Minimierung des Regrets über einen endlichen Horizont übereinstimmt und gleichzeitig die Handhabbarkeit der dynamischen Programmierung bewahrt.

Methodik
Die Autoren schlagen einen Rahmen der treuen Stationarisierung vor, um das nicht-stationäre Problem der Minimierung des Regrets über einen endlichen Horizont in ein stationäres Online-Optimierungsproblem umzuwandeln.

Quadratisches Regret-Ziel: Anstatt den kumulativen Regret $R_T$ direkt zu minimieren oder diskontierte Belohnungen zu verwenden, führen die Autoren die Minimierung des kumulativen quadratischen Regrets $R_2$ ein. Sie etablieren eine Schranke $R_T \leq \sqrt{R_2 \cdot T}$ . Die Minimierung der unendlich-horizontigen Summe der quadratischen Regrets $R_2(Q; \pi_0) = \mathbb{E}[\sum r^2(q_t; \pi_t)]$ stellt sicher, dass die Policy die optimale Regret-Rate von $O(\sqrt{T})$ erreicht, während sie ein stationäres Ziel bietet.
Stationäre Bellman-Gleichung: Dieses neue Ziel liefert eine stationäre Bellman-Gleichung für die Wertfunktion $V(\pi_t)$ (den minimalen zukünftigen quadratischen Regret):
$V(\pi_t) = \min_{q_t} \left[ r^2(q_t; \pi_t) + q_t \cdot \mathbb{E}_{\pi_t}[V(\pi_{t+1}) | A_t = \cdot] \right]$
Im Gegensatz zum Gittins-Index (der den linearen diskontierten Gewinn maximiert), ist diese Minimierung quadratisch in den Aktionswahrscheinlichkeiten, was zu einer randomisierten optimalen Policy führt, anstatt zu einer deterministischen.
Online-Optimierungsform: Durch eine Variablentransformation mit Fokus auf die erwartete Belohnung der nächsten Runde $x_t$ leiten die Autoren ab, dass die $R_2$ -optimale Policy ( $Q_{R2}$ ) die Form eines Online-Optimierungsproblems annimmt:
$x_{R2}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{R2}(\pi_t) x_t \right]$
Hier repräsentiert der erste Term die instantane Exploitation (Gierigkeit), und der zweite Term ist eine lineare Regularisierung, die Exploration darstellt. Der Regularisierer $\nu_{R2}(\pi_t)$ wird aus der Bellman-Gleichung abgeleitet und misst die Spannung zwischen Exploration und Exploitation (die Differenz im zukünftigen Wert zwischen dem Ziehen der Arme).
Neudeutung von Thompson Sampling: Die Autoren zeigen, dass Thompson Sampling die exakt gleiche Online-Optimierungsform zulässt:
$x_{TS}^t = \arg\min_{x_t} \left[ (\mathbb{E}_{\pi_t}[\max(\theta_1, \theta_2)] - x_t)^2 + \nu_{TS}(\pi_t) x_t \right]$
Allerdings ist ihr Regularisierer $\nu_{TS}(\pi_t)$ die biserialle Kovarianz zwischen der Gewinnlücke ( $\theta_1 - \theta_2$ ) und der Identität des optimalen Arms ( $\text{sign}(\theta_1 - \theta_2)$ ). Dieser Regularisierer misst die Unsicherheit darüber, welcher Arm besser ist, und nicht die Spannung zwischen sofortigem Gewinn und zukünftigem Wert.

Hauptbeiträge

Treue Stationarisierung: Der Artikel führt eine stationäre Formulierung (Minimierung des quadratischen Regrets) ein, die das Wesen der Minimierung des Regrets über einen endlichen Horizont bewahrt und die Lücke zwischen heuristischem Sampling und prinzipieller dynamischer Programmierung schließt.
Strukturelle Vereinheitlichung: Es wird aufgezeigt, dass sowohl Thompson Sampling als auch die Bellman-optimale Policy ( $Q_{R2}$ ) Instanzen von Online-Optimierungsalgorithmen sind, die Gierigkeit gegen einen Regularisierer abwägen.
Mechanismus-Identifikation: Der Artikel identifiziert den spezifischen Mechanismus, der TS antreibt: Er regularisiert Gierigkeit basierend auf Unsicherheit (biserialle Kovarianz), während die optimale Policy basierend auf Spannung (Differenz im zukünftigen Wert) regularisiert.
Policy-Verbesserung: Unter Ausnutzung des Bellman-Rahmens schlagen die Autoren einen Standard-Schritt zur Policy-Verbesserung für TS vor. Durch die Evaluierung der Wertfunktion von TS und das Zurücksetzen in die Bellman-Gleichung leiten sie eine verbesserte Policy ( $Q_{TS'}$ ) ab, die einen spannungsbasierten Regularisierer verwendet.

Ergebnisse

Leistungsgefälle: Numerische Experimente an Gaußschen und Bernoulli-Bandits zeigen, dass die $R_2$ -optimale Policy ( $Q_{R2}$ ) einen signifikant niedrigeren kumulativen Regret erreicht als Thompson Sampling. Das Gefälle wird dem Regularisierer von TS zugeschrieben, der ein Unsicherheitsmaß ist und die „Spannung" nicht erfasst, wenn der führende Arm unsicher ist, der suboptimale Arm jedoch übermäßig ausgenutzt wird.
Informationsgerichtete Abtastung (IDS): Der Artikel stellt fest, dass IDS, eine weitere Heuristik, die gleiche spannungsbasierte Regularisierer-Struktur wie $Q_{R2}$ teilt und nahezu identisch mit der Bellman-optimalen Policy performt, wodurch informationstheoretische und dynamisch-programmierende Perspektiven verbunden werden.
Ein-Schritt-Verbesserung: Ein einzelner Policy-Verbesserungsschritt, der auf Thompson Sampling angewendet wird, schließt etwa 90 % des Leistungsgefälles zwischen TS und dem Bellman-optimalen Benchmark. Diese Verbesserung wandelt den Regularisierer von TS effektiv von einem Unsicherheitsmaß in ein Spannungsmaß um.
Strukturelle Eigenschaft im K-armigen Fall: Im K-armigen Setting weist die Bellman-optimale Policy (und die verbesserte TS) zu jedem Zeitpunkt positive Wahrscheinlichkeiten für höchstens zwei Arme zu, während Standard-TS positive Wahrscheinlichkeiten für alle Arme zuweisen kann. Der Policy-Verbesserungsschritt verleiht TS diese strukturelle Sparsamkeit.

Bedeutung
Der Artikel beansprucht, einen „umfassenderen Blick" auf Thompson Sampling zu bieten, indem er es als Online-Optimierungsalgorithmus neu fasst. Diese Perspektive:

Erklärt die Heuristik: Sie klärt auf, dass TS Exploration und Exploitation ausbalanciert, indem es Gierigkeit mit einem Maß für residuale Unsicherheit regularisiert.
Identifiziert Einschränkungen: Sie zeigt auf, dass die Abhängigkeit von TS von Unsicherheit statt von Spannung zu suboptimalem Verhalten in spezifischen Regimen führt (z. B. wenn der optimale Arm unsicher ist, der suboptimale Arm jedoch eindeutig übermäßig ausgenutzt wird).
Ermöglicht prinzipielle Verbesserungen: Sie bietet einen rigorosen Rahmen zur Verbesserung von Posterior-Sampling-Algorithmen. Durch die Ausrichtung des Regularisierers auf das spannungsbasierte Bellman-Optimum zeigen die Autoren, dass TS mit minimalem Rechenaufwand (ein einziger Policy-Iterationsschritt) erheblich verbessert werden kann, wodurch es sich dem theoretischen Optimum annähert, ohne seine sampling-basierte Natur aufzugeben.