Technisches Resümee: Flow-Korrigiertes Thompson-Sampling für nicht-stationäre kontextuelle Banditen

Problemformulierung

Die Arbeit befasst sich mit der Herausforderung nicht-stationärer linearer kontextueller Banditen, einem Szenario, in dem die Beziehung zwischen Kontexten, Aktionen und Belohnungen (Rewards) im Zeitverlauf evolviert. In klassischen kontextuellen Banditen wird ein Parametervektor $w_t$ als stationär vorausgesetzt. In realen Anwendungen (z. B. Empfehlungssysteme, dynamische Preisgestaltung, Finanzen) driften jedoch Nutzerpräferenzen und Marktbedingungen, was historische Daten systematisch verzerrt, wenn diese naiv verwendet werden.

Die zentrale Schwierigkeit liegt im Kompromiss zwischen dem Behalten historischer Daten, um die Posterior-Varianz zu reduzieren, und dem Verwerfen alter Daten, um eine Verzerrung durch veraltete Modelle zu vermeiden. Bestehende Ansätze – wie gleitende Fenster (Sliding Windows), exponentielle Diskontierung oder periodische Neustarts – behandeln historische Daten primär als eine Last, die durch das einheitliche Verwerfen oder Abwerten zu managen ist. Die Autoren argumentieren, dass historische Beobachtungen, wenn die Nicht-Stationarität eine vorhersehbare Struktur aufweist (z. B. gradueller Drift, Periodizität oder wiederkehrende Regime), wertvolle Informationen enthalten, die genutzt werden können, sofern sie für die dazwischen liegenden Umweltveränderungen korrigiert werden.

Methodik: Flow-Korrigiertes Thompson-Sampling (FC-TS)

Die Autoren schlagen Flow-Korrigiertes Thompson-Sampling (FC-TS) vor, ein Bayessches Framework, das historische Beobachtungen in „Present-Time Pseudo-Beobachtungen“ transformiert, bevor sie in den Posterior einfließen. Die Methode entkoppelt die Handhabung der Nicht-Stationarität in zwei distinkte Komponenten: einen Transport-Operator und eine Konfidenz-Gewichtungsregel.

1. Kernmechanismus

In jeder Runde $t$ konstruiert FC-TS für jede vergangene Beobachtung $(x_s, a_s, r_s)$ eine transportierte Belohnung $\hat{r}_{s \to t}$:
$$\hat{r}_{s \to t} = r_s + \hat{\Delta}_{s \to t}(x_s, a_s)$$
wobei $\hat{\Delta}_{s \to t}$ die Verschiebung der mittleren Belohnung von Zeit $s$ bis $t$ schätzt. Dies lässt die vergangene Belohnung effektiv „vorwärts fließen“, um sie am aktuellen Belohnungsmodell auszurichten.

Um Rauschen durch ungenaue Drift-Schätzungen zu verhindern, wird jeder transportierten Beobachtung ein Konfidenzgewicht $\omega_{s,t} \in [0, 1]$ zugewiesen. Dieses Gewicht steuert den Einfluss der Beobachtung auf den Posterior, indem es die effektive Rauschvarianz erhöht, falls die Korrektur unsicher ist.

Der Posterior für eine Aktion $a$ wird unter Verwendung dieser gewichteten, transportierten Beobachtungen aktualisiert:
$$\Lambda_t^{(a)} = \lambda I + \sigma^{-2} \sum_{s<t, a_s=a} \omega_{s,t} x_s x_s^\top$$
$$\eta_t^{(a)} = \lambda m_t^{(a)} + \sigma^{-2} \sum_{s<t, a_s=a} \omega_{s,t} \hat{r}_{s \to t} x_s$$
$$\mu_t^{(a)} = (\Lambda_t^{(a)})^{-1} \eta_t^{(a)}$$
Die Aktionswahl erfolgt über Standard-Thompson-Sampling unter Verwendung der Gaußschen Posterior $\mathcal{N}(\mu_t^{(a)}, (\Lambda_t^{(a)})^{-1})$.

2. Strukturierte Instanziierungen

Das Framework bietet ein vereinheitlichtes Template mit spezifischen Instanziierungen für drei gängige Nicht-Stationaritätsmuster:

• Linearer Drift: Nimmt an, dass Parameter als $w_t^{(a)} \approx \theta^{(a)} + t \delta^{(a)}$ evolvieren. Der Transport-Operator nutzt eine Online-Ridge-Regression-Schätzung $\hat{\delta}_t^{(a)}$, um Belohnungen zu verschieben: $\hat{r}_{s \to t} = r_s + (t-s)\langle \hat{\delta}_t^{(a)}, x_s \rangle$. Gewichte nehmen exponentiell ab ($\omega_{s,t} = \gamma^{t-s}$), um die Extrapolationsunsicherheit zu berücksichtigen.
• Periodische Variation: Nimmt an, dass Parameter mit einer Periode $P$ repetieren. Der Transport-Operator ist die Identität ($\hat{r}_{s \to t} = r_s$) für Beobachtungen in derselben Phase. Die Gewichte werden durch die zirkuläre Distanz zwischen den Phasen bestimmt, was dem Algorithmus ermöglicht, Daten aus vorherigen Zyklen wiederzuverwenden ($\omega_{s,t}$ hängt von der Phasen-Nähe ab).
• Wiederkehrende Regime: Handhabt Umgebungen, die zwischen einer endlichen Menge von Regimen wechseln. Der Algorithmus pflegt eine Bank regimespezifischer Posteriors. Bei der Detektion eines Changepoints (via CUSUM auf Vorhersageresiduen) lädt er den Posterior des wiederkehrenden Regimes neu, anstatt von Grund auf neu zu starten.

