When May a Bandit Leave Its Anchor? E-Process-Authorized Thompson Sampling under Non-stationarity

Stationary reward distributions let bandit algorithms benefit from memory: the more history an algorithm accumulates, the more accurately it can estimate each arm's true mean. This memory effect is precisely what makes methods like Thompson sampling effective in static environments. When the underlying reward distributions shift over time—whether due to changing user preferences, concept drift in streaming data, or deliberately changing policies—the same historical data can become misleading. A model that has fully committed to estimates from an earlier regime will suffer from stale preferences, wasting samples and accumulating regret. The core challenge, then, is determining when and how much forgetting to permit: enough to track changes, but not so much that the algorithm loses the benefits of accumulated data.

E-process-authorized Thompson sampling (e-ATS) addresses this challenge through a two-stage authorization mechanism. Each arm maintains both a full-history Beta state and a discounted Beta state that gives less weight to older observations. An anytime-valid e-process first examines the discounted state and authorizes its use if certain statistical conditions are met. Only after this authorization does a reversible relevance score control how much influence the discounted state actually exerts on the sampling decision. This design ensures that forgetting is not applied blindly but is instead gated by evidence about whether the discounted state remains informative.

Before the e-process authorizes the discounted state, e-ATS reduces exactly to optimistic Thompson sampling (OTS). In the OTS framework, arms are sampled preferentially when their uncertainty is high, encouraging exploration of potentially better arms. The transition from OTS to e-ATS is not an abrupt change in algorithmic structure but a gradual shift in behavior as the authorization conditions are met. This means that in stationary environments where the discounted state is clearly appropriate, e-ATS naturally settles into OTS behavior, preserving the exploration properties that make Thompson sampling effective.

Under a Beta-Bernoulli prior-predictive stationary model, e-ATS carries a strong theoretical guarantee: the probability that it ever departs from optimistic Thompson sampling is at most the chosen α_E parameter, without the need for any fitted thresholds or data-dependent tuning. This bound holds unconditionally, meaning that the method's deviation from OTS is constrained by design rather than estimated from the data. The absence of fitted thresholds simplifies deployment and makes the method's behavior more predictable, since practitioners need not select or validate a threshold value specific to their problem.

The authors evaluate e-ATS against variants that remove the e-process authorization step, using two suites of non-stationary bandit problems. On the registered suite, removing authorization increases the mean normalized dynamic pseudo-regret by 38.4 percent, demonstrating that the evidence-driven adaptation mechanism substantially improves performance when the environment changes. On the literature-derived replay suite, the effect reverses: removing authorization reduces regret by 7.5 percent, suggesting that in some previously published non-stationary settings, retaining full history without selective forgetting actually harms performance. These contrasting results highlight that the benefit of forgetting is problem-dependent and that the e-process authorization mechanism provides a principled way to determine when adaptation should activate.

The combined theoretical and empirical findings lead to the paper's central thesis: evidence controls when adaptation begins, not whether it always helps. In some non-stationary environments, retaining full history and never forgetting is detrimental, and the 7.5 percent regret reduction on the replay suite confirms that blindly applying stationary methods can fail. In other environments, sudden changes require rapid forgetting, and the 38.4 percent regret increase on the registered suite shows the cost of failing to adapt. The e-ATS framework resolves this tension by letting the data itself determine the appropriate level of forgetting through the authorization process.

For practitioners looking to apply e-ATS in real systems, the method offers several advantages. The α_E parameter provides a direct knob for controlling the maximum probability of deviating from OTS, without requiring cross-validation or problem-specific tuning. The two-state architecture (full-history and discounted) is straightforward to implement on top of existing Thompson sampling code. The anytime-valid e-process ensures that authorization decisions can be made at any time without violating statistical guarantees. However, the method's effectiveness depends on the quality of the e-process calibration; if the e-process is misspecified or too conservative, the authorization may never trigger, causing e-ATS to behave like OTS even when rapid adaptation is needed.

The theoretical guarantee of bounded departure from OTS holds only under the specific Beta-Bernoulli stationary model; more complex reward distributions or non-Bayesian settings may require additional analysis. The method's performance on the replay suite, where removing authorization helps, suggests that there are non-stationary regimes where full-history methods are already well-suited, and the added complexity of e-ATS may not be warranted. Extending the framework to context-dependent bandits, restless bandits, or multi-agent settings remains an open question. Additionally, the computational overhead of maintaining both full-history and discounted states, along with running the e-process at each step, may be significant in high-arms or real-time constraints.

Developers working with bandits in potentially non-stationary environments should consider methods like e-ATS that provide a data-driven mechanism for controlling forgetting. The key insight is that there is no universally correct level of forgetting; the appropriate amount depends on the speed and nature of environmental changes. The e-ATS framework offers a principled approach: let statistical evidence, not arbitrary scheduling decisions, determine when the discounted state earns influence. For teams already using Thompson sampling, the primary change is adding the authorization layer and maintaining dual state estimates—changes that can be incremental rather than requiring a full algorithm rewrite. The contrasting results on the two evaluation suites also suggest that any deployment should include experimentation across multiple non-stationarity patterns to validate that the chosen authorization strategy delivers the expected regret improvement.