📊 statistics

On-Policy and Off-Policy Learning for Large Action Spaces

Diese Arbeit adressiert die Herausforderungen des Policy-Learnings in kontextuellen Banditen mit großen Aktionsräumen, indem sie strukturierte Bayessche Methoden für das On-Policy-Learning zur Verbesserung der Explorations- und Regret-Schranken vorschlägt, ergänzt durch neuartige Off-Policy-Techniken, welche Schätzfehler minimieren und Bias-Varianz-Abwägungen durch optimierte Zielfunktionen sowie differenzierbare pessimistische Ansätze kontrollieren.

Ursprüngliche Autoren: Imad Aouali

Veröffentlicht 2026-07-31

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Imad Aouali

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

Stellen Sie sich vor, Sie sind der Kapitän eines riesigen Raumschiffs, das versucht, die beste Route durch eine Galaxie mit Millionen von Sternen zu finden. Jedes Mal, wenn Sie sich für einen Stern entscheiden, den Sie besuchen möchten, erhalten Sie ein winziges, unscharfes Signal, das Ihnen sagt, ob dies eine gute oder eine schlechte Wahl war. Dies ist die Welt der kontextuellen Banditen (Contextual Bandits), ein Zweig der künstlichen Intelligenz, der Computern hilft, Entscheidungen zu treffen, wenn sie die Regeln des Spiels noch nicht kennen. Der „Kontext“ ist die Situation, in der Sie sich befinden (wie das Wetter oder Ihre Stimmung), die „Aktion“ ist das, was Sie tun (wie das Auswählen eines Sterns), und die „Belohnung“ ist das Ergebnis (wie das Finden von Schätzen oder das Kollidieren mit einem Asteroiden).

Der schwierige Teil ist die schiere Anzahl der Möglichkeiten. Wenn Sie raten müssen, welcher von einer Million Sternen der beste ist, und Sie nur jeweils ein paar zur Zeit überprüfen können, verbringen Sie vielleicht Ihr ganzes Leben damit, die falschen zu erkunden. Dies ist das Problem des „großen Aktionsraums“ (Large Action Space). Es ist, als versuche man, eine ganz bestimmte Nadel in einem Heuhaufen von der Größe einer Stadt zu finden, aber man kann immer nur einen Halm nach dem anderen herausziehen und hoffen, dass es die Nadel ist. Wissenschaftler interessieren sich dafür, weil dies der Motor hinter Dingen wie Filmempfehlungen, der Anzeige der richtigen Werbung oder sogar dem Design neuer Medikamente ist. Wenn der Computer nur im Kreis rät, verschwendet er Zeit und Geld.

Diese Dissertation befasst sich mit der Frage, wie man einem Computer beibringt, kluge Entscheidungen zu treffen, wenn er mit Millionen von Optionen konfrontiert ist, indem zwei verschiedene Strategien verwendet werden: Lernen während des Vorgehens (On-Policy) und Lernen aus alten Protokollen (Off-Policy).

Das On-Policy-Abenteuer: Lernen durch Tun mit einer Karte

Zuerst betrachtet der Autor das „On-Policy“-Szenario, bei dem der Computer lernt, indem er in Echtzeit mit der Welt interagiert. Stellen Sie sich vor, Sie erkunden eine riesige Bibliothek mit Millionen von Büchern, aber Sie wissen nicht, welche gut sind. Ein Standard-Entdecker würde ein Buch auswählen, eine Seite lesen und, wenn es langweilig ist, zu einem völlig anderen Buch übergehen und wieder ganz von vorne beginnen. Das ist langsam und ineffizient.

Das Papier führt einen klügeren Entdecker mittels Mixed-Effect Thompson Sampling (meTS) ein. Anstatt jedes Buch als ein einzigartiges Mysterium zu behandeln, bemerkt dieser Entdecker, dass Bücher zu Genres gehören. Er lernt, dass „Science-Fiction“-Bücher gemeinsame Merkmale aufweisen. Indem er Bücher in Kategorien gruppiert (wie „Action“, „Romanze“ oder „Krimi“), kann der Entdecker aus nur wenigen Büchern etwas über das gesamte Genre lernen. Wenn er ein großartiges Science-Fiction-Buch liest, erhält er den Hinweis, dass auch andere Science-Fiction-Bücher gut sein könnten. Dieses „Informations-Teilen“ beschleunigt das Lernen drastisch. Die Mathematik zeigt, dass der Computer, anstatt Millionen einzelner Bücher lernen zu müssen, nur ein paar Dutzend „Genres“ (latente Effekte) und die spezifischen Eigenheiten jedes Buches innerhalb dieser Genres lernen muss.