Das Framework unterstützt zudem die Komposition, wodurch simultan linearer Drift und Periodizität behandelt werden können, indem die jeweiligen Transport- und Gewichtungsregeln kombiniert werden.

Wichtigste Beiträge

1. Flow-korrigierte Posterior-Updates: Die Arbeit führt eine transportbasierte Sichtweise auf Nicht-Stationarität ein, bei der vergangene Belohnungen in Present-Time Pseudo-Beobachtungen korrigiert und via konfidenzgewichteter Bayesscher Updates integriert werden, anstatt sie einheitlich zu verwerfen.
2. Modulares Algorithmus-Design: FC-TS ist definiert durch einen generischen Transport-Operator und eine Gewichtungsregel, die für linearen Drift, periodische Variation und wiederkehrende Regime instanziiert werden können. Dies schließt eine adaptive Variante ein, die Trends und multiple Periodizitäten kombiniert.
3. Empirische Validierung: Eine umfassende Evaluierung über fünf Fallstudien (linearer Drift, periodische Variation, wiederkehrende Regime, kombinierte Nicht-Stationarität und semi-synthetische Portfolio-Selektion) zeigt, dass FC-TS die State-of-the-Art Vergessens-basierten Baselines übertrifft.

Experimentelle Ergebnisse

Die Autoren evaluierten FC-TS gegen vier Baselines: Standard TS (STD-TS), Sliding Window TS (SW-TS), Discounted TS (D-TS) und Restarting TS (R-TS).

• Leistungssteigerungen: FC-TS erzielte in allen fünf Settings den geringsten kumulativen Regret, mit Verbesserungen zwischen 14,1 % und 59,0 % gegenüber der stärksten Baseline in der jeweiligen Umgebung.

• Fallspezifische Erkenntnisse:

  • Linearer Drift: FC-TS glich SW-TS während der Warm-up-Phase, entfernte sich jedoch progressiv, als die Drift-Schätzungen stabil wurden, und gewann in 8 von 10 Seeds.
  • Periodische Variation: FC-TS zeigte den größten synthetischen Gewinn (50,0 %) aufgrund des „Phasen-Gedächtnisses“, indem es Daten aus vorherigen Zyklen akkumulierte. Der Regret pro Zyklus sank von ~70 auf ~4, während die Baselines stagnierten.
  • Wiederkehrende Regime: FC-TS erreichte eine Verbesserung von 59,0 %, indem es regimespezifische Posteriors beim Detektieren eines Wechsels neu lud und so die „Cold-Start“-Strafe von Neustarts vermied.
  • Kombinierte Nicht-Stationarität: In Umgebungen mit sowohl Drift als auch abrupten Changepoints kombinierte FC-TS erfolgreich Drift-Korrektur (für glatte Evolution) und Regime-Resets (für abrupte Änderungen), was eine Verbesserung von 29,5 % ergab.
  • Semi-synthetisches Portfolio: In einer Finanzaufgabe mit überlappenden monatlichen/quartalsweisen Zyklen und Growth-to-Value-Drift verbesserte die adaptive FC-TS-Variante den Regret um 28,1 % gegenüber der besten Baseline (D-TS). Ablationsstudien bestätigten, dass die Drift-Korrektur der dominante Bestandteil dieses Gewinns war.

• Ablations-Ergebnisse:

  • Effektive Stichprobengröße: Das Beibehalten von mehr Daten ohne Transport-Korrektur (die „No-Transport“-Ablation) führte zu einem höheren Regret als Methoden, die Daten verwerfen, was bestätigt, dass veraltete Daten systematische Verzerrungen einführen.
  • Wert des Transports: Der Transport-Operator selbst war für eine Reduktion des Regret um 47–57 % im Vergleich zur No-Transport-Variante über verschiedene Drift-Skalen hinweg verantwortlich, was beweist, dass der Korrekturmechanismus und nicht nur der Posterior-Aufbau die Performance treibt.

Bedeutung und Ansprüche

Die Arbeit behauptet, dass strukturierte Nicht-Stationarität besser durch die Korrektur und Wiederverwendung von Erfahrung adressiert wird als durch das einheitliche Verwerfen derselben.

Die Autoren betonen, dass historische Daten, wenn der Drift der Umgebung vorhersehbar ist (graduell, periodisch oder wiederkehrend), ein Vermögenswert statt einer Last sind. Durch die explizite Modellierung des „Flows“ der Belohnungsverteilung über die Zeit hinweg behält FC-TS eine wesentlich größere effektive Stichprobengröße als Vergessens-basierte Methoden bei. Die Ergebnisse legen nahe, dass der Schlüssel zur Stichproben-Effizienz in nicht-stationären Banditen in der Neu-Gewichtung und Korrektur historischer Beobachtungen basierend auf der spezifischen zeitlichen Struktur der Umgebung liegt, anstatt eine einzige, uniforme Vergessensregel anzuwenden.

Die Arbeit schließt bescheiden mit dem Hinweis, dass zukünftige Arbeiten die Online-Lernstrukturen von Drifts mit kalibrierten Unsicherheiten beinhalten, das Framework auf generalisierte lineare oder neuronale Banditen erweitern und Sicherheitsmechanismen für Hochrisiko-Settings mit unmodellierten Verteilungsverschiebungen entwickeln sollen.