An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints
Authors: Jung-hun Kim
Milan Vojnovic
Se-Young Yun
Venue: NeurIPS 2024 poster (2024)
Keywords: bandits
rotting rewards
infinitely many arms
Primary area: bandits
TL;DR: Infinitely many-armed bandits with rotting rewards under generalized rotting constraints.

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.

An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints
Jung-hun Kim Scoul National University
Milan Vojnović
Se-Young Yun KAIST AI Seoul, South Korea yunseyoung@kaist. .c.kr
London School of Economics London, United Kingdom
Seoul, South Korea Junghnnkim@snu.cc .r.
v...joovcclse.... ac uk
Abstract
In this study, consider the infinitely many- bandit problems in 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 the slow-rotting case, and the other in which the cumulative
Vr, referred number rotting instances bounded by Sr, referred to as the abrupt-rotting case. To address the challenge posed by rotting rewards, introduce algorithm that utilizes UCB with an adaptive sliding window, designed to manage the bias and variance trade-off arising due 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.
Introduction
We consider multi 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 exploitation trade-off. Bandit problems have significant implications lies in balancing the exploration-exploitatio across diverse yeal-world applications, such as recommendation systems (17) and clinical trials (23]. In 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) roming bandits, has been studied by Levine et
[16] Seznec al. 20 21). The previous work 20 proposed algorithms achieving (VVKT) regret.
focuses on finite arms, which Seznec et al. This suggests that rotting bandits with 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 infinite number of arms has been extensively conducted in the context of stationary rewards 6 24 g 10 [] where the agent has no chance to play all the arms least once until horizon time T. Initially, the distribution of the mean rewards for
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Table 1: Summary of our regret bounds.
Regret upper bounds
Regret upper bounds for < Theorem 3.1
Regret lower bounds for >
Type
for 9
Theurem
T Theorem
Slow rotting (Vr)
Ö max
Tam
Ó max V T vT)
2 max
Theurem
Theorem
Theorem 4.2
Abrupt rotting (Sr)
Ó max
T
Ö max / T, Vr
max
S Tass
the arms was assumed to be uniform over the interval [0, 1] 66 81. This assumption was expanded to include a much wider range of distributions satisfying P(u(a) > " x) = O(x²), ). for a parameter 3 > O, where u(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 [ or continuum-arce -arme bandits 3 [4]. 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 (= (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 (3 = 1).
In our study, we explore rotting bandits with infinitely many arms, subject to generalized initial mean reward distribution with 3 and, importantly, generalized constraints on the rate at which the mean reward of an arm declines. Our investigation into diminishing, 'rotting,' rewards encompasses two scenarios: one with the total amount of rotting bounded by Vr, and the other with the total number of rotting instances bounded by Sr. This allows to capture characteristies of entire rotting rates over the time horizon. Similar constraints of VT or Sr regarding nonstationarity have been explored in the context of nonstationary finite K- K-armed bandit problems 19]. where the reward distribution changes over time independently of the agent. Following established terminology for nonstationary bandits, denote the environment with bounded total amount of rotting the slow rotting (Vr) case and the one with a bounded total number of rotting instances as the abrupt rolling (Sr) 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 220 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 I of Seznec et al. 22 21) ). However, in the case of infinite arms under distribution for initial mean reward that allows for an infinite number of near- 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 fiiie--amed 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 Vr or ST in our setting, which differs from the case of finite arms.
To solve our problem, we introduce algorithms that employ an adaptive sliding window mechanism, effectively managing the tradeoff between bias and variance stemming from rotting rewards. Notably, to the best of our knowledge, this is the first work to consider slow and abrupt rotting scenarios, in the context of infinitely many- bandits. Furthermore, it is the first work to consider the generalized initial mean reward distribution for rotting bandits with infinitely many arms.
Summary of our Contributions. The key contributions of this study are summarized in the following points. Please refer to Table for a summary of our regret bounds.
To address the slow and abrupt rotting scenarios, we propose UCB-based algorithm using an adaptive sliding window and a threshold parameter. This algorithm allows for effectively managing the bias and variance trade-off arising from rotting rewards.

---

