Tracking Most Significant Shifts in Infinite-Armed Bandits

Thank you for the insightful review, writing suggestions, and careful discussion about the similarities with the blackbox MASTER algorithm of Wei & Luo, 2021.

In my opinion, the methods of this work primarily extends the black-box technique from [Wei and Luo, 2021] to the infinite many-armed bandit setting, which is reasonable.

We respectfully disagree with this main point, which we believe may have lead to some confusion about the novelty of our contribution. Although our Algorithm 1 is also a blackbox, it has an entirely different algorithmic design, requirements on the base procedure, and regret analysis than MASTER. We do not agree it is a "modification or adaptation of MASTER" for the infinite-armed setting. We elaborate on the differences below:

1. Our requirement on the base algorithm (Assumption 2) is stronger than the requirement for the base learner in MASTER (Assumption 1 of Wei & Luo, '21). Namely, we require the base algorithm to achieve instance-dependent $\log(T)/\Delta$ regret bounds in mildly non-stationary environments whereas MASTER requires its base learner to have a $\sqrt{KT}$ regret bound (see Lemma 3 of Wang, '22). This difference is quite crucial as a $\sqrt{KT}$ bound would have been insufficient for attaining the optimal regret bound in our setting (see discussion in Lines 301--308, Column 2). This difference is discussed in Remark 2 of our paper.
2. As you correctly observed, we rely on empirically tracking the cumulative regret of the algorithm to detect non-stationarity (which is a new idea), rather than tracking UCB indices of different base algorithms as MASTER does.
3. Our algorithm is conceptually different from MASTER, with no randomized multi-scale scheduling of different base algorithms to facilitate re-exploration of discounted arms. Instead, we run a single a base algorithm and track its cumulative regret to detect non-stationarity.
4. As a result, our regret analysis substantially differs from that of MASTER's, as there is no need to argue about the guarantees of the re-exploration schedule. Instead, much of the proof of Theorem 2 relies on proving a novel high-probability regret upper bound for subsampling in mildly corrupt environments (see Lines 222-233, Column 2).

Additionally, one of our main contributions is the elimination algorithm (Algorithm 2) which in fact achieves tighter regret bounds than our blackbox. Note our elimination algorithm is not a blackbox at all , and thus bears no similarity with MASTER. The only other works which study "significant arm identification" (Suk & Kpotufe, '22, '23) all again rely on randomized multi-scale scheduling of different base algorithms to target a worst-case $\sqrt{KT}$ regret bound. Our regret analysis is thus very different, with no need for analyzing random scheduling, and instead focused on novel variance-based confidence bounds for tracking empirical regret (see discussion in Sec. 5.3).

We will better elaborate on these differences with the blackbox MASTER in rewrites.

In the experiments, it seems that only the impact of different $\beta$ of initial distributions on performance was considered, while the effect of varying non-stationarity was not validated. For instance, the regret bounds presented include two scenarios: one for piece-wise stationary settings, resulting in a $\sqrt{LT}$ bound, and another for drifting, yielding a $V^{1/3} T^{2/3}$ bound. However, the experiments appear to validate only the latter case.

