acceptodds
Under review as a conference paper at ICLR 2027

Fixed-Budget Target-Time Best-Arm Identification in Temporally Evolving Bandits

Abstract

Best-arm identification (BAI) in multi-armed bandits usually assumes stationary reward distributions while existing works on non-stationary BAI typically chase an arm with largest average reward over a predefined timespan. We introduce the new setting of *fixed-budget target-time BAI* where rewards may evolve away from a target decision time, and the learner must identify the best arm at that target without knowing the relevant temporal scale of non-stationarity in advance. This setting is motivated by laboratory studies that seek to identify the intervention producing the most favorable outcome at a target time –for example, at the beginning or at the end of a prescribed treatment schedule. Observations farther from the target may be less representative (ie *biased*) and deploying or evaluating an arm can be costly. This introduces a unique challenge where a learner has to manage the budget constraint using the right amount of data that can strike an optimal bias-variance tradeoff when performing BAI. In this work, we explore the limits of identifiability for the target-time non-stationary BAI problem and propose an algorithm that is information-theoretically near *optimal* (upto polylog factors) and *do not* require apriori knowledge of drift. Experiments on synthetic and real-world data expose the strengths and weaknesses of the proposed methods over existing BAI algorithms.

Primary area:
learning theory
Keywords:
Best-Arm-Identification, Multi-Armed Bandits, Non-Stationary, Distribution-Shift

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_SEHPOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The goal is to identify the best arm at a particular time using a limited number of observations from nearby times. Each arm has its own ordered stream: pulling an arm reveals its next sample, moving farther from the target. Longer prefixes reduce sampling noise but can reverse the ordering at the target. SignCount-SH compares each pair at several dyadic prefix lengths, stops at the first decisive comparison, and uses the resulting win counts for sequential halving. The paper proves a simple-regret guarantee and a lower bound over a class defined by its resolution and ranking certificates. Experiments use a synthetic reward trajectory and NYC taxi data; the strongest taxi results come from a Bernstein variant that accounts for batch sampling variance.

Critical strengths
  1. The target-time objective leads to a different statistical problem from identifying the best historical average. The multiresolution test uses this distinction directly: a prefix can preserve the sign of a gap even when it gives a poor estimate of the gap's magnitude. This is a good reason to study the setting separately from stationary BAI.

  2. The ranking certificate addresses the difficult part of the elimination proof. Lemma 12 controls the good arm's score against a bad arm through comparisons with third arms, so it remains useful for a data-dependent surviving set. The hard family in Appendix C.2 then shows that a strong target-time gap can still require many samples when the remaining observations carry only a weak signal. I find this combination more persuasive than an upper bound alone.

Critical weaknesses
  1. I cannot reconstruct the synthetic experiment from the specified stream lengths. Appendix D sets K=8K=8 and T=640T=640, includes target time 545, and reports budgets up to B/K=256B/K=256. Only 96 samples per arm remain after that target. At the largest budget, Algorithm 2 requests 85, 170, and 341 additional samples from surviving arms across its three stages, for a final depth of 596. The paper does not state whether the final regime is extended, streams are resampled, or requests are capped. The choice matters because it determines which drift the algorithms encounter. This needs resolving before the reported synthetic comparison can be assessed.

  2. The taxi results provide narrower evidence than the general scalar-observation model suggests. Section 4.2 reports that the Hoeffding version resolves no duels and behaves like Vanilla-SH through tie-breaking. The improved version uses known batch sizes and variance calibration, with up to 4,000 trips counted as one query. Appendix K appropriately separates identification from forecasting, but its afternoon results show almost no gain over Vanilla-SH. The method is promising in the morning regime; its advantage across observation models and drift patterns remains less clear.

Questions for authors
  1. Experimental clarification: How are samples beyond time 640 generated or handled for the later synthetic targets? Is the same continuation or exhaustion rule used for every method?

  2. Scope clarification: At the reported confidence level, do the experimental trajectories have finite ranking certificates? In particular, do the earlier wrong-sign exclusions in Definition 1 hold for the comparisons needed after the simulated reversals?

1 comment
AuthorsOpenReview ↗

Response to Reviewer SEHP

1. Experimental clarification

We thank the reviewer for identifying this omission. The stated T=640T=640 describes the nonconstant portion of the trajectory. In the experiments, we extend the final plateau unchanged.

  • For each additional time index, we generate a new independent Gaussian observation whose mean is given by the final plateau. No samples are reused.
  • Every requested observation is therefore available to the algorithms, including requests that extend beyond the index T=640T=640.
  • Every method receives the same extended stream realization, so this continuation introduces no additional drift and is identical across methods.

