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

Authors: jung-hun  kim
milan  vojnović
se-young  yun
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-07 03:12:24

Abstract: In this study, we consider the infinitely many-armed bandit problems in a rested rotting setting, where the mean reward of an arm may decrease with each pull, while otherwise, it remains unchanged. We explore two scenarios regarding the rotting of rewards: one in which the cumulative amount of rotting is bounded by $V_T$, referred to as the slow-rotting case, and the other in which the cumulative number of rotting instances is bounded by $S_T$, referred to as the abrupt-rotting case. To address the challenge posed by rotting rewards, we introduce an algorithm that utilizes UCB with an adaptive sliding window, designed to manage the bias and variance trade-off arising due to rotting rewards. Our proposed algorithm achieves tight regret bounds for both slow and abrupt rotting scenarios. Lastly, we demonstrate the performance of our algorithm using numerical experiments.

Main paper: 
 introduction: 
 We consider multi-armed bandit problems [15] , which are fundamental sequential learning problems where an agent plays an arm at each time and receives a corresponding reward. The core challenge lies in balancing the exploration-exploitation trade-off. Bandit problems have significant implications across diverse real-world applications, such as recommendation systems [17] and clinical trials [23] . In a recommendation system, each arm could represent an item, and the objective is to maximize the click-through rate by making effective recommendations.In practice, the mean rewards associated with arms may decrease over repeated plays. For instance, in content recommendation systems, the click rates for each item (arm) may diminish due to user boredom with repeated exposure to the same content. Another example is evident in clinical trials, where the efficacy of a medication can decline over time due to drug tolerance induced by repeated administration. The decline in mean rewards resulting from playing arms, referred to as (rested) rotting bandits, has been studied by Levine et al. [16] , Seznec et al. [20, 21] . The previous work focuses on finite K arms, in which Seznec et al. [20] proposed algorithms achieving Õ( √ KT ) regret. This suggests that rotting bandits with a finite number of arms are no harder than the stationary case.However, in real-world scenarios like recommendation systems, where the content items such as movies or articles are numerous, prior methods encounter limitations as the parameter K becomes large, resulting in trivial regret. This emphasizes the necessity of studying rotting scenarios with infinitely many arms, particularly when there is a lack of information about the features of each item. The consideration of infinitely many arms for rested rotting bandits fundamentally distinguishes these problems from those with a finite number of arms, as we will explain later.The study of multi-armed bandit problems with an infinite number of arms has been extensively conducted in the context of stationary rewards [6, 24, 8, 10, 5] , where the agent has no chance to play all the arms at least once until horizon time T . Initially, the distribution of the mean rewards for the arms was assumed to be uniform over the interval [0, 1] [6, 8] . This assumption was expanded to include a much wider range of distributions satisfying P(µ(a) > µ * -x) = Θ(x β ), for a parameter β > 0, where µ(a) represents the mean reward of arm a and µ * is the mean reward of the best-performing arm [24, 10, 5] . Additionally, feature information for each arm is not required for multi-armed bandit problems with infinitely many arms, which differs from linear bandits [1] or continuum-armed bandits [3, 14] , where feature information for each arm, either for the Lipschitz or linear structure, is involved. While Kim et al. [13] , as the closest work, explores the concept of diminishing rewards in the context of bandits with infinitely many arms, their focus is restricted to the case of the maximum rotting rate constraint, where the amount of rotting at each time step is bounded by ρ (= o(1)). This naturally directs focus towards regret regarding the maximum rotting rate rather than the total rotting rate over the time horizon. Furthermore, their focus is limited to the case where the initial mean rewards are uniformly distributed (β = 1).Õ max V 1 β+2 T T β+1 β+2 , T β β+1 Theorem 3.1: Õ max VIn our study, we explore rotting bandits with infinitely many arms, subject to generalized initial mean reward distribution with β > 0 and, importantly, generalized constraints on the rate at which the mean reward of an arm declines. Our investigation into diminishing, or 'rotting,' rewards encompasses two scenarios: one with the total amount of rotting bounded by V T , and the other with the total number of rotting instances bounded by S T . This allows us to capture characteristics of entire rotting rates over the time horizon. Similar constraints of V T or S T regarding nonstationarity have been explored in the context of nonstationary finite K-armed bandit problems [7, 4, 19] , where the reward distribution changes over time independently of the agent. Following established terminology for nonstationary bandits, we denote the environment with a bounded total amount of rotting as the slow rotting (V T ) case and the one with a bounded total number of rotting instances as the abrupt rotting (S T ) case.Here we discuss why (rested) rotting bandits for infinitely many arms are fundamentally different from those for finite arms. In the case of finite arms, rested rotting is known to be no harder than stationary case [20, 21] . This result arises from the confinement of mean rewards of optimal arms and played arms within confidence bounds, even under rested rotting (as demonstrated in Lemma 1 of Seznec et al. [20, 21] ). However, in the case of infinite arms under distribution for initial mean reward that allows for an infinite number of near-optimal arms, there always exist near-optimal arms outside of explored arms. Therefore, the mean reward gap may not be confined within confidence bounds. This fundamental difference from finite-armed rotting bandits introduces additional challenges. In our setting of infinite arms, there exists an additional cost for exploring new (unexplored) arms to find near-optimal arms while eliminating explored suboptimal arms. If the total rotting effect on explored arms is significant, then the frequency at which new near-optimal arms must be sought increases substantially, resulting in a large regret. This is why the rested rotting significantly affects the exploration cost regarding V T or S T in our setting, which differs from the case of finite arms.• In the context of slow rotting (V T ) or abrupt rotting (S T ), for any β > 0, we present regret upper bounds achieved by our algorithm with an appropriately tuned threshold parameter. It is noteworthy that V T , S T , and β are being considered for the first time in the context of rotting bandits with infinitely many arms.• We establish regret lower bounds for both slow rotting and abrupt rotting scenarios. These regret lower bounds imply the tightness of our upper bounds when β ≥ 1. In the other case, when 0 < β < 1, there is a gap between our upper bounds and the corresponding lower bounds, similar to what can be found in related literature, which is discussed in the paper.• Lastly, we demonstrate the performance of our algorithm through numerical experiments on synthetic datasets, validating our theoretical results. 
problem statement: 
 We consider rotting bandits with infinitely many arms where the mean reward of an arm may decrease when the agent pulls the arm. Let A be the set of infinitely many arms and let µ t (a) denote the unknown mean reward of arm a ∈ A at time t. At each time t, an agent pulls arm a π t ∈ A according to policy π and observes stochastic reward r t given by r t = µ t (a π t ) + η t , where η t is a noise term following a 1-sub-Gaussian distribution. To simplify, we use a t for a π t when there is no confusion about the policy. We assume that initial mean rewards {µ 1 (a)} a∈A are i.i.d. random variables on [0, 1], a widely accepted assumption in the context of infinitely many-armed bandits [8, 6, 24, 10, 5, 13] .As in Wang et al. [24] , Carpentier and Valko [10] , Bayati et al. [5] , we consider, to our best knowledge, the most general condition on the distribution of the initial mean reward of an arm, satisfying the following condition: there exists a constant β > 0 such that for every a ∈ A and all x ∈ [0, 1],EQUATIONwhere ∆ 1 (a) = 1 -µ 1 (a) is the initial sub-optimality gap. As noted in [24, 10, 5] , Eq.( 1) is a non-trivial condition only when x approaches 0, as for any constant x ∈ (0, 1], it becomes P(∆ 1 (a) < x) = Θ (1) , which may accommodate a wide range of distributions. It is noteworthy that the larger the value of β, the smaller the probability of sampling a good arm. Furthermore, the uniform distribution is a special case when β = 1. Importantly, our work allows for a wider range of distributions satisfying (1) for any constant β > 0 than the uniform distribution (β = 1) considered in Kim et al. [13] . Additional discussion is deferred to Appendix A.2.The rotting of arms is defined as follows. At each time t ≥ 1, the mean rewards of arms are updated as µ t+1 (a) = µ t (a) -ρ t (a), where ρ t (a t ) ≥ 0 for the pulled arm a t and ρ t (a) = 0 for every a ∈ A/{a t }, which implies that the rotting may occur only for the pulled arm at each time. Note that, for every a ∈ A and t ≥ 2, it holds µ t (a) = µ 1 (a) -t-1 s=1 ρ s (a), allowing µ t (a) to take negative values. For notation simplicity, in what follows, we write ρ t for ρ t (a t ) when there is no confusion. We refer to ρ 1 , ρ 2 , . . . as rotting rates. We also use the notation [m] := {1, . . . , m}, for any integer m ≥ 1.We consider two cases for rotting rates: (a) slow rotting case where, for given V T ≥ 0, the cumulative amount of rotting is required to satisfy the slow rotting constraint T -1 t=1 ρ t ≤ V T , and (b) abrupt rotting case where, for given S T ∈ [T ], the cumulative number of rotting instances (plus one) is required to satisfy the abrupt rotting constraint 1 + T -1 t=1 1(ρ t ̸ = 0) ≤ S T . The values of rotting rates of pulled arms, {ρ t } t∈ [T -1] , are assumed to be determined by an adversary, described as follows. Assumption 2.1 (Adaptive Adversary). At each time t ∈ [T ], the value of the rotting rate ρ 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 . Remark 2.2. The adaptive adversary under the slow rotting constraint (V T ) is more general than that in Kim et al. [13] , in which the adversary is under a maximum rotting rate constraint; that is, for given ρ = o(1), ρ t ≤ ρ for all t ∈ [T -1]. This is because our adversary is under a weaker constraint bounding the total sum of the rotting rates rather than each individual rotting rate. Additionally, the abrupt rotting constraint (S T ) is fundamentally different from the maximum rotting constraint [13] because the adversary for abrupt rotting is under a constraint on the total number of rotting instances rather than the magnitude of rotting rates. Our problem's objective is to find a policy that minimizes the expected cumulative regret over a time horizon of T time steps. For a given policy π, the regret is defined asE[R π (T )] = E[ T t=1 (1 - µ t (a π t ))]. The use of 1 in the regret definition for the optimal mean reward is justified because among the infinite arms with initial mean rewards following the distribution specified in (1) , there always exists an arm whose mean reward is sufficiently close to 1. 1We note that while we have S T ≤ T because the number of rotting instances is at most T -1, the upper bound for V T may not exist due to the lack of a constraint on the values of ρ t 's. Here we discuss an assumption for the cumulative amount of rotting. In the case of T -1 t=1 ρ t > T , the problem becomes trivial as shown in the following proposition.Proposition 2.3. In the case of T -1 t=1 ρ t > T , there always exists a rotting adversary that incurs regret of Ω(T ) and a simple policy that samples a new arm every round achieves the optimal regret of Θ(T ).Proof. The proof is provided in Appendix A.3T -1 t=1 ρ t > T , the regret lower bound of this problem is Ω(T ), which can be achieved by a simple policy. Therefore, we consider the following assumption for the region of non-trivial problems.T -1t=1 ρ t ≤ T .Notably, from the above assumption, we consider V T ≤ T for the slow rotting case. We also note that the assumption is not strong, as it frequently arises in real-world scenarios and is more general than the assumption made in prior work, as described in the following remarks. Remark 2.5. The assumption ofT -1 t=1 ρ t ≤ T is satisfied if mean rewards are under the constraint of 0 ≤ µ t (a t ) ≤ 1 for all t ∈ [T ], because this condition implies ρ t ≤ 1 for all t ∈ [T ]. Such a scenario is frequently encountered in real-world applications, where reward is represented by metrics like click rates or (normalized) ratings in content recommendation systems. Remark 2.6. Our rotting scenario with T -1 t=1 ρ t ≤ T is more general in scope than the one with the maximum rotting rate constraint where ρ t ≤ ρ = o(1) for all t ∈ [T -1], which was explored in Kim et al. [13] . This is because for our setting, ρ t is not necessarily bounded by o(1), and under the maximum rotting constraint, the condition T -1 t=1 ρ t ≤ T is always satisfied. 
