Tracking Most Significant Shifts in Infinite-Armed Bandits
Authors: Joe Suk
Jung-hun Kim
Venue: ICML 2025 poster (2025)
Keywords: non-stationary
infinite-armed bandits
bandits
adaptive
parameter-free
Primary area: theory->online_learning_and_bandits
TL;DR: First optimal and adaptive regret bounds for non-stationary infinite-armed bandits

Abstract: We study an infinite-armed bandit problem where actions' mean rewards are initially sampled from a _reservoir distribution_. Most prior works in this setting focused on stationary rewards (Berry et al., 1997; Wang et al., 2008; Bonald and Proutiere, 2013; Carpentier and Valko, 2015) with the more challenging adversarial/non-stationary variant only recently studied in the context of rotting/decreasing rewards (Kim et al., 2022; 2024). Furthermore, optimal regret upper bounds were only achieved using parameter knowledge of non-stationarity and only known for certain regimes of regularity of the reservoir. This work shows the first parameter-free optimal regret bounds while also relaxing these distributional assumptions. We also study a natural notion of _significant shift_ for this problem inspired by recent developments in finite-armed MAB (Suk & Kpotufe, 2022). We show that tighter regret bounds in terms of significant shifts can be adaptively attained. Our enhanced rates only depend on the rotting non-stationarity and thus exhibit an interesting phenomenon for this problem where rising non-stationarity does not factor into the difficulty of non-stationarity.

