acceptodds
Under review as a conference paper at ICLR 2027

Rising Multi-Armed Bandits with Known Horiozons

20 views

Abstract

Rising Multi-Armed Bandits (RMABs) model sequential decision problems where each arm's expected reward improves with repeated pulls. In such problems, the value of investing in an arm depends on how much time remains, making knowledge of the horizon useful side information, yet its benefit remains underexplored. We investigate this benefit through CURE-UCB, a horizon-aware algorithm that estimates each arm's cumulative reward over the remaining horizon. Theoretically, under structured assumptions, we prove that CURE-UCB uniformly dominates a representative horizon-agnostic algorithm and show that the advantage of horizon awareness can be substantial: on some instances, CURE-UCB incurs only regret whereas the horizon-agnostic algorithm suffers . Furthermore, we establish a regret upper bound for the general concave rising bandit setting whose growth-dependent term matches the known lower bound in its dependence on . Empirically, across synthetic benchmarks and real-world model selection tasks, CURE-UCB achieves lower regret than both rising and non-stationary baselines over a wide range of horizons.

Primary area:
learning on time series and dynamical systems
Keywords:
Multi armed bandit, model selection

Reviews

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

This paper studies the model of rising bandits where arm mean rewards are monotonic and concave in the number of pulls. In this model, the benchmark clairvoyant optimal policy is naturally horizon-dependent, balancing growth potential with remaining horizon. However, the existing bandit algorithm for this setting due to Metelli et al. (2022), called R-ed-UCB, is horizon-agnostic, a potential reason being that horizon-dependence is immaterial to worst-case regret optimality. The present paper proposes a natural horizon-dependent variant that (a) achieves essentially the same worst-case regret bound, (b) dominates R-ed-UCB on the class of deterministic linear-then-flat (LTF) instances with a potentially linear dominance gap, and (c) obtains better empirical performance.

Critical strengths
  1. The rising bandits model is an interesting and practically useful model of non-stationary bandits. The proposed index is better aligned with the finite-horizon cumulative-reward objective than the extrapolation used by R-ed-UCB. This is a simple but meaningful improvement to an established algorithm.

  2. The paper is generally well-written and situates its findings in the context of the literature very well. The empirical findings clearly support the contribution.

Critical weaknesses
  1. While the paper presents a practically meaningful algorithmic advancement, its technical advancement is limited. The worst-case regret guarantee is essentially the same as Metelli et al. (2022). The theoretical advantage of the policy is established only for deterministic LTF instances.

  2. Broadly, the theoretical analysis and bounds do not sufficiently highlight the general sense in which the practical improvement to the policy translates to improved performance. Clearly, worst-case regret rate is not the right benchmark here as already R-ed-UCB achieved the optimal worst-case dependence on T.

  3. There are other considerations that remain open. On fixed stochastic LTF instances with positive limiting reward gaps, logarithmic asymptotic regret should be achievable. However, it seems that CURE-UCB does not achieve this bound since its confidence blow-up is order T rather than order sqrt{log T}. So it remains unclear if there is a policy that attains both optimal instance-dependent as well as worst-case rates even for the class of stochastic LTF instances.

Questions for authors
  1. Can Theorem 5.2 be extended beyond deterministic LTF instances? Even a characterization of conditions under which CURE-UCB improves on R-ed-UCB would strengthen the theoretical contribution. At the very least, is there an extension to stochastic LTF rewards?

  2. Clearly, worst-case regret rate is not the right benchmark, but is there any other evidence of improved performance in the derived bound?

  3. Would it be possible to attain both optimal instance-dependent as well as worst-case rates for the class of stochastic LTF instances? This is less critical as it is beyond the scope of the current investigation, but could strengthen the technical contribution of the paper.

4 comments

Dear Reviewer yX2j, Thank you for your thoughtful review and insightful questions. We have carefully considered your suggestions and incorporated additional theoretical results and discussions into the revised manuscript. We would greatly appreciate your consideration of these updates. We provide detailed responses to your questions below.


Q1, W1. Scope and Strength of Uniform Dominance

We acknowledge that the uniform dominance in Theorem 5.2 is sensitive to its assumptions. To illustrate this limitation, we provide a two-arm counterexample showing that the guarantee can fail when nonzero intercepts are allowed:

