Best Arm Identification for Stochastic Rising Bandits

We thank the Reviewer for spending time revising our work, for having appreciated our theoretical analysis and our experimental campaign. Below, our response to the reviewer's concerns.

Weaknesses

While Assumption 2.1 appears intuitive, Assumption 2.2 falls short of being satisfactory. Even though the authors present some theoretical findings solely under Assumption 2.1, their interpretability is somewhat lacking.

Assumption 2.1 implies that the expected values are non-dereasing and concave. Assumption 2.2 provides a more explicit characterizarion of the increment function $\gamma_i(n)$ by enforcing an upper bound of the form $c n^{-\beta}$ depending on the parameters $(c,\beta)$. Although our results hold under Assumption 2.1 only (Theorems 4.1 and 5.1), the forms of the error probability $e_T$ and of the minimum time budget $T$ become more interpretable under Assumption 2.2. Indeed, intuitively, the BAI problem is easier when the expected reward function reaches the stationary behavior faster (see [IMAGE]). This "speed" (a.k.a. rate) is governed mainly by $\beta$. The larger is $\beta$, the faster is the convergence rate. This is visible in Corollary 4.2 and 5.2 where the minimum requested time budget $T$ as well as the error probability decrease as $\beta$ increase. We will add this comment in the final version.

The proposed algorithm closely resembles UCB-E and SR for standard multi-armed bandits, with the primary distinction lying in the estimators. I'm not suggesting this is unacceptable, but it does somewhat diminish the novelty of this work. <!--A promising future direction would involve integrating both estimators into a unified algorithm.-->

While we agree that our algorithms follow the basic scheme of the ones of (Audibert et al., 2010), we point out that our algorithms follow well-established principles: optimism in the face of uncertainty (UCB-E) and arm elimination (SR) which are the basic building blocks of a large majority of works in bandits published in top-tier venues [1,2,3]. Thus, we do not think this diminishes the novelty of the work. Furthermore, we stress that our main contributions are: ($i$) the challenging theoretical analysis that the rested rising nature of the arms requires for both the estimators and the algorithms and ($ii$) the conception of the novel lower bound which shed lights on the complexities of the setting.

Since the expected rewards are bounded in $[0,1]$ and non-decreasing, they must converge to some value. Thus, it is not surprising that the error probability lower bound will be matched by R-SR for large $T$. For non-stationary BAI, the algorithm SR is minimal optimal up to constant factors.

While we agree that the expected rewards must converge to some value, it is not guaranteed that they will all converge to different values. Suppose that the second-optimal arm converges for $T \rightarrow +\infty$ to the same expected reward as the optimal arm. This SRB instance will be very challenging for large values of $T$. This is why we need a characterization of the conditions (Eq. 11 or 13) under which R-SR succeeds in identifying the optimal arm. Furthermore, we remark that the application of standard SR is not guaranteed to yield the same guarantees, since it uses as estimator the standard sample mean that does not discard too old samples and might fail to deliver an estimator with a bias that diminishes at the number of samples increases.

I appreciate your prompt response.

• I still hold the opinion that Assumption 2.2 is excessively strong and unrealistic, despite the proposed algorithms not requiring it. The absence of Assumption 2.2 renders the theoretical results perplexing and challenging to comprehend. Are there any analogous assumptions in existing literature that might provide a basis for comparison?

• Upon reading all other reviews and their corresponding rebuttals, I find myself somewhat perplexed by the problem setup. Why is there a need to explore BAI in stochastic rising bandits? The definition of the best arm in this context appears intricate, and even if we find the best arm, pulling it is essential for improving its expected reward, which strikes me as unusual. What advantages does BAI offer over regret minimization in the context of stochastic rising bandits?

We thank the Reviewer for spending time revising our work, and for having appreciated our theoretical analysis and our experimental campaign. Below, our response to the reviewer's concerns.

My major concern is the insufficient problem motivation. In the introduction, the example introduces the SRB is "the arm improve performances over time", but the problem setup of SRB is arms whose performances increase with pulls. I personally feel it is the example of adversarial MAB or non-stationary MAB rather than SRB. In fact it's hard for me to figure out real-world scenario (with the neccessary to model as a SRB) that solves practical problems.

In the main paper, we proposed a relevant motivating practical example, the combined algorithm selection and hyperparameter optimization (CASH), a real-world scenario arising from the AutoML research field that naturally models as a SRB problem (see Introduction). Moreover, we devoted Appendix C to discuss two additional motivating examples. We refer the Reviewer to these sections (Introduction and Appendix C) for a more detailed discussion. We agree that the sentence "the arm improve performances over time" is misleading since it may suggest that the arms evolve regardless they are pulled. We will replace it in the final version of the paper with "the arms improve their performances as it is pulled" to avoid confusion.