algorithms and regret analysis: 
 We propose an algorithm (Algorithm 1) utilizing an adaptive sliding window for delicately controlling bias and variance tradeoff of the mean reward estimator from rotting rewards, drawing on insights from [4, 21] . This is why our algorithm can adapt to varying rotting rates ρ t and achieve tight regret bounds with respect to V T or even S T . Furthermore, our algorithm accommodates the general mean reward distribution with β > 0 by employing a carefully optimized threshold parameter.Here we describe our proposed algorithm in detail. We define µ[t1,t2] (a) = t2 t=t1 r t 1(a t = a)/n [t1,t2] (a) where n [t1,t2] (a) = t2 t=t1 1(a t = a) for t 1 ≤ t 2 . Then for window-UCB index of the algorithm, we define W U CB(a, t 1 , t 2 , T ) = µ [t1,t2] (a) + 12 log(T )/n [t1,t2] (a).In what follows, 'selecting an arm' means that a policy chooses an arm before pulling it. In Algorithm 1, we first select an arbitrary new arm a ∈ A ′ without prior knowledge regarding the arms in A ′ , denoting the corresponding time as t(a). We define T t (a) as the set of starting times for sliding windows of doubling lengths, defined as T t (a) = {s ∈ [T ] : t(a) ≤ s ≤ t -1 and s = t -2 i-1 for some i ∈ N}. Then the algorithm pulls the arm consecutively until the following threshold condition is satisfied: min s∈Tt(a) W U CB(a, s, t -1, T ) < 1 -δ, in which the sliding window having minimized window-UCB is utilized for adapting nonstationarity. If the threshold condition holds, then the algorithm considers the arm to be a sub-optimal (bad) arm and withdraws the arm. Then it selects a new arm and repeats this procedure. Utilizing the adaptive sliding window having minimized window UCB index enhances the algorithm's ability to dynamically identify poorly-performing arms across varying rotting rates. This adaptability is achieved by managing the tradeoff between bias and variance. The concept is depicted in Figure 1 (left), where an arm a undergoes multiple rotting events. WUCB with a smaller window exhibits minimal bias with the arm's most recent mean reward but introduces higher variance. Conversely, WUCB with a larger window displays increased bias but reduced variance. In this visual representation, the value of WUCB with a small window reaches a minimum, enabling the algorithm to compare this value with 1 -δ to identify the suboptimal arm. Moreover, as illustrated in Figure 1 (right), by taking into account the constraint of s = t -2 i-1 for the size of the adaptive windows, we can reduce the computation time for determining the appropriate window and reduce the required memory from O(t) to O(log t), respectively, for each time t.Having introduced our algorithm, we compare it with the previously proposed algorithm UCB-TP [13] , which is tailored for the maximum rotting rate constraint ρ t ≤ ρ (= o(1)) for all t > 0 and the uniform initial mean reward distribution (β = 1). The mean reward estimator in UCB-TP considers the worst-case scenario with the maximum rotting rate ρ as μo t (a) -ρn t (a) where μo t is an estimator for the initial mean reward, n t (a) is the number of times arm a is pulled until time t -1, and ρn t (a) is for reducing the bias from the worst-case rotting, which leads to achieving a regret bound of Õ(max{ρ 1/3 T, √ T }). This estimator is not appropriate for dealing with our generalized rotting constraints because it aims to attain the regret bound regarding the maximum rotting rate ρ without adequately addressing individual ρ t values. Our algorithm resolves this by using an adaptive sliding window estimator, which can handle rotting rates carefully. Furthermore, it can accommodate any constant β > 0 by using a carefully optimized δ, as shown below.Slow Rotting (V T ). Here we consider the case of slow rotting, where, recall, the adaptive adversary is constrained such that the total amount of rotting is bounded by V T . We analyze the regret of Algorithm 1 with tuned δ using β and V T . We define δV (β) = max{(V T /T ) 1/(β+2) , 1/T 1/(β+1) } when β ≥ 1 and δ V (β) = max{(V T /T ) 1/3 , 1/ √ T } when 0 < β < 1.The algorithm with δ V (β) achieves a regret bound in the following theorem.Theorem 3.1. The policy π of Algorithm 1 with δ = δ V (β) achieves:E[R π (T )] = Õ(max{V 1 β+2 T T β+1 β+2 , T β β+1 }) f or β ≥ 1, Õ(max{V 1 3 T T 2 3 , √ T }) f or 0 < β < 1.We observe that when β increases above 1, the regret bound becomes worse because the likelihood of sampling a good arm decreases. However, when β decreases below 1, the regret bound remains the same due to the inability to avoid a certain level of regret arising from estimating the mean reward. Further discussion will be provided later. Also, we observe that whenV T = O(max{1/T 1/(β+1) , 1/ √ T })where the problem becomes near-stationary, the regret bound in Theorem 3.1 matches the previously known regret bound for stationary infinitely many-armed bandits, Õ(max{T β/(β+1) ,T }), as shown in Wang et al. [24] , Bayati et al. [5] .Proof sketch. The full proof is provided in Appendix A.4. Here we outline the main ideas of the proof. There are several technical challenges involved in regret analysis, such as dealing with varying ρ t individually with respect to the total rotting budget of V T , adaptive estimation in our algorithm, and the generalized distributions of initial mean rewards of arms with parameter β > 0, none of which appear in Kim et al. [13] .We separate the regret into two components: one associated with pulling initially good arms and another with pulling initially bad arms. An arm a is said to be good if µ 1 (a) ≥ 1 -2δ and, otherwise, it is said to be bad. The reason why the separation is required is that our adaptive algorithm has different behaviors depending on the category of arms. Good arms may be pulled repeatedly when rotting rates are sufficiently small but bad arms are not. We writeR π (T ) = R G (T ) + R B (T ), where R G (T ) is the regret from good arms and R B (T ) is the regret from bad arms.We first provide a bound for E[R G (T )]. For analyzing regret from good arms, we analyze the cumulative amount of rotting while pulling a selected good arm before withdrawing the arm by the algorithm. Let A G T be a set of distinct good arms selected until T , t 1 (a) be the initial time step at which arm a is pulled, and t 2 (a) be the final time step at which the arm is pulled by the algorithm so that the threshold condition holds when t = t 2 (a) + 1. For simplicity, we use t 1 and t 2 for t 1 (a) and t 2 (a), when there is no confusion. For any time steps n ≤ m, we define V EQUATIONwhich consists of regret from the initial mean reward and the cumulative amount of rotting for each arm. For the first term ofa∈A G T ∆ 1 (a)n [t1,t2] (a) in (2), since ∆ 1 (a) = O(δ) from the definition of good arms a ∈ A G T , we have E[ a∈A G T ∆ 1 (a)n [t1,t2] (a)] = O(δT ).The main difficulty in (2) lies in dealing with the second term,a∈A G T t2 t=t1+1 V [t1,t-1] (a), where we need to analyze the amount of cumulative rotting until the arm is eliminated by using the adaptive threshold condition. A careful analysis of the adaptive threshold policy is required to limit the total variation of rotting. By examining the estimation errors arising from variance and bias due to the adaptive threshold condition, we can establish an upper bound for the cumulative amount of rotting asEQUATION.(3)Therefore, from δ = δ V (β), V T ≤ T , and Eqs. ( 2) and (3), using Hölder's inequality, we haveEQUATIONNext, we provide a bound for E[R B (T )]. We employ episodic regret analysis, defining an episode as the time steps between consecutively selected distinct good arms by the algorithm. By analyzing bad arms within each episode, we can derive an upper bound for the overall regret arising from bad arms. We define the regret from bad arms over m G episodes as R B m G . We first consider the case of V T = ω(max{1/ √ T , 1/T 1/(β+1) }). In this case, by setting m G = ⌈2V T /δ⌉, we can show that R B (T ) ≤ R B m G with a high probability. By analyzing R B m G with the episodic analysis, we canshow that E[R B (T )] ≤ E[R B m G ] = Õ(max{T β+1 β+2 V 1 β+2 T , T 2 3 V 1 3T }). As in the similar manner, whenV T = O(max{1/ √ T , 1/T 1/(β+1) }), by setting m G = C 3 for some constant C 3 > 0, we can show that E[R B (T )] ≤ E[R B m G ] = Õ(max{T β β+1 , √ T }).From the above two inequalities, we haveEQUATIONFinally, from (4) and ( 5), we can conclude the proof fromE[R π (T )] = E[R G (T )] + E[R B (T )].Remark 3.2. We compare our result in Theorem 3.1 with that in Kim et al. [13] , which, recall, is under the maximum rotting rate constraint ρ t ≤ ρ = o(1) for all t and uniform distribution of initial mean rewards (β = 1). For a fair comparison, we consider an oblivious adversary for rotting rates where the values of ρ t 's are determined before an algorithm is run, which may implyV T = T -1 t=1 ρ t and ρ = max t∈[T -1] ρ t .Then with β = 1, from V T ≤ T ρ, we can observe that the regret bound of Algorithm 1 is tighter than that of UCB-TP [13] as Õ(max{V1 3 T T 2 3 , √ T }) ≤ Õ(max{ρ 1 3 T, √ T }), where the latter is the regret bound of UCB-TP. We will demonstrate this in our numerical results.Abrupt Rotting (S T ). Here we consider abruptly rotting reward distribution under the constraint of S T . We consider Algorithm 1 with δ newly tuned by S T and β. We define δ S (β) = (S T /T ) 1/(β+1) for β ≥ 1 and δ S (β) = (S T /T ) 1/2 for 0 < β ≤ 1. We also define VT =T -1 t=1 E[ρ t ].In the following theorem, we present a regret upper bound for Algorithm 1 with δ S (β). Theorem 3.3. The policy π of Algorithm 1 with δ = δ S (β) achieves:E[R π (T )] = Õ(max{S 1 β+1 T T β β+1 , VT }) f or β ≥ 1, Õ(max{ √ S T T , VT }) f or 0 < β < 1.As in the slow rotting case, for the abrupt rotting case (S T ), we observe that when β increases above 1, the regret bound in the above theorem worsens as the likelihood of sampling a good arm decreases. When β decreases below 1, the regret bound remains the same because we cannot avoid a certain level of regret arising from estimating the mean reward of an arm. Additionally, we observe that the regret bound is linearly bounded by VT , which is attributed to the algorithm's necessity to pull a rotted arm at least once to determine its status as bad. Later, in the analysis of regret lower bounds, we will establish the impossibility of avoiding VT regret in the worst-case. Notably, in the typical cases where 0 ≤ ρ t ≤ 1 for all t > 0, as discussed in Remark 2.5, VT is negligible in the regret bound from VT ≤ S T ≤ T . Furthermore, we observe that for the case of S T = 1, where the problem becomes stationary (implying VT = 0), the regret bound matches the previously known regret bound of Õ(max{T β/(β+1) , √ T }) for the stationary infinitely many-armed bandits [24, 5] .Proof sketch. The full proof is provided in Appendix A.5. Here we provide a proof outline. We follow the proof framework of Theorem 3.1 but the main difference lies in carefully dealing with substantially rotted arms. For the ease of presentation, we consider each arm that experiences abrupt rotting as if it were newly selected by the algorithm, treating the arm before and after abrupt rotting as distinct arms. The definition of a good arm and a bad arm is based on the mean reward at the time when it is newly selected. Then we divide the regret into regret from good and bad arms asR π (T ) = R G (T ) + R B (T ).From the definition of good arms, we can easily show thatE[R G (T )] = O(δ S (β)T ) = Õ(S 1 β+1 T T β β+1 ) f or β ≥ 1, Õ( √ S T T ) f or 0 < β < 1.For dealing with R B (T ), we partition the regret into two scenarios: one where the bad arm is initially bad sampled from the distribution of (1) and another where it becomes bad after rotting. This can be expressed as R B (T ) = R B,1 (T ) + R B,2 (T ). Then for the former regret, R B,1 (T ), as in the proof of Theorem 3.1, by using the episodic analysis with m G = S T , we can show thatE[R B,1 (T )] ≤ E[R B m G ] = Õ(S 1 β+1 T T β β+1 ) f or β ≥ 1, Õ( √ S T T ) f or 0 < β < 1.For the regret from rotted bad arms, R B,2 (T ), it is critical to analyze significant rotting instances to obtain a tight bound with respect to S T , a factor not addressed in the regret analysis of slow rotting (V T ) in Theorem 3.1. We analyze that when there exists significant rotting, then the algorithm can efficiently detect it as a bad arm and eliminate it by pulling it at once. From this analysis, we haveE[R B,2 (T )] = Õ(max{S β β+1 T T 1 β+1 , VT }) f or β ≥ 1, Õ(max{ √ S T T , VT }) f or 0 < β < 1.Putting all the results together withE[R π (T )] = E[R G (T )]+E[R B,1 (T )]+E[R B,2 (T )] and S T ≤ T , we can conclude the proof.Remarkably, our proposed method, utilizing an adaptive sliding window, yields a tight bound (lower bounds will be presented later) not only for slow rotting but also for abrupt rotting (S T ) scenarios characterized by a limited number of rotting instances. The rationale behind the effectiveness of the adaptive sliding window in controlling the bias and variance tradeoff with respect to abrupt rotting is as follows. It can be observed that the adaptive threshold condition of min s∈Tt(a) W U CB(a, s, t -1, T ) < 1 -δ is equivalent to the condition of W U CB(a, s, t -1, T ) < 1 -δ for some s such that t 1 (a) ≤ s ≤ t -1 (ignoring the computational reduction trick). The latter expression represents the threshold condition tested for every time step before t, encompassing the time step immediately following an abrupt rotting event. Consequently, as illustrated in Figure 2 , this adaptive threshold condition can identify substantially rotted arms by mitigating bias and variance using the window starting from the time step following the occurrence of rotting.In what follows, we study the case of rotting under both slow rotting and abrupt rotting constraints. In this case, Algorithm 1, with δ = min{δ V (β), δ S (β)}, can achieve a tighter regret bound as noted in the following corollary, which can be obtained from Theorems 3.1 and 3.3. Corollary 3.4. Let R V and R S be defined asR V := max{V 1 β+2 T T β+1 β+2 , T β β+1 } f or β ≥ 1, max{V 1/3 T T 2/3 , √ T } f or 0 < β < 1 and R S := max{S 1 β+1 T T β β+1 , V T } f or β ≥ 1, max{ √ S T T , V T } f or 0 < β < 1.The policy π of Algorithm 1 with δ = min{δ V (β), δ S (β)} achieves the regret bound ofE[R π (T )] = Õ (min {R V , R S }) .Case without Prior Knowledge of V T , S T , and β. Here we study the case when the algorithm does not have prior information about the values of V T , S T , and β under the constraints of V T and S T . These parameters play a crucial role in determining the optimal threshold parameter δ in Algorithm 1. We propose an algorithm based on estimating the optimal threshold parameter δ directly (Algorithm 2), rather than estimating each unknown parameter separately, employing the Banditover-Bandit (BoB) approach [11] . Under assumptions concerning the bounds for the cumulative amount of rotting and a constrained version of the adaptive adversary for rotting rates, which are less general than Assumptions 2.1 and 2.4 but still more general than those in Kim et al. [13] , the algorithm achieves a regret bound of E[R π (T )] = Õ(min {R V , R S } + max{T (2β+1)/(2β+2) , √ T }). The additional cost arises from learning δ compared to the regret bound of Corollary 3.4. Further details of the algorithm and regret analysis are provided in Appendix A.6. 
regret lower bounds: 
 In this section, we present regret lower bounds for our problem under Assumptions 2.1 and 2.4 to provide guidance on the tightness of our regret upper bounds. For the regret lower bounds, we consider worst-case instances of rotting rates. In the following theorems, we provide regret lower bounds for slow rotting (V T ) and abrupt rotting (S T ), respectively. Theorem 4.1. For the slow rotting case with the constraint V T and β > 0, for any policy π, there always exists a rotting rate adversary such that the regret of π satisfiesE[R π (T )] = Ω max V 1 β+2 T T β+1 β+2 , T β β+1 .Proof. The proof is provided in Appendix A.8. Theorem 4.2. For the abrupt rotting case with the constraint S T and β > 0, for any policy π, there always exists a rotting rate adversary such that the regret of π satisfiesE[R π (T )] = Ω max S 1 β+1 T T β β+1 , VT .Proof. The proof is provided in Appendix A.9.For the abrupt rotting (S T ) case, it is unavoidable to incur a Ω( VT ) regret because an arm may only be rotted once and any algorithm pulls this rotted arm at least once in the worst case. From Table 1 , we can observe that Algorithm 1 achieves near-optimal regret when β ≥ 1. The optimality proven only for β ≥ 1 has also been observed for stationary infinitely many-armed bandits [5, 24] . We believe that our regret upper bounds are near-optimal across the entire range of β. Achieving tighter regret lower bounds when β < 1 is left for future research; see Appendix A.1 for further discussion. 
experiments: 
 In this section, we present numerical results validating some claims of our theoretical analysis. 2 We use randomly generated datasets under a uniform distribution for initial mean rewards (β = 1).We first compare the performance of our Algorithms 1 and 2 with UCB-TP [13] , the state-of-the-art algorithm for the rotting setting, and SSUCB [5] , a near-optimal algorithm for stationary infinitely many-armed bandits. For comparison with UCB-TP, recall our discussion in Remark 3.2. We set the rotting rates such that ρ t = 1/(t log(T )) for all t, for which ρ= ρ 1 = 1/ log(T ) = o(1), V T = O(1), and S T = T . In Figure 5 (a), we can observe that Algorithms 1 and 2 perform better than UCB-TP and SSUCB (and Algorithm 1 outperforms Algorithm 2), which is in agreement with our theoretical analysis for the case β = 1. In this case, the regret bounds for Algorithms 1 and 2 are Õ(T 2/3 ) and Õ(T 3/4 ) from Corollary 3.4 and Theorem A. 15 , respectively, which are tighter than the regret bound of Õ(T / log(T ) 1/3 ) for UCB-TP.We next compare the performance of our Algorithms with benchmarks for smaller or larger β. In Figure 5 (b, c ), we can observe that our algorithms outperform the benchmarks for β = 0.5 and β = 2. Additional experiments can be found in Appendix A.10. 2 The source code is available at https://github.com/junghunkim7786/ An-Adaptive-Approach-for-Infinitely-Many-armed-Bandits-under-Generalized-Rotting-Constraints 0 1 2 3 4 5 T 1e6 0 1 2 3 E[R (T)] 1e6 SSUCB UCB-TP Algorithm 2 Algorithm 1 (a) β = 1 0 1 2 3 4 5 T 1e6 0.0 0.5 1.0 1.5 2.0 2.5 3.0 E[R (T)] 1e6 SSUCB UCB-TP Algorithm 2 Algorithm 1 (b) β = 0.5 0 1 2 3 4 5 T 1e6 0 1 2 3 4 E[R (T)] 1e6 SSUCB UCB-TP Algorithm 2 Algorithm 1 (c) β = 2 
conclusion: 
 We explore the challenges of infinitely many-armed bandit problems with rotting rewards, focusing on slow rotting (V T ) and abrupt rotting (S T ) scenarios. To address these challenges, we propose an algorithm incorporating an adaptive sliding window, which achieves tight regret bounds for both cases. We also provide regret lower bounds for both slow rotting and abrupt rotting cases. Lastly, we demonstrate our algorithm using synthetic datasets. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [No] Justification: The conducted experiments do not require significant computing power.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [NA] Justification: Given that this study primarily focuses on theoretical analysis, we do not foresee any negative social consequences.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [NA] Justification: This paper does not use existing assets.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. 
 
 Appendix: As we summarize our results in Table 1 , Algorithm 1 achieves near-optimal regret only when β ≥ 1.Here, we discuss the discrepancies between lower and upper bounds when 0 < β < 1. From (1), we can observe that as β decreases below 1, the probability to sample good arms may increase, which appears to be beneficial with respect to regret. However, the regret upper bounds for 0 < β < 1 in Theorems 3.1 and 3.3 remain the same as the case when β = 1 while the regret lower bounds in Theorems 4.1 and 4.2 decrease as β decreases, resulting in a gap between the regret upper and lower bounds. The phenomenon that the regret upper bound remains the same when β decreases has also been observed in previous literature on infinitely many-armed bandits [5, 24, 10] . As mentioned in Carpentier and Valko [10] , although there are likely to be many good arms when β is small, it is not possible to avoid a certain amount of regret from estimating mean rewards to distinguish arms under sub-Gaussian reward noise. Therefore, we believe that our regret upper bounds are near-optimal across the entire range of β, and achieving tighter regret lower bounds when β < 1 is left for future research. Notably, the optimality proven only for β ≥ 1 has also been observed for stationary infinitely many-armed bandits [5, 24] .A.2 Additional Explanations for Eq. ( 1) To discuss the effect of β on the distribution of ∆ 1 (a) and the probability of sampling a good arm (having small ∆ 1 (a)), we consider the case when P(∆ 1 (a) < x) = x β , which is shown in Figure 4 for some values of β. It is noteworthy that the uniform distribution is a special case when β = 1. Importantly, the larger the value of β, the smaller the probability of sampling a good arm.1 1 𝛽 = 1 𝛽 > 1 𝛽 < 1 𝑥 ℙ Δ ! 𝑎 < 𝑥 (Uniform distribution) (Good arm ¯) (Good arm )Recall∆ 1 (a) = 1 -µ 1 (a). We first show that E[µ 1 (a)] = Θ(1). For any randomly sampled a ∈ A, we have E[µ 1 (a)] ≥ yP(µ 1 (a) ≥ y) = yP(∆ 1 (a) < 1 -y) for y ∈ [0, 1]. With y = 1/2, we have E[µ 1 (a)] ≥ (1/2)P(∆ 1 (a) < (1/2)) = Θ(1) from constant β > 0 and (1). Then with E[µ 1 (a)] ≤ 1, we can conclude E[µ 1 (a)] = Θ(1) (Especially when P(∆(a) < x) = x β , we have E[∆ 1 (a)] = 1 0 P(∆ 1 (a) ≥ x)dx = 1 - 1 0 P(∆ 1 (a) < x)dx = 1 - 1 0 x β dx = 1 -1 β+1 , which implies E[µ 1 (a)] = Θ(1) with constant β > 0).We then think of a policy π ′ that randomly samples a new arm and pulls it only once every round. Since E[µ 1 (a)] = Θ(1) for any randomly sampled a,we have E[R π ′ (T )] = Θ(T ).Next we show that the policy π ′ is optimal for the worst case of T -1 t=1 ρ t > T . We think of any policy π ′′ except π ′ . For any policy π ′′ , there always exists an arm a such that the policy must pull arm a at least twice. Let t ′ and t ′′ be the rounds when the policy pulls arm a. If we consider ρ t ′ > 0 andρ t = 0 for t ∈ [T -1]/{t ′ } such that ρ t ′ = T -1 t=1 ρ t then such policy has Ω( T -1 t=1 ρ t ) regret bound. Since T -1 t=1 ρ t > T , for any algorithm π ′′ except π ′ , there always exist a rotting rate adversary such that E[R π ′′ (T )] = Ω( T -1 t=1 E[ρ t ]) = Ω(T ).Therefore we can conclude that π ′ is the optimal algorithm for achieving the optimal regret of Θ(T ).A.4 Proof of Theorem 3.1: Regret Upper Bound of Algorithm 1 for Slow Rotting with V T Let ∆ t (a) = 1 -µ t (a). Using a threshold parameter δ, we classify an arm a as good if ∆ 1 (a) ≤ δ/2, near-good if δ/2 < ∆ 1 (a) ≤ 2δ, and otherwise, we classify a as a bad arm. In A, let ā1 , ā2 , . . . , be a sequence of arms, which have i.i.d. mean rewards with uniform distribution on [0, 1]. Without loss of generality, we assume that the policy samples arms, which are pulled at least once, according to the sequence of ā1 , ā2 , . . . , . Let A T be the set of sampled arms over the horizon of T time steps, which satisfies|A T | ≤ T . Let A GT be a set of good or near good arms in A T . WLOG, the following proofs proceed under the given A T , since the proofs hold for anyA T . Let µ [s1,s2] (a) = s2 t=s1 µ t (a)/n [s1,s2] (a) for the time steps 0 < s 1 ≤ s 2 . We define event E 1 = {| µ [s1,s2] (a) -µ [s1,s2] (a)| ≤ 12 log(T )/n [s1,s2] (a) for all 1 ≤ s 1 ≤ s 2 ≤ T, a ∈ A T }.By following the proof of Lemma 35 in Dylan J. Foster [12] , from Lemma A.29 we haveEQUATIONwhere X i = r τi -µ τi (a) and τ i is the i-th time that the policy pulls arm a starting from s 1 . We note that even though X i 's seem to depend on each other from τ i 's, each value of X i is independent of each other. Then using union bound for s 1 , s 2 , and a ∈ A T , we haveP(E c 1 ) ≤ 2/T 2 . From the cumulative amount of rotting V T , we note that ∆ t (a) = O(V T + 1) for any a and t, which implies E[R π (T )|E c 1 ] = o(T 2 ) from V T ≤ T .For the case where E 1 does not hold, the regret isE[R π (T )|E c 1 ]P(E c 1 ) = O(1), which is negligible compared to the regret when E 1 holds, which we show later. Therefore, for the rest of the proof, we assume that E 1 holds.For regret analysis, we divide R π (T ) into two parts, R G (T ) and R B (T ) corresponding to regret of good or near-good arms, and bad arms over time T , respectively, such that R π (T ) = R G (T )+R B (T ). We first provide a bound of R G (T ) in the following lemma. Lemma A.1. Under E 1 and policy π, we haveE[R G (T )] = Õ T δ + T 2/3 V 1/3 T . Proof. Here we consider arms a ∈ A G T . Let V [n,m] (a) = m l=n ρ l (a) and ρ [n,m] (a) = m l=n ρ l (a)/n [n,m] (a)for time steps n ≤ m. For ease of presentation, for time steps r > q, we defineV [r,q] (a) = n [r,q] (a) = ρ [r,q] (a) = q t=r x(t) = 0 for x(t) ∈ R and 1/0 = ∞. Then, for any s such that n ≤ s ≤ m, under E 1 we have µ [s,m] (a) ≤ μ[s,m] (a) + 12 log(T )/n [s,m] (a) ≤ µ m (a) + m-1 l=s ρ l 1(a l = a) + 12 log(T )/n [s,m] (a) = µ n (a) - m-1 l=n ρ l 1(a l = a) + m-1 l=s ρ l 1(a l = a) + 12 log(T )/n [s,m] (a) ≤ µ n (a) -V [n,m-1] (a) + ρ [s,m-1] (a)n [s,m] (a) + 12 log(T )/n [s,m] (a).Therefore, from µ n (a) ≤ 1 we obtainEQUATIONLet t 1 (a) be the initial time when the arm a is sampled and pulled and t 2 (a) be the final time when the policy pulls the arm. For simplicity, we use t 1 and t 2 instead of t 1 (a) and t 2 (a), respectively, when there is no confusion. We define A 0 as a set of arms a ∈ A G T such that t 2 (a) = t 1 (a) and define A 1 as a set of arms a ∈ A G T such that t 2 (a) = t 1 (a) + 1. We also define a set of armsA G T = {a ∈ A G T /{A 0 ∪ A 1 } : n [t1,t2-1] (a) > ⌈(log T ) 1/3 /ρ [t1,t2-2] (a) 2/3 ⌉}. Let w(a) = ⌈(log T ) 1/3 /ρ [t1,t2-2] (a) 2/3 ⌉.For simplicity, we use w for w(a) when there is no confusion. Then with the fact that µ t (a) = µ t1 (a) -EQUATIONwhere the first inequality comes from ∆ 1 (a) ≤ 2δ for any a ∈ A G T . For the second term in the right hand side of the last inequality (8) ,EQUATIONFor the third term in (8) , from the fact that nEQUATIONNow, we focus on the fourth term in (8) . From EQUATIONNow we focus on (8) . From the definition of t 2 and the threshold condition in the algorithm with (7) , for any t 1 ≤ t ≤ t 2 and anya∈A G T t2(a) t=t1(a)+w(a)+1 V [t1,t-1] (a) inEQUATIONFor t ≥ t 1 +w(a)+1, there always existst 1 ≤ s(t) ≤ t-1 such that w(a)/2 ≤ n [s(t),t-1] (a) ≤ w(a)and s(t) = t -2 l-1 for l ∈ Z + . Then from ( 12) with s = s(t), we haveEQUATION)Using the facts that nEQUATIONwhere the second inequality is obtained from the fact that the number of times that ρ t is duplicated for eacht ∈ [t 1 (a) + 1, t 2 (a) -2] in the expression t2(a) t=t1(a)+1+w(a) t-2k=t-w(a) ρ k is at most w(a). Then with ( 13) and ( 14), using the fact thatEQUATION)Then putting the results from ( 8),( 10), (11) , and ( 15) altogether, we haveEQUATIONwhere the last equality comes from Hölder's inequality and V T ≤ T . This concludes the proof. Now, we provide a bound for R B (T ). We note that the initially bad arms can be defined only when 2δ < 1. Otherwise when 2δ ≥ 1, we have R(T ) = R G (T ), which completes the proof. Therefore, for the regret from bad arms, we consider the case of 2δ < 1. We adopt the episodic approach in Kim et al. [13] for the remaining regret analysis. The episodic approach is reformulated using the cumulative amount of rotting instead of the maximum rotting rate. In the following, we define some notation.Given a policy sampling arms in the sequence order, let m G be the number of samples of distinct good arms and m B i be the number of consecutive samples of distinct bad arms between the i -1-st and i-th sample of a good arm among m G good arms. We refer to the period starting from sampling the i -1-st good arm before sampling the i-th good arm as the i-th episode. Observe that m B 1 , . . . , m B m G are i.i.d. random variables with geometric distribution with parameter 2δ, given a fixed value of m G . Therefore, for non-negative integer k we have P(m B i = k) = (1 -2δ) k 2δ, for i = 1, . . . , m G . Define mT to be the number of episodes from the policy π over the horizon T , mG T to be the total number of samples of a good arm by the policy π over the horizon T such that mG T = mT or mG T = m -1, and mB i,T to be the number of samples of a bad arm in the i-th episode by the policy π over the horizon T .Under a policy π, let R B i,j be the regret (summation of mean reward gaps) contributed by pulling the j-th bad arm in the i-th episode. Then letR B m G = m G i=1 j∈[m B i ] R B i,j, which is the regret from initially bad arms over the period of m G episodes.Let a(i) be a good arm in the i-th episode and a(i, j) be a j-th bad arm in the i-th episode. We define V T (a) = T t=1 ρ t 1(a t = a). Then excluding the last episode mT over T , we provide lower bounds of the total rotting variation over T for a(i), denoted by V T (a(i)), in the following lemma.Lemma A.2. Under E 1 , given mT , for any i ∈ [ mG T ]/{ mT } we have V T (a(i)) ≥ δ/2. Proof. Suppose that V T (a(i)) < δ/2, then we have min t1(a(i))≤s≤t2(a(i)) µ [s,t2(a(i))] (a(i)) + 12 log(T )/n [s,t2(a(i))] (a(i)) ≥ min t1(a(i))≤s≤t2(a(i)) {µ [s,t2(a(i))] (a(i))} ≥ µ t2(a(i)) (a(i)) ≥ µ 1 (a(i)) -V T (a(i)) > 1 -δ,where the first inequality is obtained from E 1 , and the last inequality is from V T (a(i)) < δ/2 and µ 1 (a(i)) ≥ 1 -δ/2. Therefore, from the threshold condition, policy π must pull arm a(i) until its total rotting amount is greater than (or equal to) δ/2, which implies V T (a(i)) ≥ δ/2.In the following, we consider two different cases with respect to V T ; large and small V T .Case 1: We consider V T > max{1/ √ T , 1/T 1/(β+1) } in the following.In this case, we haveδ = δ V (β) = max{(V T /T ) 1/(β+2) , (V T /T ) 1/3 }.Here, we define the policy π after time T such that it pulls a good arm until its total rotting variation is equal to or greater than δ/2 and does not pull a sampled bad arm. We note that defining how π works after T is only for the proof to get a regret bound over time horizon T . For the last arm ã over the horizon T , it pulls the arm until its total variation becomes max{δ/2,V T (ã)} if ã is a good arm. For i ∈ [m G ], j ∈ [m B i ] let V Gi and V B i,j be the total rotting variation of pulling the good arm in i-th episode and j-th bad arm in i-th episode from the policy, respectively. Here we define V G i 's and V B i,j 's as follows: If ã is a good arm,V G i = V T (a(i)) for i ∈ [ mG T -1] max{δ/2, V T (a(i))} for i ∈ [m G ]/[ mG T -1] , V B i,j = V T (a(i, j)) for i ∈ [ mG T ], j ∈ [ mB i,T ] 0 for i ∈ [m G ]/[ mG T ], j ∈ [m B i ].Otherwise,V G i = V T (a(i)) for i ∈ [ mG T ] δ/2 for i ∈ [m G ]/[ mG T ] , V B i,j = V T (a(i, j)) for i ∈ [ mG T ], j ∈ [ mB i,T ] 0 for i ∈ [m G ]/[ mG T -1], j ∈ [m B i ]/[ mB i,T ]. For i ∈ [m G ], j ∈ [m B i ] let n B i,jbe the number of pulling the j-th bad arm in i-th episode from the policy. We define n T (a) be the total amount of pulling arm a over T . Here we define n B i,j 's as follows:n B i,j = n T (a(i, j)) for i ∈ [ mG T ], j ∈ [ mB i,T ] 0 for i ∈ [m G ]/[ mG T ], j ∈ [m B i ].Then we providem G such that R B (T ) ≤ R B m G in the following lemma. Lemma A.3. Under E 1 , when m G = ⌈2V T /δ⌉ we have R B (T ) ≤ R B m G .Proof. From Lemma A.2, we havei∈[m G ] V G i ≥ m G δ 2 ≥ V T , which implies that R B (T ) ≤ R B m G .From the result of Lemma A.3, we set m G = ⌈2V T /δ⌉. We analyze R B m G for obtaining a bound for R B (T ) in the following. Lemma A. 4 . Under E 1 and policy π, we haveE[R B m G ] = Õ max{T (β+1)/(β+2) V 1/(β+2) T , T 2/3 V 1/3 T } .Proof. Let a(i, j) be a sampled arm for j-th bad arm in the i-th episode and mT be the number of episodes from the policy π over the horizon T . Suppose that the algorithm samples arm a(i, j) at time t 1 (a(i, j)). Then the algorithm stops pulling arm a(i, j) at time t 2 (a(i, j)) + 1 if µ [s,t2(a(i,j))] (a) + 12 log(T )/n [s,t2(a(i,j))] (a) < 1 -δ for some s such that t 1 (a(i, j)) ≤ s ≤ t 2 (a(i, j)) and s = t 2 (a(i, j)) + 1 -2 l-1 for l ∈ Z + . For simplicity, we use t 1 and t 2 instead of t 1 (a(i, j)) and t 2 (a(i, j)) when there is no confusion. We first consider the case where the algorithm stops pulling arm a(i, j) because the threshold condition is satisfied. For the regret analysis, we consider that for t > t 2 , arm a is virtually pulled. We note that under E 1 , we haveµ [s,t2] (a(i, j)) + 12 log(T )/n [s,t2] (a(i, j)) ≤ µ [s,t2] (a(i, j)) + 2 12 log(T )/n [s,t2] (a(i, j)) ≤ µ 1 (a(i, j)) + 2 12 log(T )/n [s,t2] (a(i, j)).Then we assume that t2 (≥ t 2 ) is the smallest time that there exists t 1 ≤ s ≤ t2 with s = t2 + 1 -2 l-1 for l ∈ Z + such that the following threshold condition is met:EQUATION)From the definition of t2 , we observe that for given t2 , the time step s = s ′ which satisfying (17) equals to t 1 (i.e. s ′ = t 1 ). Then, we can observe that n [s ′ , t2] (a(i, j)) = n [t1, t2] (a(i, j)) = ⌈C 2 log(T )/(∆ t1 (a(i, j)) -δ) 2 ⌉ for some constant C 2 > 0, which satisfies (17) . Then fromn [t1,t2] (a(i, j)) ≤ n [t1, t2] (a(i, j)), for all i ∈ [ mT ], j ∈ [ mB i,T ] we have n B i,j = Õ(1/(∆ 1 (a(i, j)) - δ) 2 ). Then with the facts that n B i,j = 0 for i ∈ [m G ]/[ mG T ], j ∈ [m B i ]/[ mB i,T ], we have, for any i ∈ [m G ] and j ∈ [m B i ], n B i,j = Õ(1/(∆ t1 (a(i, j)) -δ) 2 ). For 2δ < x ≤ 1, let b(x) = P(∆ 1 (a) = x|a is a bad arm). Then we have b(x) = P(∆ 1 (a) = x|∆ 1 (a) > 2δ) = P(∆ 1 (a) = x)/P(∆ 1 (a) > 2δ) = P(∆ 1 (a) = x)/(1 -C(2δ) β ).We note that 2δEQUATIONRecall that we consider 2δ < 1 for regret from bad arms. We adopt some techniques introduced in Appendix D of Bayati et al. [5] to deal with the generalized mean reward distribution with β. Let K = (1 -2δ)/δ, a j = 2 jδ , and p j = (j+1)δ jδ b(t + δ)dt. Then for obtaining a bound of the last equality in (18) we haveEQUATIONWe note that j i=1 p i ≤ C 0 (jδ) β for all j ∈ [K] for some constant C 0 > 0. Then for getting a bound of the last equality in (19) , we haveEQUATIONNow we analyze the term in the last equality in (20) according to the criteria for β. For β = 1, we can obtainEQUATIONFor β > 1, we have j β -(j -1) β ≤ βj β-1 using the mean value theorem. Therefore, we obtain the following.EQUATIONFor β < 1, when j > 1 we have j β -(j -1) β ≤ β(j -1) β-1 using the mean value theorem. Therefore, we obtainEQUATIONFrom ( 19),( 20),( 21), (22) , and ( 23), we have1 2δ 1 (x -δ) 2 x b(x)dx = Õ(max{1, δ β-1 }).EQUATIONEQUATIONEQUATION)Case 2: Now we consider V T ≤ max{1/ √ T , 1/T 1/(β+1) } in the following. In this case, we haveδ = max{1/T 1 β+1 , 1/ √ T }.For getting R B m G , here we define the policy π after time T such that it pulls V T amount of rotting variation for a good arm and 0 for a bad arm. We note that defining how π works after T is only for the proof to get a regret bound over time horizon T . For the last arm ã over the horizon T , it pulls the arm up to V T amount of rotting variation if ã is a good arm. Fori ∈ [m G ], j ∈ [m B i ] let V G i and V B i,jbe the amount of rotting variation from pulling the good arm in i-th episode and j-th bad arm in i-th episode from the policy, respectively. Here we define V G i 's and V B i,j 's as follows: If ã is a good arm,V G i = V T (a(i)) for i ∈ [ mG T -1] V T for i ∈ [m G ]/[ mG T -1] , V B i,j = V T (a(i, j)) for i ∈ [ mG T ], j ∈ [ mB i,T ] 0 for i ∈ [m G ]/[ mG T ], j ∈ [m B i ].Otherwise,V G i = V T (a(i)) for i ∈ [ mG T ] V T for i ∈ [m G ]/[ mG T ] , V B i,j = V T (a(i, j)) for i ∈ [ mG T ], j ∈ [ mB i,T ] 0 for i ∈ [m G ]/[ mG T -1], j ∈ [m B i ]/[ mB i,T ]. For i ∈ [m G ], j ∈ [m B i ] let n B i,jbe the number of pulling the j-th bad arm in i-th episode from the policy. We define n T (a) be the total amount of pulling arm a over T . Here we define n B i,j 's as follows:n B i,j = n T (a(i, j)) for i ∈ [ mG T ], j ∈ [ mB i,T ] 0 for i ∈ [m G ]/[ mG T ], j ∈ [m B i ].Then we providem G such that R B (T ) ≤ R B m G in the following lemma. Lemma A.5. Under E 1 , when m G = 3, we have R B (T ) ≤ R B m G .Proof. From Lemma A.2, under E 1 we can find thatV G i ≥ min{δ/2, V T } for i ∈ [m G ]. Then if m G = 3, then with δ = max{1/T 1/(β+1) , 1/ √ T } and V T ≤ max{1/T 1/(β+1) , 1/ √ T }, we have i∈[m G ] V G i ≥ C 3 min{δ/2, V T } > V T , which implies R B (T ) ≤ R B m G .We analyze R B m G for obtaining a bound for R B (T ) in the following. Lemma A. 6 . Under E 1 and policy π, we haveE[R B m G ] = Õ max{T β/(β+1) , √ T } .Proof. From (24) , for any iEQUATION)Conclusion: Overall, from (26) and ( 27), we haveE[R π (T )] = Õ max{V 1/(β+2) T T (β+1)/(β+2) , V 1/3 T T 2/3 , T β/(β+1) , √ T } .A.5 Proof of Theorem 3.3: Regret Upper Bound of Algorithm 1 for Abrupt Rotting (S T )Using the threshold parameter δ in the algorithm, we define an arm a as a good arm if ∆ t (a) ≤ δ/2, a near-good arm if δ/2 < ∆ t (a) ≤ 2δ, and otherwise, a is a bad arm at time t. For analysis, we consider abrupt change as sampling a new arm. In other words, if a sudden change occurs to an arm a by pulling the arm a, then the arm is considered to be two different arms; before and after the change. The type of abruptly rotted arms (good, near-good, or bad) after the change is determined by the current value of rotted mean reward. Without loss of generality, we assume that the policy samples arms, which are pulled at least once, in the sequence of ā1 , ā2 , . . . , . Let A T be the set of sampled arms, which are pulled at least once, over the horizon of T time steps, which satisfies |A T | ≤ T . We also define A S as a set of arms that have been rotted and pulled at least once, which satisfies |A S | ≤ S T . To better understand the definitions, we provide an example. If an arm a suffers abrupt rotting at first, then the arm a is considered to be a different arm a ′ after the rotting. If the arm a ′ again suffers abrupt rotting, then it is considered to be a ′′ after the rotting. If arms a, a ′ , a ′′ are pulled at least once, then {a, a ′ , a ′′ } ∈ A T and {a ′ , a ′′ } ∈ A S but a / ∈ A S . If arm a ′′ is not pulled at least once but a and a ′ are pulled at least once, then {a, a ′ } ∈ A T and a ′ ∈ A S but a ′′ / ∈ A S .WLOG, the following proofs proceed under the given A T , since the proofs hold for anyA T . Let µ [t1,t2] (a) = t2 t=t1 µ t (a)1(a t = a)/n [t1,t2] (a). We define the eventE 1 = {| µ [s1,s2] (a) - µ [s1,s2] (a)| ≤ 12 log(T )/n [s1,s2] (a) for all 1 ≤ s 1 ≤ s 2 ≤ T, a ∈ A T }.By following the proof of Lemma 35 in Dylan J. Foster [12] , from Lemma A.29 we haveEQUATIONwhere X i = r τi -µ τi (a) and τ i is the i-th time that the policy pulls arm a starting from s 1 . We note that even though X i 's seem to depend on each other from τ i 's, each value of X i is independent of each other. Then using union bound for s 1 , s 2 , and a ∈ A T , we have P(E c 1 ) ≤ 2/T 2 . Let t(s) be the time when s-th abrupt rotting occurs with ρ t(s) for s ∈[S T ]. Then we have ∆ t (a) = O(1 + S T s=1 ρ t(s) ) = O(1 + V T ) for any a and t, which implies E[R π (T )|E c 1 ] = O(T + T V T ). For the case that E 1 does not hold, the regret is E[R π (T )|E c 1 ]P(E c 1 ) = O((1 + V T )/T ), which is negligible comparing with the regret when E 1 holds true which we show later. Therefore, in the rest of the proof we assume that E 1 holds true.Recall that R π (T ) = T t=1 (1 -µ t (a t )). For regret analysis, we divide R π (T ) into two parts, R G (T ) and R B (T ) corresponding to regret of good or near-good arms, and bad arms over time T , respectively, such that R π (T ) = R G (T ) + R B (T ). Recall that we consider abrupt change as sampling a new arm in this analysis. Then, from ∆ t (a) ≤ 2δ for any good or near-good arms a at time t, we can easily obtain thatE[R G (T )] = O(δT ) = O(max{S 1/(β+1) T T β/(β+1) , S T T }).(29)Now we analyze R B (T ). We divide regret R B (T ) into two regret from bad arms in A T /A S , denoted by R B,1 (T ), and regret from bad arms in A S , denoted by R B,2 (T ) such that R B (T ) = R B,1 (T ) + R B,2 (T ). We denote bad arms in A S by A B S . We first analyze R B,1 (T ) in the following. For regret analysis, we adopt the episodic approach suggested in Kim et al. [13] . The main difference lies in analyzing our adaptive window UCB and a more generalized mean-reward distribution with β. In the following, we introduce some notation. Here we only consider arms in A T /A S so that the following notation is defined without considering (rotted) arms in A S . We note that from the definition of A T , arms a before having undergone rotting are contained in A T /A S . Here we consider the case of 2δ S (β) < 1 since otherwise when 2δ S (β) ≥ 1, bad arms are not defined in A T /A S .Given a policy sampling arms in the sequence order, let m G be the number of samples of distinct good arms and m B i be the number of consecutive samples of distinct bad arms between the i -1-st and i-th sample of a good arm among m G good arms. We refer to the period starting from sampling the i -1-st good arm before sampling the i-th good arm as the i-th episode. Observe that m B 1 , . . . , m B m G are i.i.d. random variables with geometric distribution with parameter 2δ, given a fixed value of m G . Therefore, for non-negative integer k we have P(mB i = k) = (1 -2δ) k 2δ, for i = 1, . . . , m G .T to be the total number of samples of a good arm by the policy π over the horizon T and mB i,T to be the number of samples of a bad arm in the i-th episode by the policy π over the horizon T . For i ∈ [ mG T ], j ∈ [ mB i,T ], let ñG i be the number of pulls of the good arm in the i-th episode and ñB i,jbe the number of pulls of the j-th bad arm in the i-th episode by the policy π over the horizon T . Let ã be the last sampled arm over time horizon T by π.With a slight abuse of notation, we use π for a modified strategy after T . Under a policy π, let R B i,j be the regret (summation of mean reward gaps) contributed by pulling the j-th bad arm in the i-th episode. Then letR B m G = m G i=1 j∈[m B i ] R B i,j, which is the regret from initially bad arms over the period of m G episodes. For getting R B m G , here we define the policy π after T such that it pulls T amounts for a good arm and zero for a bad arm. After T we can assume that there are no abrupt changes. For the last arm ã over the horizon T , it pulls the arm up to T amounts if ã is a good arm and ñGmG T < T . For i ∈ [m G ], j ∈ [m B i ] let n Gi and n B i,j be the number of pulling the good arm in i-th episode and j-th bad arm in i-th episode under π, respectively. Here we define n G i 's and n B i,j 's as follows:If ã is a good arm,n G i =    ñG i for i ∈ [ mG T -1] T for i = mG T 0 for i ∈ [m G ]/[ mG T ] , n B i,j = ñB i,j for i ∈ [ mG T ], j ∈ [ mB i,T ] 0 for i ∈ [m G ]/[ mG T ], j ∈ [m B i ]/[ mB i,T ].Otherwise,n G i =    ñG i for i ∈ [ mG T ] T for i = mG T + 1 0 for i ∈ [m G ]/[ mG T + 1] , n B i,j = ñB i,j for i ∈ [ mG T ], j ∈ [ mB i,T ] 0 for i ∈ [m G ]/[ mG T -1], j ∈ [m B i ]/[ mB i,T ].Using the above notation and newly defined π after T , we show that ifm G = S T + 1, then R B (T ) ≤ R B m G in the following. Lemma A.7. Under E 1 , when m G = S T we have R B,1 (T ) ≤ R B m G .Proof. There are S T -1 number of abrupt changes over T . We consider two cases; there are S T abrupt changes before sampling S T -th good arm or there are not. For the former case, if π samples the S T -th good arm and there are S T -1 number of abrupt changes before sampling the good arm, then it continues to pull the good arm until T . This is because when the algorithm samples a good arm a at time t ′ , from E 1 and the stationary period, we haveµ [t ′ ,t] (a) + 12 log(T )/n [t ′ ,t] (a) ≥ µ t ′ (a) ≥ 1 -δ.This implies that from the threshold condition, the algorithm does not stop pulling the good arm a. After T , from the definition of π for the case when ã is a good arm, n G mG T = T . Therefore, the algorithm pulls the good arm for T rounds. Now we consider the latter case, such that π samples the S T -th good arm before the S T -1-st abrupt change over T . Before sampling the S T -th good arm, there must exist two consecutive good arms such that there is no abrupt change between the two sampled good arms. This is a contraction because π must pull the first good arm among the two up to T under E 1 and S T -1-st abrupt change must occur after T . Therefore, it is enough to consider the former case. When m G = S T , we havei∈[m G ] n G i ≥ T, which implies R B,1 (T ) ≤ R B m G .From the above lemma, we set m G = S T . We analyze R B m G to get a bound for R B,1 (T ) in the following lemma. Lemma A.8. Under E 1 and policy π, we haveE R B m G = Õ max{S 1/(β+1) T T β/(β+1) , S T T } .Proof. Recall that we consider arms in A T /A S . Let a(i, j) be a sampled arm for j-th bad arm in the i-th episode and mT be the number of episodes from the policy π over the horizon T . Suppose that the algorithm samples arm a(i, j) at time t 1 (a(i, j)). Then the algorithm stops pulling arm a(i, j) at time t 2 (a(i, j)) + 1 if µ [s,t2(a(i,j))] (a) + 12 log(T )/n [s,t2(a(i,j))] (a) < 1 -δ for some s such that t 1 (a(i, j)) ≤ s ≤ t 2 (a(i, j)) and s = t 2 (a(i, j)) + 1 -2 l-1 for l ∈ Z + . For simplicity, we use t 1 and t 2 instead of t 1 (a(i, j)) and t 2 (a(i, j)) when there is no confusion. For the regret analysis, we consider that for t > t 2 , arm a is virtually pulled. With E 1 , we assume that t2 (≥ t 2 ) is the smallest time that there exists t 1 ≤ s ≤ t2 with s = t2 + 1 -2 l-1 for l ∈ Z + such that the following condition is met:EQUATIONFrom the definition of t2 , we observe that for given t2 , the time step s = s ′ satisfying (30) equals to t 1 (i.e. s ′ = t 1 ). Then, we can observe that n [s ′ , t2] (a(i, j)) = n [t1, t2] (a(i, j)) = ⌈C 2 log(T )/(∆ t1 (a(i, j)) -δ) 2 ⌉ for some constant C 2 > 0, which satisfies (30). Then from n [t1,t2] (a(i, j)) ≤ n [t1, t2] (a(i, j)), for all i ∈ [ mT ], j ∈ [ mB i,T ] we have n B i,j = Õ(1/(∆ t1 (a(i, j))δ) 2 ). We note that this bound for the number of pulling an arm holds for not only the case where the arm stops being pulled from the threshold condition but also the case where the arm stops being pulled from meeting an abrupt change (recall that abrupt changes are considered as sampling a new arm) or T . Then with the facts that nB i,j = 0 for i ∈ [m G ]/[ mT ], j ∈ [m B i ]/[ mB i,T ], we have, for any i ∈ [m G ] and j ∈ [m B i ], n B i,j = Õ(1/(∆ t1 (a(i, j)) -δ) 2 ). For 2δ < x ≤ 1, let b(x) = P(∆ t1 (a) = x|a is a bad arm). Then we have P(∆ t1 (a) = x|a is a bad arm) = P(∆ t1 (a) = x|∆ t1 (a) > 2δ) = P(∆ t1 (a) = x)/P(∆ 1 (a) > 2δ) = P(∆ t1 (a) = x)/(1 -C(2δ) β ) = O(P(∆ t1 (a) = x)), where the last equality comes from small δ with S T = o(T ).For any i ∈ [m G ], j ∈ [m B i ],we haveEQUATION)From the above results in (31),( 19),( 20),( 21),( 22), (23) , for β > 0 we haveE[R B i,j ] = Õ(max{1, δ β-1 }). Recall that R B m G = m G i=1 j∈[m B i ] R B i,j. With δ = max{(S T /T ) 1/(β+1) , (S T /T ) 1/2 } and m G = S T , from Lemma A.7 and the fact that m B i 's are i.i.d. random variables following geometricdistribution with E[m B i ] = 1/(2δ) β -1, we have E[R B m G ] = O   E   m G i=1 j∈[m B i ] R B i,j     = Õ S T 1 δ β max{1, δ β-1 } = Õ max{S 1/(β+1) T T β/(β+1) , S T T } . From Lemma A.8, we have E[R B,1 (T )] = E[R B m G ] = Õ max{S 1/(β+1) T T β/(β+1) , √ S T T } .Now we analyze R B,2 (T ) in the following lemma. Here, we consider arms in A B S , which is allowed to have negative mean rewards.Lemma A.9. Under E 1 and policy π, we haveE R B,2 (T ) = Õ max{S T /δ, VT } .Proof. Recall that we consider arms a ∈ A B S so that ∆ t1 (a) > 2δ from definition. Suppose that the arm a is sampled and pulled for the first time at time t 1 (a). Then the algorithm stops pulling arm a at time t 2 (a) + 1 if µ [s,t2(a)] (a) + 12 log(T )/n [s,t2(a)] (a) < 1 -δ for some s such that s ≤ t 2 (a) and s = t 2 (a) + 1 -2 l-1 for l ∈ Z + . For simplicity, we use t 1 and t 2 instead of t 1 (a) and t 2 (a) when there is no confusion. For regret analysis, we consider that for t > t 2 , arm a is virtually pulled. With E 1 , we assume that t2 (≥ t 2 ) is the smallest time that there exists t 1 ≤ s ≤ t2 with s = t2 + 1 -2 l-1 for l ∈ Z + such that the following condition is met:EQUATION)From the definition of t2 , we observe that for given t2 , the time step s, which satisfies (32), equals to t 1 . Then, we can observe that n [t1, t2] (a) = max{⌈C 2 log(T )/(∆ t1 (a) -δ) 2 ⌉, 1} for some constant C 2 > 0, which satisfies (32). From the above, for any a ∈ A B S satifying ∆ t1 (a) ≥ C 2 log(T ) + δ, we have n [t1, t2] (a) = 1. This implies that after pulling the arm a once, the arm is eliminated and after that, the arm is not pulled anymore. Therefore, for any arm a ′ which was rotted to a, we have∆ t1(a ′ ) (a ′ ) < C 2 log(T ) + δ. This is because otherwise such that ∆ t1(a ′ ) (a ′ ) ≥ C 2 log(T ) + δ,the arm a ′ is eliminated and a cannot be pulled which means a / ∈ A B S , which is a contradiction. Then for any arm a ∈ A B S , we have ∆ t1 (a) ≤ C 2 log(T ) + δ + ρ t1(a)-1 . Recall that we consider abrupt rotting of an arm as sampling a new arm. Let t(s) be the time step when the s-th abrupt rotting occurs. Then we note that ρ t1(a)-1 = ρ t(s) when arm a is a sampled arm from s-th abrupt rotting for s ∈ [S T ].From n [t1,t2] (a) ≤ n [t1, t2] (a), we have n [t1,t2] (a) = Õ(max{1/(∆ t1 (a) -δ) 2 , 1}). We note that this bound for number of pulling an arm holds for not only the case where the arm stops to be pulled from the threshold condition, but also the case where the arm stops to be pulled from meeting an abrupt change (recall that abrupt changes are considered as sampling a new arm) or T . From the definition of bad arms, we have ∆ t1 (a) ≥ 2δ. Then the regret from arm a, denoted by R(a), is bounded as follows: R(a) = ∆ t1 (a)n [t1,t2] (a) = Õ(max{∆ t1 (a)/(∆ t1 (a) -δ) 2 , ∆ t1 (a)}). Since x/(x -δ) 2 ≤ 2/δ for any x ≥ 2δ, we have R(a) = Õ(max{1/δ, ∆ t1 (a)}). Therefore, with the fact that ∆ t1 (a) ≤ C 2 log(T ) + δ + ρ t(s) for the corresponding s ∈ [S T ] such that ρ t1(a)-1 = ρ t(s) , we haveE   a∈A B S R(a)   = Õ   max    S T /δ, E   a∈A B S ∆ t1 (a)        = Õ(max{S T /δ, S T + S T s=1 E[ρ t(s) ]}) = Õ(max{S T /δ, S T s=1 E[ρ t(s) ]}) = Õ(max{S T /δ, VT }),where the second last equality comes from S T /δ ≥ S T .Finally, from R π (T ) = R G (T ) + R B (T ), (29), and Lemmas A.8, A.9, we have E[R π (T )] = Õ max{S 1/(β+1) T T β/(β+1A ′ ← A, w(δ ′ ) ← 1 for δ ′ ∈ B for i = 1, 2, . . . , ⌈T /H⌉ do t ′ ← (i -1)H + 1 Select a new arm a ∈ A ′ Pull arm a and get reward r (i-1)H+1 p(δ ′ ) ← (1 -α) w(δ ′ ) k∈B w(k) + α 1 B for δ ′ ∈ B Select δ ← δ ′ with probability p(δ ′ ) for δ ′ ∈ B for t = (i -1)H + 2, . . . , i • H ∧ T do if min s∈Tt(a) W U CB(a, s, t -1, H) < 1 -δ then A ′ ← A ′ /w(δ) ← w(δ) exp α Bp(δ) 1 2 + i•H∧T t=(i-1)H rt CH log(H)+4 √ H log T end forHere, we consider the case where there are constraints for both S T and V T , and parameters of V T , S T , and β are unknown to the agent. We note that VT ≤ V T from the constraint. The parameters of β, V T , and S T are used to set the optimal threshold parameter δ in Algorithm 1. Therefore, when the parameters are not given, the procedure to find the optimal value δ is required. We adopt the Bandit-over-Bandit (BoB) approach in Cheung et al. [11] , Kim et al. [13] by additionally considering adaptive window. In Algorithm 2, the algorithm consists of a master and several base algorithms with B. For the master, we use EXP3 We defineδ † V = max{(V T /T ) 1/(β+2) , (V T /T ) 1/3 , 1/H 1/(β+1) , 1/ √ H} and δ † S = max{(S T /T ) 1/(β+1) , (S T /T ) 1/2 , 1/H 1/(β+1) , 1/ √ H}.Then the optimized threshold parameter is δ † V S = min{δ † S , δ † V }. The optimized threshold parameter can be derived from the theoretical analysis in Appendix A.7. The target of the master is to find the parameter. From the above, we can observe that 1/√ H ≤ δ † V S ≤ 1. Therefore, we set B = {1/2, . . . , 1/2 log 2 √ H } which is the candidate values for unknown δ † .The regret is composed of two factors from the master and bases. To ensure that the regret bound from each base concerning V T and S T remains guaranteed irrespective of the bases chosen, we consider a constrained adaptive adversary. For the following, we consider that ϱ t for all t > 0 are arbitrarily determined before an algorithm is run, under the constraints of V T and S T whereT -1 t=1 ϱ t ≤ V T and 1 + T -1 t=1 1(ϱ t ̸ = 0) ≤ S T .Then under ϱ t for all t > 0, we consider the following adversary for rotting rates. Assumption A.10 (Constrained Adaptive Adversary). At each time t > 0, the value of rotting rate ρ t is determined arbitrarily immediately after the agent pulls an arm a t under the constraint of 0 ≤ ρ t ≤ ϱ t for given ϱ t . Remark A.11. Assumption A.10 is still more general than that for the maximum rotting rate constraint in Kim et al. [13] where ϱ t = ρ for all t > 0. We also observe that the constrained adaptive adversary in Assumption A.10 is milder than the adaptive adversary in Assumption 2.1. Additionally, we note that a special case of constraint ρ t = ϱ t for all t > 0 in Assumption A.10 represents an oblivious adversary because ϱ t 's are determined before an algorithm is run.With a time block size of H (where H = ⌈ √ T ⌉), the algorithm operates over ⌈T /H⌉ blocks. Denote by T i the set of time steps in the i-th block containing time steps of (i -1)H + 1 ≤ t ≤ iH ∧ T . It is possible to encounter large rotting for some i block, potentially resulting in an arm's mean reward having a significantly low negative value, leading to suboptimal behavior by the master incurring large regret from the master. To address this, we introduce the assumption of equally distributed cumulative rotting for blocks, stated as follows: Assumption A.12.t∈Ti ρ t ≤ H for all i ∈ [⌈T /H⌉] Remark A.13. As similarly highlighted in Remark 2.5, this assumption is satisfied when mean rewards are under the constraint of 0 ≤ µ t (a t ) ≤ 1 for all t ∈ [T ], which is frequently encountered in real-world applications where reward is represented by metrics like click rates or (normalized) ratings in content recommendation systems. Remark A.14. Our rotting scenario with t∈Ti ρ t ≤ H for all i ∈ [⌈T /H⌉] is more general in scope than the one with a maximum rotting rate constraint where ρ t ≤ ρ = o(1) for all t ∈ [T -1], which was explored in Kim et al. [13] . This is because for our setting, ρ t is not necessarily bounded by o(1), and for the maximum rotting constraint setting with ρ t ≤ ρ = o(1), the condition of t∈Ti ρ t ≤ H for all i ∈ [⌈T /H⌉] is always satisfied. It is noteworthy that Assumption A.12 implies Assumption 2.4.We provide a regret bound of Algorithm 2 under Assumption A.10 and Assumption A.12 in the following. Theorem A.15. Let R ′ V and R ′ S be defined asR ′ V := V 1 β+2 T T β+1 β+2 + T 2β+1 2β+2 f or β ≥ 1, V 1 3 T T 2 3 + T 3 4 f or 0 < β < 1 and R ′ S := max{S 1 β+1 T T β β+1 + T 2β+1 2β+2 , V T } f or β ≥ 1, max{ √ S T T + T 3 4 , V T } f or 0 < β < 1.Then, the policy π of Algorithm 2 with H = ⌈ √ T ⌉ achieves the following regret bound:E[R π (T )] = Õ(min{R ′ V , R ′ S })Proof. The proof is provided in Appendix A.7.We can observe that there is the additional regret cost of T (2β+1)/(2β+2) for β ≥ 1 or T 3/4 for 0 < β < 1 compared to Algorithm 1. This additional cost originates from the additional procedure to learn the optimal value of δ in Algorithm 2, which is negligible when V T and S T are large enough. We also note that the well-known black-box framework proposed for addressing nonstationarity [25] is not applicable to this problem because the UCB of the chosen arm in this context does not consistently surpass the optimal mean reward, violating the necessary assumption for the framework.Attaining the optimal regret bound under a parameter-free algorithm remains an unresolved issue.A.7 Proof of Theorem A.15: Regret Upper Bound of Algorithm 2In the following, we deal with the cases of (a)δ † V ≤ δ † S so that δ † V S = δ † V and (b) δ † V > δ † S so that δ † V S = δ † S , separately. A.7.1 Case of δ † V ≤ δ † S Let π i (δ ′) for δ ′ ∈ B denote the base policy for time steps between (i -1)H + 1 and i • H ∧ T in Algorithm 2 using 1 -δ ′ as a threshold. Denote by a πi(δ ′ ) tthe pulled arm at time step t by policy π i (δ ′ ). Then, for δ † ∈ B, which is set later for a near-optimal policy, we haveEQUATION)whereR π 1 (T ) = T t=1 1 - ⌈T /H⌉ i=1 i•H∧T t=(i-1)H+1 µ t (a πi(δ † ) t ) and R π 2 (T ) = ⌈T /H⌉ i=1 i•H∧T t=(i-1)H+1 µ t (a πi(δ † ) t ) - ⌈T /H⌉ i=1 i•H∧T t=(i-1)H+1 µ t (a π t ).Note that R π 1 (T ) accounts for the regret caused by the near-optimal base algorithm π i (δ † )'s against the optimal mean reward and R π 2 (T ) accounts for the regret caused by the master algorithm by selecting a base with δ ∈ B at every block against the base with δ † . In what follows, we provide upper bounds for each regret component. We first provide an upper bound for E[R π 1 (T )] by following the proof steps in Theorem 3.1. Then we provide an upper bound for E[R π 2 (T )]. We set H = ⌈T 1/2 ⌉ and δ † to be a smallest value in B which is larger than δ † V = max{(V T /T ) 1/(β+2) , (V T /T ) 1/3 , 1/H 1/(β+1) , 1/H 1/2 }. Remark A.16. One might wonder whether R π 1 (T ), regret from the near-optimal base of δ † , satisfies the constraint of V T and S T even though the master may not select the near-optimal base in the algorithm for each block. From Assumption A.10, we can guarantee the constraints of V T and S T for rotting rates from each base regardless of the selected bases from the master for each block because the rotting upper bound ϱ t 's are determined before staring the game regardless of the behavior of the master. Therefore, we can utilize V T and S T for bounding R π 1 (T ), which is the regret from the near-optimal base of δ † .Upper Bounding E[R π 1 (T )].We refer to the period starting from time step (i -1)H + 1 to time step i • H ∧ T as the i-th block. For any i ∈ ⌈(T /H) -1⌉, policy π i (δ † ) runs over H time steps independent to other blocks so that each block has the same expected regret and the last block has a smaller or equal expected regret than other blocks. Therefore, we focus on finding a bound on the regret from the first block equal toH t=1 1 -µ t (a π1(δ † ) t). We define an arm a as a good arm if ∆(a) ≤ δ † /2, a near-good arm if δ † /2 < ∆(a) ≤ 2δ † , and otherwise, a is a bad arm. In A, let ā1 , ā2 , . . . , be a sequence of arms, which have i.i.d. mean rewards following (1) . Without loss of generality, we assume that the policy samples arms in the sequence of ā1 , ā2 , . . . , .Denote by A(i) the set of selected (explored) arms in the i-th block, which satisfies |A(i)| ≤ H. WLOG, we consider the case of given A(i) for the following because the proof can be applied to any given A(i). Let µ [t1,t2] (a) = t2 t=t1 µ t (a)/n [t1,t2] (a). We define the event (6) , we haveE 1 = {| µ [s1,s2] (a) - µ [s1,s2] (a)| ≤ 12 log(H)/n [s1,s2] (a) for all 1 ≤ s 1 ≤ s 2 ≤ H, a ∈ A(i)}. As inP(E c 1 ) ≤ 2/H 2 .over time horizon H. For the last arm ã over the horizon H, it pulls the arm until its total variation becomes max{δ† /2, V H (ã)} if ã is a good arm. For i ∈ [m G ], j ∈ [m B i ] let V Gi and V B i,j be the total rotting variation of pulling the good arm in i-th episode and j-th bad arm in i-th episode from the policy, respectively. Here we define V G i 's and V B i,j 's as follows: If ã is a good arm,V G i = V H (a(i)) for i ∈ [ mG H -1] max{δ † /2, V H (a(i))} for i ∈ [m G ]/[ mG H -1] , V B i,j = V H (a(i, j)) for i ∈ [ mG H ], j ∈ [ mB i,H ] 0 for i ∈ [m G ]/[ mG H ], j ∈ [m B i ].Otherwise,V G i = V H (a(i)) for i ∈ [ mG H ] δ † /2 for i ∈ [m G ]/[ mG H ] , V B i,j = V H (a(i, j)) for i ∈ [ mG H ], j ∈ [ mB i,H ] 0 for i ∈ [m G ]/[ mG H -1], j ∈ [m B i ]/[ mB i,H ]. For i ∈ [m G ], j ∈ [m B i ] let n B i,jbe the number of pulling the good arm in i-th episode and j-th bad arm in i-th episode from the policy, respectively. We define n H (a) be the total amount of pulling arm a over H. Here we define n B i,j 's as follows:n B i,j = n H (a(i, j)) for i ∈ [ mG H ], j ∈ [ mB i,H ] 0 for i ∈ [m G ]/[ mG H ], j ∈ [m B i ].Then we providem G such that R B (H) ≤ R B m G in the following lemma. Lemma A.19. Under E 1 , when m G = ⌈2V H,1 /δ † ⌉ we have R B (H) ≤ R B m G .Proof. We can easily show the theorem by following the proof steps of Lemma A.3From the result of Lemma A.19, we set m G = ⌈2V H,1 /δ † ⌉. In the following, we anlayze R B m G for obtaining a regret bound for R B (H). Lemma A. 20 . Under E 1 and policy π, we haveE[R B m G ] = Õ max{V H,1 (T /V T ) (β+1)/(β+2) + (T /V T ) β/(β+2) , V H,1 (T /V T ) 2/3 + (T /V T ) 1/3 } .Proof. We can easily prove the theorem by following proof steps in Lemma A.4. From (24) , for anyi ∈ [m G ], j ∈ [m B i ],we haveE[R B i,j ] ≤ E ∆(a(i, j))n B i,j + V B i,j n B i,j = Õ max{1, (δ † ) β-1 } + E[V B i,j ]/(δ † ) 2 . Recall that R B m G = m G i=1 j∈[m B i ] R B i,j . With δ † = max{(V T /T ) 1/(β+2) , (V T /T ) 1/3 } and m G = ⌈2V H,1 /δ † ⌉, from the fact that m B i 's are i.i.d. random variables with geometric distribution with E[m B i ] = 1/(2δ † ) β -1, we have E[R B m G ] = O   E   m G i=1 j∈[m B i ] R B i,j     = Õ (E[V H,1 ]/δ † + 1) 1 (δ † ) β max{1, (δ † ) β-1 } + E[V H,1 ]/(δ † ) 2 = Õ max E[V H,1 ] (δ † ) β+1 , E[V H,1 ] (δ † ) 2 + max 1 (δ † ) β , 1 δ † = Õ max{E[V H,1 ](T /V T ) (β+1)/(β+2) + (T /V T ) β/(β+2) , E[V H,1 ](T /V T ) 2/3 + (T /V T ) 1/3 } . From R π1(δ † ) (H) = R G (H) + R B (H) and Lemmas A.17, A.19, A.20, with δ † = max{(V T /T ) 1/(β+2) , (V T /T ) 1/3 } we have E[R π1(δ † ) (H)] = Õ max E[V H,1 ](T /V T ) (β+1)/(β+2) + H(V T /T ) 1/(β+2) + (T /V T ) β/(β+2) , E[V H,1 ](T /V T ) 2/3 + H(V T /T ) 1/3 + (T /V T ) 1/3 + H 2/3 E[V 1/3 H,1 ] .The above regret bound is for the first block. Therefore, by summing regrets from ⌈T /H⌉ number of blocks, from V T > max{T /H (β+2)/(β+1) , T /H 3/2 }, H = ⌈T 1/2 ⌉ and the fact that E[ T -1 t=1 ρ t ] ≤ V T , using Hölder's inequality we have shown thatEQUATIONNow, we consider the case where V T ≤ max{T /H 3/2 , T /H (β+2)/(β+1) }. In this case, we have 21 . Under E 1 and policy π, we haveδ † = max{1/ √ H, 1/H 1 β+1 }. From the result of Lemma A.19, by setting m G = ⌈2V H,1 /δ † ⌉ we have R B (H) ≤ R B m G . Lemma A.E[R B m G ] = Õ max{V H,1 (T /V T ) (β+1)/(β+2) + (T /V T ) β/(β+2) , V H,1 (T /V T ) 2/3 + (T /V T ) 1/3 } .Proof. We can easily prove the theorem by following proof steps in Lemma A.4. From (24) , for anyi ∈ [m G ], j ∈ [m B i ],we haveE[R B i,j ] ≤ E ∆(a(i, j))n B i,j + V B i,j n B i,j = Õ max{1, δ β-1 } + E[V B i,j ]/δ 2 . Recall that R B m G = m G i=1 j∈[m B i ] R B i,j . With δ † = max{1/H 1/2 , 1/H 1/(β+1) } and m G = ⌈2V H,1 /δ † ⌉, from the fact that m B i 's are i.i.d. random variables with geometric distribution with E[m B i ] = 1/(2δ † ) β -1, we have E[R B m G ] = O   E   m G i=1 j∈[m B i ] R B i,j     = Õ (E[V H,1 ]/δ † + 1) 1 (δ † ) β max{1, (δ † ) β-1 } + E[V H,1 ]/(δ † ) 2 = Õ max E[V H,1 ] (δ † ) β+1 , E[V H,1 ] (δ † ) 2 + max 1 (δ † ) β , 1 δ † = Õ E[V H,1 ]H + max{H β/(β+1) , H 1/2 } . From R π1(δ † ) (H) = R G (H) + R B (H) and Lemmas A.17, A.19, A.21, with δ † = Θ(max{1/H 1/2 , 1/H 1/(β+1) }) we have E[R π1(δ † ) (H)] = Õ max{H β/(β+1) , H 1/2 } + H 2/3 E[V 1/3 H,1 ] + E[V H,1 ]H .Therefore, by summing regrets from ⌈T /H⌉ number of blocks and from V T = O(max{T /H 3/2 , T /H (β+2)/(β+1) }), H = ⌈T 1/2 ⌉, and the fact that length of time steps in each block is bounded by H, we haveEQUATIONwhere the second equality comes from Hölder's inequality.From (34) and (35), we haveEQUATIONUpper Bounding E[R π 2 (T )]. We observe that the EXP3 is run for ⌈T /H⌉ decision rounds and the number of policies (i.e. π i (δ ′ ) for δ ′ ∈ B) is B. Denote the maximum absolute sum of rewards of any block with length H by a random variable Q ′ . We first provide a bound for Q ′ using concentration inequalities. For any block i, we haveEQUATIONDenote by T i the set of time steps in the i-th block. We define the eventE 2 (i) = {| µ [s1,s2] (a) - µ [s1,s2] (a)| ≤ 14 log(H)/n [s1,s2] (a), for all s 1 , s 2 ∈ T i , s 1 ≤ s 2 , a ∈ A(i)} and E 2 = i∈[⌈T /H⌉] E 2 (i). From Lemma A.29, with H = ⌈ √ T ⌉ we have P(E c 2 ) ≤ i∈[⌈T /H⌉] 2H 3 H 6 ≤ 2 T .By assuming that E 2 holds true, we can get a lower bound for µ t (a π t ), which may be a negative value from rotting, for getting an upper bound for | i•H∧T t=(i-1)H+1 µ t (a π t )|. We can observe that i•H∧T t=(i-1)H+1 µ t (a π t ) ≤ H. Therefore the remaining part is to get a lower bound for i•H∧T t=(i-1)H+1 µ t (a π t ). For the proof simplicity, we consider that when an arm is rotted, then the arm is considered as a different arm after rotting. For instance, when arm a is rotted at time s, then arm a is considered as a different arm a ′ after s. Therefore, each arm can be considered to be stationary. The set of arms is denoted by L. We denote by L + the set of arms having µ t (a) ≥ 0 for a ∈ L. We first focus on the arms in L/L + . Let δ max denote the maximum value in B so that δ max = 1/2. With E 2 and a ∈ L/L + , we assume that t2 (≥ t 2 ) is the smallest time that there exists t 1 ≤ s ≤ t2 with s = t2 + 1 -2 l-1 for l ∈ Z + such that the following condition is met:EQUATIONFrom the definition of t2 , we observe that for given t2 , the time step s, which satisfies (38), equals to t 1 . Then, we can observe that n µ t (a t ) ≥ -max{C 4 H log(H), H + V H,i }, which implies that from V H,i ≤ H under Assumption A.12, for some C 5 > 0, we have P (E 3 (i) c ) ≤ 2 T 2 .Then, under E 2 ∩ E 3 , with (37), we haveQ ′ ≤ max{C 5 H log H, H} + 2 H log(T ) ≤ C 5 H log H + 2 H log(T ), which implies 1/2+ i•H∧T t=(i-1)H r t /(C 5 H log H +4 √ H log T ) ∈ [0, 1]or some large enough C > 0. With the rescaling and translation of rewards in Algorithm 2, from Corollary 3.2. in Auer et al. [2] , we haveEQUATIONRemark A.22. Regarding the utilization of the regret analysis of Corollary 3.2 (EXP3) in Auer et al. [2] , we note that the reward for each base can be defined independently of the actual master's action. One might wonder whether the regret analysis for EXP3 can be utilized, considering the fact that the reward from a selected base may depend on the master's action due to the adaptive rotting rates. However, we highlight that the critical aspect of applying EXP3 analysis is whether the rewards from each base are defined independently of the actual action of the master, rather than whether the received (observed) reward from the selected base depends on the master's action. We can construct rewards for each base δ ∈ B at time t when a block starts, denoted as x t (δ), as the reward obtained when the master selects base δ (even though base δ is not actually selected from the algorithm). Then, we can define x t (δ) for each δ regardless of the master's actual action. In other words, irrespective of the actually selected base, we define x t (δ) for all δ ∈ B as the reward that the master can obtain by selecting δ. In such a case, whatever the selected base by the master is at time t, x t (δ)'s remain the same, respectively. This construction is feasible because it's solely for analytical purposes and not necessary for the algorithm's functioning. With this construction of reward for each base, we can utilize EXP3 analysis to obtain a regret bound regarding the master (R π 2 (T )). Note that the expected regret from EXP3 is trivially bounded by o(H 2 (T /H)) = o(T H) and B = O(log(T )). Then, with (39), we haveEQUATIONFinally, from (33), (36), and (40), with H = T 1/2 , we haveE[R π (T )] = Õ max V 1 β+2 T T β+1 β+2 + T 2β+1 2β+2 , V 1 3 T T 2 3 + T 3 4, which concludes the proof.A.7.2 Case of δ † V > δ † SLet π i (δ ′ ) for δ ′ ∈ B denote the base policy for time steps between (i -1)H + 1 and i • H ∧ T in Algorithm 2 using 1 -δ ′ as a threshold. Denote by a πi(δ ′ ) tthe pulled arm at time step t by policy π i (δ ′ ). Then, for δ † ∈ B, which is set later for a near-optimal policy, we haveEQUATIONwhereR π 1 (T ) = T t=1 1 - ⌈T /H⌉ i=1 i•H∧T t=(i-1)H+1 µ t (a πi(δ † ) t ) and R π 2 (T ) = ⌈T /H⌉ i=1 i•H∧T t=(i-1)H+1 µ t (a πi(δ † ) t ) - ⌈T /H⌉ i=1 i•H∧T t=(i-1)H+1µ t (a π t ).Note that R π 1 (T ) accounts for the regret caused by the near-optimal base algorithm π i (δ † )'s against the optimal mean reward and R π 2 (T ) accounts for the regret caused by the master algorithm by selecting a base with δ ∈ B at every block against the base with δ † . In what follows, we provide upper bounds for each regret component. We first provide an upper bound for E[R π 1 (T )] by following the proof steps in Theorem 3.3. Then we provide an upper bound for E[R π 2 (T )]. We set δ † to be a smallest value in B which is larger than δ † S = max{(S T /T ) 1/(β+1) , 1/H 1/(β+1) , (S T /T ) 1/2 , 1/H 1/2 } such that we have δ † = Θ(max{(S T /T ) 1/(β+1) , 1/H 1/(β+1) , (S T /T ) 1/2 , 1/H 1/2 }).Upper Bounding E[R π 1 (T )]. We refer to the period starting from time step (i -1)H + 1 to time step i • H ∧ T as the i-th block. For any i ∈ ⌈T /H -1⌉, policy π i (δ † ) runs over H time steps independent to other blocks so that each block has the same expected regret and the last block has a smaller or equal expected regret than other blocks. Therefore, we focus on finding a bound on the regret from the first block equal toH t=1 1 -µ t (a π1(δ † ) t). We define an arm a as a good arm if ∆ t (a) ≤ δ † /2, a near-good arm if δ † /2 < ∆ t (a) ≤ 2δ † , and otherwise, a is a bad arm at time t. In A, let ā1 , ā2 , . . . , be a sequence of arms, which have i.i.d. mean rewards following (1) . For analysis, we consider abrupt change as sampling a new arm. In other words, if a sudden change occurs to an arm a by pulling the arm a, then the arm is considered to be two different arms; before and after the change. The type of abruptly rotted arms (good, near-good, or bad) after the change is determined by the rotted mean reward. Without loss of generality, we assume that the policy samples arms, which are pulled at least once, in the sequence of ā1 , ā2 , . . . , .Denote by A(i) the set of sampled arms, which are pulled at least once, in the i-th block, which satisfies |A(i)| ≤ H. We also define A S (i) as a set of arms that have been rotted and pulled at least once in the i-th block, which satisfies |A S (i)| ≤ S i , where S i is defined as the number of abrupt changes in the i-th block. Let µ [t1,t2] (a) = t2 t=t1 µ t (a)/n [t1,t2] (a). We define the eventE 1 = {| µ [s1,s2] (a) -µ [s1,s2] (a)| ≤ 12 log(H)/n [s1,s2] (a) for all 1 ≤ s 1 ≤ s 2 ≤ H, a ∈ A(i)}.From Lemma A.29, as in (6), we haveP(E c 1 ) ≤ 2/H 2 . For the case that E 1 does not hold, the regret is E[R π (H)|E c 1 ]P(E c 1 ) = O(1), which is negligible comparing with the regret when E 1 holds true which we show later. Therefore, in the rest of the proof we assume that E 1 holds true.In the following, we first provide a regret bound over the first block.For regret analysis, we divide R π1(δ † ) 1 (H) into two parts, R G (H) and R B (H) corresponding to regret of good or near-good arms, and bad arms over time T , respectively, such that R π 1 (H) = R G (H) + R B (H). We can easily obtain thatEQUATIONfrom ∆(a) ≤ 2δ † for any good or near-good arms a.Now we analyze R B (H). We divide regret R B (H) into two regret from bad arms in A(1)/A S (1), denoted by R B,1 (H), and regret from bad arms in A S (1), denoted by R B,2 (H) such that R B (H) = R B,1 (H) + R B,2 (H). We first analyze R B,1 (H) in the following. We consider arms in A(1)/A S (1).For the proof, we adopt the episodic approach in Kim et al. [13] for regret analysis. In the following, we introduce some notation. Here we only consider arms in A(1)/A S (1) so that the following notation is defined without considering (rotted) arms in A S (1) . Given a policy sampling arms in the sequence order, let m G be the number of samples of distinct good arms and m B i be the number of consecutive samples of distinct bad arms between the i -1-st and i-th sample of a good arm among m G good arms. We refer to the period starting from sampling the i -1-st good arm before sampling the i-th good arm as the i-th episode. Observe that m B 1 , . . . , m B m G 's are i.i.d. random variables with geometric distribution with parameter 2δ † , conditional on the value of m G . Therefore,P(m B i = k) = (1 -2δ † ) k 2δ † , for i = 1, . . . , m G . Define mGH to be the total number of samples of a good arm by the policy π 1 (δ † ) over the horizon H and mB i,H to be the number of selections of a bad arm in the i-th episode by the policy π over the horizon H. For i ∈ [ mG H ], j ∈ [ mB i,H ], let ñG i be the number of pulls of the good arm in the i-th episode and ñB i,j be the number of pulls of the j-th bad arm in the i-th episode by the policy π 1 (δ † ) over the horizon H. Let ã be the last sampled arm over time horizon H by π 1 (δ † ).With a slight abuse of notation, we use π 1 (δ † ) for a modified strategy after H. Under a policy π 1 (δ † ), let R B i,j be the regret (summation of mean reward gaps) contributed by pulling the j-th bad arm in the i-th episode. Then letR B m G = m G i=1 j∈[m B i ] R B i,j, which is the regret from initially bad arms over the period of m G episodes. For getting R B m G , here we define the policy π 1 (δ † ) after H such that it pulls H amounts for a good arm and zero for a bad arm. After H we can assume that there are no abrupt changes. For the last arm ã over the horizon H, it pulls the arm up to H amounts if ã is a good arm and ñGmG H < H. For i ∈ [m G ], j ∈ [m B i ] let n Gi and n B i,j be the number of pulling the good arm in i-th episode and j-th bad arm in i-th episode under π, respectively. Here we define n G i 's and n B i,j 's as follows: If ã is a good arm,n G i =    ñG i for i ∈ [ mG H -1] H for i = mG H 0 for i ∈ [m G ]/[ mG H ] , n B i,j = ñB i,j for i ∈ [ mG H ], j ∈ [ mB i,H ] 0 for i ∈ [m G ]/[ mG H ], j ∈ [m B i ]/[ mB i,H ].Otherwise,n G i =    ñG i for i ∈ [ mG H ] H for i = mG H + 1 0 for i ∈ [m G ]/[ mG H + 1] , n B i,j = ñB i,j for i ∈ [ mG H ], j ∈ [ mB i,H ] 0 for i ∈ [m G ]/[ mG H -1], j ∈ [m B i ]/[ mB i,H ].With a slight abuse of notation, we define S i to be the number of abrupt changes in i-th block. Then, we show that ifm G = S 1 , then R B,1 (H) ≤ R B m G . Lemma A.23. Under E 1 , when m G = S 1 we have R B,1 (H) ≤ R B m G .Proof. There are at most S 1 -1 number of abrupt changes over the first block H. We consider two cases; there are S 1 -1 abrupt changes before sampling S 1 -th good arm or not. For the first case, if π 1 (δ † ) samples the S 1 -th good arm and there are S 1 -1 number of abrupt changes before sampling the good arm, then it continues to pull the good arm for H rounds from E 1 and the definition of π 1 (δ † ) after H. Now we consider the second case. If π 1 (δ † ) samples the S 1 -th good arm before T and there is at least one abrupt change after sampling the arm, then before sampling the S 1 -th good arm, there must exist two consecutive good arms such that there is no abrupt change between sampling the two good arms.Finally, from (41), (44), and (45), with the fact thatS T s=1 E[ρ t(s) ] ≤ V T , H = T 1/2, and δ † = Θ(max{(S T /T ) 1/(β+1) , 1/H 1/(β+1) , (S T /T ) 1/2 , 1/H 1/2 }), we haveE[R π (T )] = Õ T δ † + (T /H + S T ) max{1/(δ † ) β , 1/δ † } + √ HT + S T s=1 E[ρ t(s) ] = Õ T δ † + max{T /H, S T } max{1/(δ † ) β , 1/δ † } + √ HT + S T s=1 E[ρ t(s) ] = Õ 2T δ † + √ HT + S T s=1 E[ρ t(s) ] = Õ max{S 1/(β+1) T T β/(β+1) + T (2β+1)/(2β+2) , S T T + T 3/4 , V T } ,which concludes the proof.A.8 Proof of Theorem 4.1: Regret Lower Bound for Slowly Rotting RewardsWe first consider the case when V T = Θ(T ). Recall that ∆ 1 (a) = 1 -µ 1 (a). Then for any randomly sampled a ∈ A, we haveE[µ 1 (a)] ≥ yP(µ 1 (a) ≥ y) = yP(∆ 1 (a) < 1 -y) for y ∈ [0, 1]. Then with y = 1/2, we have E[µ 1 (a)] ≥ (1/2)P(∆ 1 (a) < (1/2)) = Θ(1) from constant β > 0 and (1). Then with E[µ 1 (a)] ≤ 1, we have E[µ 1 (a)] = Θ(1). We then think of a policy π ′ that randomly samples a new arm and pulls it once every round. Since E[µ 1 (a)] = Θ(1) for any randomly sampled a, we have E[R π ′ (T )] = Θ(T ). Next, we think of any policy π ′′ except π ′ . Then any policy π ′′ must pull an arm a at least twice. Let t ′ and t ′′ be the rounds when the policy pulls arm a. If we consider ρ t ′ = V T then such policy has Ω(V T ) regret bound. Since V T = Θ(T ), any algorithm has Ω(T ) in the worst case. Therefore we can conclude that any algorithm including π ′ has a regret bound of Ω(T ) in the worst case, which concludes the proof for V T = Θ(T ).Now we think of the case where V T = o(T ). For the lower bound, we adopt the proof methodology of Theorem 1 in Kim et al. [13] by making necessary adjustments to accommodate V T and β. We note that since higher β implies a reduced chance of sampling a near-optimal arm, the criteria for defining the mean rewards of near-optimal arms becomes less stringent for higher β, which does not appear in the previous work. We first categorize arms as either bad or good according to their initial mean reward values. For the categorization, we utilize two thresholds in the proof as follows. Consider 0 < γ < c < 1 for γ, which will be specified, and a constant c. Then the value of 1 -γ represents a threshold value for identifying good arms, while 1 -c serves as the threshold for identifying bad arms. We refer to arms a satisfying µ 1 (a) ≤ 1 -c as 'bad' arms and arms a satisfying µ 1 (a) > 1 -γ as 'good' arms. We also consider a sequence of arms in A denoted by ā1 , ā2 , . . . . Given a policy π, without loss of generality, we can assume that π selects arms according to the order of ā1 , ā2 , . . . . For the rotting rates, we define ϱ = V T /(T -1). Then we consider ρt = ϱ for all t ∈ [T -1] so that T -1 t=1 ρ t = V T . Case of V T = O(1/T 1/(β+1) ): When V T = O(1/T 1/(β+1)), the lower bound of order T β β+1 for the stationary case, from Theorem 3 in Wang et al. [24] , is tight enough for the non-stationary case. From Theorem 3 in Wang et al. [24] , we haveEQUATIONWe note that even though the mean rewards are rotting in our setting, Theorem 3 in Wang et al. [24] remains applicable without requiring any alterations in the proofs providing a tight regret bound for the near-stationary case. For the sake of completeness, we provide the proof of the theorem in the following. Let K 1 denote the number of bad arms a that satisfy µ 1 (a) ≤ 1 -c before sampling the first good arm, which satisfies µ 1 (a) > 1 -γ, in the sequence of arms ā1 , ā2 , . . . . Let µ be the initial mean reward of the best arm among the sampled arms by π over time horizon T . Then for some κ > 0, we haveEQUATIONProof. Let X i for i > 0 be Bernoulli random variables with success probability γ. From Section 2 in Brown [9] , we haveEQUATIONFrom (53) and Lemma A.28, for any 1/2 + γ/m < α < 1 we haveP K m ≤ αm 1 γ -m = P K m ≤ αm 1 γ -m = P    ⌊αm 1 γ ⌋ i=1 X i ≥ m    ≤ exp - (1 -1/α) 2 3 αm 1 γ γ ≤ exp - (1 -1/α) 2 3 (αm -γ) ,in which the first inequality comes from Lemma A.28, which concludes the proof.From Lemma A.26 with α = 1 -1/ √ m and large enough T , we haveEQUATIONTherefore, from (52) and (54), we haveEQUATIONFinally, from (46) and (55), we conclude that for any policy π, we have Now we consider the case of S T = o(T ) and S T ≥ 2. We initially provide a regret bound with respect to the cumulative rotting amount of VT . We first think of a policy π that randomly samples a new arm and pulls it once every round. Then for any randomly sampled a ∈ A, we have E[µ 1 (a)] = Θ(1). Then from constant β > 0, E[R π (T )] = Ω(T ). Then there always exists ρ t 's satisfying T -1 t=1 ρ t = T , which implies E[R π (T )] = Ω(T ) = Ω( VT ). Now we think of any nontrivial algorithm which must pull an arm a at least twice. Let t ′ and t ′′ be the rounds when the policy pulls arm a (t ′ < t ′′ ). If we consider ρ t ′ > 0 and ρ t = 0 for tEQUATION∈ [T -1]/{t ′ } in which ρ t ′ = T -1 t=1 ρ t and 1 + T -1 t=1 ρ t 1(ρ t ̸ = 0) ≤ S T , then such policy has R π (T ) = Ω( T -1t=1 ρ t ) regret bound because, at time t ′′ , it pulls the arm a rotted by ρ t ′ . Therefore, for any policy π, there always exist a rotting rate adversary satisfying the following expected regret bound ofEQUATIONNext, for the regret bound with respect to S T , we follow the proof steps in Theorem 4.1. However, the regret bound of S T does not depend on the magnitude of rotting rates but on the number of rotting instances. To address this, we need to design a new worst-case in which an adversary makes near-optimal arms rotted to be sub-optimal arms abruptly rather than gradually. We first categorize arms as either bad or good according to their initial mean reward values. For the categorization, we utilize two thresholds in the proof as follows. Consider 0 < γ < c < 1 for γ, which will be specified, and a constant c. Then the value of 1 -γ represents a threshold value for identifying good arms, while 1 -c serves as the threshold for identifying bad arms. We refer to arms a satisfying µ 1 (a) ≤ 1 -c as 'bad' arms and arms a satisfying µ 1 (a) > 1 -γ as 'good' arms. We also consider a sequence of arms in A denoted by ā1 , ā2 , . . . . Given a policy π, without loss of generality, we can assume that π selects arms according to the order of ā1 , ā2 , . . . . Let K m denote the number of bad arms a that satisfy µ 1 (a) ≤ 1 -c before sampling m-th good arm, which satisfies µ 1 (a) > 1 -γ, in the sequence of arms ā1 , ā2 , . . . . Let N T be the number of sampled good arms a such that µ 1 (a) > 1 -γ until T .We can decompose R π (T ) into two parts as follows:EQUATIONWe set m = S T and γ = (S T /T ) 1/(β+1) with S T = o(T ). For getting a lower bound for the first term in (57), R π (T )1(N T < m), we consider the fact that the minimal regret is obtained from the situation where there are m -1 arms whose mean rewards are 1. In such a case, the optimal policy must sample the best m -1 arms until their mean rewards become equal to or below the threshold value of 1 -γ (step 1) and then samples the best arm at each time for the remaining time steps (step 2). In step 1, when the optimal policy pulls an optimal arm, we can think of the case when the mean reward of the arm is abruptly rotted to the value of 1 -γ. This implies that the required number of rounds for step 1 is m -1. The regret from step 2 is R = Ω((T -m + 1)γ) = Ω(S 1/(β+1) TT β/(β+1) ), in which the optimal policy pulls arms which mean rewards are below or equal to 1 -γ for the remaining time after step 1. Therefore, we have R π (T )1(N T < m) = Ω(R1(N T < m)) = Ω(S 1/(β+1) T T β/(β+1) 1(N T < m)).(58) For getting the above, we note that there always exists ρ t 's satisfying ≥ Ω(S 1/(β+1) TT β/(β+1) P(K m ≥ κ)).(61)Next we provide a lower bound for P(K m ≥ κ). Observe that K m follows a negative binomial distribution with m successes and the success probability P(µ 1 (a) > 1 -γ)/P(µ 1 (a) / ∈ (1 -c, 1γ]) = γ, in which the success probability is the probability of sampling a good arm given that the arm is either a good or bad arm. We recall Lemma A.26 for a concentration inequality for K m in the following. Lemma A.27. For any 1/2 + γ/m < α < 1,P(K m ≥ αm(1/γ) -m) ≥ 1 -exp(-(1/3)(1 -1/α) 2 (αm -γ)).From Lemma A.27 with α = 1 -1/ √ m + 3 and large enough T , we haveEQUATIONwhere the last inequality comes from m/(m + 3) = (S T )/(S T + 3) ≥ 1/4 and √ m + 3/( √ m + 3 -1) ≥ 1. Therefore, from (61) and (62), we haveEQUATIONOverall from (56) and (63), for any π, there exist ρ t 's such that E[R π (T )] = Ω(max{S 1/(β+1) TT β/(β+1) , V T }). We compare the experiment results of our algorithm with the theoretical results in Corollary 3.4 and Theorem A.15. We follow the same setting in Fig 5 (a) so that the theoretical bounds are T 2/3 log(T ) and T 2/3 log(T ) + T 3/4 log(T ) for Algorithms 1 and 2, respectively, including logarithmic factors with constant terms set to 1. In Figure 5 , the experiment results outperform the theoretical bounds, which is expected since the theoretical bounds represent worst-case scenarios, while the experiments reflect a specific instance.Lemma A.28 (Theorem 6.2.35 in Tsun [22] ). Let X 1 , . . . , X n be identical independent Bernoulli random variables. Then, for 0 < ν < 1, we haveP n i=1 X i ≥ (1 + ν)E n i=1 X i ≤ exp - ν 2 E[ n i=1 X i ] 3 .Lemma A.29 (Corollary 1.7 in Rigollet and Hütter [18] ). Let X 1 , . . . , X n be independent random variables with σ-sub-Gaussian distributions. Then, for any a = (a 1 , . . . , a n ) ⊤ ∈ R n and t ≥ 0, we haveP n i=1 a i X i > t ≤ exp - t 2 2σ 2 ∥a∥ 2 2 and P n i=1 a i X i < -t ≤ exp - t 2 2σ 2 ∥a∥ 2 2 .• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.Justification: We have reviewed the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).This assertion follows from the fact that for any ϵ > 0, there exists an arm a in A excluding rotted arms such that ∆1(a) < ϵ with probability 1, as limn→∞(1 -P(∆1(a) ≥ ϵ) n ) = 1.S Ti=1 E[µ 1 (a)] = Ω(S T ) = Ω(T ), which concludes the proof for S T = Θ(T ). 


Decision: This paper considers the many-armed bandit problem where the arms rewards may drop as one draws them. The paper considers two regimes (slow and abrupt rottings). The problem setting of this paper generalizes Kim et al. [13] for general beta (top-arm ratio) and variation budget. They propose sliding-UCB-based algorithms and analyze them for the two regimes. They also provided a lower bound that is tight for $\beta > 1$. The main strength of this paper is its adaptivity against a general setting with a single algorithm. Regarding the motivation based on real-world, sentiment is mixed (generally positive). The weaknesses of this paper, suggested by the reviewers, are mainly due to the requirement for the variation size ($S_T$ or $V_T$), which is partially addressed in Algorithm 2 with additional assumptions). The score of this paper is on the margin. The overall sentiment is positive about the paper. In the discussion phase, some of the reviewers suggest consideration of existing work (such as the replay phase method by Chen et al. [2019] or Auer et al. [2018]). Even though the complexity of the method on Chen et al. is relatively high.

Reviews: review: paper_summary: paper_summary: The paper studies infinite-armed bandits with rotting rewards. They show a lower bound on regret in terms of the total-variation and number of abrupt changepoints in the change in rewards. They also provide regret upper bounds: (1) a UCB-like algorithm tuned with knowledge of problem parameters gets optimal regret in some regimes and (2) a parameter-free bandit-over-bandit algorithm can attain optimal regret in some regimes when the level of non-stationarity is large.
strength_weakness: strength_weakness: * 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 $\rho_t$ depends on the chosen arm $\rho_t$ and is thus random (in fact, determined by an adaptive adversary according to Assumption 2.1). But, meanwhile, $V_T,S_T$ seem to be treated as deterministic constants in the whole paper given that they are, for example, used to tune Algorithm 1 to get the best regret bounds. In fact, it would not even make sense for $V_T,S_T$ to _appear_ in the expected regret bounds if they were random. So, the only way the results of this work can rigorously hold is if $V_T,S_T$ bound the respective random quantities $\sum_{t=1}^{T_1} \rho_t$ and $1 + \sum_{t=1}^{T-1} 1\{\rho_t\neq 0\}$ for all realizations of the randomness, which then means there are some missing assumptions for the results of this paper. For instance, even for a "nice" algorithm, $\sum_{t=1}^{T_1} \rho_t$ could be very large with some probability in which case $V_T$ is forced to be large as well because of a "bad realization". The only other way around this is to make further assumptions about the adversary/design of non-stationarity. In either case, there should be more discussion as the rigor of results presented versus the given assumptions seems unclear to me.
*  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.
questions: questions: Please refer to strengths and weaknesses above.
limitations: limitations: No broader impact concerns.
paper_summary: paper_summary: Authors investigated an adaptive approach for the rotting bandits problem under the infinitely arms assumption.
strength_weakness: strength_weakness: No clear weaknesses
questions: questions: I wonder how the regret bound behaves with respect to the effective rotting instead of the V_T or S_T. Assuming their values to be large and far from the real rotting, would it be possible to extend this analysis and solution to propose an adaptive result? Additionally, I wonder if also the regret lower bound would be tight in that case.

Similarly, I was wondering how good these results would be for the infinitely many afrmed bandit with no rotting.
limitations: limitations: No clear limitations have been found.
paper_summary: paper_summary: This paper considers the extension of the classic stochastic multi-armed bandit problem to the case where there is a) an infinite set of arms and b) rotting of the arm means. Specifically the rotting behaviour is of the 'rested bandit' variety, where the mean reward of an arm may fall as an immediate consequence of playing it, but the mean of an unplayed arm will not change, in contrast to the restless bandit. The infinite set of arms have i.i.d. mean rewards (no structural assumptions on the set of arms or existence of a reward function over them etc.) and reward observations are sub-Gaussian.

This paper considers a more general rotting behaviour than Kim et al. (2022, ICML). In Kim et al. (2022) the magnitude of rotting in each round was bounded, in the present paper the more general setting where the total amount of rotting in T rounds is bounded is considered, and the somewhat different setting where the number of rounds in which rotting occurs is considered. These two settings are referred to as the 'slow' and 'abrupt' rotting cases respectively.

An important parameter in the infinitely-many-armed bandit problem is $\beta>0$ which controls the probability of an arm being $\delta$-near optimal. All regret bounds in the paper for mean rewards in [0,1] and consider dependence on the number of rounds $T$ and parameter $\beta$. $\beta=1$ corresponds to a uniform distribution on arm means.

