📊 statistics

PFN-TS: Thompson Sampling for Contextual Bandits via Prior-Data Fitted Networks

Das Papier schlägt PFN-TS vor, einen Thompson-Sampling-Algorithmus, der Prior-Data Fitted Networks nutzt, um bayessche Posteriori in einem einzigen Vorwärtspass zu approximieren, indem er verrauschte Vorhersageverteilungen über einen zentralen Grenzwertsatz mit Teilstichproben in Mittelwert-Belohnungs-Stichproben umwandelt, wodurch starke empirische Leistung und theoretische Bedauernsschranken über verschiedene kontextuelle Banditen-Benchmarks hinweg erreicht werden.

Ursprüngliche Autoren: Yan Shuo Tan, Kenyon Ng, Ruizhe Deng, Sumetha Loganathan, Qiong Zhang, Bibhas Chakraborty

Veröffentlicht 2026-05-12

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Yan Shuo Tan, Kenyon Ng, Ruizhe Deng, Sumetha Loganathan, Qiong Zhang, Bibhas Chakraborty

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 Manager eines Automaten mit vielen verschiedenen Tasten (Aktionen). Jedes Mal, wenn ein Kunde herankommt, befindet er sich in einer bestimmten Stimmung oder Situation (Kontext), und Sie müssen erraten, welche Taste ihm den besten Snack (Belohnung) gibt. Der Haken? Sie wissen nicht, welche Taste für welche Stimmung am besten ist, und Sie erfahren es erst, nachdem Sie sie gedrückt haben. Ihr Ziel ist es, im Laufe der Zeit so viele zufriedene Kunden wie möglich zu machen und gleichzeitig die Anzahl der falschen Vermutungen zu minimieren. Dies ist das Problem des „Kontextuellen Banditen".

Um dies zu lösen, benötigen Sie eine Strategie, die Exploration (das Ausprobieren neuer Tasten zum Lernen) und Exploitation (die Nutzung dessen, was bereits als wirksam bekannt ist) ausbalanciert. Eine beliebte Strategie heißt Thompson-Sampling. Es ist wie eine Kristallkugel, die für jede Taste eine „beste Vermutung" liefert, aber mit einem Twist: Die Kristallkugel ist etwas verschwommen. Sie liefert Ihnen einen Bereich von Möglichkeiten. Sie wählen die Taste aus, die in dieser verschwommenen Vermutung am besten aussieht, was Sie natürlich dazu anregt, Tasten auszuprobieren, die möglicherweise großartig sind, bei denen Sie sich aber noch nicht sicher sind.

Das Problem: Die Kristallkugel ist zu verrauscht

Seit Jahren verwenden Menschen einfache Modelle (wie gerade Linien), um diese Kristallkugeln zu bauen. Doch menschliches Verhalten ist keine gerade Linie; es ist chaotisch, komplex und voller Überraschungen. Neuere, intelligentere Modelle namens Prior-Data Fitted Networks (PFNs) (wie TabPFN) sind darin hervorragend. Sie sind wie „supertrainierte Köche", die Millionen von Rezepten probiert haben. Wenn Sie ihnen ein paar Zutaten (Daten) zeigen, wissen sie sofort, wie das Gericht schmecken wird, ohne dass sie es erneut kochen müssen.

Allerdings gibt es einen Haken. Diese Superköche sind großartig darin, den endgültigen Geschmack (die verrauschte Belohnung) vorherzusagen, aber Thompson-Sampling muss die Unsicherheit bezüglich des Rezepts selbst (die zugrunde liegende mittlere Belohnung) kennen. Die Köche geben Ihnen die Unsicherheit des Rezepts nicht direkt heraus; sie liefern Ihnen nur das fertige Gericht. Zu versuchen, die Unsicherheit des Rezepts herauszufinden, indem man den Koch bittet, das Gericht eine Million Mal zu kochen, ist für einen Echtzeit-Automaten zu langsam.

Die Lösung: PFN-TS (Der intelligente Abkürzungsweg)

Die Autoren dieses Papiers erfanden PFN-TS, eine neue Art, diese Superköche für das Problem des Automaten einzusetzen.

1. Der „subprobenbasierte" Abkürzungsweg (Das geometrische Gitter)
Anstatt den Koch zu bitten, das Gericht für jede einzelne Zutatenkombination zu kochen (was ewig dauert), verwendet PFN-TS einen cleveren mathematischen Trick namens Subsampled Central Limit Theorem (Zentraler Grenzwertsatz auf Basis von Teilstichproben).

