PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Sharan Sahu, Martin T. Wells

arXiv:2610.29982v2stat.MLcs.LG

TL;DR

Nonstationary bandits make current treatment-effect inference difficult because older observations may no longer represent present conditions, while adaptive allocation can leave some arms with little recent data. The paper characterizes the regret–precision tradeoff and introduces TRACE and extensions for adaptive exploration and inference. Its bounds show that maintaining precise current-effect estimates has an unavoidable regret cost, even when one arm is uniformly optimal.

  • Problem

    Under temporal drift, historical observations become less representative of current effects, while adaptive allocation may leave lower-reward arms with few recent observations needed for inference.

    Source: §1.2 · p. 4

  • Method

    The paper characterizes a minimax regret–precision tradeoff and introduces TRACE, an empirical-Bernstein extension, and reuse of observations under local stability.

    Source: §5 · p. 21

  • Results

    Matching bounds up to logarithmic factors characterize the minimum dynamic regret for uniformly precise current-effect inference, whose cost persists even when one arm is uniformly optimal.

    Source: §5 · p. 21

  • Takeaways & Limitations

    Locally stable periods permit reuse of reward-learning observations for asymptotically normal inference, with local asymptotic efficiency under stronger conditions.

    Source: §5 · p. 21

    A regret constraint can prevent honest adaptation to unknown smoothness, even when the true environment is constant.

    Source: §3.5 · p. 16

Abstract

from arXiv · show

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\"older-smooth mean rewards of exponent $\beta\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}_{\beta}\left(\sqrt{KT}+K^{\beta/(2\beta+1)}L^{1/(2\beta+1)}T^{(\beta+1)/(2\beta+1)}+Kw^{-2}(1+L^{1/\beta}w^{-1/\beta})\right)$, where the notation hides logarithms and constants depending only on $\beta$. 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.

1 Introduction

Bandit experiments must balance reward maximization with reliable estimates of treatment effects at the present time, especially when rewards drift. The paper studies this regret–inference tradeoff and presents matching bounds, TRACE, and results on adaptive and locally efficient inference.

1 Introduction

  • Adaptive experiments also seek current treatment-effect estimates, which can be distinct from the cumulative-reward objective of choosing interventions that appear more rewarding.The paper notes applications spanning online recommendation, clinical trials, personalized treatment, and sequential policy design.Source: §1 · p. 2
  • Under drift, past outcomes become less representative, while reward-maximizing policies may stop sampling inferior arms even when current-effect inference still needs recent observations.The target is the present effect, not a historical average; earlier observations can describe past performance while poorly describing current performance.Source: §1 · pp. 2–3

1.1 Inference from adaptive experiments

  • Prior work addresses adaptive-data inference, anytime-valid methods, regret–estimation tradeoffs, and nonstationary bandits, but the paper targets current effects under temporal drift.Historical observations trade lower sampling uncertainty against greater temporal bias, while adaptive allocation can leave lower-reward arms with few recent observations.Source: §1.1 · p. 4, §1.2 · p. 4

1.3 Our contributions

  • The paper establishes matching bounds up to logarithmic factors for the minimum dynamic regret required by uniformly precise current-effect inference.The inferential cost of repeatedly sampling arms persists even when one arm is uniformly optimal.Source: §1.3 · p. 5
  • TRACE attains the regret–precision tradeoff by separating reward-learning from inferential sampling; an empirical-Bernstein e-process extension adapts exploration to predictable forecasts while retaining the worst-case guarantee.The paper also shows that small realized drift permits reuse of all TRACE observations for asymptotically normal inference, with local asymptotic efficiency under stronger local stationarity.Source: §1.3 · p. 5
  • Honest inference cannot generally adapt freely to unknown smoothness under a regret constraint, even when the true reward trajectory is constant.Coverage over a rougher Hölder class can require wider intervals when a low-regret policy lacks enough local information to rule out rougher alternatives.Source: §1.3 · p. 5

2 Current-effect bandit model

The model describes a nonstationary K-armed bandit with Hölder-smooth mean rewards and current effects defined against a reference arm. Procedures choose actions and report confidence intervals subject to simultaneous coverage and precision requirements.

