Technische Samenvatting: Flow-Corrected Thompson Sampling voor Niet-Stationaire Contextuele Bandits

Probleemformulering

Het artikel behandelt de uitdaging van niet-stationaire lineaire contextuele bandits, een setting waarin de relatie tussen contexten, acties en beloningen in de loop van de tijd evolueert. In klassieke contextuele bandits wordt aangenomen dat de parametervector $w_t$ stationair is. Echter, in real-world toepassingen (bijv. aanbevelingssystemen, dynamische prijsstelling, financiën) veranderen gebruikersvoorkeuren en marktomstandigheden, wat historische data systematisch vertekend maakt als deze naïef wordt gebruikt.

De kernproblematiek ligt in de afweging tussen het behouden van historische data om de posterieure variantie te verminderen en het verwerpen van oude data om bias door verouderde modellen te voorkomen. Bestaande benaderingen—zoals sliding windows, exponentiële korting en periodieke herstarts—behandelen historische data primair als een last die beheerd moet worden door ze uniform te verwerpen of te verzwakken. De auteurs stellen dat wanneer niet-stationariteit een voorspelbare structuur vertoilt (bijv. geleidelijke drift, periodiciteit of terugkerende regimes), historische observaties waardevolle informatie bevatten die kan worden benut als ze gecorrigeerd worden voor de tussenliggende omgevingsveranderingen.

Methodologie: Flow-Corrected Thompson Sampling (FC-TS)

De auteurs stellen Flow-Corrected Thompson Sampling (FC-TS) voor, een Bayesiaans raamwerk dat historische observaties transformeert naar "huidige pseudo-observaties" voordat ze in de posterieure verdeling worden opgenomen. De methode ontkoppelt de afhandeling van niet-stationariteit in twee afzonderlijke componenten: een transportoperator en een vertrouwenswegingsregel.

1. Kernmechanisme

In elke ronde $t$ construeert FC-TS voor elke verleden observatie $(x_s, a_s, r_s)$ een getransporteerde beloning $\hat{r}_{s \to t}$:
$$\hat{r}_{s \to t} = r_s + \hat{\Delta}_{s \to t}(x_s, a_s)$$
waarbij $\hat{\Delta}_{s \to t}$ de verschuiving in de gemiddelde beloning van tijd $s$ naar $t$ schat. Dit "stroomt" de verleden beloning effectief vooruit om deze af te stemmen op het huidige beloningsmodel.

Om ruis door onnauwkeurige drift-schattingen te voorkomen, krijgt elke getransporteerde observatie een vertrouwensgewicht $\omega_{s,t} \in [0, 1]$. Dit gewicht reguleert de invloed van de observatie op de posterieure verdeling, waarbij de effectieve ruisvariantie wordt opgeblazen als de correctie onzeker is.

De posterieure verdeling voor actie $a$ wordt bijgewerkt met behulp van deze gewogen, getransporteerde observaties:
$$\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)}$$
Actie-selectie verloopt via standaard Thompson sampling met de Gaussische posterieure $\mathcal{N}(\mu_t^{(a)}, (\Lambda_t^{(a)})^{-1})$.

2. Gestructureerde Instantiaties

Het raamwerk biedt een verenigde mal met specifieke instantiaties voor drie veelvoorkomende niet-stationaire patronen:

• Lineaire Drift: Veronderstelt dat parameters evolueren als $w_t^{(a)} \approx \theta^{(a)} + t \delta^{(a)}$. De transportoperator gebruikt een online ridge regressie-schatting $\hat{\delta}_t^{(a)}$ om beloningen te verschuiven: $\hat{r}_{s \to t} = r_s + (t-s)\langle \hat{\delta}_t^{(a)}, x_s \rangle$. Gewichten nemen exponentieel af ($\omega_{s,t} = \gamma^{t-s}$) om extrapolatie-onzekerheid te compenseren.
• Periodieke Variatie: Veronderstelt dat parameters zich herhalen met periode $P$. De transportoperator is de identiteit ($\hat{r}_{s \to t} = r_s$) voor observaties binnen dezelfde fase. Gewichten worden bepaald door de circulaire afstand tussen fasen, waardoor het algoritme data uit vorige cycli kan hergebruiken ($\omega_{s,t}$ hangt af van de nabijheid van de fase).
• Terugkerende Regimes: Behandelt omgevingen die wisselen tussen een eindige set regimes. Het algoritme onderhoudt een bank van regime-specifieke posterieure verdelingen. Bij detectie van een changepoint (via CUSUM op voorspellingsresiduen) laadt het de posterieure verdeling van het herhalende regime opnieuw in, in plaats van vanaf nul te beginnen.