\mu_1(n) &= \min(0.73,,0.49+0.12n),\\\\ \mu_2(n) &= \min(0.82,,0.34+0.16n). \end{aligned}$$ At $T=6$, after two initial pulls per arm, CURE-UCB selects each arm 3 times, whereas R-ed-UCB selects arms 1 and 2 a total of 2 and 4 times, respectively. Consequently, CURE-UCB incurs regret $0.39$, while R-ed-UCB incurs $0.30$, violating uniform dominance. We would like to emphasize that Theorem 5.2 provides a strong guarantee: CURE-UCB achieves no larger regret than R-ed-UCB on every instance in the specified class and for every finite horizon. The deterministic zero-intercept LTF assumptions allow us to isolate the difference between CURE-UCB's remaining-horizon cumulative reward estimation and R-ed-UCB's surrogate objective. The proof shows how this difference can prevent unnecessary exploration whose gains cannot compensate for its cost before the horizon. We expect such uniform dominance to be fragile under stochastic rewards, as observation noise could alter arm selections and reverse the regret comparison at certain horizons. Extending this guarantee may therefore require additional assumptions or a weaker form of dominance. --- # Q2, W2. Theoretical Benefits of Horizon Awareness We agree that worst-case regret rates alone may not fully capture the benefit of horizon awareness. This motivated our analysis in Theorem 5.2 and Proposition 5.3, which directly compare the algorithms' actual regret and show that CURE-UCB can incur $O(1)$ regret where R-ed-UCB incurs $\Omega(T)$. As discussed in Q1, uniform dominance is a strong guarantee under restrictive assumptions. To further characterize the benefit of horizon information, we introduce Proposition 5.4, establishing a separation against every horizon-agnostic policy: > **Proposition 5.4 (Benefit of Horizon Awareness).** > > For every fixed $K \geq 2$ and every integer $c \geq 256K$, there exists a deterministic LTF instance $\mu_c \in \mathcal{U}_K$ such that, for any horizon-agnostic policy $\pi$, with > > $$> \mathcal{T}_c = \left\\{ \left\lfloor \frac{c}{2} \right\rfloor, 2c \right\\}, >$$ > > the following statements hold: > > **(i) CURE-UCB:** $\max_{T \in \mathcal{T}_c} \operatorname{Reg}_{\mu_c}(\pi_0^{\mathrm{cure}}, T) \leq 4(K-1)$. > > **(ii) Any horizon-agnostic policy:** $\max_{T \in \mathcal{T}_c} \operatorname{Reg}_{\mu_c}(\pi, T) \geq c/64$. Unlike Theorem 5.2, this result does not require dominance on every instance and every horizon. Instead, it establishes a separation over two horizons on a single LTF instance, while extending the comparison to *any arbitrary horizon-agnostic policy*.. The two horizons require conflicting early investments, demonstrating a benefit of horizon information beyond any particular baseline. --- # Q3, W3. Instance-Dependent Regret in Stochastic LTF We agree that logarithmic instance-dependent regret is achievable in stochastic LTF settings with positive limiting reward gaps. For instance, if saturation times are known or are constants, we can design a simple policy; select each arm until saturation and then apply a standard stationary bandit algorithm like UCB or Thompson sampling. However, CURE-UCB is designed for general concave rising rewards, and its exploration bonus does not explicitly exploit the finite-time saturation structure of LTF rewards. Thus, our current analysis does not establish logarithmic regret in this setting. Developing an adaptive algorithm that achieves logarithmic regret on fixed LTF instances while retaining the general concave regret guarantee is an interesting direction for future work.

Dear Reviewer yX2j,

Thank you again for your feedback. Following up on our rebuttal, we would like to clarify one point about your question on worst-case and problem-dependent regret. Even when the horizon is known, the worst-case regret over LTF instances is Ω(T)\Omega(T). This follows from a simple adaptation of the construction in the proof of Proposition 5.4. Since bounded rewards give every policy a matching O(T)O(T) worst-case upper bound over the LTF class, an interesting open question is under what additional assumptions a single policy can achieve both a sharper worst-case bound and an instance-dependent regret bound.