2 Current-effect bandit model

  • Arm a has mean reward μ_t,a = μ_a(t/T), with Hölder drift exponent β and constant L; L = 0 is stationary and β = 1 is Lipschitz drift.The learner observes Bernoulli rewards in the minimax formulation, while upper bounds also allow bounded rewards with the specified conditional mean.Source: §2 · p. 6
  • The current effect τ_t(a) is the difference between intervention a's and reference arm 0's expected rewards at round t.Its temporal variation is bounded by 2L|(t − s)/T|^β, so older observations can become less representative.Source: §2 · p. 6
  • A procedure combines action selection with pre-reward confidence intervals for every non-reference arm, requiring simultaneous validity and precision after burn-in.Coverage is required over the full horizon, while precision is required only after a finite burn-in; the main results use t0 = ⌈T/2⌉.Source: §2 · p. 6
  • The model assumes the learner knows T, K, β, L, w, and δ, and measures the cost of inference through constrained minimax regret.The notation suppresses dependence on K, β, and L in the regret criterion.Source: §2 · p. 6

3 Theoretical results

The theoretical results characterize the regret cost of precise current-effect inference, including TRACE’s minimax tradeoff and adaptive exploration that preserves worst-case guarantees. They also examine reusing reward-learning observations under local stability and how regret constraints can limit adaptation to unknown smoothness.

3.1 The regret–precision tradeoff

  • Current-effect inference adds an unavoidable refresh cost: roughly 1 + (L/w)^(1/β) regions each require order w^-2 observations per arm, even if one arm stays optimal.For Lipschitz drift with fixed K and δ, regret is ≍ T^(2/3) + w^-3 log(1/w); in the stationary case it is ≍ T^(1/2) + w^-2.Source: §3.1 · pp. 7–8

3.2 TRACE: Tracking Rewards and Current Effects

  • TRACE separates inference and reward learning, and achieves (w, δ)-valid intervals of width at most w after the first inference block while attaining the minimax regret upper bound.It reserves samples from every arm in inference blocks and runs restarted EXP3 on remaining rounds.Source: §3.2 · pp. 8–9

3.3 Adaptive TRACE with empirical-Bernstein e-processes

  • Adaptive TRACE uses empirical-Bernstein e-processes to stop arm-specific exploration when confidence sequences narrow, retaining TRACE’s worst-case guarantee while reducing samples on favorable paths.When accumulated squared prediction errors scale as v times the sample count, exploration needs Õ(v/w^2 + 1/w) samples, improving from Õ(w^-2) to Õ(w^-1) when v ≲ w.Source: §3.3 · pp. 10, 12

3.4 Local asymptotic inference

  • When arm sample counts stabilize and within-block drift is negligible relative to sampling error, reusing all preceding-block observations yields asymptotically normal current-effect estimates.The estimator includes observations collected during reward-learning rounds, without changing TRACE’s action policy.Source: §3.4 · pp. 13–15
  • Under a stronger local-stability condition, the all-observation estimator attains the convolution lower bound and is locally asymptotically efficient.The varying-block experiment is asymptotically equivalent to a constant-mean adaptive-bandit experiment, so no regular estimator can asymptotically improve its variance.Source: §3.4 · pp. 15–16

3.5 Limits of adaptation to unknown smoothness

  • A regret constraint can limit the information needed to distinguish localized alternatives, preventing full adaptation to reward-trajectory smoothness even when the true environment is constant.Whenever condition (28) is satisfied, max_{⌈T/2⌉≤t≤T} Eπ μ◦|C_t| ≳β L^{1/(2β+1)}r^{-β/(2β+1)}.Source: §3.5 · p. 16

4 Numerical experiments

The experiments examine the regret–precision tradeoff, prediction-adaptive exploration, and local-stationarity inference using synthetic data and Yahoo! R6B, ZOZOTOWN, and HeartSteps datasets.

4.1 Synthetic data experiment

  • Adaptive TRACE approaches w^-2 inference-sample scaling when prediction errors are small, while fixed TRACE shows approximately w^-3 scaling; accurate forecasts also reduce sampling needs.Under locally negligible drift, reusing reward-learning observations maintains approximately nominal coverage and narrows intervals, but coverage deteriorates when local stationarity fails.Source: Figure 3 · p. 17, Figure 4 · p. 18, §4.1 · p. 18

