PaperlayerView exact revision on arXiv

Source-linked AI summary

Best Arm Identification for Bandits with Shifting Means

Lukas Zierahn, Wouter M. Koolen, Shubhada Agrawal, Christina Katsimerou, Dirk van der Hoeven

arXiv:2610.10488v1stat.MLcs.LG

TL;DR

Best-arm identification is challenged when time-varying perturbations shift all arms’ means, even if their pairwise gaps stay fixed. The paper proposes ISM for this setting and proves correctness and sample-complexity guarantees with a matching lower bound up to constants. Its conclusions rely on fixed gaps and boundedness assumptions.

  • Problem

    Classical best-arm identification can lose correctness guarantees when unmodeled perturbations shift all arms’ means, motivating a setting with arbitrary common offsets and stable pairwise gaps.

    Source: §1 · p. 2

  • Method

    ISM uses an evidence measure that generalizes importance weighting and tunes hyperparameters so evidence for suboptimal arms being best does not grow.

    Source: §1 · p. 2

  • Results

    ISM is δ-correct and has an asymptotic K(σ^2 + U^2)/∆_min^2-order sample-complexity upper bound matched by a worst-case lower bound up to constants.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Shifting Means captures common adversarial offsets without a specific generative process while preserving a unique best arm through fixed gaps.

    Source: §1 · p. 2

    The approach assumes fixed pairwise gaps; extending power-side guarantees to gaps that vary adversarially or vanish remains open.

    Source: §7 · p. 10

Abstract

from arXiv · show

We study the best arm identification problem in a stochastic environment with a novel form of adversarial perturbations, which we coin Shifting Means. While classically the mean rewards of the $K$ arms are stable in time, in Shifting Means only the gaps $\boldsymbol{\Delta}$ between mean rewards are stable, while their common shift may be determined adversarially in each round. The objective of the learner is to identify the best arm with high probability while minimizing sample complexity (the fixed confidence setting). Handling shifts requires new tools: we show that algorithms employing a Generalized Likelihood Ratio Test (GLRT) stopping rule, including the popular Track-and-Stop, fail under time-varying shifts. Instead, we propose Importance Weights for Shifting Means ($\mathsf{ISM}$). Assuming means bounded by $U$ and $\sigma^2$-sub-Gaussian rewards, we show $\mathsf{ISM}$ to be $\delta$-correct and to enjoy a sample complexity bound of order $K (\sigma^2 + U^2) \Delta_{\min}^{-2} \ln \frac{1}{\delta}$. We also present a matching (up to constant factors) worst-case lower bound and evaluate our results empirically.

1 Introduction

The paper studies best-arm identification when adversarial common shifts change all arms’ means but leave their pairwise gaps fixed. It introduces ISM, establishes its correctness and sample-complexity guarantees, and examines its empirical practicality and scope.

1 Introduction

  • Shifting Means models arbitrary, unobserved roundwise common offsets while keeping pairwise gaps fixed, so a unique best arm persists.The setting is motivated by global trends that affect all arms in the same direction.Source: §1 · p. 2
  • ISM is proved δ-correct using an evidence measure that generalizes importance weighting and prevents evidence for suboptimal arms from growing.The paper also shows that Track-and-Stop fails under Shifting Means.Source: §1 · p. 2
  • K(σ^2 + U^2)/∆_min^2-order upper and lower bounds match up to constant factors, with the upper bound asymptotic as δ → 0.The lower bound contains the standard BAI lower bound.Source: §1 · p. 2
  • Experiments examine when theoretical bounds predict stopping time and test ISM’s δ-correctness under misspecification.The numerical evaluation is limited to synthetic instances.Source: §1 · pp. 2–3
  • The model assumes additive common shifts, fixed pairwise gaps, and valid known upper bounds on conditional means and the sub-Gaussian variance proxy.The upper sample-complexity bound is asymptotic as δ → 0, and numerical evaluation is synthetic.Source: §1 · p. 3
  • Compared with prior common-shift work, Shifting Means permits shifts to change adversarially every round without the learner observing them.Srisawad et al. [2024] study fixed-budget BAI with fewer environment changes and observed change points.Source: §1 · p. 3

2 Setup and Notation for Shifting Means

The setup formalizes sequential bandit interaction under latent common shifts and defines the fixed-confidence objective. It assumes bounded conditional means, sub-Gaussian rewards, and time-invariant gaps; randomization is central to the stated complexity guarantees.