As the author–reviewer discussion deadline (Nov. 18) approaches, we would appreciate your consideration of our rebuttal and additional results. If you have any remaining questions or would like us to clarify any part of the revision, we would be happy to respond before the deadline.

I thank the authors for engaging meaningfully with my comments. I appreciate the acknowledgment of the limitations of what can be formally said about CURE-UCB and the difficulty of extending beyond deterministic LTF instances. I also appreciate the further sharpening of the benefit of horizon awareness in LTF instances.

Having said that, my main concern remains. While this is a meaningful practical improvement of a bandit policy, limitations in originality and what can be theoretically said about the proposed policy put it slightly below the bar for me. I would hence maintain my score.

Dear Reviewer yX2j,

Thank you for your thoughtful follow-up. We understand your remaining concerns regarding originality and theoretical analysis, and would like to clarify one point about the distinction between our work and Metelli et al. (2022).

We emphasize that although CURE-UCB and R-ed-UCB have similar index structures, they are designed to estimate fundamentally different objectives. R-ed-UCB extrapolates the expected reward at a single future point, whereas CURE-UCB estimates the cumulative reward obtainable over the remaining horizon. This distinction is central to our algorithm design and its originality, as we derive the index from the finite-horizon optimality criterion rather than simply modifying the index of R-ed-UCB.

This distinction also carries over to the analysis. Since both methods are UCB-based algorithms, we acknowledge that our proof follows a similar general structure on Metelli et al. (2022). However, the different estimators require distinct analytical arguments. In particular, equations (98)–(113) in Appendix F establish a bound for an estimation discrepancy arising specifically from our remaining-horizon estimator, which does not appear in the other analysis including Metelli et al. (2022).

We hope these clarifications better convey the originality of our algorithm and theoretical analysis, and we would be grateful if you could reconsider your assessment.

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

This paper studies rising multi-armed bandits with a known horizon. In this setting, each arm’s expected reward increases with the number of times it is selected, with non-increasing marginal improvements. The objective is to maximize cumulative reward over a finite horizon TT. Since an arm with high initial reward may be preferable for a short horizon while a slower-starting arm may become preferable for a longer horizon, knowledge of TT can affect the optimal decision.

The authors propose CURE-UCB, an algorithm that combines a recent average reward, an estimated growth rate weighted by the remaining horizon, and an exploration bonus. In the deterministic linear-then-flat setting, they prove that CURE-UCB has no larger regret than R-ed-UCB under the specified algorithm configurations. They also construct instances where CURE-UCB incurs O(1)O(1) regret while R-ed-UCB incurs Ω(T)\Omega(T) regret. For general stochastic concave rising rewards, the paper provides a regret bound involving cumulative reward increments and a stochastic term of order O~(Kϵ(σT)2/3)\widetilde O \left (\frac{K}{\epsilon}(\sigma T)^{2/3} \right ). Experiments evaluate the algorithm on synthetic instances, IMDB model selection, and an offline replay environment derived from LLM fine-tuning trajectories.

Critical strengths
  1. The paper studies a meaningful finite-horizon decision problem. In rising bandits, selecting an arm is also an investment in its future performance, and the value of this investment depends on the remaining time. The paper clearly explains why the same reward functions can favor different arms at different horizons. Incorporating this information into arm selection is therefore a well-motivated objective.

  2. The deterministic analysis provides a direct comparison between algorithms rather than only comparing their regret upper bounds. Theorem 5.2 establishes uniform dominance over R-ed-UCB within the specified linear-then-flat class, while Proposition 5.3 shows that the difference can be linear in the horizon. These results provide concrete evidence that the proposed decision rule can substantially improve performance in this structured setting.

  3. The experimental evaluation covers several complementary settings and a broad collection of baselines. The authors evaluate different horizons, report pairwise win rates in addition to cumulative regret, and include both synthetic problems and model-selection tasks. The additional experiments on window size and observation noise also help assess the sensitivity of CURE-UCB. The reported results are consistently encouraging across the evaluated environments.

Critical weaknesses
  1. The theoretical comparison has a narrower scope than the general motivation of quantifying the benefit of horizon awareness. The dominance theorem applies to deterministic reward functions of the form μi(n)=min⁡{bi,ain}\mu_i(n)=\min\{b_i,a_i n\}, with zero intercept, integer saturation time, and unit windows. It does not establish dominance under stochastic rewards or general concave curves. Moreover, the comparison is against one particular horizon-agnostic algorithm, R-ed-UCB, rather than the best possible horizon-agnostic policy. Thus, the result demonstrates an advantage of the proposed algorithm in a structured setting, but does not fully characterize the general value of knowing the horizon.

  2. The interpretation of the proposed index as an upper confidence bound on remaining cumulative reward requires clarification. Equations (9)–(10) use the current mean reward to obtain an upper bound, whereas Equation (6) replaces this quantity with an average of earlier observations without explicitly correcting for their age. For a linear reward segment μ(n)=an\mu(n)=an, after nn observations with window size h>1h>1 and RR rounds remaining, the true average reward from committing to the arm is a(n+R+12).a\left(n+\frac{R+1}{2}\right). However, the mean of the estimator before adding the exploration bonus is a(n−h−12+R+12),a\left(n-\frac{h-1}{2}+\frac{R+1}{2}\right), which underestimates the target by a(h−1)/2a(h-1)/2. The exploration bonus controls statistical uncertainty but does not automatically correct this bias. This observation does not by itself invalidate Theorem 5.5, whose proof separately controls estimation discrepancies, but it weakens the stated optimism interpretation of the index.

  3. The LLM experiment relies on substantial offline processing of the measured reward trajectories. Appendix B.2 applies smoothing, accumulated cost penalties, post-peak capping, fixed Gaussian perturbations, and normalization before replay. In particular, replacing the trajectory after its global maximum with a constant does not eliminate decreases before that maximum, and the subsequent perturbation can introduce additional decreases. Therefore, the stated procedure does not guarantee monotonicity or concavity. Moreover, selecting the global peak retrospectively does not demonstrate that an online learner can identify the corresponding stopping point. Although evaluating beyond the theoretical assumptions is reasonable, results on raw trajectories and preprocessing ablations are needed to better establish the practical significance of the reported improvements.

Questions for authors
  1. Can the dominance guarantee be extended to linear-then-flat curves with nonzero intercepts or stochastic rewards? If not, can the authors identify examples where the dominance fails?

  2. Can the authors distinguish more explicitly between outperforming R-ed-UCB and establishing the general benefit of horizon knowledge? Is a separation between horizon-aware and horizon-agnostic policy classes possible?

  3. How should the downward bias introduced by the recent-average term be reconciled with the upper-confidence-bound interpretation of Equation (6)? Would adding a correction for the age of the observations preserve the theoretical guarantees and empirical performance?

  4. Can the authors report results on raw LLM reward trajectories and ablate the preprocessing steps, particularly peak-capping and fixed perturbations? How would the stopping decision represented by peak-capping be implemented without access to future rewards?

4 comments

Dear Reviewer kLCV, thank you for your thoughtful review and valuable suggestions for improving our paper. Your comments have been very helpful in strengthening our work.. While some revisions are still in progress, we would like to share the update so far and provide detailed responses to your questions below. We would greatly appreciate your consideration of these updates.


Q1, W1. Limitations of Uniform Dominance

The uniform dominance in Theorem 5.2 does not generally extend to LTF curves with nonzero intercepts. We provide a counterexample with two arms:

\mu_1(n) &= \min(0.73,,0.49+0.12n),\\\\ \mu_2(n) &= \min(0.82,,0.34+0.16n). \end{aligned}$$ At $T=6$, after two initial pulls per arm, CURE-UCB selects each arm 3 times, whereas R-ed-UCB selects arms 1 and 2 a total of 2 and 4 times, respectively. Consequently, CURE-UCB incurs regret $0.39$, while R-ed-UCB incurs $0.30$, violating uniform dominance. Uniform dominance is a particularly strong guarantee, requiring CURE-UCB to achieve no larger regret than R-ed-UCB on every instance in the specified class and for every finite horizon. We carefully chose the deterministic zero-intercept LTF setting to isolate the effect of the decision objective. Under these assumptions, CURE-UCB uses the known horizon to construct an estimate aligned with the exact finite-horizon objective, whereas R-ed-UCB relies on a surrogate that extrapolates reward at a single future point. The proof of Theorem 5.2 shows how this mismatch can lead R-ed-UCB to explore additional arms whose gains cannot compensate for their exploration cost before the horizon. While these assumptions are restrictive, they allow us to establish a strong uniform dominance guarantee. --- # Q2, W1. Value of horizon information We agree that extending the comparison beyond R-ed-UCB would further strengthen our characterization of the benefit of horizon information. To this end, we introduce Proposition 5.4, which establishes a separation between CURE-UCB and arbitrary horizon-agnostic policy: > **Proposition 5.4 (Benefit of Horizon Awareness).** > > For every fixed $K \geq 2$ and every integer $c \geq 256K$, there exists a deterministic LTF instance $\mu_c \in \mathcal{U}_K$ such that, for any horizon-agnostic policy $\pi$, with > > $$> \mathcal{T}_c = \left\\{ \left\lfloor \frac{c}{2} \right\rfloor, 2c \right\\}, >$$ > > the following statements hold: > > **(i) CURE-UCB:** $\max_{T \in \mathcal{T}_c} \operatorname{Reg}_{\mu_c}(\pi_0^{\mathrm{cure}}, T) \leq 4(K-1)$. > > **(ii) Any horizon-agnostic policy:** $\max_{T \in \mathcal{T}_c} \operatorname{Reg}_{\mu_c}(\pi, T) \geq c/64$. The key insight is that the same reward curves require conflicting early investments under different horizons. Without knowing the horizon, a policy cannot adapt its initial allocation to both budgets, while CURE-UCB achieves bounded regret at both. Unlike Proposition 5.3, which compares CURE-UCB with R-ed-UCB, Proposition 5.4 establishes a separation against every horizon-agnostic policy, including randomized policies. Thus, the benefit of horizon information is not specific to R-ed-UCB but applies to the *entire horizon-agnostic policy class* on the constructed instance.

Q3, W2. Recent-average bias and the UCB interpretation

Thank you for pointing out this bias. We agree that the reward estimator should account for the age of observations. We will incorporate this correction into CURE-UCB and update the corresponding theoretical analysis and experiments, aiming to share the revised results before the review period ends. To address the bias, we can consider the following corrected index:

μ^i(t)=1h∑ℓ=n−h+1n[Xi(ℓ)+(T−t+22+n−ℓ)Xi(ℓ)−Xi(ℓ−h)h]\boxed{\hat{\mu}_i(t) = \frac{1}{h} \sum_{\ell=n-h+1}^{n} \left[ X_i(\ell) + \left(\frac{T-t+2}{2} + n - \ell\right) \frac{X_i(\ell) - X_i(\ell-h)}{h} \right]} where n=Ni,t−1n=N_{i,t-1} and h=hih=h_i. The additional term n−ℓn-\ell corrects the sliding window bias identified by the reviewer. Our preliminary theoretical analysis suggests that this correction does not change the order of the regret bounds, and our initial experiments show no substantial change in empirical performance. Nevertheless, we believe that the corrected estimator better reflects our intended intuition and provides a clearer interpretation of the algorithm. We thank the reviewer again for this valuable observation.


Q4, W3. Preprocessing and online stopping

We agree with the reviewer that our preprocessing does not guarantee monotonicity or concavity. Our intention was to approximate practical fine-tuning dynamics, rather than strictly enforce the theoretical assumptions. We apologize for the ambiguity in our previous description and have clarified this distinction in Appendix A.2. To examine the effect of preprocessing, we conducted additional experiments on raw LLM reward trajectories and three preprocessing variants (Appendix K.3). Specifically, we compare (i) raw trajectories, (ii) smoothing only, (iii) smoothing with cost penalties and peak-capping, and (iv) the full preprocessing pipeline. All experiments use T=1KT=1K, 50 random seeds, and the same observation-noise setting.

Table 1. Effect of reward-trajectory preprocessing on LLM selection performance.

PreprocessingCURE-UCB (ours)R-ed-UCBSW-UCB
Raw trajectory145.02 ± 0.00448.79 ± 0.20324.85 ± 0.05
Smoothing only212.24 ± 0.09432.51 ± 5.13318.30 ± 0.10
Smoothing + cost penalty + peak-capping151.45 ± 0.08308.39 ± 7.99201.46 ± 0.02
Full preprocessing (main-reference)207.95 ± 0.13271.14 ± 0.08314.68 ± 0.07

