An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints

We appreciate your feedback and positive evaluation. Below, we address each comment.

The paper is an extension of [1]. When $\beta\in(0,1)$, the proposed algorithm can not be proved optimal:

First of all, we highlight that we consider rotting constraints with $V_T$ or $S_T$ and initial mean rewards with $\beta>0$, both of which are not considered in [1]. As mentioned in Remark 2.2, the rotting constraint with $V_T$ ($\sum_t \rho_t \le V_T$) is more general than the maximum rotting constraint in [1]. Furthermore, the constraint with $S_T$ ($1+\sum_t 1(\rho_t \neq 0) \le S_T$) is fundamentally different from that in [1] because $S_T$ considers the total number of rotting instances rather than the magnitude of the rotting rate.

While, in our work, we have demonstrated optimality only for $\beta \ge 1$, we believe that the suboptimality for $\beta \in (0,1)$ arises from the looseness of our lower bounds rather than the regret upper bounds. The gap between lower and upper bounds comes from that when $\beta(<1)$ decreases, the regret lower bounds (in Theorems 4.1, 4.2) also decrease while the upper bounds (in Theorems 3.1, 3.3) remain the same. As discussed in Appendix A.1, the phenomenon where the regret upper bound remains the same as $\beta$ decreases has also been observed in many infinitely many armed bandits [5, 24, 10]. This is because, as mentioned in [10], although there are likely many good arms when $\beta$ is small, it is not possible to avoid a certain amount of regret from estimating mean rewards. Therefore, we believe that our regret upper bounds are near-optimal across the entire range of $\beta$, and achieving tighter lower bounds for $\beta < 1$, considering such unavoidable regret, is left for future research. Notably, the optimality proven only for $\beta \ge 1$ has also been observed in stationary infinitely many armed bandits [5, 24].

When $\beta,V_T,S_T$ are unknown, additional regret is generated with Algorithm 2:

While our algorithm (Algorithm 2) incurs an additional regret to estimate the threshold parameter when parameters are unknown, if $V_T$, $S_T$ are large enough (e.g. $V_T\ge T^{1/4}$, $S_T\ge \sqrt{T}$ for $\beta=1$), then the regret bound of Algorithm 2 matches that of Algorithm 1 in Corollary 3.5 (for known parameters). This is because the additional term becomes negligible compared to the main term involving $V_T$ and $S_T$. We leave it as future work to obtain a tighter regret bound for the entire range of $V_T$ and $S_T$ when the parameters are unknown.

Extensive experiment study by varying the rotting rate with randomness:

The main purpose of our experiments is to validate some claims of our theoretical analysis such as Remark 3.2. Based on your comments, we have conducted an additional experiment for random rotting rates in Figure 3 in the attached pdf. Following the rotting rates used in the experiment section in our paper, which rotting rates are convenient to compare the theoretical results of algorithms, we introduced random rotting rate $\rho_t$ uniformly sampled from $[0,3/(t\log(T))]$ for each time $t$. In Figure 3, our algorithms outperform other benchmarks. We will include further experiments regarding rotting rates in our final version.

The rotting budget $V_T$ and $S_T$ are defined for all selected arms. How about treating the rotting process for each arm independently with the budget of each arm, $f(N)$, for selected $N$ times:

In our setting, the constraints on $V_T$ and $S_T$ quantify the rotting rate of all selected arms for all $t$, as you mentioned. We note that similar quantities related to overall nonstationarity across all arms have also been considered in standard non-stationary bandits [7, 19, 4]. These quantities help quantify the overall difficulty of the problem in our regret analysis. As you suggested, addressing individual budgets for each arm would be an interesting research question.

We believe that our algorithm and analysis provide helpful insights for solving such a problem. This is because the core of our algorithm involves determining whether a selected arm is good or bad based on a threshold parameter tuned by the value of the constraint budget. If we know $f(N)$ for each arm, we can use our method to determine the status of the arm using a threshold adjusted by the budget information.

Addressing the unknown parameters without incurring large additional regret. Can the methodology in [2] be applied in this paper? Can $\beta$ be estimated?

Here, we provide our thoughts regarding the applicability of [2]. In our problem, it is required to determine whether a selected arm is bad or not. In our algorithm, using a threshold, we can determine this with some confidence. Although we assume that nonstationarity can be detected using techniques from [2], it may not be clear how to determine the status of an arm whose initial mean reward is bad (small). In our setting, which includes infinitely many arms and many near-optimal ones, an absolute threshold (rather than a relative value between arms) may be required, as used in our algorithm to determine the status of arms. Without knowledge of parameters of $V_T$, $S_T$, and $\beta$, how to determine such a threshold combined with the detection method is an unresolved problem.

