CS Paper Radar

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

Mayand Gulati, Kerong Wang, WeiChen Au

cs.LG stat.ML ·submitted 2026-10-02 17:31 UTC · v1
published

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.

Comment
25 pages, 3 figures. Accepted to the E-Values Workshop at NeurIPS 2026 (poster)

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.LG ·2026-09-17 ·Sulgi Kim
code/data similarity 0.72
Abstract · 25 pages, 7 figures, 2 tables in the main text; 2 figures and 3 tables in the supplement. Reference implementation at https://github.com/sul…

Batched multi-armed bandits update on a service's own schedule, and the usual implementation carries each arm's absolute reward rate from one update to the next. When the shared level moves between batches, that memory goes stale even though the comparisons between arms may not have. Odds-Ratio Thompson Sampling (OR-TS) instead carries the joint posterior over log-odds contrasts and fits the common level afresh in every batch, marginalizing it out. This paper specifies that update, places it inside a Bayesian bandit agent with two controls, decay for how much past evidence survives an update and aggressiveness for how sharply belief becomes allocation, and evaluates it against absolute-rate memory. Across 86 public A/B series the level varies about twenty-five times more than the contrast. In prespecified synthetic environments a moving level costs absolute-rate memory five times the regret and leaves the best arm below a majority of traffic in 7 of 20 runs, against none for OR-TS. In a policy simulation built from 71 real experiments, where the contrasts are too small to resolve, expected-click differences stay within 0.1% for 58 of them, yet contrast memory still ends on the better arm more than twice as often. Where the contrasts themselves move, the bet fails, and that case is reported too.

0.26

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

cs.LG stat.ML ·2026-10-21 ·Sharan Sahu, Martin T. Wells
similarity 0.70
Abstract · 49 pages, 8 figures, 5 tables

Adaptive experiments use bandit algorithms to favor interventions with higher expected rewards. However, decision-makers also require reliable inference on current treatment effects: differences between intervention and reference-arm mean rewards at the present time, rather than historical averages. These objectives conflict: reward maximization favors better interventions, whereas current-effect inference requires continued exploration of potentially suboptimal interventions as outcomes change over time. We characterize this tradeoff for $K$-arm bandits with Hölder-smooth mean rewards of exponent $β\in(0,1]$ and constant $L$. Requiring high-probability simultaneous coverage of all current effects by confidence intervals of width at most $w$, we establish matching minimax bounds, up to logarithmic factors, on expected dynamic regret. Over horizon $T$, our algorithm TRACE (Tracking Rewards and Current Effects) achieves regret of order $\widetilde{O}_β\left(\sqrt{KT}+K^{β/(2β+1)}L^{1/(2β+1)}T^{(β+1)/(2β+1)}+Kw^{-2}(1+L^{1/β}w^{-1/β})\right)$, where the notation hides logarithms and constants depending only on $β$. This regret--precision tradeoff separates reward-learning regret from the cost of refreshing current-effect estimates, which remains unavoidable even when one arm is uniformly optimal. An empirical-Bernstein e-process extension adapts exploration to realized prediction errors while preserving worst-case guarantees. When within-block drift is negligible relative to sampling error, all observations, including reward-learning observations, can be reused for asymptotically normal pointwise inference and stronger local stationarity yields local asymptotic efficiency. Finally, we show that regret constraints can prevent honest adaptation to unknown smoothness and support our theory with extensive numerical experiments.

0.08

Structure, Not Belief: Correlated Thompson Sampling from LLM-Derived Covariance in Combinatorial Semi-Bandits

cs.LG cs.AIstat.ML ·2026-10-05 ·Vikram Kakaria, Anish Kataria, Anany Kotawala
publishedbenchmark similarity 0.68
Abstract · 15 pages. Accepted (poster) at DynaFront 2026: Dynamics at the Frontiers of Optimization, Sampling, and Games, NeurIPS 2026 Workshop