(We have updated this table after correcting the bias of sliding-window.)

CURE-UCB achieves the lowest expected regret in all four environments, including the raw trajectories. These results demonstrate that its empirical advantage persists without the retrospective peak-capping or fixed perturbations used in the original experiment.

Regarding online stopping, peak-capping is intended to approximate early stopping in practical fine-tuning, where training is terminated once performance has sufficiently converged. For simplicity, our offline simulation identifies the stopping point retrospectively using the maximum reward. In practice, an online stopping criterion could instead monitor recent reward improvements and terminate training when the improvement rate falls below a predefined threshold.

Dear Reviewer kLCV,

Thank you again for pointing out the sliding-window bias in the CURE-UCB index. Following up on our initial response, we have implemented your suggested correction, revised the proof, and rerun all four main experiments. We have uploaded the revised manuscript with these updates.

In equation (6), we now account for the number of times an arm has been selected since each observation. This removes the downward bias you identified on linear reward segments. We also revised the exploration bonus and its analysis. For the corrected index, Theorem 5.6 retains the original coefficient of the growth-dependent term and the order of the stochastic term (Appendices F and H).

The table compares mean cumulative regret before and after the correction. Lower values are better.

SettingHorizonOriginal CURE-UCBCorrected CURE-UCBChange
Concave100K4,611.534,327.86−6.15%
LTF100K7,564.617,702.99+1.83%
IMDB50K2,256.422,273.59+0.76%
XSum-LLM1K216.74220.14+1.57%

Overall, the results were similar to those obtained with the original index. The largest change was in the concave setting, where the correction reduced mean cumulative regret by 6.15%. In each of the other three settings, mean cumulative regret increased by less than 2%.

As the author–reviewer discussion deadline (Nov. 18) approaches, we would appreciate your consideration of our rebuttal and additional results. If you have any remaining questions or would like us to clarify any part of the revision, we would be happy to respond before the deadline.

Dear Reviewer kLCV,

As the author–reviewer discussion deadline is only a few hours away, we would like to kindly follow up on our rebuttal. We have carefully addressed your concerns through additional theoretical analysis and experiments, including correcting the CURE-UCB index as you suggested, and conducting additional ablation studies. All these updates have been incorporated into the revised manuscript.

We would greatly appreciate it if you could consider our responses and revised results before the discussion closes. If these updates have addressed your concerns, we would be grateful if you could reconsider your assessment.

Thank you again for your time and constructive feedback.

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

The paper propose and algorithm for sequential allocation problems (MABs), where arms improve as they are pulled. The proposed CURE-UCB algorithm uses the remaining horizon to estimate the reward obtainable by committing to an arm. The paper presents three theoretical results:

  1. CURE-UCB performs at least as well as R-ed-UCB in deterministic settings where rewards increase linearly and then level off.
  2. On a specially constructed family of problems CURE-UCB has constant regret, while R-ed-UCB has regret that grows at least linearly in horizone.
  3. ,The paper gives a regret bound for more general settings with noisy rewards that improve at a decreasing rate.

Experiments cover synthetic environments and learning-curve-based model selection on IMDB and XSum.

Summing up: the paper offers a simple, well-motivated algorithm with encouraging empirical results and a meaningful comparative theorem in a restricted setting. The main concerns are the interpretation and scope of its guarantees, and whether the experiments establish that horizon awareness specifically explains the improvements. See below.

Critical strengths

The paper proposes a simple well-motivated algorithm that uses the remaining budget, proves its advantage over an existing method under specific assumptions, and shows consistent improvements across synthetic and model-selection experiments.

The paper is well-written and clera about its goals and motivation.

The experimental evaluation is sufficeint, but obviously can be extended.

Critical weaknesses

The paper acknowledges the restriction of the dominance theorem. My concern is how much broader a conclusion we should draw from these results. They provide a convincing example of where knowing the horizon helps, while leaving its benefit in more general settings less clear. I think it would bi nice to have a clearer discussion of which assumptions are essential, how sensitive the comparison is to departures from those assumptions, and where the advantage might disappear. The paper still has space for such analysis as I understand.

