Non-Stationary Bandits with Auto-Regressive Temporal Dependency
Authors: Qinyi Chen
Negin Golrezaei
Djallel Bouneffouf
Venue: NeurIPS 2023 poster (2023)
Keywords: non-stationary bandits; autoregressive model; low-regret policy; online learning algorithms
TL;DR: We introduce a novel non-stationary MAB framework with an autoregressive reward structure to encapsulate real-world dynamics, and propose an algorithm that achieves near-optimal regret while demonstrating good numerical performance.

Abstract: Traditional multi-armed bandit (MAB) frameworks, predominantly examined under stochastic or adversarial settings, often overlook the temporal dynamics inherent in many real-world applications such as recommendation systems and online advertising. This paper introduces a novel non-stationary MAB framework that captures the temporal structure of these real-world dynamics through an auto-regressive (AR) reward structure. We propose an algorithm that integrates two key mechanisms: (i) an alternation mechanism adept at leveraging temporal dependencies to dynamically balance exploration and exploitation, and (ii) a restarting mechanism designed to discard out-of-date information. Our algorithm achieves a regret upper bound that nearly matches the lower bound, with regret measured against a robust dynamic benchmark. Finally, via a real-world case study on tourism demand prediction, we demonstrate both the efficacy of our algorithm and the broader applicability of our techniques to more complex, rapidly evolving time series.

Non-Stationary Bandits with Auto-Regresse Temporal Dependency
Qinyi Chen
Negin Golrezaei
Operations Research Center Massachusetts Institute of Technology qinyic@mit.
Sloan School of Management
Massachusetts Institute of Technology
golrezae@mit. edu
Djallel Bouneffouf
IBM Research
djallel. ouf 8ilm. com
Abstract
Traditional multi-armed bandit (MAB) frameworks, predominantly examined under stochastic adversarial settings, often overlook the temporal dynamics inherent in many real-world applications such recommendation systems and online advertis- ing. This paper introduces a novel non-stationary MAB framework that captures the temporal structure of these real-world dynamics through an auto- auto-regressive (AR) reward structure. We propose algorithm that integrates two key mecha- nisms: (i) an alternation mechanism adept at leveraging temporal dependencies dynamically balance exploration and exploitation, and (ii) a restarting mechanism designed to discard out-of-date information. Our algorithm achieves a regret upper bound that nearly matches the lower bound, with regret measured against robust dynamic benchmark. Finally, via a real-world case study on tourism demand prediction, we demonstrate both the efficacy of our algorithm and the broader applicability of our techniques more complex, rapidly evolving time series.
Introduction
The multi-armed bandit (MAB) framework [51 46 is commonly used to study online decision-
making under uncertainty. is primarily examined under either the stochastic setting [51] 6
where
arms have fixed unknown reward distributions, or the adversarial setting 7 31 16], where an
adversary determines the reward distributions that can change arbitrarily over time. However, neither
setting accurately represents real-world decision-making problems (see examples in dynamic pricing
[30. online advertising [42]. and online auctions (33). where reward distributions change over time following intrinsic temporal structures. These structures often exhibit frequent variations and temporal dependencies, making them challenging to approximate using stationary distributions.
This motivates us to consider a non-stationary bandits setting involving certain temporal structure, which captures the real-world characteristies. Specifically, we are interested in temporal structures with linear amount of changes, which are distinct from the infrequent, limited changes typically handled by change-point detection (25) or seasonality analysis [15). Such frequent changes are commonly observed in applications such as financial data [14] and click-through rates in online advertising (2]. where the data experience lots of volatility within short time. Traditional bandits algorithms, such as Thompson sampling or UCB, may explore too aggressively in response to these drastic changes, leading to suboptimal performance (39]. That being said, the observed time series in these scenarios typically exhibit certain temporal dependencies between past and present, which can be leveraged to improve Deeisionnmmaknng
To encapsulate the main characteristics of real- world time series, we relax the previously restrictive assumptions on the reward distributions and study non-stationary MAB problem, where the reward
37th Conference on Neural Information Processing Systems (NeurIPS 2023).

---

of each arm evolves over time following an auto-regressive (AR) temporal structure. The AR model is popular time series model for predicting outcomes in applications such as sales [47], advertising M and marketing [8]] simultaneously captures frequent changes (i.e., linear amount of changes over the time horizon) and temporal dependencies, both of which impact the quality of online decision- making. Although real-world data cannot be perfectly represented by an AR model, it has been shown that the AR parameters accurately capture temporal dependencies and can serve as a useful proxy [47 The non-stationary bandits framework with an AR reward structure can effectively model a wide range of real-world applications, including:
(1) recommendation systems, where MAB can determine the best product/contents display to users, while the AR model captures the evolution of user preferences and demand over time [2] (see Section for a related case study on tourism demand prediction); (2) online advertising, where MAB adjusts budget allocation for ad campaigns, and the AR model can capture the evolution of click-through rates of ads. The amount of changes are usually linear in
time, making the AR structure a potential modeling choice [2];
(3) financial portfolio management, where MAB can determine the investment allocation, and the
AR model can capture the evolution of returns for each investment/asset 19].
When making online decisions in the presence of frequent changes, traditional methods that are designed for stationary or adversarial settings can be ineffective, due to two main challenges.
1. Balancing exploration and exploitation becomes more challenging, as complete exploration is often unattainable. Continuous exploration is crucial, but there is also a risk of over- exploratto.... Therefore, finding the right balance becomes essential in navigating this tradeoff effectively.
2. Frequent changes in the environment can significantly diminish the value of past learnings. Failing to promptly leverage the knowledge we have gained can lead to a swift deterioration in our confidence levels regarding the accuracy of our reward estimates.
The goal of this work is to show, via non- stationary bandits framework with an AR reward structure, that effectively leveraging knowledge of temporal structure can address these challenges. In our approach, we would use our knowledge or estimates of the temporal dependency, measured by the AR parameter. Since non- -tatstiiioaay bandits with temporal structures exhibiting such real real-world characteristics have been scarcely explored in the literature, we consider the AR structure a suitable starting point for showcasing key ideas and techniques. We anticipate that this work will inspire future research on bandits with alternative temporal structures with similar features.
1.1 Main Contributions
We present an algorithm for the non-stationary AR bandits, called AR2, which stands for "Alternating and Restarting" algorithm for non-stationary "AR" bandits. AR2 features two mechanisms: (i) an alternation mechanism that handles the first challenge above by enforcing exploitation at least every other round, and switch to exploration only when we discover an arm with potential, instead of simply adopting the principle of "optimism in the fact of uncertainty" which can lead to ever-exploration. (ii) a restarting mechanism that handles the second challenge by discarding unnecessary information when our confidence level deteriorates significantly, which balances second tradeoff known as "remembering". "arriingtand""foogeettt""" "forgetting": this tradeoff is crucial even for time series with limited changes [10]. Overall, our work addresses an important gap in the literature by studying non-stationary bandits with temporal structure that exhibit frequent changes and temporal dependency. While the AR structure does not capture all temporal structures in the real world, we believe that our high-level messages and techniques will guide future research on bandits with other temporal structures.
In evaluating the performance of our algorithm, we employ the concept of per-round steady state dynamic regrer (Definition 2. This metric serves as a robust dynamic benchmark that competes with the best arm in each round. It surpasses the static benchmark used in stochastic and adversarial MAB, making a considerably stronger measure of performance. We provide an upper bound on the regret of AR2 (Theorem 5.2). for which the analysis is rather intricate (Section 6). and show that it almost matches the regret lower bound (Theorem 3.1). Our lower bound result also characterizes the challenges embedded in AR temporal processes, as shows the per-round dynamic regret does not go to zero as T increases, implying that any algorithm needs to keep exploring over time.
Finally, we conduct a real-world case study on tourism demand prediction [36] in Section 7 con- firming the superiority of AR2 compared to benchmark algorithms. There, we also show that the techniques and high-level ideas of our algorithm can be readily extended to handle more complicated, rapidly changing temporal structure (e.g., general AR-p processes) while still achieving good perfor- mance. Our case study is complemented by synthetic experiments in Appendix A which show the strength of AR2 against number of benchmarks designed for stationary and sta-soaiionary settings.

---

1.2 Related Work
Our work, which focuses MAB with an AR temporal structure, contributes to the stationary MAB literature that draws attention in recent years. Most related works on non-stationary bandits focused on either the rested bandits [26] or restless bandits [53]. In rested bandits, only the expected reward of the arm that is being pulled will change, while in restless bandits, the expected reward of each arm changes at each round according
known yet arbitrary stochastic process, regardless of whether the arm is pulled. Recently, there has also been a third stream of literature that studies non-stationary bandits where the changes in reward distributions depend on both which arm is pulled and the time period that passes by since its last pull (see, c.g. [32 [3). The non-stationary bandit problem that we study belongs the restless setting, since the reward distributions change each
round based on AR processes, independent of our actions. Restless bandits, however, is known to be difficult and intractable [43. and many work thus focus on studying its approximation [28 or relaxation (9]
One line of closely related work on restless bandits studies non-stationary MAB problems with limited
amount of changes. These works either assume piecewise stationary rewards (see 25 37
[2),,
)), or
impose a variation budget on the total amount of changes (see [TO). They differ from our setting in that they rely on the amount of changes in the environment to be sublinear in T, while in AR
processes, changes are more rapid and linear in T. Another line of relevant research on restless bandits
assumes different types of temporal structures for the reward distributions. See, e.g.. [38 41 50 40
for anite-state Markovian processes, (27) for stationary e-mixing processes and [48] for Brownian
processes, which is a special case of an AR model but does not experience the exponential decay in the correlation between the past and the future. Recently, (39 proposed predictive sampling algorithm that can also be applied to AR-1 bandits; their main focus, however, is to show the algorithm's 's superiority over the traditional Thompson sampling algorithm in non-stationary environments.
Similar to the second line of works above, our work also aims to exploit the temporal structure of the reward distributions devise well-performing learning algorithms. However, the AR process much more unpredictable than the temporal structures studied previously, due to its infinite state space and the fast decay in the values of the past observations. We are thus prompted to take different approach that is designed specifically for adapting to the rapid changes attributed to the AR process.
2 Preliminaries
Expected rewards. Consider a non-stationary MAB problem with & arms over T rounds. The state (expected reward) of arm E [k] at any round & [T] is denoted by (t). where rx(() E [- +R. Conditioned on the state (t), the realized reward of arm at round t, denoted by (t), is given by (2(1) = r:(()) + <<()), where (t()) ~ N(0, ar) is independent across arms and rounds and we call E (0, 1) the stochastic rate of change. More generally, if each arm i E [k] has different, unknown stochastic rate of change o; as long as we have an upper bound o 2 max; as, all of our theoretical results naturally carries over with the same dependency on a.
Evolution of expected rewards. The expected reward of each arm i E r(), evolves over time. In our model, we assume that rt()) undergoes an independent AR-1 process:
+ ra(l + +()r(((++())))))
(()
or equivalently. Rt + 1) aR,(t) - +t where a E (0, the parameter of the AR-1 model and can be used as a proxy to measure temporal correlation over time. As a increases, the temporal correlation increases. As commonly seen in the bandit literature (e.g.. (55). we make the rewards bounded by truncating (1 1) when its absolute value exceeds some finite boundary value
R >>000 O. That is, rt + 1) B (()(r.(t) + et())) where B(y)) min(max' (v. )) R}.
Here, we assume that the AR parameter a is known to the decision maker, a common assumption in literature 10 27 48) and often justifiable in real-world scenarios where sufficient historical data enables accurate fitting of AR models (see Section 7 This assumption is made to simplify the analysis. However, in Section g we would show that this assumption can be relaxed, and the AR parameter can be effectively esumated via maximum likelihood estimation.
We also assume here that all arms share the same AR parameter a. As our numerical studies in Appendix and Section 8 suggest, this assumption can be relaxed too. There, we generalize our model by considering heterogeneous AR parameters a; for each arm i E [k), and our algorithm maintains its performance. Nonetheless, it worth noting that the homogeneity of AR parameter can be justified in some applications. One example can be seen in our case study in Section [ where a travel agency offers vacation packages to travelers originating from particular origin and heading
3

---

to specific destination. In this scenario, the demand is modeled as a general AR-4 process, with the AR parameters being consistent across all arms. This is because the temporal correlation here is primarily determined by exogenous factors related to the travel route, such as popular attractions and the availability of flights between the two locations, hence impacting all arms in the same way.
Feedback structure and goal. Our goal is to design an algorithm that obtains high reward, against a strong dynamic benchmark that in every round 4, pulls an arm that has the highest expected reward. This benchmark much more demanding than the time-invariant benchmark used in traditional MAB literature. Obtaining good performance against the dynamic benchmark is particularly challenging as in any round t (T), only the reward of the pulled arms can be observed. Not being able to observe the reward of unpulled arms in dynamic and lime-varying environments introduces missing values in the AR process associated with arms. This, in turn, deteriorates the prediction quality of the future expected rewards and the performance of any algorithm that relies on such predictions (see [3] for a work that studies the impact of missing values on the prediction quality in AR processes).
We now formally define how we measure the performance of any non-anticipating algorithm. Definition 2.1 (Dynamic steady state regret). Let A be a non-anticipating algorithm that, at each round E (T), pulls arm I based on the history (11, Bi......l Jt-1,, R where Ry = R1, (t) is the observed reward at round t' t. The dynamic regret of A at round t defined as
A() (t) (t),
where (+) (ax is the maximum expected reward round t. Furthermore, the per-round steady state regret of algorithm A is defined as
T Σ
REGA= = lim sup
E T-000
REG A(t)
T
We remark that in Definition 2.1 our per-round regret is defined asymptotically mainly because we would like to focus on evaluating the steady state performance of our algorithm (i.e., under the steady state distribution) All of our theoretical analyses for regret lower bound (Section 3 and upper bounds (Section 5 also performed under the steady state distribution.
In this work, we would like design an algorithm with small per-round steady state regret, where the per-round regret is a function of the stochastic rate of change (a) and the temporal correlation (a).
3 Regret Lower Bound
We now provide a lower bound on the best achievable dynamic per-round steady state regret. Theorem 3.1 (Regret Lower Bound), Consider non-stationary MAB problem with k arms, where the expected reward of each arm evolves as an independent AR-I process with parameter a, stochastic rate of change a and truncating boundaries [-R, B]. Then the per-round steady state regret of any algorithm A is at least [ig(k, at, a )) where g(k, Ot, o)) is the probability that two best arms are within aα distance of each other at any given round, under the steady state distribution. See the expression of this probability in Equation (16) in Appendix
The proof of Theorem3 3.1
provided in Appendix F builds on the following idea: even if algorithm A has access to all past information at round f, due to stochastic noise e, et),, A will pull sub-optimal arm with constant probability round f 1. We show that the probability of the two best arms' expected rewards being within aa of each other can be expressed as g(k, a, a) (see (66) If the two best arms ad close, A will incur 2(ar) regret with constant probability at round
In the extreme case when is close to one, the steady state distribution of rt()) can be approximated with a uniform distribution within the boundaries and two probability masses at the boundaries (see Appendix DD. Using the uniform approximation, one can show that g(k, a, (,,)). = 2(kkrr) (see discussion in Appendix F. This then yields a regret lower bound of order ((ka²
Theorem 3.1 implies that under our setup, the best achievable per-round regret with respect to a strong dynamic benchmark does not converge to zero, which differs from stationary or adversarial
If we assume that the initial state r0) is drawn from the steady state distribution. defined in Appendix D 1 REG A [t)] and all of our results remain valid.
we can simply define our per-round regret as REG م = E Σ
This also matches the definition of dynamic regret in works such as [10 [1] (39
See, also, Appendix E.1 for illustration of how g a, σr) evolves with respect under different

---

Algorithm 1 Alternating and Restarting algorithm for non-stationary AR bandits (AR2)
Input: AR Parameter a, stochastic rate of change epoch size Asp, parameter co.
1. Set the epoch index = 1, parameter
24co.
Repeat while 8 [T/Aup]:
(a) Initialization: Set tu = (s - 1) Set the initial triggered set T 0. Pull each arm E [k] at round to + Set estimates (l + l + t-t (la + i)).
to + and set
(b) Repeat for f = to + (A + I)...., min(to + Aep. T}
Update the identity of the superior arm and its estimated reward
1--1 if fi (t) 2 f1.-a(1) (t) if 1 (t)
kuu (t)
-
T--2
and Pap(t) = (t)
(I)
Trigger arms with potential: For i $ T U { ( (f) trigger arm i if
Pap (t) S e1 (a2 a 22(0 a?))
(2)
If triggered, add i to T and set siz f.
Alternate between exploration and exploitation:
If / is odd and T * 0. pull a triggered arm with the earliest triggering time: 1, = arg min
Otherwise, pull the superior arm Lt = it)(t).
Receive reward Rr, (t), and set 71, = t.
Maintain Estimates: Set Fr, (t + 1) (a (f)) and set (t 1) = (t) for i
(c) Set s s+L. 1.
bandits with iiee-inariant benchmark where algorithms like UCB for stationary bandits and Exp3 for adversarial bandits can achieve zero per-round regret as 'I' approaches infinity, In our setting, each arm undergoes linear amount of changes, making it challenging for any algorithm to adapt to the changing environment in time. Our result aligns with the lower bound from [10), which states that when the total variation of expected rewards is OTT), the regret also grows linearly.
4 Algorithm AR2
In this section, we present our algorithm, called AR2 (Altemating and Restarting algorithm for non- stationary "AR" bandits). Algorithm| foutlines the workings of AR2, which operates in epochs of fixed length. Within each epoch, AR2 maintains and updates estimates of the expected rewards for each arm i E [k]. It alternates between exploitation and exploration steps based on these estimates. During exploitation, AR2 plays a "superior arm" expected to yield high rewards, while in exploration, selects a "triggered arm" that hasn't 't been pulled recently but has high potential. At the end of an epoch, the algorithm restarts. As alluded earlier, AR2 effectively balances two inherent tradcoffs in non-stationary MAB problems with AR reward structure. Firstly, it addresses the exploration- exploitation tradeoff by alternating between exploiting the superior arm and exploring the triggered arm within each epoch. Secondly, it handles the tradeoff between "remembering" -andiing"""add-ooooooao "nno"ffogetting". a commonly considered tradeoff in non-stationary environments 10 [1].
via restarting.
Maintaining estimates of expected reward of arms. For any round l. and arm i E [M]. let (1) be the last round before t (including 1) at which arm is pulled, and let 7 7.mext (f) be the next round after t (excluding t) at which arm i is pulled. Let (t; 7.ext(tt Tt()) be the gap between two consecutive pulls of arm i around f. Define (t) as the estimate of the reward of arm at based on
the most recent observed reward of arm i (i.e., R; (f))))). Via recursive updates (see Step (b)), AR2 maintains the following estimate of expected reward for each arm:
(t) = a F + 1) = a (000--11-1-- ((B.
Superior arms. The superior arm at round t, denoted by is))(t). is one of the two most recently pulled arms, i.c., 4-11 or 1,-2, that has the higher estimated reward (see (I)). We further define (sup(t) = (t) (t) as the estimated reward of the superior arm at round t. We remark that here, for simplicity of analysis, our definition of the superior arm only considers the two most recently pulled arms. We can in fact set the superior arm to be the one with the highest estimated reward among the m most recently pulled arms for any constant 2 A similar theoretical analysis will then yield the same theoretical guarantee, as shown Theorem 5.2 We further verify the robustness of AR2 to the choice of m in our numerical studies, where we consider all arms as potential candidates for the superior arm, and AR2 maintains its competitive performance (see Appendix A)
5.2
5

---

Triggered arms. In order to adapt to changes, AR2 identifies and keeps track of a set of arms with potential that are not pulled recently. We refer to these arms triggered arms and denote their associated set by T. a round I, an arm + ksup (t) gets triggered the triggering criteria in (2) is satisfied. We call the earliest such time t (t) as the triggering time of arm and denote it as 7 (t). If arm triggered, it is added to the triggered set 7. When arm gets pulled or is chosen as the superior arm, it is removed from 'T. The right-hand side of the triggering criteria is a confidence bound constructed based on Hoeffding's s Inequality (see details in Section 6 and Appendix H..
Note that at the exploration step, AR2 would only pull triggered arm if the triggered set T is non-empty. This inherently adjusts the rate of exploration in our alternation mechanism. In a slowly- changing environment (e.g., with small σ), the triggered set may not always include arms needing exploration, thus allowing focused exploitation of the superior arm; in a fast-changing environment, the rate of exploration can be as high as the rate of exploitation.
Regret of Algorithm AR2
Our algorithm AR2 works for AR-1 model with any choice of parameter a (0, 1). However, turns out that the problem is less challenging when the future weakly correlated with the past (i.e., when a is small). Theorem 5.1 states that any algorithm -inn-udin both a naive approach that continuously pulls the same arm throughout the horizon and our algorithm AR2-
achieve near- optimal performance when a is too small. This because with small a, (i) for any arm i [kt] the steady state distribution of its expected reward (t) concentrates around zero with high probability, and (ii) our observations of past rewards quickly deteriorate in their value of providing insights on the evolution of expected rewards in the future.
Theorem 5.1. Any non-anticipating algorithm A incurs per-round steady state regret of at most o( min( (oml/oool///o) + log k- 00 Vi-az, .28) 27))
In Figure I we compare the order of the regret upper bound in Theorem 5.1 with the order of the regret lower
bound in Theorem 3.1 Observe that ā - 0.5 serves rough threshold value such that when a (0, @), the orders of lower and upper bounds almost match each other, which suggests limited room for improvement. (That be- ing said, our numerical studies in Appendix A in fact show that AR2 still outperforms other benchmarks even when a is small.) On the other hand, as a + 1, the gap be- tween lower and upper bounds start to expand, implying that the problem becomes more difficult and simplistic approaches such as the naive algorithm would no longer produce satisfying performance.
10
value
C-y Togchleoo a logk
v1
10
atk. d. djoe
0.2
0.4
0.6
0.8
Figure 1: Comparison of the orders of the regret upper bound in Theorem 5.] and the lower bound in Theorem 3.1
In the rest of the discussion, we thereby focus on the more challenging regime (i.e., E [ā, 1)), and establish regret upper bound for AR2 when a E [ax 1).
tained with k = 5, a = 0.2, C 0.4. (Similar plots can be obtained for differ- ent values of l: and a.)
Theorem 5.2. Let K(aa) & 1 (log())/loga + 1)J, and let A be the AR2 algorithm that gets restarted in each epoch of length Dep [ka 30 If E [ā,1) and i K(aa), the per-round steady state regret of A satisfies REGA & Olcaa2 log(couo where co =
/4log(1/ao) +loog Dep + log(4k).
Recall that if a is close to one, the regret lower bound can be characterized as Q(ka? This shows that our algorithm is optimal in terms of AR parameter and stochastic rate of change (up to logarithmic factors). In Appendix E.3 we further highlight the significance of Theorem [.2 by illustrating the evolution of upper and lower bounds, as well as the per-round regret attained by AR2, at different values of a and a. We show that Theorem 5.2 well characterizes the performance of AR2 under different settings.
We remark that terms of the dependency on k. Theorem 5.2 requires k < K((a)) mainly for the rigor of theoretical analysis, and this bound loosens as a approaches one (for example, when a = 0.95,
See, also, Figure in Appendix E.2 for comparison of upper/lower bounds with respect a.

---

K((a) = 20)) Our numerical studies in Appendix A also reveal that (i) AR2 maintains its competitive performance even when the number of arms lt exceeds K(a)); and (ii) its per-round regret grows modestly with k. These suggest that the asuumpion/dependdnnyy on for our upper bound are artifacts of our analysis, rather than an intrinsic property of our algorithm.
Proof of Theorem 5.2
The proof of Theorem 5.2 proceeds in four steps. Step I introduces distributed regret, a novel notion that distributes instantaneous regret over subsequent rounds, enabling to rephrase per-round steady state regret. Step 2 defines a high-probability good event crucial for analyzing distributed regret. In Step 3. we leverage the good event to establish an upper bound for each round's distributed regret. Finally, Step 4 aggregates these regrets across rounds and epochs, establishing the per-round steady state regret of AR2 against the dynamic benchmark.
Step 1: Distributed regrets. Let (t) = (t) (t) be the instantaneous regret from pulling
arm at round I, where r" (t) = max (1) the maximum expected reward at round L. Consider
(rr, (Ar,, where Ary, (4) r (1) - rr, (t) the instantaneous regret incurred at round In the following, we show that we can distribute this instantaneous regret over subsequent rounds.
the expected per-round regret: REG = E
+ EL REG = -
Note that for any i E [k], let e00) denote the round at which arm gets pulled for the jth time within an epoch. Then during the period between two consecutive pulls e(1) S < e(++1) the only regret incurred from pulling arm is the instantancous regret (g.))) By previous definition, also
have (t) = p(()) next (t) = gli+1) and (r,(t) = e(1+1) e(1) for all glr) < t < e(5+)) Observe that we can decompose Ar, (c( as follows, which then leads to the notion of distributed regret:
((041-11
Ari(e(")a2((-:))
Ar, (T) I+ (1 +...++..00 4.... 21
(r.(e!)) Σ
Σ
1+ + ... 21000)
t=
Definition 6.1 (Distributed regret). The distributed regret of arm at round t is defined as
Di(1) = (1 (1+02 1 ((())(()-))
Ar. (r:(T.(t))
a ((-)((()))
Note that Dz(() = if arm i is the best arm at round T; (1). Now, let Ti be the total number of rounds we pull arm i in the horizon, we can rewrite the expected per-round regret
& T. (E(A)())))
k
T
s
A
REG SEER
1
EEEEDOO
Σ
(att=ta-1)iii 11
where the second equality follows from the Definition and the third equality follows from that AR2 proceeds in epochs of length Dep. and S App is the total number of epochs.
Good event and its implications. Before proceeding, we first define a good event (()) at round which would help simplify our analysis. In principle, we say that a good event (() happens round if the noises within the epoch including are not too large in magnitude. Recall from Section that (t) follows an AR-1 process with truncating boundaries: r + 1) B (a(r((t) + et(t)) ).
Step 2:
where Byy) = min max (y. - R), R... Hence, we need to first define a new noise term that shows the influence of the truncating boundary.
if a(r;(t) ct()) E ब. (t) - L (1B((0))0)) ((ri((() +(()())++((t)))))))))))))))))))) ar.(t)) otherwise
(t)
(5)
*Here, the bound K((a) results from our loose upper bound for the number of triggered arms in the proof of Lemma H.3 where we used the fact that there are at most - 1 < K((a) triggered arms at any round to limit how quickly the values of the past observations diminish. If, any given round, the number of triggered arm O(1), the upper bound K((a) would no longer he required, and the regret upper bound can he further reduced to Oc o² log(coco)), which matches the lower bound up logarithmic factors.
7

---

In particular, the new noise (t) satisfies the following recursive relationship: ri 1 at: - (t). We now formally define the good event G(t), which states that for any sub-interval [to t within the epoch including i, the weighted sum of (l) satisfies a concentration inequality.
Definition 6.2 (Good event at round t). We say that the good event ((t) occurs at round t if for every i E [k), and for every sub-interval (to, 12], where - Dep S to <h St+ Dep. the weighted
sum of the noises (t) satisfies Ei= (01)) < <coo a Q2(tt-to+ a²), where
co- = / (llog(//oo) + log Dep + 2 log(4k))
By building connection between E.(1) and et( and Hoeffding's inequality, we show Lemma 6.3 which confirms that the good event ((t) happens with high probability.
Lemma 6.3. For any E [T), we have (t) S (ao)².
Step 3: Distributed regret analysis. For a given round in the s-th epoch, we can bound its expected distributed regret by first decomposing it into two terms: (t)] = where 1g is the indicator function of event E. We can bound the first term by applying Lemma 6.3
(ge)
E[ s 2 (t) = 28 (ao)² = O(o²a²).
(6)
To bound the second term, we rely on the implications of the good event g(t) (presented in Ap- pendix H.I) to show the following.
Lemma 6.4. Suppose that we apply AR2 to the non-stationary MAB problem with a E [ā,
and and k S K((a), for every arm i E [k] and some round Tt(t) S t < neext(t) (t), where (t))) and T,eex(t) Occga20²1² log(cooaa/k)).
(t) are two consecutive rounds at which i gets pulled, we have E(Da(t)lou) -
The proof of Lemma (.4mi deferred Appendix H.2 There, we provide a bound for the nominator and denominator of Di( respectively, conditioning on the good event g and the value of Ar, (t). In the proof, we critically use the implications of the good event (see Appendix H.T. Now, combining (6) and Lemma 6.4 for any round within the sth epoch such that T((1) S 7
text (I), we have
BID((1) = E(D,(())= + E[D.(())go))
S Oleio2 22 log log(enoavkk)).
(7)
Step 4: Summing the distributed regrets. Given Equations (4) 7 and Aup = [ka - 3--
30-37,
summing the expected distributed regrets first within an epoch, and then along the horizon yields
S
1 REG A T
Σ
B(D,(1)
1 S T E
S. 10(0 (o())) + 23) O(k (oocr (O),
t=
11
where the additional 2 term comes from the initialization round and the last round we pull arm i within an epoch. This concludes the proof if we plug in Č = co VT.
7 A Real- World Case Study on Tourism Demand Prediction
In this section, we numerically demonstrate the efficacy of AR2 via real-world case study based on international Tourism Demand dataset for Australia [36]. In this case study, we act as travel agency that needs to determine which vacation package to offer, where the demand for each vacation package is highly dependent on the tourism demand during each quarter. Our case study is further complemented by number of synthetic experiments in Appendix [ where we compare AR2 against various benchmarks designed for both stationary and non-stationary settings and again show the superior performance of AR2 in adapting to the rapidly changing environment.
Dataset and setup. The international tourism demand dataset 33., obtained from the Australian Bureau of Statistics, records the number of individual tourist arrivals to Australia from Hong Kong during each quarter between the years 1975-1989 The authors of [6 have fitted an AR model the
logarithms of quarterly tourist arrivals, which results in an AR-4 model with trend component
rt( = -0.01 + 0.32R, 2) + 0.6.. (t 4). Note that here, the number of tourist arrivals is strongly correlated with the number of arrivals four quarters before, which is likely due to seasonal patterns. The time series analysis in [36] also supports our assumption in Section 2 that the AR
'ee keep the significant lags in forecasting tourist arrivals, which are the second and fourth lags.
8

---

parameters are known. In this dataset, as well as many others from the real world, decision- recision-mmaers are likely to have access to historical data, which enables them to fit AR processes with good precision.
Given the AR model, we consider recommendation setting where the travel agencies have k 5 vacation packages (arms) to offer to the tourists from Hong Kong, and wish to dynamically feature the package with the highest demand (reward) at each round. For each arm, we simulate its reward sequence by randomly drawing the initial reward from a uniform distribution in [0, 1] and simulate
r. (1()) for a total of = 200 rounds, based on the AR-4 model above. We take the stochastic rate of change to be 0 = 0.1 for all arms.
Extension of AR2 to A processes. We extend our algorithm AR2 to handle MAB problems with rewards modeled using general AR-p processes with trends; see Algorithm 2in Appendix B22 At high level, the extension of AR2 uses similar techniques described in Section 4 The key difference is that, for each arm i E [k], it maintains not only an estimate 7: (t) of the arm's 's reward at round t, but
also an estimate (1) that captures the associated estimation error. These estimates are dynamically updated based on the structure of the AR- process with trends. The extended algorithm, akin to Algorithm|| [ (i) selects the arm with the highest estimated reward (t) and (ii) triggers arms with potential, where the confidence bound in the triggering criteria now depends on the estimate of the error (t). For a comprehensive discussion of our extension, please refer to Appendix B.2
Results. We compare the performance of AR2 against the two most competitive benchmarks (e-greedy and a modified UCB algorithm) that we identfied in synthetic experiments; see Appendix [A] for comparisons with the other benchmarks. The comparison is shown in Table IT It can be seen that AR2 stands out in terms of both the regre and the number of times it pulls the optimal arm. In this case study, while the e-greedy algorithm frequently selects the optimal arm, it still accumulates high regret due to its purely random exploration, which can lead to the selection of arms with low rewards. Similarly, the modified UCB algorithm, which leverages the knowledge of the temporal structure in its confidence bound (see description in Appendix C). doesn't 't perform well. Due to the rapidly changing nature of the AR-p process, modified UCB over-explores. AR2, on the other hand, prove to be effective even amidst the rapid changes introduced by more complex time series.
Table 1: Performance comparison.
Algorithm normalized regret
# optimal arms
AR2
0.26 (0.14)
142.04 (15.71)
UCB-mod
0.60 (0.27)
106.62 (7.12)
e-greedy
0.38 (0.16)
133.83 (12.47)
Extension on Learning the AR Parameter
In the previous sections, we have assumed full knowledge of the AR parameter, which as discussed in Sections 2 and 7 when we have access to past data. This section proposes an algorithm extension for when the AR parameter needs estimation. We introduce maximum likelihood method and numerically evaluate the performance of AR2, which show that AR2 still remains competitive despite noise in the estimated AR parameter.
A Maximum Likelihood Estimator. If the decision maker does not have prior knowledge of the AR parameter o, one can learn the AR parameter via Maximum Likelihood Estimation (MLE). In the first Tex rounds of the time horizon, where Tex- O for some 3 E (0. 1), we pull one arm i E [k) consecutively for fixed arm i and observe rewards (1,,), R2 (Tes). We then define the maximum likelihood estimator ā = arg min L(a). where [(a) is the negative of the log- ligeeikkiiood function defined in (60) of Appendix [ Observe that here we cannot directly apply linear regression for estimating a because the existence of truncating boundaries would lead to a biased estimator. MLE, on the other hand, remains robust even when the expected reward of our arm hits the boundary. Since the number of rounds used for estimation Tea scales sublinearly with T, the regret incurred within the first Text rounds would not impact our per-round regret upper bound. If we have heterogeneous AR parameters a, for arms i E [k] (as in Appendix A). one can simply pull each arm i E [k] consecutively for Test rounds and perform MLE for each a;,.
The following proposition quantifies the amount of noise in the estimated AR parameter. Proposition 8.1. Let ā = arg min.0( L(a)) be the estimated AR parameter. Then, for 7 >> O. with probubility at least 1 - 2/T2 2 exp(-Te.. V /22/2"/", there exists constants L1, Lo such that
'eere we evaluate each algorithm using the normalized regret: LT=, (E) ET. (+),,, which nor- malizes the total regret with the optimal reward in hindsight.

---

Iā - S (40RL:)((VL)) 2/2 log Teg, where V is the variance of the observed reward in the steady state distribution, which is independent of our algorithm or the time horizon T.
We plot the normalized regret incurred by AR2, e-greedy and mod-UCB using the estimated AR parameters, obtained through MLE with Test = {25, 50, 100). We observe that whenever the AR parameters a; are small or large, the performance of AR2 outcompetes the other two benchmarks. In particular, AR2 appears to be robust to the noises in the estimated AR parameter, with performance close to what we would otherwise obtain with the accurate AR parameters (see Table 2 Appendix
25
50
100
small
0.75
0.75
0.75
0.65
0.65
0.05
0.55
AR2
mos-UCC
0.55
AR2
egreedy mod4Kch
0.55
AR2
Egreedy mod4kch
0.8
D4
0.4
04
0.2
med
Figure 2: Box plots of normalized regret incurred by each algorithm at T = 10, 000 (AR2 highlighted in gray). The input AR parameter a; is the maximum-likelihood estimator of the true AR parameter. We vary the magnitudes of AR parameters EJa.] {0.4, 0.9} and the number of rounds used for estimation Tea {25, 50, 100). The parameters of our instances are the same as in Appendix A and we take k = 6.
Conclusion and Future Directions
In this paper, we studied a non-stationary MAB problem with an AR structure, which captures the rapid changes commonly observed in real-world dynamics. Our proposed algorithm, AR2, leverages our knowledge estimate of the temporal dependency effectively handle the challenges associated with the fast-changing environment, and our techniques can be potentially adapted to more complex temporal series. As the realm of non-stationary bandits with rewards governed by temporal structures remains largely unexplored, there are several exciting avenues for future research. One intriguing direction incorporate seasonality into our framework, exploring models such seasonal ARIMA with both long-term and short-term changes. Additionally, building on the promising numerical results in Section 8 it would be interesting to theoretically characterize the performance of our algorithm when estimation of the AR parameter and dediisdn making are performed simultaneously.
Acknowledgments
We are grateful to the MIT-IBM Watson Al Lab for their generous support.
References
[1] A. Aaker, J. M. Carman, and R. Jacobson. Modeling advertising-sabe sales relationships involving feedback: time series analysis of six cereal brands. Journal of Marketing Research, 19(1):116 125, 1982.
[2] D. Agarwal, B.-C. Chen, and P. Elango. Spatio-temporal models for estimating click-through rate. In Proceedings of the 18th International Conference on World Wide Web, page 21-30, 2009.
[3] O. Anava, E. Hazan, and A. Zeevi. Online time series prediction with missing data. In Proceedings of the 32nd International Conference on Machine Learning, volume 37, pages 2191-2199, 2015.
[4] A. A. Ariyo, A. O. Adewumi, and C. K. Ayo. Stock price prediction using the arima model. In 2014 UKSim-AMSS 16th international conference on computer modelling and simulation, pages 106-112. IEEE, 2014.
[5] P. Auer. Using confidence bounds for exploitation-exploratii trade-offs. Journal of Machine Learning Research, 3:397-422, 2003.
[6] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine Learning, 47:235-256, 2002.
10

---

[7] P. Auer, N. Cesa- Cesa-Bianchi, Y. Freund, and R. E. Schapire. The non-stochastic multi-amman armed bandit problem. SIAM journa of computing, 32:48-77, 2002.
[8] K. Azuma. Weighted sums of certain dependent random variables. Tohoku Mathematical Journal, Second Series, 19(3):57-367, 1967.
[9] D. Bertsimas and J. Niño-Mora. Restless bandits, linear programming relaxations, and a primal-dus index heuristic. Operations Research, 48(1):80-99) 90, 2000.
[10] O. Besbes, Y. Gur, and A. Zeevi. Stochastic multi-armed- problem with non-stationary rewards. In Advances in Neural Information Processing Systems, volume 27, 2014.
[11] Bogunovic, J. Scarlett, and V. Cevher. Time-varying gaussian process bandit optimization. In Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51, pages 3 114-323. PMLR, 2016.
[12] Y. Cao, Z. Wen, B. Kveton, and Y. Xie. Nearly optimal adaptive procedure with change detection for piecewise-stationa bandit. In Proceedings the 22nd International Conference on Artificial Intelligence and Statistics, volume 89 of PMLR, pages 418-427, 2019.
[13] L. Cella and N. Basa-Bianchi. Stochastic bandits with delay-dependent payoffs. In International Conference on Artificial Intelligence and Statistics, pages 1168-1177 PMLR, 2020.
[14] V. Chavez-Demoulin and J. McGill. High-frequency financial data modeling using hawkes processes. Journal of Banking & Finance, 36( 36(12):3415-33) 2012.
[15] N. Chen, C. Wang, and L. Wang. Learning and optimization with seasonal patterns. arXiv preprint XXiv:2005.080885 2020.
[16] V. Dani and T. P. Hayes. Robbing the bandit: Less regret in online geometric optimization against an adaptive adversary. In Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithm (SODA), page 937-943, 2006.
[17] H. A. David and H. N. Nagaraja. Order Statistics. Wiley, 2003.
[18] M. G. Dekimpe and D. M. Hanssens. The persistence of marketing effects on sales. Marketing science, 14(1):1-21, 1995.
[19] B. U. Devi, D. Sundar, and P. Alli. An effective time series analysis for stock trend prediction using arima model for nifty midcap-50. International Journal of Data Mining & Knowledge Management Process, 3(1):65, 2013.
[20] R. Durrett. Probability: Theory and Examples. Cambridge University Press, 5th edition, 2019.
[21] Fattah, L. Ezzine, Z. Aman, H. E. Moussami, and A. Lachhab. Forecasting of demand using arima model. International Journal of Engineering Business Management, 10, 2018.
[22] T. C. Gard. Introduction to Stochastic Differential Equations. Marcel Dekker, 1988.
[23] C. W. Gardiner. Handbook of stochastic methods: for the natural and social sciences. Springer,
2009.
[24] A. Garivier, T. Lattimore, and E. Kaufmann. On peplore-then-commeee strategies. In Advances Neural Information Processing Systems, volume 29, 2016.
[25] A. Garivier and E. Moulines. On upper-confidence bound policies for switching bandit problems.
In Algorithmic Learning Theory, pages 174-188. Springer Berlin Heidelberg, 2011.
[26] J. Gittins and Jones. A dynamic allocation index for the sequential design of experiments. In Progress in Statistics, pages 241-2661 North-Holland, 1974.
[27] S. Grünewälder and A. Khaleghi. Approximations of the restless bandit problem. Journal of Machine Learning Research, 20(14):1-33 2019.
[28] Guha and Munagala. Approximation algorithms for partial- inrtialiiffrmmation based stochastic control with markovian rewards. In 48th Annual IEEE Symposium on Foundations of Computer Science 07), pages 483-493, 2007.

---

[29] W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American statistical association, 58(301):13-30, 1963.
[30] N. B. Keskin and A. Zeevi. Chasing demand: Learning and earning in changing environment. Mathematics of Operations Research, 42(2):277-307, 2017.
[31] R. Kleinberg. Nearly tight bounds for the continuum-armed bandit problem. In Proceedings of the 17th International Conference on Neural Information Processing Systems, page 697-704, 2004.
[32] R. Kleinberg and N. Immorlica. Recharging bandits. In 20/8 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 309-319. IEEE, 2018
[33] R. Kleinberg and T. Leighton. The value of knowing a demand curve: Bounds on regret for online posted-price auctions. In Proceedings of the 44th Annual IEEE Symposiun on Foundations of Computer Science (FOCS), pages 594-605, 2003.
[34] Kloeden and E. Platen, Numerical Solution of Stochastic Differential Equations. Springer, 1992.
[35] T. L. Lai, H. Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22) 1985.
[36] C. Lim and M. MacAleer. Time series forecasts of international tourism demand for australia. Technical report, ISER Discussion Paper, 2001.
[37] F. Liu, J. Lee, and N. B. Shroff. A change-detection based framework for piecewise-stationar multi-armed bandit problem. In AAAI, pages 3651-3658, 2018.
[38] K. Liu and Q Zhao. Indexability of restless bandit problems and optimality of whittle index for dynamic multichannel access. IEEE Trans. Inf. Theor, (66111)5554755555 nov 2010.
[39] Y. Liu, B. Van Roy, and K. Xu. Nonstationary bandit learning via predictive sampling. In International Conference on Artificial Intelligence and Statistics, pages 6215-6244 6244. PMLR, 2023.
[40] A. Mate, J. Killian, H. Xu, A. Perrault, and M. Tambe. Collapsing bandits and their application to public health intervention. In Advances in Neural Information Processing Systems, volume 33, pages 16699-16550 Curran Associates, Inc., 2020.
[41] R. Ortner, D. Ryabko, P. Auer, and R. Munos. Regret bounds for restless markov bandits. In Proceedings of the 23rd International Conference on Algorithmic Learning Theory, page 214-228, 2012.
[42] S. Pandey, D. Agarwal, D. Chakrabarti, and V. Josifovski. Bandits for taxonomies: A model- based approach. In SIAM International Conference on Data Mining, pages 216-227, 2007.
[43] C. H. Papadimitriou and J. N. Tsitsiklis. The complexity of optimal queuing network control. Mathematics of Operations Research, 24(2):293-305, 1999.
[44] G. A. Pavliotis. Stochastic processes and applications. Springer- New York, 2016.
[45] D. Pollard.
Convergence of stochastic processes. Berlin: Springer. 1984.
[46] H. Robbins. Some aspects of the sequential design of experiments. Bulletin of the American Mathematical Society, 58(5):527 -535, 1952.
[47] R. H. Shumway and D. S. Stoffer. Time Series Analysis and Its Applications: With R Examples. Springer, 4th edition, 2017.
[48] A. Slivkins and Upfal. Adapting a changing environment: the brownian restless bandits. In 21 Conference on Learning Theory (COLT), pages 343-354, 2008
[49] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018
[50] C. Tekin and M. Liu. Online learning of rested and restless bandits. IEEE Transactions on Information Theory, (8(8):5588-5611, 2012.
12

---

[51] W. R. Thompson. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples. Biometrika, 25:285 294, 1933.
[52] F. Trovo, S. Paladino, M. Restelli, and N. Gatti. Hiding-windon thompson sampling for non-stationary settings, Journal of Artificial Intelligence Research, 68:311-364, 2020.
[53] P. Whittle. Restless bandits: activity allocation in changing world. Journal of Applied Probability, 25A:287-295, 1988.
13

---

Appendices for Non-Stationary Bandits with Auto-Regressive Temporal Dependency
A Numerical Studies on Synthetic Data
Set-up. We consider non-stationary bandit problem with k arms and T 10, 000 rounds. To make the setting more general, we let the expected reward rt(() of each arm i E kk] follow an independent AR-1 process with heterogeneous AR parameter dj, stochastic rate of change di and truncating boundary [-1, 1]. We consider two different regimes of a,'s: (i) Small og 's: the AR-1 parameters {ar} are drawn from dirichlet distribution with rescaling such that for all i E [k]. [B[a,]] = 0.4, which is less than the threshold value 0.5 that we defined in Section []] (ii) Large ay 's: the AR-1 parameters {or} are chosen from a dirichlet distribution with rescaling such that E Baa;] = 0.9 for all E [k). The concentration parameters of the dirichlet distributions are all
be 5. For each regime of a; 's (small v.s. large), we consider 100 instances, where each instance corresponds to AR parameters (A1, ( .4.) generated as described above; and stochastic rates of change (0...... .x) generated from i.i.d. uniform distributions in (0. 0.5). The initial reward r, (0) is drawn independently from the steady state distribution discussed in Appendix [D]
Performance comparison. We implement AR2 and compare it against a number of benchmarks designed for stationary and non-stationary bandits respectively. (See Appendix [B. for the imple- mentation details, where we generalize AR2 to the setting with heterogeneous a, and o, s.) All parameters used in the following algorithms are tuned.
The benchmark algorithms designed for stationary settings are: (i) "explore-then-commee
(ETC)
policy [24] that first selects each arm for m rounds, and commits to the arm with the highest average pay-off in the remaining T mk rounds; (ii) UCB algorithm (6). which achieves sublinear regret under static settings; (iii) c-greedy algorithm 49 with probability of exploration c = 0.1, which acts greedily with probability (1 - c) and explores random arm otherwise. (iv) Exp3 algorithm (7]. which is designed for the adversarial setting and achieves sublinear regret when evaluated against the weak static benchmark.
Further, we also consider several benchmark algorithms designed for non-stationary settings: (i) Rexp3 algorithm [1O.. which modifies the Exp3 algorithm for the non-stationary setting by introducing a restarting mechanism, and assumes that the total variation of expected rewards is bounded by a variation budget Vy; (ii) a modified UCB algorithm (mod-UCB), which modifies the upper confidence bound based on the structure of the AR-1 process; see Appendix C description and discussion of the algorithm; (iii) the sliding-window UCB (SW-UCB) algorithm (25) and the dlding-window Thompson Sampling (SW-TS) algorithm (52), both of which adopt sliding-windan approaches: (iv) the predictive sampling (PS) algorithm for AR-1 bandits recently introduced by (39), which is shown to outperform the Thompson sampling algorithm in non-stationary environments.
Results. In Table 2 we evaluate and compare the performance of AR2 against the benchmark algorithms in instances with small a; 's (E ag] = 0.4) as well as large a; ks's (E[a,] = 0.9). We also vary the number of arms k E (2, 10, 20). To keep our results consistent across instances, we evaluate each algorithm A using the normalized regre?" Σr ( Σ r" (t), which normalizes the total regret using the reward of optimal in hindsight dynamic policy.
From Table 2, we see that AR2 clearly outperforms the benchmarks in almost all choices of and regimes of ag's. The algorithms designed for stationary settings (ETC, UCB, Exp3) perform poorly, as the AR setting includes non-stationarity that differs substantially from the stochastic or adversarial settings they were intended for. Similarly, the algorithms designed for non-stationary setting with limited amount of changes (RExp3, SW-UCB, SW-TS) do not perform well since they are designed to tackle environments either with abrupt changes, or with sublinear amount of changes, and are not suited for the fast changes in the AR environment. Finally, when compared against benchmarks that take into account the AR structure rewards (e-greedy, modified UCB, PS), AR2 also displays superior performance. Here, the PS algorithm indeed dominates TS-based approaches
NNoe that since the expected rewards can be negative, the normalized regret can exceed one. Further, when ar, are small, the normalized regret of each algorithm is in general larger. This is because the optimal reward used in normalization tends to be smaller, and hence does not contradict the fact that our problem is more challenging when the AR parameters are small.

---

Table 2: The mean and standard deviation (in parenthesis) of normalized regret incurred by each algorithm at T = 10, 000. All experiments are run with 100 instances. The algorithm with the smallest normalized regret is highlighted in gray. (a) Comparison with Stationary Benchmarks
E|a.]
k:
AR2
ETC
UCB
é-greedy
Exp3
2
0.38 (0.10)
1.00 (0.03)
0.68 (0.09)
0.43 (0.09)
0.99 (0.02)
0.4
10
0.67 (0.01)
1.00 (0.01)
(0.01)
0.76 (0.02)
1.00 (0.01)
20
0.72 (0.01)
1.00 (0.01)
0.84 (0.01)
0.81 (0.01)
1.00 (0.01)
2
0.18 (0.06)
1.00 (0.11)
0.65 (0.13)
0,36 (0.14)
0.95 (0.12)
0.9
10
0.40 (0.04)
1.00 (0.05)
0.58 (0.04)
0.60 (0.06)
0.99 (0.02)
20
0.49 (0.02)
1.00 (0.02)
0.62 (0.02)
0.64 (0.03)
0.99 (0.01)
(b) Comparison with Non-Stationary Benchmarks
E|as]
k:
AR2
Rexp3
mod-UCB
SW-UCB
SW-TS
PS
0.38 (0.10)
0.96 (0.03)
0.45 (0.05)
0.69 (0.05)
1.00 (0.03)
0.51 (0.04)
0.4
10
0.67 (0.01)
0.99 (0.01)
0.67 (0.03)
0.90 (0.02)
0.98 (0.01)
0.78 (0.03)
20
0.72 (0.01)
1.00 (0.01)
0.72 (0.02)
0.95 (0.01)
0.99 (0.01)
0.84 (0.02)
0.18 (0.06)
0.87 (0.08)
0.20 (0.07)
0.55 (0.13)
0.99 (0.15)
0.52 (0.33)
0.9
10
0.40 (0.04)
0.97 (0.01)
0.43 (0.05)
0.70 (0.03)
0.86 (0.04)
0.47 (0.03)
20
0.49 (0.02)
0.99 (0.01)
0.53 (0.03)
0.84 (0.02)
0.91 (0.02)
0.52 (0.02)
in non-stationary environments, as suggested by [39], but AR2 remains competent in all kinds of AR- AR-based setups; fürther. [39] also suggests that deriving the conditional probability distribution in the predictive sampling procedure and implementing it can be complicated in general, and hence it is unclear how one can adapt the PS algorithm for more complicated AR-P processes as we did in our case study (see Section 7 and Appendix B.2). Among all stationary benchmarks, e-greedy is the most competitive; while mod-UCB stands out the most competitive within the non-stationary benchmarks. However, there are instances where AR2 can contribute to a decrease in regret as high as 50% when compared to e-greedy, and a 15.5% decrease in regret when compared to modified UCB. All of the aforementioned results attest to the efficacy of AR2 in rapidly changing environments governed by the AR process.
B Implementation Details and Extensions of Algorithm AR2
B.1 Implementation of AR2
To apply AR2 to the more general setting described in Appendix A where the expected reward of each arm undergoes an AR-I process with heterogeneous AR parameter a; and stochastic rate of change og, we make a few straightforward updates to AR2: (i) when maintaining estimated reward (t) of arm i, we use its AR parameter az; (ii) we assume that an arm + (() gets triggered if at round I,
Sup (1) F((() S coo (a} a; 2(t 2(1-+(+)) a²)
Empirically, we make two more minor changes to AR2 in its numerical implementation. (i) The definition of the superior arm: instead of considering one of the two most recently pulled arms, we consider all arms and choose the one with the highest estimated reward round & to be the superior arm at round f, i.c., (t) = arg max;e]]] (t). (ii) The triggered arm to be played: in the exploration round t (when t is odd and T + 0). we consider the upper confidence bound of the expected reward of each arm i, defined as:
(t) F((t) (t(tt)++ +G (a aj (1= at)
and pull the triggered arm with the highest upper confidence bound, i.e. I = arg max UCB, (t). Note that the arms in the triggered set T differ in terms of both triggering time and estimated rewards. Previously, our criteria for selecting the triggered arm to play only takes into account one aspect of such heterogeneity, i.e., the triggering time. The new criteria allows us to also consider the estimated reward of each arm, which is another indicator of the arm's 's potential.

---

B.2 Extension of AR2 to AR-p Process with Trend
In this section, we provide extension of AR2 (Algorithm IT. which would apply to non-stationary bandits where the rewards follow general AR-p processes with trends for any p 2 1. This algorithm applied when we perform our case study on tourism demand prediction in Section and is shown to adapt well to the more complex, rapidly evolving environment.
Let us assume that for each arm i E [kc], the reward distribution following an AR-p process, potentially with trend component. That is, conditioning on past history during rounds 1,..., 1, the expected reward arm i at round is
ri(1) = 04,0 +
on Σ 5=1
Re - j),
where 0i,0 is the trend component and (as.l,.... Ogi ) is the set of AR parameters associated with arm i.
The details of the extension of AR2 is presented in Algorithm 2 which called AR2-p. At a high level, the main techniques used in AR2-p are very similar to those used in AR2. As AR2-p specifi- cally designed to address practical scenarios where real-world dynamics are represented by more complex time series, we have incorporated the implementation changes discussed in Appendix B.1 to enhance its practical applicability.
At each round of Algorithm 2 first determine the superior arm (t)((), which is the arm with the
highest expected reward. We then decide if there are any arms that we wish to trigger, depending on whether some untriggered arm has an upper confidence bound that exceeds the expected reward of the superior arm Fsup(t) We then alternate between exploration and exploitation: (i) during exploitation rounds, we pull the superior arm; (ii) during exploration rounds, we pull the arm with the highest upper confidence bound out of the set of triggered arms, denoted as T. Finally, after we pull arm It at each round, we update the estimate for the state of each arm i E [R].
The main difference between AR2-p and AR2 for AR-1 process lies in how we maintain estimates for each arm. To account for the more complicated structure of an AR-p process with trends, we need maintain two estimates for each arm an estimate for the expected reward ft(t), and an estimate for the error bound (1), defined as follows:
(1) = 03,0 + Pa and RA(1)
Oig Bi(1 j) 0s.j.
j=1
Here, the estimate for error bound Et(t) essentially captures how much error is contained in our
estimate for arm at round t, i.e., (t).. Since we estimate (t) based on p past estimates ft(t
1)...., (t(t p). the error associated with each of these terms, i.e., Ex(t 1), 1)..... É,(t p). would contribute the total error for arm at round t. i.c. (t).
We would then use the error estimate Et(t) in determining our triggering condition. We trigger an arm i & TT (1sup(t)) at round if
Sup (t) < ca2 E.(t).
The error bound estimates would also be useful when we determine which arm to pull out of all the triggering arms. To do that, we form the upper confidence bound for each arm
UCB, (t) = (t) + ca.y (t())
and pick the one with the highest upper confidence bound: I, = arg maxter (t).
C Description of Modified UCB Algorithm
In our numerical studies (Appendix(A), we have considered the modified UCB algorithm as one of the non-stationary benchmarks. We now describe this algorithm, which borrows idea from the UCB algorithm (6) for stochastic MAB, and modifies the expression of the upper confidence bound based on the AR temporal structure.
3

---

Algorithm 2 Alternating and Restarting algorithm for non-stationary bandits with AR-p reward structure (AR2-p)
Input: AR parameters ic(e), trend components (ou)))ee(k)) stochastic rate of change {a: (e())) epoch 3E/pl
size Aep parameter
1. Set the epoch index = 1.
Repeat while
[T/ upp:
(a) Initialization:
Set to (s 1) Set the initial triggered set T = 0.
For each arm E [k], set estimates expected rewards (i( = and error bound estimates
(t()))
for S O.
(b) For t to + I,... .....,..iinnn min + Ae,
- I p k. pull arm i [(t- to 1)/p}+1.
I.
I| Pull each arm consecutively for p rounds.
Elsc,
Update the identity of the superior and its estimated reward
upp (1)
arg max (1) and (t) Frap (4)
sE(M]
Trigger arms with potential: For
TTU (tup( (t)), trigger arm i if
Sup Fi(t) S ear (t)..
If triggered, add to T. Alternate between exploration and exploitation:
i. If is odd and T * 0. pull triggered arm with the highest upper confidence bound estimate:
It arg e (i() + ca. (.(.).
ii Otherwise, pull the superior arm (tp
Receive reward R1, (t). Update Fi, (t) = RA, (t) and Er,
Maintain Estimates: For each arm E [k:], set estimates for expected rewards and error bounds
(t(t) = 0,,0 + Σ
Pt (t and B,(1) = Σ on Et + on.
(c) Set + 1.
Algorithm 3 A modified UCB algorithm for non-stationary AR bandits (mod-UCI)
Input: AR Parameters (01, ..., ...) stochastic rates of change (øI...., Jk),, parameter d.
Initialization: pull each arm i e [k] at round i. Set estimates P: + 1) a k- ((aR((()) and t. i.
2. While & < T:
(a) For each arm [b)), compute its upper confidence bound (UCB):
(t) (t) /2log(2/8) o, (af a; ((1 a?)
arg max UCB, (f). Receive a reward Rı, (f), and set (b) Pull the arm with the highest UCB: I
Tt, L. Maintain Estimates: Set Fr, B(aRi, (t)) set (t + (t) for t It
The details of modified UCB is presented in Algorithm Similar to the original UCB algorithm. consider upper confidence bound of the expected reward of each arm i round f, denoted as (t), which consists of two terms. The first term (t) is the estimated reward of arm based on past observations; the second term is the size of the one-sided confidence interval for the expected reward r. (t). The confidence interval is constructed based on Hoeffding's 's Inequality (see Lemma J.3) and is designed such that the true expected reward rt(t) will fall into the confidence interval with probability at least confidence bound in the AR setting, consider non statioooy MAB problem, in which the expected reward of arm i follows an AR-I process with parameter
where is an input parameter. To derive the expression the upper
(0. 1), stochastic rate of change 2 for details about the set-up.) The
a; E (0, 1), and truncating boundary R, R). (See Section estimated reward of arm i round (t), can be maintained in the same way done in Algorithm ]

---

The modified UCB algorithm always selects the amm with the highest upper confidence bound. To construct the confidence bound, first recall from Section that define new noise term (t)
(see (5) that incorporates the influence of the truncating boundary, and the new noise term satisfies the recursive relationship: rz(L+t + 1)= (r) + aé; (1). Suppose that at round I, we last observed the
reward of arm i at round T.()). Using the recursive relationship. we have:
rt(t) at - 1) + az 1) of
(-7((0- -110)-1,00 (T((s(()) + 1) + -- (2a00 + +... ag&i(t 1)
= 1- ( (t) + +)+
Σ a = ('=,(0+1
a att')t))
(==)((++1
(8)
where the last equality follows from the way we maintain estimates. By Lemma H.1 any > O,
we have that for
Σ a''a(()) (+)++++++
S 2 P
a' (t') ('=r((+++
Σ
S
(9)
where ei(t') ~ (00, σ.) is the independent Gaussian noise applied to arm at round t'. By Hoeffd- ing's s Inequality (Lemmal) J.3). for fixed 8 > O, we also have the following concentration result:
P
Σ
a- c((t)) (2log(2/0) oi o. (af - 2(t ((--
2 1 1 6. (10)
(1)+
together establish a confidence bound centered around (t), such that the true expected reward (t) falls into the confidence bound with probability at least 1 5. In Algorithm we thus define the upper confidence bound of arm at round /. as:
Equations 8 and (T)
UCB Fi(() + 22lo((2/8) o. (a a ((t- (11-
and we have (tr:(t) > (CB < 6 when implementing the modified UCB algorithm for numerical experiments in Appendix A
Finally, we remark that our algorithm AR2 and the modified UCB algorithm share some similarities. Both algorithms incorporate our knowledge of the AR temporal structure into their design, which makes them more competitive against the rest of the benchmarks. The triggering criteria of AR2 essentially constructs a confidence interval around the estimated reward (t) of arm at round t, and triggers arm i if the upper confidence bound arm i exceeds the estimated reward of the superior arm. On the other hand, AR2 also differs from the modified UCB in two main aspects. (i) By alternating between exploration and exploitation rounds, AR2 avoids potential over- exclorxpoor This is especially common when a; are close one, and any arm that has not been explored for a few rounds would have a very high confidence bound. In that case, modified UCB is likely to shift in between arms very often, which leads to too little exploitation. (ii) As discussed in Section 4 unlike the modified UCB algorithm, AR2 also deals with the tradeoff of "remembering" and "forgetting" via the restarting mechanism, which especially important a fast changing environment such as the AR setting.
D Steady State Distribution of Rewards
In this section, we characterize the steady state distribution of the expected reward re(t). Lemma D.J shows that the steady state distribution depends on two probability masses at the boundaries and probability density function between the boundaries.
Lemma D.1 (Probability density of steady state distribution). Consider the steady state distribution of (t),, which follows the AR process with truncating boundaries defined Section 2 Suppose that at the steady state distribution, we have two probability masses at the boundaries, tee., P(r,(t) =
[8] = P(rr(()) = - p, where E (0, 1/2) depends on a and a. Then, the steady state distribution between the boundaries can be characterized by the following probability density function (PDF),
denoted by fp (-00, R. (R.)
fo(T) = (1 Cp)C(a, exp (a (a-1)u²
E (- 02)
(11)
a²0²
where C(a,a)=
VI=a
is a normalization factor and erf(z) 3n Sot -8 ds is the
RiVI-a 000
Vingerf
functionn
5

---

Given Lemma D.1 we are now ready to define the steady state distribution of rt())):
Definition D.2 (Steady state distribution rewards). Let random variable with range [-B, R whose probability distribution characterizes the steady state distribution of rf(t). It has probability masses on the boundaries, i.e., P(r RJ P(r [ [] p, and probability density function fp on (-R, 0.) as defined in (11). that satisfies the following conditions:
1. IP [a(r +) RR = [P + - R -p
2. IP [o + 6) = L (x) for all E (-R, R. R).
(
Note that the probability masses the boundaries result from the truncating boundary condition, and by symmetry, the masses on upper and lower boundaries are the same. If one adopts reflecting boundary condition, we would have p = 0; if one adopts an absorbing boundary condition, we would have p = 1/2 (see [44] for definitions of the aforementioned boundary conditions).
We remark that for any fixed E (0, 1), when the steady state distribution of (t) can be well approximated by a constant function. In Figure 3 plot the PDF of the steady state distributions for E {0.3, 0.6. 0.9} (with and numerically compute the value of (see legends in Figure It can be seen that for larger the distribution within the boundaries becomes almost "uniform a - O, it can be seen both from Figure 3 and from the definition of fz(z) in Lemma D.I that the distribution can be approximated by normal distribution.
the probability density function fa( in
0.8 and OR 1).
the other extreme case, when
0- 0-03.p33x19
or 0...p 0.04
1.5
0...p
1.2
1.00
0.5
0.00
-1.00
-075
-0.50
-0.25
0.00
0.25
0.50
0.75
100
Figure 3: PDF of the steady state distribution of AR process with truncating boundaries for a (0.3, 0.6, 0.9). a = 0.8, R 1. The probability masses associated with the steady state distribution are included in the legends.
Proof of Lemma D.I: We first note that the continuous-time analogue of AR-1 process is Omstein-UUlleneedn (OU) process 22 defined as the following stochastic differential equation (SDE):
dr: (0 rz) dt CdW,.
(12)
where K. 0, Ç are constant parameters and W, denotes the Wiener process If we perform Euler- we get
Maryuama discretization (see 34) on the above OU process at At, 2
Tt+1
k0At
(mAt 1)r, (e,VAt,
(13)
where ei is standard normal noise. Now, recall from Section that the evolution of expected rewards evolve as an independent AR-1 process:
ri(1 + aR, = or (r)(1) + +())
(14)
where (t) ~ o). Let (t). By coefficients in 13) and 14) the two equations are equivalent if let = 1- a, 0
wa, Al A 1. By plugging the values of coefficients into (2), the continuous-tin analogue of [14] can be described by the following SDE:
dr. (a 1)r,dt + aodW.
Let fp(x) be the PDF for the steady state distribution of r:(() on (R, R), given that the probability mass on either side of the boundary p. We can now solve for fa( by solving the following
'For numerically simulating steady state distributions of SDEs, 34
We will see that when v: follows an AR-1 process with AR parameter a and stochastic rate of change a.
these constants take the following values: x = a, f = 0, 1) = aa.
A Wiener process W; is continuous-ting stochastic process that satisfies the following propertics: (i) W9 (ii) W. is continuous in t; (iii) {W: Wi)cea i has stationary, independent increments; (iv) We4a W. (00 t).
(See 20 for more details.)

---

ordinary differential equation (see 233 44 for a discussion of forward and backward equations for SDEs):
1
(1 (f)(((())+++((()) + 5
(15)
which gives
(a (a-1), 1)
fp(z)= Č(a, σ) exp(
a²o²
for C that depends on a, a. Since (2) is probability density, we can solve for C(a, by requiring
R
[ R fa(2) dr = 2p, given that the total probability within the boundaries is 2p. This then
gives
C(a,o) = (1- 2p) a//iaa erf (Byl-a) (1 - (ap))
where C(a,, o) is defined in the statement of Lemma D.I
E
Additional Illustrations
E.1
Illustration of g(k, o) in Regret Lower Bound
Recall that in Section 3 we characterize our regret lower bound to be Slg(k, d)ao), where g(k, at a)) is the probability that two best are within distance of each other any given round under the steady state distribution, with closed form presented in Equation (16) in Appendix F
To better understand how g(k, at a) evolves in terms our parameters, Figure we plot the evolution of g(, a, o) in terms of a in two different regimes: (i) a small-c regime when = 0.4, and (ii) large-o regime when
0.9. Note that here, consider the regimes separately because Section we will show that the large-a regime inherently much more challenging than the small-o regime.
In Figure 4 we see that in the small-o regime (a 0.4), g(k, a, o) is roughly constant as a increases, while in the large-a regime (a 0.9), g(k, a, σ)) is roughly linear in terms of a. To understand why, recall from our discussion in Appendix Dithat when a O, the steady state distribution approaches a normal distribution with standard deviation proportional to ao, while when a + 1, the steady state distribution resembles a uniform distribution. Hence, when a is small, we expect g(k, a, a) to be roughly constant in terms of while when is close to one, expect g(k, o) to be roughly linearly in terms of a. Here, our observations Figure concur with our discussion Appendix
0.8
0.7
glk, a.a)
0.6
0.5
-
a
0.9
0.1
0.2
0.3 0.4
0.5
0
Figure 4: The evolution of function g(k; ar o), as defined Equation (16) Appendix respect σ. Here, we set {0.4, 0.9), and R 1.
with
E.2 Illustration of Upper/Lower Bounds in the Small-a Regime
In Figure 5 we illustrate the evolution of our upper and lower bounds in the small-a regime (i.c., (0, a:)). Here, take 0.4, and similar plots can be obtained for different values of < Recall from Section55thaa this regime is considered less challenging due to our result in Theorem [.1 which states that any algorithm can attain optrmoptimal performance when a E (0, ā). Here, Figure reveals that our upper/lower bounds indeed have the same trend of increase in terms of a in the small-a regime, which complements our result in Figure [that shows our upper/lower bounds match in terms of a in small-a regime).

---

0.150
0.125
value
0.100
0.075
which characterizes the Vagl logk
00
0.050
V1
gik. a, aiaa
0.1
0.2
0.3
0.4
0.5
Figure 5: Comparison of the order of the regret upper bound in Theorem 5.1 and the order of the
lower bound in Theorem 3.1 with respect a, obtained with & = 0.4, R 1, C' 0.4. This plot complements Figure that shows dependency on a.
E.3
Illustrations of Upper/Loower Bounds and Per-Round Regrets of AR2
To further highlight the significance of Theorem 5.2 and how well characterizes the performance of AR2, in Figure(6) we plot the evolution of the upper bound in Theorem 5.22 the lower bound Okka² a?) for a close one, and the per-rount regret attained by AR2, at different values parameters a and respectively. In Figure 6a the per-round regret AR2 increases at roughly the same rate as the upper and lower bounds. and stays close to the lower bound, a increases. In Figure (bb] the upper and lower bounds follow the same trend of increase with respect a. We note that upper bound loosens up as the per-round regret of AR2 experiences smaller growth and approaches the worst-case lower bound. This especially highlights the strength of AR2 in adapting to rapidly changing environment.
increases, the
10
10
valuee
10
10"
10
10
0.86
0.88
0.90
0.92
0.94
0.1
0.2
0.4
0.5
upper
per-round regret
upper bound
regnat
Tower bound
lower bound
(a) Evolution of the upper/lower bounds and per-round regret of AR2 with varying a. We take E [0.85, 0.95] and o = 0.4.
(b) Evolution of the upper/lower bounds and per-round regret of AR2 with varying We take a E [0.1, 0.5) and = 0.9.
Figure 6: Comparison of the order of regret upper bound of AR2 (Theorem 5.2 the order of the lower bound, and per-round regret attained by AR2 (averaged across 100 experiments). The constants of upper/lower bounds are tuned for illustration purposes. Here, k = 5 and R
F
Missing Proof of Section
Before we show the proof for Theorem 3.1 we first present Lemma joint distribution for order statistics.
Lemma F.1 (The joint distribution of order statistics of continuous distribution). Let ( ( .... < (k) be the order statistics of i.i.d. samples drawn from some continuous distribution with probability density function (PDF) ff fx) and cumulative density function ( (CDF) F(x). The joint
PDF of x x(5))x(i) for any < < S is
Xx0 (u MFF (1)
(v) - F())) (1-F(t)*
1)1(j 1)1(k: 5)
In particular, if we take i 1 and j = k, Lemma F. suggests that
fx(--1)x(>>> (u, v) k(k
1)F 2
f())f(())
which will be used in the following proof of Theorem 3.1

---

The proof proceeds in two steps. First, we compute the probability that the expected rewards of two best arms are close each other at any given round t. Then, conditioning on this event, we show that at the next round + 1, any algorithm incurs M(uo) regret with constant probability.
Proof of Theorem 3.1;
Step 1. We first lower bound the probability that the expected rewards of the two best arms are within ox of each other at round l. Recall from Appendix D that rt(()) follows the steady state distribution with probability mass p on the boundary and PDF pp(x) defined in (TT) within the boundaries. Let F(x)) be the CDF of the the steady state distribution of rr((). We can compute the probability that the expected rewards of the two best arms are within do by breaking the event into the following cases:
1. Both arms are at the upper boundary. This will happen with probability Σ (1 -) where denote the number of arms are at the upper boundary, i.e., have expected reward R.
2. The best arm is at the upper boundary, and the second best arm is within the boundaries.
This will happen with the following probability: k:k - 1) p -a- ((o))~2(((x))d)
3. Both the best arm and the second best arm are belween the boundaries. This will happen with the following probability: k(k--) 1) fo J_R ((()) this probability, we used the joint PDF stated in Lemma
To obtain
4. The best arm is within the boundaries, and the second best arm is at the lower boundary. This will happen with the following probability k- =_ RR fz(z)dz ph-1
5. Both arms are at the lower boundary. This will happen with probability p².
We define g(k, a, o) as the probability that the expected rewards of the two best arms are within oo of each other at round t, which is the sum of the terms above:
R
g(k,,,0)
Σ j=2
(
k
p0(11 (1 -)- + AAlk- 1). 1p
((o))22f(()dds
R
R
paa- RR
/ a0
+ kkk - 1)
((x))~2fp(x)f) fp(x)f((x= + 2)drdz + k. F(x))~
fo(x)dx pt-1 +p*
R
R
(16)
We now make a brief remark about the order of g(k, a. as a approaches one. First note that among the aforementioned cases, the first three cases would happen with probability at least 1 1/2 given that the steady state distribution of expected reward is symmetric and the expected rewards of the two best arms are skewed towards the upper boundary. Conditioning on the third case, i.e., both the best and the second best arms are within the boundaries, as a approaches one, the conditional PDF can be approximated
uniform function (see Remark G. in Appendix D related discussion), and hence the conditional probability that two best arms are within ou of each other are of order 2 (kar)). Further, conditioning on the first and the second cases, i..., the best arm is at the upper boundary, the conditional probability that two best arms are within au of each other are lower bounded by 2 (karr) We thus have g(k; a, T) 2 Q(kar) as approaches one.
Step 2. Let A be any algorithm that selects arm A(L) round t. In this step, we show that conditioning on the event that the two best arms are within axr each other at round t, with constant probability, A will make a mistake at round & + 1 and incur regret of order O(ar).
Without loss of generality, let us suppose (t) 2 2 (t), and that algorithm A(t) selects arm 1
at round (if AAt)) selects a different arm at round f, the following proof works similarly). We first assume that rn (4) E [-0 + 3o, OR - 3o Let (xx) be the CDF of standard normal distribution. Since
<e(() is.dd. N(0, a), when pulls arm at round f, with constant probability ( 1, we have Je, (t) S g. Let A(t 1) be the arm that A chooses to pull at round + 1. At round + 1. one of the following scenarios will take place:

---

(i) If (((++11 = 1, then if (t E [2o, 3o it will incur regret
r2(t+ - (1 1) (r2(t) + c2(() ri(() (1))
2 a - |r2(t) -
-ri (1) - (ta))))
2 a(2 ao 2
00
2
The event e2()) E [2o, 30] happens with constant probability Φ(3) - -4(2). (ii) If A(L + 1) = j for any j # 1 at + 1, then if e,(() 1-20, -o]. it will incur regret
ri + 1) - (t + 1) = a (ri(t) + (t) - (t) ct)
2 (1) - (())
2 a 2 +
a0
The event (1() E 1-20, -o] happens with constant probability +(2) +(1).
In all of the above cases, we show that A will incur regret at least az with constant probability, conditioning the event that r(1) - ((2) S ao. If ri (() is close to either side of the boundary, similar analysis can establish the same result. To see that, if rı E [ 3o, TR| and A pulls arm 1 at round f. with constant probability we have (t) E [-2o, -3o Then, we have one of the following: (i) A(t + 1) = If (t)
2
g arm is sub-optimal and incurs regret by at least ag (ii) A(t + 1) = for some j + 1. If (t) E [-3o, -4a], arm j is sub-optimal and incurs regret by at least ao. This, again, shows that A incurs regret at least l(ar) at round t + 1 with constant probability. The proof follows similarly when 1 E R - + 30r.
Combining step 1 and 2, conclude that the per-round regret of any algorithm A is at least Mgg(k, a, a,),a)) )ao) which concludes the proof.
G Missing Proof of Section 5
Proof of Theorem 5.1 At any given round I, recall from Appendix D that r((() follows steady
state distribution as defined Definition D.2 Let us define (t)
s.1.d. N(0, VI-az) ). The variable
(t) has the following PDF:
a2 V2TTO
(a 1)x²
f(x)
exp
2a
R. we have that P [I]r(tt) > s] [t) s| which can be obtained by directly computing both probabilities. Intuitively, one can think of the normal distribution above as the steady state distribution of rz(t) that follows the same AR-1 process rt(++1) = (rr((t)+()))))))))))))))) (t))), without the truncating boundaries at (- RR. As result of the truncating boundaries, the steady state distribution D (characterized in Appendix D) is more "concentrated" 0g
for all x R. Note that for all 0
than the normal distribution (0, -I- ). Now, using the concentration bound for normal random
variable (see Lemma
J.2
we have
2 )
P [ri(t))
c ao
P [r((t)] >
c
ao
< 2 eexp(
vI
vI a²
for every arm E [k). Now let 8 = 2 exp( :)) By the union bound, with probability at least 1- kd,, would have (t)) I VV-az for all i [k). And hence Ar:(t) < 2c /i= for all i [k]. Let
us denote the above event E. If we set //loggl/ao) log (2k), would have 8 22 and hence P[E] > 1 kd 1 ag.
10

---

Let A be any non non-annto anticipating algorithm that selects arm A(t) at round t. The expected regret A incurs round t is
A(Ar FE ( (1 S 2c
+2 00
v1 a²
0
ad a²
= log
=0
v1 V
Given that the per-round regret is also bounded by 23, this naturally gives
= =omii(Voog((//a log
E
Ar A())
v1 a 23)
In Section we choose ā - 0.5 as the threshold value such that when a E [ā, 1), the problem is more challenging and thereby of our interest. Given the threshold ã. we further expand on the remark made in Appendix which will be useful in the proof of Lemma
Lemma/6.4jin 6.44in Appendix [H]
Remark G.1 (Uniform Approximation). For any fixed density function that characterizes steady state distribution of ((( within the boundaries can be well approximated by constant function. This can be seen from
(0, 1), when 1, the probability
(a (a-1)x²2 a²o²
max fx(z) min fo(x) = (1 (1-)p) x 0R R) ZE( R)
exexp
1 - exp
C(a,o) - 0. a=1
In particular, by Lemma D.1 for any E [ā, and 2 c'vl a, we can bound the PDF fp(x)
that characterizes the steady state distribution of (t) for all x E [-OR, RR] using constants:
p- S fz(2) S P+.
(17)
where p- 2p) a) (-R2/a²C22 pt =1 (11-pp) C(, -a) are both
constants.
When jā, 1) and a o(vI ar., the steady state distribution of (t) can well approximated by a normal distribution, and similar to what we show Theorem [5. in this case even the naive algorithm performs well. We thus focus on the more challenging regime when a E [ā. 1) and Cavs-(((VV) - a) in the following analysis.
H
Missing Proofs of Section 6
H.1 Step 2: Good event and its implications.
In Section 6
define noise term in that shows the influence of truncating boundary:
et a(t) - 1 (((r(((+++(0))) -or()) otherwise
if ar:((() + +x)(() [-RR R
The new noise &t(t) satisfies the recursive relationship: r+ ar;(t) + (t) Recall that here, the boundary function is defined as B(y) = min (max R], R..
Before proceeding with the proof of Lemma 6.3 we first show an auxiliary lemma that establishes the relationship between (t) and (t).. In partrcular, Lemma H.l shows that if the weighted sum of ct(t) is small with high probability, the weighted sum of (t) also small with high probability.
Lemma H.1. For any 0, E
[k)], and rounds t1, have
41
PP
Σ
<
Σ - ( S
(18)

---

Proof of Lemma H.1:
For simplicity of notation, let us drop the notation for dependence on i. We first show that the tollowing inequality holds for any r(to):
1- Σ ath a s s 2 P Σ t a ((1) S s((tr
Pl
(19)
To show (19). we first consider a fictional scenario in which r(.) only gets truncated at the first time it hits the boundary, and longer gets truncated afterwards. Let 1' denote the first round at which r(.) hits the boundary. With slight abuse of notation, we define corresponding fictional noises such that e1 (1) = e(l) for all & & and el(() = =(L").
el (lo),...., (1 -
Since the expected reward r(.) hits the boundary for the first time at t',, we have (ar(t") +ac(t)) R for some to S t' t1. Recall that in the fictional scenario, (t <(t) for all f. Let
L = ==aa" tr())) Ei = Et= (l))). Without loss of generality, let us assume that the expected reward hits the upper boundary R, i.c.
R < ar(l)) + ac(()) = I. +
Σ a =1)=+ I. t=
(E(
Let d = -++Es aacttt(((t))
0 be the distance by which the expected reward exceeds the boundary t'. By (5) and the definition of the truncating boundary in Section 2
we have
ar(t') (t'(t') B(ar(t') + ac(t') R.
From the discussion above, we have E1 + (t') R - d L and Ei + 1 (t')= L. Since in the fictional scenario, the expected reward only gets reflected at the first time of hitting the boundary, we also have e (f) e(t) for all t'. Let E, Ei=r- a=1=te(t) 'e(t) denote the weighted sum of the noises after time of reflection t'. Now conditioning on the initial expected reward r(tu), we have
t 1
4 6n (1)
S s0(r(())
Plaa- E + n-
61(1) + E2 S 8 [1((()))
P
11 ( D) s Es 8 (R L)) L))r((t))
L)
2
P
1 d L) Eg
(TR L) r(to))
4-1
IP
- Ej ni (((() E2 S s s
IP
Σ n - e(t) s s s
(20)
Note that the inequality in 20) holds because Eg normally distributed (it is a weighted sum of normal noises). we let ai = a -t' 1 ( L) and Ø2 = -- (I + d - L), we must have
1911 < [g2/- This, along with the normal distribution of Eg, gives
P|-s - q Es < s - 4il 2 Pl-s - q2 S Eg S -2].
Following the same procedure as above, we can define fictional scenarios in which r(.) only gets truncated when it hits the boundary for the first m times, for corresponding fictional noises em (lo)) (l,))..., - 1) and use the same proof ideas to show
to. We can then define
IP
Σ
a
cm (1)) s s r(()))
2 p
Σ a fe---mm-(00 s | t=to
for all m < t1 to- Note that if m i1 lo. the fictional rewards 6. ē for all t (1a, 1]. Hence,
4-1
I
Σ 200 (s)r((o) 2 P t=
Σ th + (00) S s|((t))
Finally, since 19 holds for any initial expected reward r(to), taking expectation with respect to r(4p)
gives [18. which concludes the proof.
12

---

Proof of Lemma 6.3: Let us first consider the sequence of noises e (t) (i.e., the noises before
applying the truncating boundary). For any fixed i E [k], and for t' { Aep t + Aeple we have
(tt) Lid. ((0,0). o). Then, by Hoeffding's inequality (see Lemma J.3 where for 1 S j S t to.
toe 22-1 16-1) set X, = a ( j)), of a' and t1
fort Aop S to < t - t Dp
l-a7
we have
h1
c /
(ao) ) 2k
Σ t Ec(1) > cooo/ (a² a2 2o0t- -02) S 2 22xpp(=
2
bp
where the last equality follows from Co =
14loog1/// 4 Aup + 2 log (4k).. By Lemma H.1
we can use the above inequality to also obtain a concentration inequality for the weighted sum of the new noises (t), which incorporate the influence of truncating boundary:
P
a (() > co (a2 2000/(22-2lt-tot/////
2011) - a²)
t0
(ot QQ2) $ (av)²
$
P
Σ
> co la² -00//02--tth--b//////
21:12
Since we have k arms and the number of sub-intervals to consider in (1-1 -pppp l & is we can apply union bounds get
2mm12
2
k
4-11
(() =
Σ
Σ
a
2c()
> cuo cooVia (a2 a²(11 -02 a2(1) a2)
iml t- Sto
Stg <t1 St+
t=
2 up (2Aep k
1)
(ao)²
k
(ao)²
24
= (ao))
2
2k
2
i=1
Having showed that good event G()) happens with high probability, we now establish a number of important implications of the good event:
In Lemma H.2
we show that the expected reward r.()) satisfies a series of concentration inequalities. These incqualities guarantee that our estimated reward (t) does not deviate too much from the true expected reward rt()).
(ii) In Lemma reward.
H.3
we show that AR2 does not wait too long to play an arm with high expected
(iii) In Lemma H.4
we show that the best expected reward rt) is not too far away from our estimate reward for the superior arm Fsup (t).
These implications will be critical for our proof of Lemma 6.4 Before we proceed, let us define the following:
F(At) e coo V a² + a+ + 20 = coo (a² a2( a??)
(21)
where the second equality follows from the geometric sum formula. The expression (1 will be used throughout the rest of the analysis. In particular, since e = 24c,, the triggering criteria becomes: at round t, an arm i + duup (t) gets triggered if the following is satisfied:
Psup (t) (t) S ei (a2 - a20 -20- /(1 o2) (1()))
Lemma H.2. Given (t). for any arm E [k] and any rounds to, t1 such that App S to < 4 S
t + Dep the expected rewards satisfy the following inequalities:
Ir((t)) at - (to)) S F(t1 to)
(22)
(r1(t)) at to (to) S F(ti to)
(23)
Ar.(ti) - to $ 2F(ti to)
(24)
13

---

Proof of Lemma H.2
Given the AR-1 model and 5 we have the following recursive relationship
r.(tt) = a [n.(t1 - 1) + Et(1 - 1)]
(a(r:(11 2) + (11 2)) + Es((41 -1)]
4-1
a rr Σ a (t)
(25)
by repeating the above steps. Then by Lemma 6.3 we have that
41
(re(ti) - a ar
=
Σ
aa- (t))
S F(tt to);
to
which concludes the proof for 122g
As for 23 note that
(f1) max S max {a (a"1-tar,(th + F(t1 10--t))) to)) S a01-ta (to) + F(t1 to)
sE[k]
sE[k]
and the other side of the inequality can be derived similarly.
The last inequality (24) easily follows from (22). (23). and the triangle inequality
Arr(l)) (or-orrrloo))) S (rr (4) ra ((1)) a -o--too (r" (40) rr((4))
| (4) 1 (46) + (1a(11) aa1-for;(la)) s 2F - lo)-
This concludes the proof of Lemma
Lemma H.3. Suppose we apply AR2 to the non-stationary MAB problem with a E (ā, 1) and
k S K(a)), given (()), the following holds for the best arm i at round t: 1 - T((1) S 4k 3.
Suppose a E |ā, 1). Let arm i be the best arm at round t, i.e. i arg max, (t). We let r = (t), and let - 2 r be the triggering time of arm i after it gets pulled
Proof of Lemma H.3
at round т. First note that by design of AR2, must have t - < 2(k 1), since at any given round there are at most & triggered arms. We would prove the statement of the lemma by showing the following incquality:
rlig T S t trg +
(26)
If (26 holds, we then have ( ---= (r r) + (1- )(i))= - 2(1 - + S 4k - 3.
Suppose by contradiction that (26) does not hold. By the triggering criteria, have
Psup ( 1) Pr 1) 24 F((r"ie T)
(27)
j = (7 1) as defined in ( Hence we have Sau -بار 1) = r, ( 1) (7
ar 2). Let us assume Psup "ig 1) r, (7(" (ii 1) and the proof follows similarly for the
other case. Since we also have (- 1) = a - ((x = a m - +1), (27 can
be rewritten as
Ty( 1) a (T(T + 1) > 24 F((r"ie - 1) 7)
(28)
By 22 of Lemma H.2 we also have the following two inequalities:
(t( S a -- (r+1) +
F(t - (T + 1))
(29)
(t) 2 a - (7 (r 1) F(t (7 - 1))
(30)
Then by 29 and 30 we have
(t) - (t) >
a - (-' (r - 1) - Fitt (r - 11) - (a' + +) - (T 1))
2 a² +1 (- - 1) - a." t - 2-2 (T + 1) - F(t - (7 1)) F(t - (T + 1))
2 24 a +- F((Ttri 1) - 7) - F(t - (f - 1)) - F(t - (T 1)),
33l)
14

---

where the last inequality follows from 28 Since & S K((a,, we have a² a-- 2 a 2 which yields
TT(1) - (t) 2 24
8 F( the - T 1) - F(t - th + 1) - F(t - 1).
Since uig - 2 1 --ii 2, we have F(r - 7) 2 F(I - ,rig + 1). This further yields
1
(t) - r((()) 2 (24
1)
F( - - - F(t - T - 1) = 2F( the T - 1) - F(t - T - 1).
8
(32)
Note that if -rrgg- T > ui + 1, then since t - T = (t - -lrie) + (7 -), we must have
2(7 7) > - - 1, and thus
2F (T wis - T 1) = 200o V a² + -1((100---11
> 2000 V a² +a----1
co0 (v a²
ta
V a at-r+1 r+1 +... a2(1-))-22
2 coo cooV V a²
+ +... 2 since va + vb 2 va +
= F(t - -
Plugging this into 332 giver -r.(t) -tr O, which contradicts that arm i is the best arm at t. Hence,
we must have -'n - St - + 1. By our previous argument, this then gives t - S 4k 3.
Lemma H.4, Suppose we apply AR2 to the non-stationary MAB problem with [ā, 1) and
k K(a)), for any arm i [k] and round we have
(1)
Sup (1) < &Ocooaa))
(33)
where Faup (t) = - (t) and sup (f) is defined in (I)
Without loss of generality, suppose that even, and as a result = isup (t). The proof then proceeds in two steps. In step one, we establish a recursive incquality for the estimated reward of the superior arm. In step two, we show that the estimated reward of the superior arm is in fact close to the expected reward of the best arm.
Proof of Lemma H.4
Step 1: Establish recursive inequality for Fsup (f). We first assume that ixup (t) It-2 and hence
Ssup (t) = aB(aR Ri (t)(t 10t--27 2)) = ar am (t - 1). We also have
(e) (t) = O. (t) (t 1) + (t (t - 1) = Pmsp(t) + (e 1),
which then gives
(t (t) 2 Smp acqo
(34)
by definition of the good event G(I) (set to = and 1 t 1). Since L, = (su((t), we additionally have
Psup + 1)= (ta (t)) = (t)) + (n))(t)(()
2 (t) (t) acga
(35)
Combining (34) and (35) gives us the following inequality, which the desired result.
Faup (t + 1) 2 ((Fsup(t) - acoo) - acoa 2 mp 2egar..
(36)
On the other hand, if ismp(() (1) = I--1, we have (1) (1) = B(aa (16-11 1)) = Fap (4), and combining this with (35) also gives
P (1 + 1) 2 ar (1)))(1))()) - acgo = ur - acoo 2 (1) 20qav..
Overall, we show that P + 1) 2 (t) - 2egar, which completes the proof of the first step.
Step 2: Show that Sup and (I) are close. For simplicity of notation, let j be the best
arm at round t, so r* (+)))= (t). Let (t). Recall that by Lemma H.3 we have that
t < 4k - 3 = O(k). First note that
Sou (4) 2 af sup (1 1) 20gur
by 36
2 a' (r+) Sup (T + 1) 20 ... a (r++))
by applying 336 recursively
2 0² (++1) kuu (T + 1) - 2c + ... + a -4)
+
since - T - 4k -3 3
2 20 3a' B(aR, RT( - 200 - 4)
since Pau + 1) 2 (T + +1) 1)= = B((R((((
- + 1) - O(crork)
(37)
15

---

We also note that
(1) = S a
by 22 of Lemma H.2
- +
a2(1-1-1)
(38)
S (r
= -a- +))
since - I 4k - 3.
Combining (37) and 38 then gives (1) /sup (1) S Occoaak). The proof works in similar
fashion for the case when f is odd.
H.2 Step 3: Distributed regret analysis.
Recall from Definition 6. that the distributed regret of arm at round is defined
D1(t) ( Ar:(T,(t) 1 + +o ((( a2(1-7((0),
(39)
Before proceeding with the proof of Lemma 6.44. we first establish the following two claims, In Claim H.5 and Claim H.6 we respectively bound the nominator and denominator of (t),), condi- tioning on the good event (t) and the value of (t).
Claim H.S. Suppose we apply AR2 to the non-stationary MAB problem with a E [a, 1) and k S K(a)). Given (t). for any arm i E [ks). let & Ar,(t) > for time Tt(t) I t < T steex((t), we have that the nominator of 39) satisfies: a (0) (r(((())) - On + cooavk)
Proof of Claim H.5
For simplicity of notation, let r = (t) and - Ti next (t). Let gi be the first round at which arm gets triggered after it gets pulled round T. We divide our proof into two cases.
Case 1: ,trig J
St t- 7lri S Okk), we must have = O(k). Then by ,rri,, If rin T
22 of Lemma H.2. we have
Ar,(t) ( 2F(t 2c0oaat Stntttt-sSOooaaaa O(corrak)
a 1 (r.(T) S =n
+ a 2(-T) Ari(T) S O cooavk) < +
Case 2: flrig
,lrsg, Consider time such that t < next Then, we have
Fsup (1) max (B(aRI, (1 1B), 2ll 2])} max {rr- (1)-1(1), or), _(--1)) 1)}
I max (r" (1), (1),ar" ar arr(( 1)} < max {1)()) (()()))))))))))())))) 20 a²
(3) of Lemma H.2
r" (t) + 2epoa.
(40)
Let = tig - denote the round right before the round arm i gets triggered. Then since at round /' the arm has not been triggered, we have
24F(1' 7) < Pau (1') (()
< (1') + 2e0 a² - r; 1)
by 40
(r,(t') + 2c0oa F(ll' (T+ 1))
by 22 of Lemma H.2
Arr(t') + 20joa FF(t'- -
(41)
This then gives
F(t' - -) (Ar;(t') + (cqooa))
(42)
23
By 22
Lemma H.2 and Equation 42 we also have
Ari(t) Ar.(t) 2F(t t) < (r;
Ar, + Ochra))
(43)
23
16

---

We also have
a 2k Ar:(t') S a Ar,(t')
(44)
since - -1 --=-ltg +1 v 2(k 1) + = 2k - 1. Now since k S K(a)) = [1og(()) log or + 1),
we have a 2 2 8 and hence
An((t)=An(tt) Ar((t) + (cqaar)
(45)
23
Now by 22 of Lemma H.2 we also have
2 Ar((tt) + O(cra)),
Am((r) (n)))
Ar((t) +
(46)
23
where the last inequality follows from
42 and - S t' T. By multiplying the last equation by
an and by applying Equation (45) we then have
cT (ri(T) S aa" -r
(Ar(()) (1,) + O(coao) S (1+
2
ja'-'' Ar;((') )a'""Ar;(())- + ( - o)
23
23
(t, + O(caao)
$ (1 + 23' 8
+ O - O(rr((( + cgoo) = 0(1) + cg(ro)
23
(47)
Since ( /- 0, we then have ((--)) Ar:(T) S 0(1 +
In summary of both cases, we have a (t-r)) Ar,(T) - O(1 cjoaVk).
Claim H.6. Suppose we apply 182 the non-stationary MAB problem with a E [ā, 1) and k S K((a).
Given (t)), for any arm i E [kc], let 17 & Arr(t) > ffr time S < quen, the denominator of satisfies
1 a² +... ((+-1) 1- a
n²²
max
2 1.
Proof of Claim H.6 The first equality follows from the geometric sum formula. Since 1 1=a2+ + a 1) 2 1. it suffices show that it is also lower bounded by U
t/²
). Let S t next
and recall that v) (r)(t). We divide our proof into two cases.
Case 1: a (T; S /22 Then by (2) of Lemma H.2 we have
||| a² 1- (rx(T)) = (rr)()) a " Ar((T)) s 2F(t -)
22F(1 -) 2 1/2
20 / (1 a2(l-r)) //11))/11111 a 2 n/2
11²
+11 - -01-((((-)) (2(((r)) /(11 - x²) > l
2020
2
1- 22T 20
1 1- a 2(- r)
Since AT 2 t- T, we have
2 91
1- 0²
1 a²
G G022222
2
1 1- a 247
n
Case 2: a arrr)r) > 2 We would show that
2 12(
) We have
1 a²
G/0
2
202222222
ft()) um (t) - rx(()
2 (r" (t) Ocoooak)) (r- (r))))
by Lemma H.4
a' : Ar((T) + (r'(t) -a" -T(()) Ocooaak)
7 (2F(1- - -7) + +(coorak))
by 23 of Lemma H.2
2
7 (kF(t -)))
2
(48)
17

---

Now consider ,l the round at which arm i gets triggered. By the triggering criteria, we have
fsup(T"BB) ( s 24F thg r)
!
0 (KF r)) - 24 -) by (48
2
0 (F - -])) 2 !
2
a
a -
rp
2 0
by 21
1- a²
c0 2
22 -))
0
a
2 o22
(49)
Since we must have ÅT > - T, we have
- 23r - 2
n
M
22
Having showed Claim H.5 and Claim H.6 we now formally prove Lemma 6.4
Proof of Lemma 6.4 Fix arm [X] and round t. For simplicity of notation, let (t).
Tooxs = T Te (t) and
Ar = An((). Let us write (t), Lco)
(Ar,(()))))))
(ID,()) goo (Ar,0)00)] and in the following analysis, we will bound the two terms on the right-
hand side respectively.
First term (Arm is optimal at round t). We first rewrite the first term as E ((Dx(1) (())) [Arx(0)=0)] (1)(()))( (Ar.(1) = 0}] ()r())())r()) 0}}-
Note that if (t) takes place and (f, = 0, we have
a² (--Ar:(T)
a (r:(T) Ari(t) S 22F(t- - T).
(50)
by
24 in Lemma H.2
By Definition 6.1
we have
Ar;(T)
a"-T Ar.(T) 1 a (a² + ... + a. +...
Dt(t)
21-T)
a
1 a + + a (
2000 a² + 2(
a 1-1+2
by 21 and 50
a² +.... 22
2010
a 1T-2
since 1 151-7 S Ar
Va2 ((())))
(51)
That is,
2000
BID.(0)G(() n (Ar: 03] <
a 1-7+2
(52)
+ + az
Now, let j be the optimal arm at time r. G()) takes place and (r: = 0, we have
Ary (t) |a'~>Ary (T) - Ar)(t) < 22F(t-1) T).
by 24 in Lemma H.2 Hence we have
(g (() 0)] < (() < 2F(( - T), where j = arg max (7)
(53)
< P Bj * such that Ar,(t) 2F -)(t-T)]
Recall from the discussion in Appendix and Remark G.I that the steady state distribution of (t) can be reasonably approximated by a uniform distribution, and (17) states that the PDF of the steady state distribution f f(x) satisfies p- < fxx < p+ for all x E [- R. R], where p-, p+ are constants. Now let r .,, r be k i.i.d. uniform( -1/ 1/2pp, random variables. We have
Ej A such that (t) < 2F -))
P the two best arms of {ri (t), ... (t)) are within 2F - T)
< P the two best arms of (r(...., r are within 2F(t r)] O F(tt T) III
(54)
18

---

Combining 53 and 54
thus gives
P(g(t) = = O(k: F(t - 7))
(55)
Overall, by 52 and (55). for all 2 have
((D:(())s(e) (a))())=))) (():(())((()) n (Ari(t) = P =0]
2000
a a'-7+2 0 F(t - 7)) Oc a2..
(1-
(56)
Second term (Arm i sub-optimal at round f), Given ((t) and the value of n - Ar,
we have bounded the nominator and denominator of (t(t) in Claim H.5 and Claim H.6 respectiivv..
For any time+ S nest in Claim H.5 we have showed a 21(--) Ari(T) O(1 + coooy /) and
(2 2 max {or cFoo )
17
in Claim we have showed 1 + a²
These results
then give
E (Am000000 X min - choook
11 + cocorkk }k]
naa
Let Ö = cooo VR, this then yields
E (D) & min {R( (x(*+
C
min { kl 82 Es ), O.
pp pp).n
This then further leads
{ k c in 8 ircasse
(i(1) g()) (A)(0))0)))) $
We can now bound the second term by taking expectation of the above expression with respect to Recall from (17) that the PDF of the steady state distribution of rı(t) satisfies p- S fxx) S p+ for all E R, RJ. where p_ and p+ are constants. This then gives
82 dn E[Da(())o() ( f(' k
= O(K0 log(()) O(2aa00 log(enaov (57)
n
and
(t) (ocant000)) $ Ō C.PP
Ari(t) < Ōj = = (58)
which provides upper bound for the second term.
Finally, summing 56 (7 and 58 gives L()) O(ciaa0 log(coao which
concludes the proof of Lemma 6.4
Missing Proof of Section g
Proof of Proposition 8.1 Before proceeding, first make some notational changes that would simplify our proof. Since we pull arm i consecutively for Tea rounds for some fixed arm E [ki), in the rest of this proof we omit the dependency of (t) on and denote R2 A Rt).).
Let us first define the loss function C(ax) stated in the optimization problem
à arg min L(a), (E())
(59)
1This follows from the fact that X(1) S X(2) < ... < X(a) are the order statistics of i.i.d. uniform(0, 1) random variables, then X(x) - X(k-1) follows the Beta(1, k) distribution with CDF F(x) = 1 (1 (1-x") x)* for E (0, (see, e.g.. (17).
19

---

which is the negative of the log- logeliiklhoodd function:
Tei
1
1 1i = 3 log [1 1- 2
8 a R
((a)= =
Test
Φ -aaR-11)
(60)
+ 1 [ = BR log
R - -a-Bt-11 2
R
aR
+ 1{ < R2 < R log 4
where ((.) is the CDF of standard normal distribution Note that the three terms in the loss function respectively represent the log likelihood of the observed reward at the upper boundary, at the lower
boundary and in between the boundaries.
Recall that ā is the solution to the optimization problem in Taylor's Theorem to obtain the following:
59
We can apply the second-order
((a) [(ā) (a) - a) 1
(a) f 2)²
(61)
for some & between true AR parameter a and estimated AR parameter ã In the rest of this proof, we will provide bound for ja al via bounding the first and second derivatives of the loss function C())
We thus have
To
O --aB-1)]
(-Hee1
('(x)= = Test Σ
Il = [.. "log''
1 0
o
0
t=1
+ -1 = -BR loo'' ( RR -
}] ( R
0
0
R - aoR
(-Re-1
+ -1(- R < R, < h} log'
$
σ
o
where log' h(y) denote the derivative of function log h(y) with respect to y. Let
me(o) =1 1 2.l''''' 1 Φ R aoRe-
+ 1i =- log' ( R aBl-ll)
R a-aRR-1)
4 R a -
+1[- < R < R7. - log'
o
Note that L'(a)= = Tei
Et (r) Rr-1
To bound the first derivative of the loss function, our next
goal is to bound
Σ/=1 4e (a). Let Sj- = =Ein ue(a). Observe that
S 5--1 S
sup
max log' [1 - (in)), log' (122,, ( - +(1>))
v1 2 w2c 2/o,00
Let us define
max log'11 [1 - o(11)), D(y2), (f((1) - (((z))}}}
L sup
(62)
2
- R/000
Since (1)) the CDF of the standard normal distribution, y/2 E (0, 28//) and y/2 E 22 0), we have that L. is a constant well defined by the above expression. Also observe that
E[S;- Sy-11$ S1] ((u((a))))_1.... Si]
R R-aBi-1
Φ( R aaa
P(R, = R
P(R, = - -R]
B R
R R-aR Ri
Φ
O R-aRi-1
- 06
R -a-all-
+P R < R₁ < R}.
B2 aB
/
- 41
R aR
R aR
R aaR
R R
= =
+ 06
+ 0
- 06
0.
20

---

where ((y) and (ty) are the CDF and PDF of the standard normal distribution. The third equality above follows from ct. being independent from Si...., SJ Hence, Sj is martingale with bounded difference.
By numa--Hoffdiing Inequality (see Lemma J.5). we thus have that for y > O, the following concentration result holds:
2
PIIST.. > L1 V 23 log S
(63)
Tea
Let us denote the high probability event, i.e., |STcll S Ln 2// ea log Teus as E7. Note that condition- ing on E,, we would have
1 T
R 1 L1 RR
27 log Test
(a)
vr(a)
(64)
Tost
Tost
We also bound the second derivative using constant T,2 2 as follow:
(a) =
1 Toi Test
1RR RR- -log" [1 [1- 20 R 1-aR(-1) |
1-
02
t=1
+ 1 = -R. loo" ( R 10-aaRt-) (aRt-1]] )]
Ri-1
0²
[ R aBb-1 1 R
|]
(
+ 11-1 < R4 < RF- log"
0²
Tea
R2
{ mmn { fonl-loog' log""1 [y]1)], - -log" Q(y2), log"( ((12)) }
inf
Test 1=1
2
un 000 R/oo).
x26-2 226-2R/0000
Toi
R2 σ²
L2
Test
(65)
Here, we define the constant L2
L2 inf MI R/)).
min
log"ll ((y1)), - llog (22)), (2((() - (122)) (66)
v R)
Similar to our arguments above, since pyy) is the CDF of the standard normal distribution, V1 (0, 20) and 1/2 E 22//o, 0), we have that L2 2 0 is a constant well defined by the last equality. Let V R?] > denote the variance of reward under the steady state distribution. Since R² is bounded, we can apply Hoeffding's 's Inequality (see Lemma J.4p that states
T V
(- Test VosV2
V2
P
Σ
R
Tos V
< 2 cexp
2082
Let Eg denote the high probability event that ETa RZ-1 ToaV < TaV Then, under this event,
we have that Dine
n2 2
TepV
2 Hence, conditioning on the event Ez, we have
VTa
C"(a)= 2 20
(67)
After bounding the first and second derivatives of L(a) respectively, we are now ready to show the proximity between our estimated parameter â and the true parameter a, conditioning on the high-probability events & n &g. By optimality of 6, have that L(ā) L(a). This, together with
(1), ). gives
1 c² a)² < -L'a a) S (C)((a) aa al.
//
(68)
Using
67 we can bound the left-hand side as
VL2
Cd c"(ā)(a a)² N
-(a a)²
(69)
20
21

---

Conditioning on E₁, we also know from 644 have that
L1 R
2y log Tost
[c'(a) lā al =
lā a
(70)
Teu
Finally, combining
668
69
and 70p
we have that with probability at least 1 2/T
2 exxp(-Tos 22 //T2
we have
L2 20
- (a - a)² 1
(4)
L1 R
27 log Teat
Jā ad
2
Tost
which implies
a 4o RT.1
27 log Tex.
L1
Tea
Concentration Inequalities
In this section, we state some useful concentration inequalities for subgaussian variables (see 29 for references).
g
45
Definition J.1 (Subgaussian variables). We say that zero-mean random variable X is o-subgaussian (or, X subG(a)). for all À R, E[e²X] =
22.2
In particular, note that X ~ [(0, o), then X subG(a)). Subgaussian variables satisfy the following concentration inequalities:
Lemma J.2 (Concentration of subgaussian variables). zero-mean random variable a- subgaussian if and only for any 8 > 0, [| 2 s] < eexp(- )
Lemma J.3 (Hoeffding's 's Inequality). Let Xi..... X2 be independent zero-mean random variables such that X, ~ subG(a,, then for any
1 Ej=
S 2 exp( 2 2Σ
n²s²
In partieular, bounded variables known to be subgaussian, and thus have special of the Hoeffding's s Inequality that applies to bounded variables:
Lemma J.4 (Hoeffding's Incquality for Bounded Variables). Let Xi, Xn be independent random variables such that a; S X; S b. Consider the sum of these random variables Sn, = Ei= X,. We
have that for > 0, P [| - E[S.]] 2 s] < 2 2exp
Σn
Another related concentration result is the Azuma-Hooffdingg's Inequality stated below, which applies to martingales with bounded differences.
Lemma J.5 (Azuma- (Azuma-Hoeffdine Hoeffding's Inequality). Suppose that {Sy 0,1. } is martingale and has bounded difference SSt Sa-11 1| S by almost surely. Then, the following concentration
bound holds for any E Z and > 0: P ([SN Sul 2 s) < 2 exxp
2
22


Reviews:
[{"review_id": "P0MwkpX7he", "reviewer": "Reviewer_UBzK", "summary": "This paper studies a non-stationary bandits problem where the reward rate of each arm evolves according to the AR(1) model, i.e., shrinks by a known multiplicative factor and adds an indep noise. They proposed an algo that strikes a balance between (i) exploration v. exploitation and (ii) remembering v. forgetting. As their main results, they showed that this algo achieves nearly optimal regret. Moreover, they presented a real world case study.", "questions": "- To ensure boundedness of the mean reward, you truncated the AR process. Why is this wlog?\n- this problem is reminiscent of the Slivkins Upfal COLT'08 paper - that paper also considered stochastically evolving reward rates, truncated at the boundary, and their results mainly depends on \\sigma. Can you comment on the connections between these two papers? E.g. does the S-U paper implies any preliminary results for your problem?\n- Can this problem be approximately viewed as RL? Specifically, assuming alpha is a constant, then the history older than log # rounds has little impact on the current reward rate. Can we encode the log n - step history as the state? (If so, the transition matrix is also known) Can we immediately obtain a regret bound using existing RL results?\n- the theoretical part considers AR(1) but the case study considers AR(4). Is this difference essential?\n\nother comments: \nline 145: \"2exogenous\" - is this a typo?", "limitations": "(typesetting issue) when I click on a reference, the pdf file does not jump to the reference page", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- the model is novel, neat and fundamental.\n- provided a nearly optimal regret\n- presented a high quality real world case study\n- the manuscript is well-written\n", "weaknesses": "- Since the main term in the regret is sigma, it is better to specify the function g in the lower bound (Thm 3.1), especially how it depends on sigma. After skimming the appendix, I am still not 100% sure whether the claimed UB and LB really match.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback! We’d like to address your questions below. We will incorporate the following discussions and fix the typo in our revised paper.\n\n**(1) Dependency of function $g$, upper and lower bounds on $\\sigma$.**\n\n* Our function $g(k, \\alpha, \\sigma)$ represents the probability that two best arms are within $\\alpha\\sigma$ of each other under the stationary distribution. To see how $g$ evolves in terms of $\\sigma$, we can consider the scenarios of small $\\alpha$ and large $\\alpha$ separately. \n\n    As depicted in Figure 3 in Appendix D, when $\\alpha$ is small, the stationary distribution resembles a normal distribution with standard deviation proportional to $\\alpha\\sigma$; while when $\\alpha$ is close to one, the stationary distribution resembles a uniform distribution. Hence, when $\\alpha$ is small, we expect $g$ to be roughly constant in terms of $\\sigma$, while when $\\alpha$ is close to one, $g$ should be roughly linear in terms of $\\sigma$. \n\n    Our statement above is confirmed in _Figure 5 in the PDF of the global response_, where we numerically computed the values of $g$ for different $\\sigma$ under the two scenarios ($\\alpha = 0.4$ and $\\alpha = 0.9$) respectively. \n\n* Having seen the evolution of $g$, we can see that our upper bound (UB) and lower bound (LB) indeed match in terms of $\\sigma$. \n    - For the regime with small $\\alpha$, we illustrate the evolution of our UB and LB in _Figure 6 in the PDF of the global response_. This plot reveals that our UB and LB have the same trend of increase in terms of $\\sigma$ in the small-$\\alpha$ regime, which complements our result in Figure 1 of Section 5 (that shows our UB and LB match in terms of $\\alpha$ in the same regime).\n    - For the regime with large $\\alpha$, we have already illustrated the evolution of UB, LB and the per-round regret of AR2 in Figure 4(b) of Appendix E, which again shows that the UB and LB follow the same trend of increase with respect to $\\sigma$. \n\n**(2) Boundness of rewards and our truncation approach.**\n\n* Here, we adopt a truncating approach at the boundary $[-R, R]$ mainly because it is a simple and natural method to ensure boundedness of the expected rewards. However, it's important to note that this truncating boundary is merely one of the many we're equipped to handle. Our main results would remain valid across various boundary conditions such as reflecting or absorbing boundaries, with slight changes in the PDF/PMF of the stationary distribution (see Appendix D for our discussion). \n\n* In our setting, in the absence of such boundedness, the variance of expected rewards under the stationary distribution would go to infinity as $\\alpha$ goes to 1, and it then becomes impossible to design any useful algorithm for such a volatile environment. Further, note that the boundedness of rewards is a common assumption in the MAB literature (e.g., Lai & Robbins 1985, Auer et al. 2002, Besbes et al. 2014), and hold in most real-world applications such as demand forecasting and ad CTR prediction. \n\n**(3) Comparison with [Slivkins et al. 2008].** \n\n* [Slivkins et al. 2008] mainly studies non-stationary bandits where the rewards evolve as Brownian processes. Their setup can be viewed as a special case of the AR model where $\\alpha = 1$ (see our comment in Section 1.2). In fact, if we simply take $\\alpha = 1$, our method and results are also valid for the Brownian process, and our upper/lower bounds would share the same dependency on $\\sigma$ as their upper/lower bounds.\n\n* However, our general AR model studies a broader spectrum of environments that accommodates $\\alpha \\in (0,1)$. As such, the algorithm designed for Brownian bandits is not directly applicable for general AR bandits. One key challenge that arises from the AR model is that the correlation between past and future information now decays exponentially fast. Hence, the design of our algorithm is different from theirs in two important aspects: \n    - While the algorithm of [Slivkins et al. 2008] can seamlessly leverage past observations from any arm to estimate its current state, we have to factor in the exponential decay of past values we've observed. This impacts our definition of the estimated reward, triggering condition, and the rate of the alternation mechanism. \n    - Our approach also mandates periodic restarts to judiciously discard outdated information. This becomes crucial for the general AR setup as any older data can swiftly become misleading.\n\n**(4) Viewing the problem as an RL problem.**\n* Traditional RL methods (e.g., Q-learning) operate best with limited, finite state space. In our case, following your suggestion, the state would be a $\\log(T)$-dimensional vector, where each coordinate can be any real number between $[-R, R]$. That is, the size of the state space is infinite, and hence such an algorithm cannot be implemented in polynomial time. Discretizing the state space could be a potential alternative, but the impact of such discretization on regret remains unclear given how the AR process evolves.\n\n    Nonetheless, we really appreciate your suggestion and believe that it is certainly a promising area for further exploration. We will mention it in our future works section in the revised paper.\n\n**(5) Our theory and the case study.**\n* We would like to remark that our theory and case study serve different purposes. We develop our theory around AR-1 processes mainly to shed light on the design of our two main mechanisms (alternation and restarting) and show near-optimally of our algorithm with theoretical rigor. On the other hand, our case study highlights the adaptability of AR2 to more complicated time series observed in the real-world (AR-$p$ processes with trend), underscoring its robust performance. Our hope is that the combined insights from our theoretical and empirical findings would inspire more works that explore bandits in a time-varied environment."}, {"review_id": "97x6mYGNvW", "reviewer": "Reviewer_jsRP", "summary": "This paper studies the problem of non-stationary bandit learning in bandits where rewards have auto-regressive temporal dependency. More specifically, this paper considers bandits where the evolution of the expected mean reward of each arm undergoes an independent AR-1 process truncated to a bounded interval. All arms share the same AR parameter $\\alpha$. The authors propose an algorithm Alternating and Restarting algorithm for dynamic AR bandits (AR2), which takes the AR parameter $\\alpha$, a stochastic rate of change $\\sigma$, epoch size $\\Delta_{\\mathrm{ep}}$ and a parameter $c_0$ as input. The algorithm “addresses the exploration-exploitation tradeoff by alternating between exploiting the superior arm and exploring the triggered arm within each epoch,” and it “handles the tradeoff between remembering and forgetting” via restarting. To illustrate the efficacy of the algorithm, an upper bound on the regret of AR2 is established, and is compared with a lower bound on the regret. Numerical experiments and a real-world case study on tourism have also been conducted. ", "questions": "My concerns and questions are raised in the Weakness section. In summary: \n1. It would be great if the authors could explain the intuition behind why the alternation mechanism can effectively balance exploration with exploitation, although it seems that the extent to which the algorithm explores is the same as the extent to which the algorithm exploits. \n2. Can the authors provide justifications of how well the algorithm AR2 performs when each of the assumptions $\\alpha \\in [\\overline{\\alpha}, 1)$, and $k \\leq \\mathcal{K}(\\alpha)$ in Theorem 5.2, is violated, and when $k$ is large? \n3. Can the authors explain why experiments are run against synthetic data instead of real data, when real data is provided in the tourism case study? \n\n", "limitations": "N/A", "rating": 3, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is well-organized and the exposition is clear and easy to follow. The use of AR-1 model in characterizing non-stationary dynamics is also well-motivated. ", "weaknesses": "The main weakness of the paper lies in the insufficient justification of the efficacy of the algorithm AR2. Specifically: \n1. The paper suggests that a key mechanism of the algorithm is “an alternation mechanism adept at leveraging temporal dependencies to dynamically balance exploration with exploitation,” without discussing the intuition behind this counter-intuitive argument. \n- One question I have is that it seems that via alternation, the algorithm explores and exploits at the same intensity. Shouldn’t the intensities change according to the AR-1 parameter $\\alpha$ and the stochastic rate of change $\\sigma$? \n2. The regret upper bound established by Theorem 5.2 doesn’t sufficiently justify that AR2 performs well, due to the somewhat restrictive assumptions. \n- The bound does not consider the range $\\alpha \\in [0, \\overline{\\alpha})$. Does AR2 perform well in this regime? In addition, I understand that some other naive algorithm performs well in this regime, but Theorem 5.1 cannot fully justify that because the bound on average regret explodes as the number of arms $k \\rightarrow +\\infty$ (the bound becomes vacuous when $k$ is large enough because rewards are bounded). Also, Theorem 5.1 does not apply to AR2. \n- The assumption of $k \\leq \\mathcal{K}(\\alpha)$ suggests that Theorem 5.2 can only be applied when the number of arms $k$ is small. For example, when $\\alpha = \\overline{\\alpha} = 0.5$, the number of arms $\\mathcal{K}(\\alpha) = 2$: the theorem only applies to bandits with two arms. \n- Moreover, the bound on average regret grows in $k^3$, which can be very large when the number of arms $k$ is moderately large. \n3. I also have concerns on the numerical experiments.\n- One concern is that although the paper suggests that a real-world case study has been completed, experiments were not conducted on the real data, but rather, synthetic data generated by an AR-4 model fitted to the data.   ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your valuable feedback! We’d like to address each of your questions below.\n\n**(1) Regarding the alternation mechanism,**\n* We'd like to first clarify that we do not always explore and exploit at the same intensity. At the exploration step, we only pull a triggered arm during odd rounds if the triggered set $\\mathcal{T}$ is non-empty (see Alg. 1). Our triggering condition (Eq. 2), defined by AR parameters ($\\alpha, \\sigma$), naturally determines the rate of exploration.\n* Unlike stochastic bandits, the dynamic environment mandates **continuous exploration** alongside continuous exploitation because the best arm keeps changing. Neglecting any arm for too long reduces our confidence in its potential. This makes balancing exploration and exploitation especially challenging (as discussed in Sec. 1), since the rate of exploration needs to be adjusted based on the amount of changes in our environment. Our alternation mechanism is tailored for this task, with the help of the superior arms and the triggered set.\n\n    To see that, consider the following two scenarios:\n    - In slower-changing environments (e.g., with small $\\sigma$), the triggered set may not always include arms needing exploration, allowing focused exploitation of the superior arm. For instance, if there are only two arms whose rewards change slowly, one might dominate for extended periods before the other arm meets the triggering condition (Eq. 2). In this case, our alternation mechanism makes exploitation its primary strategy, only exploring occasionally.\n    - In fast-changing environments where the best arm shifts rapidly, the triggered set is likely to always contain some arms worth exploring. Here, the rate of the exploration can be as high as the rate of exploitation to ensure that we keep track of all arms while not over-exploring.\n\nWe will add the above discussion to Section 4 to add more clarity and justification.\n\n**(2a)  Regarding the regime of small $\\alpha$ and Thm. 5.1,**\n* We’d like to clarify that a more accurate statement of Thm. 5.1 should be that **any algorithm** (including the naive algorithm and our algorithm AR2) would incur per-round regret at most $\\mathbf{O(\\min(\\sqrt{\\log (1/\\alpha\\sigma)+\\log k}\\cdot\\frac{\\alpha\\sigma}{\\sqrt{1-\\alpha^2}},2R))}$. The proof of Thm. 5.1 does not use any property unique to the naive algorithm. Our initial statement is meant to emphasize that in the small $\\alpha$ regime, even the regret upper bound of a rudimentary algorithm matches the lower bound (see Fig. 1).  \n* We remark that it is reasonable for the bound to scale with $k$ here. Even in vanilla stochastic bandits, the per-round regret scales with $\\sqrt{k/T}$, inherently increasing in $k$.\n* Given that Thm. 5.1 suggests theoretically sound performance for any algorithm in the small-$\\alpha$ regime, we therefore focus on analyzing the performance of AR2 in the large-$\\alpha$ regime in Thm. 5.2.\n* Moreover, our numerical studies in Appendix A show the superior performance of AR2 in both small-$\\alpha$ and large-$\\alpha$ regimes compared to various benchmarks.\n\nWe will revise the statement of Thm. 5.1 and add clarity in our revised paper.\n\n**(2b/2c) Regarding the number of arms $k$,**\n\nThank you for your question on (i) the bound $k \\leq \\mathcal{K}(\\alpha)$ and (ii) the dependency on $k$ in Thm. 5.2. We will address both points below.\n* The bound $k \\leq \\mathcal{K}(\\alpha)$ is mainly required for the rigor of theoretical analysis. Both this bound $\\mathcal{K}(\\alpha)$ and the $k^3$ dependency in our upper bound come from the loose upper bound we used for the number of triggered arms (in Lemma H.3, we used the fact that at any given round, there are at most $k-1$ triggered arms). See Line 252-259 of Sec. 5 for more details.\n* Theoretically, if at any given round, the number of triggered arms is $O(1)$, the bound $k \\leq \\mathcal{K}(\\alpha)$ would no longer be needed, and our upper bound can be tightened to $O(c_0^2\\alpha^2 \\sigma^2k\\log(c_0\\alpha\\sigma))$, which exactly matches the lower bound up to logarithmic factors.\n* Our numerical studies in Appendix A also reveal that (i) AR2 maintains its competitive performance even when $k$ exceeds $\\mathcal{K}(\\alpha)$; and (ii) our per-round regret grows modestly with $k$, despite the theoretical $k^3$ dependency. These suggest that the assumption/dependency on $k$ for our upper bound are artifacts of our analysis, rather than an intrinsic property of our algorithm.\n\n    For instance, when $\\alpha = 0.9$, we’d have $\\mathcal{K}(\\alpha) = 10.4$, but AR2 remains competitive even when $k=20$. Also, as the number of arms doubles from 10 to 20, the regret of AR2 increases gracefully by 20%, significantly milder than the $k^3$ dependency. See Appendix A for more details.\n\n**(3) Regarding the real-world case study,**\n* Using raw data from [36] in our case study wasn’t feasible for two reasons.\n    - Their data only consists of quarterly arrivals during 1975-1989, amounting to merely 60 data points in total. For our algorithm's learning process to be meaningful, a substantially larger dataset is crucial.\n    - Our bandit setup seeks to establish competing arms (demand for vacation packages) correlated with the same exogenous variables (the tourism demand). Yet, the provided dataset comprises only a single time series without accompanying data on the demand for vacation packages.\n* To address these, we used the AR parameters from [36] to model demand for different vacation packages (arms). The authors of [36] fitted the logarithms of quarterly tourist arrivals to an AR-4 model, validating each lag with computed t-statistics. This model allowed us to craft time series for competing arms over a multitude of rounds.\n* Finally, we’d also like to highlight that the main purpose of our case study is to demonstrate the adaptability of AR2 to more complicated time series with real-world characteristics (AR-p processes with trend). This has indeed been shown in our case study.\n"}, {"review_id": "EuA93IWso2", "reviewer": "Reviewer_6t1b", "summary": "This work uses AR(1) model to model the non-stationary multi-armed bandit (MAB) problem. This paper considers a new performance metric, dynamic steady-state regret, and establishes lower bound on regret. Furthermore, This paper proposes the AR2 algorithm and provides a relatively tight regret upper bound.", "questions": "I hope the authors can provide an explanation for the issues I mentioned regarding the stationary AR(1) model, the bounded expected rewards, and Theorem 5.1.\n\nIf the response is reasonable, I will consider increasing the score.", "limitations": "As mentioned in the weakness.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Previous works on non-stationary multi-armed bandit (MAB) problems have often assumed bounded non-stationarity, as only bounded non-stationarity allows for achieving sublinear dynamic regret. This work, however considers the setting of unbounded non-stationarity. This provides a new perspective on handling non-stationarity and addresses the evaluation of algorithm performance in the context of linear regret. Additionally, this paper introduces the concept of steady state error to quantify the algorithm's performance under these conditions.", "weaknesses": "1. In this paper, the AR(1) model is defined with α∈(0,1), which actually qualifies it as a stationary model. α would need to be at least equal to 1 to be considered non-stationary. For example, in scenarios involving bounded non-stationarity, the expected reward's variation bound is typically represented by \\sum_{t=1}^T||r(t+1)-r(t)||_\\infty, which corresponds to the case of AR(1) with α=1. Therefore, using this stationary AR(1) model ( α∈(0,1) ) to characterize non-stationary multi-armed bandit (MAB) problems seems to be unreasonable.\n\n2. It seems unreasonable to assume that the expected reward has upper and lower bounds of [-R, R] in this setting. If we assume that the expected reward is bounded within [-R, R], even with random arm selection, the per-round dynamic regret should be at most 2R. This implies that any algorithm (e.g., algorithms without restarts) would eventually reach a steady state, which is unrealistic in a non-stationary environment. However, Theorem 5.1 in the paper does not seem to make this point clear: as α approaches 1, the per-round dynamic regret upper bound for random arm selection tends to infinity (which should be at most 2R when the expected reward is bounded by [-R,R]).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful feedback! We’d like to address each of your questions below. We will also integrate the following discussions and clarifications into our revised paper.\n\n**(1) Stationarity in time series vs. bandits.** \n\nWe appreciate your comments regarding the AR-1 model's stationarity and would like to clarify the terminology used in our paper. \n\n* In time series analysis, we agree that the definition of a stationary time series is a stochastic process with a constant unconditional joint probability distribution, which characterizes the AR-1 model with $\\alpha < 1$ as a stationary time series model.\n\n* However, within the bandit literature, the terms \"stationary\" and \"non-stationary\" are used differently. \"Stationary bandits\" refer to setups where the underlying distribution of each arm remains fixed, while \"non-stationary bandits\" encompass any scenario where the reward distribution of each arm changes over time. In our context, since the expected reward $r_i(t)$ varies over time following the AR process and since the best arm (i.e., the arm with the highest expected reward) changes over time, our problem aligns with the non-stationary bandit category. In fact, our work delves into a notably more volatile environment than most studies within the non-stationary bandit literature (e.g., [10, 52]). \n\n* We suspect the term “non-stationarity” might be causing some confusion due to its varied interpretations across different domains. We are open to renaming our setting to “dynamic bandits” if this helps alleviate potential misunderstandings and align terminologies with existing literature. We thank the reviewer for pointing this out and will make the necessary adjustments for better clarity in the paper.\n\n* We'd also like to remark on the total variation term:\n     - In our context, the total variation you mentioned can be computed as follows. Recall that our AR-process is defined as $r_i(t+1) = \\alpha r_i(t) + \\alpha \\epsilon_i(t)$. \nHence, the total variation is given by $\\sum_{t=1}^T \\Vert r(t+1) - r(t) \\Vert_\\infty = \\sum_{t=1}^T \\Vert (\\alpha-1) r(t) + \\alpha \\epsilon(t) \\Vert_\\infty,$ where $r(t) = (r_1(t), \\dots, r_k(t))$ and $\\epsilon(t) = (\\epsilon_1(t), \\dots, \\epsilon_k(t))$.    \n\n    - Note that the total variation here scales linearly with the number of rounds $T$. To see this, consider a simple example where $\\alpha = 1/2$, boundary $R = 1$, and for illustrative purposes, assume $\\epsilon_i(t)$ independently takes value from $\\pm 1$ with equal probability $1/2$. In this simplified scenario, for any $r(t) \\in [-1,1]^k$, the per-round variation at any given round (i.e., $||r(t+1) - r(t)||_\\infty$) would be at least $1/2$ with probability at least $1/2$. Therefore, the total variation is $O(T)$.      \n    - This suggests that our AR-based environment is more volatile than settings characterized by sublinear total variation, such as the one studied in [Besbes et al. 2014]. Our established lower bound also aligns with their lower bound result, which states that if the total variation is $O(T)$, our best achievable total regret would be $O(T)$ (see Line 184-187 of Section 3). Hence, studying per-round regret and presenting upper bounds based on AR parameters $\\alpha$ and $\\sigma$ would provide better insights into an algorithm’s performance in our rapidly changing environment.\n\n**(2) Per-round regret is bounded.**\n\n* Given the bound $R$ on our reward, we agree with the reviewer that a more accurate statement of Theorem 5.1 would be: **any algorithm** (including the naive algorithm) would incur per-round regret of at most $\\mathbf{O(\\min(\\sqrt{\\log (1/\\alpha \\sigma)+\\log k} \\cdot \\frac{\\alpha \\sigma}{\\sqrt{1-\\alpha^2}}, 2R))}$. We would update this in the revised paper to add clarity. \n\n* The main purpose of presenting Theorem 5.1 is to show that under the setting where $\\alpha$ is small (i.e., $\\alpha < \\bar{\\alpha}$), the upper bound attainable by any algorithm (even the naive algorithm) stays close to the lower bound (refer to Figure 1). As Figure 1 also shows, when $\\alpha \\rightarrow 1$, the upper/lower bounds deviate from each other, highlighting the need to design an algorithm for the case of large $\\alpha$ as we did in the paper (see Theorem 5.2).\n\n* We’d like to further add that the lower bound presented in Section 3 scales with the AR parameters $\\alpha$ and $\\sigma$. If the constant $R$ is large enough, our lower bound would be quite far away from the bound of $2R$. Hence, assuming $R$ is large enough, our goal is to devise an algorithm whose per-round regret upper bound can be characterized in terms of the AR parameters ($\\alpha, \\sigma$), and ensure that its upper bound stays close to our lower bound.\n\n* In our setting, in the absence of such boundedness, the variance of expected rewards under the stationary distribution would go to infinity as $\\alpha$ goes to 1, and it then becomes impossible to design any useful algorithm for such a volatile environment. Further, note that the boundedness of rewards is a common assumption in the MAB literature (e.g., Lai & Robbins 1985, Auer et al. 2002, Besbes et al. 2014), and hold in most real-world applications such as demand forecasting and ad CTR prediction. \n"}, {"review_id": "Qz4T9Z5CjP", "reviewer": "Reviewer_s53A", "summary": "The authors propose a bandit algorithm in the restless setting, when the rewards have an auto-regressive structure.", "questions": "1. Some discussion of Exp3's limitation is already discussed in the lower bound section. Would be great to see a discussion on on adversarial bandits and how much tighter your results are compared to some of the algorithms there. \n2. Unclear why the dynamic benchmark was chosen instead of the static one (other than it does seem suitable and is harder?). If instead we use the static benchmark, would there be any regret UB/LB gains?", "limitations": "None identified.", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. Contributes to the non-stationary case, in contrast to the vast majority of results in the stationary setting.\n", "weaknesses": "1. Knowledge of (single parameter) alpha, and the problem of estimating it simultaneously. It is unclear of the theoretical claims (in addition to the numerical results) hold when these are relaxed (ref. Sec 2)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insightful feedback! We’ve addressed your questions below and will integrate the discussions into our revised paper.\n\n**Regarding learning the AR parameter,**\n* In Sec. 8, we introduced a MLE-based approach that learns the AR parameter. We provided theoretical guarantees for our estimation (Prop. 8.1), and also numerically showed that the performance of our algorithm remains robust and competitive even when there exists noises in estimated AR parameters (Fig. 2).\n\n    Specifically, our numerical results reveal that AR2 is robust to the lack of knowledge of $\\alpha$. For instance, in experiments we conducted for Fig. 2, performing MLE with only 50-150 data points and using the estimated AR parameter in AR2 would only increase normalized per-round regret by at most 4% compared to using the true AR parameter.\n\n    Given the promising numerical results, we believe that our MLE-based approach, which also handles heterogeneous $\\alpha_i$’s (as noted in Sec.8), can be a useful method for practitioners to estimate the AR parameters in reality. \n\n* Many decision-makers in practice also have some prior knowledge of the AR parameters given past data (see discussion in Sec. 2 and our case study in Sec. 7). This motivates our initial assumption of known AR parameters. Even if such prior knowledge isn’t fully accurate, using them as initial estimates can significantly ease our learning process. \n\n* The main focus of our paper is to study how to use knowledge of the temporal structure to enhance online decision-making. With this in mind, we first focused on the AR-based bandit problem assuming knowledge of $\\alpha$, and addressed learning of the AR parameters as a subsequent problem. Even with ample information on the underlying AR process, our non-stationary MAB problem remains challenging. \n\n    We appreciate your comment on the simultaneous learning of AR parameters. Given the focus of this paper, we will leave its theoretical analysis as an exciting future direction, and will add it to our future works section.\n\n**Regarding comparison with Exp3,**\n* We first highlight that Exp3 is designed for a completely adversarial setting where rewards can change arbitrarily. It is shown to be optimal against a weak static benchmark, which only considers a single best arm in hindsight, rather than a dynamic benchmark that chooses the best arm at every round. Further, it does not consider any temporal structure associated with the reward distributions. Hence in our setting where we intend to capture the best moving target, Exp3 doesn’t seem to be the most appropriate choice.\n\n* In our numerical studies (Appendix A), we’ve already compared our algorithm with a variation of Exp3—the RExp3 algorithm from [Besbes et al. 2014]. RExp3 uses Exp3 as a subroutine, restarting at the start of each epoch. Similar to AR2, their restarting mechanism balances the \"remembering\" and \"forgetting\" tradeoff, improving Exp3's performance in non-stationary bandits with dynamic benchmarks.\n\n    Yet, there are key differences between RExp3 and our approach: (i) RExp3 assumes sublinear total variation in expected rewards, while our AR setup involves $O(T)$ total variation, and (ii) RExp3 does not use any knowledge of the temporal structure. Theoretical results for RExp3 merely suggest that its total regret would be $O(T)$ in our setup, but do not offer any per-round regret guarantees in terms of AR parameters $\\alpha$ and $\\sigma$. Our simulations (Table 2, Appendix A) also show that RExp3 does not perform well in the AR setup, as it's tailored for environments with limited changes (see Appendix A for more discussion).\n\n* For completeness, we have additionally evaluated the performance of Exp3 and compared it with AR2 and RExp3. Please refer to _Table 3 in the PDF of the global response_. From the table, we see that Exp3's performance is very close to (sometimes slightly worse than) RExp3, which is expected considering their similarities. Nonetheless, AR2 performs much better than EXP3/Rexp3 in all types of environments, as AR2 leverages knowledge of the AR temporal structure to swiftly adapt to changes.\n\n* Please also refer to Table 2 in Appendix A to see the comparison of AR2 with other algorithms that adopt the static benchmark (e.g., UCB, $\\epsilon$-greedy, etc.). There, AR2 also displays superior performance.\n\n**Regarding our choice of the dynamic benchmark,**\n\n* Following our discussion on Exp3, if we were to adopt a static benchmark in an adversarial setting, the Exp3 algorithm could already yield a $O(\\sqrt{T})$ static regret. Yet, as illustrated by our numerical results (Table 2 in Appendix A and _Table 3 in the PDF of global response_), algorithms tailored for static benchmarks, such as UCB and Exp3, do not adapt well to the rapid changes inherent to our setting.\n\n* While we recognize that the dynamic benchmark presents a tougher challenge than the static benchmark and does not permit sublinear regret, it allows us to aim high and track the best moving target. This is especially important in a fast-changing environment that we studied, as no single arm can consistently dominate. Algorithms designed for static benchmarks tend to fall behind, as seen in our numerical studies. Essentially, the dynamic benchmark highlights the value of leveraging temporal structure in online decision-making, which is our main goal, and also where our algorithm excels.\n\n* The real-world applications discussed in Sec. 1 also underscore the importance of adopting a dynamic benchmark. In practice, the decision-maker usually wishes to be agile and swiftly react to changes in the environment. For example, in online product recommendations, as product demand shifts, it's vital to quickly adjust to show in-demand items. Relying on a single historically \"best\" product can’t be optimal in such dynamic scenarios. The same rationale applies to predicting ad CTR, where ad platforms must pivot quickly in response to fluctuating CTRs."}]

Author rebuttal:
We would like to express our sincere gratitude to all reviewers for your valuable and insightful feedback! We have carefully addressed each reviewer’s comments and questions below. For Figures 5, 6 and Table 3 crafted during the rebuttal period, please kindly refer to the attached PDF in this global response. We will incorporate all clarifications and discussions in our response into the revised version of the paper.

Our work is, to our knowledge, the first that studies non-stationary bandits with reward distributions governed by time series that encapsulates real-world characteristics, specifically the AR process. Our aim is to identify the major challenges inherent to such rapidly changing environments commonly observed in practice, and propose effective mechanisms for addressing them. We hope that the high-level ideas shown in this paper would provide insights for any future research that explores bandits with other types of temporal structures.

Once again, thank you for your time and thoughtful contributions to improving our work!


Meta-review: The reviewers and myself have come to an agreement that the paper should be accept due to the quality of the contributions as well as the clarity and topic of the paper. 

We recommend the authors to add the discussions on the choice of regret metric and the additional results to the final draft as we believed they add value to the work.
Decision: Accept (poster)