Der Autor geht dann mit Diffusion Thompson Sampling (dTS) noch einen Schritt weiter. Wenn die erste Methode wie das Gruppieren von Büchern nach Genres war, dann ist diese neue Methode wie ein superintelligenter Bibliothekar, der die tiefen, komplexen Verbindungen zwischen Büchern versteht. Vielleicht ist ein Buch eine Mischung aus „Cyberpunk“ und „Historischer Fiktion“, oder es teilt einen spezifischen Schreibstil mit einem Buch aus einem anderen Jahrhundert. Unter Verwendung einer Art von KI namens „Diffusionsmodell“ (dieselbe Technologie, die hinter einigen Bildgeneratoren steckt), lernt der Computer eine reiche, tiefe Karte darüber, wie alle Bücher miteinander in Beziehung stehen. Dies ermöglicht es ihm, die Bibliothek viel schneller zu erkunden, selbst wenn die Bibliothek riesig ist. In Simulationen fanden diese Methoden die besten Bücher viel schneller als ältere Methoden, die jedes Buch wie einen Fremden behandelten.

Die Off-Policy-Herausforderung: Lernen aus einem chaotischen Tagebuch

Als Nächstt beschäftigt sich das Papier mit dem „Off-Policy“-Szenario. Stellen Sie sich vor, Sie können die Bibliothek nicht mehr selbst erkunden können. Stattdessen müssen Sie aus einem chaotischen Tagebuch lernen, das ein früherer Entdecker mit sehr unterschiedlichem Geschmack hinterlassen hat. Vielleicht hat dieser Entdecker nur Horrorfilme gesehen, und nun müssen Sie die besten Liebesfilme finden. Dies ist das „Off-Policy“-Problem: Lernen aus Daten, die von jemand anderem gesammelt wurden.

Der Autor stellt einen weit verbreiteten Glauben auf dem Gebiet infrage: dass das Wichtigste darin besteht, den genauesten „Belohnungsschätzer“ (einen Kristallball, der vorhersagt, wie gut eine Wahl sein wird) zu bauen. Das Papier argumenttiert, dass in riesigen Bibliotheken die Optimierung tatsächlich das größere Problem ist. Es ist, als hätte man eine perfekte Karte (den Schätzer), aber versucht, sich mit einem kaputten Kompass (dem Optimierungsalgorithmus) darauf zu bewegen. Die Mathematik zeigt, dass Standardwege der Nutzung dieser Karten oft in „flachen Plateaus“ oder lokalen Fallen stecken bleiben, was es unmöglich macht, den besten Pfad zu finden, egal wie gut die Karte ist.

Um dies zu beheben, schlägt der Autor einen neuen Ansatz vor: Policy-Weighted Log-Likelihood (PWLL). Anstatt zu versuchen, die exakte Belohnung vorherzusagen, konzentriert sich diese Methode darauf, den Optimierungspfad glatt und leicht begehbar zu machen. Es ist, als würde man von einem zerklüfteten, felsigen Bergpfad zu einem sanften, gewundenen Weg wechseln. Selbst wenn der Weg nicht perfekt gerade ist, ist es viel einfacher, den Gipfel zu erreichen. In Experimenten mit bis zu einer Million Aktionen war dieser einfache, glatte Ansatz konsequent besser als die komplexen, „intelligenten“ Schätzer, die stecken blieben.

Das Papier führt auch eine neue Methode ein, um mit dem „Rauschen“ in dem alten Tagebuch umzugehen. Wenn der vorherige Entdecker bestimmte Abschnitte selten besucht hat, sind die Daten unzuverlässig. Der Autor schlägt die Verwendung von exponentieller Glättung (Exponential Smoothing) komb Kombination mit „prinzipieller Pessimismus“ vor. Betrachten Sie dies als einen vorsichtigen Entdecker, der dem Tagebuch vertraut, aber einen Sicherheitsbuffer hinzufügt. Wenn das Tagebuch sagt, dass ein Pfad großartig ist, die Daten aber unsicher sind, nimmt der Entdecker an, dass der Pfad etwas schlechter sein könnte als berichtet, um Katastrophen zu vermeiden. Das Papier beweist mathematisch, dass diese Methode den Entdecker sicher hält, während sie ihm dennoch erlaubt, effektiv zu lernen, und dass sie auch dann gut funktioniert, wenn die Daten spärlich sind.