I would find the explanation more convincing with a controlled ablation. For example, one could compare the true remaining horizon with a fixed lookahead, and examine the effects of horizon dependence in the reward estimate and exploration bonus separately. Keeping initialization, window sizes, and tuning comparable would help make the result easier to interpret. The current experiments give encouraging evidence that the complete algorithm works well; the specific claim that accurate knowledge of the remaining budget explains the improvement needs more direct support.

Questions for authors
  1. How sensitive is the dominance result to the deterministic LTF assumptions?
  2. Could you provide a controlled ablation that separates the effect of using the true remaining horizon in the reward estimate from its effect in the exploration bonus, while keeping the other experimental choices matched?
3 comments

Dear Reviewer ckT4, thank you for your thoughtful review and constructive suggestions. We have revised the manuscript based on your constructive review. We provide detailed responses to your questions below and would greatly appreciate your consideration of these updates.


Q1, W1. Limitations of Uniform Dominance and Broader Theoretical Guarantees

The uniform dominance in Theorem 5.2 does not generally extend to LTF curves with nonzero intercepts. We provide a counterexample with two armed case:

\mu_1(n) &= \min(0.73,,0.49+0.12n),\\\\ \mu_2(n) &= \min(0.82,,0.34+0.16n). \end{aligned}$$ Consider $T=6$, After two initial pulls per arm, CURE-UCB selects arms 1 and 2 a total of 3 times each, whereas R-ed-UCB selects them 2 and 4 times, respectively. Consequently, CURE-UCB incurs regret $0.39$, while R-ed-UCB incurs $0.30$, violating uniform dominance. The deterministic zero-intercept LTF assumptions provide a controlled setting that allows us to isolate the effect of the decision objective. Under these assumptions, observation noise and differences in initial reward levels are eliminated, and both algorithms explore arms in the same order of growth rates. The key distinction is therefore how they evaluate future rewards: CURE-UCB uses the known horizon to construct an estimate aligned with the exact objective, whereas R-ed-UCB relies on a horizon-agnostic surrogate that extrapolates a single future reward. The proof of Theorem 5.2 shows how this mismatch can lead R-ed-UCB to explore additional arms whose gains cannot compensate for their cost before the horizon. While these assumptions are restrictive, they enable a strong uniform dominance guarantee that holds for every instance in the class and every finite horizon. Nevertheless, we agree that broader theoretical evidence for the benefit of horizon information is necessary. We therefore introduce Proposition 5.4, extending the comparison beyond R-ed-UCB to every horizon-agnostic policy: > **Proposition 5.4 (Benefit of Horizon Awareness).** > > For every fixed $K \geq 2$ and every integer $c \geq 256K$, there exists a deterministic LTF instance $\mu_c \in \mathcal{U}_K$ such that, for any horizon-agnostic policy $\pi$, with > > $$> \mathcal{T}_c = \left\\{ \left\lfloor \frac{c}{2} \right\rfloor, 2c \right\\}, >$$ > > the following statements hold: > > **(i) CURE-UCB:** $\max_{T \in \mathcal{T}_c} \operatorname{Reg}_{\mu_c}(\pi_0^{\mathrm{cure}}, T) \leq 4(K-1)$. > > **(ii) Any horizon-agnostic policy:** $\max_{T \in \mathcal{T}_c} \operatorname{Reg}_{\mu_c}(\pi, T) \geq c/64$. The two horizons require conflicting early investments, preventing any horizon-agnostic policy from achieving low regret at both. This extends our theoretical evidence for the benefit of horizon information beyond the comparison with R-ed-UCB. --- # Q2, W2. Ablation Study on Horizon Dependence Thank you for this valuable suggestion. We agree that isolating the effects of horizon dependence is important for understanding CURE-UCB. We therefore conducted a controlled ablation, with results provided in Appendix K.4 and summarized below. **Table 1. Ablation of remaining-horizon versus fixed lookahead in the reward estimator and exploration bonus.** | Estimator / Bonus | Remaining | Fixed 50K | Fixed 150K | |---|---:|---:|---:| | Remaining | 7,703.0 | **7,274.8** | 8,210.6 | | Fixed 50K | 7,921.0 | 7,662.8 | 8,462.9 | | Fixed 150K | 8,536.1 | 8,200.0 | 9,357.4 | (We have updated this table after correcting the bias of sliding-window.) Here, “Remaining” means the estimator or bonus uses the remaining time $(T-t+1)$ in its calculation. The remaining-horizon estimator achieves the lowest mean regret under every bonus configuration, while a fixed 50K lookahead yields the lowest mean regret for the exploration bonus. This difference reflects the distinct roles of the two components. The reward estimator uses the remaining horizon to evaluate future gains, whereas the exploration bonus is derived to ensure statistical confidence in these estimates. Compared with stationary bandit algorithms, rising bandit algorithms require more conservative confidence bonuses to obtain theoretical guarantees, since extrapolating reward growth amplifies estimation uncertainty. However, such theoretically motivated optimism may cause excessive exploration in practice. In our experiments, the fixed 50K bonus is smaller during the early rounds, when exploration decisions can have a lasting impact on cumulative reward, potentially explaining its better performance despite becoming larger later. Developing tighter exploration bonuses under additional assumptions on reward convergence is an interesting direction for future work.

