Official Comment by Authors
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.