When May a Bandit Leave Its Anchor? E-Process-Authorized Thompson Sampling under Non-stationarity
cs.LG, stat.ML
Submitted: 2026-10-02
Updated: 2026-10-02
Comments: 25 pages, 3 figures. Accepted to the E-Values Workshop at NeurIPS 2026 (poster)
License: http://creativecommons.org/licenses/by/4.0/
The gist: Stationarity rewards memory, but after a change the same history can mislead.
Terminology
Abstract
Stationarity rewards memory, but after a change the same history can mislead. We ask when forgetting should be permitted. E-process-authorized Thompson sampling (e-ATS) gives each arm full-history and discounted Beta states. An anytime-valid e-process first authorizes the discounted state, then a reversible relevance score controls its influence. Before authorization, e-ATS exactly follows optimistic Thompson sampling (OTS). Under a Beta-Bernoulli prior-predictive stationary model, e-ATS's probability of ever departing from OTS is at most the chosen α E, without fitted thresholds. Relative to e-ATS, removing authorization increased mean normalized dynamic pseudo-regret by 38.4% on the registered suite but reduced it by 7.5% on the literature-derived replay suite. Therefore, evidence controls when adaptation begins, not whether it always helps.
Sources
- Sliding-Window Thompson Sampling for Non-Stationary Settings
- Taming Non-stationary Bandits: A Bayesian Approach
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks