Tightening Regret Lower and Upper Bounds in Restless Rising Bandits
Authors: Cristiano Migali
Marco Mussi
Gianmarco Genalti
Alberto Maria Metelli
Venue: NeurIPS 2025 poster ()
Keywords: Restless Bandits
Rising Bandits
Regret
Lower Bounds
Primary area: theory

Abstract: *Restless* Multi-Armed Bandits (MABs) are a general framework designed to handle real-world decision-making problems where the expected rewards evolve over time, such as in recommender systems and dynamic pricing. In this work, we investigate from a theoretical standpoint two well-known structured subclasses of restless MABs: the *rising* and the *rising concave* settings, where the expected reward of each arm evolves over time following an unknown *non-decreasing* and a *non-decreasing concave* function, respectively. By providing a novel methodology of independent interest for general restless bandits, we establish new lower bounds on the expected cumulative regret for both settings. In the rising case, we prove a lower bound of order $\Omega(T^{2/3})$, matching known upper bounds for restless bandits; whereas, in the rising concave case, we derive a lower bound of order $\Omega(T^{3/5})$, proving for the first time that this setting is provably more challenging than stationary MABs. Then, we introduce Rising Concave Budgeted Exploration (RC-BE($\alpha$)), a new regret minimization algorithm designed for the rising concave MABs. By devising a novel proof technique, we show that the expected cumulative regret of RC-BE($\alpha$) is in the order of $\widetilde{\mathcal{O}}(T^{7/11})$. These results collectively make a step towards closing the gap in rising concave MABs, positioning them between stationary and general restless bandit settings in terms of statistical complexity.

