An online experiment usually has to serve two masters. It should send as few people as possible to the worse option, which means keeping "regret" low. It should also produce a trustworthy estimate, with a confidence interval, of how much better one option is. Prior work has worked out the price of this compromise when the options' quality never changes: lowering regret necessarily inflates estimation error. When user preferences drift, as they do under satiation, cultural change, or shifting safety norms, the quantity a decision-maker cares about is no longer the average effect over the trial. It is the effect today. The trial-wide average can name a winner whose advantage has already disappeared.
This note proposes a simple design and asks what it can achieve. The design keeps a fixed minimum share of traffic on every arm for the whole experiment instead of exploring only at the start, and it estimates the current effect from recent data only, reweighting each observation by the known probability that it was assigned. The central claim is that, under drift, the price of good estimation is set jointly by this exploration floor and by how far back the estimator looks. The two must be chosen together, and the resulting trade-off has an exponent set by how smoothly preferences drift. That exponent recovers the known stationary trade-off as a limiting case. We will prove this trade-off, build a version that tunes its look-back window from the data, and test whether its confidence intervals actually cover the true current effect on drifting benchmarks.
Core Claim and Where It Sits
Three results anchor the problem. Multi-armed Bandit Experimental Design proves that for fixed arm gaps, estimation error times the square root of regret is bounded below by a constant. Its EXP3E algorithm moves along this frontier with a forced-exploration dial and corrects the adaptive bias by inverse propensity weighting, which divides each outcome by its assignment probability. Its analysis assumes constant gaps, so it motivates our question but does not answer it. CLIP-OGD shows that minimizing participant regret and minimizing estimator variance cannot both be done at optimal rates. It clips assignment probabilities away from 0 and 1 to keep variance estimates valid. We reuse the clipping idea, but Clip-OGD targets static potential outcomes and ignores welfare. The closest work is Non-stationary Experimental Design under Linear Trends. Its L-EOFU design explores deterministically for $T^\alpha$ rounds and then switches to optimistic arm selection, and it proves a Pareto frontier of error ≈ regret$^{-1/4}$ when effects move along straight lines. Our proposal differs in three ways. We allow any drift of bounded roughness, including abrupt flips, rather than a linear trend. We target the current effect rather than a slope. And we argue that front-loaded exploration is the wrong shape once drift is non-parametric: data from the start of the trial says little about the effect at its end, so exploration must continue throughout.
The drift literature constrains the design and supplies the application. Right Now, Wrong Then shows that stationary preference learning (DPO) falls to roughly 50–55% reward accuracy when preferences flip, while exponential discounting (NS-DPO) stays above 60–70%. Its method is offline and passive, however. It reweights a logged dataset and cannot control which comparisons get collected. Its discount factor also needs a known variation budget, which is the same problem we must solve for the look-back window. Treatment effect optimisation in dynamic environments tracks drifting uplift with contextual bandits but offers no debiased estimator or confidence intervals. Breaking Feedback Loops in Recommender Systems applies inverse propensity weighting to logged recommender data but assumes the interventional preference distribution is stationary. None of these papers controls the data collection and also delivers valid inference about a moving target.
The heuristic behind the claim is short. Let $\varepsilon$ be the minimum assignment probability per arm and let $h$ be the look-back window in rounds. Suppose the effect $\tau(t)$ changes by at most $V(h/T)^\beta$ over any window of $h$ rounds out of horizon $T$, where $\beta$ measures smoothness. Then the windowed weighted estimator $\hat\tau_h(T)$ of the current effect has error
$$\mathbb{E}\big[(\hat\tau_h(T)-\tau(T))^2\big] \lesssim \frac{1}{\varepsilon h} + V^2\Big(\frac{h}{T}\Big)^{2\beta}.$$
The first term is the variance from roughly $\varepsilon h$ samples on the less-favored arm. The second is the bias from averaging over a moving target. Exploration costs regret of order $\varepsilon T$. Choosing $h$ to balance the two error terms gives the conjectured frontier
$$\text{Error}\times \text{Regret}^{\beta/(2\beta+1)} \gtrsim V^{1/(2\beta+1)}.$$
As $\beta\to\infty$ the exponent tends to 1/2, which recovers the EXP3E stationary bound. For Lipschitz drift ($\beta=1$) the exponent is 1/3, a strictly harsher price. This is a back-of-envelope calculation. Whether a matching minimax lower bound holds once the identity of the better arm also drifts, adding tracking regret, is the main theoretical question.
Research Program
The theoretical part has three pieces. First, we prove the lower bound over all adaptive designs for drift classes indexed by $(\beta, V)$, including a piecewise-constant class with $S$ change points. For that class we expect $\varepsilon$ and the inter-change spacing to play the roles that $\varepsilon$ and $h$ play above. Second, we show that the floored design with a matched window attains the bound. Third, we handle the unknown roughness, which is a practical gap in both L-EOFU and NS-DPO. Because the design sets the propensities, the variance of each windowed estimate is known exactly. A Lepski-style rule, which picks the largest window whose estimate agrees with all shorter windows within their noise levels, should therefore choose $h$ without knowing $V$ or $\beta$, at the cost of a logarithmic factor.
For inference, the propensities are fixed before each outcome is observed, so a martingale central limit theorem applies to the windowed estimator. The drift bias does not vanish on its own. Because fully adaptive bias-honest intervals are generally out of reach without knowing the drift scale, we will report undersmoothed intervals that use a window shrunk below the error-optimal choice, and we will measure their empirical coverage rather than assume it.
The algorithm sends $1-(K-1)\varepsilon$ of traffic to the arm currently favored by a sliding-window optimistic rule and $\varepsilon$ to each other arm, clipping in the style of Clip-OGD. Preference drift enters as the application: the arms are competing model versions or recommendation policies, and the outcome is a user's pairwise preference or engagement.
Baselines
The naive reference point is a balanced randomized trial over the full horizon with a single trial-wide average. It has the best stationary precision and linear regret. It also has a non-vanishing bias for the current effect under drift, the failure that motivates L-EOFU. We will run it with the same horizon and also report a variant that uses windowed averages, which is the honest "do nothing adaptive" competitor. Beating it means lower regret at equal or better error on the current effect.
The strongest existing design is L-EOFU from Non-stationary Experimental Design under Linear Trends. It is the only method in the file that trades estimation error against regret under drift. We will give it the same horizon and sweep its $\alpha$ dial over the same grid as our $\varepsilon$, and we will estimate the current effect by extrapolating its fitted lines. No reported result was found on Lacuna for L-EOFU on any of our benchmarks; the paper reports rates rather than benchmark numbers. Beating it means its achieved error–regret curve lies strictly above ours under non-linear and abrupt drift, while staying comparable under linear drift, where L-EOFU is provably optimal.
EXP3E with inverse propensity weighting, from Multi-armed Bandit Experimental Design, is the stationary-optimal design. We run it with matched exploration levels to show what ignoring drift costs. We also run sliding-window Thompson sampling with post-hoc propensity weighting, the regret-focused option. For the offline-drift comparison, NS-DPO-style exponential discounting applied to data logged by a uniform policy indicates how much passive reweighting can recover. Its reported 60–70% versus about 50–55% accuracy under flips is offline and not directly comparable to our metric.
Two ablations isolate the key ingredients, each at matched total exploration and matched tuning budget. The first spends the same exploration budget up front, as L-EOFU's first phase does, instead of spreading it across the horizon. The second uses a fixed window instead of the data-driven one.
Why not just…?
Why not just run a balanced A/B test with rolling windows? It gives clean inference and is a genuine competitor when the arms are nearly tied, because regret is then small anyway. Its regret grows linearly whenever a real gap persists. Our experiments sweep the gap size, and we expect, and will report, a crossover point below which balanced testing is simply fine.
Why not just add an exploration floor to a discounted or sliding-window bandit? This is the honest threat, because it is essentially our algorithm. We concede that the mechanism is simple. The contribution is knowing how to set the floor and the window together, a lower bound showing that no cleverer design does better, a tuning rule that does not need the unknown drift scale, and checked coverage. The window ablation and an ad hoc floor-plus-window grid will show whether the rule matters in practice. If an untuned default does as well, we will say so.
Why not just fit L-EOFU with richer trends, such as polynomials or piecewise lines? Under smooth drift this may work well. Its front-loaded exploration, however, cannot detect a flip that occurs after the phase switch, and the authors themselves flag the fixed switch as an open problem. The late change-point benchmarks decide this question directly.
Why not just log data and discount offline, as NS-DPO does? Discounting cannot create samples on an arm that the logging policy starved. When the logging policy is a bandit, recent windows hold almost no data on the losing arm, and their variance explodes. We will measure this by applying NS-DPO-style weighting to Thompson-sampling logs.
Proposed Experiments
We will use semi-synthetic benchmarks where the true effect path is known. The first is the Hillstrom marketing data (64,000 randomized units, three arms), used by Treatment effect optimisation in dynamic environments, with injected smooth, linear, and abrupt effect drift. The second is the macro-insurance bootstrap of about 14,000 units from CLIP-OGD, with drifting effects. The third is a preference setting built from the TV-HH and UltraFeedback change-point constructions in Right Now, Wrong Then. There, two fixed response policies are the arms and a drifting reward model supplies pairwise preference outcomes. The New Yorker caption ratings (dataset) span 365 weekly contests. We treat them as an exploratory source of real drift trajectories for crowd preference between caption types, with the caveat that the arms must be constructed by us.
The metrics are cumulative regret against the per-round best arm, root-mean-squared error of the current-effect estimate, and coverage and width of 95% intervals. Results are shown as full error–regret curves, not single points.
Three checks are decisive. First, the empirical slope of log error against log regret should approach −1/2 under near-constant effects and become shallower, near −1/3, under Lipschitz drift. If the slopes do not separate, the central claim fails. Second, at matched exploration, the persistent floor should beat front-loaded exploration on current-effect error under late flips. Third, undersmoothed intervals should achieve close to 95% coverage on the endpoint effect, while the bandit-with-post-hoc-weighting baseline should undercover.
References
- Multi-armed Bandit Experimental Design: Online Decision-making and Adaptive Inference
- CLIP-OGD: An Experimental Design for Adaptive Neyman Allocation in Sequential Experiments
- Non-stationary Experimental Design under Linear Trends
- Right Now, Wrong Then: Non-Stationary Direct Preference Optimization under Preference Drift
- Treatment effect optimisation in dynamic environments
- Breaking Feedback Loops in Recommender Systems with Causal Inference