Here, we provide two plots of additional synthetic experiments. The second plot covers the piecewise stationary setting where we use a rotting rate of $\rho_t=1$ at $L=\sqrt{T}$ different rounds with $\beta=1$. The prior art AUCBT-ASW (Kim et al., '24) has a regret bound of $\sqrt{LT} = T^{3/4}$, yet we see from the plot that our procedures (Blackbox and Elimination) have empirically better regret owing to the small number $\tilde{L} = O(1)$ of significant shifts. We've also included an additional benchmark, a sliding-window version of SSUCB (of Bayati et al., '20) using a window size of $\sqrt{T}$, for more expansive comparison.

The abstract does not meet the submission requirements. According to the ICML submission guidelines, abstracts must be written as a single paragraph. However, the abstract in this paper is divided into three paragraphs.

Thank you for pointing this out, as well as other writing suggestions. We'll fix it in revision.

Thank you for the detailed review, and astute questions.

On Comparison of Regret Bounds and $V, V_R, S_T$ Depending on Agent: You're correct that, in general, a direct comparison of bounds between algorithms is tricky since the adaptive adversary may vary its behavior depending on the algorithm. As a trivial example, a naive algorithm which samples a single arm and commits to it for $T$ rounds would incur linear regret $\Omega(T)$ in a stationary environment, yet could incur constant regret if an adversary helps the agent and increases the reward of the committed arm to make it optimal.

We note this phenomenon is inherent to all online learning settings involving an adaptive adversary, yet there is a substantial literature of works analyzing dynamic regret bounds in terms of quantities such as $V$ or $L$ (which as you note depends on the adversary and algorithm) (e.g., see [1]-[4] below).

For some specific choices of adversary, a comparison of regret bounds is meaningful. For example, if the adversary is oblivious, then $V,V_R,S_T$ in our work can be upper bounded by worst-case quantities which do not depend on the agent's decisions, but on restless changes. Even for such an oblivious adversary, we note optimal and adaptive regret upper bounds were unknown before this work.

Whether other meaningful choices of adversary could yield direct comparison of regret bounds is an intriguing direction for future work. We'll include this discussion in a revision.

On Lower Bounds in Rotting vs. General Non-Stationary Setup: You're correct that we consider a more general setup than the rotting setup of (Kim et al., '24). Since our setup includes the rotting problem as a sub-case, the worst-case lower bounds for our setup are at least as large as the worst-case lower bounds for the rotting sub-case. Thus, the lower bounds of Kim et al., '24 hold for our setting as well.

On Broader Experimental Comparison with Other Algorithms and Setups: We emphasize our main contribution is theoretical, rather than to propose a practical algorithm. The algorithms in our paper are of a theoretical nature that serves to resolve the main question of attaining the first optimal and adaptive regret bound for non-stationary infinite-armed bandits. The synthetic experimental results of Section 6 are mainly to support the message that our algorithm does indeed attain improved regret over the previous state-of-art. We agree with the reviewer that there's much further work to be done in designing more practical procedures, and admit the theoretical state-of-the-art is far from this.

We'd also like to note that the strategy of "sampling a fixed set of arms and then running a finite-armed non-stationary bandit algorithm'' would not have the correct theoretical regret upper bounds as the optimal sampling rate depends on the unknown non-stationarity and, furthermore, only worst-case rates of the form $\sqrt{LKT}$ for $K$ sampled arms are known for such procedures (e.g., Wei & Luo, '21), which would be inadequate for attaining the optimal regret rate (see discussion in Lines 301--308, Column 2). The difficulty of using this approach is also further discussed in Lines 112--140 (Column 2) of the paper.

The paper indicates the rising non-stationarity is benign and only exploit the case where the rewards are decaying (Corollary 5). Therefore, it remains unclear to me whether the bound can be further improved or not if take the rising part into consideration.

We'd like to emphasize that we allow for both rising and rotting non-stationarity. You are correct, however, that the bound of Corollary 5 is worst-case and only takes into account the challenge of rotting changes. It is an interesting future direction to study whether rising can improve the rate. Note, even in finite-armed bandits, improved regret bounds beyond the worst-case $\sqrt{LT} \land V^{1/3} T^{2/3}$ rates are still unknown in general.

However, in remark 1, the authors indicate Kim et al. 2022; 2024 allow for unplayed arms' rewards to change each round. As I checked these two papers, they consider rested rotting bandits, where only the means of the pulled arms will decrease and the means of unplayed arms remain unchanged.

Thanks for catching this! You're correct that Kim et al. ('22, '24) in fact study the same rested setting as ours, and we'll revise this remark.

[1] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM journal on computing, 2002.

[2] Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online Optimization : Competing with Dynamic Comparators. AISTATS 2015.

