- 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
-
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.
-
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
-
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.
-
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.
-
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
-
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?
-
Clearly, worst-case regret rate is not the right benchmark, but is there any other evidence of improved performance in the derived bound?
-
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 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 . This follows from a simple adaptation of the construction in the proof of Proposition 5.4. Since bounded rewards give every policy a matching 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.
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.