Tightening Regret Lower and Upper Bounds in Restless Rising Bandits
Cristiano Migali
Marco Mussi
Politecnico di Milano, Milan, Italy cristiano. migamigllill @mail. poliiippplmmii.
Politecnico di Milano, Milan, Italy marco mussi @polimi
Gianmarco Genalti
Alberto Maria Metelli Politecnico di Milano, Milan, Italy albertomaria, wwtelli@pollmiiti......... it
Politecnico di Milano, Milan, Italy gi gianmarco. aamarco.genalti@pol... genalti@polimi..
Abstract
Restless Multi-Arman Bandits (MABs) are a general framework designed handle real-world decision-make -making problems where the expected rewards evolve over time, such as in recommender systems and dynamic pricing. In this work, we investigate from theoretical standpoint two well-known structured subclasses restless MABs: the rising and the rising concave settings, where the expected reward of each arm evolves non-decreasing concave function, respectively. By providing a novel methodology of independent interest for general restless bandits, establish new lower bounds on the expected cumulative regret for both settings. In the rising case, we prove a lower bound of order ((TT2/3), matching known upper bounds for restless bandits; whereas, in the rising concave case, we derive a lower bound of order 3/73/ proving for the first time that this setting is provably more challenging than sta- tionary MABs. Then, we introduce Rising Concave Budgeted Exploration regret minimization algorithm designed for the rising concave MABs. By devising a novel proof technique, we show that the expected cumulative regret of RC-BE(a) is in the order of Ö(T7/11). These results collectively make a step towards closing the gap in rising concave MABs, positioning them between stationary and general restless bandit settings in terms of statistical complexity.
time following unknown non-decreasing and
(RC-BE(C) (C)))
Introduction
Multi-Armed Bandits (MABs, Lattimore and Szepesvári, 2020) well-known framework model decision decision-making problems, where, for each round, an agent chooses (pulls) an action (arm) among a of available actions and observes reward, i.e., numerical feedback which represents the goodness of the choice. In this setting, the goal of the learner is to minimize the expected cumulative regret accumulated during the interaction, i.e., the sum time of the difference between the expected reward of the optimal arm and that of the chosen one. The standard MAB setting considers stationary reward distributions. However, in many real-world ceciiion-makinn problems, the expected rewards of available actions can vary over time due to changes in the surrounding environment, such as shifting in consumer preferences for online marketplaces (Wu et al., 2018) or evolving health status of patients in treatment selection during clinical trials (Aziz et al., 2021). To address such dynamics, the restless MABs framework (Tekin and Liu, 2012) has been introduced. This model generalizes the classical MAB setting by explicitly incorporating the non non-stationarity of the arms.'
With slight abuse of terminology, will use the words non statioaat and restless interchangeably.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Holds for
Result
Restless Rising Concave
Restless Rising
Restless
Lattimore and Szepesvái 2020 (Thm. 15.2)
1(
Lower Bounds
Beshes al. 2014 (Thm. 1)
/
x
Q(T4/))
This work (Thm. 3.2)
/
x
22T - 9((7:35)
This work (Thm. 3.3)
/
/
Q(T1/2) (((7//))
Upper Bounds
Besbes 2014 (Thm. 2)
O(T2a)
Metelli al. 2022 (Thm. 5.3)
x
x
This work (Thm. 4.4)
X x
O (
Table I: Existing and new bounds for the restless, restless rising and restless rising concave settings.
The arrow - points from the previous best result to the improved one presented in this paper.
Non-stationarity in bandit problems has been addressed through a variety of models and methods, such as restless bandits with abrupt changes the reward distribution (e.g., Garivier and Moulines, 2011), 1), smoothly evolving expected rewards (e.g., Trovà et al., 2020), and settings where the total variation of expected rewards is bounded over time (c.g., Besbes et al., 2014). These frameworks allow the expected rewards to fluctuate in complex ways, such as increasing and then decreasing, without constraints on their direction of change. In contrast, there are important classes of bandit models that enforce monotonicity the expected rewards. These include rising bandits (Heidari et al., 2016; Metelli et al., 2022), where expected rewards are non non-decreasing, and rotting bandits (Levine et al., 2017; Seznec al., 2019, 2020), where they non-increasing. Such models well-suited for capturing structured real-workl dynamics, including online model selection (Metelli et al., 2022), hyperparameter optimization (Mussi al., 2024), and recommendation systems (Levine et al., 2017).
Motivation. In this work, we focus on the restless rising bandits and restless rising concave bandits and we aim to characterize them from theoretical standpoint since several fundamental questions remain unresolved. In the general restless bandit setting, where the expected rewards may vary over time with bounded variation over ''' rounds, the minimax regret is known to be lower bounded by ((T2/3) (Besbes et al., 2014).² However, class of non-decreasing (rising) or non-decreasing concave (rising concave) restless bandits yet, making the classical lower bound for stationary bandits, ((T (Lattimore and Szepesvári, 2020, Thm. 15.2), the best available reference, and leaving the following question open.
regret lower bound has been derived for the specific
Question 1: Is possible to conceive regret lower bounds for restless rising and restless rising concave bandits that are strictly larger than the 2(T1/2) bound for stationary bandits?
The currently available algorithms for restless rising bandits are those designed for general restless bandits with bounded variation, which achieve regret upper bound of order OTT2/3) (Besbes et al., 2014). When incorporating concavity, more specific algorithms have been proposed (Metelli et al., 2022), but unfortunately, they fail to improve the regret order. This generates the following question.
Question 2: Is it possible to devise algorithms for restless rising and rising concave bandits whose regret upper bounds are strictly smaller than the (TT233) bound for general restless bandits?
Original Contribution. In this paper, we aim provide an answer to the research questions presented above, making step towards the complete statistical characterization of restless rising and restless rising concave bandits. The contribution summarized as follows:
In Section 3, we provide general recipe for deriving regret lower bounds for restless bandits, which generalizes the construction of Besbes et al. (2014) and is of potential independent interest (Lemma 3.1). We then specialize this construction the cases of rising and rising concave bandits. First, we derive lower bound of order 2/32/33 for rising bandits, showing that this setting shares the same statistical complexity as general restless bandits (Theorem 3.2) and answering negatively
We 22-)) and O(-) highlight the dependence T' in the lower and upper bounds, respectively, omitting constant factors. For upper bounds, also use Ö(-) suppress logarithmic dependencies on I too.

---

to Question 2 for rising bandits. Second, for restless rising concave bandits, we show that the regret is at least of order 12(T5/5), showing that this setting is more challenging than stationary MABs (Theorem 3.3). These results provide a positive answer Question for both settings. In Section 4, we present Rising Concave Budgeted Exploration (RC-BE(a)), a novel regret minimization algorithm for restless rising concave MABs, which extends Budgeted Exploration (Jia et al., 2023). By devising a novel analysis, we provide an upper bound on its regret of order ((TT/L)) (Theorem 4.4) with requested knowledge of the learning horizon or of the total variation. This result improves upon the current best upper bound order O(T2/5) and provides a positive answer to Question 2 for rising concave bandits.
Numerical simulations are provided in Section 5. Related works are discussed in Appendix A. Omitted proofs are provided in Appendices B and C for lower and upper bounds, respectively. A summary of known and new results presented in this paper is provided in Table 1.
2 Setting
restless K-armed MAB (Tekin and Liu, 2012; Lattimore and Szepesvári, 2020) is defined as a vector of probability distributions v [<] where v4 2 A (IR). Let T e N₂1 be the learning horizon, at each round e [T]. the agent selects an arm I, [K] and observes reward R. Xr,, where X;, ~ vi(1) for all [ L N31- We denote the random table with all possible rewards as X (X For every arm E [K]] we define its expected reward 14: N31 - R as the expectation of the reward obtained by pulling such arm, i.e., (t) = Ex (x-,(()) [X] and denote the vector of expected reward functions as (14) (14)=E(K) We assume that the expected rewards are bounded in [0. 1]. and that the realizations are o-subgaussian..
Rising Bandits. We revise the rising bandits notion, i.e., MABs with non-decreasing expected rewards (Heidari et al., 2016). Such a property is captured by the following assumption.
Assumption 2.1 Moon-Decreasing expected reward). Let v be a restless MAB. For every arm E [K] and round t E N1,, the function (t(t) is non-decreasing in t. In particular, defining the increments:
(t) = +) (t) > 0.
We introduce a further assumption on the concavity of the expected rewards (Heidari et al., 2016).
Assumption 2.2 (Concave expected reward). Let be a restless MAB, For every arm i [K] and round E 111, the function (t((t) is concave in t, i.e.:
(t + 1) (t) < O.
Formally, we call restless rising a restless MAB in which Assumption 2.1 holds, and restless rising concave a restless MAB in which both Assumptions 2.1 and 2.2 hold. From now on, we omit the adjective restless for the sake of conciseness.
Learning Problem. Let N₃1 be round, we denote with He (Jz, Ri) the history of observations up to l. A (non-stationary deterministic) policy is a function π : I mapping a history to an arm, that is abbreviated as T(t)= == T(H-11). We define the performance of a policy i in restless MAB as the expected cumulative reward collected over the I rounds, formally:
JT E
Σ (0)
policy N is optimal it maximizes the expected cumulative reward: ~ E arg [ T))- In restless MABs, the optimal policy does not explicitly depend on T and consists of pulling in each round the arm with the highest expected reward: (t()) E arg max (t( for every e N
Denoting with (T) = Ju (n T) the expected cumulative reward of an optimal policy, the suboptimal policies are evaluated via the expected cumulative regret:
RT T) == J (T) Ju( T).
(1)
'Let b E Nz1. b a, denote with [a, bl := {a ....b). probability measures over the measurable set XX.
b). with [a] == [1, aI. and with A(Y) the set of
'A random variable X is subgauussinn if Ele ([XXI) &
o2x² for every X e H.
3

---

Instances Characterization. To characterize an instance v, we introduce the following quantity, namely the cumulative increment, defined for every 8,,82 22 E N31 with & $ t2 as:
(2)
max (I). [||
The cumulative increment extends to an arbitrary interval with & and t2 as extremes the analogous notion (T. q) employed in (Metelli et al., 2022), restricting to q 1. It is immediate to show that (t1, 12) e [0, K] since (t, 12) & Ei Eie[K] (I))) & EmE[K]
K. Analogously to what done (Besbes et al., 2014), we consider the class of instances whose cumulative increment over the learning horizon T' is bounded by variation budger Vr (0, K], which we assume known, formally (1, & VT. Then, we call, respectively, & (T, V/) and (T, VT) the set of rising MABs and rising concave MABs instances, with o-subgaussian rewards, whose T2 (1, satisfies the previous inequality.
Lower Bounds
In this section, we analyze the statistical complexity of the learning problem in both the rising and rising concave settings. To this end, we provide a regret lower bound suffered by any deterministic policy æ on a class of instances which are rising and rising concave, respectively. In particular, we show that rising MABs are not easier than restless MABs with bounded variation (Besbes et al., 2014, Thm. 1) and that rising concave MABs are harder than stationary MABs (Lattimore and Szepesvári, 2020, Thm. 15.2). The analysis is carried out as follows. We develop general recipe for regret lower bound construction on richer class of restless MABs, described Section 3.1. Then we specialize it to both the settings of interest (Sections 3.2 and 3.3).
3.1 General Recipe for the Lower Bound
We consider class of restless MABs with the following structure. The set of rounds N311 split into windows. Let (Aw)) where An E N31 be a sequence of window widths. A window consists of a of rounds [5 ewd c Na where sw == > A + 1 and ew You A,, for Na1- For each window index w E N1 we define two functions FT Pu: [ - [0, IJ. which we call base and modified trend respectively, that describe how the expected rewards of the arms evolve in [ss, ew] In particular, in each window, at most one arm among the K has expected reward that follows the modified trend, while all the others have expected rewards that follow the base trend. The arm whose expected reward follows the modified trend can change between windows. We further enforce (t,. & (t) for all w E N31, / [Aw]]. 6 so that the arm whose expected reward follows the modified trend is the optimal one. More formally, let wi(t) := min(w E N₂1 s.t. 6w 3 8} be the index of the window which contains the round e 231- For each sequence o (Ow)weN,, with
Owr E [0, K] in each window of index w and for each subgaussian parameter > 1, we define an instance v = (Vo,)) as follows:
(t) = (b (t- Sw(() + 1),
if # ow((t)
(2)
( sw()) + o),
if i = Ow(()
where (M,, o) is arobbability distribution with parameters μ E [0. 1], o > 1 such if (H,,)), then:
w.p. 1 + 20
0 J0 w.p. 1/4 1/2
First of all observe that μ [0. o > imply p/(2a) E [0. 1/2). so that the distribution is well- defined. Furthermore, if X Vi(,, o), then, in virtue of Hoeffding lemma, X is o-subgaussian, and, by direct calculation, it has expected value equal to μ. Notice that, if ow 0, all the arms follow the
*Since considering stochastic bandits, our lower bounds be generalized stochastic policies. yielding analogous results, at the cost of additional notational complexity.
"We consider pr (t) and (t) both in the domain e [А.]]] instead of in the domain [[s.,, ew] for the sake of simplicity in the notation, every window is defined independently from the others.

---

base trend, otherwise, ow corresponds to the only arm following the modified trend. We denote with ę we and ft (P. weeNN the sequences of base and modified trends respectively. and with ET. [Vo s.t. o [[o, K] x7 the class of instances that they induce by varying the sequence of optimal arms in each window. The following result, whose proof is deferred to Appendix B, holds.
Lemma 3.1 (General Lower Bound), Under the assumption that Th (t) & (t) for all w Nat. t e [A for any deterministic policy subgaussian parameter 3 1, and learning horizon
Te Næ1. it holds that:
w(T)
(n(2) D PA.To
sup (T, T)
1
A.....
wEE miB
2K
where:
min(ew TT Σ
D
(KL(v(Pm(tt- sw + 1), (). sw +))00))
minfew.Ty
AF..TTT
Σ
(Rull - 8w + 1) 1w (1- 8m + 1));
for all [w(TT); with DKL(-I-) being the Kullback-Leibee divergence of the two distributions (formally defined in Appendix B).
This result highlights the trade-off in designing "challenging" restless instance. On the hand, we do not want to make the base and modified trends too far apart, otherwise would be easy for the agent discern one from the other. This is reflected in Equation (3), the term D. increases when the two trends diverge and contributes to reducing the regret lower bound since AT.U. is non-negative by construction. On the other hand, want maximize the area AF.R. between the two trends. In this way, under the assumption that DE.AT is small enough so that the factor that multiplies AF. is non-negative, we increase the regret lower bound.
3.2 Specializing the Lower Bound for the Rising Setting
In this part, apply Lemma 3.1 to provide regret lower bound for the class E,7 (T, VT), holding for any deterministic policy æ. To this end, we construct sequences of window widths (A, A and of base and modified trends Ft. f4, such that &o R. S E (T, VT). A representation of the structure of the instances is depicted in Figure We choose windows of the same width. In each window, the base and modified trend are both constant, the latter is greater than the former by a quantity e, O and the value of the modified trend in a window corresponds to the value of the base trend in the next window. In this way, we guarantee that the instances are rising no matter which arm follows the modified trend. Appendix B, we formalize the instances and we prove that the following holds.
Theorem 3.2 (Lower Bound for the Rising Setting). For any deterministic policy subgaussian parameter a > 1, and learning horizon T e N T R [min(1, Vr) -2, it holds that:
1 Jir K3 min ViJ}a
sup (T.VV
(T,
>
64
The orders of growth for T, K, and V in this result match the upper bound for the general restless case with bounded variation (Besbes al., 2014, Thm. 2) when VT & 1.7 This implies that rising MABs are not easier than general restless MABs with bounded variation despite the additional assumption. Thus, the characterization of the statistical complexity of this setting is completed.
3.3 Specializing the Lower Bound for the Rising Concave Setting
In this part, we provide a regret lower bound for the class Eg (T, Viy) holding for any deterministic policy In analogy to Section 3.2 for the rising setting, we construct sequences of window widths
We believe this is an artifact of the analysis since, in the lower bound construction, have T(1 L.
5

---

Pep
m22 w
Pr,w
m2
Pr,w
To.
Ac
Figure 1: Base (dashed) and modified (solid) trends of the lower bound instances for the rising setting.
Figure Base (dashed) and modified (solid) trends of the lower bound instances for the rising concave setting.
(Ac,w)weN: and of base and modified trends Fhe Pe such that &0 of the instances depicted in Figure 2. We choose again windows the same width. each window, the base and modified trends share the same starting and ending values. Furthermore, the end value of expected rewards in a window matches the start value of expected rewards in the next window. The end value is greater than the start value to guarantee that the instances are rising. The base trend joins the two endpoints of the expected rewards each window with a single segment, while the modified trend uses two segments. At the beginning, it rises with slope greater than that of the base trend until half the window. At this point, the distance between the base and the modified trend the window is maximum. Then, the modified trend keeps rising, but with slope that is smaller than that of the base trend, until the two trends meet at the end of the window. The pattern repeats and the slopes chosen in such way that the slope of the second part of the modified trend in window (which is the smallest slope in a window) corresponds to the slope the first part of the modified trend in the next window (which is the greatest slope of expected reward in window). In this way, we guarantee that the instances are rising and concave, no matter the choice of which arm follows the modified trend. In Appendix B, formally present the instances and prove the following result.
P...A. S (T, VT). representation
Theorem 3.3 (Lower Bound for the Rising Concave Setting). For any deterministic policy pallic holds subgaussian parameter a z 1, and learning horizon T E N21, T 3 2 02 K min(1, Vr -2, holds that:
RT 2 1 K min V
sup v
This result proves that regret minimization in rising concave MABs represents harder learning problem w.r.t. stationary MABs which are characterized by the usual 1/T lower bound.
4 Upper Bound for the Rising Concave Setting
In this section, we present novel regret minimization algorithm, Rising Concave Budgeted Exploration (RC-BE(a)), designed for rising concave MABs (Algorithm 1), and analyze its perfor- mance by providing an upper bound of the expected cumulative regret suffered on generic instance E (T, Vr). We show that this upper bound attains a strictly smaller rate w.r.t. the lower bound on the expected cumulative regret generic restless MAB with bounded variation (Besbes et al., 2014), and thus that rising concave MABs are indeed an easier setting w.r.f. them.
Algorithm. RC-BE(a) is an improvement of the Budgeted Exploration (BE) algorithm (Jia et al., 2023),, originally designed for 2-armed general restless bandits." The original algorithm works as follows. The learning horizon T is split in windows of A E N₂ rounds each. In each window, the algorithm restarts. the beginning of each window, the agent carries out an exploration phase which consists of several round-robin cycles. In particular, the agent keeps track of the arms alive in
'The extension of BE to K K-armed bandits is proposed in the unpublished preprint (Jia et al., 2024) for the case of smooth MABs. However, we have found soundness issues in the analysis proposed there (see Appendix F). For this reason, will develop independent analysis which overcomes these issues.

---

Algorithm RC-BB(()).
I: Input: a 1, N222
2: Initialize <- d e 1, A [K] B A. S. 0, ViE
3: for t e [T] do
4: if d A 1 +1 then
5: Increment
6: Reset - 1, A [K], B - A. S - 0, 0.vie
7:
end if
8:
Pull I E B
Remove B B ((11
Observe R₂ XIn
11:
Update St. -S, Rs
12:
B O then
13:
Compute S* maxia St for E [K] do
14:
15:
if A and S; B(a)) Remove A Ab(1)
S* then
16:
17:
end 18: end for
19: Reset B A
20:
end if
21:
Increment d - d + 1
22:
end for
the current window in a set = [K], initialized [K] at the beginning of each window, and, in each round-robin cycle, pulls each of these arms once. The agent cumulates the observed rewards for each arm in the variables S with i E [K]] At the end of each round-robin cycle, the agent compares the cumulative reward of each alive arm with the maximum cumulative reward among alive arms S* := m S, If for i E A we have S + B S*, where B > is parameter of the algorithm, say that arm has out of budget and the agent removes it from the set of alive arms. It can happen that, after several round-robin cycles, the set of alive arms becomes singleton: A = (i*). J. In this case, no more eliminations can happen and the agent will commit the remaining arm i*
RC-BE(a) extends the original algorithm as follows. It exploits the concavity of the instance through increasing window widths (aa)
|w*|| and corresponding budgets B = 2(1 + ( In(2K A (122)()))) 12/) The rationale is the following. The algorithm suffers a high regret in windows during which the optimal arm changes. Indeed, in windows where change happens, the algorithm is likely to commit to the best arm, suffering no regret after the initial exploration phase. Conversely, in windows where the optimal arm changes, the algorithm could commit to an arm that then becomes suboptimal, or could fail in estimating the optimal arm. In this case, the regret increases with the distance the expected rewards of i* and the actual optimal arm in round t: it E arg [ (t). Thanks to the concavity, the maximum increment max [K] (t()) decreases as t increases. Thus. time passes, if the optimal arm changes, it takes longer for the restart the algorithm with
expected rewards of 8* and iž to diverge significantly. Hence, lower frequency, which equivalent to having windows with increasing width.
Regret Analysis. RC-BE(a) partitions the set of rounds Na1 in windows [[((]] (()) with sw DE A(a) (a) and ((a) Σn A A(a), for w N31. Let ()() min(w N31 s.t. 6er (a) t) be the index of the window that contains the round f. E N Thus, the learning horizon is split in
(TT windows. In what follows, we bound the regret suffered by RC-BE(a) on the set of windows W which enjoy certain properties that we introduce later. To this end, we denote the regret suffered by a policy π on a set of windows W = Na1, [W] < 00 as:
(
Ro W) ==
Σ
(1)(1)) - [1x(1)-m,100)
X Kap
7

---

Now, we present the properties which induce the classes of windows of interest for the analysis. In particular, we need formally characterize the fact that, in a window, the optimal arm can change. To this end, we introduce the following definitions, in analogy to what is done in (Jia et al., 2024).
Definition 4.1 (Overtaking). An arm E [K] overtakes an arm j E [K] at time L E N32 if pi(t- 1) < pt 1) and pu(t) 2 py(t). Formally, we write 1 (note that te i). Definition 4.2 (Crossing). Two arms i.j [K] cross at time t E N82 if ta J or j 1e Formally, we write i x (note that x i).
We introduce a binary relation for arms that cross in the w-th window. For w N31, i,j [K]]
i xj iff i x for some e [s + 1, I.
Let x be the transitive closure of x, x is an equivalence relation since x is reflexive and symmetric. For an arm e [K], we denote with [i] x its equivalence class w.r.t. x x- Let:
I = {i [K] s.t. there exists t ( e with arg ja P. [tz()).
be the set of optimal arms in window w. Furthermore, we define I := [ for some in I Observe that the definition is well posed since, in virtue of Lemma C.2, it does not depend on the choice of w For w E N i [K]. we define the diameter of its equivalence class w.r.t. w x as
de
max TE (0) (0
(M₂(t) (x)
j.keli
We use the shorthand d for d.p (i)) where thh I The following lemma decomposes the regret suffered by RC-BE(a) during the w-th window as the sum of the regret due to the exploration phase plus the regret due the commitment phase.
Lemma 4.1. For all restless rising concave MABs v, a 2 1, W, W. E No1 we have that:
(RC- (RC-BE (RC-BB(A)), (w]) 3KB
d
Exploration
Commirment
Thus, the regret due to exploration is proportional to the budget B( while the regret suffered during the commitment phase depends on the width of the window A (a) and on the diameter d of T In windows where the optimal arm does not change, I% is singleton and, thus, its diameter is 0. This reflects the fact that, such windows, the algorithm suffers only the regret due to the exploration.
We now provide an upper bound for (i) with w E N i E [K] which exploits concavity.
Lemma 4.2. For all restless rising concave MABs v. a e 1, w E Na1. i [K] we have that:
(i)( < 8(1 + a)) (11).x--11) - (1, ((a)) & 16aK (T (1)
Recall that (1, elo)) is upper bounded by K. Thus, as expected, eventually the upper bound of the diameter decreases as w increases. This reflects what we informally stated before. As time goes, due to the concavity, it takes more time for the expected rewards of arms which have crossed to diverge significantly. Thus, it makes sense to increase the width of the windows over time.
We now discriminate between two kinds of windows: those in which the expected rewards of arms which cross (and thus of the arms which belong I do not diverge significantly and those in which, instead, the converse happens. More formally, let d E K]:
(Td(T) == {w [win) (T'I S.A. d (1) < d for all [K]].
W>a(T) = {w ww (T)) s.t. (i) > d for some i [K]]-
In the second class of windows, we have no upper bound to the diameter d other than that of Lemma 4.2, which considers a worst-case scenario in which the divergence of the expected rewards of the arms which cross is the maximum possible. We now show that this scenario, in the rising concave setting, can happen only a limited number of times. In particular, this is translated into an upper bound to the number of windows in W>a(T', which is captured by the following lemma.
8

---

Lemma 4.3. For all restless rising concave MABs a TE Nę1. de (0, K] we have that:
[W>a(T) & 9
3e (Ty) k/d) kdd
Informally, this lemma states that, in the rising concave setting, it cannot happen in too many windows that the expected rewards of arms which cross diverge significantly (i.e., more than d).
We use this fact to conclude the analysis. In particular, observe that we can always upper bound the regret suffered on set of windows W as (T, W) & [W] maxwew Rp(T, (w]). We use this to upper bound the regret suffered on both (T) and Wza(T). In the first case, we ob- serve that [T) & w/(a) (T) and use the definition of Wga(T) together with Lemma 4. I to bound max (RC-BEE((C) [w)). In the second case, we use Lemma 4.3 to upper bound [T> and Lemma 4. together with Lemma 4.2 to deal with max (RCCCBE(()) (w}).
These observations lead to the following result which is formally proven Appendix C.
Theorem 4.4 (Upper Bound for the Rising Concave Setting). For all restless rising concave MABs T' E Na24, we have that:
V, Q >
Rw (RCC-B((O))) & 2 (In (aKTT)) (a (1+ 3i4 +
5/4o-1 1ea
(1(,TT)
14/2 + {1+
In particular, for a' = 88/3, we get:
= =6 =o(oK Ry(RC-BE(a),,T +
+oKTH).
Furthermore, for
K2Vz 1+0
a" 8 4logr
3 4logr
K²V2 1+a
under the additional assumptions 0Φ (T, VT).
(1 o1+13/18K
8/3 8/3 4/3
+1
T = max
[1 -8/5
8/5 K 16/5 y
8/3
we get:
Ro (R(RC-BE(a"))T)=
(ot))) H
+ t
By looking at the algorithm and Theorem 4.4, observe how by selecting 8/3, we achieve a regret of order Ö(T7/1)) without the knowledge of either the total variation Vr or the learning horizon T, making it an anytime algorithm, at the price of worse dependence on K and Vr. This result shows that the regret minimization problem in rising concave MABs is indeed easier w.r.t. general restless MABs with bounded variation (Beshes et al., 2014) and rising MABs. Indeed, the regret O in upper bound is smaller than that of the lower bound for restless MABs with bounded variation (Besbes al., 2014, Theorem 1) and rising MABs (Theorem 3.2), i.e., 2(T2/3).
5 Numerical Simulations
In this section, we present the results of numerical simulation of (EC-BE(44 a compared to state-of-the- art algorithms for restless, restless rising concave, and stationary MABs."
Baselines. We consider the bascline algorithms: Rexp3 (Besbes et al., 2014), an algorithm for restless MABs based on variation budget; R-less- UCB (Metelli et al., 2022), algorithm for restless rising concave MABs; and UCB1 (Auer et al., 2002a; Bubeck, 2010), one of the most effective
Additional simulations are reported in Appendix E. The code to reproduce the results is available at https://github www.///gwiiggg////bl/hpaaaaaaaae eep.raaeexxepiimmtte.eee

---

-109
RC- RC-BE(a)
Expected Reward
0.8
Cunuulative Regret
Rexp3
R-less-UGe
0.6
UCB1
0.4
0.2
0
0
0
2
3
4
5
0
2
3
4
Rounds
-10%
Rounds
-10
(a) Expected rewards.
(b) Cumulative regret (10 runs, mcan + 95% C.I.)
Figure 3: Instance and results of the experimental validation.
algorithms for stationary MABs. The choices of the parameters of the algorithms are reported in Appendix E.
Setting. The algorithms are evaluated for 7 = 5 10 rounds on synthetic instances with K 5 arms. The stochasticity is realized by adding Gaussian noise with standard deviation 0.1. The curves of the expected rewards have the functional form f(t) = c(1 exp(-sat/[l for t E [T]] where a, e (0, 1]. s 50, and are reported Figure 3a. We compare the algorithms in terms of empirical cumulative regret (T,,
(T, t) which the empirical counterpart of the expected cumulative regret (T,, f) at round averaged over multiple independent runs. In each simulation, the parameter a of (C-BB(()) is set to a 8/3, as suggested by Theorem 4.4.
The empirical cumulative regret suffered by the algorithms is shown in Figure 3b. We observe that RC-BE((:) is the algorithm that achieves the lowest regret at the horizon. UCB1 has the lowest regret in the first rounds, afterwards its regret starts increasing when the optimal arm changes. This is consistent with the fact that we are violating the stationarity assumption on which the algorithm relies. Rexp3 is an algorithm which restarts at a fixed frequency. In particular, the number of restarts has order 71/3, Thus, in this simulation, there are R 10 restarts, and, by looking at the figure, is not possible to appreciate the behavior of the algorithm between one restart and the next. For this reason, Rexp3 shows cumulative regret which increases linearly. This is consistent with the fact that the algorithm not anytime. A-less-UCB, consistently with its theoretical guarantces, shows sublinear growth of the cumulative regret. Its estimator relies rested model of the evolution the expected rewards of the arms, penalizing the empirical performance.
Results.
Discussion and Conclusions
In this paper, studied the restless rising and rising concave MABs, where the expected rewards of the arms are non-decreasing and non-decreasing concave in the number of played rounds, respectively, We derived lower bounds to the expected cumulative regret in both settings. The lower bound in the rising setting has order 2/T2233) and implies that the non-decreasing expected reward assumption does not simplify the learning problem w.r.t. the general restless setting with bounded variation, and that all the algorithms which optimal for the general setting optimal also in this special subclass, closing in this way the gap present in the literature. Thus, for the rising setting, we provided positive answer our Question and negative answer to our Question 2. The lower bound in the rising concave setting has order (/T3555 and implies that rising concave MABs represent statistically harder problem w.r.t. stationary MABs. After having presented two statistical barriers for these settings, developed learning algorithm with the goal of exploiting the structured model rising concave MABs. To this end, we designed RC-BE(a), and we derived an upper bound to its expected regret of order Ö(T7/11). This result implies that the non-decreasing expected reward assumption, together with the concave expected reward assumption, simplifies the learning problem w.r.t. the same setting without concavity. Thus, for the rising concave setting, provided a positive answer for both Question and Question 2. The natural future research direction includes closing the gap in rising concave MABs which is now only 7/11 3/5 2/55 in the exponent of T'.
10

---

Acknowledgments
Funded by the European Union Next Generation EU within the project NRPP M4C2, Investment 1.3 DD. 341 - 15 March 2022 FAIR- Future Artificial Intelligence Research Spoke 4 PE00000013
-D$3C22003380066.
References
Tor Lattimore and Csaba Szepesvári. Bandit Algorithms. Cambridge University Press, 2020.
Qingyun Wu, Naveen Iyer, and Hongning Wang. Learning contextual bandits in a non-stationary environment. In International Conference on Research & Development in Information Retrieval (SIGIR), pages 495-504, ACM, 2018.
Maryam Aziz, Emilie Kaufmann, and Marie-Karelle Riviere. On multi-armed bandit designs for dose-finding trials. Journal of Machine Learning Research, 22(14) 22(14):1-38, 2021.
Cem Tekin and Mingyan Liu. Online learning of rested and restless bandits. IEEE Transactions Information Theory, 58(8):5588-5555 1611,,2111211 2012.
Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In Algorithmic Learning Theory (ALT), pages 174-188. Springer Berlin Heidelberg, 2011.
Francesco Trovò, Stefano Paladino, Marcello Restelli, and Nicola Gatti. Sliding-window thompson sampling for non-stationary settings. Journal of Artificial Intelligence Research, 68:311-364, 2020.
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed-banine problem with non- stationary rewards. In Advances Neural Information Processing Systems (NIPS), page 107-207. MIT Press, 2014.
Hoda Heidari. Michael Kearns, and Aaron Roth. Tight policy regret bounds for improving and decaying bandits. In International Joint Conference on Artificial Intelligence (IJCAI), 2016.
Alberto M. Metelli, Francesco Trovò, Matteo Pirola, and Marcello Restelli. Stochastic rising bandits. In Proceedings of the International Conference on Machine Learning (ICML), volume 162 of Proceedingg of Machine Learning Research, pages 15421-15457. PMLR, 2022.
Nir Levine, Koby Crammer, and Shie Mannor. Rotting bandits. In Advances in Neural Information Processing Systems (NIPS), pages 3074-3083, 2017.
Julien Seznec, Andrea Locatelli, Alexandra Carpentier, Alessandro Lazaric, and Michal Valko. Rotting bandits are no harder than stochastic ones. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 89 of Proceedings of Machine Learning Research, pages 2564-2572. PMLR, 2019.
Julien Seznec, Pierre Ménard, Alessandro Lazaric, and Michal Valko. A single algorithm for both restless and rested rotting bandits. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 108 of Proceedings of Machine Learning Research, PMLR, 2020.
pages
Marco Mussi, Alessandro Montenegro, Francesco Trovà, Marcello Restelli, and Alberto M. Metelli. Best arm identification for stochastic rising bandits. In Proceedings of the International Conference on Machine Learning (ICML), volume 235 of Proceedings of Machine Learning Research, pages 36953-36989, PMLR, 2024.
Su Jia, Qian Xie, Nathan Kallus, and Peter I. Frazier. Smooth non-stationary bandits. In Proceedings of the International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pages 14930- 49330-14944, PMLR, 2023.
Su Jia, Qian Xie, Nathan Kallus, and Peter Frazier. Smooth non-stationary bandits. CoRR, abs/2301. 12366, 2024.

---

Peter Auer, Nicolo problem. Machine learning, 47:235 256, 2002a.
and Paul Fischer. Finite-time analysis of the multiarmed bandit
Sébastien Bubeck. Bandits games and clustering foundations. PhD thesis, Université des Sciences et Technologie de Lille-Lille I, 2010.
Siwei Wang, Longbo Huang, and John C. S. Lui. Restless-ucb, an efficient and low-complexity algorithm for online restless bandits. In Advances in Neural Information Processing Systems (NeurlPS), volume 33, pages 11878- 1889. Curran Associates, Inc., 2020.
Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Proceedings of the Anmual Conference on Learning Theory (COLT), volume 99 of Proceedings of Machine Learning Research, pages 138-158. PMLR, 2019.
Fang Liu, Joohyun Lee, and Ness Shroff. A change-detection based framework for piecewise- stationary nulti-armed bandit problem. Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Lilian Besson, Emilie Kaufmann, Odalric- Maillard, and Julien Seznec. Efficient change- point detection for tackling
bandits. Journal of Machine Learning Research,
23(77): 2022.
Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xie. Nearly optimal adaptive procedure with change detection for piecewise-stationary bandit. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), pages 418-427. PMLR, 2019.
Lilian Besson and Emilie Kaufmann. What doubling tricks can and can't do for
bandits.
CoRR, abs/1 803.06971, 2018
Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund, and Robert E. Schapire. The nonstochastic multiarmed bandit problem. SIAM Journal on Computing, 32(1):48-77, 2002b.
Yifang Chen, Chung- Wei Lee, Haipeng Luo, and Chen-Y Yu Wei. A new algorithm for non-stationary contextual bandits: Efficient, optimal and parameter-fire. In Proceedings of the Annual Conference on Learning Theory (COLT), volume 99 of Proceedings of Machine Learning Research, pages 696-726. PMLR, 2019.
Yang Li, Jiawei Jiang, Jinyang Gao, Yingxia Shao, Ce Zhang, and Bin Cui. Efficient automatic cash via rising bandits. In AAAI Conference on Artificial Intelligence, pages 4763-4771, 2020.
Leonardo Cella, Massimiliano Pontil, and Claudio Gentile. Best model identification: A rested bandit formulation. Proceedings of the International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 1362-1372. PMLR, 2021.
Sho Takemori, Yuhei Umeda, and Aditya Gopalan. Model-based best arm identification for decreasing bandits. In Proceedings of the International Conference on Artificial Intelligence and Statistics (AISTATS), volume 238 of Proceedings of Machine Learning Research, pages 1567-1575 PMLR, 2024.
Gianmarco Genalti, Marco Mussi, Nicola Gatti, Marcello Restelli, Matteo Castiglioni, and Alberto M. Metelli. Graph-triggered rising bandits. In Proceedings the International Conference on Machine Learning (ICML), volume 235 of Proceedings of Machine Learning Research, pages 15351-15380. PMLR, 2024a.
Gianmarco Genalti, Marco Mussi, Nicola Gatti, Marcello Restelli, Matteo Castiglioni, and Alberto M. Metelli. Bridging rested and restless bandits with graph-triggering: Rising and rotting. CoRR, abs/2409.05980, 2024b.
Achim Klenke. Probability Theory: A Comprehensive Course. Universitext. Springer, 3 edition, 2020.
Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (2nd Edition). Wiley, 2006.
12

---

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

---

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

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
The code is made available in the supplemental material, All the simulations are on synthetic instances, thus no external data is needed.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.ce
httpesumiissiiooooosiooeee colllycy) for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / /ttpps.ccpppliiiiim wwtppccppcc////ccccccccccccccclt htppllc/ggiieee http//uudieeeeeeee https//ooSSSuuiiseeeeeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The parameters of all the compared algorithms are explicitly listed Ap- pendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We report 95% confidence intervals on the cumulative regret curves used to compare the algorithms.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The information is provided Section E.2.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics attps://neuripe
Answer:
[Yes]
Justification: The paper is coherent with NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode. thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.MM policy (https: https///eeuiissppeee caarrripssccccoofffeeeeeee/////s for what should or should not be described.
19

---

A Related Works
Restless Bandits. In the original restless MAB setting, introduced by Tekin and Liu (2012), the evolution of the expected reward of each arm was described by a Markov chain. Several algorithms have been proposed to deal with this new framework, e.g., Restless-UG -UBB (Wang et al.,, 2020), which relies on the optimistic estimation of the transition kernel of the underlying chain. Over time, the term restless acquired broader meaning, encompassing all bandits in which the expected reward changes as time passes. Such arbitrary evolution can be described by a function that maps each round to the expected reward of given arm. This is the type of restless bandit we target in this work. There are two families of methods to tackle restless MABs: passive (e.g.. Garivier and Moulines. 2011; Besbes et al., 2014; Auer al., 2019; Trovò al., 2020) and active (e.g., Liu et al.. 2018: Besson et al., 2022; Cao et al., 2019). Passive methods base their estimates on the recent feedback, forgetting obsolete observations. Active methods try to detect the changes in arms' expected rewards and use only the observations gathered after the last change. Among the most common passive approaches we find methods based on discounted rewards, e-g., D-UCB (Garivier and Moulines, 201 1), or adaptive sliding window, e.g., SW-UCH (Garivier and Moulines, 2011). Both algorithms suffer a ((7) regret in the setting in which expected rewards change abruptly fixed number of times over the time horizon, and such number is known. Auer et al. (2019) obtained a similar result in the same setting, without knowing the number of changes, by resorting on the doubling trick (Besson and Kaufmann, 2018). Another common setting is the one that allows the expected rewards to evolve arbitrarily, with the only constraint that the maximum absolute difference between the expected rewards of an arm in one round and the next, summed over the time horizon, is smaller than or equal to a variation budget VT (Besbes al., 2014). The Rexp3 algorithm (Besbes et al., 2014), a modification of the Exp3 (Auer et al., 2002b) policy, originally designed for adversarial MABs, shows regret bound of (TT23) under the knowledge of the variation budget Vy. The need for the knowledge of such quantity has been removed by Chen et al. (2019) by means of the doubling trick. In (Trovà et al., 2020), an approach which combines a Thompson-Sar Saampsoo-Sampling-iiii algorithm with a sliding window, shows theoretical guarantees in both the abruptly and smoothly changing settings.
Rising Bandits. Rising concave MABs have been introduced in the deterministic setting by Heidari et al. (2016) and Li et al. (2020), where the rewards observed by the agent in each round are not affected by noise. In their formulation of the problem, the rewards of an arm are non-decreasing in the number of times such an arm has been pulled and satisfy the decreasing marginal return assumption, i.e., the increment in the reward observed between one pull and the next of the same arm is non-increasing in the number of pulls. The online algorithm designed by Heidari al. (2016) to minimize the regret relies on an optimistic estimate of the cumulative reward that can be obtained by pulling given arm. Indeed, in this setting, Heidari et al. (2016) show that the optimal policy consists of repeatedly pulling the arm with the highest cumulative reward over the horizon. Li et al. (2020) use the rising concave MAB framework model the problem of parameter optimization in machine learning and design an algorithm based on iterative elimination of unpromising arms that has good empirical performance. Cella al. (2021) consider a setting in which the reward is increasing in expectation and the observations are affected by noise. However, in their framework, the expected rewards are constrained to follow specific parametric form known to the agent. The authors analyze the setting under both the regret minimization and best arm identification frameworks. Anyway, the given parametric form makes this setting not applicable to an arbitrary expected reward evolution that satisfies the non-decreasing assumption. Recently, a surge of approaches has been designed for addressing other learning problems in stochastic rising concave MABs, including regret minimization (e.g.. Metelli et al., 2022) and best arm identification (e.g., Takemori et al., 2024; Mussi et al., 2024). Finally, Genalti et al. (2024a.b) proposes a novel framework that interpolates between rested and restless MABs, still assuming the rising concave condition.
B Lower Bounds
In this appendix, we provide the proofs of the results presented in Section 3 in the main paper.
B.1 General Recipe for the Lower Bound
The goal of this section is to prove Lemma 3.1. Remember that we work with rewards which follow
the distribution vi(, σ)) defined in Section 3.1. The result is obtained through techniques from the
20

---

adversarial literature in which the instance is also affected by randomness. Thus, we define two probability distributions over [0, K] which induce probability distributions over the instances in e ".. In particular, let E. ( K]) defined as:
E(fo)) = 0
if e [K].
i =
1
o [K]]
{((o))
K
o
for e [0, K]. We can extend & and & to probability distributions over [[0, K] via infinite product (see Example 1.63 Klenke 2020):
Tw = 08-1
& (8) 1 5)
for all w E Nş1.
: OweN
7 models a random instance in which, in each window, we choose independently and uniformly one arm whose expected reward follows the modified trend, while the expected rewards of all the other arms follow the base trend. instead models random instance which behaves like up to window N31 (excluded); from window w onward all arms follow the base trend. For technical reasons which will be clear in what follows, we need to build probability space in which the randomness over the instance and the randomness over the rewards are unlinked. Observe that with the current construction this is not the case. Indeed, X is sampled from vg but is also a random element. To this end, let (Bt,))e[]]] JEEN
À [ (eN Unif(0, 1) where Unif(0, 1) is the uniform distribution with support [0, 1]. Then, we can redefine:
(t. 1 2
( 8) = 20 81 <
20
where (t) is defined in analogy to Equation (2). In this way, we moved the dependency from inside the definition of the random variables, preserving their distributions. Indeed, once fixed, we have X (l).,(1),0) o). For consistency with the notation, we introduce the random variables O OwwNeNN where (w
Ow- The probability distributions that we just defined, induce probability density functions over finite reward sequences taking into account the randomness both in the instance and in the rewards. In particular, let
PT)
P
[R1
ri...., Rr rT].
T~
a~
(r PT)
P
R1
Rrr rr O = =t].
8~
for w E No1. E [K]. the conditional and marginal distributions; disambiguation happens through the arguments, e.g.. (u -1)
E (-1/2o, 3/2o]. We use Phe and pur, to denote also all
To obtain the result,
the following tools from information theory (Cover and Thomas, 2006). Definition B.1 (L' Distance Two Discrete Probability Density Functions). Let p. be two discrete probability density functions defined over the finite set X, we define their T,A distance as:
p
411 = Σ [xx))-((z)}
ZEA
Definition B.2 Kullback-Leibler Divergence of Two Discrete Probability Density Functions). Let P.q be two discrete probability density functions defined over the finite set X, we define their Ballback-Leible divergence as:
p(x)
DRt(plg) = Σ p(x) logg
((x))
NEX
By extension, we define:
DKL(V DKL (pv (ps)
where v, are probability distributions with discrete support and Pus Pe are their corresponding discrete probability density functions.
21

---

We now state and prove generalization of Lemma A.1 in (Auer et al., 2002b) which we then use to derive Lemma 3.1. Lemma B.I. Let [w(T]], i [K], f: (-1/2o, 3/2o) mintew.. /mb [0,
with M > 0. Then:
E
[[ Bmin(ew..T). O =i] =]-
E Tm
[S Rmin(ew.:T))
minfew T)
M
In(2)
Σ
DRa(v(Pult - Sw + 1)) sw + 1),
P [4 i). (4)
V2
Proof. To simplify the notation, let 1 Sws l2 == minfews T3. The of Equation (4) can be written as:
Σ
f(r1....,, (F. Tea) P (T
1 El 3/20)
M
(Pu.( Pmo (r.
11 1/203/20)
Pen 7 (12m0)tt))
P (ri....... Tt)) -
(5)
where line (5) can be found in (Chapter 11, Cover and Thomas, 2006). Again, from (Lemma 11.6.1 Cover and Thomas, 2006), have that:
(r............. Pta)) Pr.ilri..... .r.
Pm. rta)).
From the chain rule of entropy:
(P.. (ri,..., .t, Pa (ri....,r(.)) r(,))
(P
ri,...,,
(a)
(ri, (M.......
Because of how F. and 7 are defined, we have that:
-1) and thus term (b) is O because of the properties of (-I(.l.). To deal with term (a) we need to work on the expressions of (r, ri. .t....,,tt1)) and Pa, (r: ri..... for / [l,, (2]. First of all observe that the arm that the agent pulls at round / fully determined by the past sequence of observed rewards r1.-..,Ft-1 since the policy is deterministic. As remarked in Section 2, we denote it through (t), omitting the dependence on r1, ......,f T--1- Now:
(1 (ri. Te, -1)
= (r........,,..... for all T1. 71..1. 1-1/20,33 3/20]
(r..
P [R 71..... R re 1 O
o-
[Xx(1),1 = T1 , X = rt On =
o a-x
[ = -T .....,Xttee ",...., ( = Tt- On = =]]
o 8~8
(1[T(() = -jpbre Po (t 8 + 1), a)
+ +1[m(() i)v(r: (1 81 1),
(6)
(t = i]o(rr Trm - 8w + 1),
([((t) (r (oo Sw 1),
Wiihh slight abuse of notation, we will use the symbol vfx a)) to denote the p.d.f. associated to the distribution e(u,a),
22

---

where line (6) follows from the fact that, under the event Oz i, X Xx()) is independent from I.())....., Xx(t, (1,-t)))--111 and follows distribution vi(pw (t- - + 1), if n(t) = i, ( (t - +
1) otherwise. Thus, we conclude:
(w, ; = (t) = () (t-
sw +1), ()) +1(x((t) * deb( (t sw +1), 0).
From analogous calculations, it is possible to derive:
Pw (r. ri,...; Tt-1) ((rx Moll 81 + 1),
Thanks to the last results and the definition of (-I--))):
(ri, ;,,,,,,,,,,,,,)))) Pua (r1....,, r()))
Σ
Pu (r(
Pinn F.E( ( 3/20)
(rr Th 8u 1)
Fult sw + +),07)
logg
1[x(t)
-1pere Molt Sw 0)) + 1[x(t) # d1
Σ
Pw (1))
Σ
((n Fuu(t Sw 1),
ree( 1e(311/2,3/22)
v(ri Ano(t - Sw + 1)
log2
vb(re Bw 5w +))
DKL (KL(Fol - -w + 1),,))ll(((hdl - + 1),o))
Σ
Pe Pe
minfew..1 .2
Σ
DRL(V(T, Sw + ()) - 8w + +), P [Te - 1).
outw and
t=8
The lemma follows by chaining the results.
We ready prove Lemma 3.1.
Lemma 3.1 (General Lower Bound). Under the assumption that (t) & (t) for all Nş1.
t E [. for any deterministic policy n, subgaussian parameter o 2 1, and learning horizon T E Na1. holds that:
(TT)
In(2) D 7.7,0
sup (T T)
1
A..B.T
vEEo
2K
where:
min min
DT.
DKL(W(Mmn Sw + +)) sw 1),
min min (ew, T)
A
Σ
(Dwllt- - Sw 1) The + 1)),
for all [[][T)]. with DKL(.I-) being the Kullback-Leible divergence of the two distributions (formally defined in Appendix B).
Proof. For o E [0, Ms1, E [T], let i e arg max [ (t). Then:
sup R,( wEER
sup of K Kx a~
Σ (Mo.t,) (t) Ho.l(t))
23

---

No.ss, (t) No. ((oott(()) (1))
Under the assumption (1)(1)) > (1) for all w Na1, [Aw] we have:
Mo,e, (t) Mo,1, w[0 * O, Ow(l) * (o]( Sw(() + 1) "ultt Sw(() 1)).
Then, observing that Ow = has probability under 7:
(T minfew.
sup VEE P
T)
(Trrlt - sw + 1) - 1w (t- 8w + 1)) E [1[0 * I.]l
W0
a-2
w(T) m
Σ
(t 8w + Th 8w + 1))
Σ
[1 * i, =1]
ie [=[A] a~
w(l') Iin Σ
Eo [144 + i, Ow =i]]
Σ
(Dwlt - sw + +1 - Fl
Sw + 1))
Σ
10 = $
P PoNi fo =
ie [<[]a~> a~
8~
w(T) Ti
Σ
(Rolt - 8w 1) - Fl (t Sw + 1))
Σ
E 11/4 * 11 O =
K
00
iE[
w(T) minfew.T?
Σ
Σ
(Dwllt - Sw 1) Fl (t- Sw + 1))
Σ
1-
1-4,114 =i]
K
KE[K]
(T) minfew.T)
(Dolt sw 1) Ft Su + 1))
Σ
1
E [1[4 i]]
K
omf
8e []]
2~d
min minfew: T)
(n)
Σ
DRI(ViMM - 8w o))lb(((()m) 8m +))
P [T =1]
2
om
a~
w (2) Ii
Σ
(Tr - sw 11 - pw Sw + 1))
K
1=
min T)
1
KK
ln(2)
DRL(V(P sw + 1), ())l((((()) sw + 1),
(8)
K
V2
f=
where line (7) follows from Lemma B.1 with f corresponding to the function from the observed rewards to the arm 4 pulled in round t, which is well defined for deterministic policies, and line (8) follows from Cauchy-Schward inequality applied to a vector of K ones and the vector of the terms under square root. The result follows from the definitions of D.. and AR..T
B.2 Specializing the Lower Bound for the Rising Setting
The goal of this section is prove Theorem 3.2.
Theorem 3.2 (Lower Bound for the Rising Setting). For any deterministic policy subgaussian
parameter 2 1, and learning horizon T E N T o² K min (rr it holds that:
1 goirs k v
sup (T,VV)
(T(
T)
>
64
24

---

Proof. First of all, we need to formally define the sequences of window widths, base, and modified
trends. Let Ar, = A, = 2//33/2/3 min(1, Vr}
2/3 aadd
(t) ( 1oww11 1) (TW(()
if & w(T) if w > w(T)
if w (())
(t)
(Ew((T)
w w(T)
for all N31 where E, min(1, (T((T) O. Observe that (A,) & Fr,w+1 (1) for all w N31, hence, for any choice of E [O, K K] Vi.o satisfies Assumption 2.1. Furthermore, for all o [0. ]1 s1, the expected rewards of the arms change at most between one window and the next, i... w 1 times in the learning horizon, and the magnitude of the increment is at most 28,, thus:
Twg (1, (T"(T) 1) VT.
Hence 80 i E VT) indeed holds. Finally, is easy to verify that & (r,,,(t) < Pr.w & 1 for all w E Nz1. t [[,]] so that the assumptions of Lemma 3.1 are satisfied. From Lemma D.I, we have that:
2 A.
D...T.TT.
In(2)
The choice of Ar,w D, implies & 1/233/11/3 1/3 123 min(1, V/ once we observe that ((T = [T/A,]. Then:
K 8 In(2)
D To
for w e [T]
Thus, observing that K 2, we have
In 2) D T.
1 K
2K
4
A.. = e, (minff Cwg, -)-s sw + 1), J. by plugging the previous results in Lemma 3.1, assuming Since
that T 0² K 1mmmm1111 Vr which guarantees T > Ar. we have:
sup (T.V))
Ru(
4 TT
1 64
L min(1,
where the last step follows from the definition of s, and the fact that [x] > x/2 and |æ| < 2x for 1.
B.3 Specializing the Lower Bound for the Rising Concave Setting
The goal of this section is to prove Theorem 3.3.
Theorem 3.3 (Lower Bound for the Rising Concave Setting). For any deterministic policc m.
subgaussian parameter 1, and learning horizon T N21, T> 200g2 2 min(1, Vr)- it holds that:
Ry T) 2- 1/67 K min 1 vEEg
sup
Proof. First of all, we need to formally define the sequences of window widths, base, and modified
trends. Let No = | 2/// K --/6 min/1, 1, 2/55 Aew A. = [T/Ne] for all w E N
Observe that A, is defined in such way that w(T) = iT/Ael & [T/(T/N)] = No. Furthermore,
being o, K 1, we have:
No
T
T =
so that T/N > 1 and A & 2T/Ne since [x] x 2x for x 2 1. Let my == 1 min(1, Vr (0, 1), may (2N. w)mo/ (2NN)) for E [2N.]. 12N the slopes of the segments which
25

---

constitute the trends. Observe that mo > my > ... M2N.-1 > M2N. 0. We are ready to define the trends:
w
A
M2-1
-m2
if & w(T)
Fe, (1)
(
A
M21-1
w w(()
W-
Ag 2
A
m2-1
22 +
t
(m2w m2w-22
if & w(T)
ee (t)
(T)
A
m22-1
if > w(T)
for all E No.. In what follows, with slight abuse of notation, will regard Ngw and ño, as defined on [0, A.). Observe that, as we informally stated before, Pe, (0) Mr, and Me (A.) = Me,ar Ae) Me,,+1 (0) for all w N₂1- Furthermore, it is easy to check that the slope of the second segment of the modified trend in window is equal to the slope of the first segment of the modified trend in the next window. Thus, because of what remarked when we informally introduced the construction, for any choice of o E [0, K] Ve. satisfies Assumptions 2.1 and 2.2. Furthermore, in each window with index w [w[ the maximum increment of the expected reward of an arm, corresponds to the slope of the first half of the modified trend m2 Thus:
w(T
A.
Tue (1, & Ae
Σ
m2w
2 & Ao
m22
(Ne 1)
T
min(1, Vr)
A &
NNe
min(1, 1, VT} & VT.
N. 4
T
2
(7, indeed holds. Finally, by calculations analogous to what we did above to bound the cumulative increment, one can verify that:
Hence 0 P.
A
m2w-1 & min Vr & 1,
which, together with the previous remarks, implies 0 & (t) & (t, & 1 for all w E N31. t e [[Ac] so that the assumptions of Lemma 3.1 are satisfied. The maximum distance between the two trends in a window is attained for = - and has value:
Ac
Ac
Aomo
min(1, Vr3 N²
Eo
New
$
2
2
4Nc
Hence, in virtue of Lemma D.I, we have:
2ea
A min(1, VT
K
DP T.
(2)2
16 (n(2)22
16 (n()
for all w E [w[[]]. Thus, remembering that K > 2. we get:
Dy
1
2
K
2K
Now, let's lower bound the expression of Al. B..TT for w E [w([]- 1]:
-1]:
A
A..
m2w-2 m2
(m2w -12
(m2w m2w-2)
t=
+1
mg
2
A
2
11
A
A - 1) (A. -
2N
2
2
26

---

mg
A
Ac
mo
5
4
m
4No
16
4No
16
16
64.N
mg T
min
Vr
64N
256N'
where line (9) follows from the fact that [x:] 30- x/2 for x > 1 together with A./2 1//22 > being 7> Ne when 3 (which is guaranteed by the constraint on T), and that a & x² for x > 1. Finally, T > 2 o K min(1, VT guarantees w(T) - z No/4, /4, and thus, by Lemma 3.1 in conjunction
with the results we just proved, we have:
1 Σ Ae. 3 (w(T) 1) min 1, VTJT
sup NEES (T.Yr)
(T,
256N2
min 1, VI
2 2-11 K min Vr
(10)
2
where line (10) follows from our choice of N₂ and from the fact that [x] 2x for x 1.
C Upper Bound for the Rising Concave Setting
In this appendix, we provide the proofs of the results presented Section 4 in the main paper.
C.1 Additional notation
We begin by introducing the additional notation required for the analysis. Let:
(n) +d-1
(an +
Simmn
Σ
1/ = Re,
B
= i),((),
t=
be respectively the cumulative reward and cumulative expected reward by RC-BE(a)) for arm i [K] in the first E [O, A (a) rounds of window w E N Let N be the number of round-robin cycles
of window w 21 where also count the degenerate cycles in which we pull the only remaining
alive arm i Let tw. I be the round in which the (-th round-robin cycle (with [ [[Nw>) started during window w Nş1- Analogously, let New be the number of times arm i E [K] is pulled in the w-th window (with
N21) and w, the round in which arm is pulled for the 1-th time (with
1 E [Ni,w]) during window w. For simplicity in the notation, we define dw bw.t (a) + 1 and ds,w,1 = ti,,.l
Sur + 1. Finally, we define the good events:
{1s |Ss.ma Bimmaa & a 0 24 (In (I(22Al0)) + In (7) (5)
)
Gim =
for [K], w E Nzi. de [A IA
1,6E de (0, 11. and
G
Gi
[E[K] d
for [K], d E (0, 1].
C.2 Concentration
We start the analysis with a concentration result for Si,
Lemma C.1 (Concentration). For every w E N 8 (0, 1]. we have that:
X~p [G & 8.
27

---

Proof. Forie [K]. de [0, A. I, X E R, let:
Mi, exp (*
( (Sired Bewwd))
XK.I, Fund == d (XI_,..,,KII,- X 1,000) +d-1:
X K +a-1)
Let t' = sw + d 1 to ease the notation. Observe that Io is -meds---masuuablle and that X is independent from F Furthermore, rewrite Si,w.d as
S,add =
Σ
114 = i].
(m) (c)
Then:
E X-v
(M) Fw.d-1] M...dd-(M E
[1[e = 1) exp (A (((r)))((t))
X-v
+ 1 - 1|1 = il Fu,d-1]
X²0²
Aoo22
Mi 1 exp
1[ = 1
& M Mi, exp
2
2
where in the last line we use the properties of conditional expectation (Klenke, 2020) and the sub-gaussianity of X Thus, by induction:
A20² 2
((a) 1²02
[M)) & exp (d
& eexp
X-v
2
Then, thanks to Markov inequality, for every E R:
P
Si - 3r > 6
[Mim > exp(Ae)]
X~v
X~v
< E
[M exp(p --x)
X-v
(a) 02
exp
1
Xe
2
By choosing & = / (a) In 2K + In (1)) x
(1)
we get:
X-v Si - 3l > 6
2K ((a
An analogous bound holds for
Br.dd - Simnd > 8).
X-
Then, thanks to union bound,
8
P
x X-
KA (A(aa
Finally:
IP
G
&
Σ
P
Gimm E..
x
X-v
[K]
del de(A
C.3
Proof of Lemma 4.1
The goal of this section is to prove Lemma 4.1. To this end, we need several intermediate results. We start by proving that Ix is indeed well-defined.
Lemma C.2. Let in j I then it w x j
28

---

Proof. If p. (t') ()a(tt)) for some t' [si
(a) _m then it must be E x Thus, assume
(a)(t') < 21 (t') for some t' [sle ew If tn and f do not cross, then
P& (t) Mys (1) for all te [ 1
which is a contradiction with the fact that v E T
We now prove a very useful property of w x
Lemma C.3. Let i,j. E [K]. If wiixx x and there exists t' [>(h] . e such that pa(t') & (x(t)) & (t),), then e xx]
Proof. If (x((t) pi(t') or pe(t') = pz,(t) then the statement is trivial. Consider pt((') <
me(t') (t((t). We proceed by contradiction. Assume that it is not true that io m +i Let
I (TE [1] xt s.t. (e(t)) px((')) and I2 {le [1]
pi(t') px((')) Since In J I2 S [ x+, I II I, 0 there must be I1, I2 such that i w x iz. But, since is
not true that k ti, cannot be xi nor k w xig. Thus it must be
p4, (t) < (t) Mi, (t) for all te [s(o), e c())]
But this is absurd since i w xig, concluding the proof.
This leads to the following corollary.
Corollary C.4. Let I j $ Ig then:
m5(1) pe(1) for all I [s e(o)).
Proof. By contrapositive, if (t()t) > pt(t') for some t' e (a) cla), then there exists & arg k pa(t") such that (t))t) & pt((t) & (t'(t) and thus E I by Lemma C.3.
We are ready prove Lemma 4.1.
Lemma 4.1. For all restless rising concave MABs v, w N31 we have that:
R2 (RCCBB(((), (w)) & 3KB
(0)
Exploration
Commitment
Proof. We start by proving that, under event 9 ( at least one arm in IX is always alive in each round-robin cycle. We need to consider all the eliminations which happen the end of a round-robin cycle, except for the last, in which eliminations are irrelevant (remember that the window ends the end of the last round-robin cycle and the algorithm restarted). To this end, let E [N - I]. For an arm i E [K]. to eliminate an arm j [K] at the end of the nith round-robin cycle, must be:
S, au n+1 > S wj, + B(a)
which, under event 9 (2KA())) 1s implies
Si + 40 Alaa) In (2KAle))
Sj.ndd.n + B(o)
if and only if
Σ (uiltwa) + pi(ti.w.) - Hi(tw.)) + 4oy - (2K a
Σ (1z(bwa))) + us(lim))) - (b()),))) B(a)
29

---

which implies, being the instance rising:
n
2 pi(lm,)) + 1 4a Au (a) In (2K (.:))
Σ pz(bm,)) + B
and thus, because of the choice of (.a) it must be:
n Σ pe(tw.)) > Σ (j]tw..). 1=1
Thus, in virtue of Corollary C.4, it cannot be i I j I But, eliminate all alive arms in TV we would need at least one cycle in which an elimination of the kind above happens, Hence there will always be at least arm in I alive. Let 1x be such arm during the n-th round-robin cycle. Let's bound the regret of generic arm j [K] during the w-th window, under event 9 (2.()
Nw -1
Mey symm
(tg,0,)) - H4 (s(t),w..)
$
Heg Simee (ty,w,)) Ms (s(t)sa)))
+
Mex Ny (1.w,)) - M4 (brrwa))) + Ni
Mes (Eex (ooon w. Myy ()(t)ams))
N
Max Pu (gywar)) - Mos (lex OEE mir)
+ N. +1
33.w wwu -1 + + N Now 1
N.N wuddi Ngw
< 2 Aoy (a) In (2KAl1))
S F My w.rchr N
-S.u,dar -1 Now
B(o) +8,x N widd No
Sp.wddw. -1 + No
< 2B(a) + No
where the last line follows from the fact that we have not eliminated arm j at the end of the (N 1)- th round robin eycle. Thus, the regret during the w-th window, under event g (w,(2K(())) is upper bounded as:
N
Σ (t) mz) = Σ t=
(ty,w,)) - (t((t.)).)) & 2KB(a) + (a) d
pie 2y
jE[K]
Finally, in virtue of Lemma C.I:
R2 (RC-BE(()), (w]) & 2K B(a) A (a) P
g (2.(
X-M
1
& 2K 2KB(a) + A
(a) +
& 3KB((a) + A (c) de
2K
C.4 Proof of Lemma 4.2
The goal of this section is to prove Lemma 4.2. To this end, we need several intermediate results. We start with a lower bound to (a)
30

---

Lemma C.5. For any a 3 1, E N₂1 it holds that
w 1y1-0 t
e
2(1 + a)
Proof. If w 1, we trivially have
(a)
1>
2(1 + 0))
Now, suppose > 2, then
10
2
w ++
e(a)
(0)
aa
x do
1+a
1+a
2(1 + a
1=1
Now introduce the results through which exploit the concavity of the instance.
Lemma C.6. For any restless rising concave MAB 11 12 E N31, 12 3
t 3 2, we have:
t2 t
(2),
t2 t + (t 1,
Proof.
(1(,
max (1)))
iE[K]
1
max 71())
max 71 -1)
7((1) i[[K]
max
iE[A]]
1/2 81
iE[A]
12 t
t2
Σ
max 7((1)
t2 t
rx(41 - 1,42)
1/2 1 +
[[[]]
1/
1 +
Before proving Lemma 4.2, we need an intermediate upper bound to dw (1). Lemma C.7. For all restless rising concave MABs v. a 3 1, w E N31. e [K]] we have that:
(t) & (lfi) x+1+++111 1)
stf xk (ng(t) mb(()). te|
max
j.kl
Proof. If a x+ k, there must exist distinct i,,..., different from j and le (n [0, [+]]]x+ 2D
such that .. xxx. á1 x x ..... in-1 w in. in x k. Then, for t E [( ( I. we have: (my(t) (x())) < (1,(1) u4, (f) + | (t) - (t) + +... 1.., pu (t)
(n + 1)
I [e x stJ' xk (ty uw (t')l
max
e'El c([]]
< [[]]]_++] 1)
lpy(t') - Me (t')l.
max
j'EE[[ x st xM (ee ,511
We ready to prove Lemma 4.2.
Lemma 4.2. For all restless rising concave MABs v, a 2 1, w N21, [K], we have that:
(i) < 8(1 + a) (I1i,..-I 1) T1, (()) & 16aK LG ((,,
31

---

Proof. Let j to & for some j, k E [i] x t' E [s 1, ( Let > te te [s ee
II.
then
(t(t) - (x(()) py(t) - me(t' - 11 E p,(()) uu(t' - 1) & T2 (s e c(a
(x(()) - (t) & (x) 11(1) E (x(1) -m(()) & Tr (s! c(cr))
Analogously, if < L', we have
(l(() - (1) pz(l' - 1) - (l) & pall - 1) mm(() & Tu (s17) (o(() - (t(() & (x) p1(() p2((t) -ty(t) Tr (s/o clai)
We conclude that, i j x then (mz(1) mx(()) & Tu (5 c ( for all LE 1 ew (0)
Thus, in
virtue of Lemma C.7, j o x k, then:
(l,(t) - pe(() E (I1,xxI1-1) To (o(0) (6(")e(o))
For w 2 2. by applying iteratively Lemma C.6, we have
(a)
sie (a)
A (a)
Tu (
(a)
$
Tv (1,
& 2 (a)
Tv (1, claa)
6w
ew
8(1++)
a)
wa wl Tv (1, (1,
= 8(1 +
(1,
where in the last line we used Lemma C.5, the fact that [x] < 2x for x > 1, and the definition of The same upper bound holds trivially for since s(()) c(aa 1.
A 10
(o)
C.5 Proof of Lemma 4.3
The goal of this section to prove Lemma 4.3. To get the result, we start by providing an upper bound to the number of times an arm i overtakes arm j and the expected rewards diverge by a quantity greater than G > O. To this end, we need to prove two auxiliary results.
Lemma C.8. Let t & tt E Na1 e > >i> tt, GE (0, 1]. i,j E [K] such that
i 11 > m3(()) G.j ta i.
Then:
nit - 1) > 75(0= > (t()))
(11)
1
i (6) - 1) >>> G
(12)
rill - 1) 70()
(1)
m(( 1t(1" 1) 3 G
(13)
71t - (f)
Proof. We start by proving Equation (11). Suppose 7/(1) > 7i(t" - 1). Then:
(,(() > (t - 1) + (f (t' (1)
> n,(t" - 1) + (f- - (t' - (t) -1)
> m.(t)
which is a contradiction with the definition of f. Thus it must be 7y(() < nltt 1). Analogously, suppose (f) (t)). Then:
m,(tt) & (f,()) + (dd00)s(0) < (f( - G (t)(t)) < (t())) - G
32

---

which is a contradiction with the definition of t Thus it must be [5(t) 2 (((t)) We now prove Equation (12):
G E ((()) - (0) & pi(t? - +)+ ( (t) 1))+st
- Mylt - 1) (f - -1))((t
< (f (t) - 1))(((((t) - -1)) -1)-2((f)
and thus
-- (1t - 1) 3 G 1
1i(t - 77s(t
Finally, prove Equation (13):
pa(f) pt(() 1) (t) ut(t! - 1) (f- (t) - (f)
(0)
G N1(11 - - (t)
Lemma C.9. Let Me N31, 2, my m2
mm MM+1 then:
M
M
(14)
my
M4+1
m1
1M++
m4+1
M
(15)
my
mW+1
122
mM++1
Proof. We regard my MM+1 0 as fixed constants and study the functions
1
f mm)
m:
74++1
M
mi+1
g(m mm)
m, 74+11
defined for my > m2 > ... mm MM+1- Observe that the functions are defined on an open set and their values tend to infinity when the input tends to the border of the domain. We show that they have only one stationary point, which then must be minimum point. We start by proving Equation (14). Let h: E [2, M]:
df
1
(m2,.... .... mM) = (m--1 m2
dmp
(mz m
if and only if
m 2m m6-1-
The linear system above equivalent to:
(i - 1)m² - (i - 2) for ie [3, M 1].
(16)
Thus MM+1 Mm2 (M - 1)m1, and then
(M 1)ml m++1
m2
M
By plugging this result into Equation (16), get the coordinates of the minimum point:
(M 1 i)m1 + (i 1)mM+1 for i [2, M]..
m
M
Thus:
M
fmm),..,,mx) mm) > f(m m+ my MM+1
33

---

We now prove Equation (15) analogously:
dg dmpk
(m2...., "mng...,,,...
mmr)
mi
11k++1 1
(m m2)²
(my - m
if and only if if and only if
m
m 77-1
1 = 2 In my - In m
Observe that we get the same linear system of the previous case, with the difference that the variables are now In my. Thus, the solution is:
In m (M 1 i) In mi (i- 1) ImMM+1
M
and then
M+1-1 M
m = m,
m
for iE M... MM
Finally:
M
3 g(m?....,,. .mmm.,,,)))
-1
WM+1
Lemma C.10. Let G E (0, 1]. T' N21 M e N21. i,j E [K] such that there exist rounds
2 2 & < & < t < < thy & tm < T
which satisfy
ig j. ((i) > m2((1) + for all l E [M],
j 14 for all le [M- 1 1].
Then:
M < 4lm G
Proof. Observe that, since
mi((m) > p,((ss) + G > 14((th - 1) + G
3 mithis - 1) + G.
we have
T'y(tt) - -1) > (fM- (thr - (t) 1) i m.(tar) - Ni(ths 1) G
and thus
G
nu(thr 1) x T"
Now, assume M 2 3. Then:
M-1
1 13 (T(T)) - 1((1) > Σ
(ma(1)) - mi(1 - 1))
G M-1
(9((i)
(17)
70( - 1) - (t)
76(1111 1)
(18)
(t) - 1) - - - 1)
M
(19)
(+(+| 11) W--
7r(4 11)
34

---

M - M-
M -1
G
G
(20)
[G(T)G) M-1
exp
where line (17) follows from Lemma C.8, line (18) follows from the fact that
2 is dencesergg for a 2= and the concavity, line (19) follows from Lemma C.9, and line (20) a-
follows from the fact
that (t) 1 - 1) & and 7i( - 1) > G.
T Now, M > 1 1 In(TT//)) by Lemma D.2, we have /G( - & 3 /G) and thus, by the chain of inequalities above: M-
exp
M-1
1 (M- 1)2 3ln(T//) if /ln
Thus, by considering all possible cases, we have:
M & max Int
/3n((T/G)G-1 (330///00)),++(((/00000))))1 41)
We are now ready prove Lemma 4.3. Lemma 4.3. For all restless rising concave MABs 2 1, Nş1. d (0, KJ. we have that:
[W>((T) < 9In wy K/d) K d
(3ela)
Proof. Let w W>a(T). Then there exists [K] such that dw(() d. But, in virtue of Lemma C.7, we have:
x+1-11
max x saj a
(1y(t) mx((t) > du (t) > d.
j.ke
Thus, there must be k lil_x and [sle] eloy such that j x k and
d
(ns(t) - (x(+))= > [[ - K
Observe that it must be either i j for & or i X for t, with l' [s + +1, ela)) W.L.og. assume that overtakes j. In the first case, window must contain of the rounds in which overtakes j and then their expected rewards diverge by at least d/ K. In the second case, window w must contain either the first round in which overtakes j and which is right after of the rounds in which i overtakes j and their expected rewards diverge by at least d/ K or the first time in which i overtakes In virtue of Lemma C.10 with G= A and T" =e(a)
(a)
(T)) the rounds described in the
first case are in number more than In (3e (3e(a) (T) K/d) (d/K) while the rounds described in the second are in number more than 4 4n (3e(a) (T) K/d) (d/K)-1/2 for fixed choice of i [K]. Since have most K2 such choices, must be:
[s>((T) & K2 (8ln wry k/d) (d/K) +
& In (a (T) k/d) kåd-..
C.6 Proof of Theorem 4.4
The goal of this section is to prove Theorem 4.4. We start with an upper bound to w((o) w)() (a)
and Tr (1, e(a) (T)
35

---

Lemma C.11. For all restless rising concave MABs v, 2 TE E N32, we have:
(T)
& (2 a))) (1) & 40T
(21)
(a)
(T)
4(1+ a)T & 807,
(22)
Tv e (7)))))))) 8(1+ a) (1,T)
(23)
Proof. We start by proving Equation (21). If N31, w (2(1+a)7)U(Lt)) then, by Lemma C.5, we have:
wl+a
ST.
+1+
Thus it must be (T) & (2(1 + T) 1((+a)) We now use Equation (21) to prove Equation (22).
(0) (T))((
& < (T) (T) (a)
(T)
< 2(2 + a) + (2 + a) = 4(1 a)T,,
(24)
where in line (24) the definition of A (a) Finally, we prove Equation (23).
Equation (21), and the fact that |>| < 2x for >
1.
(a) win) (T)
Tp (I,
(())())))
Y (1,)7))
(25)
T-1
(0)
wlm)(T) (T)
(L(1T))
& 8(1 a)T,()
(26)
T
where line (25) follows by applying iteratively Lemma C.6 and line (26) follows from the fact that T > 2 and by Equation (22).
We ready to prove Theorem 4.4.
Theorem 4.4 (Upper Bound for the Rising Concave Setting). For all restless rising concave MABs U, a 3 1, T E N224, we have that:
R. (RCCBB(())) & 25 (In (akT*))
(1+ 3:4e
3 Iia (l,
5/4--1
14222
(1 KT 14a
In particular, for a' = =8/3, we get:
(R(CCBE(('),,T = =ō =Ō k (KTt))
Furthermore, for
8 - 4l0g a"
K²Vz
1+a
3 4logg
K2VG 1+7
under the additional assumptions v E Eo (T, Vr).
(1 0) 4/3 -
4/3 +1
T max
(1 + 0) 8/5 K 16/5 1 8//
get:
(_,(CC-E((a")TT H ( if K #
36

---

Proof. Let d' = KT- (a/2)/11a)) E (0, K]. Then:
Ry(BB-BE(a), Wid (T))
W (T)
max
(3KBl0) + + d
(27)
wEW (2)
9In 3e (a)
TTm
K2T
(28)
win (T)
(3KB (a)
+ 16aaK (0) TT
max
wEW
9 R 9/4
(29)
6K 1 20 Al) In(2K (0))
max weW
32a2 w - (1,
(30)
6K
1 1 8aT rio In(16aKT)
+ KKT Iu(L,T)
2 )
(31)
2 (Ina"((( K (1 + o)T T Y (1,
2 (I(ak77) ((1+ (1++)) 3:40
+T T+ I,(,,T)
where line (27) follows from Lemma 4.1, line (28) follows from Lemma 4.3 and Lemma 4.2, line (29) follows from Lemma C.11, the definition of ( the fact that [>] 2x for æ > 1, and the definition of Bla), line (30) follows from the fact that the expression inside max is increasing in w, Lemma C.11, and the fact that [z] & 2x for x > 1, and line (31) follows from T > 24. Furthermore:
Ry (RC-BE(()) Wea (T)) & (T)I
w max (3KB + A d
(32)
WEW
< (T) 6K 1 20
(a) (T)
In(2K (a) w
(a)
(2r) d"
wi
(33)
< 4a (1 + (b(k) 8
(34)
2/2 + +8KKTTaT
14// Tro
< (0dd( KT
1ia T1a
1ta/2 ; 1+a
KT
where line (32) follows from Lemma 4.1, line (33) follows from the definitions of (( and Wea (T),
and line (34) follows from Lemma C.11, > 24, [x] & 2x for x 1, and the definition of d'. By summing the previous results:
(R(CC-BE(a))T) T) & R,(-BCBE(a)) Wsa (T)) + R2 (RC-BE(()) Wey (T))
23 2 # (1+
3/4
+ K&T (1,T)
(11+ (1+o)KTT)
Finally, observe that, under the additional assumption u E (T, Vr), we have Y,(1,)) & Vr, and the additional constraint on 7' guarantees a" > 1.
D
37

---

D Technical Lemmas
Lemma D.I. Let Pi, [0, 1] with bn & μ2 and a E Then:
(KL( (1 σ)) 2 11)
In(2)
where DRI(-1-) is the Kullback-Leibler divergence defined in Appendix B, and (1,, σ) is the distri- bution defined in Section 3.1.
Proof. Let p(1, 0) = 21 Consider the function:
f(z) = DKL ( ()] + +2,0))
0(
1 - p-puu,,))
= p((1,0) log2
+ (1 (a-pp(u))) loga
p( + x,,)
1 p(u1 + x,
for x E [0, U1 - -.1. Then:
(a) 1 δp
1 1-p(un,0) 1-p(M1 + +2,0) p(11 + )
p((),
(1 + 07
In(2) 0μ
Cp (1 + 2,01)
1- 0-p(u1,0) 11-11ppu (1p-p(m1 p(u1 2, 220))2 p²(m + 22
p(1,0)
f((x) (2)
Ōp
By direct evaluation, we have f(0) = f0( = 0. Furthermore, since μ E [0,1], o > 1, imply o( 1/4,3/4], then:
1
(p + 2100))
1 11- 0) p((),0)
(x) <
In(2)
(1/4)2
(1/4)2
16
Ōp
2
(n + x,
In(
2p
In(2)
Finally:
S (F(0)+
_0a f"(z2)dxz
2x
f(x) f())+ f(0)
d3b $
Jo
In(2)
The result follows from the fact that
o)) f(12 H1).
Lemma D.2.
d- 3x for e [0,
Proof. Let f(x) = e" 1. Then: f(() = = = (x)).. Thus, by Taylor's theorem, x e [0, 1].
there exists E (0, 1) such that
(E) x² x (1 1
e 2
(1+ E) )T $ 3x.
((x) ((0) ('(
E Numerical Simulations
In this appendix, present additional numerical simulations which compare RC-BE(a) with the baseline algorithms reported in Section 5. Furthermore, we provide information regarding the compute resources used run the simulations.
Baselines. We consider the following baseline algorithms:
Rexp3 (Besbes et al., 2014), an algorithm for restless MABs based on a variation budget for the expected rewards of the arms over the learning horizon.
R-less-UCE (Metelli et al., 2022), algorithm for restless rising concave MABs which relies on the optimism principle and exploits the structure the setting through a specifically crafted estimator.
38

---

11p
RC-BB(oi)
Raxp3
R-less-UCB
Expested Reward
Camullaive Regret
DCB1
0.6
0.4
0.4
0.2
0.2
10"
Rounds
-00P
(a) Expected rewards.
(b) Cumulative regret (10 runs, mean + +3% C.I.).
Figure 4: Piecewise linear instance.
UCB1 (Auer et al., 2002a; Bubeck, 2010), one of the most effective algorithms for stationary MABs.
The choices of the parameters of the algorithms that we compared are the following:
Rexp3: Vr = K since, as remarked in Section 2, in the rising setting the cumulative increment is always smaller than or equal to K; År [(K In (TT/))))(((V
min {I. K In( ((TTK(((A((()))) 1))} as recommended in (Besbes et al., 2014).
R-less-UCB: h, [eN where N1.-11 is the number of times arm i has been pulled by the agent in the first f rounds, with E (0, 1/2); > 2 as prescribed in (Metelli et al., 2022). In particular, we choose c 0.25; a 2.1.
UCB1: the upper confidence bound interval for arm round a o (44nnt///NN/..
E.1 Additional Instances
Piecewise Linear Instance. The piecewise linear curves that describe the evolution of the expected rewards in the simulation have the following functional form:
+ S0
if < fnat
f(t)
T 7-1 pa
T He
if taa
for t E [T]] where μi: Pe [0, 1]. M4 & Me. After the flattening time tha E [[']] the expected rewards of the arms stop increasing. The expected reward curves of the simulated instance are reported in Figure 4a. The algorithms are evaluated on 7 = 5 10th rounds. The standard deviation of the noise is 0.1. The empirical cumulative regret suffered by the algorithms is shown Figure 4b. We can observe that RC-BE(a) is the algorithm that achieves the lowest regret at the horizon. The behavior of all other algorithms explained by the same observations stated for the exponential instance in Section 5. Conversely to what happens in the exponential instance, in this case, UCB1 shows better performance than R-less-UCB. This due to fact that the change of the optimal arm happens later in time and the distance between the expected rewards of the first and last optimal arms is less w.r.t. the exponential instance presented in Section
Constant Instance. In this simulation, the expected rewards of the arms do not change with time (i.c.. stationary MABs). The expected reward curves of the simulated instance are reported in Figure 5a. The algorithms are evaluated on T = 106 rounds. The standard deviation of the noise is o = 0.01. The empirical cumulative regret suffered by the algorithms is shown in Figure 5b. UCB1 is the algorithm that achieves the lowest regret. This is consistent with the fact that the instance is stationary. RC-BE(a) has the second-best performance. The reduction of the standard deviation of the noise leads to smaller confidence bounds and, thus, better performance, for R-less-UCB, Conversely, Rexp3 is not able to exploit this fact, being based on the Exp3 algorithm which designed for the adversarial setting.
39

---

-10
BC-BB(a)
Rexpa
R-less-UCB
UCB1
Expected
0.2
0
0.0
0.6
0.8
0.0
0.2
0.4
0.6
0.8
1.0
Rounds
100
Rounds
-10"
(a) Expected rewards.
(h) Cumulative regret (10 runs, mean t 95% C.T.).
Figure 5: Constant instance.
E.2 Compute Resources
The simulations were run on a single CPU core with a clock frequency of 2.60 GHz. The system has 8.0 GiB RAM. For each algorithm, report the approximate time required simulate single run on the exponential instance with 5 10 rounds:
Rexp3: 5 min 50s;
R-less-UCB: min;
UCB1: 3 min 30s;
RC-BE(a): min 50s.
Flaw in the Original Analysis of K-armed Budgeted Exploration
1/2
JeL
1/2
1/2
fi(z)
-VOL
f(()
fs(2)
....... f(())
fz())
f(())
3917
2V
3/17
3/17 + 1/E
1/17 4 & 5/17
+.
3/17 +
(a) Reward functions.
(b) Derivatives the reward functions.
Figure 6: Example instance.
In this appendix, we highlight flaw in the original analysis of the extension of Budgeted Exploration in the K K-armed setting, which is presented in the unpublished preprint (Jia et al., 2024). For notation and definitions, refer the original paper. The analysis relies on the following proposition, stated in Lemma 1.7: "First, we observe that on the clean event C, any arm in 4 can never be eliminated for "losing" to an arm in (A*)e", which satisfies the hypotheses of the lemma and violates the previous proposition. We now show
possible to construct a counterexample
40

---

how. We work with 3 arms. We describe the evolution of the expected reward of the arms only in certain window. This is sufficient for the construction of the counterexample since the lemma regards the behavior of the algorithm in single window. The window is composed of 17W rounds, with W N32 to be chosen later. The expected rewards of the arms are defined as follows:
Ta (1) = fa 17W
for [17W]
where La [-11)- is 2-Hölder function with Lipschitz constant L > 0 for E [3]. Such functions and their derivatives are depicted in Figure and Figure 6b, respectively. More specifically, we choose:
The function in which the expected rewards of the first arm are embedded as:
0
ift E
0,
3 + 2 7/4 17
L (
3 - -2 %. 17
ift
3
+ 2
3
+ 3v
(z) = 2 Jn
17
L 17
dt.
vdL (t 3 3V2
if
3
+
3
3
+ 4 AVIL
17
L 17
if
3
17
The function in which the expected rewards of the second arm embedded
f2(z) =
2
The function in which the expected rewards of the third arm are embedded as:
0
if E
0,
3
17
3 L
(
if E
3
+
17
I7
17
fa(z) = 2 j
+
VdL - L tt 3
VA.
if E
17
+
17
d 3
+
+2
d
dt.
0
if E
17
3
+
2
E.1
The definitions rely the constants d, 0, d 1/2, which choose later. To guarantee that the functions are well-defined, we impose:
1
17 iff L> 34
(35)
We work with deterministic rewards, which can be regarded as special realization under the clean event C. Let Z be the cumulative reward of arm a e [K] observed up to round t [17W], included. Assuming there is no elimination before round 3W (we choose d and in such a way that this is true), we have that:
7 3,
W
3
1 -
W
Stotal,W
(1 - W.
2
2
Then:
Looall
22 30
sW,
2
30
too dW.
Let:
B
B
2W
where B is the budget of the algorithm. These choices such that eliminate arm 3 at the end of round 3W (and not before), losing to arm 1. Arm 2, instead, stays alive. To satisfy d & 1/2, it sufficient to require W > 3B. After round 3W, the algorithm pulls only arms and 2. When (1()) > (t), their difference is at most e. Thus:
7lotal,5W
7, 5W
2:W B.
Hence, arm 2 is not eliminated before round 5W (included). By the choice of the instance, in virtue of Equation (35), after round 5W, have (t) 1/2 d. Thus, after each round robin cycle, which takes 2 rounds, Z Ziotal.t tootll,t increases by d S. Then:
Z 17W Ziotll, 6(d E)W (Z) (2 Z 55,
3B B = 2B.
41

---

This means that, at some point after round 5W, arm 1 will be eliminated, losing to arm 2. But it evident that 1 A and 2 E (A*)². However, important notice that I consistent with our analysis. It remains to show that there are choices of B, W. T, and I. which satisfy the hypotheses of the lemma and the additional requirements we imposed. In particular, they need to satisfy:
17W In(3) In(T) & B W
34 B
W-I & L
17W TT
2 & W
is clear that such an assignment exists. Furthermore, we can find such an assignment even when we restrict the budget the natural choice which has order W1/2
42


Reviews:
[{"review_id": "L9v59gZj45", "reviewer": "Reviewer_9yKg", "summary": "This paper investigates restless MABs whose expected rewards evolve over time. \nThey consider two different settings where the expected rewards are either non-decreasing (rising) and non-decreasing concave (rising concave). \nThey derive regret lower bounds of $\\Omega(T^{2/3})$ for rising MABs and $\\Omega(T^{3/5})$ for rising concave MABs, showing that the rising assumption alone does not simplify learning. \nFor the rising concave case, they propose the RC-BE($\\alpha$) algorithm achieving a regret upper bound of $\\tilde{O}(T^{7/11})$.", "questions": "Please comment point 1,2 in the above weakness part.\n\nThere is a typo in line 209: $\\Delta_w^{(\\alpha)} \\rightarrow \\Delta_l^{(\\alpha)}$", "limitations": "Yes.", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n1. The overall writing and presentation in the paper pretty good. \n2. Table 1 was very helpful. It clearly sums up past work on restless MABs and demonstrates what this paper contributes.\n3. Figure 1 was also helpful for understanding the rising and rising-concave setting.\n4. Repeated actions may yield steadily improving rewards. Their restless rising (concave) bandits model this effect better and match reality than stationary models.\n\n**Weaknesses**\n\nI have no major issues but a few minor questions and would appreciate clarification to confirm my understanding.\n\n1. Beyond the formal lower bound in Theorem 3.2, could you give an intuitive explanation for why the additional rising structure does not make the problem easier?\n2. Theorem 3.2 shows a lower bound of $\\Omega(T^{2/3})$ for rising MABs. Theorem 3.3 shows $\\Omega(T^{3/5})$ for rising concave MABs. Does this imply that the rising MAB is a harder problem than the rising concave MAB? Could you briefly compare the two settings?", "was_revised": true, "final_justification": "I value this work for proposing the Rising MAB and Rising Concave MAB frameworks, which capture non-stationary rewards of environment. The theoretical analysis is concrete and contributes meaningful insights to the literature. Additionally, the authors have provided helpful intuitions in response to my questions about the theorem in the initial review. The authors have provided a clear rebuttal that addresses my questions. I maintain my positive rating.", "rebuttal": "We thank the Reviewer for the time spent reviewing our work and for having appreciated it. Below, our answers to the Reviewer's questions and comments.\n\n> Beyond the formal lower bound in Theorem 3.2, could you give an intuitive explanation for why the additional rising structure does not make the problem easier?\n\nThe complexity of the general restless setting is due to the fact that the optimal arm can **change abruptly** and very often over the time horizon. This can be seen by looking at the lower bound instance used in the proof of Theorem 1 (Besbes et al., 2014), where the time horizon is split in windows: in each window all arms have the same expected reward, equal to $\\frac{1}{2}$, except for one, chosen at random, which has expected reward equal to $\\frac{1}{2} + \\varepsilon$, being thus optimal. In the rising scenario, despite the additional constraint, we can **still exploit abrupt changes** (see Figure 1) to construct instances which are sufficiently challenging, but we have to be more careful in the variation $\\varepsilon$ due to the fact that we cannot allow arms to \"come back\" to expected value $\\frac{1}{2}$ or \"go beyond\" expected value $1$. We conjecture that what makes identificability challenging is the chance to have very rapid shifts in expected values.\n\n> Theorem 3.2 shows a lower bound of $\\Omega (T^{2/3})$ for rising MABs. Theorem 3.3 shows $\\Omega (T^{3/5})$ for rising concave MABs. Does this imply that the rising MAB is a harder problem than the rising concave MAB? Could you briefly compare the two settings?\n\nYes, it is correct. For rising MABs, we have a lower bound in the order of $\\Omega(T^{2/3})$, while we have an algorithm for rising concave MABs whose regret is upper bounded by $\\widetilde{O}(T^{7/11})$. Being $2/3 > 7/11$, this allows us to conclude that rising concave MABs constitute an easier setting. In light of what has been remarked in the answer to the previous question, this is due to the fact that, under the non-decreasing assumption in conjuction with the concavity, it gets increasingly harder for the optimal arm to change and diverge significantly from suboptimal ones.\n\n> Suggestions and typos\n\nThank you, we will fix them."}, {"review_id": "SB4yStgGFv", "reviewer": "Reviewer_jBg5", "summary": "This paper studies the statistical complexity of two restless multi-armed bandits (MABs) models: (1) restless rising bandits and (2) restless rising concave bandits. A rising bandits is a bandits that has non-decreasing rewards over time, while a rising concave bandits is the one that has non-decreasing and concave rewards over time. In this paper, the authors propose a generic lower-bound instance constructing method for restless MAB, by dividing  the time horizon into windows with base and modified trends that are hard to distinguish. \n\nGiven this, the authors prove a new lower bound at $\\Omega(T^{2/3})$ for restless rising bandits and $\\Omega(T^{3/5})$ for the concave one. Meanwhile, they introduce an RC-BE algorithm that achieves a O(T^{7/11}) upper bound for the concave bandit. Finally, numerical experiments are conducted for RC-BE against Rexp3, R-less-UCB and the classical UCB1 algorithms as baselines, where the former outperforms all of the latters.", "questions": "### Questions:\n\n1, Is the $K^{27/11}$ dependence on the upper bound relatively tight? I.e., is it a matter of algorithmic design or a matter of analysis?\n\n2, How will the performance change if the concavity is enhanced? I.e. will it be beneficial if the bandits reward is $\\alpha$-strongly concave (and as $\\alpha$ increases)? \n\n3, Is Lemma 3.1 able to be generalized to more bandits settings (for instance, non-stationary bandits as dynamic regret, or adversarial bandits)?\n\n### Suggestions:\n\nThe authors are not required to make any changes to their original submission or deliver more results during the rebuttal period, from my point of view. They are encouraged to revise according to the suggestions before submitting their camera-ready or resubmission versions.\n\n1, It would be better to plot the regret comparison diagrams on a log-log scale, where the slope represents the polynomial order dependence.\n\n2, Some typos to fix: e.g. Page 2 Line 39, “expected expected”. Also, the reference of Jia et al (2024) is missing (while an Arxiv reference of it exists at least).", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "### Strengths:\n\n1, This paper proposes novel methods to prove information-theoretic lower bounds on restless bandits. This is beneficial for the whole community of online learning, reinforcement learning, and ML theory in general.\n\n2, The authors propose an any-time practical algorithm that beats baselines that are commonly adopted. More importantly, it gets rid of pre-knowledge assumptions (w.r.t. $T$ and $V_T$) comparing to existing works.\n\n3, The paper is clearly written, with results rigorously delivered and well justified.\n\n### Weakness:\n\nThe main concern from my perspective is the regret dependences on $K$: On the one hand, the theoretical guarantee is $O(K^{27/11})$ w.r.t. $K$, which is far from the lower bound and intuitively far from optimal. On the other hand, the numerical experiments are only conducted on $K=5$, which is relatively small and also implies an undermine on the potential application to massive arms.\n\nBesides, the tuning of $\\gamma$ either requires pre-knowledge on $V_T$ or leads to a worse dependency (please correct me if I am wrong).\n\n**Note**: Although the regret gap is not closed on $T$, I do not consider it as a significant weakness since they have already improving the existing results substantially, and I agree to leave it for future study.", "was_revised": true, "final_justification": "The rebuttal clarifies most of my concerns. I am supporting to this paper as it extends the scope of multi-armed bandits with non-trivial and rigorous techniques.", "rebuttal": "We thank the Reviewer for the time spent reviewing our work and for having appreciated it. Below, our answers to the Reviewer's questions and comments.\n\n> Is the $O(K^{27/11})$ dependence on the upper bound relatively tight? I.e., is it a matter of algorithmic design or a matter of analysis?\n\nWe think that it is likely that, by employing a different analysis path, it would be possible to obtain a better dependence on $K$ without modifying the algorithm, but the current analysis strategy doesn't show significant room for improvement.\nIn particular:\n- The regret suffered by `RC-BE`($\\alpha$) in a window is upper bounded by $3 K B\\_w\\^{(\\alpha)} + \\Delta\\_w\\^{(\\alpha)} d\\_w^\\*$ (see Lemma 4.1). The presence of $K$ in the first term is due to the fact that each arm can consume its exploration budget. The second term also increases with $K$, indeed, the diameter $d_w^*$ (see lines 221, 222) scales with the size of $\\mathcal{I}_w^\\times$ (line 221), which is $K$ in the worst case.\n- The analysis relies on an upper bound to the number of times two non-decreasing concave curves with values in $[0, 1]$ can intersect, diverge by a quantity $G > 0$, and then intersect again. When the curves are more than two, the maximum number of intersections of this kind between any pair of curves increases with the number of curves $K$.\n\nFinally, we suspect that the dependence on $K$ is due in part to the algorithm itself because of its extensive round-robin phases. \n\n> The tuning of $\\gamma$ either requires pre-knowledge on $V_T$ or leads to a worse dependency.\n\nWe assume that $\\gamma$ is a typo, and that the Reviewer wants to refer to the hyperparameter $\\alpha$ of the `RC-BE`($\\alpha$) algorithm (please, correct us if this is not the case).\nUnder the choice $\\alpha = 8/3$, which doesn't require pre-knowledge of $V_T$, the dependence on $K$ is indeed worse ($O(K^3)$). Anyway, in a rising MAB (and thus also in a rising concave MAB), $V_T = K$ is always a valid upper bound to the cumulative increment $\\Upsilon_\\nu(1, T)$ and, under the choice $\\alpha = \\alpha''$ with $V_T = K$ (see Theorem 4.4) we get a better rate in $K$: $O(K^{24/11})$. Choosing $\\alpha = 8/3$ versus $\\alpha = \\alpha''$ with $V_T = K$ really depends on the relative scale of the quantities involved in the upper bound.\n\n> How will the performance change if the concavity is enhanced? I.e. will it be beneficial if the bandits reward is $\\alpha$-strongly concave (and as $\\alpha$ increases)?\n\nInstead of $\\alpha$-strong concavity, we considered other forms of enhanced concavity, although we did not include these results in the paper.\nIndeed, $\\alpha$-strong concavity conflicts with the non-decreasing assumption as $\\alpha$-strong concave curves need to be strictly decreasing for $t \\geq t_0$ for some $t_0 \\in \\mathbb{R}$.\nInstead, we studied a subclass of rising concave MABs in which the increments are further constrained to satisfy $\\gamma_i(t) \\leq t^{-a}$ for some $a \\geq 1$ (observe that every rising concave MAB with expected rewards bounded in $[0, 1]$ must satisfy the additional assumption with $a = 1$ since $\\gamma(t) \\leq (\\mu(t) - \\mu(1))/t \\leq 1/t$). In this setting, assuming the knowledge of $a$, it is possible to devise an algorithm with upper bound rate $\\widetilde{O}(T^{\\max\\{ 1/2, 1-a/3 \\}})$ which matches the lower bound for stationary MABs for $a \\geq \\frac{3}{2}$. However, we believe that the additional assumption is very restrictive. Furthermore, the algorithm shows the same regret upper bound ($\\widetilde{O}(T^{2/3})$) which holds for general restless MABs when $a = 1$ (which, as remarked before, is the standard rising concave MAB setting).\nWe're going to add these results in the final version.\n\n> Is Lemma 3.1 able to be generalized to more bandits settings (for instance, non-stationary bandits as dynamic regret, or adversarial bandits)?\n\nLemma 3.1 already holds for the whole class of non-stationary bandits with dynamic regret in the current form. It doesn't hold in the adversarial setting due to the fact that the regret is there defined differently by comparing the played action with the best fixed action in hindsight. \n\n> Suggestions and typos\n\nThank you, we will fix them."}, {"review_id": "HDs6Jbr4NV", "reviewer": "Reviewer_yLk5", "summary": "This paper proposes a general framework on the lower bound for the restless rising bandits and an algorithm that achieves a regret bound on restless rising concave bandits. The lower bound for the restless rising bandits matches the upper bound proven in previous works and the lower bound for the restless rising concave bandits discovers the degree of hardness of the problem.", "questions": "1. Could author provide a real-world example that motivates the model for the restless rising concave MAB bandits?\n\n2. Which techniques or derivations in the proof are newly developed in this work?\n\n3. What is the challening part of deriving a novel regret bound? What is the limitations of the previous works that could not improve the regret bound on the rising restless concave bandits?\n\n4. In eq (3), what is the definition of $w(T)$?\n\n\n**Minors**\n\nIn line 39, 'expected' is duplicated.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n1. The general lower bound (Lemma 3.1) covers a wide range of the restless rising MAB bandits.\n\n2.The upper bound shows an improvement over the previous work on the restless rising concave bandits and shows the interplay between the rising budget and the cumulative regret.\n\n**Weakness**\n\n1. It is not sure whether there is a novel techniques that overcomes the challenges of the previous works.\n\n2. It would be better to include a specific example for the restless rising bandits for concrete motivation.", "was_revised": true, "final_justification": "The authors response helped me understand the practicality of the model and the novelty of the technical derivations.", "rebuttal": "We thank the Reviewer for the time spent reviewing our work and for the positive feedback. Below, our answers to the Reviewers questions and concerns.\n\n> Could author provide a real-world example that motivates the model for the restless rising concave MAB bandits?\n\n**Example 1: Athlethes training**: Consider the scenario in which a coach must choose an athlete to call up for the next competition from those they train. Ideally, the coach would like to select the athlete with the highest expected performance in the group. However, this expected performance must be estimated from the history of each athlete’s past call-ups, by observing the actual performances which are affected by noise, as they depend on the athlete’s condition on the particular day. Finally, the expected performance of each athlete varies over time. Through training, it is reasonable to assume that it increases over the course of their career, though with a gradually diminishing rate, in line with the assumptions of non-decreasing and concave growth. This problem can be modeled as a restless rising concave MAB, where each athlete corresponds to an action and each competition to a round.\n\n**Example 2: Online Model Selection with Paraller Training**: In many applications, an AI-powered service (such as an LLM) is offered to a customer base. Every time a user interacts with the service, the interaction is logged and used to improve the service. In modern applications, it is common to train multiple models (using the same log of interactions) and to use, at inference time, the one that promises the better customer experience. While every model tends to improve with an increasing dataset, it is only possible to evaluate its current quality by letting it face an actual interaction with a user, that can then leave a feedback. In this scenario, every model represents an arm, and in every round a user arrives, interacts the selected model for that round, and leaves a feedback. This feedback allows all of the models to re-train and improve (restless rising dynamic), as they can learn from a new observation, but can only quantify the quality of the model that is currently running (bandit feedback).\n\n> It is not sure whether there is a novel techniques that overcomes the challenges of the previous works.\n\n> Which techniques or derivations in the proof are newly developed in this work?\n\n**Lower Bounds**: Lemma 3.1 provides a novel generalization of the construction used in Theorem 1 (Besbes et al., 2014) to derive the lower bound for the general restless setting. The scope of this generalization can go beyond this work and allows to construct lower bounds (Theorems 3.2 and 3.3) for generic subclasses of restless bandits. The instances used to derive the lower bounds for the rising and rising concave setting are novel (see Figures 1, 2). In particular, the instance used to construct the lower bound for the rising setting (Figure 1), modifies the abrupt changes in the optimal arm exploited by Besbes et al. (2014) to further satisfy the non-decreasing expected rewards assumption.\nInstead, the instance used to construct the lower bound for the rising concave setting (Figure 2) smooths the changes of the optimal arm, being in this way compliant with the additional assumption on the concavity of the expected rewards, while trying to keep significant suboptimality gaps.\n\n**Upper Bound**: The analysis of the proposed algorithm is novel and changes significantly from the analysis of the algorithm we choose as starting point. In particular, the use of equivalence relations obtained by taking the transitive closure of \"crossing\" relations is novel (see Regret Analysis in Section 4) and solves issues present in previous approaches (see Appendix F). The improvement in the upper bound rate for rising concave MABs is due to a novel approach which limits the number of times two non-decreasing concave curves with values in $[0, 1]$ can intersect, diverge by a quantity greater than or equal to $G > 0$, and then intersect again (see Lemmas C.8, C.9 and C.10 in Appendix C).\n\n> What is the challening part of deriving a novel regret bound?\n\nThe key insight, which allowed to derive a novel regret bound, is that the rising concave setting is easier w.r.t. the general restless setting since, under the non-decreasing assumption plus the concavity, it gets increasingly difficult for the optimal arm to change and diverge significantly. Our work exploited this observation, developing a bound to the number of times this can happen in the rising concave setting (see Lemma 4.3). \nThis bound has been obtained by studying an optimization problem (as anticipated in the answer to the previous question) which considers the number of times two non-decreasing concave curves with values in $[0, 1]$ can intersect, diverge by a quantity greater than or equal to $G > 0$, and then intersect again.\nThe main difficulty lies in reframing the regret bound as the aforementioned optimization problem. This process involves, among the other things, the transitive closure of \"crossing\" relations (cited in the previous answer), the definition of novel quantities like the diameter $d_w(i)$ (line 221), and the regret decomposition due to Lemma 4.1.\n\n> What is the limitations of the previous works that could not improve the regret bound on the rising restless concave bandits?\n\nPrevious works focused on devising ad-hoc optimistic estimators which exploit the concavity of the instance. Unfortunately, this approach has been unsuccessful since it is difficult to design estimators with a satisfactory bias-variance trade-off. \nIn particular, the estimator designed in (Metelli et al., 2022) tries to predict the evolution of the expected rewards curves with a linear affine projection built through an optimistic estimate of the values and the increments of the expected reward of an arm, in the rounds in which the arm has been pulled. This estimator doesn't exhibit desirable concentration properties as the projection is very sensitive to the noise in the increments estimates.\n\n> In eq (3), what is the definition of $w(T)$?\n\nThe function $w(t)$ is defined at line 123 as $w(t) : t \\mapsto \\min\\\\{ w \\in \\mathbb{N}_{\\geq 1} \\ \\text{s.t.} \\ e_w \\geq t \\\\}$ and represents the index of the window to which round $t$ belongs. Thus, $w(T)$ is the index of the last window in the considered time horizon $T$.\n\n> Typos\n\nThank you, we will fix them."}, {"review_id": "jslX3VMeyK", "reviewer": "Reviewer_W5ZX", "summary": "This paper considers an instance of non-stationary multi-armed bandits given by the following framework: There are $K$ arms; each arm $i \\in [K]$ has a time-varying mean $\\mu_i(t)$ in $[0,1]$. The samples observed by the learner are drawn from a $\\sigma$-subGaussian distribution. The objective is to minimize the expected regret with respect to a strategy that picks the arm with the minimal mean in each round $t$.\n\nThe authors assume a structure for the means. More precisely, they consider two cases:  \n(i) the case where the mean of each arm is increasing over the rounds, and  \n(ii) the case where the means are increasing while satisfying a concavity-like assumption.\n\nThe main contributions are threefold:  \n1. The authors derive a lower bound for the increasing means scenario.  \n2. A lower bound for the increasing concave means scenario.  \n3. An algorithm with upper bound guarantees for the increasing+concave means scenario.\n\nThe upper bound for the increasing+concave means case, in its dependence on the horizon $T$, is smaller than the lower bound for the increasing-only scenario, which shows that the concavity assumption impacts the optimal complexity of the problem.", "questions": "- Could you address the concern regarding the dependence on $V_T$? Removing the min would in my opinion improve the strength of the results.\n- Since the authors assume that the arms' means are in $[0,1]$ and the distributions are $\\sigma$-subGaussian, is it possible to make the dependence on $\\sigma$ explicit in the lower bound by considering, for example, normal distributions instead of Bernoulli?\n- Is there a way to bypass the need for prior knowledge of $V_T$ in the last bound of Theorem 4.4?", "limitations": "A discussion on the following points would benefit the reader: The threshold condition on $T$ for the last guarantee of Theorem 4.4 and the dependence on the number of arms of the guarantees of the same theorem.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**  \nThe paper gives a refinement of the framework of non-stationary bandits. The constructions of the distributions in the lower bounds especially for the increasing concave case are interesting and allow the authors to distinguish between the settings considered. The authors further adapt some existing ideas for algorithms and upper bounds by leveraging the assumed structure followed by the arms' means to derive bounds that are sharper in their dependence on the time horizon $T$.\n\n**Weaknesses:**\n- For the presented lower bounds, the main weakness is the dependence of the lower bound on the total variation $V_T$. Prior works, such as Besbes *et al.*, have a lower bound of order $V_T^{1/3}$, while the authors derive a lower bound of order $\\min(1, V_T)^{1/3}$ for the rising case and $\\min(1, V_T)^{1/5}$ for the rising and concave case. This difference is important, as it can create a gap when $V_T$ grows like $T^\\alpha$. \n- The dependence of the upper bounds on the number of arms $K$ is worse than known results for standard and non-stationary MAB problems.\n- On the terminology used: to the best of my knowledge, the term *rising bandits* is used in the literature for a different type of framework, where the change in the means of the arms happens when the arms are pulled (which corresponds to the rested bandits setting). In contrast, the authors consider a *restless bandits* setting, where the arms' means change regardless of whether they are queried. If I am correct, I suggest the authors address this point, as it may be confusing to readers.\n- Line 123: The comparison is not fair because in Besbes *et al.* no prior knowledge is required.\n- Please modify the related work section in the appendix, as it is very similar to an existing one.\n\n**Minor remark:**  \nLine 84: The considered definition corresponds to $\\sigma$-subGaussian rather than $\\sigma^2$-subGaussian.", "was_revised": true, "final_justification": "The main concerns about this paper were addressed in the rebuttal.", "rebuttal": "We thank the Reviewer for the time spent reviewing our work. Below, our answers to the Reviewer's questions and comments.\n\n> For the presented lower bounds, the main weakness is the dependence of the lower bound on the total variation $V_T$. Prior works, such as (Besbes et al., 2014), have a lower bound of order $V_T^{1/3}$, while the authors derive a lower bound of order $\\min(1, V_T)^{1/3}$ for the rising case and $\\min(1, V_T)^{1/5}$ for the rising concave case. This difference is important, as it can create a gap when $V_T$ grows like $T^\\alpha$.\n\n> Could you address the concern regarding the dependence on $V_T$? Removing the $\\min(\\cdot)$ would in my opinion improve the strength of the results.\n\nIn the rising setting (and thus also in the rising concave setting), the cumulative increment $\\Upsilon_\\nu(1, T)$ is always smaller or equal to $K$ (see Instances Characterization in Section 2). Hence, the variation budget $V_T$ is always chosen smaller than or equal to $K$. This implies that it is not possible for $V_T$ to grow like $T^\\alpha$ (for sufficiently large $T$), making the dependence on $T$ in the lower bounds unaffected by the $\\min(\\cdot)$.\n\n> The dependence of the upper bounds on the number of arms $K$ is worse than known results for standard and non-stationary MAB problems.\n\nWe agree with the Reviewer on the fact that the algorithm has a worse dependence in $K$.\nWe think that this is partly due to the analysis, which, however, doesn't show significant margin of improvment.\nIn particular:\n- The regret suffered by `RC-BE`($\\alpha$) in a window is upper bounded by $3 K B\\_w\\^{(\\alpha)} + \\Delta_w\\^{(\\alpha)} d\\_w^\\*$ (see Lemma 4.1). The presence of $K$ in the first term is due to the fact that each arm can consume its exploration budget. The second term also increases with $K$, indeed, the diameter $d_w^*$ (see lines 221, 222) scales with the size of $\\mathcal{I}_w^\\times$ (line 221), which is $K$ in the worst case.\n- The analysis relies on an upper bound to the number of times two non-decreasing concave curves with values in $[0, 1]$ can intersect, diverge by a quantity $G > 0$, and then intersect again. When the curves are more than two, the maximum number of intersections of this kind between any pair of curves increases with the number of curves $K$.\n\nIt is likley, that the dependence is also partly due to the algorithm itself, because of the extensive round-robin phases.\nHowever, we believe that the improvement in the dependence on $T$, under the customary implicit assumption $K \\ll T$, gives us a better overall result compared to the state of the art. We will add a discussion on this in the updated version of the paper and the improvement of the dependence on $K$ among the future works.\n\n> On the terminology used: to the best of my knowledge, the term rising bandits is used in the literature for a different type of framework, where the change in the means of the arms happens when the arms are pulled (which corresponds to the rested bandits setting). In contrast, the authors consider a restless bandits setting, where the arms' means change regardless of whether they are queried. If I am correct, I suggest the authors address this point, as it may be confusing to readers.\n\nThe term \"rested\" is used for bandits in which the expected reward changes only when the arm is pulled, while the term \"restless\" is used to consider the case in which the arm expected rewards evolve as a function of time (a.k.a. non-stationary setting). The term \"rising\" (Metelli et al., 2022) is used for all kinds of bandits in which the expected rewards are non-decreasing, being they restless or rested. In this work, we focus on restless rising bandits (as in the title), and use the term rising bandits, without the adjective restless, only after the setting has been carefully defined (see line 90).\n\n> Line 123: the comparison is not fair because in (Besbes et al., 2014) no prior knowledge is required.\n\nThe reference to line 123 is likely incorrect, since in such line there is no comparison with (Besbes et al., 2014). We believe that the Reviewer wants to refer to line 183 (please correct us if this is not the case). However, we want to highlight two facts:\n- `Rexp3` (Besbes et al., 2014) does require prior knowledge of $V_T$ to obtain the $O(T^{2/3} V_T^{1/3})$ rate (see Theorem 2 of (Besbes et al., 2014), where hyperparameter $\\Delta_T$ and by consequence $\\gamma$ are chosen as a function of $V_T$).\n- Our algorithm allows to obtain a better regret without the knowledge of $V_T$ by choosing hyperparameter $\\alpha$ in two different ways: either $\\alpha = 8/3$ or $\\alpha = \\alpha''$ with $V_T = K$ (see Theorem 4.4), since, as remarked in one of the previous points, $K$ is always a valid upper bound to the cumulative increment.\n\n> Please modify the related work section in the appendix, as it is very similar to an existing one.\n\nWe thank the Reviewer for the comment. We updated the manuscript by rephrasing parts of the related works section.\n\n> Line 84: the considered definition corresponds to $\\sigma$-subGaussian rather than $\\sigma^2$-subGaussian.\n\nWe thank the Reviewer for the comment. We updated the manuscript.\n\n> Since the authors assume that the arms' means are in $[0, 1]$ and the distributions are $\\sigma$-subGaussian, is it possible to make the dependence on $\\sigma$ explicit in the lower bound by considering, for example, normal distributions instead of Bernoulli?\n\nYes, it would be possible to use Gaussian distributions, but it would require significantly modifying the proof.\nIndeed, the analysis relies on the fact that the Bernoulli distribution has a discrete support. This allows to define some probability density functions (see Appendix B, p. 13) by directly evaluating the probability measures of interest at specific points. With continuous supports instead, Radon-Nikodym derivatives are needed. A smarter approach to make $\\sigma$ appear in the lower bound, would involve considering another distribution with discrete support, with, for instance, the following structure:\n\n$$\nf(\\\\mu, \\\\sigma) := \\begin{cases}\n\\frac{3}{2} \\sigma & \\text{w.p.} & \\frac{1}{4} + \\frac{\\mu}{2 \\sigma} \\\\\\\\\n-\\frac{1}{2} \\sigma & \\text{w.p.} & \\frac{3}{4} - \\frac{\\mu}{2 \\sigma}\n\\end{cases}\n$$\n\nwhere $\\mu \\in [0, 1]$ is the **expected value** and $\\sigma \\geq 1$ the **subgaussianity constant** (in virtue of Hoeffding's lemma). Observe that $\\mu \\in [0, 1]$ and $\\sigma \\geq 1$ guarantee that the above distribution is well defined.\nIn this way, all the arguments of the proof still hold (since they depend on the fact that the support is discrete and not on the actual values in it), furthermore, by means of Lemma D.1 (which again holds also for $f(\\mu, \\sigma)$ since it depends only on the fact that the cardinality of the support is $2$), it is possible to obtain an upper bound to the KL divergence of these new distributions which has the same structure of the KL divergence of two Gaussians with standard deviation $\\sigma$, allowing to obtain the desired dependence on $\\sigma$ in the lower bound.\nWe thank the Reviewer for the constructive comment, as it allows to improve our work. We will add a remark on this in the final version.\n\n> Is there a way to bypass the need for prior knowledge of $V_T$ in the last bound of Theorem 4.4?\n\nThe goal of the second bound in Theorem 4.4 is exactly to show that a better rate can be obtained when the knowledge of a tight upper bound for $\\Upsilon_\\nu(1, T)$ in the form of a variation budget $V_T$ is available. Indeed, the exponent to the term $\\Upsilon_\\nu(1, T)$ in the first bound is $1$. Under the assumption $\\Upsilon_\\nu(1, T) \\leq V_T$, $\\Upsilon_\\nu(1, T) \\approx V_T$, we get a better rate in the second bound. When the knowledge of a tight upper bound $V_T$ is not available, we can resort to the choices $\\alpha = 8/3$ or $\\alpha = \\alpha''$ with $V_T = K$ (see Theorem 4.4), which allow to obtain still the same rate in $T$.\n\n> A discussion on the following points would benefit the reader: the threshold condition on $T$ for the last guarantee of Theorem 4.4 and the dependence on the number of arms of the guarantees of the same theorem.\n\nThe additional requirement on $T$: $T \\geq \\max\\\\{ K^{-8/3} V_T^{-4/3} + 1, K^{16/5} V_T^{8/5} \\\\}$ present in the second bound of Theorem 4.4 guarantees $\\alpha'' \\geq 1$ (as specified in the proof of Theorem 4.4 in Appendix C) so that it is possible to apply the first part of the theorem. We will add a footnote in the main paper to highlight this fact.\nThe fact that the second guarantee of the theorem requires a threshold on $T$ which depends on $K$ doesn't undermine the validity of the result, since the aim is to study the asymptotic behavior of the regret as $T$ grows, while other quantities (like $K$) are treated as constants.\nFurthermore, we are able to obtain the same rate of $\\widetilde{O}(T^{7/11})$ in $T$ with the first bound which doesn't have such requirement."}, {"review_id": "efr6KmmxMN", "reviewer": "Reviewer_w3Bt", "summary": "The rising and rising concave restless MAB setting is considered. The previous best lower bound for both settings was $\\Omega(T^{1/2})$. This work improves the lower bound to $\\Omega(T^{3/5})$ for the rising concave setting and to $\\Omega(T^{2/3})$ for the rising setting. The previous best upper bound for the rising setting was $O(T^{2/3})$, which matches the newly shown lower bound, while the best upper bound for the rising concave setting was $O(T^{2/3})$. This work improves the upper bound in the rising concave setting to $\\tilde{O}(T^{7/11})$, which nearly matches the new lower bound. Experiments are provided that support the theoretical results.", "questions": "Please see the Weaknesses above.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Quality**\n\n*Strengths*\n1. The definitions and results in the body are all well defined. I have not checked the appendix; however, it does seem that the analysis follows common strategies used in previous work, which makes it likely to be correct.\n\n**Clarity**\n\n*Strengths*\n1. Setting is clearly defined and results are easy to follow, especially due to the nice table.\n\n*Weaknesses*\n1. After Theorem 3.2 it is mentioned that the lower bound matches the upper bound when $V_T \\le 1$ since it is assumed that $\\Gamma(1, T) \\le 1$ in the lower bound. Does this imply that if $V_T > 1$ then the lower bound does not hold and the previous lower bound of $\\Omega(T^{1/2})$ would have to be used in that case? Is this assumption critical for your lower bound construction to go through, and if so can it elaborated on why you believe it is just an artifact of the analysis?\n\n**Significance**\n\n*Strengths*\n1. The paper provides improved lower bounds for the rising and rising concave restless MAB problems. It also provides an improved upper bound for the rising concave setting. The lower and upper bounds match in the rising setting and they almost match in the rising concave setting, which is a significant contribution.\n\n**Originality**\n\n*Weaknesses*\n1. It would be helpful if the lower bound construction used to arrive at Lemma 3.1 could be compared to previous construction of Besbes et al. 2014. In particular what was the insight or change in the technique that allowed for the improved bounds. Currently it is unclear if the entire construction is novel or if only a specific modification was made that was very useful.", "was_revised": true, "final_justification": "The authors have addressed my concerns. I think this paper is a significant contribution as it almost gets the optimal rate in a setting that is of interest by many other researchers.", "rebuttal": "We thank the Reviewer for the time spent reviewing our work and for having appreciated it. Below, our answers to the Reviewer's questions and comments.\n\n> After Theorem 3.2 it is mentioned that the lower bound matches the upper bound when $V_T \\leq 1$ since it is assumed that $\\Upsilon_\\nu(1, T) \\leq 1$ in the lower bound. Does this imply that if $V_T > 1$ then the lower bound does not hold and the previous lower bound of $\\Omega(T^{1/2})$ would have to be used in that case? Is this assumption critical for your lower bound construction to go through, and if so can it elaborated on why you believe it is just an artifact of the analysis?\n\nWhen $V_T > 1$, $\\min\\\\{ V_T, 1 \\\\}$ evaluates to $1$ and the lower bounds become $\\Omega(T^{2/3} K^{1/3})$ and $\\Omega(T^{3/5} K^{2/5})$ for the rising and rising concave settings, respectively. Observe that, in the rising (and thus also in the rising concave) setting $V_T \\leq K$, thus, even when $V_T > 1$, the dependency on $T$ in the lower bound is not affected. In order to build the lower bounds, we generalized the approach used in (Besbes et al., 2014), where the time horizon is split in windows, in each window, one arm, chosen at random, is promoted to optimal, while all the suboptimal ones share the same expected rewards. An instance with this structure which further satisfies the non-decreasing expected rewards assumption and has expected rewards bounded in $[0, 1]$, has necessarily the cumulative increment $\\Upsilon_\\nu(1, T) \\leq 1$ (see Figure 1). Intuitively, in order to get a certain value of variation budget $V_T$ in the lower bound, you need to construct a \"difficult\" instance which \"consumes all the budget\", i.e., $\\Upsilon_\\nu(1, T) = V_T$. Since $\\Upsilon_\\nu(1, T) \\leq 1$, this is not possible when $V_T > 1$. This is why we believe that it is an artifact of the analysis.\n\n> It would be helpful if the lower bound construction used to arrive at Lemma 3.1 could be compared to previous construction of (Besbes et al., 2014). In particular what was the insight or change in the technique that allowed for the improved bounds. Currently it is unclear if the entire construction is novel or if only a specific modification was made that was very useful.\n\nLemma 3.1 is a generalization of the construction used in Theorem 1 (Besbes et al., 2014) which carries a certain amount of novelty and is of independent interest (outside of the context of restless rising bandits) since it allows to construct lower bounds for general subclasses of restless MABs.\nIn particular, as it has been partially anticipated in the previous answer, the challenging instance used in (Besbes et al., 2014) to derive the lower bound has the following structure. The time horizon is split in windows; in each window, one arm, chosen at random, is promoted to optimal and has expected reward equal to $\\frac{1}{2} + \\varepsilon$, while all the suboptimal ones share expected reward equal to $\\frac{1}{2}$. This construction produces a class of instances with no particular structure since the expected reward of each arm can either increase, decrease, or stay constant between one window and the next, depending on the sequence of optimal arms. Thus, it is difficult to inject further assumptions on the evolution of the expected rewards (like non-decreasing or concave).\nLemma 3.1 generalizes the approach introducing in each window two functions: the base trend $\\overline{\\mu}_w$, which specifies the evolution of the expected rewards of suboptimal arms, and the modified trend $\\widetilde{\\mu}_w$, which specifies the evolution of the expected reward of the optimal arm (which is still chosen at random, in each window). By carefully choosing the base and modified trends in each window, it is possible to construct a class of instances which satisfies the desired additional assumptions (e.g., see Figures 1, 2).\nAt this point, Theorem 1 (Besbes et al., 2014) becomes a special case of  Lemma 3.1 that allows to derive the exact same lower bound by choosing base trend $\\overline{\\mu}_w(t) = \\frac{1}{2}$ and modified trend $\\widetilde{\\mu}_w(t) = \\frac{1}{2} + \\varepsilon$ in each window."}]

Author rebuttal:

Meta-review: The paper studies the problem of restless rising bandits, in which all arms improve over time (that is, their average return increases). They first provide a lower bound of $\Omega(T^{2/3})$, matching existing upper bounds for this problem. They then analyze the problem when arm means are concave (reward improvement decreases over time) and prove lower bounds of $\Omega(T^{3/5})$. They complement this bound with an upper bound of $\tilde{O}(T^{7/11})$, showing that the concave case is separated from both the stationary setting (where an $O(\sqrt{T})$ regret is achievable) and the general rising setting.

The reviewers agreed that the problem is well-motivated, the paper is well-written and that all the aforementioned contribution are significant and might be generalized to other similar settings. The main weakness raised by the reviewers is the sub-optimal dependence of the bounds on the number of arms $K$, but this is only a minor weakness.
Decision: Accept (poster)