2 Setup and Notation for Shifting Means

  • The model assumes bounded conditional means, σ^2-sub-Gaussian rewards, and a constant gap vector with a unique best arm.The setup allows arbitrary dependence between the latent rewards and shift.Source: §2 · p. 4
  • A learner is δ-correct when its probability of stopping and recommending a non-best arm is at most δ for every instance satisfying the assumptions.Never stopping also meets this correctness definition.Source: §2 · p. 4
  • In fixed confidence, the learner chooses arms, a stopping time, and a recommendation rule; the goal is strong sample-complexity guarantees.The sample-complexity bound is stated asymptotically as δ → 0.Source: §2 · p. 4
  • The environment may choose latent shifts and conditional noise distributions adversarially and history-dependently, while the setup previews a matching asymptotic lower bound for the sample-complexity guarantee.Randomized arm selection is needed for sample-complexity upper bounds, and randomized shifts are needed for nontrivial lower bounds.Source: §2 · p. 4

3 TAS and GLRT Fail

The section explains why shifting means undermine Track-and-Stop and GLRT stopping rules: shifts can hide arm differences or make the stopping statistic unsafe or ineffective.

3 TAS and GLRT Fail

  • With shifts larger than the gaps, an adversary can make every reward zero-mean against a deterministic arm choice, leaving the sampling rule no information about the gaps.Without constraints on arm means, every δ-correct algorithm requires an unbounded expected number of samples.Source: §3 · p. 4
  • Marginalizing the latent shift adds its variance to reward variance, explaining how shifts can inflate the variability used by a stopping test.The passage expresses the added variance as the variance of the conditional mean given the shift.Source: §3 · p. 4
  • Ignoring shifts in GLRT can exceed the target error probability because randomized shifts inflate reward variance; modeling shifts instead can make GLRT never stop through overfitting.When shifts are included, the statistic remains at its starting value and never crosses its threshold.Source: §3 · p. 5

4 Design and Sample Complexity Analysis of the ISM Strategy

ISM combines pairwise evidence-based stopping and recommendation with optimized sampling; its analysis establishes δ-correctness and sample-complexity guarantees.

4.1 The ISM Stopping and Recommendation Rules

  • Pairwise evidence tracks evidence against b being better than a, and a unit exponential-moment safety constraint yields δ-correct stopping and recommendation.The correctness proof also works when gaps vary arbitrarily over time, provided the best arm stays fixed, though sample complexity may worsen.Source: §4.1 · p. 5

4.2 The Oracle Strategy for Known Gaps

  • For known gaps, the oracle optimizes the minimum evidence drift subject to a safety constraint, with equalized drift across competitors determining the stopping-time scale.The asymptotic stopping-time intuition is about ln(1/δ)/D*(Δ).Source: §4.2 · p. 6
  • The optimization problems for the oracle sampling rule and its parameters are efficiently solvable.The paper notes that a special-purpose implementation exploits the problem's structure.Source: §4.2 · p. 6

4.3 The ISM Sampling Rule for Unknown Gaps

  • For unknown gaps, ISM plugs in estimated gaps, optimizes sampling as if those estimates were true, and mixes in exploration to form its sampling probabilities.The analysis uses forced exploration and Bernstein-type concentration to control estimation and variance complications.Source: §4.3 · p. 7

4.4 Interpretable Bounds

  • The inverse-rate bound resembles classic BAI except for U; the two sides differ by about 2.1, and the stated lower bound requires 2 max_a Δ_a ≤ γU.The paper leaves proving an exact graceful degradation of performance to future work.Source: §4.4 · p. 8

5 Lower bounds

The lower bound constructs bounded-shift bandit instances that make distinguishing different best arms difficult. A raised-cosine shift distribution minimizes Fisher information, yielding a lower bound that nearly matches ISM’s upper bound in the stated regime.

5 Lower bounds

  • The lower-bound instances use Gaussian rewards with means B_t − Δ_a and shifts bounded to preserve the assumed mean range.The shift distribution is chosen to make rewards from instances with different best arms as hard to distinguish as possible.Source: §5 · p. 8
  • A raised-cosine distribution minimizes Fisher information among shift distributions supported on a closed interval [−R, R].For B′ drawn from this distribution, I(B′) = π^2/R^2.Source: §5 · p. 9
  • Theorem 8 establishes a lower bound for any algorithm that is δ-correct across bandit instances with the given U and σ^2.The construction uses a gap vector and shift distribution chosen for the algorithm-independent bound.Source: §5 · p. 9
  • Within a factor of at most 2π^2 ≈ 20, ISM is optimal for gaps small relative to U; the factor approaches 2 when σ^2 dominates U^2.The comparison is between the lower bound and the upper bound of Theorem 6.Source: §5 · p. 9