Combinatorial Thompson sampling (CTS) draws independent posterior samples for every arm, so its exploration dynamics ignore any relation among arms. We study a minimal change to those dynamics: an LLM is queried once for a partition of the arms, the partition becomes a positive-definite correlation matrix $Σ$ through an RBF kernel on cluster ranks, and the per-round posterior sample is drawn with covariance $Σ$ while the Beta posteriors are updated from real rewards only, so the LLM shapes how the sampler moves, not what it believes. We give a self-contained Bayesian regret bound for the idealized Gaussian sampler whose information gain splits into a $K\log T$ term from the $K$-cluster structure and a ridge term that grows to $d\log T$: the $\sqrt{d/K}$ improvement over independent sampling is a finite-horizon transient, exact only as the within-cluster correlation tends to one. The correlated sampler reduces regret by 19% over CTS on 16 synthetic Bernoulli families at $T=2{,}500$ (6-7% at $T=25{,}000$ with data-adaptive kernels) and by 41% on the Microsoft MIND-small news benchmark ($d=200$ real articles), while pseudo-observation warm starts give nothing. An LLM-free ablation with a simulated oracle of controlled quality shows that on unstructured instances the gain is a property of the kernel shape (a random partition, or a plain tempering of the sampling noise, reproduces it), while belief injection at matched oracle quality never helps.

0.36

Planned Restlessness: Delayed Meta Bandits with Budgets

cs.LG cs.DS ·2026-10-28 ·Sudipto Guha
theory similarity 0.67
Abstract

We study episodic finite-horizon Bayesian bandits, or meta-bandits, with independent arms. Each episode draws fresh arm qualities from unknown recurring priors. Observations arrive after known delays, and plays obey hard per-episode caps and total budgets. A play earns reward and informs both the current quality and the recurring prior: the learner must explore, use, and generalize. We formulate a common planning optimization over learning trajectories. Its LP relaxation values experiments through current reward, resource consumption and continuation: the value of future decisions from the learning state produced. Dual prices separate the arms into local programs and certify every admissible policy, including hierarchical Thompson sampling. Execution enforces the hard constraints while preserving the promised learning transitions or accounting for their loss. The framework also represents risk-sensitive objectives and prices purchased observations and buyout options. Delayed reports create planned restlessness: an arm's information changes while it is not played, through reports of its own earlier plays arriving on a known calendar. For stationary priors, finite reward alphabets, bounded report lag and nonbinding budgets, posterior sampling over the recurring priors bounds the price of not knowing them by $O(\sqrt{N})$ over $N$ episodes, with other parameters fixed. For one undelayed $T$-step episode with arms capped at $T/X$ plays each, we obtain the LP-relative approximation factor $1+(2πX)^{-1/2}+O(X^{-1})$, improving previous factors, with a matching lower bound for the leading term.

0.13

The Surrogate Is Not the Reward: Post-Surrogate Primary-Outcome Acquisition in Contextual Bandits

cs.LG stat.ML ·2026-10-05 ·Kyungbok Lee, Michael R. Kosorok
benchmarkhot direction similarity 0.66
Abstract

We study contextual bandits in which a surrogate is observed after the action but before the learner decides whether to acquire the primary outcome that defines action value and regret. The value of acquiring the primary outcome depends on both decision relevance (how much the current outcome matters for comparing policies) and the residual uncertainty after observing the surrogate. The Audited Surrogate Bandit (ASB) learns a contextual policy while allocating a budget of $B$ primary-outcome acquisitions over $T$ rounds. ASB sets a pre-surrogate acquisition level from current decision relevance and, after observing the surrogate, redistributes that level using an estimate of that residual uncertainty. For a finite class of $N$ policies over $K$ actions, ASB incurs $\widetilde O[\sqrt{KT\log N}\{1+\sqrt{T/B}\}]$ regret relative to the best policy in the class. In a two-action family where the surrogate does not reveal the better action, a learner that observes the surrogate before deciding whether to acquire can achieve bounded regret, whereas any learner that must decide before seeing the surrogate incurs $Ω(T/B)$ worst-case regret under the same budget. Synthetic experiments show that both acquisition factors matter: ASB has lower regret than variants using only decision relevance or only residual uncertainty. On a KuaiRec benchmark of user-video interactions, the regret gap relative to relevance-only acquisition widens and then narrows as the budget grows.

0.47

When Offline Evaluation Misleads: A Diagnostic Protocol for Reward and Policy Selection in Delayed-Feedback Contextual Bandits