The paper derives a sliding-window-UCB-based approach, which can be tuned to both the slow and abrupt rotting cases when the bounds on rotting behaviour are known, and an adaptive version which aims to learn the rotting behaviour when these parameters are not known. The paper shows tight (in terms of order) regret guarantees on these algorithms, and improved empirical performance over sensible competitors.
strength_weakness: strength_weakness: There are three main weaknesses which I would like to see commented on the rebuttal phase. I think the first is difficult to address fully in a rebuttal phase, but I would like to be reassured that potential issues do not limit the scope of the contribution.

1. All of the theoretical results are ultimately order results only, without identification of the constants in the appendices, and some being somewhat vaguely described as needing to be 'large enough'. The paper would be stronger if these constants (or upper bounds on them) could be identified, to guarantee for which values of $T$ the bounds are meaningful. 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.

2. If I am not mistaken the experiments only consider $\beta=1$? It would be interesting to see if the convergence of the algorithm is replicated for various $\beta \neq 1$.

3. The motivation in terms of real applications is not especially strong. It is difficult to imagine a setting where the precise assumptions of the paper are realistic. In a recommendation setting, is it likely that there will be sufficient information to be confident that the click through rate of an item is always non-increasing, yet there is no contextual information available to supplement the model or exploit similar click through rates across similar items? In the clinical setting, is it likely that the rested assumption is realistic (i.e. any loss in efficacy is only determined by the actions of a single decision maker) alongside the immediacy of feedback and time horizons being of a scale such that the algorithms actually exhibit non-linear regret? If it is the case that the benefit of the paper is more fundamental - it presents an understanding of a simpler problem and its insights serve as a foundation to tackling these more complex real-world challenges, then perhaps it would be more helpful to make that clear?
questions: questions: 1. Can you provide clarity on whether your constants in the regret analysis are identifiable, and suggest the values of these for some simple instance of the problem? How would the resultant bounds compare to the empirical performance of Algorithms 1 and 2?