We will state this explicitly in Appendix D.


2. Scope clarification

At (δ,σ)=(0.05,0.02)(\delta,\sigma)=(0.05,0.02), target times 1, 289, and 545 have finite ranking certificates and satisfy the earlier wrong-sign exclusions in Definition 1. Target 49 does not. In this case, for comparisons between the target-best arm 5 and arms 1 and 4, recent-prefix averages never produce a sufficiently strong correctly signed signal to exceed the conservative 3qi(δ)3q_i(\delta) certificate threshold. As older observations enter, the prefix averages eventually become significantly wrong-signed. Their resolving depths, and therefore HNS(δ)(θ,0)H_{\mathrm{NS}}^{(\delta)}(\theta,0), are infinite.

Theorem 5 therefore does not cover target 49. Its success there is empirical. This is possible because Definition 1 is a sufficient certificate, not an instance-wise necessary condition. We will clarify that the experiment deliberately includes both certified and challenging uncertified trajectories.

Reviewer_tCGQOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers a version of the Best arm identification problem, where the arms vary temporally, in that their means evolve with time. They create an algorithm, Sign-COUNT SH, which they prove returns the best arm with high probability under sufficient budget. Subsequently, they show a mimimax lower bound, hence demonstrating that their algorithm is minimax-optimal.

Critical strengths

a) Its setting, which is novel in the combination of its components (no single component is new, in and of itself).

b) The creation of a minimax-optimal algorithm with an extensive, rigorous analysis and a number of extensions in the appendix.

c) the practical and synthetic experiments.

Critical weaknesses

I do not find any significant weaknesses in the paper, apart from some typographical errors.

Questions for authors

a) The size of the quantity HNSδH^{\delta}_{NS} should really be mentioned for simple cases e.g. where the μi\mu_i are all the same, or when the μi\mu_i themselves come from some i.i.d distribution. Right now, I don't know how to judge how big or small it is in general.

b) There is a necessity to talk about instance-specific optimality i.e. situations where the μi\mu_i are not distributed as per the hard instance contributing to the minimax lower bound, but in some other more natural manner that might be occurring in the literature. There, simpler algorithms may yield optimal algorithms in comparison to Algorithm 2.

c) Please confirm these minor typos :

•⁠ ⁠Definition 1 should have ∑i=1kj\sum_{i=1}^{k_j} in place of ∑i=1j\sum_{i=1}^j in the definition of dˉ\bar{d}. •⁠ ⁠⁠Definition 2 should have Wa,b=(1+sa,b)/2W_{a,b} = (1+s_{a,b})/2 in place of sa,bs_{a,b}

d) I think, as B/K increases, you should have some confirmation of better algorithm performance: this isn't clear enough in the experiments, where B/K seems more of a hyperparameter than a quantity which should give your algorithm more time to improve. Can your algorithm adapt to B/K in some way and improve itself to give steadily better performance with B/K?

1 comment
AuthorsOpenReview ↗

Response to Reviewer tCGQ

1. Interpreting the magnitude of HNS(δ)H_{\mathrm{NS}}^{(\delta)}

We thank the reviewer for this suggestion. A deterministic one-jump family acts as an instructive example for understanding the magnitude of our complexity measure. Please see Definition 1 for notations not defined here.

Setup. Set ϵ=0\epsilon=0 in the complexity measure, which corresponds to exact BAI. Suppose there is a unique target-time best arm and 0=Δ1<Δ2≤⋯≤ΔK0=\Delta_1 \lt \Delta_2\le\cdots\le\Delta_K. Let H2=max⁡i≥2i/Δi2H_2=\max_{i\ge 2} i/\Delta_i^2 be the standard complexity measure for the stationary BAI problem. For simplicity, consider piece-wise constant reward signals that has a changepoint at a (dyadic) T0T_0:

μa(s)=θa(1≤s≤T0),μa(s)=γθa(s>T0).\mu_a(s)=\theta_a \quad (1\le s\le T_0), \qquad \mu_a(s)=\gamma\theta_a \quad (s \gt T_0).

For a pair with positive terminal gap da,b(1):=μa(1)−μb(1)d_{a,b}(1) := \mu_a(1) - \mu_b(1),

Γa,b(k)=da,b(1)(k≤T0),Γa,b(k)=da,b(1)(γ+(1−γ)T0k)(k>T0).\Gamma_{a,b}(k)=d_{a,b}(1) \quad (k\le T_0), \qquad \Gamma_{a,b}(k)=d_{a,b}(1)\left(\gamma+(1-\gamma)\frac{T_0}{k}\right) \quad (k \gt T_0).