Dear Reviewer ckT4,

Thank you for your encouraging response. We have added the ablation you suggested to Appendix K.4 of the revised manuscript. On LTF instances, we varied the lookahead in the reward estimator and the exploration bonus independently. The remaining-horizon estimator achieved the lowest mean regret under every bonus setting we tested.

As the author–reviewer discussion deadline (Nov. 18) approaches, we would appreciate your consideration of our rebuttal and additional results. If you have any remaining questions or would like us to clarify any part of the revision, we would be happy to respond before the deadline.

Tahnk you for the detailed responce!

I find the answers in the rebuttal ecouraging and do not intend to change my assesment score of the paper. I will argue for acceptance.

Comments on the paper

1 comment

We thank you and the reviewers for your time and constructive feedback. We summarize below the strengths recognized by the reviewers and the main revisions made during the rebuttal.


The reviewers highlighted three strengths of our work:

  • Importance of the problem: All reviewers (ckT4, kLCV, and yX2j) recognized the motivation for incorporating horizon information into rising bandit decisions and aligning arm selection with the finite-horizon cumulative-reward objective.
  • Breadth and consistency of the empirical results: All reviewers (ckT4, kLCV, and yX2j) positively assessed the broad evaluation and consistent improvements across synthetic and model-selection tasks.
  • Dominance result: Reviewers ckT4 and kLCV recognized the value of our uniform dominance theorem, which establishes CURE-UCB’s advantage over R-ed-UCB, a representative horizon-agnostic algorithm, under specific assumptions.

In response to the reviewers’ questions, we made the following revisions:

  1. Clarifying the dominance assumptions and establishing a broader policy comparison (ckT4, kLCV, yX2j).

    All reviewers asked about the assumptions underlying our dominance result. We clarified that these assumptions were carefully chosen to isolate the effect of horizon awareness and establish a strong guarantee: uniform dominance across all instances and horizons within the specified class. To broaden this comparison, we added Proposition 5.4, which relaxes the requirement of uniform dominance and establishes a theoretical advantage of CURE-UCB over any horizon-agnostic algorithm, including randomized algorithms. This demonstrates that the benefit of horizon information extends beyond the comparison with R-ed-UCB.

  2. Additional ablation studies on horizon dependence and preprocessing (ckT4, kLCV).

    We conducted additional ablation studies guided by the reviewers’ valuable suggestions. Following ckT4’s request, we independently varied the lookahead in the reward estimator and exploration bonus. The remaining-horizon estimator achieved the lowest mean regret under every bonus setting tested. Following kLCV’s request, we evaluated raw LLM reward trajectories and preprocessing ablations. CURE-UCB outperformed R-ed-UCB and SW-UCB in all four evaluated settings, showing that its empirical advantage persists without the preprocessing pipeline.

  3. Correcting the sliding-window estimator (kLCV).

    We gratefully incorporated kLCV’s suggestion to account for observation age in the estimator. We updated the algorithm, the corresponding proofs, and the experiments. The corrected estimator preserves the main theoretical guarantees and empirical conclusions.


We appreciate the reviewers’ suggestions, which helped us sharpen our theoretical contributions and strengthen the empirical evidence for our approach. Thank you for considering our revised manuscript.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.