Another issue is that our setting allows for potentially large negative rewards from rotting with sub-Gaussian noise, whereas [2] considers rewards within $[0,1]$. This difference makes it challenging to apply the concentration inequality of Lemma 12 in [2] to our problem. As you suggested, applying the detection-based algorithm [2] to our setting while addressing those issues would be an interesting direction for future work.

Regarding the unknown $\beta$, estimating $\beta$ directly was considered in Algorithm 3 in [10]. However, it requires additional information on a (non-zero) lower bound of $\beta$, and the performance depends on the tightness of this lower bound.

We appreciate your feedback and positive evaluation of our work. Below, we address each comment.

All of the theoretical results are ultimately order results only, without identification of the constants in the appendices. It would be helpful if the bounds could thus be realised for the cases considered in the experiments and compared to the actual regret of Algorithms 1 and 2:

In our work, we provide regret bounds in terms of the horizon time $T$ and the rotting constraint parameters $V_T$ and $S_T$ (to the power of $\beta$ terms), which hold up to constant factors whose values are not asserted in the statements of our theorems.

Based on your feedback, we will include more details regarding the values of these constant factors in the final version of our paper. For instance, in Lemma A.5, instead of using $m^{\mathcal{G}} = C_3$ for some sufficiently large constant $C_3 > 0$, we can specify $m^\mathcal{G}=3$ with $V_T\le \max\\{1/T^{1/(\beta+1)},1/\sqrt{T}\\}$ and $\delta=\max\\{1/T^{1/(\beta+1)},1/\sqrt{T}\\}$. Then, we have $m^{\mathcal{G}}\min\\{\delta/2,V_T\\}=3\min\\{\delta/2,V_T\\}>V_T$, which can conclude the lemma.

We will also provide additional experimental results related to this. For now, we present an experiment in Figure 1 in the attached pdf that compares the performance of our algorithms with theoretical regret upper bounds with a constant of 1. We observe that the performance of our algorithms (blue and green solid lines) is better than the theoretical regret upper bounds (light blue and light green dashed lines), respectively, because the theoretical bounds represent worst-case regret regarding rotting rates, while the experiment is conducted under a specific instance of rotting rates.

It is noteworthy that providing regret bounds that hold up to constant factors is an important first step to establishing fundamental bounds for the underlying learning problem. Note that previous work on stationary infinitely-armed bandits (e.g. [24, 10]) also focused on providing regret bounds up to constant factors, whose values are not identified explicitly.

What would the experimental results look like for $\beta\neq 1$:

We appreciate your suggestion. We have included additional experiments in which we varied the value of $\beta$ in Figure 2 of the attached pdf. In Figure 2, our algorithms outperform other benchmarks for various $\beta$. We will incorporate this into our final version.

The motivation in terms of real applications is not especially strong:

We appreciate your comments and suggestions. We highlight that (rested) rotting rewards in bandits have been studied [16, 20, 21, 13], motivated by real-world applications such as recommendations and clinical trials. For instance, in recommender systems, the click rate for each item may diminish due to user boredom with repeated exposure to the same content. Similarly, in clinical trials, the efficacy of a medication can decline due to drug tolerance induced by repeated administration. However, the previous work regarding rotting bandits, except for [13], focused on MAB with finite arms, which have limitations when the number of items is large, as in recommender systems. In contrast, we consider the case with infinitely many arms without contextual information.

We believe our algorithm, as you mentioned, provides insights into handling rotting cases in real-world scenarios. Specifically, our adaptive SW-UCB and threshold approach offers valuable insights for designing bandit algorithms regarding when to explore new arms and how to estimate rotting mean rewards and determine the status (good or bad) of each arm when rotting occurs. Furthermore, our study on optimizing the threshold parameter provides practical guidance for setting threshold values in real-world applications.

Is Prop 2.3 missing some kind of additional condition, or clarity over what is meant by worst-case in line 453?:

Our regret analysis focuses on the worst-case regret concerning rotting rates. As outlined in Assumption 2.1, we consider an adaptive adversary that determines the rotting rate $\rho_t$ arbitrarily immediately after the agent pulls an action $a_t$ at each time step $t$. In Proposition 2.3, we show that there always exists a rotting adversary (or instances of rotting rates over $T$) with $\sum_t\rho_t>T$ such that it incurs at least $T$ regret for any algorithm, implying an $\Omega(T)$ regret lower bound. This does not imply that any rotting adversary (or any rotting instances) occur $T$ regret. This worst-case lower bound can be demonstrated by providing a rotting adversary (or rotting rate instances) where any algorithm will incur at least $T$ regret. Additionally, we show that this lower bound can be achieved by a simple algorithm that pulls a new arm every round. Therefore, Proposition 2.3, which is regarding the worst case, does not contradict the example you mentioned. We appreciate your helpful comments to improve clarification. We will include the explanation to clarify Proposition 2.3 in our final version.

Can you put the WUCB definition in an equation display and reference its equation number in the statement of Algorithm 1?:

We appreciate your helpful comments for improving the clarity of our paper. We will display the WUCB definition in an equation and reference its number in Algorithm 1.

We appreciate your feedback and positive evaluation of our work. Below, we address each comment.

I wonder how the regret bound behaves with respect to the effective rotting instead of the $V_T$ or $S_T$:

In this problem, as mentioned in Assumption 2.1, we consider an adaptive adversary who determines $\rho_t$ arbitrarily, subject to the constraint $\sum_t \rho_t \le V_T$ or $1 + \sum_t 1(\rho_t \neq 0) \le S_T$ for given $V_T$ or $S_T$. As a side remark, these constraints are more general than the stricter conditions $\sum_t \rho_t = V_T$ or $1 + \sum_t 1(\rho_t \neq 0) = S_T$. Our regret analysis, for both upper and lower bounds, addresses the worst-case scenario concerning the rotting rates under the general constraint of $V_T$ or $S_T$. Hence, our regret bounds are expressed in terms of $V_T$ or $S_T$. We also note that standard nonstationary bandits have been studied under a similar concept of a nonstationary budget upper bounded by $V_T$ [7,19].

We can consider a scenario where an adversary determines $\rho_t$ under the stricter constraints of $\sum_t \rho_t = V_T$ or $1 + \sum_t 1(\rho_t \neq 0) = S_T$. Our (upper and lower) regret bounds apply with these values of $V_T$ and $S_T$, respectively corresponding to the effective rotting amounts of $\sum_t\rho_t$ and $1 + \sum_t 1(\rho_t \neq 0)$. When there is no rotting such that $V_T=0$ and $S_T=1$, then our bounds are the same as the bounds for the stationary case (e.g. $\sqrt{T}$ for $\beta=1$ as in [24, 5]). Furthermore, if $V_T$ and $S_T$ are unknown, Algorithm 2 (in Appendix A.6) can achieve regret bounds that depend on the values of $V_T$ and $S_T$ (Theorem A.15).

We appreciate your time to review our paper and comments. Below, we address each comment.

The definition of $V_T$, $S_T$ are a bit unclear and may not be fully rigorous. They are bounds on the total amount and count of rotting, but the rotting depends on the chosen arm and is thus random:

We appreciate your detailed comments. However, we argue that the definitions of $V_T$ and $S_T$ are rigorous in our context, as they serve as constraints on the rotting adversary. These quantities are not random outcomes based on the adversary's behavior but rather imposed conditions. To clarify this, we restate our Assumption 2.1 concerning the adaptive adversary as it is.

Assumption 2.1. At each time $t\in[T]$, the value of rotting rate $\rho_t>0$ is arbitrarily determined immediately after the agent pulls $a_t$, subject to the constraint of either slow rotting for a given $V_T$ or abrupt rotting for a given $S_T$.

According to this assumption, we consider $V_T$ and $S_T$ to be given a priori to the adversary, and the adversary determines $\rho_t$ subject to these constraints. $V_T$ and $S_T$ are deterministic quantities that act as constraints, which are determined before the game begins. This is why we refer to the two scenarios as the slow rotting constraint ($V_T$) and the abrupt rotting constraint ($S_T$). In our setting, if $V_T$ or $S_T$ is large, then, as we have shown in our regret lower bounds, any algorithm naturally cannot avoid a large regret bound in the worst case.

There are no optimal regret upper bounds without parameter knowledge. Also, the bandit-over-bandit result for parameter-free result requires further assumptions on the non-stationarity and so does not apply as generally as the other results of this paper:

In the case when the parameters are unknown, there is an additional regret for Algorithm 2, which stems from learning the threshold parameter. However, if $V_T$ and $S_T$ are large enough (e.g. $V_T\ge T^{1/4}$, $S_T\ge \sqrt{T}$ for $\beta=1$), then the regret bound in Theorem A.15 for Algorithm 2 matches that in Corollary 3.5 for Algorithm 1 (for known parameters). It is an open problem to achieve tight regret bounds for entire ranges of $V_T$ and $S_T$.

Now we discuss the further assumptions. For the unknown parameter case, we consider Assumptions A.10 and A.12 rather than Assumptions 2.1 and 2.4 (for the known parameter case). In Assumption A.10, we still consider an adaptive adversary for the rotting rates, such that $0 \le \rho_t \le \varrho_t$ for given $\varrho_t$ to the adversary, where $\sum_t \varrho_t \le V_T$ and $1 + \sum_t 1(\varrho_t \neq 0) \le S_T$. Here $\varrho_t$'s are assumed to be determined before the algorithm is run. As we describe in Remark A.11, this assumption is more general than that in [13], where $\varrho_t = \rho$ with a maximum rotting rate $\rho$ for all $t$. In the special case where $\rho_t = \varrho_t$, the assumption represents an oblivious adversary.