In the context of slow rotting (Vr) or abrupt rotting (Sr), for any 3 > 0, we present regret upper bounds achieved by our algorithm with an appropriately tuned threshold parameter. It is noteworthy that Vr, Sr, and B 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 | Z 1. In the other case, when 0 < B < 1, there is 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.
2 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 pa(a) denote the unknown mean reward of arm E AA at time t. At each time t, an agent pulls arm of e A according to policy т and observes stochastic reward ra given by r2 px(a.) + Te where is a noise term following a --sub-Gaussia distribution. To simplify, we use a, for of when there is no confusion about the policy. We assume that initial mean rewards {1 (a))ae are i.i.d. random variables on [0, 1], a widely accepted assumption in the context of infinitely many-armed bandits
8 6
13
As in Wang et al. 244 Carpentier and Valko 10], Bayati al. [51, we consider, 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 3 > 0 such that for every a E A and all [0,1]. 1].
P(u > 1 1) = (a) < z) O(x*).
where (1 = 1 - μr (a) is the initial sub-optimality gap. As noted in [24 10 51. Eq. is a non-trivial condition only when x approaches 0, as for any constant z E (0, 1], becomes P(A, (a) < x) = ((), which may accommodate wide range of distributions. It is noteworthy that the larger the value of 3, the smaller the probability of sampling a good arm. Furthermore, the uniform distribution is special case when 3 = 1. Importantly, our work allows for wider range of distributions satisfying (T) for any constant 3 > 0 than the uniform distribution (B = 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 2 1, the mean rewards of arms are updated as Ms+1(a) (a) = (e(a) Pc(),,
where (at) 2 0 for the pulled arm 0₂ and Pt (a) = for every a E A/fa,). which implies that the rotting may occur only for the pulled arm at each time. Note that, for every a E A and f 2 2, it holds
(a) = (4(((a) (a) Σ s=1 Pa (a), allowing (*((a) to take negative values. For notation simplicity, in what follows, we write Pt for Pe (a;) when there is no confusion. We refer to Pl, P2.... as rotting rates. We also use the notation [m]] == (l....,m,, for any integer 2 1.
We consider two cases for rotting rates: (a) slow rotting case where, for given V/ 2 0, the cumulative amount of rotting required to satisfy the slow rotting constraint _P-1 Pt S Vy, and (b) abrupt rotting case where, for given Sy E [T', the cumulative number of rotting instances (plus one) is required satisfy the abrupt rotting constraint + ET=! 1(p # 0) < Sr. The values of rotting rates of pulled arms, (T 1]. are assumed to be determined by an adversary, described as follows.
Assumption 2.1 (Adaptive Adversary). At each time & E [T]. the value of the rotting rate P: 2 is arbitrarily determined immediately after the agent pulls a,, subject to the constraint of either slow rotting for a given Vr or abrupt rotting for a given Sr.
Remark 2.2. The adaptive adversary under the slow rotting constraint (Vr) is more general than that in Kim et al. [13, in which the adversary is under maximum rotting rate constraint; that is, for given p = (1)), ), Pt S p for all f E [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 (Sr) is fundamentally different from the maximum rotting constraint [I3 because the adversary for abrupt rotting is under constraint on the total number of rotting instances rather than the magnitude of rotting rates.
3

---

Our problem's 's objective is to find policy that minimizes the expected cumulative regret over a time horizon of T time steps. For given policy л. the regret is defined EE (T)] = B (1 (4(a)) )) The use of 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 (T, there always exists an arm whose mean reward is sufficiently close to
We note that while we have ST S T because the number of rotting instances is at most T 1, the upper bound for VT may not exist due to the lack of a constraint on the values of p Here we discuss an assumption for the cumulative amount of rotting. In the case of > P: > T, the problem becomes trivial as shown in the following proposition.
Proposition 2.3. In the case of Ei= > T, there always exists rotting adversary that incurs regret of (I()) and simple policy that samples a new arm every round achieves the optimal regret (T)).
Proof. The proof is provided in Appendix
A.3
From the above proposition, when Σ P: > T, the regret lower bound of this problem is (?()). which can be achieved by simple policy. Therefore, we consider the following assumption for the region of non-trivial problems.
Assumption 2.4. Σ P: S.
Notably, from the above assumption, we consider VT S. T for the slow rotting case. We also note that the assumption not strong, as frequently arises real-world scenarios and more general than the assumption made in prior work, as described in the following remarks.
Remark 2.5. The assumption of ET=
(=1 Pt I T is satisfied if mean rewards are under the constraint of 0 S pa(a,) S for all t E [T' because this condition implies Pt S for all t E [7]. Such scenario is frequently encountered in real-works applications, where reward is represented by metrics like click rates or (normalized) ratings in content recommendation systems.
T-1
Remark 2.6. Our rotting scenario with Σ Pt S T is more general scope than the one with the maximum rotting rate constraint where Pt S p = o(1) for all t E [T' -], which was explored in Kim et [3]. This is because for our setting, Pt is not necessarily bounded by o(1), and under the maximum rotting constraint, the condition Σi=1 Pt. I T is always satisfied.
3 Algorithms and Regret Analysis
We propose an algorithm [Algorithm[] utilizing an adaptive sliding window for delicately controlling bias and variance tradeoff of the mean reward estimator from rotting rewards, drawing on insights from [ 21). This is why our algorithm can adapt to varying rotting rates Pt and achieve tight regret bounds with respect to Vr even Sr. Furthermore, algorithm accommodates the general mean reward distribution with 3 > 0 by employing a carefully optimized threshold parameter.
Here we describe our proposed algorithm detail. We define (a) Ele,, rel (at
a)/m +2] where (it E'=, 1(a, = a) for t S tz. Then for window-UCE index of the algorithm, we define WUCB(a, (1,2, (a), + lolloo(T)// (a). what follows, "selecting arm' means that policy chooses select an arbitrary new arm a E A' without prior knowledge regarding the arms in A denoting the corresponding time t(a). We define Ta(a) as the set of starting times for sliding windows of doubling lengths, defined as (a) = {s E [T] +(a)= S 8 < t-11 --1 and = t- 2 for some E N). Then the algorithm pulls the arm consecutively until the following threshold condition is satisfied: min WUCB(aa s, 1, T) < - 5, 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 new arm and repeats this procedure.
before pulling it. In Algorithm T first
'This assertion follows from the fact that for any > 0, there exists an arm a in A excluding rotted arms such that (a) < with probability 1, as 1om (1 (a) 2 e)") I.

---

Algorithm UCB-Threshold with Adaptive Sliding Window
Input: T,6, A: Initialize: A' +-
Select a new arm a E A'; Pull arm and get reward t(a) 1
for f = 2...., do
(innneT((a) s, 8, 1,7) < A' 4- A ((a)
then
Select new arm a E A'; Pull arm and get reward r. t(a) t
else
Pull arm a and get reward
Mean reward (arm a)
Rotting with pulls
Small window
Large window
First time arm a pulled
(a)a((a)
WUCB
t(a)
WUCB
Time step
(e)
Small blas
Large Small variance
Large
Sliding window candidates
Figure I: Illustrations for the adaptive sliding window: (left) the effect of the sliding window length on the mean reward estimation, (right) sliding window candidates with doubling lengths.
Utilizing the adaptive sliding window having minimized window UCB index enhances the algorithm's ability to dynamically identify pprrly-performing arms across varying rotting rates. This adaptability achieved by managing the tradeoff' between bias and variance. The concept is depicted in Figure (left), where an arm a undergoes multiple rotting events. WUCB with a smaller window exhibits min- imal bias with the arm's most recent mean reward but introduces higher variance. Conversely, WUCB with larger window displays increased bias but reduced variance. In this visual representation, the value of WUCB with small window reaches a minimum, enabling the algorithm compare this value with 1 8 to identify the suboptimal arm. Moreover, as illustrated in Figure I (right), (right), by taking into account the constraint of s computation time for determining the appropriate window and reduce the required memory from ((t) to (log t), respectively, for each time t.
1 for the size of the adaptive windows, we can reduce the
Having introduced our algorithm, we compare it with the previously proposed algorithm UCB-TP 13 which tailored for the maximum rotting rate constraint Pt S p (= o(1)) for all 0 and the uniform initial mean reward distribution (5 1). The mean reward estimator in UCB CCB-PP considers the worst-case scenario with the maximum rotting rate p as j2 pny(a) where Ø is an estimator for the initial mean reward, ne (a) is the number of times arm is pulled until time f - 1, and (a) for reducing the bias from the worst-case rotting, which leads to achieving a regret bound of Ó(max /3T, VT)). This estimator not appropriate for dealing with our generalized rotting constraints because it aims to attain the regret bound regarding the maximum rotting rate p 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 3 > 0 by using a carefully optimized 8, as shown below.
Slow Rotting (Vr). 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 Vr. We analyze the regret of Algorithm| I with tuned 8 using 3 and Vr. We define (B) = (VT/((VTTTT//// 1/VT) when 0 3 < 1 for some constant
1/T11/1111
when 8 2 and (33) Ci The algorithm with 5 achieves a regret bound in the following theorem.
5

---

Theorem 3.1. The policy ι of Algorithm 1 Twith d = (3) achieves:
(max V I
T 0+2 To for 32 1,
E|R (T)
Ommax (V, vT)) for 0 <<
We observe that when / increases above the regret bound becomes worse because the likeli- hood of sampling 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 estimat- ing the mean reward. Further discussion will be provided later. Also, we observe that when V1 (max 1 1/VTT) 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 (max(TT8/(++) (T18/(8+1), vT}), vT)) as shown in Wang et al. 24 Bayati 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 regret analysis, such as dealing with varying P: individually with respect to the total rotting budget of Vr, 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. 113
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 μ (a) 2 1- --20 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 write RD (T) R (T) + R (T). where R (T) is the regret from good arms and R (T) is the regret from bad arms.
We first provide bound for E. R (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 be a set of distinet good arms selected until T, t1 (a) be the initial time step at which arm is pulled, and (a) be the final time step at which the arm is pulled by the algorithm so that the threshold condition holds when t = tz t2) + 1. For simplicity, we use t and t2 for t, (a) and l2 (a),, when there no confusion. For any time steps S m, we define Vin.m (a) = Ee Pr (a) and (a) = mm. (a)) mm. (m)/mimmmm (a). We show that the regret is decomposed as (a)/n
re = Σ (Aila)man))a)) GEAA.
+ Σ Vinaa-((a)). 1=1++1
which consists of regret from the initial mean reward and the cumulative amount of rotting for each arm. For the first term of EaEAg A (a 2 since A (a) = 0(8) from the definition of good arms a e Ag. we have E/Eae
= (6T).
The main difficulty in 2 lies in dealing with the second term, EoeAp Ei V (i),-1j((a)) where we need to analyze the amount of cumulative rotting until the arm 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 upper bound for the cumulative amount of rotting as
Σ "E t=1++1
Vi Ö + VT
Σ a
(
Therefore, from (3), Vi S T, and Eqs. (2) and 33, using Hölder's inequality, we have
E (T)) = Om { V 2 T o Tom for 824 1, Ommax V
(4)
T$ VTH) for 0< 1.
Next, we provide bound for ([)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 episodes R ms. We first consider the case of Vr > max[[/VV; 1/T2/(3+1)) In this case, by setting m = [2Vr/0], we can show that R (T) I R with high probability. By analyzing R with the episodic analysis, we can
show that E(R & B = O (max 2=1 Vi .v }). As in the similar manner, when VT max VT, 1 (2))) J. by setting m C3 for some constant C3 O, we can show that E (T) s E R m (max ( Tir vT)). From the above two inequalities, we have
(max V s T T for 82 1, (max (0lmaxVV2T50 (V VT)) for 0 0<
E (T)
(S)
Finally, from and we can conclude the proof from (T)
+
Remark 3.2. We compare our result in Theorem 3.1 with that in Kim et al. [3]. which, recall, is under the maximum rotting rate constraint A S (11) for all t and uniform distribution of initial mean rewards (3 = 1). For fair comparison, we consider an oblivious adversary for rotting rates where the values of Pt 's are determined before an algorithm is run, which may imply Vi = =E=1 Pt. and p m Pr. Then with 3 = 1, from Vr S Tpp we can observe that the regret bound of Algorithm tighter than that of TCB-TP [13] as (max (V, vT)) I ( T, vT}). where the latter is the regret bound of UCB-TP. We will demonstrate this in our numerical results.
Abrupt Rotting (ST). Here we consider abruptly rotting reward distribution under the constraint of Sr. We consider Algorithm I with newly tuned by S7 and B. We define d3(3) c₁ (Srr - when 33 and (B) ca (ST/ 1/2 when O < 1 for some constant 0 c1 < We also define VT = Σ E[p.]. In the following theorem, we present a regret upper bound for Algorithm with (3).
Theorem 3.3. The policy x of Algorithm 7 Twith 6 = 63( achieves:
(Timax(57ii11 Vrr)) for 821, 0(max (VST,
EIRe (T)
for 0 < <3<1
As in the slow rotting case, for the abrupt rotting case (ST), we observe that when 3 increases above 1, the regret bound in the above theorem worsens the likelihood of sampling a good arm decreases. When 3 decreases below 1, the regret bound remains the same because we cannot avoid a certain observe that
level of regret arising from estimating the mean reward of an arm. Additionally, the regret bound is linearly bounded by Vr, which is attributed to the algorithm's '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 Vy regret in the worst-case. Notably, in the typical cases where 0 $ Pe < 1 for all 0, as discussed in Remark 2.5 VT is negligible in the regret bound from Vy S ST < T. Furthermore, we observe that for the case of ST = 1, where the problem becomes stationary (implying Vr = 0), the regret bound matches the previously known regret bound of Ómax (10(64)) )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 as Rd (T) RO(TT) + RT)). From the definition of good arms, we can easily show that
EIRe (T) 0(6s = (Ö(S."
for 3 2 1,
( (((VTTT) STT) for 0 B 8<1 1.
For dealing with R (T), we partition the regret into two scenarios: one where the bad arm is initially bad sampled from the distribution of (I) and another where it becomes bad after rotting. This can be
7

---

Abrupt rotting event
Time step
Appropriate sliding window
Figure 2: Adaptive sliding window for abrupt rotting.
expressed as R (T) = R (T) + (T). Then for the former regret, R (T), as in the proof of show that
Theorem 3.1 by using the episodic analysis with m Sr,
E[R (T) S E(R
for B 1 ( for 0 B
- SÖ ((VSTT))
For the regret from rotted bad arms, (T) it is critical to analyze significant rotting instances to obtain a tight bound with respect to Sy, factor not addressed in the regret analysis of slow rotting
(VT) Theorem [.T] We analyze that when there exists significant rotting, then the algorithm can efficiently detect it as bad arm and eliminate it by pulling it at once. From this analysis, we have
Omaxx {S 3.5+1g THE VIH) for B 1, Óm [VS,TT Vr+) for 0 < B <.
B( =
Putting all the results together with (E(R R (T)) (T) B (() and ST 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 (Sr) scenarios characterized by a limited number rotting instances. The rationale behind the effectiveness 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 min.eT.(a)) WU (CB, 8, is equivalent to the condition of WUCB s, 1, T) 1. (a) s - (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 abrupt rotting event. Consequently, condition can identify substantially rotted arms by mitigating bias and variance using the window starting from the time step following the occurrence of rotting.
ô for some such that
illustrated in Figure 2 this adaptive threshold
Slow rotting (Vr) and abrupt rotting (Sr). In what follows, we study the case of rottiig under both slow rotting and abrupt rotting constraints. In this case, Algorithm I with 5 = min (1)) {8))
can achieve a tighter regret bound as noted in the following corollary, which can obtained from
Theorems 3.1 and 3.3
Corollary 3.4. Let Ry and Rg be defined as
TEi Vr for 82 1, max Maxx(V,7 (V, /3 VT) for 0 and Rs == (max(5p (S {
max 1 2 T for 3 1,
Ry
[axx (max( (VST. VT} for 0 0< 3 <1.
The policy of Algorithu Ō (min (Ry, Rs)).
7 with 8 min(fvv(5), 8g ( achieves the regret bound of E (T)) =
Case without Prior Knowledge of VT, ST, and 3. Here we study the case when the algorithm does not have prior information about the values of Vr, Sr. and 3 under the constraints of Vr and ST. These parameters play a crucial role in determining the optimal threshold parameter 8 in Algorithm|] T. We propose an algorithm based on estimating the optimal threshold parameter å directly (Algorithm 2), rather than estimating each unknown parameter separately, employing the Bandit-over- Bandit (BoB) approach [ 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 Kim et al. [3], the algorithm
achieves regret bound of E R (T)
(min { Rs} + (2x(7220+1005-2) 7T341). 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 (Vr) and abrupt rotting (Sr), respectively.
Theorem 4.1. For the slow rotling case with the constraini VT and B > 0, for any policy n, there always exists rotting rate adversary such that the regret of satisfies
E (T) = 22 max V1 3-2 T42 T }).
Proof. The proof is provided in Appendix A.8
Theorem 4.2. For the abrupt rotting case with the constraint Sr and 3 > 0, for any policy n, there always exists rotting rate adversary such that the regret of satisfies
E (T) = 22 (max
c3+1 ST
T To Vr Vr
Proof. The proof is provided in Appendix A.9
For the abrupt rotting (Sr) case, it unavoidable to incur D(Vr) 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 I we can observe that Algorithm| T achieves near-optimal regret when 1. The optimality proven only for 3 > 1 has also been observed for stationary infinitely many believe that our regret upper bounds are near-optimal across the entire range of 3. Achieving tighter regret lower bounds when B < is left for future research; see Appendix A. for further discussion.
bandits [5] 24]. We
5 Experiments
1e6
SSUCB
3
UCSTPP
Algorkhm
Algorkhm
EIAT
0-
1e6
Figure 3: Regret Performance comparison between our algorithms and benchmarks.
In this section, we present numerical results validating claims of theoretical analysis We use randomly generated datasets under a uniform distribution for initial mean rewards (6 = 1).
We first compare the performance of our Algorithms/ I and 2 with UCB-TP [3] the state-of-the-art
algorithm for the rotting setting, and SSUCB [5) near-optimal algorithm for stationary infinitely
http:////ggguuu...oooouugggunuie An- www.tiie-eeeeeeeeeeeeeee www.-ve--pppoccchhoooo for- wnw.inninnnnniiiniiiinn Many armed- Bandits- uwder Stg.
'The source
code is available

---

many-armer bandits, For comparison with UCB-TP, recall our discussion in Remark 3.2 We set the rotting rates such that p: = (tlo))) for all t, for which p P1
o = V (1). and ST = T. In Figure 3 we can observe that Algorithms [ and 2 perform better than UCB-TP
and SSUCB (and Algorithm| D oouperforms Algorithm 2). which in agreement with our theoretical
analysis for the case 1. this case, the regret bounds for Algorithms | and 2 are O(T2/3) and OTT8/1) from Corollary 3.4 and Theorem A.15 respectively, which are tighter than the regret bound of Ó(T/ log(TT) for UCB-TP. Additional experiments can be found in Appendix A.10
A.10
6 Conclusion
We explore the challenges of infinitely many-armed bandit problems with rotting rewards, focusing on slow rotting (Vr) and abrupt rotting (Sr) 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.
7
Acknowledgements
The authors thank Joe Suk and the anonymous reviewers for helpful discussions. JK was supported by the Global-LAMM Program of the National Research Foundation of Korea (NRF) grant funded by the Ministry of Education (No. mation & communications Technology Planning & Evaluation (IITP) grant funded by the Korea goVerMmentMMSTT) (No. RS-2022-11200111 Development of Goal-Oriented Reinforcement Learning Techniques for Contact-Rich Robotic Manipulation of Everyday Objects)
SY was supported by Institute of Infor-
References
[1] Yasin Abbasi- Yadkori. Dávid Pál. and Csaba Szepesvári. Improved algorithms for linear stochastic bandits, Advances neural information processing systems, 24, 2011.
[2] Peter Auer, Nicoló Cesa-Bianchi Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(():48 2002.
[3] Peter Auer, Ronald Ortner, and Csaba Szepesvári. Improved rates for the stochastic continuum- armed bandit problem. In International Conference on Computational Learning Theory, pages 454 468. Springer, 2007.
[4] Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. Conference on Learning Theory, pages 138-158. PMLR, 2019.
[5] Mohsen Bayati, Nima Hamidi, Ramesh Johari, and Khashayar Khosravi. The unreasonable effectiveness of greedy algorithms in multi-armed bandit with many arms. arXiv preprint arXiv:2002.1012/ 2020.
[6] Donald A. Berry, Robert W. Chen, Alan Zame, David C. Heath, and Larry A. Shepp. Bandit problems with infinitely many arms. The Annals of Statistics, 25(5):2103 2116, 1997.
[7] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armes armed-bandittt problem with non-stationary rewards. Advances in neural information processing systems, 27, 2014.
[8] Thomas Bonald and Alexandre Proutière. Two-target algorithms for infinite- bandits with bernoulli rewards. In Proceedings of the 26th International Conference on Neural Information Processing Systems Volume 2, NIPS' 13, page 2184-2194 Red Hook, NY, USA, 2013. Curran Associates Inc.
[9] Daniel Brown. How wasted too long finding concentration inequality for sums of geometric variables. Found at https://cs. wwaterloo. cal" browndg/negbin. pdf. 8(4), 2011.
10

---

[10] Alexandra Carpentier and Michal Valko. Simple regret for infinitely many armed bandits. In Proceedings of the 32nd International Conference on International Conference on Machine Learning Volume 37, ICMI''15, page 1133-1141. JMLR.org. 2015.
[11] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu, Learning optimize under non- stationarity. The 22nd International Conference on Artificial Intelligence and Statistics, pages 1087. PMLR, 2019.
[12] Alexander Rakhlin Dylan J. Foster. Statistical reinforcement learning and decision making: Course notes. MIT Lecture notes for course 9.S915 Fall 2022, 2022.
[13] Jung-hun Kim, Milan Vojnovic, and Se-Young Yun. Rotting infinitely many-armed bandits, In International Conference on Machine Learning, pages 11229-11254. PMLR, 2022.
[14] Robert Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. Advances in Neural Information Processing Systems, 17, 2004.
[15] Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
[16] Nir Levine, Koby Crammer, and Shie Mannor. Rotting bandits. Advances in neural information processing systems, 30, 2017.
[17] Lihong Li, Wei Chu, John Langford, and Robert E Schapire. A contextual-bandi approach to personalized news article recommendation. Proceedings of the 19th international conference on World wide web, pages 661-670, 2010.
[18) Phillippe Rigollet and Jan Christian Hütter. High dimensional statistics. Lecture notes for course /8$997, 81 813:814, 2015.
[19] Yoan Russac, Claire Vernade, and Olivier Cappé. Weighted linear bandits for non-stationary environments. arXiv preprint arXiv: 1909:v1990.000000 00909999446...... 2019.
[20] Julien Seznec, Andrea Locatelli, Alexandra Carpentier, Alessandro Lazaric, and Michal Valko. Rotting bandits are no harder than stochastic ones. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 2564-2572. PMLR, 2019.
[21] Julien Seznec, Pierre Menard, Alessandro Lazaric, and Michal Valko. single algorithm for both restless and rested rotting bandits. In Silvia Chiappa and Roberto Calandra, editors, Pro- ceedings of the Twenty Third International Conference on Artificial Intelligence and Staristics, volume 108 of Proceedings of Machine Learning Research, pages
PMLR, 26 28
Aug 2020.
[22] Alex Tsun. Probability & statistics with applications to computing, 2020, URL https
//www.alezttttt alextsun www.etsu.coo/fllle/////eooeeeeee
pdf
[23] Soffa S Villar, Jack Bowden, and James Wason. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges. Statistical science: a review journal of the Institute of Mathematical Statistics, 30(2): 199, 2015.
[24] Yizao Wang, Jean-Yves Audibert, and Rémi Munos. Algorithms for infinitely many-armed bandits. Advances in Neural Information Processing Systems, 21, 2008.

---

A Appendix
A.1 Limitations & Discussion
As we summarize our results in Table I Algorithm I achieves near-optimal regret only when 3 > 1. Here, we discuss the discrepancies between lower and upper bounds when 0 < 3 < 1. From ( can observe that as 3 decreases below 1, the probability to sample good arms may increase, which appears be beneficial with respect to regret. However, the regret upper bounds for 0 < 3 < 1 in Theorems 3.1 and 3.3 remain the same as the case when B 1 while the regret lower bounds in decreases, resulting in a gap between the regret upper and lower bounds. The phenomenon that the regret upper bound remains the same when 3 decreases has also been observed in previous literature on infinitely many-armen bandits 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 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 3, and achieving tighter regret lower bounds when research. Notably, the optimality proven only for B 2 has also been observed for stationary infinitely many-armed bandits 5 24
Theorems 4.1 and 4.2 decrease
is left for future
A.2 Additional Explanations for Eq.
P(d, (a) <xx
1
B= 1
B >
B <
(Uniform distribution)
(Good arm 4
(Good arm ft
Figure 4: P(Ar(a) < <x) 0 for different values of B.
To discuss the effect of on the distribution (a) and the probability of sampling a good arm (having small A1 (a)), we consider the case when (a) < < = x", which is shown Figure for some values of B. It is noteworthy that the uniform distribution is special case when / Importantly, the larger the value of 3, the smaller the probability of sampling a good arm.
A.3 Proof of Proposition 2.3
Recall (1(a) = (a). We first show that [[un(a)] = @(1). For any randomly sampled a E A. we have E[pp(() 2 (a) 2 y) = yP < <1 y) for y E [0, 1]. With y = 1/2,
have Elu,(a) 2 (a))) < (1/2))
((1) from constant B > 0 and ( Then with
[a)] < 1, we can conclude (a)] @(1) (Especially when P(A(a) < <x) x we have [a) = fo (a) 2 æ)dx =1 1111 S (a) x)dx
So dx = 34T which implies [a)] = @(1) with constant 9 > 0). We then think of policy n' that randomly samples
new arm and pulls it only once every round. Since Elp, (a)] = (1) for any randomly sampled we have E ER (T)) (TT).
Next we show that the policy x' is optimal for the worst case of ΣT-I Pe T. We think of any policy T" except n'. For any policy n!., there always exists an arm such that the policy must pull arm a at least twice. Let and t" be the rounds when the policy pulls arm a. If we consider Pr > 0 and = 0 for t E [T - 1)/(t'} such that Pr = -T- Pt then such policy has M pa) regret bound. Since ΣT1 Pr T', for any algorithm T" except n', there always exist rotting rate T-
T-1
adversary such that R (T)) 3<Er" Rlpp)) = 2(T)). Therefore we can conclude that n'
the optimal algorithm for achieving the optimal regret of (
12

---

A.4 Proof of Theorem 3.1 Regret Upper Bound of Algorithm for Slow Rotting with Vi
Let Ae(a) (a)). Using a threshold parameter 6, we classify an arm a as good if A1(a) - 8/2. near-good if 6/2 < (1(a) I 26, and otherwise, we classify a as a bad arm. In A, let @1. .g..... be a sequence of arms, which have i.idd 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 01, a2,..... ................................ Let Ar be the set of sampled arms over the horizon of time steps, which satisfies |AT| S T. Let A&. be a set of good or near good arms in Ar. WLOG, the following proofs proceed under the given Ar, since the proofs hold for any Ar.
Let (()) Ei=e, Me (e(a)/( [s1..a)) (a) for the time steps 0 81 $2- We define event (a)l S v 12
E1 = {| (a) oal
[a] for all 1 < 81 S $2 S T, a E Ar). By
following the proof of Lemma 35 Dylan J. Foster [12]. from Lemma
A.30 we have
12 log T 11s1,
p
((mnss)(a) - F1ss,,z) (a)
T
n Xi S /V22log(T)/m
Σ
P
n=1
i=1
2
1 T
(6)
where X, rr. 14, (a) and т; is the i-th time that the policy pulls arm a starting from $1- We note that even though X, 's seem to depend on each other from T; 's each value of X, is independent of each other. Then using union bound for 81, 82, and a E Ar, we have P(E)) < 2/T². From the cumulative amount of rotting Vr, we note that A,(a) = O(V + 1) for any and 1, which implies E (T) = O(T2) from VT T. For the case where F, does not hold, the regret is E|R" (T") (T))))))())) = (l), which is negligible compared to the regret when Ej holds, which we show later. Therefore, for the rest of the proof, we assume that Ei holds.
For regret analysis, we divide H' (T) into two parts, R (T) and R (T) corresponding to regret of good or near good arms, and bad arms over time T, respectively, such that Rd RT(T)= R (T) (R)+ We first provide a bound of R (T) in the following lemma.
Lemma A.1. Under En and policy n, we have
[T) Ô (16+1213)713)
Proof. Here we consider arms a AG. Let Vi (a) En pr(a) and Pio. (a) ((4))//mn
for time steps n S m. For ease of presentation, for time steps r > q. we define (in=j(a) = [lr=e (a) = P(r.g) (a) Ei_, x(t) = 0 for z(t) e IR and 1/0 = oc. Then, for
any s such that n < s S m, under Ei we have
P)a.mi (a)
s Ml (a) + /
12
m-1 1
s pm(() +
Σ
p:l(a; = =)) + 12log(TT//m)..)
1=s
m-1
m-1
= -M((a)- - Σ
m1 = a) + Σ
p:l(a = a) + 12log(T)/M(en))) (a)
I=n
I=s
S pa(a) Vm,m- (0) + P + (a) + (2log(1T)/T/mmml(
Therefore, from (n,(a) < 1 we obtain
Ma.m] (a) + /
< 1 - Vin.m-1((a) + 9/).m-1(())) + 2 12log(T) (m),mm))))
13

---

Let f (a) be the initial time when the arm a is sampled and pulled and (z(a) be the final time when the policy pulls the arm. For simplicity, we use t and t2 instead of t (a) and f2(a). respectively, when there no confusion. We define A as a set of arms a A such that f2(a) = t (a)
and define A as a set of arms a E AG such that (2(a) = (1(() + 1. We also define a set of arms AS {a E 1 UA P(1))t-1((()) [(log / -2 (a))2/87). Let w(a)
[(oo 7) //1..2 1/1.12222)( 2))22//8) For simplicity, we use w for w(a) when there is no confusion. Then with the fact that (4( = M4g (a) Eizii(a) Pe(a) = ,4, (a) - ( for (1)) S t2(a).
we have
(2(a)
E[
E
Σ Σ
(1 (1-)((a))
LEAA (=(i(a)
12(a)
E Vint-1(aa)
E
+
AE
(=)(()+1
ta)a)
E
2T8 +
Σ
Ptila) +
Σ
Σ
(io,c-1((a)
aEAt
R5.4/ (AAMAAAAA (a]+1
(1(a)+w(a)
f2(a)
Σ
Σ
Vinns-y((a) +
Σ
Mant-u((a)
a AEAT
(0)+
((()())
(8)
where the first inequality comes from (a) S 26 for any Al. For the second term in the right hand side of the last inequality g
Σ aEA!!
Pti(a) S VT.
(9)
For the third term in (8. from the fact that n ((es+1.es(a)) (((1)t2-1(aa)) < w(a) for from the definition of Ay we have
any any
A9
ta(a)
Σ
Σ
Vin)t-1((a)
(a)+1
E
1/ (a + Ptz(a)-1
rEAL (AAAAAAAAA
=0
V++
Σ
w(a))1n,te-2(a)
dEAS (EAA//AAAAPUAA
=
V
Σ
Thi (1)))-2((1)/// V 11 (a)1/3
REAA./ DEABG/(APUAPUAY
(10)
14

---

Now, focus the fourth term in (8- From (1(0) + w(a) + S (2(a) for a E A7 from the
definition of Ay and (0), we first have
(a)+ Σ
4 (a)++a())) [-1
Σ
((.r-1((a)= = Σ Σ
Σ
Ps
aE (a)++1
aEAt (a)+1 1=h1
(a)+ [=(a)
Σ
Σ
Ps
A (a) (at)(a)
Σ
a
=
Σ rEA4
Rit 121,62221006 -
(1I)
Now we focus on Egeae Etea) (a)+(aa) VPL a- (a) in (8) FFrm the definition of tz and the
threshold condition the algorithm with 77. for any t S S l2 and any 4 S s S s.t. = f 2 for 7 E Z+, we have
- V (a) + Ma 1 2 (2log(() 2 -.
(12)
Fort 2 +1+ +1, there always exists t S s()) S 1-11 such that w(a)/2 m(((0)--1](() S w(a)
and s(t) = t - 2/ for l Zt. Then from [2) with s = s(t), we have
(a))
= Pla(e), (000),-2100///p1z (a) + P (20)
(13)
Using the facts that ((s(t),--2)00 (a) > (0(0),c1(aa/22 2 w(a)/4 and t s(t) I w(a) from (((())--1](a)) w(a), we can obtain that
ta()) Σ
ta(a)
Ek=t-w(a)
1-2
(1))))0-2(005
Σ
-(((0)(-2((0)
(=t+(a)++++m(a)
12(a)-2
w(a)pt
Σ
(0(1))22((0))
(a)+
(a)-2
<
Σ Pe.
(14)
(mtz(a)
where the second inequality is obtained from the fact that the number of times that Pa is duplicated for each / E (a) + 1, (2(2 2) in the expression Etzaa) (o)
Et= w(a) Ph is at most w(a))
Then with 13 and (14. using the fact that
(a(a) Σ
P ( (13 < n 12 (0 (a) = -0 (a)2/33 2 (a) 1/3),
(())+1+m(a)
15

---

we have
taaa
Σ
Σ
(())-1(aa)
T t=t, ( (1)+)
(a(a)
Σ
Σ
(()c)2((a)) + Pra(a)-1
T
t= (a) +1+w(())))
(2(a)
t2(a)
0
8T VT + Σ
Σ
(u00).-2(00//P (a)
Σ Σ
Pl (a)
aEA. (I())
aEAd t= (=)
ta(a)
0
8T + VT + Σ
Σ
Σ
mlt 1 -2),)=-2((a)2/33 22, (1
aEAg t=
aEA9
12(2)-2
0
8T V+ + Σ
Σ
Pe/ Pc/P PelP(n,t--2(1))21
Σ
(a) V2
12 (a)
aEA; (a)
a
-
8T 1/+ Σ
Tit 12 12 -2 -2))
(a)
(15)
Then putting the results from
10 1
11 and 15 altogether, have
E E (T))
Σ Venaa-((a)) ]
(a)
Σ
A((a)m)n)s1(a) +
LAE
(t)(a))+
δ T8 + VT +E
Σ
Mith (t a0 (a)233
1/3
DEAA/((AULA
= Ö (8 VT 22/3)
(16)
where the last equality comes from Hölder's inequality and Vr S T. This concludes the proof.
Now, we provide a bound for (T). We note that the initially bad arms be defined only when 25 < 1. Otherwise when 25 2 1, we have R(T) = (T), which completes the proof. Therefore. for the regret from bad arms, consider the case of 25 < 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 policy sampling arms in the sequence order, let m be the number of samples of distinct good arms and m 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² 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 ..... m mn are i.i.d. random variables with geometric distribution with parameter 25, given a fixed value of m Therefore, with some constant > 0, for non non-negann neggaateeve integer & we have PPm = k) = (1- C(26))) for 1,..., m Define myr to be the number of episodes from the policy over the horizon T, m be the total number of samples of good arm by the policy æ over the horizon such that m. mrr or n = mn 1, and m to the number of samples of bad arm in the i-th episode by the policy x over the horizon T.
16

---

Under policy π, let R, be the regret (summation of mean reward gaps) contributed by pulling the j-th bad arm in the i-th episode. Then let R m Ejelmg) R which is the regret from initially bad arms over the period of m2 episodes.
Let a(i) be a good arm in the i-th episode and a(i,j) be j-th bad arm in the i-th episode. We define (a) = Σi= p:l = a). Then excluding the last episode myt over T, we provide lower bounds of the total rotting variation over 7 for a(i), denoted by Vr(a(i)), in the following lemma.
Lemma A.2. Under E,, given mr, for any [m ( we have
Vr(((i)) 2 8/2.
Proof. Suppose that (a()) 8/2, then we have
{ ( (Msts(oto))(((i)) /12 /22bog(())/mmaaaaaannaaaa
min (attaaa)))(
min (M(sss(a(o
t (taa))))))))
2 (a(())) -
2 -
11
where the first inequality is obtained from Er, and the last inequality is from Vrr((()) < 6/2 and yn (a(i)) 2 8/2. Therefore, from the threshold condition, policy must pull arm a(i) until its total rotting amount is greater than (or equal to) 6/2, which implies Vr(((()) 2 8/2.
In the following, we consider two different cases with respect to V7; large and small VT.
Case 1: We consider Vr ///
in the following.
In this case, we have 5 = (B) c₁ max (VT /T)/1(+2)) (Vr/T)2/33. Here, we define the policy ı after time such that it pulls a good arm until its total rotting variation equal to or greater than 5/2 and does not pull 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, pulls the arm until its total variation becomes max 8 8/2, Vr(ā) if is good arm. For i [m j E [m,"]
let V and VB 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.9's 's and V as follows:
If à is good arm,
v (Vr(a(i))
for i E [m 1] for i [m
(v((((i)))
for E [m E [m
V.5
1]
for i [m9//[m]] E [m
Otherwise,
v. (Vr(((i)) for E [m 88/2
Vr((((,)))
for i E [m]].] J E im
v ij
for i E | mm
9
0
for i E [m m - 11 E [m (
For E [m9) j E [m let m.
B be the number of pulling the j-th bad arm in i-th episode from the policy. We define nr (a) be the total amount of pulling over T. Here we define n 's as follows:
(nt(a(i,
for i [mf], E [ for i e /m01/[m4), E [m
8
nij
Then we provide m such that RB( < g in the following lemma. Lemma A.3. Under Ed, when m = [2VV//0] we have
RB(TT) < R
17

---

Proof. From Lemma A.2
we have
Σ (m(m9)
V.9
2 00
2 Vr,
2
which implies that R
RT)TT)
S R
From the result of Lemma
A.3 set m [2Vr/66]. We analyze R me for obtaining bound for
1 (T)) in the following.
Lemma A.4. Under En and policy n, we have
E g = Ô = (max((1SHD//0H233))/000 (2/3/2/311
Proof. Let a(i, be a sampled arm for j-th bad arm the i-th episode and myt be the number of episodes from the policy π over the horizon T. Suppose that the algorithm samples arm a(i, at time t (a(i.))). Then the algorithm stops pulling arm a(i. j) at time (z(a(i,])) 1 if (1ssst((.))))
< 1 --a 5 for some 8 such that (a(( S S (a( and tz (z(a(t, ()) 1--1-1111 for l E Z+. For simplicity, we use t and tz instead of 1 (a) and tz(a(i. when there is no confusion. We first consider the case where the algorithm stops pulling arm j(),j) because the threshold condition is satisfied. For the regret analysis, we consider that for t >> 12, arm a virtually pulled. We note that under E,, we have
(alt, / 12 (2zlog((///ss S Fisss 2 12log(()/m(sx:((((...))
s (a((a(i))) + 2 12 (2log(t))//ssss((((..)))
Then we assume that f2(2 12) is the smallest time that there exists 1 S s S i2 with 4-
for l E Z+ such that the following threshold condition is met:
(i(((i,))) + / (1rp(TT))/,,_(((iiiaaaaa < -
(17)
From the definition of 12, we observe that for given 12, the time step = s which satisfying (17) equals l (i.e. 8 = (1). Then, we can observe that n E (a(i,)))
5 (a(((()))
[C2 (Cg)))(T)/AA, (a(i.)) - 5)21 for some constant C2 > O, which satisfies (77). Then from
(a(t,, S 22,, (a),, (a(()))) for all E [mr], E [m we have nLe = (((((Ar(a(is)))
8).). Then with the facts that nf, 0 for [m9)/[mg] j (mf]//mrrr we have, for any i [m]] and j E [m²].
))
For 26 < x 1 let b(x) PPA (a) = æ/a is a bad arm). Then we have
b(x) = IP(A, (a)
> 26)
(P (a) = x)/P(A) > 26) = (P(A(()) (a) = z)/(1 )(20)
where C(26) < with small enough positive constant C < for d. We note that 28 <
Au, (a(i,))) = (a) s 1. Since n = O(1/(An, - 8)22 = Õ(1/8) we have
ta(a
12(a(())))1
E. = E
D (a(i,
Σ Ps
(((((()))
(=t((((i)))) (a(,0(
E A 8 + V B
< (a(i, + (1/8g)
Ô (f=
28 (x - 8)2 (b( dor 2
(18)
18

---

Recall that we consider 26 < 1 for regret from bad arms, We adopt some techniques introduced in
Appendix D of Bayati al. [5] deal with the generalized mean reward distribution with B. Let
K = (1 26)/6, aj =
(6511/6 b(t + 5)dt. Then for obtaining a bound of the last 2 and Pj = 510
equality in 18 we have
1-8
(1
8
(x - (8)= bl
bit blt+ + 8)dt
12)
26
K
(U+1)6
(t-
Σ
bit 8)dt
t²
16
j=1
K
2
(1+1)6
b(t 5)dt
j8
J8
K
Σ
ajPj.
(19)
==1
We note that E Pt Co for all j E [K] for some constant Co 0. Then for getting bound of the last equality in (19
we have
Σ 1=1
Σ
(az as+1)
Σ Pi
akk
Pb
1=1
K-1
Σ
(ag ()++)) + (oK))
1=1
K
= Cg a1 + Σ
Colj - -
j=2
0
((j8)* ((j 1)090)
8
j8
j=2
K
0
88
+
(0 (js -1 -1)9) (i-)))
(j
(20)
j=2
Now we analyze the term in the last equality in 20 according to the criteria for 8. For 3 = 1, we obtain
o
(00- +
Σ
K
1 (
(i- = Ō(1).
(21)
1=2
For 3 > 1, we have jo (j 1) S 23j8-1 following.
using the mean value theorem. Therefore, we obtain the
1 (08-1) (j (j0- G 1)9) --1))) =0 ( (( 30H1
0
83
1=2
0
Σ
1
0
80-1 1
8-1 (KK
1)0-1=1 -1) 11)
0(1).
(22)
19

---

For 3 < 1, when > 1 we have j -(j Therefore, we obtain
-(j- - -118 I B(j - 1)a-1 using the mean value theorem.
8
1 (08
(j8 (58- (j -1- (j-1)) =0 88-1 + Σ
500-1)
) (1 118-11
==1
K
0
8
8 1 (j- 1)8-2
j=2
1
0
8 0-1 88-1
((K + 1)8-1-11
3 3-1
0
80-1
8
1
((1 - -8) 10
(23)
1- B
From
19 20
22
and
23 we have
[ (10-
28 (x (0--6)3 6)22) o)22 b(x)dr Ómax 188-111 88-1)).
Then for any E [m²]. j [m²], we have
E E[ S E ((a VBB
Ô (max L1, 100x(1,80011 - EVV.31/88)
(24)
Recall that 1 m _x E [m) Re. With 8 = 6₁ (V (V7/7)2//) and m
[2V /5], from the fact that m ma's are i.i.d. random variables with geometric distribution with Elm;"1 (1/C(28)*) for some constant 0, we have
m
g
R [ = 0
IE
B [m
..j
JEE
0
(Vr
53 max (1, 58-13 + V
1
= Ô
(mxx(7(3+1)(642)) V (2/(0+2) 12/3/2/31)
(25)
From ReT(T) R& + (T) and Lemmas
A.
A.3
A.4
with
max (VT (Vr/T))/0022 133 we have
E (T) ò (Tax (2/((+2) (2/31//33)
(26)
in the following. In this case, we have 8 = ei max max(1/T 1/vT). For getting R c here we define the policy æ after time T such that it pulls VG amount of rotting variation for a good arm and 0 for 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 Vi amount of rotting variation if is good arm. For i [m]].j E [m{]] let v. and vB be 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.9's 's and vB as follows:
Case 2: Now consider Vr L/x
à is good arm,
[Vi
for i img
Vz (a(i.))
for i [m E [m for i [ E [m]].
vg-
Vi3
VT
for i |
1]
0
20

---

Otherwise, v = [Vr(((t)) Vvr
for E |
for E [myl.j E im],7] (V)(((())) 00
V 4.
for i E [m 1 [
for i E [m²) m - 11,5 E [mf]/ (m),))
For (m²), j E [m]] let n,, be the number of pulling the j-th bad arm in i-th episode from the policy. We define ur(a) the total amount of pulling arm over T. Here we define n ' as follows:
[nr(a(i,5))
for E [mf].j E [, for i E [m E [m
8 n 4.5
Then we provide m such that R2 (2)(T) S R in the following lemma.
Lemma A.5. Under Ey, when m C3 for some constant C3 > 0, we have R (T) < R
Proof. From Lemma A.2 under E1
find that V.8 2 min Vr) for i [m²]. Then m C3 for large enough C3 then with ò cj max(1/T)/0H) .1/111/ 1/VT) and Vr z max(1/T4//++), Ratpii,.///I// 1/VT), we have
Σ V 2 C3 min VT} > Vr,
which implies (T) <
R
mm
We analyze R., for obtaining bound for (T) in the following.
Lemma A.6. Under En and policy n,, we have
BRR Ô (max(T0/(++1),, vT})
Proof. From 24), for any E [m [m we have
E E|R 1 S [A(a(i, + v.
Ô (max 88-1) + E(V
m Recall that RB = >mm ii Σ Ej R With 5 = max (T) 1((+1), 1// and m = C3. from the fact that m²'s are i.i.d. (1/C(25))) - for some constant C'
(I/T))/((+))
random variables with geometric distribution with E[m = 0, we have
6 Σ Σ
)
JBB m
=
E
R
jm(m
Ô max 11 83 88-1)- + Vr/02)
= Ô ( vT)).
From Lemma A.1
with c1 max (1/T 1/ 1/VT) we have
E (T)) = ò [max vT3)
From 1T R2 (T) and Lemmas A.1 A.5 A.6 with ā = max 1/VT) we
have
E (T) = ò (max((T1(04)) ( (
(27)
21

---

Conclusion:
Overall, from 26 and 27). we have
B(R*(T) Ō max ( V /
2), vi /2//1/2/ ppr(tt)) vT)).
A.5 Proof of Theorem 3.3 Regret Upper Bound of Algorithm 1 for Abrupt Rotting (Sr)
as good arm if Ax(a) S 6/2, a near-good arm if 6/2 < Ar(a) I 26, and otherwise, a is a bad arm at time f. For analysis, we consider abrupt change as sampling new arm. In other words, if sudden change occurs to an arm a by pulling the arm 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 .g....... Let Ar be the set of sampled arms, which are pulled at least once, over the horizon of I time steps, which satisfies [Ar] S T. We also define Ag as set of arms that have been rotted and pulled at least once, which satisfies [As] < Sr. To better understand the defimitions, we provide an example. If an arm a suffers abrupt rotting at first, then the arm is considered to be 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 E Ar and {a', a") E As but a & As. If arm a" is not pulled at least once but and a' are pulled at least once, then {a, a'} E AT and a' E As but a" As.
Using the threshold parameter á in the algorithm, we define an
WLOG, the following proofs proceed under the given Ar, since the proofs hold for any Ar. Let Pata (a) -E (a(a) a)/m(t..aa(a)) We define the event Ej {2 [e (a)l S / 12 (T) (f...) (a) for all 1 S 81 S $2 S T,a E Ar By following the proof of Lemma 35 in Dylan J. Foster [12), from Lemma A.30 we have
12 log T
[a) (a) - MMoore)) (a) S Mp)s.co)(a))
Σ P n=1
X, S &V12
(28)
T
where X, =r, - 11. (a) and Tú is the i-th time that the policy pulls arm a starting from 81. We note that even though X, 's seem depend each other from T; s, each value of X, is independent of each other. Then using union bound for s), $2, and E Ar, we have
P(E)) S 2/T².
Let t(s) be the time when s-th abrupt rotting occurs with Pa(e) for s E [Sr]. Then we have (a) 0(1 + P((s)) = 0(1 + VT) for any and t, which implies E[R E1] = O(T + TVr). For the case that E1 does not hold, the regret is ER [T) [TIPP(E))) = O((1 + VT), which is negligible comparing with the regret when E, holds true which we show later. Therefore, in the rest of the proof we assume that E, holds true.
Recall that RT = El - m+(a))) For regret analysis, we divide (T) into two parts, (T) and (T) corresponding to regret of good or near-good arms, and bad arms over time T. respectively, such that R2 (T) (T) + R (T). Recall that we consider abrupt change as sampling a new arm in this analysis. Then, from A (a) < 20 for any good or near-good arms a at time I, we easily obtain that
E (T) = O(8T) Omax S (11//111)/////0011 11/0411) ( VSSTH).
(29)
Now we analyze (T)). We divide regret R (T) into two regret from bad arms in Ar/As. denoted by RT. and regret from bad arms in As, denoted by R3.)(T) such that R²((T) = RT) + R8.) We denote bad arms in As by Ag. We first analyze RBB1(TT) in the following. For regret analysis, we adopt the episodic approach suggested in Kim et al. [3.. The main difference lies in analyzing our adaptive window UCB and more generalized rewn-r distribution with
22

---

3. In the following, we introduce some notation. Here we only consider arms in Ar/ As so that the following notation is defined without considering (rotted) arms in As. We note that from the definition of Ar, arms before having undergone rotting are contained in Ar/As. Here we consider the case of 26s(3) (8) < since otherwise when 25x(3) 2 1, bad arms are not defined in Ar/As.
Given a policy sampling arms in the sequence order, let m be the number of samples of distinct good arms and m be the number of consecutive samples of distinct bad arms between the 1- and i-th sample of good arm among m good arms. We refer to the period starting from sampling the - 1-st good arm before sampling the i-th good arm as the i-th episode. Observe that mf ........ m are i.i.d. random variables with geometric distribution with parameter C(25)9 for some constant C > 0, given fixed value of m Therefore, for non-negative integer k have P(mm k) = (1 ((26) (( for i 1,... ..........
Define my to be the total number of samples of a good arm by the policy π over the horizon and m to be the number of samples of a bad arm in the i-th episode by the policy ı over the horizon T. For i e [m j [m let n be the number of pulls of the good arm in the i-th episode and n.. be the number of pulls of the j-th had 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 modified strategy after T. Under a policy π, let R be the regret (summation of mean reward gaps) contributed by pulling the j-th bad arm in the i-th episode. Then let 0 = Eie Eje(m,]] R which is the regret from initially bad arms over the period of m episodes. For getting R here we define the policy x after 7 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, pulls the arm up to amounts à is good arm let n and nf, 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 nf 's and B 's as follows:
and ng < T. For i [m²]. j E [m='] "i
If ā is good arm,
n
for i E i -1] 1]
[nf
for i E [m j E [m for i E [m [/ [m/1/(m
n
T
for i my
G
15 n
10
for e [m
Otherwise,
n
for E [m
[ [
for E j E [m
n
T
for i = m +1
to
for i E [m [mg 11 E (mfl/(mrr)
0
for E [ +
Using the above notation and newly defined æ after T, we show that m ST + 1, then (T) < RB in the following.
Lemma A.7. Under E,, when m = ST we have
BB. S R
Proof. There are ST number of abrupt changes over T. We consider two cases; there Sr abrupt changes before sampling Sy-th good arm or there are not. For the former case, æ samples the -h good arm and there S7 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 E', from E; and the stationary period, we have
(a) + v log) 2 (e 2 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 good arm, m = T'. Therefore, the algorithm pulls the good arm for I rounds.
23

---

Now we consider the latter case, such that π samples the Sy-th good amm before the Sy- 1-st abrupt change over T. Before sampling the Sy-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 and ST 1-st abrupt change must occur after T.
Therefore, is enough consider the former case. When m ST, we have
Σ iE/m9)
n 2 T,
which implies R (T) S R R
From the above lemma, we set m = Sr. We analyze R mg to get a bound for R (T) in the following lemma.
Lemma A.8. Under E1 and policy ग,, we have
E [ = Ô (S
v STT)
Proof. Recall that we consider arms Ars Let j] be sampled arm for j-th bad arm in the i-th episode and my be the number of episodes from the policy x over the horizon T. Suppose that the algorithm samples arm j) at time t (a(i, Then the algorithm stops pulling arm a(i, j)) at time (z(a(i, j)) + if ((s.ta(((..))) + /12 log) (asta))))s (a) < 1
for some such that
t (a(i,))) < 8 & t2(a(i,)) j)) and s = (z((((,))) + 2 for E zt For simplicity, we use t and l2 instead of 1 ()) and tz(a(i,)) ()) when there is confusion. For the regret analysis, we consider that for t > tg, arm a is virtually pulled. With E1. we assume that fz(2 12) is the smallest time that there exists f S s < 22 with s = =t +1 for E zt such that the following condition met:
Ny (a(i.))) + 12 (as <
(30)
From the definition of fz. we observe that for given fg, the time step = satisfying (30
equals to t1 (i.e. s' = t1). Then, we observe that ni Fa) (a(i.j)) nig Fy (a(i, j))
[C2 (og()))))(A,, (a(i.)) 5)27 for some constant C2 O, which satisfies (30). Then from Nit, (alii, (a(i, S .2. ()), for all E [mT],J E [m we have n = Ó(1/(A,, (a(t,)))-
5)²). 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 new arm) or T. Then with the facts that nf, 0 for i [m²]///r] E [mf]// [m,rr, we have, for any i E [m]] and j E [m,].
ni.j (Ol((,,,((ii,)))) - ))
For 25- < x < 1, let b(x) = IP(A,, (a) = æ/a is bad arm) Then we have P(A,, (a) =
ala is bad arm) P(A,, (a) x D (a)
20) P(A,, (a) x)/P(Ai(a) > 26)
P(A,, (a) =) C(28)*) O(P(A A (a) x)). where the last equality comes from small 5
with small enough c1 < 1. For any E im mm],
1.je E [m,
11 we have
E s [ (a(t.)) (a(i, ())
1
rb(2 dxz
(31)
25 (xr 8)22
From the above results in 3
for B > we have
E (max (1, 8 88-11).
Recall that R8 mg
R With d e₁ (ax (S7/T) and m A.7 and the fact that mtss are iid. random variables following geometric
6
Em
Sr, from Lemma
24

---

distribution with B/mp] = (1/C((6))) - 1 for some constant C' > 0, we have
E| E mg] = O
Σ
Σ
i=1 jE (mm))
=
ST88 1
max 1, 888-13
Ô
[max ( 10 /SrT))
From Lemma A.8. we have ER [[T] = E[ m0 Ö (max = ( , VSTTT)
Now we analyze RT) in the following lemma. Here, we consider arms A which is allowed to have negative rewards.
Lemma A.9. Under En and policy n, we have
E [(T) = Ô (max Vr))
Proof. Recall that consider arms A that Dr, (a) 25 from definition. Suppose that the arm a is sampled and pulled for the first time at time (a). Then the algorithm stops pulling arm a at time (a) + 1 if [[stt((a]]( S (a) and 8 = 12(a) + 2'-1 for 1 E - For simplicity, we use 1 and l2 instead of in (a) and ta(a) when there is no confusion. For regret analysis, we consider that for > f2, arm a virtually is the smallest time that there exists la 2 for I g+ such that the following condition is met:
(a) + (12
< 1 - for some such that
pulled. With E2, we assume that (2(2 (2)
Ez with
Me (a) + 2 12 (Tgg
5.
(32)
From the definition of ig, we observe that for given iz, the time step s, which satisfies (32) equals to 4. Then, we can observe that (i,,, .z] (a) = max log(T)) (a) 8)21, 1} for some constant
C2 > O, which satisfies (32). From the above, for any E A satifying A,, (a) 2 /Cz + 5, have 2|t, F2) (a) 1. This implies that after pulling the arm a once, the is eliminated and after that, the arm not pulled anymore. Therefore, for any arm a' which was rotted a, we have (ar)""((a) (a') < /Ca Iog(T) + 8. This is because otherwise such that (ar) (ar)aaa)) 2 (C2log(T)) the arm a' is climinated and cannot be pulled which means a & A5. which a contradiction. Then for any arm a E Ag we have Ae, (a) S C2 log(T) + 8 (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 note that (a)(a) Pt(s) when arm is sampled arm from s-th abrupt rotting for E [ST].
From n (a) I (O), we have (a)) = (4)) 8)),))) 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 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 A,, (a) 2 25. Then the regret from arm a, denoted by R(a), is bounded as follows: R(a) = A., (a,(M), (a) = Ómax Ar, (a)/(A,, - 5)2, Ar, (a))). . Since x/(z 5)2 < 2/5 for any 2 26, we have R(a) = Ó(max (1 1 166, A,, (a))). Therefore, with the fact that A,, (a) I CC2 log (T' + 8 + P((a) for the corresponding [Sr] such that (t) P((a).
25

---

we have
11
De, (a) ta
E
Σ
R(a)
=
max
Sr/ E
Σ
aE
LaEAS
E(pucilHt)
Sr Ó(max /T, _ B(p(n)l)))
Ómmxx ( (
where the second last equality comes from 8 2 Sr. Finally, from R (T) R (T) R
29 and Lemmas A.8 A.9
we have
(T)) = (p STT. Vr])
A.6 Details for the Case of Unknown Parameters
Algorithm 2 Adaptive UCB- Threshold with Adaptive Sliding Window Given: T, H, B, A, a, C
Initialize: A'' < A, w (8))) + for 8' E
for 1,2, ..... (T) H do
1'+ (i H)H +
Select
A'
Pull arm and get reward (((-1)H+1
p(8') + (1 - a)-=a) EveN w(A a for E B
w(6')
Select 8 8' with probability p(8') for 8' B
for = (i - 1)H + -2.... -2..... ......i.... H T do
if (ia) WUCB(a, 8, H) ô then
A' (a/{a)
Select new arm a E A''
Pull arm a and get reward rs t' +-t t else
Pull arm a and get reward end if
end for (6) t- w66 exp
--HAT E
Bp(d)
CH H4
end for
Here, consider the case where there are constraints for both S7 and Vr, and parameters of Vr. Sr, and 3 are unknown to the agent. We note that Vy < Vr from the constraint. The parameters of 3, Vr, and ST are used the parameters are not given, the procedure to find the optimal value å is required. We adopt the Bandit-over-BB Bandit (BoB) approach in Cheung al. (TT] Kim al. [3] by additionally considering adaptive window. In Algorithm| 2] the algorithm consists of master and several base algorithms with B. For the master, we use EXP3 [2] to find nearly best base B. Each base represents Algorithm [ with a candidate threshold 8' E B. The algorithm divides the time horizon into several blocks of length H. each block, the algorithm samples base B from the EXP3 strategy and runs the base over the time steps of the block. Using the feedback from the block, the algorithm updates EXP3 and samples a new base for the next block. By block time passes, the master is likely to find an optimized in B. Let B [3]. Then for Algorithm 2 we set a = min(1, / B log B/(ee - H]]THH]) and
the optimal threshold parameter in Algorithm [ Therefore, when
C. > 0 to be large enough constant.
26

---

We define 86 = 01 max (Vx ((442) / 164 1,V,, and 8%
e1 (Sr (1 (3+11) 1/vH] for some constant 0 < c < 1. Then the optimized threshold parameter is 8/ = (8.. 8... 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 c1 c//VIl S 64s S 1. Therefore, we set B =
/ which is the candidate values for unknown ot.
The regret is composed of two factors from the master and bases. To ensure that the regret bound from each base concerning Vr and Sr remains guaranteed irrespective of the bases chosen, we consider a constrained adaptive adversary. For the following, we consider that d for all & >> 0 are arbitrarily determined before an algorithm is run, under the constraints of Vr and ST where Σi= 2t S Vr and 1 + Ei= (e: + S Sr. Then under e for all / O, we consider the following adversary for rotting rates.
Assumption A.10 (Constrained Adaptive Adversary). At each time 1 > O, the value of rotting rate Pt. is determined arbitrarily immediately after the agent pulls an arm 0r under the constraint of 0 S Pt S @: for given @t.
Remark A. Assumption A. 10 is still more general than that for the maximum rotting rate constraint in Kim et al. [T3 where @: p for all t > 0. We also observe that the constrained adaptive adversary in Assumption A.I0 is milder than the adaptive adversary in Assumption 2. Additionally, we note that a special case of constraint Pt = Or for all & >> 0 in Assumption A. represents an oblivious adversary because O: 's are determined before an algorithm is run.
With a time block size of H (where H = [VT). the algorithm operates over [T/H] blocks. Denote by Ti the set of time steps in the i-th block containing time steps of - 1) + 1 S t S iH A T.T. It possible to encounter large rotting for some 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. ΣIET, Pt S H for all i E [[T/H]]
Remark A.13. As similarly highlighted in Remark [2.]] this assumption is satisfied when mean rewards are under the constraint of 0 S pr(a,) < for all E [7], 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 P: S H for all i E [[T/H]] is more general in scope than the one with a maximum rotting rate constraint where Pr S p p== -p=0(1 o(1) for all / E [ - 1}, which was explored in Kim et al. [13] This is because for our setting, Pr is not necessarily bounded by (1), and for the maximum rotting constraint setting with pr S p = o(1), the condition of E.ET, Pt < H for all i e [[T/H] is always satisfied. It is noteworthy that Assumption A.12 implies Assumption 2.4
We provide a regret bound of Algorithm following.
2 under Assumption A. 10 and Assumption A. 12 in the
Theorem A.15. Let Rly and R's be defined as
V 3 T 2+1 2941
+
for 3 az4 1, 2342
max ( {S [ T ZंP + TETT Vid for 821,
20+1
Ry
and R's
V +
for 0 << 3 <1
max VSTT + T Vr}
for 0 3
Then, the policy n of Algorithm
with H
T achieves the following regret bound:
E (T)) = Óminn R(s))
Proof. The proof is provided in Appendix A.7
We can observe that there is the additional regret cost of ((2841)((2++)) for 3 > 1 or 73/1 for 0 < B < compared to Algorithm [ This additional cost originates from the additional procedure to which is negligible when Vr and ST are large enough.
leam the optimal value of e in Algorithm 2
27

---

Remark A.16. In the case where the value of B is known, setting H = mmx ( vTH
reduces the additional regret cost of Algorithm 2 to max(T(++2)(0+3) T3/4).
Attaining the optimal regret bound under a parameter-free algorithm remains an open problem.
A.7 Proof of Theorem A.15 Regret Upper Bound of Algorithm 2
In the following, we deal with the cases of (a) 8f S 8/ so that 8//5 5% and (b) o, 8g so that b/s 8g. separately.
A.7.1 Case of o% S 5/
Let (00))) for 8' E B denote the base policy for time steps between (i 1)Hf + and i H A T in
Algorithm 2 using 1 - 8' as a threshold. Denote by ar =:(6") the pulled arm at time step t by policy (8'). Then, for ot E B. which is set later for a near-optimal policy, we have
T
HAT
B|R (T)
Σ
(e(a;)
= (TM
(33)
11++1
where
T (T) Σ
[T/M
HAT
Σ i=
Σ
uela,
t=1
and
[T/H]
HAAT
IT/M
HHAT
(5(T) = Σ Σ
(e(a
Σ
Σ
pe(af)
E (1-1)4+1
(1-1)8+1
Note that (T) accounts for the regret caused by the near-optimal base algorithm (6'))ss against the optimal mean reward and (T) accounts for the regret caused by the master al- gorithm by selecting base with 8 B at every block against the base with öt. In what fol- lows, we provide upper bounds for each regret component. We first provide an upper bound for [[R (T)) by following the proof steps in Theorem 3.1] Then we provide an upper bound for (T)). We set H [ and 5t to be smallest value in B which is larger than ot c (Vx((V//T)V((22) (Vr/T) ///////1////////// 1/H1/(0411, ( 1/H1/2).
Remark 1.17. One might wonder whether R2 (T), regret from the near-optimal base of at, satisfies the constraint of Vr and Sf even though the master may not select the near-optimal base in the algorithm for each block. From Assumption 1aaumptioonoAO0 we can guarantee the constraints of Vr and Sy for rotting rates from each base regardless of the selected bases from the master for each block because the rotting upper bound @: 's are determined before staring the game regardless of the behavior of the master. Therefore, we can utilize VT and ST for bounding RI (T), which is the regret from the near-optimal base of 8t.
Upper Bounding (T)]. We refer to the period starting from time step (i H)H + 1 to time step i H A I' as the i-th block. For any i E [(T/H) - 11, policy (,1))) runs over H time steps independent other blocks so that each block has the same expected regret and the last block has smaller or equal expected regret than other blocks. Therefore, we focus on finding bound on the regret from the first block equal to ΣH ((a) < 8t /2, a near-good arm 88/2 2 < ((a) < 28t, and otherwise, a is a bad arm. In A, let á1 d2,.... : be sequence of arms, which have i.i.d. mean rewards following ( Without loss of generality, we assume that the policy samples arms in the sequence of @1, a2,....-
(a,aa,15))) We define an arm a as a good arm
Denote by A(t) the set of selected (explored) arms in the i-th block, which satisfies IA(i) s 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 Fit, .t) (a) = Ete (aja)//(ess We define the event Ej = (P(()))))
[[ (a)l < /12 log( H) (H)/HHH)HHHH/
for all 1 S I $2 H, A(1)) As in (6). we have P(E)) < 2/H².
28

---

We denote by VH, = EIET Pt the cumulative amount of rotting in the time steps in the i-th block. From the cumulative amount of rotting, we note that (a O(HH, + 1) for any a and t in i-th block, which implies E (T)) [i] = ( from VH S H under Assumption A.12 For the case where E₁ does not hold, the regret is
O(1), which negligible compared to the regret when E1 holds, which we show later. For the case that E1 does not hold, the regret (E)) (1), which is negligible compared with the regret when En holds true which we show later. Therefore, in the rest of the proof we assume that E1 holds true.
(T) (T)
E| [H)PE)
In the following, first provide regret bound over the first block.
For regret analysis, we divide (mm (H) into two parts, Ro (H) and Ro (H) corresponding to regret of good or near-good arms, and bad arms over time H. respectively, such that ((m((") = R (H) + R R8(H) (H). We denote by VH, the cumulative amount of rotting in the time steps in the i-th block. We first provide bound of R (H) in the following lemma.
Lemma A.18. Under Ei and policy x. we have
EIR& (H) Ô (HOt ( 1/33
Proof. We can easily prove the theorem by following the proof steps in Lemma A.1
Now, we provide a regret bound for RB (H). We note that the initially bad arms can be defined only when 28 < 1. Otherwise when 28 2 1, we have R(T)) = R (T'), which completes the proof. Therefore, for the regret from bad arms, we consider the case of 25t 1. For the proof, we adopt the episodic approach in Kim et al. 13 for regret analysis.
Given policy sampling arms in the sequence order, let m be the number of samples of distinct good arms and m be the number of consecutive samples of distinct bad arms between the - 1-st and i-th sample of a good arm among m good arms. We refer to the period starting from sampling the i 1-st good arm before sampling the i-th good arm the i-th episode. Observe that m ...., m mg i.i.d. random variables with geometric distribution with parameter 26, given fixed value of m Therefore, for non non-negative integer l we have P(m = k) = (1 _))
C(28t) ( for some constant C > 0, for i 1,..., .mS Define f. to be the number of episodes from the policy h over the horizon H, i7t to be the total number of samples a good arm by the policy л over the horizon H such that m = mus or m = m. - 1, and B to be the number of samples of a bad arm in the i-th episode by the policy (ō+) over the horizon H.
Under a policy mı (5t), let R, be the regret (summation of mean reward gaps) contributed by pulling the j-th bad arm in the i-th episode. Then let RB >m Eje(m)) Re,; which is the regret from initially bad arms over the period of m episodes.
For obtaining regret bound, first focus on finding required number of episodes, m such that R (T)) < R Then we provide regret bounds for each bad arm and good arm in an episode. Lastly, we obtain regret bound for E E (T)) using the episodic regret bound.
Let (i) be a good arm in the i-th episode and aii,j) be j-th bad arm in the i-th episode. We define VH(a) > pa, a). Then excluding the last episode mH over H, we provide lower bounds of the total rotting variation over H for a(i), denoted by Vn (a(i)), in the following lemma.
Lemma A.19. Under Es, given m. for any [ (m } have
Va(((1)) 2 8//2.
Proof. We can easily prove the theorem by following the proof steps in Lemma A.2
We first consider the case where Vr > /
In this case, we have 1/33. Here, we define the policy म after time H such that
5t = C1 max max((Vr/TT) (VV+/)))//(++) 1/(++2) (Vr/T) pulls a good arm until its total rotting variation equal to or greater than 5t 51/2 and does not pull a sampled bad arm. We note that defining how works after H is only for the proof to get regret
29

---

bound over time horizon H. For the last arm à over the horizon H, it pulls the arm until its total variation becomes max /2, VH (ā)} if ā is a good arm. For i E [m²], j E [m let V and V 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 define V.9s s and V 's as follows:
is good arm,
v (VH(a(i))
for [ -
(v((((i,5)
for E [m E [m for E f/ [m
V
for E [m9]/mm, -]
00
Otherwise,
v (V((((i) for i [m
for i [ [m (a(,)()))) 10
VB 1. =
10
for E m/m
for E [m]]/(in - 11,j j E [m/]/ [
For E [m]]. E [mm] let nf, be 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 (a) be the total amount of pulling arm over H. Here we define n 's follows:
(n((a(t,))) 00
for i E [m E [m for i E fm [m
Then we provide m such that R (H))
I R m in the following lemma.
Lemma A.20. Under Et, when m
[2V 12VH,1081 we have
R (H) S e
Proof. We can easily show the theorem by following the proof steps of Lemma A.3
From the result of Lemma A.20 we set m = [2VH,,16*] the following, we anlayze RB for obtaining a regret bound for (HH..
Lemma A.21. Under E, and policy n, we have
E[R m9) = Ô (max (Tw.aT//V))0///////C
+ (T/V+)8/(042), VT.((/V/r)23 (T/V+))/3))
Proof. We can easily prove the theorem by following proof steps Lemma A.4 From 24 for any i E [m$], E [mf], we have
B < ((a(i, + V.
Ô (max (1, (ot) F[
Recall that R m = 12 / from the fact that mf'ss are i..d. random variables with geometric distribu- tion with Emm B = 1/(20t)0 - 1, we have
m
i=1 E Ej R With 5t eι max (V7 (V//T)1/3} and
a
E o
E
R5
j (m
(E[VH..)/8*
(81)3 max (8t) E[VH.)/((6)))
[[ max
})
max
(5t)a+1
(ōt)²
(ōt)3)
Ō
[mxx<[BV)a:((T//)))004111 + (T/VT) 0/18-2) E EVVVn. (T/V)))/33).
30

---

24 for any From R=1(6)) (H) (H) + (H) and Lemmas
A.18
A.20
A.21
with 8t
max (Vr. 1//4222 (VT/T) we have
B[Rmi(6') (H))
Ō ( (max [ ((VT/T)M((+2) + (T/V1))8/8443
[[VV.I(T/VV) 2/3 H(V (T/V7) 11 11 ([V (W.
The above regret bound is for the first block. Therefore, by summing regrets from [T/H] number of blocks, from Vr > max(T/ ((8+))/(8++) TT/H//// H = [T and the fact that E E pil - Vr, using Hölder's inequality we have shown that
(T/V>) E[R = Ō (max(T(6+1)004)) (2110+2) / H max (T/VT) (//1))//000,(/////))/
= Ö (max(T(0-1/042) 22 ,2// max(7(2041/100-)) 12/1)..
(34)
Now, we consider the case where VT S max(T/H>/2 (//((/-)/8+t1)) In this case, have 8t max(1/VEL // }. From the result of Lemma A.20 by setting m [2VH,1 we
have R (H) (H(H) < R mg-
Lemma A.22. Under Ej and policy x. we have
E[R = (TVT)) (T/V7)
Vn, (T/V7)22 (T/V>)2/31)
Proof. We can easily prove the theorem by following proof steps in Lemma A.4 From i [m²]. E [mf*), we have
E E S |A(a (a((i, + v
= Ō (max (1, 8 88-1) + 1/
Em E [m Re With = cı max (1/ 1/2 1//p//11//////// 1/HA/(0-11 and m 12VH,1/b 1887, from the fact that mf's 's are i.i.d. random variables with geometric distribution with E|m = (1/C(28t) 1, we have
Recall that R
E E
0
E
Σ
Σ
R
1=1
jE !1
(E(VH.1l/8t + 1) (8t)s max (0t) + E|V
[[(H.,] (51)3+1
E [H,
+ max (ot)s 57 11)
max
(ōt)²
EVVH,,) max ( (110))))))))))))))))))))))))))) H1/22). Ô
From Rmi(d" -R) + RH) and Lemmas A.18
A.20
A.22
with 8t
O(max(1/ 1/2 1/H1/(041)) we have
E( = ( + 2 1/3
H.1 BVvn,)H)
31

---

Therefore, by summing regrets from [T/H] number of blocks and from Vi ((max(T/H' T/ 1111 = [ and the fact that length of time steps in each block bounded by H, we have
T/H
IT/H 1
T
E. R4 (T) Ô
max (0011))
H1121
H B
H.3
H
Ö
T
max H (0+(11)), H1?23 + T v/ 1/3
V.H
H
= (max / 11
= Ô (max(7(35-1//224)) T2/1))
(35)
where the second equality comes from Hölder's inequality.
From
34
and (35)
have
E R [T) = (0000mm((--1111022))
+ T(2941)(2242) r2/sy// + +T/11)).
(36)
Upper Bounding ([H5(T) (T)]. We observe that the EXP3 is run for [T/H] decision rounds and the number of policies (i.c. Ty (6') for 8' E B) is B. Denote the maximum absolute sum of rewards of any block with length Ii by random variable Q' We first provide bound for Q' using concentration inequalities. For any block i, we have
$- HAT Σ
SHAT Σ
SHAT Σ
(e(af) + mh
pe(at)
(37)
(=(1-))++1
1)
(=
Denote by T; the set of time steps in the i-th block. We define the event Fnz(1) (17 (a)
(eeree)((a)) (a) S (o) (a), for 81, T, S 82, a E A(i)} and E2 =
NieliTym) (i).). From Lemma A.30 with H [VT] have
2H3 2 H6 S T
P(ES)
By assuming that Eg holds true, we can get a lower bound for 14 (a()), which may be a neg- ative value from rotting, for getting upper bound for E (ax))) We can ob- serve that HHHT 2 Me(a;) s H. Therefore the remaining part is to get a lower bound for - (az). For the proof simplicity, we consider that when arm is rotted, then the arm considered as a different arm after rotting. For instance, when arm is rotted at time 8, then arm considered as a different arm a' after 8. Therefore, each arm can considered to be stationary. The set of arms is denoted by L. We denote by L the set of arms having (a(a) 0 for E L. We first focus on the arms in C/C+.
Let kmax denote the maximum value in B so that 6max = 1/2. With F. and C+ we assume that (2 (2) is the smallest time that there exists t < s S l2 with = 1/ + 1 - 2/-1 for / E z such that the following condition is met:
Me, (a) + (1) + /
(a) 8max.
(38)
From the definition Eg. we observe that for given ig. the time step s, which satisfies (38) equals to f.. Then, can observe that n du) (a) max{ log (H)/ (a) 6max) 2²
for some constant C2 > 0. which satisfies (38 From (a) I (a), we have
(a) < max(Ca log(H))((AA))mmm) (a) - d 2,13 for some constant Cs > 0. Then the
regret from arm a, denoted by R(a), is bounded as follows: R(a) = A,, (a) S
max (Cg log( H) (H),,, (a)/(A,, (a) 8max) )2 A,, (a)). Since x/(x 8max)² < 1/(1 8max
4 for any 1. have D (a)/ (A (a) )max)² )2 S 4. Then we have R(a) S
32

---

log(H) H)) Ad, (a)} for some constant C₁ > 0. Then from [ <
H, we have
EaEc/(E-) R(a) I max[C,H H)) H. VHH..-
Since Enect R())= I H, we have Enec R(a) S H max (
H + VH,.). Therefore
from I((a) (t)h(()) (1 pr(a)), have
(2)
iAA
Σ
pc(at) 2 logx(C) + VH,s),
(1-1))4+
which implies that from VH S H under Assumption A.12 for some C5 O, have
HAT Σ
(e(az)
(max(C)Hloog(I) H + Vn,) S CsHl log(H))
11
Next provide bound for Σ HAT 2 H log(T)) and Ea [el[Trmm (i). From Lemma A.30 for any i E [[T/H]], we have
(1= Mol- We define the event Et) <[E ([t==((11)++11 Mcl
HAT
2 ((Ea())) T
Then, under Eg n Ez, with 37). we have
Q' S max ( (C3 log H. HJ + 2 lTg S C5H log H 2/ H log(T),
which implies 1/2+ 1/2+Ei HAT T
/C/(C, H log H H44 T) E [0, 1] or some large enough C' > 0.
With the rescaling and translation of rewards Algorithm P from Corollary 3.2. in Auer et al. (2]
have
E E[ E2 n Eg] = Ō ( H + 22 H log 1) BT/H =Ō (O(VBTTT
(39)
Remark A.23. Regarding the utilization of the regret analysis of Corollary 3.2 (EXP3) in Auer et al. 2). note that the reward for each base be defined independently of the actual master's 's action. One might wonder whether the regret analysis for EXP3 can be utilized, considering the fact that the reward from 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 whether the rewards from each base 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 d E B at time when a block starts, denoted (6)),, the reward obtained when the master selects base ō (even though base ö is not actually selected from the algorithm). Then, we can define (5) for each 8 regardless of the master's actual action. In other words, irrespective of the actually selected base, we define (5) for all E B as the reward that the master can obtain by selecting ò. In such a case, whatever the selected base by the master is time 2z (6)'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 regret bound regarding the master (R3 (T)).
Note that the expected regret from EXP3 is trivially bounded by (THHH = o(TH) and B Ollo)T))) Then, with (39), we have
E( = E (T) Fez n FaJT E3) -( P(ES = Ō (VHT) + (TH)))//3)
Ō (Ö(VHT)
(40)
Finally, from 33 36 and 40
with H = 1/2 we have
R (T) δ
max 1/8 1 211
+ T 2 V . + +Tt))
which concludes the proof.
33

---

A.7.2 Case of o% > 5/
Let (6') for 8' E B denote the base policy for time steps between (i 1)H + and i- H A T in
Algorithm using 1 - 8' as a threshold. Denote by aj ((66") the pulled arm at time step t by policy (..).. Then, for 8t E B, which is set later for near-optimal policy, we have
FI
SHAT
E[)
Σ
Σ
p((a;)
E +
(41)
11--1)
where
T (T) Σ
(T/M]
HHAT
Σ
Σ
(e(az((0))
(i-1))
and
HAT
HAT
(5(T) Σ
Σ
Me(a, (((
Σ
Σ
pe(a.).
(1-1))++1
(1-1))1+
Note that RT (T) accounts for the regret caused by the near-optimal base algorithm n. (8t)'s against the optimal mean reward and R (T') accounts for the regret caused by the master algorithm by selecting a base with 8 E B at every block against the base with 8t. In what follows, we provide upper bounds for each regret component. We first provide upper bound for [E[ by following the
proof steps in Theorem 3.3 Then we provide an upper bound for E[Rg (T)). . We set 8t to be smallest value in B which is larger than 5% c1 (a (T) /T 1/(++1) 2/8-11 /T) , 1/2 (ST (555/)//2,1//112
such that we have 81 =mmaax ((Sr/T))/i--,,11///
Upper Bounding [[][ We refer to the period starting from time step (i - 1)H + to time step i. H as the i-th block. For any [T/H 17, policy (5t)) 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 good arm if
the regret from the first block equal to DH 1 (a(a. (a,"..""")) We define (a) /2/2, a near-good arm if 8" /2 < (a) < 28t, and otherwise, is a bad arm at time I. In A, let (1, U2, be a sequence of arms, which have i.i.d. mean rewards following For analysis, we consider abrupt change as sampling a new arm. In other words, if sudden change occurs to an arm a by pulling the arm 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 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, a2......
Denote by A()) the set of sampled arms, which are pulled at least once, in the i-th block, which set of arms that have been rotted and pulled at
satisfies [A(i)] H. We also define As(i) least once in the i-th block, which satisfies (As(i)) < S,, where S; is defined as the number of abrupt changes in the i-th block. Let Mat,, (a) = Ele,, Pt(a)) nis, (a). We define the event
Ej (1 (a)
[()) (a)] S log H H/) (a) for all I s S s2 S H.a E A(i))
From Lemma A.30 as in (6), we have
P(E)) 2
For the case that Ei does not hold, the regret is E[ (T)PET)((ET) = 0(1), which is negligible comparing with the regret when Eú holds true which we show later. Therefore, in the rest of the proof we assume that E₁ holds true.
In the following, first provide regret bound over the first block.
For regret analysis, we divide R (6') (H) into two parts, R (H) and (5(H) corresponding to regret of good or near- arms, and bad arms over time T, respectively, such that R (H) 12 (H) + (H). We can easily obtain that
(H)
E R (H) = O(8) H),
(42)
34

---

from A(a) S 25t for any good or near-good arms a. Now analyze R (H)). We divide regret R8(H) (H) into two regret from bad arms in A(1))As()) denoted by (H), and regret from had arms in As(1), denoted by ( such that R (H)
(H) + (H). We first analyze (H) in the following. We consider arms in 4(1)/As(1)
For the proof, we adopt the episodic approach in Kim et al. [I3] for regret analysis, In the following. we introduce some notation. Here we only consider arms in notation is defined without considering (rotted) arms in (1().. Given a policy sampling arms in the sequence order, let m² be the number of samples of distinct good arms and m. be the number of consecutive samples of distinct bad arms between the i - 1-st and i-th sample of good arm among m² good arms. We refer to the period starting from sampling the i 1-st good arm before sampling si the i-th good arm as the i-th episode. Observe that m ..... m a 's are i.id. random variables with geometric distribution with parameter C(25t)$ for some constant C' > 0, conditional on the value of m² Therefore, P(m, = k) = (1 )( C* for i 1,...,m". m².
so that the following
Define m to be the total number of samples of a good arm by the policy Tı (dt) over the horizon H and " to be the number of selections of a bad arm in the i-th episode by the policy x over the horizon H. For E [ j E [ let no be the number of pulls of the good arm in the i-th episode and n, be the number of pulls of the j-th bad arm in the i-th episode by the policy T (8+) over the horizon H. Let à be the last sampled arm over time horizon H by T (8t).
With a slight abuse of notation, we use mi (8+) for modified strategy after H. Under a policy nı (6*), let RC, be the regret (summation of mean reward gaps) contributed by pulling the j-th bad arm in the i-th episode. Then let R = Σm Eje(me] R which is the regret from initially bad arms over the period of m episodes. For getting R here we define the policy πι (ōt) 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 up to H amounts if å is H. For i [m²]. j E [m]]
let n. and nē, 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 's and mi 's as follows:
good arm and π. y
If à is good arm,
for i Im G
1]
[
for i [m [m for i [m²]/mg]
n
H
for m
..i.j
8
0
for i E [m //
Otherwise,
for i E |
[
for i E [m E [m
m
H
for m +1 1 for E |/m
8
0
for i [m9]/[mg 11.j E (mf1/mm..l
0
With a slight abuse of notation, we detine St to be the number of abrupt changes in i-th block. Then, we show that if m = St, then 18 < R
Lemma A.24. Under E,, when m Si we have
1 < R
Proof. There are most S₁ number of abrupt changes over the first block H. We consider two cases; there are S 1 abrupt changes before sampling S1-th good arm or not. For the first case, if Ti (61) samples the -i good arm and there are S₁ 1 number of abrupt changes before sampling the good arm, then it continues to pull the good arm for H rounds from Ej and the definition of Ty (61) after H.
Now we consider the second case. If TT (ōt) samples the Si-th good arm before T and there is at least one abrupt change after sampling the arm, then before sampling the Si-th good arm, there must exist two consecutive good arms such that there is no abrupt change between sampling the two good arms.
35

---

This is contraction because Tı (6t) must pull the first good arm up to H under Ej and S1 1-st abrupt change must occur after H.
Therefore, considering the first case, when m = Si + 1, we have
Σ
n HI
EE 9]
which implies (H) S RB me.
From the above lemma, we set m S1 and analyze R to get a bound for (H) in the following lemma.
Lemma A.25. Under E and policy æ1 (ot), we have
El = Ô (B[S) max(1/(6))), 1/61H)
Proof. We can show this theorem by following the proof steps in Lemma A.8
Now we analyze (HH) in the following lemma. We denote by Vи a cumulative amount of rotting rates in the first block.
Lemma A.26. Under E₁ and policy we huve
= E [mxx($1/88
Σ prot))
E R 1
(H)
Proof. We can show this theorem by following the proof steps in Lemma A.9
From Lemmas A.24
A.25
A.26
we have
(1)) = Ô ( E max max((((())))1111))
51
P((s) ) (43)
([IH((H) =E E
(()) ER (1))
From (T( = RS + RH),H, (42) and 43
we have
S₁ P((s)
(()) (6t) m9 = y
Hot + E S max m +
The above regret for the first block. Therefore, by summing regrets over [T/H] HH] number of blocks, have shown that
Sr B(pol)
R (T) Ö + (T/H + Sr) max 1185) +
(44)
Upper bounding E(R (T)). By following the proof steps Theorem A.15 we have
E (T) = Ö O(VHT)
(45)
36

---

Finally, from
41
and 45 with the fact that Σx= Blp((s)] S Vr, H = T1/2 and 8t
(SmaX((ST (T) 1/(++1] 1/ H/ (ST/T) //, 1 1/H122)) we have
Sr
= T8 + (T/H + Sr) max max( + HT +
El P(sss)
Sr
T8t max (T/H, 0
ma ST) max ( (1((0) + HT +
Elputil
Sr E Elpuce)
= Ö 2T + v HT
= Ö [Sax ///1///+1))0//0 10/10(11))))000 (-00(11)0)))))) + (02041)/2222
/STT+ TT/44 Vr²)
which concludes the proof.
A.8 Proof of Theorem Regret Lower Bound for Slowly Rotting Rewards
We first consider the case when VT = (T)) Recall that (a) = 1-11-u (a). Then for any randomly
sampled E A. we have Bluu (a)] 2 ylP (a) 2 y) = yP (a) < <1-y) for y E [0, 1j. Then
with y = 1/2, we have Elui(a) 2 (1/2)P(A1 (a) < (1/2)) = (1) from constant / > 0 and (I). Then with E[pt (a)] S 1, have (a)
@(1) We then think of policy x' that randomly samples a new arm and pulls it once every round. Since [[)i(a)] = e1)) for any randomly sampled a, we have EE (T') = ((T). Next, we think of any policy x" except x'. Then any policy x" must pull an arm a least twice. Let 6' and t" be the rounds when the policy pulls arm a. If we consider Pe = Vi then such policy has (2(Vr) regret bound. Since Vy O(T), any algorithm has S2(T)) in the worst case. Therefore we can conclude that any algorithm including ''' has regret bound of (TT) in the worst case, which concludes the proof for Vr = (TT).
Now think of the case where VT- T()). For the lower bound, adopt the proof methodology of Theorem in Kim et al. [13 by making necessary adjustments to accommodate Vr and B. We note that since higher 3 implies reduced chance of sampling near-optimal arm, the criteria for defining the mean rewards of near-optimal arms becomes less stringent for higher 3, which does not appear in the previous work. We first categorize arms 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 y. which will be specified, and a constant c. Then the value of 1 - represents a threshold value for identifying good arms, while 1 - serves as the threshold for identifying bad arms. We refer to arms a satisfying #1 (a) I 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 ã ā2..... Given policy without loss of generality, we can assume that π selects arms according to the order of ā1 02:
For the rotting rates, we define @ = / - 1). Then we consider P: for all f E [T - 1] so that Et Pr VT.
Case of V/= = O(L/TV((11)) When 1/- = 0 (01/T1/((+1)) ((++1),, the lower bound of order T チサ for the stationary case, from Theorem in Wang et al. [24, is tight enough for the non-stationary case. From Theorem 3 in Wang et al. [24]. we have
B[R (f))
(46)
We 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 the proofs providing tight regret bound for the near-stationary case. For the sake of completeness, we provide the proof of the theorem in the following. Let Kj denote the number of bad arms a that satisfy Pi (a) S - e before sampling the first good arm, which satisfies /4 (a) > y in the sequence of arms 01, aū..... Let z be the initial mean reward of the best arm among the sampled arms by æ over time horizon T. Then for some O, we have
(T) = (T)) (T) >1 1
2 Ty Ki 1-7)
2 Tyl(F g1-7) 7, K1 11200 k).
(47)
37

---

By taking expectations on the both sides in 47 and setting = Ty/c, we have
E| (T)) 2 (T - - 7) + kc > 1 - - IP < x)) = cxPP(Ki 2 k).
We observe that K1 follows geometric distribution with success probability P(ui (a) g)/p(u/ (a) & (1 -1-c. c, - 7
C1 /11+ - C3c²) for some constants C2 C3 > 0
from ① in which the success probability is the probability of sampling a good arm given that the arm is either good or bad arm. Here we set constant 0 < 1 satisfying 1 Czc2 > 0. Then by
setting 7 = 1/T with x = T /c. for some constant C' > 0 we have
BI 2 ex - -) m = 2 (1
C39
-R(TTE)
where the last equality is obtained from log 2 1 - 1/2 for all x > O.
Case of VT = w(1 (1) and VT = (T):: When VT = w(1 (o(1/T/((++))) however, the lower
bound of the stationary case is not tight enough. Here we provide the proof for the lower bound of for the case of Vir = (1/TT//(++)), Let Km denote the number of "bad" arms a that satisfy Yn (a) S 1 - c before sampling m-th "good" arm, which satisfies (I(a) > 1 - % in the sequence of arms á1, 02 .... Let Nr be the number of sampled good arms a such that
V (2/(0022)(((+))(1444
(a) > 1 y until T.
We can decompose Rd (T) into two parts as follows:
R (T) 18 (T) <m) + (T)I((N m).
(48)
(0 and y = (Vr 1/0+42) with V4 V1=00 o(T). For the first term in (48) (T) m), consider the fact that the minimal regret is obtained from the situation where there are m - 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 below the threshold
We set m =
7 (step 1) and then samples the best arm at each time for the remaining time steps (step 2). The number of times each arm needs be pulled for the best m arms until their mean reward falls below 1 - is bounded from above by 7/P + = ((T 1)/Vr) + 1. Therefore, the regret from step 2 is
R Q((T my(TTVa (TTTTT/V))))) )) y v in which the optimal policy pulls arms which mean rewards are below 1 for the remaining time after step 1. Therefore, we have
RdT (NN m) = ((RL(NT < m)) V
1/8+2) (1/0022)) 1(NT < <m)).
(49)
Rd (T) 2 m). we use the minimum c. When Nr 2 m and Kn 2 k, the policy samples at least number of distinct arms satisfying (1(a) S 1 until T. Therefore, we have
For getting a lower bound of the second term in 48 number of sampled arms a that satisfy n1 (1( <
Rd (T) 2 m) 2 cx L (Nr 2 m, Km 2 k)..
(50)
We have & O()*) from I with constant G 0. By setting m/7 m vm/7, with
Vr = o(T) and constant / > 0, we have
((76441/6-2211/00000
(51)
Then from 49
500
and 51
we have
E|R" (T) = ((T =
(Nr < m) + 210+1) 2 m, Km 2 x))
S 1(+22) P(K n)).
(52)
Next we provide a lower bound for P(Km 2 k). Observe that Kn, follows a negative binomial distribution with successes and the success probability (())(a) 1 / & (1 (1-c,1, 7)) = 7, in which the success probability is the probability of sampling a good arm given that the arm is either good bad arm. In the following lemma, we provide concentration inequality for Km.
Lemma A.27. For any 1/2 + 7/m < < 1,
P(Km am(7/ m) z 1 -xp(-U/3]111aa{(mmm (am) - -)))
38

---

Proof. Let X; for > 0 be i..d. Bernoulli random variables with success probability 7. From Section
2 in Brown we have
am +
P
Km - am
m
= P
Σ
X;
N m
(53)
i=1
From 53
and Lemma A.29. for any 1/2 + 5/m < a <
we have
1
1
IP
Km I am
m
Km 1
am
m
7
7
am !
P
Σ
X; 2 m
i=1
(1 - 1/a)²
1
exp
am 7 7)
(1 - 1/a)2 2
exp
(am - 7)
in which the first inequality comes from Lemma A.29 which concludes the proof.
From Lemma A.27 with a = 1 - 1/ / m and large enough T, we have
2
P(Km 2 K3) 1211-00 exp
m vm
7)
m
2 1 exp
mm- vm)
vm
Vm
1 exp
/mm-> 1m-11
2 exp (-/6)).
(54)
Therefore, from 52 and 54 we have
EI (T)) (2 (0+1((1111/+))) vz (1((22))
(55)
Finally, from 46 and
55
we conclude that for any policy म, we have
R (T) =
max (T(*+))(++))) yz /21+)2 r
A.9
Proof of Theorem 4.2 Regret Lower Bound for Abruptly Rotting Rewards
First, we deal with the case when Sf or ST = O(T). When ST 1 (implying Vr 0). from the definition, the problem becomes stationary without rotting instances, which implics B|Ae (T)] - R(VT) from Theorem 3 in Wang et al. (24. When ST = ( we consider that rotting occurs for the first Sy rounds with P 1 for all t [Sp 1]. Then it is always beneficial to pull new arms every round until Sr - 1 rounds because the mean rewards of rotted arms are below 0 and those of non-rotted arms lie in [0. This means that any ideal policy samples a new arm and pulls it every round until Sr - 1. Then for any randomly sampled a E A, we have Elua Elur(a) 2 yP(p (a) > y) yPP(A
11-9) y) for y 1). Then with y 1/2, we have [a)] 2 (1/2)P(A1(a) < (1/2)) = -0(1) from constant 3 > 0 and []. Then with [o)) S 1, we have E((((a) = ((1). Since (()] ((1) for any randomly sampled A. any ideal policy has (T)) 2 Er (a)) = ((Sr) = Q(T), which concludes the proof for Sr = OTT).
39

---

Now we consider the case of Sr o(T) and ST 2 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 new arm and pulls it once every round. Then for any randomly sampled E A, we have [l)) (1). Then from constant 3 > O. E = Q(T). Then there always exists pt satisfying - Pt = T, which implies ((((((T) = 2(T) = ((V)).
Now we think of any nontrivial algorithm which must pull an arm at least twice. Let L' and t" be the rounds when the policy pulls arm a (t' < <t"). If we consider py > and Pt = 0 for E [T - 11/{t'} in which P = Ei= P: and 1+ 1+d++ E P. #0) S Sr, then such policy has R (T") -E==
T-1 Pe) regret bound because, at time t". it pulls the arm a rotted by pv. Therefore. for any policy ग, there always exist rotting rate adversary satisfying the following expected regret
bound of
[(RT(T)) = (VV))
(56)
Next, for the regret bound with respect to Sr, we follow the proof steps in Theorem 4.1 However, the regret bound of Sr 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 follows. Consider 0 < Y specified, and a constant c. Then the value of - y represents a threshold value for identifying good arms, while 1
< 1 for % which will be
serves as the threshold for identifying bad arms. We refer to arms a satisfying (a S 1 - c as 'bad' arms and arms a satisfying μn (a) > 1 --9 7 as "good' arms. We also consider sequence of arms in A denoted by á1, a2,.... .... Given policy æ, without loss of generality, we can assume that π selects arms according to the order of ã1, 02
Let Km denote the number of bad arms that satisfy μn (a) < 1 before sampling m-th good arm, which satisfies μn (a) > 1 - 7 in the sequence of arms ā₁, ....... Let Nr be the number of sampled good arms a such that μ (a) > 1 7 until T.
We can decompose Rd (T) into two parts as follows:
R = RT (T) m) + R 2 m).
(57)
We set = Sy and 7 (Sr (Sr/T) with o(T). For getting a lower bound for the first term in (57). RD ( < m), we consider the fact that the minimal regret is obtained from the situation where there must sample the best m 1 arms until their mean rewards become equal to or below the threshold value of - 7 (step 1) and then samples the best arm 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 the value of y. This implies that the required number of
arms whose mean rewards are 1. In such case, the optimal policy
rounds for step 1 is m -0--, The regret from step 2 is R = (( - m 1)r) = 2(S) [[(s)/(++)) (1)(+11) in which the optimal policy pulls arms which mean rewards are below or equal - y for the remaining time after step 1. Therefore, we have
R (T) < m) Q(R1(N m)) = (25) (oss1/00+1))/) (010)10000)))111-0110011010 1(NT < m)).
(58)
For getting the above, we note that there always exists Pe 's satisfying ΣL P: (07m)=
which implies ΣE P. T. Such p. 's can be considered for the below. For getting a lower bound
of the second term in (7). Rd (T)1(N; 2 m), we use the minimum number of sampled arms a that satisfy in < 1 C. When Nr 2 m and K,, 2 k. the policy samples at least x number of distinct arms satisfying Pr (a) < 1 - until T. Therefore, we have
Rd (T) 2 m) 2 cx1 2 m, Km 2 n)).
(59)
We set 7 = PP((((a)) > - 1)11) (a) $ (1 c, 1 - >)) Then we have 7 = ( from [[] with constant 3 > 0. By setting x = m/7 - m (7/ m + 3). with Sy = o(T) and constant, / > 0,
we have
= e( ( (8+1)
(60)
40

---

Then from 58
(59
and
60
we have
E (T)
S2(ST (B+ P m) + ST
51/( (0/00+10000010ppp(pp 2 m, Km 2 k))
2 STST (2(Ss/(8+1)) (8+ (8+1))1 1 0/101100+11000 P(Km 2 k)).
(61)
Next we provide lower bound for Pm x). Observe that Km follows a negative binomial distribution with m successes and the success probability (())(a) > 1 - -7)/P(u1(a) & -1- 1- y)) = 7, which the success probability the probability of sampling good arm given that the arm is either good or bad arm. We recall Lemma A.27 for concentration inequality for Km, in the following.
Lemma A.28. For any 1/2 < 1,
P(Km 2 amm1m1)) - m) 2 1 exp( - 1/a)) 7)).
From Lemma A.28 with a = 1 m + and large enough T, we have
P(Km 2 x) 2 exp
(m
7)
Vm +
Vm + -
2 exp
mm
Vm + 3
Vm
m
v m +3
- exp
6 m + Vm + -
2 exp(-1/24).
(62)
where the last inequality comes from m/ mm/mm+3) = (ST) 2 1/4 and vmn +3/ 333lvm/m +3.
1) Z 1. Therefore, from 66 and (62). we have
E (T) = 2(S) (84))
(63)
Overall from 56 and 63 for any n. there exist pt's such that E|R" (T)]
=
((max{[ ( (1/(011))11)))))111111 (1t/1//11)91111)))) Vr
A.10 Additional Experiments
1e6
1e6
3.0
UCB-TP
UCB-TP
Algorithm 2
Algorithm
2.0
Algorithm
Algorithm
E[RN(T))
1.5
2
1.0
1
0.5
0.0
0
1
2
5
3
4
1e6
1e6
(a) 8 = 0.5
(b)
Figure 5: Regret Performance comparison between our algorithms and benchmarks.
We compare the performance of our Algorithms with benchmarks for smaller or larger 3. In Figure (a,b), we can observe that our algorithms outperform the benchmarks for 3 0.5 and 2.
A.11 Lemmas for Concentration Inequalities
Lemma A.29 (Theorem 6.2.35 in Tsun 22 ). Let XI...., Xn be identical independent Bernoulli
random variables. Then, for 0 < 1, we have
n
12
Xi]
(1+ +
Σ X;
S exp
41

---

Lemma A.30 (Corollary 1.7 in Rigollet and Hütter (8). Let X1.... Xn be independent random variables with --sub-Gaussiee distributions. Then, for any a (aI...... an) R and have
IP
E aix;>
S exp
and P Σ aixx < -1) exp
20 |||
220
42

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Through the abstract and introduction, we explain our setting with providing motivation examples and summarize our contributions.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification: In the limitations section (Section A.1 we discuss an avenue for future work regarding regret lower bounds.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sell-speciiiitiinn asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
43

---

Answer: [Yes]
Justification: We provide assumptions in Section and, for the case of unknown parameters, in Appendix A.66 In addition, proof sketches of some of our main theorems (Theorems 3.1 3.3) are included the main text, with complete proof' provided for all theorems in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: In Section synthetic experiments.
we provide all the information necessary for conducting the
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
44

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
There is link to code in Section
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. ec/
gublic/guidess httae//guiiee//eeebbiiiaaeee
for more details.
While we encourage the release of code and data, we understand that this might be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
//nips ccpps.cc//pp wttppppllllllppie https///oooooooossssoooooooeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We use synthetic datasets and provide details how to generate them in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In our experimental results in Section 5 include error bars of standard deviation along with expectation values.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
45

---

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 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 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
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 compute required for each of the individual experimental runs as well 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 into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http://////eea....ccoo/////alaaa httppppllittthhccccceceeeeee.eee
Answer: [Yes]
Justification:
We have reviewed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- cration due to laws or regulations their jurisdiction).
10. 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.
46

---

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 direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that 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 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 attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
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 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 challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g.. code, data, models), used in the paper, properly credited and the license and terms of use explicitly mentioned and properly respected?
Question:
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 dataset.
The authors should state which version of the asset used and, possible, include 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.
47

---

If assets are released, the license, copyright information, and terms of use in the thcode. has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssi
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: This paper does involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
48

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
49


Reviews:
[{"review_id": "DzfuYvTcvY", "reviewer": "Reviewer_g8GP", "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.", "questions": "Please refer to strengths and weaknesses above.", "limitations": "No broader impact concerns.", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The infinite-armed bandit problem is well motivated and the problem and results are clearly presented.\n* There are matching upper and lower bounds on regret, at least for the better-understood $\\beta \\geq 1$ setting.", "weaknesses": "* 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.\n*  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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your time to review our paper and comments. Below, we address each comment.\n\n**The definition of $V_T$, $S_T$\n are a bit unclear and may not be fully rigorous. They are bounds on the total amount and count of rotting, but the rotting \n depends on the chosen arm \n and is thus random**:\n\n\n We appreciate your detailed comments. However, we argue that the definitions of $V_T$ and $S_T$ are rigorous in our context, as they serve as *constraints* on the rotting adversary. These quantities are not random outcomes based on the adversary's behavior but rather imposed conditions. To clarify this, we restate our Assumption 2.1 concerning the adaptive adversary as it is.\n \n---\n\n **Assumption 2.1.** At each time $t\\in[T]$, the value of rotting rate $\\rho_t>0$ is arbitrarily determined immediately after the agent pulls $a_t$, subject to the constraint of either slow rotting for a given $V_T$ or abrupt rotting for a given $S_T$.\n\n---\n\nAccording to this assumption, we consider $V_T$ and $S_T$ to be given a priori to the adversary, and the adversary determines $\\rho_t$ subject to these constraints. $V_T$ and $S_T$ are deterministic quantities that act as *constraints*, which are determined before the game begins. This is why we refer to the two scenarios as the slow rotting constraint ($V_T$) and the abrupt rotting constraint ($S_T$). In our setting, if $V_T$ or $S_T$ is large, then, as we have shown in our regret lower bounds, any algorithm naturally cannot avoid a large regret bound in the worst case. \n\n\n**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:**\n\n\n\n\nIn the case when the parameters are unknown, there is an additional regret for Algorithm 2, which stems from learning the threshold parameter. However, if $V_T$ and $S_T$ are large enough (e.g. $V_T\\ge T^{1/4}$, $S_T\\ge \\sqrt{T}$ for $\\beta=1$), then the regret bound in Theorem A.15 for Algorithm 2 matches that in Corollary 3.5 for Algorithm 1 (for known parameters). It is an open problem to achieve tight regret bounds for entire ranges of $V_T$ and $S_T$. \n\n\n Now we discuss the further assumptions. \nFor the unknown parameter case, we consider  Assumptions A.10 and A.12 rather than Assumptions 2.1 and 2.4 (for the known parameter case). In Assumption A.10, we still consider an *adaptive adversary* for the rotting rates, such that $0 \\le \\rho_t \\le \\varrho_t$ for given $\\varrho_t$ to the adversary, where $\\sum_t \\varrho_t \\le V_T$ and $1 + \\sum_t 1(\\varrho_t \\neq 0) \\le S_T$. Here $\\varrho_t$'s are assumed to be determined before the algorithm is run.\nAs we describe in Remark A.11, this assumption is more general than that in [13], where $\\varrho_t = \\rho$ with a maximum rotting rate $\\rho$ for all $t$. In the special case where $\\rho_t = \\varrho_t$, the assumption represents an oblivious adversary.\n\n\nIn Assumption A.12, we consider $\\sum\\_{t \\in \\mathcal{T}\\_i} \\rho\\_t \\le H$ for all $i \\in [ \\lceil T/H \\rceil]$, where $\\mathcal{T}\\_i=[(i-1)H+1,iH]$ representing the $i$-th block of times of length $H$ within horizon time $T$. As we mention in Remark A.13, this assumption is satisfied when mean rewards are constrained by $0 \\le \\mu_t(a_t) \\le 1$ for all $t$ because $0\\le\\rho_t\\le1$. The positive mean reward constraint is frequently encountered in real-world applications such as click rates in recommendation systems. We also note that, as mentioned in Remark A.14, the assumption is still more general than the one with a maximum rotting rate constraint of $\\rho_t \\le \\rho = o(1)$ in [13]. This is because, in our setting, each $\\rho_t$ is not necessarily bounded by $o(1)$ but $\\sum_{t \\in \\mathcal{T}_i} \\rho_t \\le H$.\n\n\n Lastly, we emphasize that our study is the first work to consider $V_T$, $S_T$, and $\\beta$ in the context of rotting bandits with infinite arms, which is fundamentally different from finite-armed bandits due to the necessity of exploring new arms (details are described in lines 58–70). Notably, when the parameters are known, we achieve tight results using a novel approach and provide regret lower bounds.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mb5JFU2Afu", "reviewer": "Reviewer_ALsC", "summary": "Authors investigated an adaptive approach for the rotting bandits problem under the infinitely arms assumption.", "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.\n\nSimilarly, I was wondering how good these results would be for the infinitely many afrmed bandit with no rotting.", "limitations": "No clear limitations have been found.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Authors introduced a new ucb like policy for the mentioned problem, additionally a lower bound analysis has been carried on.", "weaknesses": "No clear weaknesses", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your feedback and positive evaluation of our work. Below, we address each comment.\n\n**I wonder how the regret bound behaves with respect to the effective rotting instead of the $V_T$ or $S_T$:**\n\nIn this problem, as mentioned in Assumption 2.1, we consider an adaptive adversary who determines $\\rho_t$ arbitrarily, subject to the constraint $\\sum_t \\rho_t \\le V_T$ or $1 + \\sum_t 1(\\rho_t \\neq 0) \\le S_T$ for given $V_T$ or $S_T$.  As a side remark, these constraints are more general than the stricter conditions $\\sum_t \\rho_t = V_T$ or $1 + \\sum_t 1(\\rho_t \\neq 0) = S_T$. Our regret analysis, for both upper and lower bounds, addresses the *worst-case* scenario concerning the rotting rates under the general constraint of $V_T$ or $S_T$. Hence, our regret bounds are expressed in terms of $V_T$ or $S_T$.  We also note that standard nonstationary bandits have been studied under a similar concept of a nonstationary budget upper bounded by $V_T$ [7,19].\n\n \nWe can consider a scenario where an adversary determines $\\rho_t$ under the stricter constraints of $\\sum_t \\rho_t = V_T$ or $1 + \\sum_t 1(\\rho_t \\neq 0) = S_T$. Our (upper and lower) regret bounds apply with these values of $V_T$ and $S_T$, respectively corresponding to the effective rotting amounts of $\\sum_t\\rho_t$ and $1 + \\sum_t 1(\\rho_t \\neq 0)$. When there is no rotting such that $V_T=0$ and $S_T=1$, then our bounds are the same as the bounds for the stationary case (e.g. $\\sqrt{T}$ for $\\beta=1$ as in [24, 5]). Furthermore, if $V_T$ and $S_T$ are unknown, Algorithm 2 (in Appendix A.6) can achieve regret bounds that depend on the values of $V_T$ and $S_T$ (Theorem A.15).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0zObycRlzD", "reviewer": "Reviewer_jk3J", "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.\n\nThis 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.\n\nAn 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.\n\nThe 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.", "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?\n\n2. What would the experimental results look like for $\\beta \\neq 1$?\n\n3. 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$?\n\n4. Can you put the WUCB definition in an equation display and reference its equation number in the statement of Algorithm 1?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper studies an interesting extension of prior work to allow for more general rotting constraints. This is likely to be of interest to the multi-armed bandit community and both the methodological and theoretical work present some novelty and careful algorithmic design that merit publication.\n\nI was pleased to see a treatment of the case where key problem parameters were not known, and that largely comparable bounds were achievable in this setting.\n\nGenerally, the paper is written well and concisely, with useful clarifications made around the most important details and a clear relationship to the most closely related prior work.", "weaknesses": "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.\n\n1. 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.\n\n2. 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$.\n\n3. 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your feedback and positive evaluation of our work. Below, we address each comment.\n\n**All of the theoretical results are ultimately order results only, without identification of the constants in the appendices. It would be helpful if the bounds could thus be realised for the cases considered in the experiments and compared to the actual regret of Algorithms 1 and 2:**\n\nIn our work, we provide regret bounds in terms of the horizon time $T$ and the rotting constraint parameters $V_T$ and $S_T$ (to the power of $\\beta$ terms),  which hold up to constant factors whose values are not asserted in the statements of our theorems. \n\nBased on your feedback, we will include more details regarding the values of these constant factors in the final version of our paper. For instance, in Lemma A.5, instead of using $m^{\\mathcal{G}} = C_3$ for some sufficiently large constant $C_3 > 0$, we can specify $m^\\mathcal{G}=3$ with $V_T\\le  \\max\\\\{1/T^{1/(\\beta+1)},1/\\sqrt{T}\\\\}$ and $\\delta=\\max\\\\{1/T^{1/(\\beta+1)},1/\\sqrt{T}\\\\}$. Then, we have $m^{\\mathcal{G}}\\min\\\\{\\delta/2,V_T\\\\}=3\\min\\\\{\\delta/2,V_T\\\\}>V_T$, which can conclude the lemma. \n\nWe will also provide additional experimental results related to this. For now, we present an experiment in Figure 1 in the attached pdf that compares the performance of our algorithms with theoretical regret upper bounds with a constant of 1. We observe that the performance of our algorithms (blue and green solid lines) is better than the theoretical regret upper bounds (light blue and light green dashed lines), respectively, because the theoretical bounds represent worst-case regret regarding rotting rates, while the experiment is conducted under a specific instance of rotting rates. \n\nIt is noteworthy that providing regret bounds that hold up to constant factors is an important first step to establishing fundamental bounds for the underlying learning problem. Note that previous work on stationary infinitely-armed bandits (e.g. [24, 10]) also focused on providing regret bounds up to constant factors, whose values are not identified explicitly. \n\n**What would the experimental results look like for $\\beta\\neq 1$:**\n\nWe appreciate your suggestion. We have included additional experiments in which we varied the value of $\\beta$ in Figure 2 of the attached pdf. In Figure 2, our algorithms outperform other benchmarks for various $\\beta$. We will incorporate this into our final version.\n\n\n**The motivation in terms of real applications is not especially strong:**\n\nWe appreciate your comments and suggestions. We highlight that (rested) rotting rewards in bandits have been studied [16, 20, 21, 13], motivated by real-world applications such as recommendations and clinical trials. For instance, in recommender systems, the click rate for each item may diminish due to user boredom with repeated exposure to the same content. Similarly, in clinical trials, the efficacy of a medication can decline due to drug tolerance induced by repeated administration. However, the previous work regarding rotting bandits, except for [13], focused on MAB with finite arms, which have limitations when the number of items is large, as in recommender systems. In contrast, we consider the case with infinitely many arms without contextual information.\n\nWe believe our algorithm, as you mentioned, provides insights into handling rotting cases in real-world scenarios. Specifically, our adaptive SW-UCB and threshold approach offers valuable insights for designing bandit algorithms regarding when to explore new arms and how to estimate rotting mean rewards and determine the status (good or bad) of each arm when rotting occurs. Furthermore, our study on optimizing the threshold parameter provides practical guidance for setting threshold values in real-world applications. \n\n**Is Prop 2.3 missing some kind of additional condition, or clarity over what is meant by worst-case in line 453?:**\n\nOur regret analysis focuses on the *worst-case* regret concerning rotting rates. As outlined in Assumption 2.1, we consider an adaptive adversary that determines the rotting rate $\\rho_t$ arbitrarily immediately after the agent pulls an action $a_t$ at each time step $t$. In Proposition 2.3, we show that there always exists a rotting adversary (or instances of rotting rates over $T$) with $\\sum_t\\rho_t>T$ such that it incurs at least $T$ regret for any algorithm, implying an $\\Omega(T)$ regret lower bound. This does *not* imply that any rotting adversary (or any rotting instances) occur $T$ regret. This worst-case lower bound can be demonstrated by providing *a* rotting adversary (or rotting rate instances) where any algorithm will incur at least $T$ regret. Additionally, we show that this lower bound can be achieved by a simple algorithm that pulls a new arm every round. Therefore, Proposition 2.3, which is regarding the worst case, does not contradict the example you mentioned. We appreciate your helpful comments to improve clarification. We will include the explanation to clarify Proposition 2.3 in our final version.\n\n **Can you put the WUCB definition in an equation display and reference its equation number in the statement of Algorithm 1?:**\n \nWe appreciate your helpful comments for improving the clarity of our paper. We will display the WUCB definition in an equation and reference its number in Algorithm 1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "rbKzNL1O7f", "reviewer": "Reviewer_WSKL", "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.", "questions": "The following questions are raised simply for discussion. There is no need to address them in the paper.\n\n- 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.\n\n- 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?\n\n[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": "The authors adequately addressed the limitations.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- Extending the multi-armed bandit problem to infinitely many arms with rotting mean rewards is feasible in many real-world applications. Solid theoretical analyses and empirical results are presented to justify the proposed solution.\n\n- The paper in general is well-written and easy to follow.  Since I have not checked the supplementary material step by step, I can not guarantee the correctness of the proofs, but the theoretical results make sense to me.", "weaknesses": "- 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.\n\n[1] Jung-hun Kim, Milan Vojnovic, and Se-Young Yun. Rotting infinitely many-armed bandits. ICML, pages 11229–11254. PMLR, 2022.\n\n- When the environment parameters $\\beta, V_T,$ and $S_T$ are unknown, a significant amount of additional regret is generated with proposed Algorithm 2. \n\n- 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).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate your feedback and positive evaluation. Below, we address each comment.\n\n**The paper is an extension of [1]. When $\\beta\\in(0,1)$, the proposed algorithm can not be proved optimal:**\n\nFirst of all, we highlight that we consider rotting constraints with $V_T$ or $S_T$ and initial mean rewards with $\\beta>0$, both of which are not considered in [1]. As mentioned in Remark 2.2, the rotting constraint with $V_T$ ($\\sum_t \\rho_t \\le V_T$) is more general than the maximum rotting constraint in [1]. Furthermore, the constraint with $S_T$ ($1+\\sum_t 1(\\rho_t \\neq 0) \\le S_T$) is fundamentally different from that in [1] because $S_T$ considers the total number of rotting instances rather than the magnitude of the rotting rate.\n\nWhile, in our work, we have demonstrated optimality only for $\\beta \\ge 1$, we believe that the suboptimality for $\\beta \\in (0,1)$ arises from the looseness of our lower bounds rather than the regret upper bounds. The gap between lower and upper bounds comes from that when $\\beta(<1)$ decreases, the regret lower bounds (in Theorems 4.1, 4.2) also decrease while the upper bounds (in Theorems 3.1, 3.3) remain the same. As discussed in Appendix A.1, the phenomenon where the regret upper bound remains the same as $\\beta$ decreases has also been observed in many infinitely many armed bandits [5, 24, 10]. This is because, as mentioned in [10], although there are likely many good arms when $\\beta$ is small, it is not possible to avoid a certain amount of regret from estimating mean rewards. Therefore, we believe that our regret upper bounds are near-optimal across the entire range of $\\beta$, and achieving tighter lower bounds for $\\beta < 1$, considering such unavoidable regret, is left for future research. Notably, the optimality proven only for $\\beta \\ge 1$ has also been observed in stationary infinitely many armed bandits [5, 24].\n\n**When $\\beta,V_T,S_T$ are unknown, additional regret is generated with Algorithm 2:**\n\nWhile our algorithm (Algorithm 2) incurs an additional regret to estimate the threshold parameter when parameters are unknown, if $V_T$, $S_T$ are large enough (e.g. $V_T\\ge T^{1/4}$, $S_T\\ge \\sqrt{T}$ for $\\beta=1$), then the regret bound of Algorithm 2 matches that of Algorithm 1 in Corollary 3.5 (for known parameters). This is because the additional term becomes negligible compared to the main term involving $V_T$ and $S_T$. We leave it as future work to obtain a tighter regret bound for the entire range of $V_T$ and $S_T$ when the parameters are unknown.\n\n**Extensive experiment study by varying the rotting rate with randomness:**\n\n The main purpose of our experiments is to validate some claims of our theoretical analysis such as Remark 3.2. Based on your comments, we have conducted an additional experiment for random rotting rates in Figure 3 in the attached pdf. Following the rotting rates used in the experiment section in our paper, which rotting rates are convenient to compare the theoretical results of algorithms, we introduced random rotting rate  $\\rho_t$ uniformly sampled from $[0,3/(t\\log(T))]$ for each time $t$. In Figure 3, our algorithms outperform other benchmarks. We will include further experiments regarding rotting rates in our final version.\n\n **The rotting budget  $V_T$ and $S_T$ are defined for all selected arms. How about treating the rotting process for each arm independently with the budget of each arm, $f(N)$, for selected $N$ times:**\n\nIn our setting, the constraints on $V_T$ and $S_T$ quantify the rotting rate of all selected arms for all $t$, as you mentioned. We note that similar quantities related to overall nonstationarity across all arms have also been considered in standard non-stationary bandits [7, 19, 4]. These quantities help quantify the overall difficulty of the problem in our regret analysis. As you suggested, addressing individual budgets for each arm would be an interesting research question.\n\nWe believe that our algorithm and analysis provide helpful insights for solving such a problem. This is because the core of our algorithm involves determining whether a selected arm is good or bad based on a threshold parameter tuned by the value of the constraint budget. If we know $f(N)$ for each arm, we can use our method to determine the status of the arm using a threshold adjusted by the budget information.\n\n **Addressing the unknown parameters without incurring large additional regret. Can the methodology in [2] be applied in this paper? Can $\\beta$ be estimated?**\n\nHere, we provide our thoughts regarding the applicability of [2]. In our problem, it is required to determine whether a selected arm is bad or not. In our algorithm, using a threshold, we can determine this with some confidence. Although we assume that nonstationarity can be detected using techniques from [2], it may not be clear how to determine the status of an arm whose initial mean reward is bad (small). In our setting, which includes infinitely many arms and many near-optimal ones, an absolute threshold (rather than a relative value between arms) may be required, as used in our algorithm to determine the status of arms. Without knowledge of parameters of  $V_T$, $S_T$, and $\\beta$, how to determine such a threshold combined with the detection method is an unresolved problem.\n\nAnother issue is that our setting allows for potentially large negative rewards from rotting with sub-Gaussian noise, whereas [2] considers rewards within $[0,1]$. This difference makes it challenging to apply the concentration inequality of Lemma 12 in [2] to our problem. As you suggested, applying the detection-based algorithm [2] to our setting while addressing those issues would be an interesting direction for future work.\n\nRegarding the unknown $\\beta$, estimating $\\beta$ directly was considered in Algorithm 3 in [10]. However, it requires additional information on a (non-zero) lower bound of $\\beta$, and the performance depends on the tightness of this lower bound.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We appreciate you taking the time to review our paper. We are encouraged by the feedback indicating that our problem is well motivated by many real-world applications, solid theoretical analyses and empirical results are presented, and the paper is written well and concisely.  We have attached a pdf with additional experimental results to address the reviewers' comments. In the following, we provide detailed responses to each comment from the reviewers.

Meta-review: 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.
Decision: Accept (poster)