2. What would the experimental results look like for $\beta \neq 1$?

3. Is Prop 2.3 missing some kind of additional condition, or clarity over what is meant by worst-case in line 453? It would seem to be that you could construct an example where $\rho_1=T+1$ and all other $\rho=0$ and one could achieve $\sqrt{T}$ regret while satisfying $\sum{t=1}^{T-1}\rho_t >T$?

4. Can you put the WUCB definition in an equation display and reference its equation number in the statement of Algorithm 1?
limitations: limitations: Yes
paper_summary: paper_summary: This paper studied an extension of multi-armed bandit problem by introducing infinitely many arms and generalized rotting constraints. It provides explicit regret lower bounds and proposes an algorithm with regret upper bound matching the lower bound when $\beta \geq 1$. It has been claimed that closing the gap between the lower and upper bounds when $\beta \in (0,1) $ remains an open problem.
strength_weakness: strength_weakness: - The paper could be viewed as an extension of [1], and the impact of the paper might not be extremely significant. As mentioned in the paper, when $\beta \in (0,1)$, the proposed algorithm can not be proved near optimal at the current stage. The theoretical result could be more impactful if this issue can be solved.

[1] Jung-hun Kim, Milan Vojnovic, and Se-Young Yun. Rotting infinitely many-armed bandits. ICML, pages 11229–11254. PMLR, 2022.