In Assumption A.12, we consider $\sum\_{t \in \mathcal{T}\_i} \rho\_t \le H$ for all $i \in [ \lceil T/H \rceil]$, where $\mathcal{T}\_i=[(i-1)H+1,iH]$ representing the $i$-th block of times of length $H$ within horizon time $T$. As we mention in Remark A.13, this assumption is satisfied when mean rewards are constrained by $0 \le \mu_t(a_t) \le 1$ for all $t$ because $0\le\rho_t\le1$. The positive mean reward constraint is frequently encountered in real-world applications such as click rates in recommendation systems. We also note that, as mentioned in Remark A.14, the assumption is still more general than the one with a maximum rotting rate constraint of $\rho_t \le \rho = o(1)$ in [13]. This is because, in our setting, each $\rho_t$ is not necessarily bounded by $o(1)$ but $\sum_{t \in \mathcal{T}_i} \rho_t \le H$.

Lastly, we emphasize that our study is the first work to consider $V_T$, $S_T$, and $\beta$ in the context of rotting bandits with infinite arms, which is fundamentally different from finite-armed bandits due to the necessity of exploring new arms (details are described in lines 58–70). Notably, when the parameters are known, we achieve tight results using a novel approach and provide regret lower bounds.

Thank you for your comment. We would like to address a few points regarding your comments:

On $V_T$, $S_T$: Based on your comment, we believe your initial concern regarding $V_T$ and $S_T$ has been resolved. However, we would like to provide additional explanation for clarity. We strongly believe that the adaptive adversary under the slow ($V_T$) or abrupt rotting constraint ($S_T$) is a natural and general assumption in our adversary rotting scenario. The adaptive adversary determines an arbitrary rotting rate at each time, immediately after the agent's action is determined, under either $V_T$ or $S_T$. From the values of $S_T$ and $V_T$, we can appropriately quantify the difficulty of our problems, as demonstrated by our regret lower bounds.

Without such constraints (i.e., fully adaptive according to your comment), the adaptive adversary could easily make the problem trivial in the 'worst-case' scenario of our setting because whenever an algorithm finds a good arm, the adversary could cause that arm to rot and become a bad arm or even have a negative mean reward adaptively, without the constraints. We also note that similar quantities of $V_T$ and $S_T$ have also been considered in standard nonstationary bandit literature [7,19,4], where they are treated as determined quantities, not random variables, as in our setting. If necessary, we are more than happy to clarify this further in our final version to prevent any potential confusion.

Assumption A.10 for parameter-free: The additional constraint in Assumption A.10 is required due to our adaptive adversary, which selects the rotting rate arbitrarily and adaptively in response to the selected action at each time, within the bandit-over-bandit framework. If we consider an oblivious adversary instead of an adaptive one, where the values of rotting rates $\rho_t$ are predetermined such that $\sum_t \rho_t\le V_T$ and $1+\sum_t 1(\rho_t\neq 0)\le S_T$ before the game begins, then this satisfies Assumption A.10 with $\rho_t=\varrho_t$. In other words, as we mentioned in Remark A.11, Assumption A.10 is a more general assumption than this oblivious adversary and that in [13].

As mentioned in lines 831~834, the well-known black-box framework proposed for addressing nonstationarity [25] is not applicable to this problem, and attaining the optimal regret bound under a parameter-free algorithm for all ranges of $V_T$ and $S_T$ remains an open problem. However, we respectfully disagree with your comment that the results remain limited. We again highlight that our study is the first work to examine $V_T$, $S_T$, and $\beta$ in the context of rotting bandits with infinite arms, which is fundamentally different from finite-armed bandits (details are described in lines 58–70). Notably, we achieve tight results through a novel approach when the parameters are known, and we establish regret lower bounds. We also examine the case of unknown parameters. We believe our work is crucial for the community.

Dear Reviewer g8GP,

Thank you again for taking the time to review our paper.

We sincerely hope our responses have adequately addressed your questions and comments. If they have, we appreciate it if you could reconsider your evaluation. If you have any last-minute questions, please let us know.

Sincerely,

Authors

• On $V_T/S_T$: thank you for the clarification. It seems one assumes the adversary is not fully adaptive then and there are limitations on how much rotting it can force on the rewards. I would say wording this as a "adaptive adversary" can be a bit misleading then as it is really a constrained adversary.

• optimal regret upper bounds without parameter knowledge: I would carefully explain in the presentation why the further Assumptions A.10 is needed. It seems like it is an artifact of the bandit-over-bandit approach as you cannot have the adversary respond in an overly strong way to the master's choice of base over $H$ rounds.

Even under the broader above mentioned constrained adversary there seem to be no parameter-free results without this A.10. As such, I feel the scope of result remains limited in this work even while being the first to study this particular setting/parametrization.