4.2 Yahoo! R6B: the empirical price of current-effect inference

  • Increasing Yahoo! R6B inferential budgets improves current-effect estimation but increases dynamic regret, while Adaptive TRACE stops early and improves this tradeoff.The adaptive-stopping gain becomes more pronounced as the maximum inferential budget increases.Source: Figure 5 · p. 19, §4.2 · p. 19

4.3 ZOZOTOWN: prediction-adaptive inferential exploration

  • In ZOZOTOWN, more accurate forecasts require fewer inference observations; calibrated predictors stop earlier than the naive predictor, which exhausts available randomized observations.Adaptive TRACE reduces inference observations on average across the five selected items.Source: Figure 6 · p. 19, §4.3 · pp. 19–20

4.4 HeartSteps: time-varying current treatment effects

  • HeartSteps estimates show a declining proximal treatment effect over study time, and weekly randomized contrasts show the same qualitative pattern.When preceding windows are locally stable, all-observation Wald intervals have approximately nominal coverage and variance near the local asymptotic lower bound; coverage deteriorates as drift grows, while using all observations yields substantially lower variance than a reserved subset.Source: Figure 7 · p. 20, §4.4 · p. 21

5 Conclusion

The paper characterizes the minimax regret–precision tradeoff for current-effect inference in nonstationary bandits. TRACE separates reward-learning from inferential sampling, while local stability permits data reuse for inference.

5 Conclusion

  • The regret–precision frontier separates reward-learning regret from the additional cost of maintaining sufficiently recent information about each arm.That inferential cost remains unavoidable even when the same arm is uniformly optimal.Source: §5 · p. 21
  • TRACE attains the tradeoff by separating reward-learning and inferential sampling, and its empirical-Bernstein extension adapts exploration to realized prediction errors while retaining worst-case guarantees.Source: §5 · p. 21
  • Locally stable periods allow reward-learning observations to be reused for asymptotically normal current-effect inference, with local asymptotic efficiency under stronger conditions.Source: §5 · p. 21

A Proof of Theorem 3.1

The proof establishes Theorem 3.1 by combining lower bounds for current-effect inference and reward learning with the upper bound. Its inference construction shows that narrow, simultaneously valid intervals can require costly exploration even when one arm is uniformly optimal.

A Proof of Theorem 3.1

  • Width-w intervals must recover K−1 signs in a construction where arm 0 is optimal, and each pull of another arm incurs regret of at least 1/4.The separated possible current effects make the valid intervals identify each sign.Source: A Proof of Theorem 3.1 · p. 28
  • In the drifting construction, q ≍β 1 + (L/w)^(1/β) bump times require recovery of q(K−1) signs.The bumps have disjoint support, and arm 0 remains optimal throughout.Source: A Proof of Theorem 3.1 · p. 28
  • The reward-learning lower bound uses localized bumps and combines its nonstationary and stationary bounds with the inference bound.The proof identifies the localized testing construction as one used for smooth nonstationary bandits.Source: A Proof of Theorem 3.1 · p. 29
  • The proof combines the inference and reward-learning lower bounds with the upper bound to establish Theorem 3.1.The lower-bound terms are combined before concluding the theorem.Source: A Proof of Theorem 3.1 · p. 29

B Proof of Theorem 3.2

The proof of Theorem 3.2 controls current-effect estimation error through sampling and drift, then bounds regret by separating inference rounds from reward-learning rounds. It selects block and sample sizes to ensure valid intervals of width at most w.

B Proof of Theorem 3.2

  • The proof bounds estimation error using a martingale concentration argument and Hölder drift between the sampled block and the current time.The selected block count and sample count make the resulting confidence intervals valid with probability at least 1−δ.Source: B Proof of Theorem 3.2 · p. 30
  • J⋆ ≍ (L/w)^(1/β) and m⋆ ≍ log(KJ⋆/δ)/w^2 suffice for TRACE to be (w, δ)-valid.The choices control the temporal-bias and sampling-error contributions to the confidence interval.Source: B Proof of Theorem 3.2 · p. 30
  • The regret decomposition separates inference-round exploration, drift within reward-restart blocks, and EXP3 regret against each block’s starting best arm.The proof applies a restarted EXP3 update on reward-learning rounds.Source: B Proof of Theorem 3.2 · p. 31