cs.LG ·2026-08-12 ·Sang Su Lee, Vineeth Loganathan, Shishir Dash, Vijay Raghavan
publishedbenchmark similarity 0.66
Abstract · Accepted at the 5th Workshop on End-to-End Customer Journey Optimization (KDD 2026)

Personalizing marketing messages with contextual multi-armed bandits (CMABs) drives real business value, yet the objective that ultimately matters - a downstream conversion - is observed only weeks later, too late to drive online learning. Teams therefore train the bandit on a fast proxy reward, and separately must judge whether a contextual bandit is worth its complexity over sending one best message. Settling both decisions with the usual offline checks - a batch off-policy estimate, a marginal arm-discrimination test, a confidence interval - can mislead systematically under delayed feedback. We give an ordered diagnostic protocol that screens a reward-and-policy candidate on two axes, alignment (does optimizing the reward move the north-star?) and learnability (can the bandit identify the reward-optimal policy?), before trusting any reported lift. We validate it where the truth is known - a public off-policy-evaluation benchmark and a controllable synthetic generator - and illustrate it on a deployed large-marketplace push system (where, with five arms and one split, the evidence is directional rather than powered). Two lessons recur. (N1) A single offline number can mis-rank rewards: a denser reward signal gives the bandit more to learn from, so rewards that look tied in a static estimate pull apart once learning happens online. (N2) If you cannot tell in advance which single message is best, a per-user policy partly just avoids betting on the wrong one - that looks like personalization but is really robustness, so a "personalization premium" is easily overstated. Our contribution is methodological rather than algorithmic: the ordered protocol, the two lessons it surfaces, and the end-to-end experience of applying it to a delayed-feedback CMAB.

0.20

Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs

cs.LG ·2026-10-19 ·Xiaojin Zhang
theory similarity 0.65
Abstract

Low reward variance reduces estimation cost, but does not eliminate monitoring of arms that may improve while unobserved. We refine the variance--variation tradeoff and characterize how both costs depend on supplied variance and variation budgets in bounded, non-stationary multi-armed bandits. Let $A$ be the number of arms, $T$ the horizon, $B$ a bound on consecutive mean variation excluding the initial vector, and $Q$ a bound on the sum of the largest per-round reward variances. For every admissible pair $Q,B$, the minimax expected dynamic regret is, within a single logarithmic factor, \[ \min\{T,\;A+\sqrt{AQ}+(AQBT)^{1/3} +\sqrt{AT}\min\{B,\sqrt B\}\}. \] The deterministic boundary $Q=0$ is characterized without logarithms. For small positive budgets, a safe calibration phase identifies a common interval containing all future means of surviving arms. Clipping observations to a wider interval reduces the cost of restarting a prior hybrid static-regret algorithm; an original-mean analytical reference controls its residuals without charging the variation of clipped means. Balancing clipping bias and monitoring closes the small-budget noisy regime. Fixed oblivious constructions give the matching lower bound. We also quantify adaptation costs: on a disclosed deterministic one-improvement family, a stationary-regret budget has a matching worst-case change-regret frontier, including a finite improvement pulse. This implies an $Ω((T/A)^{1/4})$ loss when one policy competes with all supplied-budget deterministic oracle rates. The budget-free low-noise scheduling problem remains separate.

0.07

Learning from a Bandit Learner

cs.LG ·2026-10-19 ·Michela Petriconi, Nicolas Menet, Claire Vernade
similarity 0.65
Abstract

Classical inverse bandit methods typically aim to recover true reward parameters. In contrast, we infer a demonstrator's subjective beliefs, specifically its internal estimates of suboptimality gaps. We consider no-regret demonstrators that follow randomized policies, such as Thompson sampling, and characterize a family of algorithms for which per-step inversion is possible. This enables gap estimates to be recovered directly from the arm-selection distribution. Our analysis identifies an inherent stability-coverage trade-off: inversion becomes ill-conditioned as the demonstrator concentrates its probability mass on a single arm, while the number of informative rounds depends on the rate at which its policy converges. We establish conditions under which inversion is reliable and provide theoretical guarantees on the resulting estimation error. Experiments on simulated data support the analysis and illustrate how these conditions affect gap recovery in practice.

0.09