6 Numerical Experiments

The experiments compare ISM with Track-and-Stop on a four-arm Bernoulli instance under common random shifts. They report stopping times, theoretical-versus-empirical sample complexity, and robustness to misspecification of U.

6 Numerical Experiments

  • The experiment uses four Bernoulli arms with fixed gaps [0.0, 0.05, 0.07, 0.1] and i.i.d. uniform common shifts over [0.1, 1].The setup uses U = 1 and σ^2 = 1/4.Source: §6 · p. 9
  • As δ shrinks, the extra fraction of empirical samples beyond the predicted stopping time vanishes.Table 1 reports theoretical predictions and empirical measurements, with empirical values given as 95% confidence intervals over 1,000 samples.Source: §6 · p. 9, Table 1 · p. 10
  • ISM’s empirical stopping time was 28,085–29,470, versus TAS’s 3,968 or 4,052 depending on tracking strategy.The comparison uses the same setup as Garivier and Kaufmann [2016], modulo shifts.Source: §6 · p. 9
  • Four out of 1,000 runs erred with U = 1; all runs for the other tested U and δ values found the correct arm.The authors describe this as empirical robustness to misspecification of U.Source: §6 · p. 9

7 Discussion & Conclusion

The paper concludes that ISM is δ-correct and its upper sample-complexity guarantee is matched up to a constant factor by a worst-case lower bound in the stated regime. The appendix explains why GLRT-based methods can fail under shifting means, while the discussion identifies a harder power-side setting left open.

7 Discussion & Conclusion

  • ISM is δ-correct, has a sample-complexity guarantee, and is empirically robust to misspecification of U.The paper also reports that GLRT-based approaches fail in the Shifting Means setting.Source: §7 · p. 10
  • The authors’ novel lower-bound construction matches the upper bound up to a constant factor of at most 2π² ≈ 20 when gaps are small relative to U.Source: §7 · p. 10
  • The safety argument extends to settings where only the identity of the best arm is fixed each timestep, but power-side guarantees remain open when estimated gaps vary adversarially or vanish.The authors identify convergence guarantees based on a time-averaged gap as a challenge for future work.Source: §7 · p. 10

A TAS and GLRT fail in the Shifting Means setting

  • A randomized Gaussian shift can inflate observed variance, but that shift scheme is invalid when it violates the bounded mean range.The appendix uses this variance-inflation argument for intuition about why TAS tuned to a 1-Gaussian bandit may fail.Source: §A.1 · p. 12

A.1 TAS Fails

  • For a Gaussian test tuned to unit variance, the GLRT stopping rule is not δ-correct when the data variance exceeds 1.The analysis considers samples distributed as N(m, σ^2) with σ > 1.Source: §A.1 · p. 12

A.2 Naïve TAS Extension

The section tests whether a GLRT stopping rule can be adapted to Shifting Means. It shows that the rule fails to stop, because its statistic is uniformly zero regardless of the observations.

A.2 Naïve TAS Extension

  • The test's numerator and denominator optimize likelihoods under the competing constraints on whether arm a or arm b is better.Source: §A.2 · p. 13
  • At time t, the GLRT has Kt effectively independent parameters to estimate from at most t data points, leading to catastrophic overfitting.Source: §A.2 · p. 13
  • In Shifting Means, the GLRT statistic is uniformly 0 at all times, irrespective of the observed data, so the rule fails to stop with high probability.The GLRT compares the likelihood of the null that arm a is not better than arm b with the alternative that arm b is better.Source: §A.2 · p. 13

B Upper Bound - Stopping and Recommendation Rules - Details

This section gives conditions for stopping and recommendation rules to be δ-correct, then outlines the proof and an optimization result for their parameters. It also establishes joint convexity of the safety constraint Φ.