Resulting scale of the complexity (all statements suppress the log factors present in Corollary 7):

  • γ=1\gamma=1 (stationary): HNS(δ)≲K+σ2H2H_{\mathrm{NS}}^{(\delta)}\lesssim K+\sigma^2H_2, recovered by Corollary 7.
  • γ>1\gamma \gt 1 (history preserves and amplifies the gaps): K+σ2H2/γ2≲HNS(δ)≲K+σ2H2K+\sigma^2H_2/\gamma^2 \lesssim H_{\mathrm{NS}}^{(\delta)} \lesssim K+\sigma^2H_2.
  • 0<γ<10 \lt \gamma \lt 1 (history preserves but attenuates the gaps): K+σ2H2≲HNS(δ)≲K+σ2H2/γ2K+\sigma^2H_2 \lesssim H_{\mathrm{NS}}^{(\delta)} \lesssim K+\sigma^2H_2/\gamma^2.
  • γ≤0\gamma\le 0 (history eventually erases (γ=0\gamma=0) or reverses (γ<0\gamma \lt 0) the target ordering): if the needed ranking certificates are obtained before T0T_0, the complexity remains at the stationary scale; otherwise HNS(δ)H_{\mathrm{NS}}^{(\delta)} is infinite.

This example shows how HNS(δ)H_{\mathrm{NS}}^{(\delta)} reflects whether historical observations strengthen, weaken, erase, or contradict the target-time ordering relative to the evidence needed to resolve it. We will add this discussion to make the scale of the complexity more transparent.


2. Instance-specific optimality

We agree that class-level minimax optimality should be distinguished from instance-specific optimality. Theorem 8 proves near-minimaxity over the class defined by bounded HNS(δ)H_{\mathrm{NS}}^{(\delta)}; we do not claim Algorithm 2 is optimal for every individual trajectory or every more structured subclass. If additional temporal structure is known (e.g., smoothness, parametric drift, periodicity, or changepoints), specialized algorithms may obtain sharper guarantees and may also be simpler.

That said, our upper bound already has an instance-adaptive aspect. Theorem 5 scales with the realized complexity HNS(δ)(θ,ϵ)H_{\mathrm{NS}}^{(\delta)}(\theta,\epsilon), which depends on the actual pairwise resolving and ranking depths of the instance. Algorithm 2 does not require these depths, the drift pattern, or ϵ\epsilon as inputs. The multiresolution test adaptively selects the first temporal scale providing sufficient sign evidence. This adaptivity should be distinguished from the stronger notion of instance-optimality raised by the reviewer (e.g., matching the best algorithm that knows the drift structure), which we do not claim.

We acknowledge this distinction in the paper. The Conclusion section identifies "developing sharper adaptive instance-dependent algorithms" as an important future direction. We will make this scope distinction more prominent in the revision.


3. Performance as a function of B/KB/K

We respectfully disagree that increasing B/KB/K must monotonically improve empirical performance in target-time non-stationary BAI. A larger budget expands the temporal depths available to Multi-Resolution-Duel. Comparisons already resolved at shallow depths are unaffected. The main benefit is that previously unresolved pairs can access deeper prefixes thereby improving their chance of resolvability.

Whether this helps depends strongly on the adversarial nature of (population-level) gap trajectories. A deeper prefix can correctly resolve a previously unresolved pair and improve the final SignCount ranking, but under deceptive drift it can instead confidently resolve to the wrong terminal sign and hurt performance. Thus, larger B/KB/K increases the opportunity to resolve difficult pairs, not a guarantee of higher identification probability.

This rationale is reflected in the synthetic study around Fig. 3 and Appendix G. Fig. 7 shows that the final-pair sign-resolution probability increases from about 0.350.35 to 0.990.99 as B/KB/K grows, confirming that larger budgets make previously unresolved comparisons resolvable. Whether those new resolutions help depends on whether the newly accessible historical prefixes preserve or distort the target-time ordering. Their combined effect essentially leads to the plot in Fig. 3.


4. Typos

Thank you for pointing these out. We will fix them in the revision.

Reviewer_uHsbOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This paper studies fixed-budget best-arm identification in non-stationary environments, with the goal of identifying the best arm at a target time without prior knowledge of the drift magnitude. The authors propose a drift-adaptive algorithm that balances estimation variance and bias, and establish near-optimal guarantees up to polylogarithmic factors. The proposed algorithm is evaluated on both synthetic and real-world datasets.