C Proof of Lemma 3.3

The proof establishes simultaneous coverage by constructing nonnegative supermartingales under the block-mean null and converting their time-uniform bounds into confidence intervals. The resulting coverage holds under predictable predictions and adaptive action selection.

C Proof of Lemma 3.3

  • Under the block-mean null and predictable bounded predictions, the proof constructs nonnegative supermartingales for both deviation directions.The conditional empirical-Bernstein inequality and the within-block drift bound establish the required supermartingale property.Source: C Proof of Lemma 3.3 · p. 33
  • A mixture boundary and Ville’s inequality yield time-uniform deviation bounds, which produce base confidence intervals across the block.The two signs are union-bounded, and the result holds simultaneously over the specified times.Source: C Proof of Lemma 3.3 · pp. 33–34
  • A union bound over blocks and arms shows that the running intersections contain the block means simultaneously with probability at least 1−δ.This also ensures the running intersections are nonempty on the coverage event.Source: C Proof of Lemma 3.3 · pp. 34–35
  • The coverage conclusion holds for arbitrary predictable predictions and adaptive action selection.The argument requires the predictions to be bounded and measurable before the corresponding outcome.Source: C Proof of Lemma 3.3 · p. 35

D Proof of Theorem 3.3

Theorem 3.3’s proof extends the validity argument to saved intervals and bounds the added regret from data-dependent forced exploration. Exploration stops arm by arm once its interval is sufficiently narrow.

D Proof of Theorem 3.3

  • Saved intervals yield simultaneous current-effect coverage, and the drift allowance keeps their final widths at most w.The proof uses a saved-interval width at most w/4 and a Hölder-drift bound.Source: D Proof of Theorem 3.3 · p. 35
  • The reward-restart and EXP3 regret bounds carry over because forced-exploration membership is determined before observing the reward and EXP3 weights are frozen on those rounds.The proof combines these bounds with the forced-exploration cost.Source: D Proof of Theorem 3.3 · p. 35
  • Each arm is explored at most m⋆ times per block, so forced exploration contributes at most KJm⋆ expected regret.The argument bounds instantaneous regret on each forced exploration round by one.Source: D Proof of Theorem 3.3 · p. 35

E Proof of Corollary 3.4

The proof bounds how many observations are needed before the empirical-Bernstein confidence interval is narrow enough to stop exploration.

E Proof of Corollary 3.4

  • Exploration stops once the empirical-Bernstein radius is small enough that the running intersection has width below w/4.The proof uses dJ ≤ w/32 and Bα(Vj,a(t)) ≤ wn/16 to bound the base interval width by 3w/16.Source: E Proof of Corollary 3.4 · p. 35
  • A sufficiently large sample count of order (v/w^2 + 1/w)A guarantees the empirical-Bernstein radius per observation is at most w/16.Here A = log(4KJ/δ) + log log(e + m); deterministic Hoeffding concentration also guarantees stopping within m observations.Source: E Proof of Corollary 3.4 · p. 36

F Proof of Theorem 3.4

Under Assumptions 3.1(i) and 3.1(ii), the proof establishes asymptotic normality for current-effect estimates using observations in the final window. It controls the score, conditional variance, and plug-in covariance before combining these results.

F Proof of Theorem 3.4

  • The centered reward sum ST,a is of stochastic order √nT,a for each arm.This controls the leading sampling-error term in the current-effect estimate.Source: F Proof of Theorem 3.4 · p. 36
  • The current mean estimate differs from its target by ST,a/nT,a plus a term negligible relative to nT,a^-1/2.The expansion uses the final-window drift bound and the asymptotic stability of arm counts.Source: F Proof of Theorem 3.4 · p. 38
  • The conditional variance converges to the arm variance under the stated assumptions.The proof uses the local drift bound and convergence of the baseline mean estimate.Source: F Proof of Theorem 3.4 · p. 38
  • For every fixed nonzero contrast, the leading term satisfies a martingale central limit theorem.The proof verifies conditional centering, Lindeberg, and conditional variance conditions.Source: F Proof of Theorem 3.4 · pp. 39–40
  • The plug-in covariance is consistent, and combining it with the contrast limit yields the theorem’s asymptotic normality result.The proof combines the covariance result with the negligible remainder using Slutsky’s theorem.Source: F Proof of Theorem 3.4 · pp. 40–41