Das große Ganze

Kurz gesagt: Diese Dissertation zeigt, dass man bei Millionen von Entscheidungen nicht einfach durch Brute-Force zum Ziel kommen kann. Man muss die verborgenen Strukturen (wie Genres oder tiefe Verbindungen) finden, um das Gelernte zu teilen, und man muss sicherstellen, dass der Lernpfad glatt genug ist, um tatsächlich eine Lösung zu finden. Ob man in Echtzeit lernt oder in alten Protokollen wühlt – der Schlüssel liegt darin, intelligent mit der Gruppierung von Informationen umzugehen und die Mathematik geschickt zu navigieren. Die Ergebnisse, die sowohl auf künstlichen Daten als auch auf realen Filmempfehlungs-Datensätzen getestet wurden, legen nahe, dass diese neuen Methoden ein bedeutender Schritt nach vorn sind, um die Entscheidungsfindung von KI skalierbar und effizient zu machen.

Technisches Resümee: On-Policy und Off-Policy Lernen für große Aktionsräume

Problemstellung

Die Dissertation adressiert die grundlegende Herausforderung des Lernens in interaktiven Systemen, spezifisch bei kontextuellen Banditen, bei denen der Aktionsraum $K$ extrem groß ist (von tausenden bis zu Millionen). In solchen Szenarien stehen sowohl On-Policy (Online) als auch Off-Policy (Offline) Lernalgorithmen vor schwerwiegenden Skalierbarkeitsproblemen:

On-Policy: Standardmäßige Explorationsstrategien wie Thompson Sampling (TS) oder Upper Confidence Bound (UCB) verlassen sich typischerweise auf disjunkte Modelle, bei denen jede Aktion einen unabhängigen Parameter besitzt. In großen Aktionsräumen ist das unabhängige Erlernen jedes Parameters statistisch ineffizient, was zu hohem kumulativem Regret führt. Umgekehrt sind gemeinsame Modelle, die Parameter über alle Aktionen hinweg teilen, oft rechnerisch unpraktikabel aufgrund der $O(K^2)$ - oder $O(K^3)$ -Komplexität bei der Aufrechterhaltung und Aktualisierung einer vollständigen Kovarianzmatrix.
Off-Policy: Das Lernen aus statischen, durch eine Logging-Policy $\pi_0$ $π_{0}$ gesammelten Daten steht vor drei Hauptproblemen:
1. Statistische Ineffizienz: Direkte Methoden (DM) leiden unter hoher Verzerrung (Bias), wenn Aktionen selten beobachtet werden.
2. Varianz: Inverse Propensity Scoring (IPS)-Schätzer weisen eine explodierende Varianz auf, wenn die Logging-Wahrscheinlichkeit $\pi_0(a|x)$ klein ist.
3. Optimierungskomplexität: Die Dissertation argumentt, dass in großen Aktionsräumen die Optimierungslandschaft von Standard-IPS-basierten Zielfunktionen hochgradig nicht-konkav wird, mit flachen Plateaus und exponentiell vielen lokalen Maxima, was dazu führt, dass gradientenbasierte Optimierer versagen, unabhängig von der statistischen Qualität des Schätzers.

Methodik und Beiträge

Die Dissertation ist in zwei Teile gegliedert, die neuartige Methoden für jedes Lernparadigma vorschlagen.

Teil I: On-Policy Lernen (Skalierung von Thompson Sampling)

Die zentrale Erkenntnis besteht darin, die Flexibilität disjunkter Belohnungsmodelle beizubehalten und gleichzeitig strukturierte Bayes'sche Priors einzuführen, die ein Informationssharing über Aktionen hinweg ermöglichen.

1. Mixed-Effect Thompson Sampling (meTS) – Kapitel 3