Het raamwerk ondersteunt ook compositie, waardoor simultane afhandeling van lineaire drift en periodiciteit mogelijk is door de respectievelijke transport- en wegingsregels te combineren.

Belangrijkste Bijdragen

1. Flow-gecorrigeerde Posterieure Updates: Het artikel introduceert een transport-gebaseerd perspectief op niet-stationariteit waarbij verleden beloningen worden gecorrigeerd tot huidige pseudo-observaties en worden opgenomen via vertrouwensgewogen Bayesiaanse updates, in plaats van ze uniform te verwerpen.
2. Modulair Algoritmeontwerp: FC-TS wordt gedefinieerd door een generieke transportoperator en wegingsregel, geïnstantieerd voor lineaire drift, periodieke variatie en terugkerende regimes. Dit omvat een adaptieve variant die trends en meerdere periodiciteiten combineert.
3. Empirische Validatie: Uitgebreide evaluatie over vijf casestudy's (lineaire drift, periodieke variatie, terugkerende regimes, samengestelde niet-stationariteit en semi-synthetische portfolio-selectie) toont aan dat FC-TS beter presteert dan state-of-the-art forgetting-gebaseerde baselines.

Experimentele Resultaten

De auteurs evalueerden FC-TS tegen vier baselines: Standard TS (STD-TS), Sliding Window TS (SW-TS), Discounted TS (D-TS) en Restarting TS (R-TS).

• Prestatiewinst: FC-TS behaalde de laagste cumulatieve regret in alle vijf de settings, met verbeteringen variërend van 14,1% tot 59,0% ten opzichte van de sterkste baseline in elk specifiek scenario.

• Casus-specifieke Inzichten:

  • Lineaire Drift: FC-TS kwam tijdens de warm-up fase overeen met SW-TS, maar week progressief af naarmate de drift-schattingen stabiliseerden, waarbij het in 8 van de 10 seeds won.
  • Periodieke Variatie: FC-TS toonde de grootste synthetische winst (50,0%) dankzij "fase-geheugen", waarbij data uit vorige cycli werd geaccumuleerd. De regret per cyclus daalde van ~70 naar ~4, terwijl baselines plateau bereikten.
  • Terugkerende Regimes: FC-TS behaalde een verbetering van 59,0% door regime-specifieke posterieure verdelingen te herladen bij detectie van een switch, waardoor de "cold start"-straf van herstarts werd vermeden.
  • Samengestelde Niet-Stationariteit: In omgevingen met zowel drift als abrupte changepoints, combineerde FC-TS succesvol drift-correctie (voor geleidelijke evolutie) en regime-resets (voor abrupte veranderingen), wat een verbetering van 29,5% opleverde.
  • Semi-Synthetische Portfolio: In een financiële taak met overlappende maandelijkse/kwartaalcycli en growth-to-value drift, verbeterde de adaptieve FC-TS variant de regret met 28,1% ten opzichte van de beste baseline (D-TS). Ablatie-studies bevestigden dat drift-correctie de dominante component van deze winst was.

• Ablatie-bevindingen:

  • Effectieve Steekproefomvang: Het behouden van meer data zonder transport-correctie (de "no-transport" ablatie) resulteerde in een hogere regret dan methoden die data verwerpen, wat bevestigt dat verouderde data systematische bias introduceert.
  • Waarde van Transport: De transportoperator zelf was verantwoordelijk voor een regret-reductie van 47–57% vergeleken met de no-transport variant over diverse drift-schalen, wat bewijst dat het correctiemechanisme, en niet alleen de reconstructie van de posterieure verdeling, de prestaties drijft.

Betekenis en Claims

Het artikel claimt dat gestructureerde niet-stationariteit beter kan worden aangepakt door ervaring te corrigeren en te hergebruiken dan door het uniform te verwerpen.

De auteurs benadrukken dat wanneer de drift van de omgeving voorspelbaar is (geleidelijk, periodiek of terugkerend), historische data een activa is in plaats van een last. Door de "flow" van de beloningsverdeling over de tijd expliciet te modelleren, behoudt FC-TS een veel grotere effectieve steekproefomvang dan forgetting-gebaseerde methoden. De resultaten suggereren dat de sleutel tot de steekproefefficiëntie in niet-stationaire bandits ligt in het herwegen en corrigeren van historische observaties op basis van de specifieke temporele structuur van de omgeving, in plaats van het toepassen van een enkele, uniforme forgetting-regel.

Het artikel sluit bescheiden af met de opmerking dat toekomstig werk onder meer het online leren van drift-structuren met gekalibreerde onzekerheid, het uitbreiden van het raamwerk naar generalized linear of neural bandits, en het ontwikkelen van waarborgen voor high-stakes settings met ongemodelleerde distributieverschuivingen omvat.