- When the environment parameters $\beta, V_T,$ and $S_T$ are unknown, a significant amount of additional regret is generated with proposed Algorithm 2. 

- The paper could benefit from a more extensive experiment study. For example, the algorithm performances can be compared under different rotting processes (perhaps by varying the rotting rate and adding randomness).
questions: questions: The following questions are raised simply for discussion. There is no need to address them in the paper.

- Why the rotting budget $V_T$ and $S_T$ are defined for all selected arms? I would imagine it can fit better with real-world problems to treat the rotting process for each arm independently. Saying if an arm is selected $N$ times, the rotting budget is $f(N)$ where $f$ is a nondecreasing function.

- Corresponding to my second point in Weakness, is it possible to address the unknown parameters without incurring large additional regret? Can the methodology in the following paper [2] be applied in this paper to address the nonstationary rotting rewards? Can $\beta$ be estimated by selecting multiple new arms?

[2] Chen, Yifang, et al. "A new algorithm for non-stationary contextual bandits: Efficient, optimal and parameter-free." Conference on Learning Theory. PMLR, 2019.
limitations: limitations: The authors adequately addressed the limitations.

Comments: title: Official Comment by Authors
Official Comment by Authors
Thank you for your comment
Thank you for your comment.
Response to Rebuttal
Thank you for your comment.
Response to rebuttal
comment: 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.
* **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.
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
Thank you for maintaining a positive rating on our paper. We will incorporate the discussion into our final version.
Thank you to the authors for their reply. I am writing to confirm that I've read the author's rebuttal and my scores remain unchanged.
Thank you for maintaining a positive rating on our paper and increasing your confidence score. We appreciate your detailed feedback. We will incorporate the discussion into our final version, including more details regarding constant factors, a detailed explanation of Prop 2.3, and additional experimental results.
Thank you for your detailed reply to my comments. I appreciate the commitment to make modifications and am in agreement with your response. I have also read the other reviews and your responses and consider these to be suitably well addressed. As such I will retain my score and increase my confidence. (Justification: I agree with the remarks that finding results without constants and algorithms that can lead to further application-specific work are important fundamentals, but I feel for a score of 7+ the paper would have made more progress in one of these areas.)
Thank you for maintaining the positive rating of our paper. We will incorporate the discussion, including additional experimental results, into our final version. If there are any other questions, please let us know.
Thank you to the authors for their reply. I am writing to confirm that I've read the author's rebuttal and my scores remain unchanged.