Methodik: Die Autoren führen ein hierarchisches Bayes'sches Modell ein, bei dem Aktionsparameter $\theta_a$ durch $L$ geteilte latente Effektparameter $\Psi = (\psi_\ell)_{\ell \in [L]}$ gekoppelt sind. Der generative Prozess nimmt an: $\theta_a | \Psi \sim p_0(\cdot|\Psi)$ .
Algorithmus: meTS führt hierarchisches Sampling durch: Zuerst wird die globale Effekte $\Psi_t$ aus deren Posterior gezogen, dann werden die individuellen Aktionsparameter $\theta_{t,a}$ unter der Bedingung von $\Psi_t$ gezogen.
Theoretische Ergebnisse: Für linear-gaußsche Modelle leiten die Autoren exakte geschlossene Form der Posterior-Updates ab. Sie beweisen eine Bayes'sche Regret-Schranke von $\tilde{O}(\sqrt{Td K_{eff}})$ , wobei $K_{eff}$ die effektive Anzahl der Aktionen ist. Wenn die Anzahl der Effekte $L \ll K$ gilt, ist $K_{eff} \ll K$ , was eine multiplikative Verbesserung gegenüber Standard-TS ergibt.
Komplexität: Die Methode reduziert die Speicherkomplexität von $O(K^2d^2)$ auf $O((L^2 + K)d^2)$ und die Laufzeitkomplexität von $O(K^3d^3)$ auf $O((L^3 + K)d^3)$ .
Erweiterungen: Das Framework wird auf Generalisierte Lineare Modelle (GLMs) mittels traktabler Laplace-Approximationen erweitert.

2. Diffusion Thompson Sampling (dTS) – Kapitel 4

Methodik: Um komplexere, nicht-lineare Abhängigkeiten zwischen Aktionen zu erfassen, ersetzen die Autoren die einlagige latente Struktur durch eine tiefe Hierarchie von latenten Variablen, die durch vortrainierte Diffusionsmodelle gesteuert werden. Der Prior wird als eine Markov-Kette von latenten Variablen $\psi_L \to \dots \to \psi_1 \to \theta_a$ definiert, die durch nicht-lineare Link-Funktionen $f_\ell$ verbunden sind.
Algorithmus: dTS verwendet ein rekursives Inferenzverfahren. Es approximiert den schwer berechenbaren (intraktablen) Posterior, indem es ein „Posterior-Diffusionsmodell“ aufrechterhält, bei dem die Link-Funktionen und Kovarianzen über Gauß-ähnliche Updates (Kombination aus Prior-Präzision und Daten-Präzision) aktualisiert werden, ohne durch das neuronale Netz zurückzupropagieren.
Theoretische Ergebnisse: In einem linear-gaußschen Setting skaliert die Regret-Schranke mit der effektiven Anzahl der Aktionen und der Summe der Varianzen über die $L$ Schichten. Die Komplexität skaliert linear mit $L$ , d. h. $O((L+K)d^2)$ , was meTS verbessert.
Bedeutung: Dies zeigt, dass tiefe generative Modelle nicht nur für Repräsentationen, sondern auch zur Strukturierung der für effiziente Exploration notwendigen Unsicherheit eingesetzt werden können.

Teil II: Off-Policy Lernen (Adressierung von Schätzung und Optimierung)

Die Dissertation stellt das vorherrschende „Schätzungs-zentrierte“ Paradigma in Frage und schlägt drei komplementäre Ansätze vor.

1. Structured Direct Method (sDM) – Kapitel 6

Methodik: Analog zu meTS führt sDM einen geteilten latenten Vektor $\psi$ ein, um Aktionsparameter im Offline-Setting zu koppeln. Es berechnet den Posterior über latente Effekte und die bedingten Posteriors für Aktionsparameter.
Ergebnisse: Die Autoren beweisen, dass sDM eine Konvergenz von $O(1/\sqrt{n})$ in der Bayes'schen Suboptimalität erreicht, ohne die restriktive Annahme des „vollständigen Logging-Supports“ zu benötigen. Die Schranke hängt von der Ausrichtung zwischen der Logging-Policy und der optimalen Policy ab.
Erkenntnis: Unter dem betrachteten Kriterium der Bayes'schen Suboptimalität wird gezeigt, dass Greedy-Policies optimal sind und pessimistische Policies übertreffen können, was im Gegensatz zu frequentistischen Settings steht, in denen Pessimismus oft notwendig ist.

2. Optimierung ist wichtiger als Schätzung – Kapitel 7

