Flow-Corrected Thompson Sampling for Non-Stationary Contextual Bandits
For practitioners deploying contextual bandits in non-stationary environments, fcTS offers a more sample-efficient method by reusing historical data through drift correction and confidence weighting.
The paper tackles non-stationary linear contextual bandits where reward models drift over time. The proposed Flow-Corrected Thompson Sampling (fcTS) outperforms forgetting-based baselines (discounting, sliding windows, periodic restarts) across five case studies and a semi-synthetic portfolio-selection benchmark, with largest gains in settings with recurring temporal structure.
We study non-stationary linear contextual bandits where the reward model drifts over time, rendering classical contextual bandit algorithms brittle because historical data becomes systematically biased. We propose Flow-Corrected Thompson Sampling (fcTS), a Bayesian method that reuses experience by transporting past rewards to the present using an explicit drift model and incorporating each transported observation with a confidence weight that reflects transport reliability. This yields a unified template that specializes in (i) linear parameter drift via online slope estimation and reward correction, (ii) periodic variation via phase-aware reuse across cycles, and (iii) recurring regime switches via changepoint detection and regime-specific posterior memory. The resulting posterior updates remain closed-form under a linear Gaussian model and can be implemented efficiently with truncated, incrementally updated sufficient statistics. Across five controlled case studies and a semi-synthetic portfolio-selection benchmark with multiple overlapping non-stationarities, fcTS outperforms standard forgetting-based baselines (discounting, sliding windows, and periodic restarts), with the largest gains in settings exhibiting recurring temporal structure. These results demonstrate that when non-stationarity is structured, correcting and reweighting historical observations can be substantially more sample-efficient than uniformly discarding them.