The experiments still do not give the real-world applications. In fact it's hard for me to figure out real-world scenario (with the neccessary to model as a SRB) that solves practical problems.

In the experimental campaign, we test our methods with real-world data by them to perform a Best Model Selection of a set of different machine learning algorithms trained to address the classification task on the IMDB dataset. Such an experiment is reported in Appendix I.3 due to space constraints.

The problem statement is a little bit unclear. Specifically, it is mentioned that SRB is a special case of SRB, but it is never explained what the word "rested" means.

We think the Reviewer with the sentence "it is mentioned that SRB is a special case of SRB" means "it is mentioned that SRB is a special case of rested bandit". We remark that Section 1 (Introduction) does explain the word "rested" precisely at the beginning of the second paragraph, which we report here for the Reviewer's convenience: "This work focuses on the Stochastic Rising Bandits (SRB), a specific instance of the rested bandit setting (Tekin & Liu, 2012) in which the expected reward of an arm increases whenever it is pulled".

There should be some discussions about the difficulties of applying existing algorithms (or some trivial variants) to solve SRB. For example, it is only mentioned in the experiments that non-stationary MAB algorithms and adversarial MAB algorithms is outperformed, but it is essential to verify that the increasing structure of SRB is crucial both theoretically and empirically.

We considered several baselines in our numerical validation, including UCB-E (Audibert et al., 2010) and Successive Rejects (Audibert et al., 2010), the most famous solutions for fixed-budget BAI in stationary MABs. These solutions are based on estimators that do not discard old data, as they are developed for stationary setting, preventing from obtaining estimator of $\mu_i(T)$ whose bias decreases as the number of pulls increases. This prevents the error probability to decrease with $T$. We considered also Prob-1 (Abbasi-Yadkori et al., 2018) as a baseline from the adversarial setting. However, we point out that in our case the rewards stochastic and subgaussian and not bounded and adversarial. Since Prob-1 assumes bounded rewards, its analysis does not apply to our setting.

---

Audibert, J. Y., Bubeck, S., & Munos, R. (2010). Best arm identification in multi-armed bandits. In COLT (pp. 41-53).

Abbasi-Yadkori, Y., Bartlett, P., Gabillon, V., Malek, A., & Valko, M. (2018). Best of both worlds: Stochastic & adversarial best-arm identification. In COLT (pp. 918-949).

We thank the Reviewer for spending time reviewing our work, and for having appreciated our clarity and completeness. Below, our answers to the reviewer's concerns.

Assuming there is a unique best arm seems somewhat unrealistic, especially after T rounds, when there is a high probability that multiple arms could have the same reward. This can be observed in Figure 2 of the experiment, where several lines easily overlap, clearly demonstrating this point.

The assumption that the optimal arm is unique is standard in the bandit best arm identification community. Such an assumption is present in the seminal paper in this setting (Audibert et al., 2010) and in (Lattimore and Szepesvári, 2020, Chapter 33). Moreover, in our setting, it is proved to be necessary to make the problem learnable. We fear that the Reviewer might have misunderstood what we mean for "unique optimal arm". Indeed, we have to enforce that at the end of the budget $T$ the arm with the hightest expected reward (i.e., the optimal) is unique and not that there are no intersection over the full horizon $T$ (and so we admit the same expected reward at some points). Looking at Figure 2, for $T \in$ {$1,\dots,300$}, we notice that there are 4 points of intersection. Thus, there are just 4 choices of $T$ over 300 in which the optimal arm is not unique. We believe that this is a light standard assumption.

Moreover, this situation is influenced by the randomness of the algorithm, similar to the paper's mention that "$i^*(T)$ may change", which is also a result of the algorithm's randomness. While similar assumptions are made in classical MAB settings, in those cases, the algorithm does not have an impact on the best arm.

Given a specific time budget $T$ (which is an input of the fixed-budget BAI problem) and given an instance of the stochastic rising bandit (i.e., the expected rewards $\mu_i(t)$ functions), the optimal arm $i^*(T) = \text{argmax}_{i \in [K]} \mu_i(T)$ is well-defined and, thus, algorithm-independent (being defined through $T$ and $\mu_i(t)$ irrespective of the used algorithm). We stress that, exactly like in classical MAB settings, the algorithm does not have an impact on the best arm also in stochastic rising bandits.

---

Audibert, J. Y., Bubeck, S., & Munos, R. (2010). Best arm identification in multi-armed bandits. In COLT (pp. 41-53).

Lattimore, T., & Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.