G Proof of Theorem 3.5

The proof establishes equivalence between locally varying and locally constant experiments under the stated drift condition, then derives local asymptotic normality and efficiency. In the locally constant experiment, the all-observation estimator attains the convolution lower bound.

G Proof of Theorem 3.5

  • The locally constant experiment is locally asymptotically normal with information matrix I, uniformly over bounded local shifts.Its log-likelihood has a quadratic expansion with score and information terms.Source: G Proof of Theorem 3.5 · pp. 44–45
  • The locally varying and locally constant experiments are asymptotically equivalent under Assumption 3.1(i) and Eq. (27).The proof transfers stability and local comparisons using truncation and coupling.Source: G Proof of Theorem 3.5 · pp. 42, 45
  • Every regular estimator of the normalized target has limiting law N(0, 1) ∗ M for some probability law M.This is the stationary convolution lower bound.Source: G Proof of Theorem 3.5 · p. 46
  • The all-observation estimator eτT(a) attains the convolution bound and is locally asymptotically efficient.The efficiency claim follows under the locally constant experiment and the stated count-ratio condition.Source: G Proof of Theorem 3.5 · p. 46

H Proof of Theorem 3.6

The proof constructs disjoint local perturbations in the second half of the horizon and uses arm-0 sampling under a constant environment to identify a perturbation with few observations. At its peak, that perturbation creates a current-effect difference that any covering interval must accommodate.

H Proof of Theorem 3.6

  • Disjoint perturbation windows are placed in the second half of the horizon, with their number scaling as (L/∆)^1/β.Their peaks lie between the horizon midpoint and its end.Source: H Proof of Theorem 3.6 · p. 47
  • Because the windows are disjoint, the total arm-0 observations they contain cannot exceed the total number of arm-0 pulls.The proof selects a window whose expected arm-0 count is at most 2r/q under the constant environment.Source: H Proof of Theorem 3.6 · p. 47
  • The localized alternative remains β-Hölder with constant at most L while changing arm 0’s mean only within its selected window.The construction uses a β-Hölder bump and ∆ ≤ 1/16.Source: H Proof of Theorem 3.6 · p. 47
  • At the perturbation peak, an interval covering both environments must have width at least ∆.The proof uses this separation to derive its interval-width lower bound.Source: H Proof of Theorem 3.6 · pp. 47–48

I Additional experimental results

The additional experiments report real-data results for Yahoo!, ZOZOTOWN, and HeartSteps, including a comparison of local-inference behavior across windows with different temporal drift.

I Additional experimental results

  • The additional real-data experiments include Yahoo! results across values of m, item-level ZOZOTOWN results, and further HeartSteps estimates.Source: I Additional experimental results · p. 48
  • Yahoo! results report dynamic regret, current-effect RMSE, and inference-round fractions across inferential budgets, averaged over 200 Monte Carlo replications.Adaptive TRACE uses a Beta(1, 1)-smoothed historical click-through rate as its predictable reward forecast.Source: Table 3 · p. 48
  • ZOZOTOWN results report prediction RMSE and the number of randomized observations required for each selected item.The predictable reward forecast uses a Beta(1, 1)-smoothed historical click-through rate based only on earlier impressions.Source: Table 4 · p. 48
  • HeartSteps results include weekly randomized contrasts with confidence intervals based on participant-clustered standard errors.Source: Table 5 · p. 49
  • The three-day HeartSteps estimator closely follows the standard normal reference, while the fourteen-day distribution is shifted by accumulated temporal bias.Figure 8 compares studentized all-observation estimates across a locally stable three-day window and a fourteen-day window with larger drift.Source: Figure 8 · p. 49

Related papers

Loading 2610.29982v2…