Methodik: Die Autoren demonstrieren, dass in großen Aktionsräumen der Optimierungsfehler den Schätzungsfehler dominiert. Standard-IPS-basierte Zielfunktionen induzieren nicht-konkave Landschaften, die Optimierer einfangen.
Vorschlag: Anstatt den Wert zu schätzen und dann zu optimieren, plädiert die Dissertation für Policy-Weighted Log-Likelihood (PWLL) Zielfunktionen:
$\hat{U}_g(\pi) = \frac{1}{n} \sum_{i=1}^n g(R_i, \pi_0(A_i|X_i)) \log \pi(A_i|X_i)$
Ergebnisse: Für lineare Softmax-Policies sind PWLL-Zielfunktionen konvex (und stark konvex mit $\ell_2$ -Regularisierung), was einen eindeutigen globalen Maximalwert garantiert. Experimente mit Datensätzen von bis zu einer Million Aktionen zeigen, dass diese einfachen, stabilen Zielfunktionen konsistent komplexere, wertschätzerbasierte Methoden übertreffen.

3. Fundierte Pessimismus für Exponential Smoothing – Kapitel 8

Methodik: Um die Varianz von IPS zu adressieren, führen die Autoren differenzierbare Exponential Smoothing (ES) Schätzer ein, die zwischen fehlender Regularisierung und starker Varianzreduktion interpolieren.
Theorie: Eine zwei-seitige PAC-Bayesian Generalisierungsschranke wird für diese regularisierten Schätzer hergeleitet. Diese Schranke zerlegt den Fehler in Divergenz, Regularisierungs-Bias und verbleibende Varianz.
Anwendung: Die Schranke liefert eine voll differenzierbare, pessimistische Lern-Zielfunktion, die mittels stochastischen Gradientenaufstiegs optimiert werden kann. Das Framework ist vereinheitlicht, um andere Regularisierer wie Clipping und implizite Exploration abzudecken.
Erweiterung: Die Autoren führen auch Logarithmic Smoothing (LS) ein, eine sanfte, differenzierbare Alternative zu Clipping, die engere Konzentrationsschranken erzielt.

Experimentelle Ergebnisse

Die vorgeschlagenen Methoden werden sowohl auf synthetischen als auch auf realen Datensätzen validiert:

On-Policy: In synthetischen linearen und logistischen Banditen übertreffen meTS und dTS die Baselines (LinTS, GLM-TS, HierTS) signifikant, wobei sich die Leistungsdifferenz mit zunehmender Größe des Aktionsraums $K$ vergrößert. In MovieLens-Experimenten (Empfehlungssysteme) erzielt meTS den geringsten Regret selbst dann, wenn das wahre Belohnungsmodell falsch spezifiziert ist, was die Robustheit zeigt.
Off-Policy:
- sDM übertrifft Standard-Direct-Methods, wobei die Gewinne mit wachsendem $K$ steigen.
- PWLL-Zielfunktionen (Kapitel 7) übertreffen konsistent modernste IPS-basierte Methoden auf Datensätzen mit bis zu einer Million Aktionen und zeigen eine überlegene Robustheit gegenüber Hyperparameter-Tuning.
- Die PAC-Bayesian-basierten pessimistischen Zielfunktionen (Kapitel 8) erzielen bessere Belohnungen als Baselines (einschließlich London et al. und Sakhi et al.) über verschiedene Qualitäten der Logging-Policy hinweg, insbesondere wenn die Logging-Policy nicht gleichverteilt ist.

Bedeutung und Ansprüche

Die Dissertation beansprucht, die Lücke zwischen theoretischen Bandit-Algorithmen und den Beschränkungen moderner industrieller Systeme (z. B. Empfehlungssysteme mit Millionen von Artikeln) zu schließen. Ihr zentrales Argument ist, dass die Skalierung auf große Aktionsräume Folgendes erfordert:

Strukturierung der Unsicherheit: Verwendung hierarchischer und diffusionsbasierter Priors, um die statistische Stärke über Aktionen hinweg zu teilen (On-Policy).
Neubewertung von Zielfunktionen: Die Erkenntnis, dass in großen Räumen die Handhabbarkeit der Optimierungslandschaft ebenso entscheidend ist wie die statistische Genauigkeit des Schätzers (Off-Policy).
Differenzierbarer Pessimismus: Entwicklung theoretisch fundierter, jedoch computertechnisch praktikabler, pessimistischer Zielfunktionen, die Varianz und Bias kontrollieren, ohne auf unpraktablen Konstanten zu basieren.

Die Arbeit behauptet, dass durch die Abkehr von unabhängiger Aktionsmodellierung und Standard-Wertschätzung kontextuelle Banditen effektiv in Umgebungen eingesetzt werden können, in denen die Aktionsräume routinemäßig tausende oder Millionen überschreiten.