[3] Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online learning with true and noisy gradient. ICML, 2016.

[4] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. NIPS ’20

Thank you for the detailed review and positive comments.

the authors should emphasize that the "subsampling idea" for infinite-arms bandit is much older than Bayati et al[2020], see the earlier work of Berry. It is in fact standard in the infinite arm field.

This is correct - subsampling was introduced earlier for this problem, and we'll adjust the writing to reflect this.

W1) The counterpart of this strength is that the key ideas for the algorithms are not so original, although such subsampling techniques appear to be new in for non-stationary infinite-arms bandits.

Indeed, you're correct that subsampling was not used in the prior works on non-stationary infinite-armed bandits (Kim et al., '22, '24). We'd like to highlight two additional technical innovations required for our result:

1. Tracking cumulative regret using variance-based confidence bounds (this was crucial for attaining the optimal regret bound for $\beta < 1$ which was not achieved in previous works even with parameter knowledge). Note the previous works on adaptive non-stationary finite-armed bandits (e.g., Wei & Luo '21; Suk & Kpotufe '22) don't require such a refined analysis as their worst-case regret rates scale with the number of arms.
2. Doing a high-probability per-arm regret analysis for subsampling (i.e., Lines 222--233, Column 2) which is novel and departs from the previous regret analysis for subsampling (e.g., Bayati et al., '20).

W2) I feel that the topic is perhaps not that important so that achieving adaptivity (while the optimal rate were already known) makes a big impact.

As we discussed in the previous answer, in fact the optimal regret upper bound was not known for $\beta < 1$ as there was a gap between upper and lower bounds even with knowledge of non-stationarity. Our work closes this gap.

As such, hypotheses are lacking for Theorem 4 and Corollary 5. If the authors do not want to rely on Assumption 1, they should at least introduce a dedicated assumption.

Theorem 4 and Corollary 5 rely on Assumption 1, but without the upper bound on masses involving $\kappa_2$. We'll make this more clear in a revision.

In Section 1.2, the authors emphasize that this is the first work to develop dynamic regret bounds of the $V^{1/3} T^{2/3} \land \sqrt{LT}$, while such result are unknown in the finite-arm setting. I would simply like to point out that the infinite-arm setting has distinct feature which can make the problem easier than finite arm: the optimal reward is known and the distribution of the mean rewards is also known.

This is an apt point that the two settings are not directly comparable. We contend that the infinite-armed setting is not necessarily "easier" than the finite-armed counterpart. For instance, the optimal regret bounds in our setting must be free of the number of arms and so a crude $\sqrt{KT}$ bound cannot be plugged in for subsampling, instead necessitating tighter instance-dependent or variance-based bounds (as can be found in our work). In comparison, the $\sqrt{LKT}$ regret bound in $K$-armed non-stationary bandits does not require such refined analyses.

In Theorem 2, the authors provide a cumulative regret bound for Algorithm 2 which rely that use, as black-box, a bandit algorithm for $\alpha$-mildly correct bandits. How does the bound in Theorem 2 depends on $\alpha$? Alternatively, should the black-box satisfy the bound of Assumption 2 for any $\alpha$?

As our goal is to attain the optimal regret bound of $\sqrt{LT} \land V^{1/3} T^{2/3}$, we in fact only require Assumption 2 to hold in each episode $[t_{\ell}, t_{\ell+1})$ for $\alpha \approx (t_{\ell+1} - t_{\ell})^{-\frac{1}{\beta+1}}$. In terms of $\alpha$, we then show a regret bound of $\sum_{\ell=1}^{\hat{L}} (t_{\ell+1} - t_{\ell}) \cdot \alpha$ where $\hat{L}$ is the total number of episodes. Thus, for Theorem 2 to hold, it is not required for Assumption 2 to be true for any $\alpha$. Nevertheless, we show in Appendix C that classical algorithms such as UCB do in fact satisfy Assumption 2 for any $\alpha$.