B Upper Bound - Stopping and Recommendation Rules - Details

  • Φ is jointly convex in its five parameters, and the optimization over α and β can be performed analytically for fixed λ.At the optimum, the safety constraint is saturated; the proof verifies optimality using non-negative Lagrange multipliers and the KKT conditions.Source: B Upper Bound - Stopping and… · pp. 14, 16
  • Any sampling rule paired with the stated stopping and recommendation rules is δ-correct when its predictable parameters satisfy Φ ≤ 1 for every arm pair and round.Source: B Upper Bound - Stopping and… · p. 15
  • For a truly better arm a, the proof controls the chance that evidence against it crosses the threshold using Ville’s inequality and a supermartingale.The proof applies a union bound across arms to control the probability of an incorrect recommendation.Source: B Upper Bound - Stopping and… · p. 15

C Upper Bound - Maximin Drift - Details

These details develop upper bounds through maximin drift, known-gap stopping analysis, and interpretable bounds. They give a sandwich for the maximin optimization and a two-sided inequality for a function used in the interpretable bounds.

C Upper Bound - Maximin Drift - Details

  • The maximin optimization over α and β can be performed analytically for fixed λ, but further progress on D(wa, wb, Δ) is not possible in closed form.The section provides a sandwich for the resulting values and maximizers.Source: C Upper Bound - Maximin Drift - Details · pp. 16–17

D Upper Bound - Known Gaps - Details

E Upper Bound - Interpretable Bounds - Details

F Lower Bounds - Details

The lower-bound details compare histories under instances with different best arms, using a shared shift distribution. The concentration section emphasizes round-uniform exponential-moment control for the evidence.

F Lower Bounds - Details

  • The lower-bound construction compares a true gap vector with an alternative having a different best arm, then uses the KL divergence between the resulting histories.Theorem 8 asserts a lower bound for any algorithm δ-correct across instances with fixed U and σ², using some gap vector and shift distribution.Source: F Lower Bounds - Details · pp. 22–23
  • The hard shift instance uses a shared shift distribution chosen so that the resulting instance satisfies Assumption 1.Source: F Lower Bounds - Details · p. 22

G Concentration: Bernstein with bounded means and sub-Gaussian noise

  • The concentration analysis focuses on exponential moments of the evidence, for which the relevant bound need only remain constant across rounds.The stated constants depend only on U and σ².Source: G Concentration: Bernstein with… · pp. 24–25

H ISM Sample Complexity Analysis

The sample-complexity analysis establishes an asymptotic bound for ISM and explains how its accumulated evidence differs from TAS. It also describes a computation for the optimal weights and parameters.

H ISM Sample Complexity Analysis

  • Theorem 4 establishes an asymptotic sample-complexity bound for ISM, with the proof optimizing its free parameters.The analysis takes the free parameters to their limiting values to obtain the bound.Source: H ISM Sample Complexity Analysis · pp. 26–27
  • ISM accumulates evidence over time, unlike TAS, which recomputes its evidence statistic at each step; this requires different concentration events.Continuity of the optimizers supports near-optimal tuning when the estimated gaps are close to the true gaps.Source: H ISM Sample Complexity Analysis · p. 26

I Variance of evidence

  • To bound evidence variance, the analysis maximizes a convex function over the feasible interval of the common shift, checking its endpoints.The expected evidence is λ_t,a,bΔ_b − α_t,a,b − β_t,a,b.Source: I Variance of evidence · p. 31

J Computation

  • The optimal weights and parameters can be computed with three nested bisections, reaching machine precision in O(K) work.The method is compared with first-order schemes whose iteration count grows with desired accuracy and second-order schemes with O(K^2) work per iteration.Source: J Computation · pp. 31–32

K Numerical Experiments - Additional Figures

The additional experiments show stopping-time histograms from 1,000 runs and report optimized parameters for pairs involving the best arm.

K Numerical Experiments - Additional Figures

  • Figure 1 summarizes stopping times across 1,000 runs, varying δ in the first three histograms and fixing δ = 1/10 in the last.The last histogram mis-specifies U.Source: Figure 1 · p. 32
  • The stopping-time plots distinguish the Theorem 4 expected time (green), empirical average (black), and Lemma 3 prediction (red).The Lemma 3 prediction is also reported in Table 1.Source: Figure 1 · p. 32
  • For pairs involving best arm 1, Table 2 reports optimized parameters with equalized drifts; worst-case variances were not optimized but turned out similar.Source: Table 2 · p. 32

Related papers

Loading 2610.10488v1…