← Back to all news
arXiv Machine Learning

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

The paper introduces E‑Process‑Authorized Thompson Sampling (e‑ATS), a bandit algorithm that uses full‑history and discounted Beta states to decide when to forget past rewards in non‑stationary environments. An anytime‑valid e‑process first authorizes the discounted state, after which a reversible relevance score determines its influence; before authorization, e‑ATS behaves exactly like optimistic Thompson sampling (OTS). Experiments show that removing the authorization step increases mean normalized dynamic pseudo‑regret by 38.4 % on a registered suite but decreases it by 7.5 % on a literature‑derived replay suite, indicating that evidence controls when adaptation begins rather than guaranteeing improvement.

Related stories

arXiv Machine Learning
Sep 18

Odds-Ratio Thompson Sampling: A Specification and Design Guide for Contrast-Based Multi-Armed Bandits

The paper introduces Odds‑Ratio Thompson Sampling (OR‑TS), a method for batched multi‑armed bandits that updates the joint posterior over log‑odds contrasts and refits the shared level in each batch, rather than carrying over absolute reward rates. It presents a Bayesian bandit agent with controls for decay of past evidence and aggressiveness of allocation, and evaluates OR‑TS against traditional absolute‑rate memory across 86 public A/B series and synthetic environments. Results show that when the shared level varies significantly, OR‑TS outperforms absolute‑rate memory, reducing regret and ensuring the best arm receives more traffic, while also handling cases where contrasts themselves shift.

By Sulgi Kim
agentsreinforcement-learning
More like this →
arXiv Machine Learning
4d ago

The Price of Current-Effect Inference in Nonstationary Multi-Armed Bandits

The paper studies the trade‑off between maximizing rewards and accurately estimating current treatment effects in nonstationary multi‑armed bandits. For $K$‑armed bandits with H"older‑smooth mean rewards, the authors derive minimax bounds on expected dynamic regret under a high‑probability simultaneous coverage requirement for all current effects. They propose the TRACE algorithm, which achieves a regret–precision trade‑off that separates reward‑learning regret from the unavoidable cost of refreshing current‑effect estimates, and extend the method with an empirical‑Bernstein e‑process to adapt exploration while preserving worst‑case guarantees.

By Sharan Sahu, Martin T. Wells
reinforcement-learning
More like this →
arXiv Machine Learning
Sep 25

Exact Bayes Regret and Asymptotic Optimality in High-Dimensional Gaussian Bandits

The paper analyzes Bayesian linear bandits with isotropic Gaussian parameters, independent Gaussian arms, and Gaussian reward noise when the time horizon scales with the dimension. It derives explicit limits for the normalized posterior uncertainty and parameter overlaps, yielding exact regret curves for several policies—including Thompson sampling, posterior‑mean greedy selection, and scaled‑covariance variants. The results show that posterior‑mean greedy selection achieves the optimal Bayes regret, while Thompson sampling incurs a strictly larger leading regret whose ratio to greedy lies between one and two, approaching two for long horizons.

By Prakhar Singhvi (Abstract Math Institute), Yi Zou (Abstract Math Institute), Abhishek Bhattacharjee (Abstract Math Institute)
reinforcement-learning
More like this →