Tracking Most Significant Shifts in Infinite-Armed Bandits
Joe Suk Jung-hun Kim?
Abstract
K. However, in practice, the number of arms can be pro- hibitively large as is the case in recommendation engines adaptive drug design motivating the so-called many-armed, or infinite -ariiiee-amdd,..... model.
We study an infinite-armed bandit problem where actions' mean rewards are initially sampled from a reservoir distribution. Most prior works in this setting focused on stationary rewards (Berry et al., 1997; Wang et al., 2008; Bonald and Proutiere, 2013; Carpentier and Valko, 2015) with the more challenging udversarial/non -tatstiia// variant only recently studied in the context of rot- ting/decreasing rewards (Kim et al., 2022; 2024). Furthermore, optimal regret upper bounds were only achieved using parameter knowledge of non- stationarity and only known for certain regimes of regularity of the reservoir. This work shows the first parameter-free optimal regret bounds while also relaxing these distributional assump- tions. We also study a natural notion of significant shift for this problem inspired by recent develop- ments in finite-armed MAB (Suk and Kpotufe, 2022). We show that tighter regret bounds in terms of significant shifts can be adaptively at- tained. Our enhanced rates only depend on the rotting non-stationarity and thus exhibit an inter- esting phenomenon for this problem where rising non-stationarity does not factor into the difficulty of non-stationarity.
At the same time, another practical reality is that of changing reward distributions or non-stationarity. While there has been a surge of works here (Kocsis and Szepesvári, 2006; Yu and Mannor, 2009; Garivier and Moulines, 2011; I; Mellor and Shapiro, 2013; Liu et al., 2018; Auer et al., 2019; Chen et al., 2019; Cao et al., 2019; Manegueu et al., 2021; Wei and Luo, 2021; Suk and Kpotufe, 2022; Jia et al., 2023; Abbasi- Yadkori et al., 2023; Suk, 2024), most works here again focus on the finite-armed problem.
This work studies infinite-armed bandits where mean re- wards of actions are initially drawn from a reservoir distri- bution and evolve over time under rested non-stationarity, While much of the existing literature on this topic focuses on stationary rewards (Berry et al., 1997; Wang et al., 2008; Bonald and Proutiere, 2013; Carpentier and Valko, 2015), the more challenging adversarial or non-stationary scenario has only recently been explored in the context of rotting (i.e., decreasing) rewards (Kim al., 2022; 2024). Kim et al. (2024)'s 's state-of-the- thr- algorithm for rotting bandits relies on prior knowledge of non-stationarity parameters and further regularity assumptions on the reservoir distribution to attain optimal regret bounds. However, these assumptions can be impractical in real-world applications.
1. Introduction
This work studies broader non-stationary model where rewards are decided by adaptive adversary and aims to derive regret bounds without requiring algorithmic knowl- edge of non-stationarity. Additionally, we go beyond the task of attaining optimal regret bounds as posed by Kim et al. (2024), and show enhanced regret bounds which can be tighter (i.e., possibly near-stationary rates) despite large non- non-stationarity. thus more properly capturing the theoret- ical limits of learnability in changing environments. Such insights are inspired by similar developments in the finite- armed analogue (Suk and Kpotufe, 2022), where substantial changes in best arm, called significant shifts, can be de- tected leading to more conservative procedures which don't 't overestimate the severity of non-stationarity.
We study the multi-armed bandit (MAB) problem, where an agent sequentially plays arms from a set A, based on partial and random feedback for previously played arms called rewards. The agent's goal is to maximize earned rewards.
Much of the classical literature (see Bubeck and Cesa- Bianchi, 2012; Slivkins, 2019; Lattimore and Szepesvári, 2020, for surveys) focuses on finite armed bandits where A [K] for some fixed K N. The theory here then typically assumes large time horizon of play T relative to
'Columbia University *CREST, ENSAE Paris. Correspondence to: Joe Suk <joc.sul wereesskk@@uueu @oo.umiia.cdu>.
Proceedings of the 4nnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Tracking Significant Shifts in Infinite Armed Bandits
1.1. More on Related Works
the problem to analyzing finite-armed bandits.
The most relevant works are Kim et al. (2022; 2024). The first of these works studies simpler model where the reser- voir distribution is uniform on [0, 1] and there's fixed upper bound p on the magnitude of round-to-round non- stationarity. Kim et al. (2022) show the minimax regret rate is p\/3 T + VT and derive a matching upper bound, up to log terms, but using algorithmic knowledge of p as well as a suboptimal regret upper bound without knowledge of p.
Along the way, we develop the first high-probabilityy regret bounds for the infinite-armed setting. Our regret upper bound in Theorem 5 also relaxes distributional assumptions on the reservoir distribution, not requiring an upper bound on the masses of randomly sampled rewards. Both such generalizations were unknown in prior works even in the stationary setting.
To our knowledge, our work is the first to develop adap- tive dynamic regret bounds of the style v1/312/3 A VLT with bandit feedback and adaptively adversarial changes. Notably, such results are yet unknown in the finite-armed setting. Note our setting is not directly comparable to finite-armed bandits as we assume known optimal reward value.
Kim et al. (2024) study general setting where the reservoir distribution for initial mean reward po(a) of arm satisfies ((pu(a) > 1-=x)
(xx") for all x E (0, 1). They study more general setting of 1-sub-Gaussian random rewards vs. our setting of [0, 1] --oounded rewards. They show a regret lower bound of order min V 242 T Lat T441 } in terms of number of changes L in rewards or total variation V (quantifying magnitude of changes over time).
We validate our findings via experiments on synthetic data, showing our procedures perform better than the previous art for rotting infinite-armed bandits.
With knowledge of L and V, they show a matching regret upper bound for 3 2 and a worse min 1//33//// VLT) bound for 3 < 1. We suspect this latter bound for B in fact tight due to earlier works (Carpentier and Valko, 2015, Theorem 1) showing 1 lower bounds on the final- round regret. Interestingly, in our [0, 1]-bounded rewards setting, this phenomenon does not occur and the minimax regret behaves the same for B < 1 or 3 2 1. Finally, Kim et al. (2024) also have suboptimal regret upper bounds without knowledge of or V.
2. Setup
2.1. Non-Stationary Infinite-Armet Bandits
We consider a multi-armed bandit with infinite armset A. At each round t, the agent plays an arm de choosing either to newly sample from A or to play an already sampled arm among the previously chosen arms (aI....,4,-1) (-11)
When the agent samples arm a, E A at round t, it observes random reward (a,)) E [0. 1] with mean (a(aa) E [0. 1] whose value is randomly drawn from mean reservoir dis- tribution. The reward of this chosen arm in the subsequent round is then decided according to adaptive adversary with access to prior decisions {a.bese and observations (Ya(a,))sst As in prior works (Berry et al., 1997; Wang et al., 2008; Carpentier and Valko, 2015; Bayati et al., 2020; Kim et al., 2024), we assume the reservoir distribution 3-regular, parametrized by a shape parameter | > O.
We also note that non- non-stationns non-staiionarity is well-studics in more structured many or infinite-armed bandit settings such as (generalized) linear (Cheung et al., 2019; Russac et al., 2020; Zhao et al., 2020; Kim and Tewari, 2020; Wei and Luo, 2021), kernel (Hong et al., 2023; Iwazaki and Takeno, 2024), or convex bandits (Wang. 2022). To contrast, our infinite- armed setting does not assume any metric structure on the arm space and so these works are not easily to comparable to this paper. We also note there are no known results on more nuanced measures of non-stationarity, like the significant shifts, even for such structured settings.
Assumption 1 (8-Regular Reservoir Distribution). We as- sume 3-regular reservoir distribution for some B > 0: there exists constants K1 >> O such that for all E [0, 1]: K2
1.2. Contributions
We show the first optimal and adaptive (a.k.a. parameter-free) regret upper bounds for non-stationary infinite-armer bandits (Theorem 5). In fact, our bounds are expressed in terms of tighter and more optimistic measures of non-stationarity (Subsection 2.2 and Theo- rem 3) new this work. This resolves open questions of Kim et al. (2022; 2024).
Ki x S <P(uo(a)) > 1 1-11) x) S k2 x9.
Remark 1. Prior works on non-stationary bandits (e.g. Bes- bes et al., 2019) typically allow for unplayed arms' rewards to change each round, which is equivalent to our setting with a different accounting of changes, as changes in yet unplayed arms do not affect performance.
We note our procedures are substantially different from Kim et al. (2022; 2024) who rely on explore-then exploit strategies whereas we revisit the subsampling approach of Bayati al. (2020) which partially reduces
Let (a( == 111-((er (e(a) be the gap of arm a at round f. Then, the cumulative regret is R = Ei= 8,,))) Let 8a a') := pr(a) - He(a') be the relative regret of arm a' to a at round t.
2

---

Tracking Significant Shifts in Infinite Armed Bandits
2.2. Non-Stationarity Measures
Suppose there are K == |Agg subsampled arms. One can show (e.g., Theorem 11) size K subsample of a 3-regular reservoir contains, with high probability, an arm with gap O(K-1/8) Thus, the first sum in (1) is at most T KK KK-1/
Let V : E==':ele-(aa--) ized total variation which measures the total variation of changes in mean rewards through the sequence of played arms. In Section 5, we also consider the total realized rotting variation VR := Σi=a - ( (at-1) - (r (1)++ which sums the magnitudes of rotting in rewards over time.
( - ())aa-)) denote the real-
Then, plugging in the classical gap-dependent regret bounds for finite-armed MAB, the second sum in (1) is Ô (E (8) where Ag) is the (random) i-th smallest gap to the best subsampled arm. Then, it is further shown (Bayati et al., 2020, Section A.2) that this gap-dependent quantity scales like Ö(K) in expectation, by carefully inte- grating A (2) over the randommess of the reservoir.
Let L := (ppaaa((()-))) + ( denote the realized count of changes, and LR := Σi=z (()((c11) < ()-1(0(-1)} the realized number of rotting changes
To contrast, the prior works Kim et al. (2022; 2024) con- sider priori upper bounds on V. L (i.e., the adversary is constrained to incur non-stationarity at most size V or count L). and so only show expected regret bounds in terms of such bounds. Our work establishes stronger high-rrobbillity regret bounds in terms of our tighter realized values of V, L.
Then, choosing K to balance the bounds T- T-K-1/6 and K on (1) yields an optimal choice of K x Toî giving a regret bound of T which is in fact minimax.
Extending this strategy to the non- stationary problem, it's natural to ask if we can follow an analogous strategy by reducing to K-armed non non-stationary bandits. However, this poses fundamental difficulties:
Key Challenges:
Remark 2. We note that our measures of non- non-stationarity V, VR, L, LR depend on the agent's 's decisions and so may not be directly comparable for different algorithms and/or adversaries. For an oblivious adversary, these quantities can be upper bounded by worst-cuse analogues which do not depend on the agent's 's decisions. Even in this more limited setting, optimal and adaptive regret upper bounds were previously unknown.
(a) As our goal in the non-stationary problem is to achieve adaptive regret bounds, without parameter knowledge, a naive approach is to reduce to adaptive K-armed non-stationary MAB guarantees (Auer et al., 2019; Wei and Luo, 2021; Suk and Kpotufe, 2022: Abbasi- Yadkori al., 2023). However, these guarantees only hold for an oblivious adversary, and so are inappli- cable to our problem. Furthermore, these algorithms only give worst-case rates of the form v /LKT in terms of L changes. In fact, it's known in this literature that no algorithm can adaptively secure tighter gap- dependent rates over unknown changepoints (Gariv- ier and Moulines, 2011, Theorem 13). As the gap- dependent regret bound is crucial achieving opti- mally balancing exploration and exploitation in our subsampling strategy. we see this approach can only hope to achieve suboptimal rates.
3. Regret Lower Bounds
Kim et al. (2024, Theorem 4.1 and 4.2) show regret lower bounds of order (I=+1)o-..70 A(V + for the rotting infinite-armed bandit problem, which is sub- case of our non-stationary setup. Our regret upper bound in Theorem 5 matches this lower bound up to log factors, without algorithmic knowledge of LR, VR-
4. A Blackbox for Optimally Tracking Unknown Non-Stationarity
(b) Secondly, we observe that upon experiencing changes, one may have to re-sample arms from the reser- voir distribution as the regret of the best subsampled arm min {a(a) can itself become large over time. Thus, we require more refined subsampling strategy which works in tandem with non-stationarity detection.
4.1. Intuition for Subsampling
A key idea, used for the stationary problem in Wang et al. (2008); Bayati et al. (2020), is that of subsampling a fixed set of arms from the reservoir. The main algorithmic design principle is to run a finite-armed MAB algorithm over this subsample. The choice of subsample size is key here and tradeoff, appearing
exhibits its own ppploratioon-xploiaattii through a natural regret decomposition with respect to the subsample, which we'll denote by Ao C A:
4.2. Our New Approach: Regret Tracking
We handle both of the above issues with the new idea of tracking the empirical regret d((a)) := 1 - Y((a)) proxy for tracking non-stationarity The key observation is that the empirical cumulative regret of played actions up to round f, D'= at fast logarithmic rates by Freedman's 's incquality and a self-bounding argument for (0, 1]-valued random variables.
T
T
RT-
min (a)
Σ max 5e(a, 0z) Ao
Ao
1 (a.), concentrates around Σ (a,))
1
Rogret of best subsampled
Regret to subsampled arm
3

---

Tracking Significant Shifts in Infinite Armed Bandits
This means, so long as Ex= 1 - (as) S L our re- gret will be safe up to the minimax stationary regret rate. On the other hand, if Σ agent must be experiencing large regret which means some non-stationarity has occurred if the agent otherwise plays optimally for stationary environments.
and Seldin, 2019; Io., 2021; Ioo and Takemura, 2023; Dann et al., 2023) satisfy Assumption 2.
(a,)) > f then the
Algorithm 1: Blackbox Non-Stationary Algorithm
1 Input:
Finite-armed MAB algorithm Base-Alg satisfying Assumption 1. Subsampling rate Sm.
Thus, at high level, our procedure (Algorithm 1) restarts the subsampling strategy outlined in Subsection 4.1 upon detecting large empirical regret.
2 Initialize: Episode count & t 1. Starting time
ts + 1. 3 for = 1,2, .... [To((T) do
Setting up relevant terminology, an episode is the set of rounds between consecutive restarts and, within each episode, we further employ doubling epochs, termed blocks, to account for unknown changepoints and durations of play.
Subsample S.. A 2 arms Am C C. Initiate a new instance of Base-Alg(2" Am). for t = ......., (fT + +2 1) A do
7
Play arm o, (receiving reward Y((m))) () as
chosen by Base-Alg(2"h, .. Changepoint Test: if
Within each block, we run the subsampling strategy for a fixed time horizon as blackbox. The blackbox takes as input knite-armed MAB base algorithm, parametrized by Base-Alg(( Ao) for inputs horizon / and subsampled set of arms An C A.
Σ 8.(am) 2 Ci (1.Aml 22 log (T) 62
then
Restart: 1/41 + +1,1, 1+1. Return to Algorithm 1 (Restart from mn =1).
Our only requirement of the base algorithm is that it attains a gap-dependent regret bound in so-called mildly corrupt environments, defined below. It's straightforward to show this is satisfied by classical stochastic MAB algorithms such as UCB (Lai and Robbins, 1985) (proof in Section C).
10
else if t= f2 + + 1 then
t + tt + 1 (Start of the (m + 1)-th block in the f-th episode).
12
Definition 1. We say finite-rmmdd non-stationary bandit environment (EE1),,)) over horizon T with armset Ao is a-mildly corrupt a > 0 there exists a reference reward profile {μ(a)]aEAo such that
4.3. Blackbox Regret Upper Bound
Vt E [T). E Ao Ipr(a) m(a)l a
The main result of this section is that Algorithm I attains the optimal regret in terms of number of changes L and total- variation V when / 2 1 and matches the state-of-art regret bounds with known L, V for 3 < (Kim et al., 2024).
Next, in stating the requirement of our base algorithm, we use de (a, a') : Ne (a)-Ne -e(aa) to denote the gap of arm a' to a in the context of a fimeee bandit (μr (a) au
Assumption 2. Let (eettt)t))) be an a-mildly cor- rupt T-round finite-ammed bandit with reference reward profile {p(a))aeea Let ((2) S (3)) .... ....))AAo)) be the ordered gaps induced by the reference reward profile. Then, Gase-Alg(TT,A) Ao) attains, with probability at least 1/T, for all t [T), a t-round static regret bound of (for Co free of (T),))))):
Theorem 2. Under Assumption I with 8 2 1, Algorithm I with S.. =
2mma satisfies, w.p. O(1TT):
R So (I)+ A (V 0iz T 8+1 + T ( ))
If < 1, Algorithm 1 with Sm == [mm-3/2] satisfies w.p.
1 O(1TT)
LA log(T) (T), (
Σ (a,a S 6la Co aεAA
((A() (1) 2 4a
max
R s Ō (V((+L))) (VV/3 +VT)).
Remark 3. Our Assumption is at firt glance similar to Assumption 1 of Wei and Luo (2021), but it in fact stronger in requiring gap cap-dependent bounds in environments with small variation as opposed to their requirement of O(VT) regret in such enviromments (Wang, 2022, Lemma 3).
Proof. (Outline) We given an outline of the proof with full details deferred to Section A. We also focus on the setting of 3 2 1 with (minor) modifications of the argument for 3 < 1 discussed in Subsection A.6. Let I, := 13 be the start of the (-th episode it,, te+1). Let L. be the (random) number of restarts triggered over T rounds. Let my be the index of the last block in f-th episode.
Remark 4. Bandit algorithms attaining state-of rute-of-theearr -hrt regret bounds in stochastic regimes with adversarial cor- ruption (Lykouris al., 2018; Gupta et al., 2019; Zimmert
4

---

Tracking Significant Shifts in Infinite Armed Bandits
Converting Empirical Regret Bound to Per-Episode Re- gret Bound. Following the discussion of Subsection 4.2, we first use concentration to upper bound the per-block am=+ regret Σ 2 o/ 8g (a,) on each block and to also lower bound it on blocks concluding with a restart. We first have by Freedman's 's inequality (Theorem 7) and AM-GM, with high probability, for all subintervals [s1, $2] of rounds:
large means there's round l' E [17 le+1) such that
by (0 2 Smn / (fe+1 - -tt ~ 2 Th デे..
Thus, from 2 meJtI 2 (le+1 - bτ) कt., (3) holds.
Regret of Base is Large. Now, if (B) is ((5m.) but (A) is o(Sm)). suppose for contradiction that (3) is reversed. Then, this means the finite MAB environment experienced by the base algorithm is (tt+1 -t)) अें -middl corrupt (Theorem 1). Thus, Assumption 2 bounds the regret of the base, which in turn bounds the per-block regret above:
Σ (as) - )c(an) S (T)
Σ (as) + log(T) 1=
8y (a,) + log(T)
2
1
Σ #=12"
de (ār, 0z) S 1Jtr
This allows us to upper bound the regret on each block [eT e7 tm+1) by (SS)) using the bound on empirical regret -1 20=T (a.) from Algorithm 1 of Algorithm 1.
Smy
log( (T),
(A 4
2 t 2
}
}. (4)
(2)
Then, summing Sm 2d कサं over blocks and episodes yields total regret bound of Ô (Et 1 (e) क
where (A Smy arms in Ame-
(A) are the ordered initial gaps to âe,my of the
Bounding the Variation Over Each Episode. It now remains to relate E/ (te+1 - tt)=f= to the total count L of changes and total variatioo V. To this end, we show there is a minimal amount of variation in each episode [be, (1-1) which will allow to conclude the total regret bound using arguments similar to prior works (Suk and Kpotufe, 2022, Corollary 2) (Chen et al., 2019, Lemma 5).
We then bound the RHS of (4) by O(Sma) to contradict our premise that (B) is (2,,m, ). In Bayati et al. (2020, Lemma D.4), bounding (4) by O(Sm,) was done in expectation by carefully integrating the densities of each random variable (6) But, this requires additional regularity conditions on assumed density for the reservoir distribution when /3 A 1 (op. cit. Section 6.1). To contrast, we bound (4) in high probability using a novel binning argument on the values of the Ass) 's and then using Freedman-type concentration on the number of subsampled arms within each bin. Details of this can be found in Subsection A.4.
We first introduce a regret decomposition, alluded to ear- lier in (1), based on the "best initially subsampled arm", āg... == arg max,e.Am Mu(a), where we use (u(a) to de- note the initial reward of arm a when it's first sampled. The regret in the last block [1T ,te+1,) of the f-th episode is:
4.4. Comparison with MASTER of Wei and Luo (2021)
te11-1
((())) =
Σ
Se(
+
Σ me
de (āe 41)
While our blackbox (Algorithm 1) bears similarities to the MASTER algorithm of Wei and Luo (2021), we highlight that Algorithm I's design is much simpler in not requiring randomized multi-scale scheduling of re-exploration for the sake of changepoint detection.
m
(A)
(B)
Then from the above and concentration, one of two possible cases must hold if a restart occurs on round 4 either (A) or (B) is 2(S... ). In either case, we claim large variation occurs over the episode:
The method of detecting changes is also different. MASTER detects changes by comparing the UCB indices of base algorithms scheduled at different times. To contrast, we only track the estimated cumulative regret in each block to track changes. This results in a simpler regret analysis where we don't need bound the regret incurred while waiting for re-exploration phase to be triggered.
[ur(ae-))= - Pe- Pe-1 (a.- (le+1 - te) -tt.. अो..
(3)
Regret of Best Subsampled Arm is Large In the case where (A) is I(Sm))) we know due to our subsam- pling rate Sme that âe,me will w.h.p. have an initial gap of Ö(2 me भंं) (Theorem 11). On the other hand, (A) being
5. Tracking Significant Shifts
While Algorithm 1 is a flexible blackbox which can make use of any reasonable aimite-armed MAB algorithm, the
5

---

Tracking Significant Shifts in Infinite Armed Bandits
regret bound of Theorem 2 is suboptimal for 8 < 1. Futher- more, we aim show regret upper bounds in terms of the tighter rotting measures of non-stationarity LR and VR (cf. Subsection 2.2).
5.2. Comparing Significant Shifts with LR. VR
We first note that the significant shift, like LR and VR, an agent- based measure of non-stationarity and so depends on the agent's 's past decisions.
In fact, we go beyond this aim and define a new measure of non-stationarity which precisely tracks the rotting changes which are most severe to performance.
Next, we caution that a significant shift does not always measure non-stationarity and can in fact be triggered in sta- tionary environments for a "bad" algorithm. For example, consider an agent sampling exactly one arm from the reser- voir and committing to it. Then, due to the large variance of a single sample, such algorithm incurs constant regret with constant probability. In this case, a significant shift is triggered even in a stationary environment as none of the subsample is safe. Thus, in this example, the significant shift tracks the agent's suboptimality.
5.1. Defining a Significant Shift
Recent works on non-stationary finite-armed MAB achieve regret bounds in terms of more nuanced non-stationarity measures, which only track the most significant switches in best arm, or those truly necessitating re-exploration (Suk and Kpotufe, 2022; Buening and Saha, 2023; Suk and Agarwal, 2023; Suk and Kpotufe, 2023; Suk, 2024).
In spite of this example, we argue that Theorem 3 still a meaningful measure of non-stationarity for all algorithms of theoretical interest, and indeed learning significant shifts via Algorithm 2 will allow to attain optimal rates w.r.t. LR VR (Theorem 5). Note that any algorithm attaining the optimal high-probabilityy regret of O(T in station- ary environments must sample at least T arms. Intu- itively, this is because securing an arm with gap at most 8 T= T- मों (which occurs for given arm with probability P( > 1 1- 6) O(8*)) requires 2265-9) trials. Indeed, this claim is also seen in the proofs of the stationary regret lower bounds (e.g.. Wang et al., 2008, Theorem 3).
Here, we develop and study an analogous notion for the infinite-armed bandit. First, we note in the infinite-armed bandit problem, there's no single "best arm", as the arm- space is infinite and, almost surely, no sampled arm will have the optimal reward value of 1. Yet, the core inution behind the notion of significant shift for finite MAB (Suk and Kpotufe, 2022, Definition 1) remains by definining a significant shift in terms of the regret experienced by each arm. First, we say an arm a is safe on an interval [$1, 82] of rounds if:
1 - (a) SKT (32 - + 1)
(5)
At the same time, any sample of Q( arms from the reservoir will contain an arm with gap O()) w.h.p.. (Theo- rem 11), which will maintain (5) over all subintervals. Then, significant shift will not be triggered unless this best sub- sampled arm' gap increases. Thus, any algorithm attaining optimal regret in stationary environments will satisfy w.h.p. L < L.
8=81
Then, a significant shift is roughly defined as occurring when every arm in some set of arms Á is unsafe and violates (5). If we let Á = A be the full reservoir set of arms, then this proposed definition may not by meaningful as there could always exist an unsampled arm which is safe in terms of regret, but unknown to the agent.
Additionally, the only way an arm with initial gap O becomes unsafe and violates (5) is if there's large rotting total variation (i.e., Vn is bounded below). This means L S La and we'll see in the next subsection that learning significant shifts in fact allows us to recover the optimal rate 0+1
For the subsampling strategy discussed in Subsection 4. we argue is sensible to let A = Ag. the set of sub-sampled arms. Based the discussion of Section 4, we see that subsample of size Q[t (((t=1)) contains w.h.p. a safe arm with gap O(t #11). This motivates the following definition of significant shift, which is defined for any agent (regardless of whether a subsampling strategy is used).
V गंz T in terms of VR (Theorem 5).
5.3. Regret Upper Bounds
Here, derive a tight and adaptive regret bound in terms of the significant shifts. In particular, we show regret bound of (i+ T) (V T
Definition 3 (Significant Shift). We say a bandit environ- ment over L rounds is safe if there exists an arm a among the 3 first tFFT arms sampled by the agent such that (5) holds for all intervals of rounds [81, 82] C [4. Let To == 1. Define the (i ++ 1)-th significant shift T++1 given Ti as the first round t t>1 T; such that the bandit environment over rounds [Te, f) is not safe. Let L be the largest significant shift over rounds
S+1 Tofx) ) in terms of i.
significant shifts and VR total rotting variation.
A preliminary task here is as follows: Goal 1. Show regret bound of Ö(1 ) in t-round safe environments. Given a base procedure achieving said goal, we can then use
and by convention let Ti+1 == T ++++
6

---

Tracking Significant Shifts in Infinite Armed Bandits
restart strategy similar Algorithm where we restart the base upon detecting significant shift.
Algorithm 2: Restarting Subsampling Elimination
Initialize: Episode count & f- 1, start t + 1. 2 for m = 1,2,.... [log(T)] do
For the finite K-armed setting, the analogous preliminary claim (Suk, 2024, Theorem 11) is to show a regret bound of ((V in safe environments. This is achieved using a randomized variant of successive elimination (Even-Dar al., 2006).
3 Subsample (2(m+1) F+T log(T) ^ 2th arms Am
and let Gep f- Am-
for ( ........
. (4T + +2th ----1- 1) A 7 do
Play arm ot as [Gi} and observe reward (a,)).
However, once again the infinite-armed setting is more anced and so this claim cannot directly be applied. In- deed, setting K == T results in a suboptimal rate of VKT Pド. The fundamental issue here is that the V KT rate captures a worst-case variance of estimating bounded rewards. To get around this, we do more refined variance- aware regret analysis relying on self-bounding tech- niques similar to those used to show Theorem 2 in Section 4.
Eliminate arms: g++1* +
9
a: 8 2 C2. |Aml (og(T)
s=tT
Restart Test: if gc+1 = 0 then
Restart: t/41 + ++ 1, 1.
Return to Algorithm 2 (Restart from m = 1).
To further emphasize the more challenging nature of show- ing Goal I, we notice that the regret analysis of our blackbox procedure Algorithm 1 in Subsection 4.3 crucially relies on bounding the logarithmic gap-dependent regret rate of As- sumption over periods of small total-variation (used to show (3)). However, such a gap-dependent regret rate is ill-defined when the gaps A; can be changing substantially over time (as to violate Assumption 2) which can happen in safe environments while we expect stationary regret rates.
else if t= 67 + 2 then t +- -- 1 (Start of the m + 1-th block in the f-th episode).
11
Proof. (Outline) We give a proof outline here and full details are found in Section B. It suffices to bound the regret on block [t . + ) by ((Sm). To show this, we do a variance- aware version of the per-arm regret analysis of Section B. in Suk and Kpotufe (2022).
Nevertheless, we show that different per-arm regret analy- sis gets around this difficulty. Our procedure (Algorithm 2) is restarting randomized elimination using the same dou- bling block scheme of Algorithm 1.
We first transform the regret according to its conditional expectation. Note that, from the uniform sampling strategy,
Going into more detail, we note, by uniformly exploring candidate armset G. at round f, we can maintain importance- weighted estimates of the gaps of each arm G::
(a
B((,(a;) H4-1]= = Σ
|9c
eEG.
M! (a) = (1 (a:)) 1 1(a = =}} P(a.-
Next, note that
H,-1)
Var[ór(ae) [H--1] s (a.)(aa))
[H-1] S Bloc(a:) H4-1).
where H4-1 is the o-algebra generated by decisions and observations up to round / 1.
Then, using Freedman's 's inequality (Theorem 7) with the above, we have for all subintervals I S [T], with probability at least 1 - 1/T:
Next, we note, by Freedman's inequality that the estima- tion error of the cumulative estimate E1sl 8IW (a) over
(. Ge
Σ ((r)a)) Σ NET
S (og(T) (T) Σ B(š,(a,) H4-1
interval of rounds scales like / E/EEz da(a) [... The inclusion of the (a) term inside of the square root is cru- cial here and, using self- boff-boundin arguments, yield tighter concentration bounds of order Ommaxer (9,l), which we can use as a threshold for fast variance- based elimination.
aEG,
1ET
log(T))
6i(a)
log(T))
19cl
Theorem 4. Let L be the number of episodes [te, t2-1) elapsed in Algorithmm 2 over T rounds. Algorithm 2 satisfies, w. p. at least 1 I/T:
NET aeg.
where the second inequality is from AM-GM. In light of the above, it remains to bound ΣK Ei=er
5.(a)
[s.1 where ta is
the last round in block [eT,, (m that is retained.
i
Ry Ō
Σ
tee+ - oi)
We next again use Freedman's 's inequality (Theorem 7) and self-bounding to relate Σier Se(a) to Eier 8 (a). We
7

---

Tracking Significant Shifts in Infinite Armed Bandits
have w.p. at least 1 1/T:
6. Comparing Blackbox vs. Elimination
Theorem and the nearly matching lower bounds of Sec- tion show that only rotting non- staaiioatoonitt (L I Ln and VR) factor into the difficullyy of non-stationarity. In other words, rising non-stationarity is benign for non-stationary infinite-armed bandits. Intuitively, this is because our prob- lem assumes knowledge of both the top reward value and upper bound on rewards, which coincide and are equal to 1. Hence, arms with rising rewards require less exploration.
Σ (a(a) - (5m((a)
max (ellog(()) [Tg + tele,". .tal
log(1 (T)
5t(a) 19
t=
CC
max
| log((),
(6)
rE(eTr.ta)
Interestingly, unlike the case with Algorithm 1, the elimi- nation algorithm's bound in Theorem does not require an upper bound masses of the reservoir (Assumption 1), or there's s no dependence on fi2 in the regret upper bounds of Theorem 5. This is new to this work and was not known even in the previous stationary regret bounds (Wang et al., 2008; Bayati et al., 2020; Kim et al., 2024). This suggests our regret analysis is simpler and, indeed, we only require that the initial best arm in the subsample has small gap (which only requires lower bounded masses of the reservoir as see in Theorem II). To contrast, the regret analysis of Theorem 2 (more similar to those of the aforementioned works) uses the upper bound on tail probabilities scaling with R2 to bound the regret of the finite-armed MAB base algorithm. Such a step avoided in the regret analysis of Theorem 4 by estimating the regret of each arm separately.
where again we use AM-GM in the second inequality. Next,
(((a) 19c1
I
max sElTT
5a(a).
_t4] [g.
Moving the 1 Exer 6c(a) to the other side in (6), we get
1a
(.()) S
3IW (a) + (og(
max GGll.
tE [t4]
1=
Combining the above two displays with Algorithm 2 of Algorithm 2, we have:
On the other hand, the blackbox can be seen as more ex- tensible as it allows for wide range of finite-armed MAB algorithms to be used as base. We finally note Algorithm 2 can essentially be reformulated as an instantiation of the blackbox with a successive elimination base algorithm.
(a) Gr
Sm G.
max
log(T),
11 -t- yields another log(Sm) factor, while summing over blocks m E [me] and episodes é [L] finishes the proof.
Now, summing max
| over arms a E Am
7. Experiments
O
Here, we demonstrate the performance of Algorithms I and 2 on synthetic datasets. For the Base-Alg in Algo- rithm 1 we use UCB (Auer et al., 2002). As benchmarks, we implement SSUCB (Bayati et al., 2020) and a variant of it using a sliding window with size vT (SSUCB-SW), and AUCBT-ASW (Kim et al., 2024), which achieves suboptimal regret bound of Ó(min(V 2 (L + 1) म T + m
We next show the regret bound of Theorem in fact recovers the minimax regret rates in terms of L. and VT.
Corollary 5. Algorithm 2 satisfies, w.p. at least 1 1/T:
R so R ( 11 A (V T
241
+ +ToF)
1 T.) }) in rested rotting setups.
Proof. (Sketch) Using similar arguments to the proof of Theorem 2, within each block the best initial arm âg. has gap Õ(2 st1). On the other hand, within a block 10Th (te+1) ending in a restart, this best initial arm is elimi- nated meaning there exists a round t E [t te+1) such that m Z (le+1 - ( ø²r, Thus, the gap of âg.m: must have increased by at least this amount which gives a lower bound on the per-episode total variation of Q((t+11 - te) xtं). Then, by similar arguments to the proof of Theorem 2, we deduce the total regret bound. LI
Comparing Total Variation- Regret Bounds. To ensure fair comparison between algorithms, we consider a rotting scenario where the mean reward of each selected arm decreases at a rate of OLLtt) at time t. In this environment, for all our algorithms, it can be shown that L = Q(T), V = Ö(1) For the case of 3 = 1 such that initial mean rewards follow a uniform distribution on [0, 1] (Figure 1(b)), both our algorithms outperform the benchmarks, with the climination one achieving the best performance. These results validate the insights of Section 6. Specifically, our
8

---

Tracking Significant Shifts in Infinite Armed Bandits
the blackbox algorithm may also be capable of adapting to significant shifts.
L65
Ad5
AUCS1AM
0,8
AJCSSAA07
15U03
Bacence (iigerthm 1
acddio (dggrttim Li
Remark Our implementation of Algorithm does not include the log(T) factor in the subsampling rate of Algo- rithm 2, as this lead to more stable experimental results. One can show this only changes the bound of Theorem 5 up to log" 2/3 (T) factor, which is not large for B E {0.6, 0.8, 1}.
22
0.6
0.4
0.4
0.2
0.2
20000 00000 80000 100000
40000 60000 80300100000
(a) B = 0.6
(b) B = 0.8
8. Conclusion and Future Directions
165
We've shown the first optimal and adaptive dynamic re- gret bounds for infinite-armed non-stationary bandit with arms drawn from reservoir distribution. For future work, it would be interesting to see if our techniques can be ex- tended to non-stationary linear bandits, and to design more practicalcoomputationalyy efficient procedures for detecting changes.
0.8-
AUCB1-00 1-A
0.6
0.4
0.2
00000 80000000000
(c) B
Figure 1: Experimental results showing regret of algorithms
Impact Statement
As our contribution here is primarily theoretical, advancing the state-of-art in infinite-ameed non-stationary bandits, we do not foresee any major societal impact concerns.
algorithms have a regret bound of ((T2)a) (Theorem 2 and Theorem 5) vs. AUCBT-ASW's bound of O(T4/4) (Kim et al., 2024).
In Figure! we observe that our algorithms outperform the benchmarks across various 3 values, aligning with theo- retical results. Furthermore, the performance gap between the elimination and blackbox algorithms increases as 8 de- creases, which is also consistent with our theoretical results.
References
Yasin Abbasi-Yadkori, András György, and Nevena Lazič. A new look at dynamic regret for non-stationary stochastic bandits. Journal of Machine Learning Research, 24(288): 1-37, 2023.
le5
Peter Auer, Nicolo Cesa- Desa-Bianchi, and Paul Fischer. Finite- time analysis of the multiarmed bandit problem. Machine learning, 47(2-3):235-22 256, 2002.
1.0
SSUCB-SW
SSUCB
0.8
AUCBT-AW
Blackbox (Algorithm
0.6
Elimination (Algorithm
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, 2019.
&z
0.4
0.2
0.0
Mohsen Bayati, Nima Hamidi, Ramesh Johari, and Khasha- yar Khosravi. Unreasonable effectiveness of greedy al- gorithms in multi-armed bandit with many arms. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Pro- cessing Systems, volume 33, pages 1713-1723. Curran Associates, Inc., 2020.
0
20000 40000 60000 80000100000
Figure 2: Experimental results showing regret of algorithms
Comparing Regret Bounds based on Number of Changes. Figure 2 covers the piecewise stationary set- VT
ting where we use a rotting rate of P. 1 at different rounds with B = 1. The prior art AUCBT-ASW (Kim et al., 2024) has regret bound of VLT = 73/1 yet we see from the plot that our procedures have empirically better regret owing to the small number of significant shifts. Surprisingly, we see the blackbox algorithm has comparable performance to our elimination procedure, suggesting that
Donald A. Berry, Robert W. Chen, Alan Zame, David C. Heath, and Larry A. Shepp. Bandit problems with in- finitely many arms. The Annals of Statistics, 25(5):2103- 2116, 1997. doi: 10. 1/14// 166362389.
Omar Besbes, Yonatan Gur, and Assaf Zeevi Optimal exploration-exploitatio a multi-armed- problem

---

Tracking Significant Shifts in Infinite Armed Bandits
with non-stationary rewards. Stochastic Systems, 9(): 319-337, 2019.
Learning Theory, pages 174-188. ALT 2011, Springer, 2011.
Thomas Bonald and Alexandre Proutiere, Two-target algo- rithms for infinite-armed bandits with bernoulli rewards. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger, editors, Advances in Neural In- formation Processing Systems, volume 26. Curran Asso- ciates, Inc., 2013.
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corrup- tions. Proceedings of the International Conference on Computational Learning Theory (COLT), 2019.
Kihyuk Hong, Yuhang Li, and Ambuj Tewari. An optimization- based algorithm for non-stationary kernel bandits without prior knowledge. In Francisco Ruiz, Jen- nifer Dy, and Jan-Willem van Meent, editors, Proceed- ings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 3048-3085. PMLR, 25-27 27 Apr 2023.
Sébastien Bubeck and Nicoló Cesa-Bianchi, Regret anal- ysis of stochastic and nonstochastic multi-armed bandit problems. Foundations and Trends in Machine Learning, 2012.
Thomas Kleine Buening and Aadirupa Saha. Anaconda: An improved dynamic regret algorithm for adaptive non- stationary dueling bandits. In Francisco Ruiz, Jennifer Dy, and Jan- Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial In- telligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 3854-3878. PMLR, 27-27k6 Apr 2023.
Shinji Ito. Parameter- free multi-armed bandit algorithms with hybrid data-dependent regret bounds. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 2552 2583. PMLR, 15 19 Aug 2021.
Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xie. Nearly optimal adaptive procedure with change detection for piecewise-stational bandit. Proceedings of the 22nd International Conference Artificial Intelligence and Statistics (AISTATS), 2019.
Shinji Ito and Kei Takemura. Best-of-three three-worlds linear bandit algorithm with ariiace-adaptivv regret bounds. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 2653- PMLR, 12-15 Jul 2023.
Alexandra Carpentier and Michal Valko. Simple regret for infinitely many armed bandits. ICML, 2015.
Shogo Iwazaki and Shion Takeno. Near-optimal algorithm for non-stationary kernelized bandits. arXiv preprint 2rXXi:2410.16000 2024.
Yifang Chen, Chung- Chung-Wei Lee, Haipeng Luo, and Chen- Yu Wei. A new algorithm for non-stationary contextual efficient, optimal, and parameter-free. In 32nd Annual Conference on Learning Theory, 2019.
bandits:
S. Jia, Qian Xie, Nathan Kallus, and P. Frazier. Smooth non-stationary bandits. In International Conference on Machine Learning, 2023.
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Learning to optimize under non von-stationarity. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1079-1087. PMLR, 2019.
Baekjin Kim and Ambuj Tewari. Randomized exploration for non-stationary stochastic linear bandit. Uncertainty in Artificial Intelligence, 2020.
Chris Dann, Chen-Ye Yu Wei, and Julian Zimmert. A blackbox approach to best of both worlds in bandits and beyond. In Gergely Neu and Lorenzo Rosasco, editors, Proceedings of Thirty Sixth Conference on Learning Theory, volume 195 of Proceedings of Machine Learning Research, pages 5503-5570. PMLR, 12-15 Jul 2023.
Jung-Hun Kim, Milan Vojnovic, and Se- Young Yun. Rotting infinitely many-armed bandits. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song. Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th In- ternational Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 11254 PMLR, 17-23 Jul 2022.
Eyal Even-Dar, Shie Mannor, and Yishay Mansour. Action elimination and stopping conditions for the multi-armed bandit and reinforcement learning problems. Journal of Machine Learning Research, 2006.
Jung-hun Kim, Milan Vojnovic, and Se- Young Yun. An adaptive approach for infinitely many- many-armed bandits un- der generalized rotting constraints. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Aurelien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In Proceed- ings of the 22nd International Conference on Algorithmic
10

---

Tracking Significant Shifts in Infinite Armed Bandits
Levente Koesis and Csaba Szepesvári. Discounted ucb. 2nd PASCAL Challenges Workshop, 2006.
Yining Wang. Technical note-on adaptivity in nonstation- ary stochastic optimization with bandit feedback. Opera- tions Research, 2022.
T.L. Lai and Herbert Robbins. Asymptotically efficient
adaptive allocation rules. Adv. in Appl. Math, 1985.
Yizao Wang, Jean-yves Audibert, and Rémi Munos. Algo- rithms for infinitely many-armed bandits. In D. Koller, D. Schuurmans, Y. Bengio, and L. Bottou, editors, Ad- vances in Neural Information Processing Systems, vol- ume 21. Curran Associates, Inc., 2008
Tor Lattimore and Csaba Szepesvári. Bandit algoritms. Cambridge University Press, 2020.
Fang Liu, Joohyun Lee, and Ness Shroff. change-
detection based framework for snrcewise-statioona multi- armed bandit problem. Proceedings of the AAAI Confer- ence on Artificial Intelligence, 2018.
Chen-Yo Yu Wei and Haipeng Luo. Non-stationary reinforce- ment learning without prior knowledge: An optimal black-box approach. Proceedings of the 32nd Interna- tional Conference on Learning Theory, 2021.
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme.
Stochastic bandits robust to adversarial corruptions. In Proceedings of the 50th Annual ACM SIGACT Sym- posium on Theory of Computing, STOC 2018, page 114-122, New York, NY, USA, 2018. Association for Computing Machinery. ISBN 9781450355599, doi:
Jia Yuan Yu and Shie Mannor. Piecewise-statien stationary bandit problems with side observations. Proceedings of the 26th Annual international Conference Machine Learning, pages 1177-1188 1144, 2009.
10.114453388744533888888
Peng Zhao, Lijun Zhang, Yuan Jiang, and Zhi-Hua Zhou. simple approach for non-stationary linear bandits. Inter- national Conference Artificial Intelligence and Statis- tics (AISTATS), 2020.
Anne Gael Manegueu, Alexandra Carpentier, and Yi Yu. Generalized non-stationary bandits. arXiv preprint: arXiv:2102.00725, 2021.
Julian Zimmert and Tor Lattimore. Return of the bias: Al- most minimax optimal high probability bounds for adver- sarial linear bandits. In Po-Ling Loh and Maxim Ragin- sky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 3285-3312. PMLR, 02-05 Jul 2022.
Joseph Mellor and Jonathan Shapiro. Thompson sampling in switching environments with bayesian online change detection, Carlos M. Carvalho and Pradeep Raviku- mar, editors, Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, vol- ume 31 of Proceedings Machine Learning Research, pages 442 450, Scottsdale, Arizona, USA, 29 Apr-01 May 2013. PMLR.
Julian Zimmert and Yevgeny Seldin. An optimal algo- rithm for stochastic and adversarial bandits. In Kamalika Chaudhuri and Masashi Sugiyama, editors, Proceedings of the Twenty-Second International Conference on Artifi- cial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pages 467-475 PMLR. 16 18-18 Apr 2019.
Yoan Russac, Olivier Cappé, and Aurélien Garivier. Al- gorithms for non-stationary generalized linear bandits. arXiv preprint arXiv:2003. 101113 2020.
Aleksandrs Slivkins. Introduction to multi-armed ban- dits. Foundations and Trends@ in Machine Learning, 12(1-2):1-286, 2019. ISSN 1935-8237. doi: 10.1561/ 2200000068.
Joe Suk. Adaptive smooth non-stationary bandits. arXiv preprint arXiv:2407.0865: 2024.
Joe Suk and Arpit Agarwal. When can track significant preference shifts in dueling bandits? Advances in Neural Information Processing Systems (NeurIPS). 2023.
Joe Suk and Samory Kpotufe Tracking most significant arm switches in bandits. Conference on Learning Theory (COLT), 2022.
Joe Suk and Samory Kpotufe. Tracking most significant shifts in nonparametric contextual bandits. Advances in Neural Information Processing Systems (NeurIPS). 2023.

---

Tracking Significant Shifts in Infinite Armed Bandits
A. Blackbox Algorithm Regret Analysis (Details for the Proof of Theorem 2)
Here, we present the details of the proof of Theorem following the outline Section 4, Again, we focus on the case of and discuss modifications the argument required for in Subsection A.6.
A.1. Preliminaries
Let Co, C1, C2.... denote constants not depending on T, Ri, or K2 (Assumption 1). In what follows, all logarithms will
be base 2. We'll also assume WLOG that (T) 2 Ki V fig, as otherwise we can bound the regret by constant only depending on 6j and K2-
Next, we establish basic fact about the block structure of Algorithm 1.
Fact 6. Recall from Section that me is the index of the last block the t-th episode. Then, for any episode (Lz, 1e+1) terminating restart (via Algorithm I of Algorithm }, we have
Sm
2 TFT
< n
and
C1 log)(T)
(te+1 - th (1r)) )
(8)
2
Proof. By Algorithm of Algorithm 1, we must have
f241-1
2 2 t&+1
th +12
Σ
1- (-(() C1 Amil- llog
s=ty my
Now, recall the definition of Sm so that |Amel = 2 9
2m. We first note that we cannot have Amal = 2 since
the above display would then become 2 C₁ Golog" (T)) Thus
f+1 - t/ +1 C1 न कम log (T) 2 Ci (te+1 ttth + 1) log"
Rearranging this becomes (le+1 1i + +1) > C₁ (T) Further, bounding le+1 1:th +1 5 2 (le+1 -1 finishes the proof.
A.2. Using Concentration to Bound Per-Block Regret (Proof of Theorem
We first present Freedman's inequality which is used in Section bound the regret using the empirical regret bound of Algorithm of Algorithm 1.
Lemma 7 (Strengthened Freedman's Inequality, Theorem 9 (Zimmert and Lattimore, 2022)). Let X1, X2,..., Xx be
martingale difference sequence with respect filtration Fi S F2 C ... S Fr such that E[[, Fi] 0 and assume
E||x,| Fi) < oo a.s.. Then, with probability at least 1 - 8,
V, Vog [2max(Ue, VVoi) + 2UT log
(2max(Ur, vVr]
Σ x 5 3
8
where VT = ET X Fi), and UT max(1, max X.).
We next use this to relate the per-episode regret to the empirical bounds of Algorithm 1. Lemma 8. Let &1 be the event that (a) for all blocks [eT (r
Σ (a,)) < 3C1 AAml (T))
12

---

Tracking Significant Shifts in Infinite Armed Bandits
and (b) for the last block 10 .lt1)) of episodes [Le, le+1) concluding in restart, we have:
t/41 -1
C1 -AAmel llgg((T)
Σ
Ód())) 2
(10)
2
Then, & occurs with probability at least 1 /T.
Proof. First, fix an interval rounds [$1, s2]. Then, we note that
1- 1-) -E[1 - (a,) H.-1],
martingale difference sequence with respect to the natural filtration {+e) of r-algebras H4, generated by the observations and decisions (of both deaee and adversary) up to round - 1. Now, since the choice of arm at round t is fixed conditional on H4-1, we have E{Y((a)) H4-1] = (az)). We also have since Yi(a)) E [0. 1]:
Var - Ya(a)) H4-1) - E[(1 Y=(a)))² H S E - Y((a)) Hz-1] = 5z(
Then, by Freedman's inequality (Theorem 7) we have with probability at least - 1//T8: for all choices of intervals
[81, 82] C [T]:
82
$2 (a,)) 2lg (2T
Σ 8=81
(1-Y(a,))))) (1 (o(aa))) S =3 log (2T3)
8=81
13 log (27
8, (a.) +
(11)
2
2
where the second inequality is by AM-GM. Going forward, suppose the above concentration holds for all subintervals of rounds [91, s2] C [Z]]
At the same time, on each m-th block, Algorithm of Algorithm gives us an empirical regret upper bound since the changepoint test is not triggered until possibly the last round of the block. Specifically, the inequality in Algorithm 1 of Algorithm must be reversed for the second-to-last round of the block
-2 1 1- Y-(s)))) < (1Aml V 2m/2) log)(T).,
Σ
where by convention we let thhh emetl = te+1. Thus,
Σ
1-Y,(a)) < Ci (lAml v 2m/22 (T) + 1.
(12)
Combining the above with (11), we conclude
Σ (a.)) < 2C1 (IAml v 2m/2). (Z) 13log(27") s 30 (1Am / 22 1og2(1) (I).
where the last inequality holds for C2 large enough.
13

---

Tracking Significant Shifts in Infinite Armed Bandits
At the same time, for constant C in Algorithm 1 of Algorithm chosen large enough, have that, for the last block F2 le+1) of an episode concluding in restart, must have
1++11
Σ 1- --(0)) 2 (1Aml V 22/22 (T)
1
2C' (lAmel V 2mm22) log
13 log(2T
C1 (1Amel v2m/2) (T),
0s(0s)
3
where the first inequality in the second line above comes from combining the first line with (11) and the last inequality holds for C1 large enough.
2m अीエ A 2 2m/2. Thus, |Aml V 2m/² [Amm in all
Finally, we note that for 3 2 1, we have [Aml - Sm A 2 our above inequalities.
A.3. Summing Regret Over Blocks
Next, we sum the per-block regret bound of Theorem over blocks m and episodes to obtain a total regret bound. Lemma 9, Under event Eg, we have
T Σ de(as) S (T)
Σ
(te+1 to) 041 041.
EE(T]
We first decompose the regret along episodes and blocks contained therein:
T
Σ
(aa)))
Σ 1 1-m() (=1]"
(=1 mm(mm)]
Then, on event ε,, we have summing (9):
T
Σ prra))
1 Σ Σ
3C1 |Aml
-lgg
{E(L) me m[[m
2 log²(T)
2 IFI
EE mE(m2)
< 02
Σ (tet1 - -te) (T).
(E[L]]
where in the last line we sum the geometric series over m and the fact that 2 अी. < (te+1 - -t) tfx a m
A.4. Showing there is Large Variation in Each Episode
Next, following the proof outline of Section 4, our goal is to show there is minimal amount of variation in each episode.
Lemma 10. Vl [ 1), w.p. 2 4/T:
441-1 1 [u((a-1)) - (--1(a--)) 2
log3(T) (T)
Σ
(t++1 tz) pナr
Proof. As outlined in the proof outline Section 4, in light the regret lower bound (10) of Theorem we consider two
14

---

Tracking Significant Shifts in Infinite Armed Bandits
different cases which recall below:
Ci Am. log" (T) (T)
(A)
4
t m
f -1
C1
Ci pe(ae,me) pe(a)) 2 4 A (T)
1 (ae
1 Am, (T) and
Σ
(B)
4
t
Now, event & due (10), one of (A) or (B) must hold. Our goal is show that in either case, large variation must have elapsed over the episode.
Best Initial Arm has Large Dynamic Regret. We first consider the former case (A). First, establish lemma asserting the best initially subsampled arm has small initial gap with high probability.
Lemma 11. (Proof in Subsection A.7) Recall that po(a) is the initial mean reward of arm a. Let de denote the best initial arm among the arms sampled in the last block of episode [te, t(+1) or âe,m, == arg max pola). Let Eg be the event that
log" (T)
vl [i] mo(
2 3-1
Then, Eg occurs with probability at least 1 1/T.
Now, from (A) (with large enough C > 16), we also know that there exists round 1 E [1,71, ((41) such that
Ci |.Amll -log
16 2 şiI log (T)
2 log (T)
1 Mer (ae,
4(te+1 t)
4-2-2m
2 +
This means the mean reward of arm âg.me must have moved by amount at least m कमा block, implying
mh
log²(T) over the course the
log 2 (te+1 - tt) 87
log²(T)
mo) - Myr (ae,
Since the adversary can only modify the rewards of an arm a after the round / it is played, the movement must have occurred on rounds where âe was chosen by the agent. Thus,
l041-1
log (te+1 12) 1
[pe(a=-1)= - Pr- p1-1(ar-)))
(pe(ae,me) - pe- ( 2 po(ag,me) - pe (āg,me)
Regret of Base Algorithm is Large. Now, we consider the other case (B), where the regret of the subsampled bandit environment over the rounds [cT (e))) large, while the dynamic regret of the best initial arm small, In this case, want show contradiction: that the total variation over the episode small, then the finite MAB environment experienced by the base algorithm must be mildly corrupt (Theorem which means Assumption be used to bound the regret of the last block. This will yield contradiction since by virtue of Algorithm being triggered, know the regret of the last block be large.
Suppose for contradiction that
141111 ( (--((a-1) <
log (te+1 te) te) ptr
(13)
Then, since our adaptive adversary only changes the rewards of arms on the rounds they are played, we have the finite-armed MAB environment experienced by the base is a-mildly corrupt (Theorem 1) with respect to reference reward profile (T)
{u(a))oEAm, and a = (te41 10
15

---

Tracking Significant Shifts in Infinite Armed Bandits
This means we can employ Assumption 2 to bound the regret. In particular, end goal here is to show that
C1 |mmel Alme--log10 (T',
me) - Ne(as) < 4
(14)
log" (1e+1 1
which will contradict (B) and imply (13) is true. First, by Assumption 2 with a
we have
te41-1
Σ pe(ae,mn)) - Me(at) S Co
Amyl
Σ
(T)
1 {
A { z log2(T)
(1141 ) /
+ -te+1-th
- ) गम. log (T)
(
Amir
To ease notation, we now parametrize the arms in Am, Mr } via (2,.... .2,...,/ee. 1.m.. and let A; be the initial gap of arm i to mg.
A == no m - (3),
Now, we will partition the values of A; based on a dyadic grid. Let
A
:= = Σ
1&
E
12- (f+1) - -oo m.)em - 80(@a, m))} E
where j ranges from 0 to
(le+1- 11m 7+1
log
42 log (T)
Next, the following lemma bounds Nz.e in high probability using Freedman's 's inequality (Theorem 7).
Lemma 12. (Proof in Subsection A.8) Let Eg be the event that the following hold:
3Kz
13
Vj E JJ. (I,...,,I L 1:: NN S
AAme
22-1 + log 3)
(15)
2
Lmmzl
(T)
3x2 SA. 5
Amel .2
(J+1))
13
log (27
(16)
12+1 - mi
2
Then, E4 occurs with probability at least 1 1/T.
The next lemma relates the cutoff A; 2 4a to the quantity 2J++2 showing that every gap A, such that A, 2 4a lies in one of the bins of the dyadic grid.
Lemma 13. (Proof in Subsection A.9) We have
2 (J+2) - -oo(āe,me) > 4a.
Now, Theorem 13 implies 2-(J+1) - 5g( me) > 4o. Thus, every gap A; such that 4:/4
log (T)
lies in some
(te me गデ
interval [2- (2+ 50 (a 2-2 - (0( for some j E (O,..., JJ or lies in the interval [4a, 2 (J+1)
50 (ār. m )):
Thus, bound
Amel
log(
A
2 5
Nz. 124-(2-044 (2-(++)) - -do(@e, log(T))
4
1=0
Ammel
+ logg(T) a-
1(a -A, 2- -o0(ae,me)
(17)
16

---

Tracking Significant Shifts in Infinite Armed Bandits
Now, by Theorem 13, have for all j {O,...,,J} J}:
2-(111 - me) > 2 (1+2)
Combining the above with Theorem 12, we have (17) is order
ITg aa (RalAAmm 22 + log((T) + log(T)
Σ 12 [Amel 20(2--9)+2 22-++1111)00 log(T). 5=0
We have
1
42 log a0 (T)
))
42 log (O) (T)
2 (J+11 2-
2
(te+1 1/ )
8
2 (te+1 - )) )
Then,
K2 .
2-
& 03 (le+1 - ( 2+1 log 10 (T)
1-
S c4R2 log 20 8) (TT) log 3 3 (T)
cs log(T))
where the second inequality follows from (8) of Theorem 6 and | 2 1, and the third inequality follows from log(T) 2 K2 by choosing? 7 sufficiently large. Thus,
log(T) a K22 (8g/Amel= 1 129AAmll22(Utt)) 22 + log(()) S ca CallAmllonn log((T)
Next,
182 lTg(T) Σ
(0(1-9)22 S 24(J+11
+ (2119)) (9(1--)1og2(0 (T)
1=0
21-0 v (te+1 E/
D4I
1-3
(Ivibs
(te+1 )
1-11 3 (T)
8log 8log2(T)
421-8 331-91og"00 2(1 (1-188 (11-B) (T)
42 log
8og (1 + log(T))
S c7 log (T),
where the first inequality follows from R2 S log(T), and the third inequality follows from , 2 1 and (8) of Theorem 6.
Thus, (17) is at most order Imm log' (T). Thus, choosing Ci large enough in Algorithm 1 of Algorithm 1, we have that (14) holds. Following earlier discussion, this means the subsampled bandit environment over the last block [t7 (e+1) is not mildly corrupt (Theorem 1). Then, for any ul.)) Ame - [0, 1), there always exists E [4T (4+1) and a' E Am, such that
log"(T)
(pe(d') - p(a')l
(te+1 t )
This means that since the adversary can only modify the rewards of arms at after the round 4, we have
f+111
1241-1
Σ
(m(((e-1)= - (1-1(a1-11 N
(m((a-1)) - (4)1(())2)
f211-1
Σ
[me(a') - (1-r(a')
t-
(a) - (ala')l
log²(T) (T)
(le+1 ((1r) 7.77
log 30g2(T) (TT)
(te+1 (t) ,ウन
17

---

Tracking Significant Shifts in Infinite Armed Bandits
A.5. Relating Episodes Non-Stationarity Measures
Now, we show how to derive
i Σ
(te+1 tex (T) S (1++)) T A (V 011
+ Tzri) log log"(T),
from the fact that, as we have shown by Theorem 10, for all episodes & E [ī. - 1]
log²(T)
( - - 11-1(ar-1))
(l2+1 tz) 8t1
We first show the bound in terms of total variation V. Let Vierie)) = Eessi [1((a - lh- (1-1(a Then, by using Hölder's 's inequality:
0+1
i
5+3
i-11
0+2
log" (1)
(l41 - (e) Jif log"(() (T) S Tix log (T) +
Σ (=1
(le+1 - (e) log गों (T)
(te+1 - -TI
1=1
E=1
x
L-1
< T logo +
Vieetess)
T 7+42
G+1
318+11 log (o+2)* (T)
1=1
< T (T) + V
2(--122 log (8+2)²
(T)
To show the bound in terms of T., we use Jensen's inequality the function x +> प combined with the fact that the number of episodes L s L + 1 by virtue of Theorem 10.
A.6. A Sketch of Modifications Required for Proving Theorem 2 for / <
Next, describe how show a suboptimal regret bound of order Σtn Vte+1 in the setting of 3 < 1. From here, using the steps of Subsection A.5 with 3 = 1, it is straightforward to show regret bound of /(I++ + 1)T /V133322// vT). For the sake of redundancy, we only give here a sketch of the modifications the argument required.
We'll first describe at high level the difficulty of showing Σ/= (te-1 (2) गमं
F regret bound using the same arguments of the previous sections for 3 < 1. In fact, the only place where 3 2 1 was used is in the final step where we bound (17). In particular, when bounding the sum Σラ (1(1-))+2 < 4(J + 1) (1-8) for / 2 1, 21--9) a constant. However,
for 3 < 1, we may incur an extra (le41 (TTh - term in the final regret bound due to this term. Thus, this argument would only yield suboptimal regret bound. Interestingly, Bayati et al. (2020, cf. 1.1. and Kim et al. (2024) also face this difficulty in bounding similar terms which leads to a suboptimal rate.
However, we can still attain a vbe11 - te per-episode regret bound using an altered subsampling rate Sm := mmm-9/2 2m which effectively "targets" /te+1 f regret rate.
Going into more detail, first key fact, observed in Bayati et al. (2020), is that subsampling S,,. arms ensures an arm with gap (((t++1 t2) -1/2). This can be seen analogously to the proof of Theorem 1I in Subsection A.7 where letting B I
and |Am,l 2 23/ in Subsection A.7 establishes that the best initial arm has gap at most log (T) 2 3/22
Then, the key fact to show will be analogue of Theorem 10: with probability at least 1 - 4/T, for all l _L - 1]:
log3(T)
(mo(a-11)= - (4-1(ax-2))
(18)
Vte+1 - tl
18

---

Tracking Significant Shifts in Infinite Armed Bandits
To show this, we'll essentially repeat the arguments of Subsection A.4 except specializing "3 1" to target bound scaling like Vle+1 te. Note that using the scaling [ml V 2m/2 in the regret threshold for the changepoint detection test (Algorithm of Algorithm 1) is crucial here [Aml 2mm < 2m/2 in the case of B < 1.
First, if the dynamic regret of the best initial arm āe,m; is larger than 4 2 2log/ (T), then using the previously established
fact that du (,, < log" (T) 2
m/2 -- we have that (18) holds.
- be(āg,m.) S 1 Gg2me/2 log) but Next, following the argument structure of Subsection A.4, suppose -
D m)) pa(a)) 2 2/2 log (T). Then, we invoke Assumption 2 with lo))(T) (le+1 - - -1/2 and use the same dyadic gridding argument with
(14+1 (4 -t ]
J = V Vog
42 200g001 (T)
Then, observe the bounds
(le+1 1. 1/12)2/22
log
a- 2 (J-18-
2
(+t+1 1, 11/2 2 (()) (1
log" (T)
J. 2.1001))) Ammel S 2m118/2 (le+1
82/2 < 2
Thus, show E'ep pe( me(ae) C1 C12mi/2 2og log2(T) if (18) does not hold, which contradicts our earlier supposition. This means (18) holds.
A.7. Proof of Theorem 11
Let no(a) denote the initial mean reward of arm By Assumption 1, we have
P po((e,me)) S log (T) (T)
log²(TT (T)
= P
max mo(a) S 11 aEAm,
2 ア+
2 उेo
log 30 (T)
1mmpl
P (o(a)) >
2 843
[Amel
log
2mc Jं 1:
log(T')
S exp
(-ldmel
2m ofr
T2
where the fourth line follows from assuming WLOG that log(T) 2 K2 2 and B 2 1, and the last inequality from |Amyl 2
A.8. Proof of Theorem 12
By Freedman's 's incquality (Theorem 7), we have with probability at least 1/T3:
NN E[N < 3/ E[N,,) log(273) + 32
Using AM-GM, this yields,
3E (N s
13
Nz. <
+ log (27
2
2
Finally,
-P(2-0+1)
(+1) - -80(ā),m.)) S A, 2- -50(0e,m))) 1 s 50(() 11+1)
<) PP - <Ho(i)) S k2 2-08
19

---

Tracking Significant Shifts in Infinite Armed Bandits
Thus,
E[N - (IAm, 1 1) R2 2-
This shows (15). (16) is showed in nearly identical manner.
A.9. Proof of Theorem 13
Recall a := log (T) and let ón mār, ease notation. First, suppose J = 1. Then, by Theorem 11
(121 4 2
(T)
(T)
2 do 4a
(te+1 2
Now, since 321 and 2
2 le+1 me it suffices show
1 1log2(T)
(te+1 - t ( 10
8 (le+1 )+T
However, this last inequality is true from (8) of Theorem 6 for sufficiently large C1. Now, suppose J > 1. Rearranging the desired inequality we have
1
4V2. (le+1 1 F+I
(60 + 4a)-a > 22+2 4(60 + 4a)
42 log" (T)
From (8) of Theorem 6, we have for sufficiently large C₁:
2 (1++1 1 )
> 4.
42 log (T)
Thus, in light of Theorem 11 and the definition of a want to show
21 (1)
4 log 2 (T)
16 log log²(1)) (T) पन
(te+1 t पम
(te+1 t
(te+1
)
which is always true.
B. Elimination Algorithm Regret Analysis (Proofs of Theorem and Theorem 5)
Following the notation of Section C, we let co. C1, ...... denote constants not depending on T, Ri, Ki (Assumption 1).
B.1. Details for the Proof of Theorem 4
As in the proof of Theorem in Section A, assume WLOG that log(T') 2 Kg -(1A2/) constant only depending K1.
or else we can bound the regret by
Following the proof outline of Subsection 5.3, we have by Freedman's 's inequality (Theorem 7) with probability at least 1- 1/T:
mm+1_
m++1_
m++1
{a)
Σ (a(a))
+
log(T)+ +
log(T)
B(ox(a+) He-1]
Gel
1=
6EG.
t=
4m 11
3
5,(a)
+ Cg log
2
|
1=1
20

---

Tracking Significant Shifts in Infinite Armed Bandits
where the second inequality uses AM-GM. Now, recalling that 1a is the last round in block [17" ,1"" 11=1)) that arm a E [K] retained, we have:
((
1
Σ
ó((a).
(19)
19
[g]]
1=tz
We next again use Freedman's inequality (Theorem 7) to relate Σter 5i(a) to Exer 8, (a). For the variance bound, we have
((()((a) 8. (4)) ((()))
= Bllg. (1 Yi(a)))² 1fa; = a} Hi-1
I |G.l E[([ Yi(a)) H4-1] E[1fa, a} [H-11]
= |9.l (a)
|
= 5,(a) 1c
We also have max,er (a) - (a)) S max,er Gel and E B| (a) Hz-1] = 5,(a).
From the above and Freedman's 's inequality, show that w.p. least 1 1/T, for any interval I [T] on which is retained:
Σ 8a(a) (a)
I c10
max
| (oglog((T)
log(T)
Σ
5((a) (9cl
t=
da( + en
max tE(??" rr]
G log(T):
(20)
2 1=
where again we use AM-GM in the second inequality. Moving the E. (a) to the other side, we get
(aa)
2
Σ
8!w (a) + 012 log(T) max [9c]-
1E [1a)
t=
Plugging the above into (19), have
(a) |0
<
max
RIW (a) + log(T)
max [
Eller (n)]
[gel
tE .tu]
1=
t=
Am |G.
< C14
max #EITT _.']
log(T")
where the second inequality is from the elimination guarantee (Algorithm 2 of Algorithm and max ,na Gel (Am)
We next have
11t < pm+ 1}+ +
1st = t 1}
max sETem 19 1] |9.1
19--1
ggm+
ac Am
amA.m.
LAml
(
1=1
< + log(
(og((Am)) )
Now, combining the above with our previous bound and summing over arms a, we have:
(a)
1a (r) s cis/Amm log2(T) (T).
9e
21

---

Tracking Significant Shifts in Infinite Armed Bandits
We know that for any m # me, we have [m = 2((+1))= log((?) We also have
Ammel S 2|Amm-11 = [22(7 )) At log(T)
Then, summing |Am log over E [me] and & E [?] gives us the regret bound of order Σí= (le+1 (e) log²(T)
B.2. Details for the Proof of Theorem 5
We define event E, such that, for any I [T].
Σ TE/
(((a) - 8. (a)
S
Σ EE
(t(a) + cielog(T) max (9rl, tET
(21)
2
which holds with probability at least - 11 1/T, by the same reasoning as (20) We consider episode & E [ř] that terminates in a restart and let me be the index of the last block in f-th episode and tz be the start time of the f-th episode.
Bounding the Number of Episodes. We claim the number of episodes is at most the number of significant shifts prove that significant shift must have occurred over some block in each episode concluding
i < L + 1. In particular, with restart. Let 1 be the time when arm is eliminated. For the m block [t]" ( fet1),, on Es, for each arm E Am,
we have by (21) and Algorithm 2 of Algorithm with C2 > 0 large enough::
(a(a)
2
8iw (a) 81(()) Σ 1
C18 log(T')
max rE|r, ,11]
[9el
2 CmrlAm,loog(]
Then, for all a E Ame where Ameel = 2(m+1) piP log(T) 2 (le41 - ( ofr log(T) 2 (1a ( şीP log(T)), we have
8.(a) > 3(te+1 ( (Tg)(T) 2 3(t - ( 8
JFF log (T)
(22)
which implies that (5) is violated for ITg 2 Kj meaning arm a is unsafe. By Theorem 3, a significant shift must have occurred within the block [1Th ,(4+1).
Now, by considering that the L-th episode may end by reaching the horizon T' rather than restarting, which does not ensure a significant shift, we conclude that L. < + Therefore, by using Jensen's 's inequality, we have w.p. at least 1 - 7-1,
i.
tt4 - t S A <i 11++)ATT Σ
(23)
Bounding the Per-Episode Variation. Next, we show that, on event &g where (21) holds, the total rotting variation over episode [te, at least
4-1-1
log (T') IT')
Σ (wr-1(ae-1)
Me (e >
(t++1 te) FFI
tore
From (22), we have for all a E Am,, there exists t' E [tmee te]
such that
(T))
3 log (T'
(x((a) 2 (ta +
(24)
(te+1 )
22

---

logg(T) Tracking Significant Shifts in Infinite Armed Bandits
Recall Mo (a) is the initial mean reward of arm Let āe.m be the best arm in terms of initial reward value no among the arms An subsampled for block [t,] 12a+)). We have
boog (T) n ZT7
2 2log" (T)
P <
(po(
= TP max ma(a) <1
aeAm,
n गे
hAmpl
2 2log (TT
< 1 Ki
2 747
2x1 log
"0 (T)
S exp
-|Amel
o 2 7+I
S T2
where the last inequality follows from log(T) 2 1i
and Amme
2 2n log(T)) Then, we define & to be the
corresponding bogh-probability event
(Ve [i] 11:11-p0 mm S 2l0gg me m
which holds with at least probability - 1/T. On Eg, we have
2 log (T) n में
21 2 log (T)
(T)
(25)
(le41
1m क
From (24) and (25), we can observe that the mean reward of arm âemme must have moved by amount least
log
log (T)
(l2+1 (/ Iा
(le+1 (z)
over the course of the block, implying
log "ogg(17 (T)
uo(ag pe (ār, 2
(1e+1 17 ( 3+Σ
(le+1 (e)
Since the adversary can only modify the rewards of an arm a, after the round played, the movement must have occurred rounds where âr.mz chosen by the agent. Thus,
log log²(T)
Σ (He-1(ac-1) (e(at-1))+ t=tz
(pe-1(@e,me) me( mo( Pe (āe,me))
(te+1 tt 8+1
t=
Next, this lower bound on the per-episode variation gives us, in identical manner Subsection A.5, a cumulative regret bound:
i
(le+1 42) ग.. (T) S log)(T)
(v (væiz ## + Tof
C. Verifying Assumption 2 for UCB
Here, we show the UCB algorithm satisfies Assumption 2. The proof will mostly follow the standard proof for showing the classsical logarithmic regret bound (e.g. Lattimore and Szepesvári, 2020, Section 7.1), with some small modifications to account for the mild corruption (Theorem 1).
We first present a variant of the UCBI Algorithm of Auer al. (2002).
Theorem 14. Algorithm 3 satisfies Assumption
23

---

Tracking Significant Shifts in Infinite Armed Bandits
Algorithm 3: Variant of UCBI (Algoritm 3 of Lattimore and Szepesvári (2020))
Input: number of arms K, horizon T. for / ,,..., do
Let N/- (a) _ 1,a = a).
(a) =
Let ( =-
Ni-1(a) E | 1aa = Y,(a)
(T) Na-1(a)
otherwise
Play arm a; arg [ UCBa(t 1).
Proof. Our goal is to establish high-probability regret bound over t S T rounds. First, using Theorem 1, we may write the regret as
max AEAD
(a(aa (s((a)) S max
Σ u(a) - ju(as) + a.
acAu
Recall Ni(a)= := Ex=1 1fa, a). Let Aa denote the gap of arm Ao. Then, can decompose the regret based on whether the gap of each arm is large or small and write:
u(a) u(as) S
Σ Ni(a) 11A. > 4a} + a.
(26)
aEAA0
then remains to bound Na(a) w.h.p for each a E An such that A, > a. WLOG, suppose arm = 1 is the best arm among the arms Ag, which we'll 'll index by the set [|.Ao]].
We claim with probability at least 1/T, for such that (a
32 log(T)
A2
(t) < (t).
(27)
This will allow us to conclude by bounding Nz(a) <
(2
(26).
Let (a(aa) E (a) 1fa, = a) and let (4) E (a((a) 1(a, = a). Then, by Azuma-Hoeffding inequality and union bound we have
Na(a) logg(27))
P Vs E (a.(a) p.(aa)
S 1/T.
Going forward, suppose the above concentration bound holds.
Now, to show the claim, we first note for & such that (a(a) >
32 log T))
and * 1 such that A. > 4o:
A
2 log((T
UCB = (a(a) +
(a)a)
(T)
12g
(a) +
(a)
(a)(a)
2 (Tg
log
<((a) +
+
Ni(a)
(a)
A
A
An
<(((a
3A
=(aa
24

---

Tracking Significant Shifts in Infinite Armed Bandits
where the third inequality is by Theorem 1. Meanwhile,
2 llgg(T) (T)
UCBi = (c(1)
Ne(a)
21og(T)
log(2T²)
2 (1)
Ni(a)
V
2N((a)
((1)
((1) Aa/4.
Thus, claim (27) is shown.
Remark 6. Although not shown here for the sake of redundancy, very similar regret analysis as Theorem 14 shows the Successive Elimination algorithm DEven-Dar et al., 2006) also satisfies Assumption 2.
25


Reviews:
[{"review_id": "UgPX4BPmIB", "reviewer": "Reviewer_onxF", "summary": "This manuscript deals with the problem of regret minimization in an infinite-arm bandit model with a reservoir distribution where shifts can occur. As such, this work is at the crossroad of infinite bandit and non-stationary bandits. Recently, Kim et al. (2024) have characterized the minimax cumulative regret as a function of the reservoir distribution of non-stationarity indices. However, their procedure required the knowledge of these non-stationarity indices (namely V_R and T_R). In this work, the authors introduce two rate-optimal procedures which only require the knowledge of the reservoir distribution. The procedures are based on a combination of three ideas: (i) using, as classical in this field, subsampling techniques to work with a finite arm problem (ii) tracking the empirical regrets/arm reward (which is estimable as the optimal reward is known) and (iii) suitably reinitializing the sampling process when the empirical regret is unusually large or all arms are unusually large.\n\n\n## update after rebuttal\nIn their rebuttal, the authors have well addressed my questions. Nevertheless, this does not change significantly my opinion on this work.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review and positive comments.\n\n> the authors should emphasize that the \"subsampling idea\" for infinite-arms bandit is much older than Bayati et al[2020], see the earlier work of Berry. It is in fact standard in the infinite arm field.\n\nThis is correct - subsampling was introduced earlier for this problem, and we'll adjust the writing to reflect this.\n\n> W1) The counterpart of this strength is that the key ideas for the algorithms are not so original, although such subsampling techniques appear to be new in for non-stationary infinite-arms bandits.\n\nIndeed, you're correct that subsampling was not used in the prior works on non-stationary infinite-armed bandits (Kim et al., '22, '24). We'd like to highlight two additional technical innovations required for our result:\n1. Tracking cumulative regret using variance-based confidence bounds (this was crucial for attaining the optimal regret bound for $\\beta < 1$ which was not achieved in previous works _even with parameter knowledge_). Note the previous works on adaptive non-stationary finite-armed bandits (e.g., Wei & Luo '21; Suk & Kpotufe '22) don't require such a refined analysis as their worst-case regret rates scale with the number of arms.\n2. Doing a high-probability per-arm regret analysis for subsampling (i.e., Lines 222--233, Column 2) which is novel and departs from the previous regret analysis for subsampling (e.g., Bayati et al., '20).\n\n> W2) I feel that the topic is perhaps not that important so that achieving adaptivity (while the optimal rate were already known) makes a big impact.\n\nAs we discussed in the previous answer, in fact the optimal regret upper bound was not known for $\\beta < 1$ as there was a gap between upper and lower bounds even with knowledge of non-stationarity. Our work closes this gap.\n\n> As such, hypotheses are lacking for Theorem 4 and Corollary 5. If the authors do not want to rely on Assumption 1, they should at least introduce a dedicated assumption.\n\nTheorem 4 and Corollary 5 rely on Assumption 1, but without the upper bound on masses involving $\\kappa_2$.\nWe'll make this more clear in a revision.\n\n> In Section 1.2, the authors emphasize that this is the first work to develop dynamic regret bounds of the $V^{1/3} T^{2/3} \\land \\sqrt{LT}$, while such result are unknown in the finite-arm setting. I would simply like to point out that the infinite-arm setting has distinct feature which can make the problem easier than finite arm: the optimal reward is known and the distribution of the mean rewards is also known.\n\nThis is an apt point that the two settings are not directly comparable. We contend that the infinite-armed setting is not necessarily \"easier\" than the finite-armed counterpart. For instance, the optimal regret bounds in our setting must be free of the number of arms and so a crude $\\sqrt{KT}$ bound cannot be plugged in for subsampling, instead necessitating tighter instance-dependent or variance-based bounds (as can be found in our work). In comparison, the $\\sqrt{LKT}$ regret bound in $K$-armed non-stationary bandits does not require such refined analyses.\n\n> In Theorem 2, the authors provide a cumulative regret bound for Algorithm 2 which rely that use, as black-box, a bandit algorithm for $\\alpha$-mildly correct bandits. How does the bound in Theorem 2 depends on $\\alpha$? Alternatively, should the black-box satisfy the bound of Assumption 2 for any $\\alpha$?\n\nAs our goal is to attain the optimal regret bound of $\\sqrt{LT} \\land V^{1/3} T^{2/3}$, we in fact only require Assumption 2 to hold in each episode $[t_{\\ell}, t_{\\ell+1})$ for $\\alpha \\approx (t_{\\ell+1} - t_{\\ell})^{-\\frac{1}{\\beta+1}}$.\nIn terms of $\\alpha$, we then show a regret bound of $\\sum_{\\ell=1}^{\\hat{L}} (t_{\\ell+1} - t_{\\ell}) \\cdot \\alpha$ where $\\hat{L}$ is the total number of episodes. Thus, for Theorem 2 to hold, it is **not** required for Assumption 2 to be true for any $\\alpha$. Nevertheless, we show in Appendix C that classical algorithms such as UCB do in fact satisfy Assumption 2 for any $\\alpha$.", "claims_and_evidence": "The manuscript is clearly written and all the proofs seem to be correct.", "methods_and_evaluation_criteria": "The proposed procedures are minimax adaptive with respective to the cumulative regret which is the standard way of  evaluating the performances for a bandit problem.", "theoretical_claims": "I checked all the proof sketches and all the general arguments in the proof but I did not check all computational details. There does not seem to be any typo.", "experimental_designs_or_analyses": "The small-scale numerical experiments illustrate well the theoretical findings.", "relation_to_broader_scientific_literature": "The main contribution of this work is adaptivity to non-stationarity in infinite-arm bandits. This improves over the recent work of Kim et al. [2024]. For that purpose, the authors mainly adapt a sucessive elimination algorithm from (Even-Dar et al, 2006). As an aside, the proofs built upon previous arguments of Suk for non-stationary multi-armed bandits.", "essential_references_not_discussed": "Not really, but the authors should emphasize that the \"subsampling idea\" for infinite-arms bandit is much older than Bayati et al[2020], see the earlier work of Berry. It is in fact standard in the infinite arm field.", "other_strengths_and_weaknesses": "S1) On the positive side,  this is the first work which is adaptive to the changes in the infinite arm regime. Besides, the new algorithms are quite simple and natural. \n\nW1) The counterpart of this strength is that the key ideas for the algorithms are not so original, although such subsampling techniques appear to be new in for non-stationary infinite-arms bandits.\n\nW2) I feel that the topic is perhaps not that important so that achieving adaptivity (while the optimal rate were already known) makes a big impact.", "other_comments_or_suggestions": "As such, hypotheses are lacking for Theorem 4 and Corollary 5. If the authors do not want to rely on Assumption 1, they should at least introduce a dedicated assumption.\n\nIn Section 1.2, the authors emphasize that this is the first work to develop dynamic regret bounds of the $V^{1/3}T^{2/3}\\wedge \\sqrt{LT}$, while such result are unknown in the finite-arm setting. I would simply like to point out that the infinite-arm setting has distinct feature which can make the problem easier than finite arm: the optimal reward is known and the distribution of the mean rewards is also known.", "questions_for_authors": "In Theorem 2, the authors provide a cumulative regret bound for Algorithm 2 which rely that use, as black-box, a bandit algorithm for $\\alpha$-mildly correct bandits. How does the bound in Theorem 2 depends on $\\alpha$? Alternatively, should the black-box satisfy the bound of Assumption 2 for any $\\alpha$?", "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": "iTxZYFmXva", "reviewer": "Reviewer_8A6S", "summary": "This paper considers an infinite-armed bandits problem in a non-stationary setup. The means of the arms are drawn from a reservoir distribution and are chosen by an adaptive adversary in later rounds. Two algorithms are proposed with theoretical guarantees and experiments are conducted to illustrate the empirical performance.\n\n## update after rebuttal\n\nWhile the authors have resolved some of the questions, I lean to maintain my score. While the rotting cases considered in the proof of the bounds are valid (thus worst case bound is proved), I believe more general cases that consider both the rotting and rising parts of the nonstationary process are of great interest. Additionally, as mentioned by Reviewer T9xW, more comparisons with the existing method MASTER are required.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review, and astute questions.\n\n**On Comparison of Regret Bounds and $V, V_R, S_T$ Depending on Agent**:  You're correct that, in general, a direct comparison of bounds between algorithms is tricky since the adaptive adversary may vary its behavior depending on the algorithm. As a trivial example, a naive algorithm which samples a single arm and commits to it for $T$ rounds would incur linear regret $\\Omega(T)$ in a stationary environment, yet could incur constant regret if an adversary helps the agent and increases the reward of the committed arm to make it optimal.\n\nWe note this phenomenon is inherent to all online learning settings involving an adaptive adversary, yet there is a substantial literature of works analyzing _dynamic regret bounds_ in terms of quantities such as $V$ or $L$ (which as you note depends on the adversary and algorithm) (e.g., see [1]-[4] below).\n\nFor some specific choices of adversary, a comparison of regret bounds is meaningful. For example, if the adversary is oblivious, then $V,V_R,S_T$ in our work can be upper bounded by worst-case quantities which do not depend on the agent's decisions, but on restless changes. Even for such an oblivious adversary, we note optimal and adaptive regret upper bounds were unknown before this work.\n\nWhether other meaningful choices of adversary could yield direct comparison of regret bounds is an intriguing direction for future work.\nWe'll include this discussion in a revision.\n\n**On Lower Bounds in Rotting vs. General Non-Stationary Setup**: You're correct that we consider a more general setup than the rotting setup of (Kim et al., '24). Since our setup includes the rotting problem as a sub-case, the worst-case lower bounds for our setup are at least as large as the worst-case lower bounds for the rotting sub-case. Thus, the lower bounds of Kim et al., '24 hold for our setting as well.\n\n**On Broader Experimental Comparison with Other Algorithms and Setups:** We emphasize our main contribution is theoretical, rather than to propose a practical algorithm. The algorithms in our paper are of a theoretical nature that serves to resolve the main question of attaining the first optimal and adaptive regret bound for non-stationary infinite-armed bandits. The synthetic experimental results of Section 6 are mainly to support the message that our algorithm does indeed attain improved regret over the previous state-of-art. We agree with the reviewer that there's much further work to be done in designing more practical procedures, and admit the theoretical state-of-the-art is far from this.\n\nWe'd also like to note that the strategy of \"sampling a fixed set of arms and then running a finite-armed non-stationary bandit algorithm'' would not have the correct theoretical regret upper bounds as the optimal sampling rate depends on the unknown non-stationarity and, furthermore, only worst-case rates of the form $\\sqrt{LKT}$ for $K$ sampled arms are known for such procedures (e.g., Wei & Luo, '21), which would be inadequate for attaining the optimal regret rate (see discussion in Lines 301--308, Column 2). The difficulty of using this approach is also further discussed in Lines 112--140 (Column 2) of the paper.\n\n>   The paper indicates the rising non-stationarity is benign and only exploit the case where the rewards are decaying (Corollary 5). Therefore, it remains unclear to me whether the bound can be further improved or not if take the rising part into consideration.\n\nWe'd like to emphasize that we _allow_ for both rising and rotting non-stationarity. You are correct, however, that the bound of Corollary 5 is worst-case and only takes into account the challenge of rotting changes. It is an interesting future direction to study whether rising can improve the rate. Note, even in finite-armed bandits, improved regret bounds beyond the worst-case $\\sqrt{LT} \\land V^{1/3} T^{2/3}$ rates are still unknown in general.\n\n> However, in remark 1, the authors indicate Kim et al. 2022; 2024 allow for unplayed arms' rewards to change each round. As I checked these two papers, they consider rested rotting bandits, where only the means of the pulled arms will decrease and the means of unplayed arms remain unchanged.\n\nThanks for catching this! You're correct that Kim et al. ('22, '24) in fact study the same rested setting as ours, and we'll revise this remark.\n\n[1] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multiarmed bandit problem. SIAM\njournal on computing, 2002.\n\n[2] Ali Jadbabaie, Alexander Rakhlin, Shahin Shahrampour, and Karthik Sridharan. Online Optimization : Competing with Dynamic\nComparators. AISTATS 2015.\n\n[3] Tianbao Yang, Lijun Zhang, Rong Jin, and Jinfeng Yi. Tracking slowly moving clairvoyant: Optimal dynamic regret of online\nlearning with true and noisy gradient. ICML, 2016. \n\n[4] Peng Zhao, Yu-Jie Zhang, Lijun Zhang, and Zhi-Hua Zhou. Dynamic regret of convex and smooth functions. NIPS ’20", "claims_and_evidence": "Yes, the authors provide proof outlines in sections 4 and 5 with details in the appendix. \n\nHowever, in remark 1, the authors indicate Kim et al. 2022; 2024 allow for unplayed arms' rewards to change each round. As I checked these two papers, they consider **rested** rotting bandits, where only the means of the pulled arms will decrease and the means of unplayed arms remain unchanged.", "methods_and_evaluation_criteria": "Yes, the blackbox non-stationary algorithm transforms an algorithm for stationary bandits to adapt to the non-stationary bandits. The second algorithm tracks the significant changes in the means of the arms. These are common techniques in the non-stationary bandits literature.", "theoretical_claims": "I went through the proofs are the theorems. They appear reasonable to me.\n\nThe thing that confuses me is the use of $V$, $V_R$ and  $S_T$ in the regret bounds. These quantities measure the level of non-stationarity of the instances, but they also depend on the chosen arms and, consequently on the algorithm. Since different algorithms result in different values for these measurements, a direct comparison of regret bounds becomes nontrivial. For example, if an algorithm $\\pi_1$ achieves a regret bound $R_{\\pi_1}$ of order $O(V_{\\pi_1}^{1/3})$ and another algorithm $\\pi_2$ achieves $R_{\\pi_2}=O(V_{\\pi_2}^{1/2})$, it remains unclear whether $R_{\\pi_1}<R_{\\pi_2}$ or not. It is appreciated that the authors can provide more discussions on this.\n\nIn addition, for the regret lower bounds in section 3, the authors invoke the lower bounds in Kim et al. (2024), which are derived for the rotting infinite-armed bandit problem. Since this manuscript is considering the more general infinite-armed bandits problem, where the bandit instances may not be the rotting bandits case and the means of the arms are chosen by an adaptive adversary, the lower bounds for the rotting bandits cannot be directly applied here.", "experimental_designs_or_analyses": "The paper provides experimental results on some synthetic datasets, which follow the rotting bandits setup.\n\nThe experiments compare the performance of the proposed algorithms and two other algorithms in the infinite-arms setup. As there is a large amount of work on (finite-arm) non-stationary bandits, it is expected to include those algorithms as well (maybe by sampling some arms at first, followed by applying these algorithms on the sampled arms.) Also, the more general bandits setups (e.g., fluctuation, rising bandits) are expected, beyond the rotting bandits setup.", "relation_to_broader_scientific_literature": "This paper considers regret minimization in the non-stationary bandits with infinite-many arms. It extends tracking the significant shifts to the infinite-armed bandits case or, extends the infinite-armed bandits to the more general non-stationary case.", "essential_references_not_discussed": "The references look appropriate to me.", "other_strengths_and_weaknesses": "**Strengths**\n1. This paper introduces a parameter-free algorithm for the non-stationary infinite-armed bandits.\n2. The blackbox framework extends the finite-armed bandit techniques to the non-stationary case.\n\n\n**Weaknesses**:\n1. The paper indicates the rising non-stationarity is benign and only exploit the case where the rewards are decaying (Corollary 5). Therefore, it remains unclear to me whether the bound can be further improved or not if take the rising part into consideration.", "other_comments_or_suggestions": "None. Please refer to the above sections.", "questions_for_authors": "Please refer to the above sections.", "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": {"ethical_review_concerns": "None"}}, {"review_id": "VjXU6ld9XA", "reviewer": "Reviewer_T9xW", "summary": "The paper studies the non-stationary infinite-armed bandit problem where arms' mean rewards are initially sampled from a $\\beta$-regular reservoir distribution and evolve under adversarial/non-stationary dynamics. Prior works focused on stationary rewards or specific non-stationary cases requiring prior knowledge of non-stationarity parameters. This work addresses general adversarial non-stationarity without parameter knowledge, relaxing distributional assumptions of the reservoir. The model captures scenarios with massive action spaces where rewards change adaptively based on played arms.\n\nMain Algorithmic Ideas: The proposed framework introduces two key innovations:  \n1. Blackbox Reduction: Converts finite-armed MAB algorithms into parameter-free algorithms for infinite arms via dynamic subsampling. Uses empirical regret tracking to detect non-stationarity and trigger restarts.  \n2. Randomized Elimination: Enhances adaptation through a restarting elimination algorithm that detects \"significant shifts\" — intervals where all subsampled arms become suboptimal due to non-stationarity.  \n\nMain Results: Achieve the first optimal and parameter-free regret bounds for infinite-armed settings which are validated by the experiments.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the insightful review, writing suggestions, and careful discussion about the similarities with the blackbox MASTER algorithm of Wei \\& Luo, 2021.\n\n>   In my opinion, the methods of this work primarily extends the black-box technique from [Wei and Luo, 2021] to the infinite many-armed bandit setting, which is reasonable.\n\nWe respectfully disagree with this main point, which we believe may have lead to some confusion about the novelty of our contribution. Although our Algorithm 1 is also a blackbox, it has an entirely different algorithmic design, requirements on the base procedure, and regret analysis than MASTER. We do not agree it is a \"modification or adaptation of MASTER\" for the infinite-armed setting.\nWe elaborate on the differences below:\n1.  Our requirement on the base algorithm (Assumption 2) is stronger than the requirement for the base learner in MASTER (Assumption 1 of Wei & Luo, '21). Namely, we require the base algorithm to achieve instance-dependent $\\log(T)/\\Delta$ regret bounds in mildly non-stationary environments whereas MASTER requires its base learner to have a $\\sqrt{KT}$ regret bound (see Lemma 3 of Wang, '22). This difference is quite crucial as a $\\sqrt{KT}$ bound would have been insufficient for attaining the optimal regret bound in our setting (see discussion in Lines 301--308, Column 2). This difference is discussed in Remark 2 of our paper.\n2. As you correctly observed, we rely on empirically tracking the cumulative regret of the algorithm to detect non-stationarity (which is a new idea), rather than tracking UCB indices of different base algorithms as MASTER does.\n3. Our algorithm is conceptually different from MASTER, with **no randomized multi-scale scheduling** of different base algorithms to facilitate re-exploration of discounted arms. Instead, we run a single a base algorithm and track its cumulative regret to detect non-stationarity.\n4. As a result, our regret analysis substantially differs from that of MASTER's, as there is no need to argue about the guarantees of the re-exploration schedule. Instead, much of the proof of Theorem 2 relies on  proving a novel high-probability regret upper bound for subsampling in mildly corrupt environments (see Lines 222-233, Column 2).\n\nAdditionally, one of our main contributions is the elimination algorithm (Algorithm 2) which in fact achieves tighter regret bounds than our blackbox. Note our elimination algorithm is not a blackbox at all , and thus bears no similarity with MASTER. The only other works which study \"significant arm identification\" (Suk & Kpotufe, '22, '23) all again rely on randomized multi-scale scheduling of different base algorithms to target a worst-case $\\sqrt{KT}$ regret bound. Our regret analysis is thus very different, with no need for analyzing random scheduling, and instead focused on novel variance-based confidence bounds for tracking empirical regret (see discussion in Sec. 5.3).\n\nWe will better elaborate on these differences with the blackbox MASTER in rewrites.\n\n> In the experiments, it seems that only the impact of different $\\beta$ of initial distributions on performance was considered, while the effect of varying non-stationarity was not validated. For instance, the regret bounds presented include two scenarios: one for piece-wise stationary settings, resulting in a $\\sqrt{LT}$ bound, and another for drifting, yielding a $V^{1/3} T^{2/3}$ bound. However, the experiments appear to validate only the latter case.\n\n[Here](https://imgur.com/a/infinite-armed-nonstationary-bandit-experiments-Kj6VjRZ), we provide two plots of additional synthetic experiments. The second plot covers the piecewise stationary setting where we use a rotting rate of $\\rho_t=1$ at $L=\\sqrt{T}$ different rounds with $\\beta=1$. The prior art AUCBT-ASW (Kim et al., '24) has a regret bound of $\\sqrt{LT} = T^{3/4}$, yet we see from the plot that our procedures (Blackbox and Elimination) have empirically better regret owing to the small number $\\tilde{L} = O(1)$ of significant shifts. We've also included an additional benchmark, a sliding-window version of SSUCB (of Bayati et al., '20) using a window size of $\\sqrt{T}$, for more expansive comparison.\n\n> The abstract does not meet the submission requirements. According to the ICML submission guidelines, abstracts must be written as a single paragraph. However, the abstract in this paper is divided into three paragraphs.\n\nThank you for pointing this out, as well as other writing suggestions. We'll fix it in revision.", "claims_and_evidence": "The claims presented in this paper are all supported by corresponding theoretical proofs.", "methods_and_evaluation_criteria": "In my opinion, the methods of this work primarily extends the black-box technique from [Wei and Luo, 2021] to the infinite many-armed bandit setting, which is reasonable.\n\n[1] Chen-Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. COLT 2021", "theoretical_claims": "The theoretical claims presented in this work appears to be sound, and the results align with intuition, but I have not thoroughly check the proofs.", "experimental_designs_or_analyses": "In the experiments, it seems that only the impact of different $\\beta$  of initial distributions on performance was considered, while the effect of varying non-stationarity was not validated. For instance, the regret bounds presented include two scenarios: one for piece-wise stationary settings, resulting in a $\\sqrt{LT}$ bound, and another for drifting, yielding a $V^{1/3}T^{2/3}$ bound. However, the experiments appear to validate only the latter case.", "relation_to_broader_scientific_literature": "Developing optimal and parameter-free algorithms for non-stationary bandits is a highly meaningful problem. Previous results have primarily focused on finite-armed multi-armed bandits (MAB) and other contextual bandit/RL scenarios, as well as bandit convex optimization (BCO) settings. This work advances the research by extending it to the infinite many-armed MAB setting.", "essential_references_not_discussed": "I believe the discussion regarding [Wei and Luo, 2021] in this work is significantly lacking. The black-box algorithm proposed in this work largely draws inspiration from the MASTER operation in [Wei and Luo, 2021]. The paper only briefly mentions in Remark 2 a subtle difference in the definition of near-stationarity compared to [Wei and Luo, 2021], but it entirely omits any discussion on the methodological and conceptual distinctions. This could lead readers to mistakenly assume that the black-box framework is an original contribution of this work. However, in reality, from the near-stationary detection rules to the integration method of the base algorithm and the format of theoretical guarantee, it bears a high degree of similarity to [Wei and Luo, 2021].\n\nFirst, I believe the authors should explicitly acknowledge the inspiration and learning from [Wei and Luo, 2021] in their black-box framework. Then, they should clarify the specific methodological differences that enable the transformation of a finite-arm algorithm into an infinite-arm one. As a parallel example, [Wang, 2022], which also extends [Wei and Luo, 2021], focuses on adapting it to non-stationary bandit optimization. In that work, the author clearly states the learning and referencing of the black-box framework, as well as the specific adaptations made to suit the bandit optimization setting.\n\n[1] Chen-Yu Wei and Haipeng Luo. Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach. COLT 2021.\n\n[2] Yining Wang. On adaptivity in nonstationary stochastic optimization with bandit feedback.", "other_strengths_and_weaknesses": "The strength of this work lies in being the first to propose an optimal and parameter-free algorithm for the non-stationary infinite many-armed multi-armed bandit (MAB) setting. However, the weakness, in my opinion, is the insufficient discussion on how it distinguishes itself from prior work. For instance, both the black-box technique and the most significant arm identification method have been explored before. The paper fails to provide a clear explanation of the specific technical contributions of this work beyond these existing components.", "other_comments_or_suggestions": "1. The abstract does not meet the submission requirements. According to the ICML submission guidelines, abstracts must be written as a single paragraph. However, the abstract in this paper is divided into three paragraphs.\n\n2. The paper proposes multiple algorithms and derives several regret bounds. I recommend that the authors include a table in the introduction section to summarize the algorithms and their corresponding regret bounds and compare them with the previous results. This would make it easier to understand the contributions of this work.", "questions_for_authors": "My question, as mentioned above, is specifically about understanding what the incremental part of this work is compared to existing research. For example, how exactly was the black-box technique adapted to make it suitable for the infinite-arm setting? Could the authors elaborate on the specific modifications or innovations introduced to achieve this adaptation? This would help clarify the unique technical contributions of this work.", "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:

Meta-review: This submission, pertaining to infinite-armed reservoir bandits with non-stationary distribution shifts, has received three reviews, with final scores in the borderline-to-positive region. 

The referees initially raised concerns related to attribution of certain algorithmic ideas to prior work, connections to the rotting bandits literature, alternative algorithmic approaches based on subsampling, comparisons with the previously known blackbox-MASTER algorithm for non-stationary finite-armed bandits. The authors have provided detailed and adequate responses clarifying the connection to previous work, the inadequacy of pure-subsampling based approaches, and contrast with the MASTER algorithm. 

In particular, two reviewers (T9xW and 8A6S) raised concerns about the comparison with MASTER, but the authors have later clarified satisfactory and in detail that their algorithm is different from MASTER on several counts, including a simpler structure avoiding multi-scale scheduling of subroutines.

While some concerns, including the lack of more specific structural analyses in terms of the rising / rotting profile of the non-stationarity, persist in the final stage, I am inclined to believe that this paper introduces new and useful ideas, both from an algorithmic and analytical perspective, to the domain of infinite-armed non-stationary bandits. In view of this, I recommend acceptance of the paper.
Decision: Accept (poster)