Die Analogie: Stellen Sie sich vor, Sie möchten wissen, wie stark der Wasserstand eines Flusses schwankt. Sie könnten ihn jede Sekunde über ein Jahr lang messen (zu viel Arbeit!). Stattdessen misst PFN-TS den Wasserstand zu bestimmten, zeitlich abgestuften Intervallen: Tag 1, Tag 2, Tag 4, Tag 8, Tag 16 und so weiter.
Indem es diese „geometrischen" Momentaufnahmen betrachtet, kann der Algorithmus die Gesamtschwankung (Unsicherheit) des Flusses mathematisch sehr genau schätzen, jedoch mit einem winzigen Bruchteil des Aufwands. Dies ermöglicht dem System, die für Thompson-Sampling benötigte „verschwommene Kristallkugel" zu erhalten, ohne dabei langsamer zu werden.

2. Der „Speicher"-Trick (Caching)
Das Papier nutzt auch eine Eigenschaft der neuen „Superkoch"-Modelle namens KV-Caching.

Die Analogie: Wenn Sie einen Koch fragen: „Was passiert, wenn ich Salz hinzufüge?" und dann: „Was passiert, wenn ich Salz und Pfeffer hinzufüge?", könnte ein normaler Koch den Salzteil vergessen und von vorne beginnen. Aber dieser spezielle Koch erinnert sich an den „Salz"-Teil und berechnet nur noch den „Pfeffer"-Teil.
PFN-TS nutzt dieses Gedächtnis, um vorherige Berechnungen wiederzuverwenden. Wenn der Automat mehrere Tasten überprüft, berechnet er nicht alles von Grund auf neu; er aktualisiert nur die Teile, die sich geändert haben. Dies macht das System unglaublich schnell.

3. Der „Gestaltwandler" (Adaptive Kodierung)
Manchmal sind die Tasten am Gerät völlig unterschiedlich voneinander (wie eine Soda-Taste versus eine Snack-Taste). Manchmal sind sie sich sehr ähnlich (wie ein „scharfer" Snack versus ein „milder" Snack).

PFN-TS verfügt über einen eingebauten „Gestaltwandler". Es versucht gleichzeitig zwei verschiedene Arten, die Daten zu organisieren. Es verwendet ein Bewertungssystem (CRPS), um zu sehen, welche Methode besser funktioniert. Wenn die Tasten ähnlich sind, fasst es sie in einem Modell zusammen. Wenn sie unterschiedlich sind, hält es sie getrennt. Es wählt automatisch die beste Strategie aus, während es lernt.

Was haben sie herausgefunden?

Die Autoren testeten dieses neue System (PFN-TS) gegen viele andere Methoden unter Verwendung von:

Künstlichen Daten: Simulierten Szenarien mit komplexen, nicht-linearen Regeln (wie den berühmten „Friedman"-Funktionen).
Realen Daten: Acht verschiedenen Datensätzen aus der OpenML-Bibliothek (wie die Vorhersage des Einkommens Erwachsener oder von Pilzarten).
Einer echten mobilen Gesundheitsstudie: Der „Drink Less"-App, die versuchte, die beste Strategie für Push-Benachrichtigungen herauszufinden, um Menschen zu helfen, weniger Alkohol zu trinken.

Die Ergebnisse:

Nicht-lineare Aufgaben: PFN-TS war der klare Gewinner. Es übertraf alle anderen Methoden, wenn die Regeln komplex und chaotisch waren.
Lineare Aufgaben: Wenn die Regeln einfach waren (gerade Linien), schnitt es genauso gut ab wie die Standard-Methoden für lineare Zusammenhänge.
Mobile Gesundheit: In der „Drink Less"-Studie erzielte PFN-TS den höchsten geschätzten Wert, was bedeutet, dass es die effektivste Strategie gewesen wäre, um Menschen beim Reduzieren ihres Alkoholkonsums zu helfen.

Zusammenfassung

PFN-TS ist ein neues Werkzeug, das ein leistungsstarkes, vortrainiertes KI-Modell (den „Superkoch") nimmt und ihm beibringt, ein perfekter Entscheidungsträger in unsicheren Situationen zu sein. Es erreicht dies durch einen mathematischen Abkürzungsweg, um Unsicherheit schnell zu schätzen, und einen Speicher-Trick, um schnell zu laufen. Es passt sich automatisch an, ob das Problem einfach oder komplex ist, und macht es damit zu einem Spitzenreiter sowohl für synthetische Tests als auch für reale mobile Gesundheitsanwendungen.

Technische Zusammenfassung: PFN-TS

Problemstellung

Kontextuelle Banditen adressieren sequenzielle Entscheidungsfindung unter Unsicherheit, bei der ein Lernender einen Kontext beobachtet, eine Aktion auswählt und eine stochastische Belohnung erhält. Das Ziel besteht darin, die kumulative Reue über die Zeit zu minimieren. Thompson Sampling (TS) ist eine Standardstrategie, die eine bayessche Posteriorverteilung über Belohnungsfunktionen aufrechterhält und Aktionen gierig aus diesem Posterior sampelt. Die Wirksamkeit von TS hängt jedoch von der Qualität des zugrunde liegenden Belohnungsmodells ab.

In tabellarischen Anwendungen (z. B. mobile Gesundheit, Empfehlungen) sind lineare Belohnungsmodelle oft falsch spezifiziert, da sie komplexe menschliche Verhaltensweisen wie Interaktionen, Schwelleneffekte und Heterogenität nicht erfassen können. Zwar existieren reichhaltigere Alternativen (Kernel-Methoden, neuronale Netze, Baum-Ensembles), diese leiden jedoch unter Skalierbarkeitsproblemen, hohem Rechenaufwand oder starren strukturellen Annahmen. Darüber hinaus erfordern diese Modelle typischerweise schwer zu optimierende Hyperparameter in Online-Umgebungen.

Prior-Data Fitted Networks (PFNs), wie TabPFN und TabICL, bieten eine vielversprechende Alternative. Dies sind Transformer-basierte Modelle, die trainiert wurden, um bayessche posterior-prädiktive Verteilungen (PPDs) über ein breites Prior von datengenerierenden Prozessen zu approximieren. Sie arbeiten mittels In-Context-Learning (ICL), erfordern keine Parameteraktualisierungen und keine Hyperparameteroptimierung. Es besteht jedoch eine kritische Lücke: PFNs geben PPDs aus (Unsicherheit über verrauschte zukünftige Belohnungen), während TS Unsicherheit über die latente mittlere Belohnungsfunktion benötigt. Das direkte Sampeln aus der PPD entspricht nicht dem Sampeln aus dem Posterior der Mittelwertfunktion, was zu suboptimaler Exploration führt.

Methodik: PFN-TS

Die Autoren schlagen PFN-TS vor, einen Thompson-Sampling-Algorithmus, der diese Lücke schließt, indem er PFN-Posterior-Prädiktive in Stichproben der latenten mittleren Belohnungsfunktion umwandelt. Die Methodik besteht aus drei Kernkomponenten:

1. Subsampled Predictive Central Limit Theorem (SubCLT)

Um die Posteriorverteilung des latenten Mittels $f_0(x)$ aus der prädiktiven Sequenz des PFNs zurückzugewinnen, nutzen die Autoren einen prädiktiven Zentralen Grenzwertsatz (CLT).

Theoretische Grundlage: Unter spezifischen Annahmen (asymptotische Varianz, Quasi-Martingal-Bedingungen und beschränkte Momente) konvergiert der Schwanz der Sequenz des prädiktiven Mittels zu einer Gauß-Verteilung, die am latenten Mittel zentriert ist.
Effizienz-Innovation: Traditionelle Ansätze zur Schätzung der Posterior-Varianz erfordern die Berechnung des prädiktiven Mittels über alle $n$ Präfixe des Datensatzes, was für Online-Banditen rechnerisch prohibitiv ist ( $O(n)$ Vorwärtsdurchläufe). PFN-TS führt einen subgesampelten Schätzer ein, der die Varianz unter Verwendung von nur $O(\log n)$ geometrisch beabstandeten Präfixen ( $t_0, t_1, \dots, t_J$ ) berechnet.
Varianzschätzung: Die Varianz wird unter Verwendung von Blockinkrementen $D_j = m_{t_j}(x) - m_{t_{j-1}}(x)$ gewichtet harmonisch ( $w_j$ ) geschätzt. Die Autoren beweisen, dass dieser subgesampelte Schätzer konsistent ist ( $\hat{V}_{s_n} \xrightarrow{p} V(x)$ ) und den CLT erfüllt, was eine handhabbare Gauß-Approximation $N(m_{s_n}(x), \hat{V}_{s_n}(x)/s_n)$ für das Thompson Sampling ermöglicht.

2. Caching und Rechenoptimierung

Um die Kosten pro Runde weiter zu senken, nutzt PFN-TS die Architektur von TabICL (dem spezifisch verwendeten PFN):

Wiederverwendung von KV-Caches: TabICL cacht Key-Value-Aufmerksamkeitsmatrizen für einen festen Trainingsdatensatz. PFN-TS nutzt diese gecachten Repräsentationen über mehrere Runden hinweg wieder.
Aktualisierungspunkte: Der Algorithmus führt nur an den geometrischen „Aktualisierungspunkten" ( $t_j$ ), die durch das SubCLT-Gitter definiert sind, neue Vorwärtsdurchläufe durch. Zwischen den Aktualisierungspunkten verwendet er die Snapshot-Gauß-Approximation, die aus dem neuesten gecachten Zustand abgeleitet wurde. Dies reduziert die Komplexität von $O(n)$ auf $O(\log n)$ Vorwärtsdurchläufe pro Arm pro Runde.

3. Adaptive Kodierungsstrategie

Der Artikel adressiert die Designentscheidung, wie die Arm-Identität im Input repräsentiert wird:

Disjunkte Kodierung: Unterhält unabhängige Modelle pro Arm.
Gemeinsame Kodierung: Hängt die Arm-Identität als One-Hot-Vektor an den Kontext an und ermöglicht so den Informationsaustausch zwischen den Armen.
Adaptive Auswahl: Da keine Kodierung universell dominiert, führt PFN-TS beide während einer „Dual-Kodierungs"-Phase parallel aus. Es wählt die aktive Kodierung basierend auf dem Continuous Ranked Probability Score (CRPS) aus, einer strikt korrekten Scoring-Regel, die Kalibrierung misst. Die Kodierung mit dem niedrigeren kumulativen CRPS wird beibehalten, und der Herausforderer wird nach einer vorab festgelegten Umschaltzeit verworfen.

Hauptbeiträge

Algorithmische Brücke: PFN-TS ist die erste Methode, die PFNs (die PPDs ausgeben) erfolgreich für Thompson Sampling anpasst, indem sie einen konsistenten Schätzer für die Posterior-Varianz des latenten Mittels über einen subgesampelten CLT ableitet.
Theoretische Garantien:
- Konsistenz: Beweist die Konsistenz des subgesampelten Varianzschätzers unter milden Annahmen.
- Reue-Schranke: Leitet eine bayessche Reue-Schranke für PFN-TS her. Die Schranke zerfällt in die Reue des exakten Thompson Sampling unter dem Prior des PFN plus einen Fehlerterm, der von der Approximationsqualität des PFN und des Subsampling-Prozesses abhängt.
Effizienz: Zeigt, dass $O(\log n)$ Vorwärtsdurchläufe für eine konsistente Varianzschätzung ausreichen, was PFN-basierte Banditen für den Online-Einsatz machbar macht.
Empirische Leistung:
- Synthetische Benchmarks: PFN-TS erreicht den besten durchschnittlichen Rang über nichtlineare synthetische Aufgaben (Friedman-Varianten) und bleibt bei linearen Aufgaben konkurrenzfähig.
- OpenML-Benchmarks: Übertrifft Baselines (LinTS, NeuralTS, BFTS, XGBoostTS) auf sechs von acht Klassifizierungs-zu-Bandit-Datensätzen.
- Reale Anwendung: In einer Offline-Evaluation des mobilen Gesundheitsversuchs Drink Less erzielt PFN-TS den höchsten geschätzten Politikwert (SNIPS) am finalen Horizont und übertrifft BFTS und andere Baselines.

Bedeutung und Behauptungen

Der Artikel behauptet, dass PFN-TS zeigt, dass tabellarisches In-Context-Learning als effektives Belohnungsmodell für sequenzielle Entscheidungsfindung dienen kann, sobald eine effiziente Unsicherheitsextraktion und adaptive Kodierung implementiert sind.

Modellflexibilität: Im Gegensatz zu traditionellen Modellen erfordert PFN-TS keine Hyperparameteroptimierung und passt sich automatisch der Datenstruktur (Sparsity, Glattheit, Nichtlinearität) an, die im breiten Prior des PFN inhärent ist.
Praktische Machbarkeit: Durch die Reduzierung des rechnerischen Engpasses der Unsicherheitsschätzung von linear auf logarithmisch in Bezug auf die Datensatzgröße macht die Methode den Einsatz von Foundation-Modellen in Online-Bandit-Szenarien praktisch.
Robustheit: Es wird gezeigt, dass die Methode über diverse datengenerierende Prozesse hinweg robust ist und sowohl bei synthetischen nichtlinearen Aufgaben als auch bei realen mobilen Gesundheitsdaten gut abschneidet.

Die Autoren bleiben bezüglich der Einschränkungen bescheiden und weisen darauf hin, dass die Laufzeit aufgrund wiederholter Modellbewertungen weiterhin eine Einschränkung darstellt und dass die Kalibrierung bei endlichen Stichproben schlecht sein kann, wenn Arm-Historien kurz oder wenig informativ sind. Sie schlagen zukünftige Arbeiten zur regularisierten Varianzschätzung und zu schärferen Reue-Schranken für die spezifischen TabPFN/TabICL-Priors vor.