Critical strengths
  1. The problem studied in this paper is well-motivated and has clear practical relevance. Identifying the best arm at a target time under a limited query budget reflects real-world scenarios where one must use potentially biased historical observations to determine the best choice at a specific time.

  2. The proposed algorithm has some novelty, combining multiresolution pairwise sign estimation with the elimination structure of Sequential Halving. The paper also establishes a regret upper bound and a corresponding lower bound for the problem.

Critical weaknesses
  1. The nontrivial guarantee in Theorem 5 relies on finite resolving and ranking depths, which are not guaranteed for arbitrary non-stationary reward sequences. In particular, if a shorter window strongly favors an incorrect ranking, the corresponding resolving depth may still be infinite, even if a longer window recovers the correct ranking. Thus, the theoretical guarantee only applies to instances with certain identifiability properties. The paper does not sufficiently characterize which natural classes of non-stationary processes satisfy these conditions.

  2. Theorem 8 establishes that the algorithm is minimax optimal up to logarithmic factors over the complexity class defined by HNS(δ)H_{\mathrm{NS}}^{(\delta)}, which is a valid theoretical result. However, the lower-bound proof does not seem to account for ranking reversals, which the paper emphasizes as an important feature of the problem. The authors should clarify the scope of the optimality claim in this regard.

Questions for authors
  1. Could the authors further characterize a natural class of non-stationary reward processes for which HNS(δ)H_{\mathrm{NS}}^{(\delta)} is finite and meaningful? Are there instances where the resolving depth is infinite, but other algorithms that exploit temporal structure can still effectively identify the best arm at the target time?

  2. Could the authors discuss whether HNS(δ)H_{\mathrm{NS}}^{(\delta)} still captures the information-theoretic sample complexity for instances with significant ranking reversals?

3 comments
AuthorsOpenReview ↗

Response to Reviewer uHsb (1/2)

1. A natural class of non-stationarity with finite HNS(δ)H_{\mathrm{NS}}^{(\delta)}

We thank the reviewer for this question. Please refer to Definition 1 for notation.

A natural class of non-stationarity where the complexity measure is finite can be obtained by considering the class of gap trajectories that are locally Lipschitz. We make this precise below.

For a pair (a,b)(a,b) with unequal terminal means, let da,b(1)=μa(1)−μb(1)d_{a,b}(1)=\mu_a(1)-\mu_b(1). Using the kjk_j observations closest to the target time, suppose the prefix-average bias is bounded by a non-decreasing envelope

∣dˉa,b(kj)−da,b(1)∣≤ba,b(kj).\lvert \bar d_{a,b}(k_j)-d_{a,b}(1) \rvert \le b_{a,b}(k_j).

One natural choice is:

ba,b(k)=max⁡1≤m≤k1m∑t=1m∣da,b(t)−da,b(1)∣.b_{a,b}(k)=\max_{1\le m\le k}\frac{1}{m}\sum_{t=1}^{m}\lvert d_{a,b}(t)-d_{a,b}(1) \rvert.

The stochastic term is controlled by 3qj(δ)=O~(kj−1/2)3q_j(\delta)=\widetilde O(k_j^{-1/2}). Hence, a simple sufficient condition for finite complexity is that every pair with unequal terminal means satisfies:

∣da,b(1)∣>min⁡j{ba,b(kj)+3qj(δ)}.\lvert d_{a,b}(1) \rvert \gt \min_j \lbrace b_{a,b}(k_j)+3q_j(\delta) \rbrace.

Intuitively, every pair must admit some temporal window where the terminal signal dominates the best attainable bias-variance tradeoff.

Example (locally Lipschitz gaps). If the pairwise gap is locally Lipschitz up to a (pair-dependent) changepoint k0k_0,

∣da,b(t)−da,b(1)∣≤La,b(t−1),t≤k0,\lvert d_{a,b}(t)-d_{a,b}(1) \rvert \le L_{a,b}(t-1), \qquad t\le k_0,

then the above envelope satisfies ba,b(k)≤La,b(k−1)/2b_{a,b}(k)\le L_{a,b}(k-1)/2, so it suffices that some dyadic kj≤k0k_j\le k_0 satisfies

∣da,b(1)∣>La,b(kj−1)2+3qj(δ).\lvert d_{a,b}(1) \rvert \gt \frac{L_{a,b}(k_j-1)}{2}+3q_j(\delta).

  • Neither La,bL_{a,b} nor the changepoint location k0k_0 is needed by the algorithm. Further k0k_0 can be different for different pairs.
  • This class can still permit localized instantaneous ranking reversals when their magnitude/duration is limited.
  • The condition is only sufficient, and is stronger than necessary.

Special case (finitely many switches). Gap trajectories that switch value finitely many times are a special case: if the final segment (the one containing the target time) has length k0k_0, then da,b(t)=da,b(1)d_{a,b}(t)=d_{a,b}(1) for t≤k0t\le k_0, i.e., La,b=0L_{a,b}=0. The condition reduces to ∣da,b(1)∣>3qj(δ)\lvert d_{a,b}(1) \rvert \gt 3q_j(\delta) for some dyadic kj≤k0k_j\le k_0, so the final segment only needs to be sufficiently long. The number and locations of the switching points need not be known to the algorithm a-priori.

We will add this concrete characterization in the revision.

AuthorsOpenReview ↗

Response to Reviewer uHsb (2/2)

2. Why a later "recovery" cannot always be selected

We agree that there can be cases where shorter window can strongly favor the wrong terminal ordering while a longer window later recovers the correct one. Without additional temporal structure, however, such a recovery cannot be recognized uniformly -- if two scales support conflicting orderings, the learner has no principled basis for knowing which scale is more representative of the target time. The apparent recovery is only identifiable in hindsight.

This limitation is already noted in Sec. 3.1 (cf. around Line 151). We explicitly state that strongly adversarial drift modes can yield an incorrect sign resolution, and Definition 4 formalizes the class where non-trivial guarantees are possible.

Can an instance with infinite resolving depth still be solvable by another algorithm? Yes, if additional structure is available, e.g., known smoothness, parametric drift, periodicity, or known changepoints. Our setting deliberately assumes none of this structure. Designing algorithms that exploit such optimistic structural hints when available, while degrading gracefully when they are inaccurate, is an interesting direction for future work for the setting we introduce in this paper.


3. Ranking reversals and the lower bound

We would like to remark that Theorem 8 is a class-level minimax result as the reviewer correctly noted; it does not claim that HNS(δ)(θ,ϵ)H_{\mathrm{NS}}^{(\delta)}(\theta,\epsilon) is the exact instance-wise information-theoretic complexity of every trajectory. For

Θh={θ:HNS(δ)(θ,ϵ)≤h},\Theta_h=\lbrace \theta : H_{\mathrm{NS}}^{(\delta)}(\theta,\epsilon)\le h \rbrace,

a minimax lower bound only needs a hard subclass Θhard⊆Θh\Theta_{\mathrm{hard}}\subseteq\Theta_h. Thus the constructed hard instance need not exhibit every phenomenon in the full class.

Nevertheless, the lower-bound argument itself does not rely on ranking stability. To see this, modify the hard family so that under alternative θi\theta_i,

μi(1)=2ϵ,μi(s)=ηξs(s≥2),\mu_i(1)=2\epsilon, \qquad \mu_i(s)=\eta\xi_s \quad (s\ge 2),

all other arms have mean zero, and

(ξ2,ξ3,ξ4,ξ5,ξ6,ξ7,…)=(+1,+1,−1,+1,+1,−1,…).(\xi_2,\xi_3,\xi_4,\xi_5,\xi_6,\xi_7,\ldots)=(+1,+1,-1,+1,+1,-1,\ldots).

Arm ii now undergoes arbitrarily many ranking reversals. Under Gaussian noise, either +η+\eta or −η-\eta contributes the same KL divergence η2/(2σ2)\eta^2/(2\sigma^2) from the all-zero null, so reversals do not make individual observations more informative. Moreover,

∑s=2kξs≥k−13,\sum_{s=2}^{k}\xi_s\ge\frac{k-1}{3},

so the prefix-averaged gap dˉi,a(k)\bar d_{i,a}(k) remains a constant multiple of η\eta for every k≥2k\ge 2. Hence the resolving-depth and HNS(δ)H_{\mathrm{NS}}^{(\delta)} scalings are unchanged up to constants, while the hard instances now contain repeated reversals.

The same lower-bound intuition explained in Sec. C.2 carries over verbatim for this new construction: the terminal sample supplies only O(ϵ2/σ2)O(\epsilon^2/\sigma^2) information and each historical sample only O(η2/σ2)O(\eta^2/\sigma^2) information, so high-confidence identification still requires accumulating many weak observations. We will emphasize in the manuscript that Theorem 8 is not an instance-wise lower bound for every severely deceptive trajectory.

Thanks for the author's reply. The authors' reply resolved the issue I raised. I choose to keep the score unchanged, but increase the soundness score from 2 to 3.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.