Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits
Authors: Yunlong Hou
Vincent Y. F. Tan
Zixin Zhong
Venue: NeurIPS 2024 poster (2024)
Keywords: Multi-armed bandits
piecewise stationary bandits
best arm identification
fixed-confidence
Primary area: bandits
TL;DR: We propose a minimax-optimal algorithm PS$\varepsilon$BAI$^+$ to identify an $\varepsilon$-best arm in the piecewise-stationary linear bandits problem.

Abstract: We propose a novel piecewise stationary linear bandit (PSLB) model, where the environment randomly samples a context from an unknown probability distribution at each changepoint, and the quality of an arm is measured by its return averaged over all contexts. The contexts and their distribution, as well as the changepoints are unknown to the agent.
We design Piecewise-Stationary $\varepsilon$-Best Arm Identification$^+$ (PS$\varepsilon$BAI$^+$), an algorithm that is guaranteed to identify an $\varepsilon$-optimal arm with probability $\ge 1-\delta$ and with a minimal number of samples.
PS$\varepsilon$BAI$^+$ consists of two subroutines, PS$\varepsilon$BAI and Naïve $\varepsilon$-BAI (N$\varepsilon$BAI), which are executed in parallel. PS$\varepsilon$BAI actively detects changepoints and aligns contexts to facilitate the arm identification process.
When  PS$\varepsilon$BAI and N$\varepsilon$BAI are utilized judiciously in parallel,  PS$\varepsilon$BAI$^+$ is shown to have a finite expected sample complexity. 
By proving a  lower bound, we show the expected sample complexity of PS$\varepsilon$BAI$^+$ is optimal up to a logarithmic factor.
We compare PS$\varepsilon$BAI$^+$ to baseline algorithms using numerical experiments which demonstrate its   efficiency.
Both our analytical and numerical results corroborate that the efficacy   of PS$\varepsilon$BAI$^+$ is due to   the delicate change detection and context alignment procedures embedded in PS$\varepsilon$BAI.

Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits
Yunlong Hou Department of Mathematics National University of Singapore yhoušu. wws.
Vincent Y. F. Tan
Department of Mathematics Department of Electrical and Computer Engineering National University of Singapore vtan@nus edu. sg
Zixin Zhong
Data Science and Analytics Thrust
Hong Kong University Science and Technology (Guangzhou)
zixinzhongehkust- edu.
Abstract
We propose a novel piecewise stationary lincar bandit (PSLB) model, where the environment randomly samples a context from an unknown probability distribution at each changepoint, and the quality of arm measured by its return averaged over all contexts. The contexts and their distribution, as well as the changepoints are unknown to the agent. We design Piecewise-Stationn (PS=BAI*), an algorithm that is guaranteed to identify an e-optimal arm with probability
E-Best Arm Identification
å and with a minimal number of samples. PSaBAI+ consists of two subroutines, BSEBAI and NAIVE e- e-BAI (N&BAI), which are executed in parallel. BSaBAI actively detects changepoints and aligns contexts to facilitate the arm identification process. When BSB and N=BAI are utilized judiciously in parallel, PS=BAI* shown to have a finite expected sample complexity. By proving lower bound, show the expected sample complexity of PS=BAI+ is optimal up to a logarithmic factor. We compare PS=BAI+ to baseline algorithms using numerical experiments which demonstrate its efficiency. Both analytical and numerical results corroborate that the efficacy PS=BAI* is due to the delicate change detection and context alignment procedures embedded in PS=BAI.
Introduction
In stochastic multi-armed bandits (MABs), agent interacts with the environment at each time step. The agent pulls an arm and observes the corresponding return provided by the environment. The classical MAB framework assumes stationary environment where the expected return of cach arm remains unchanged over time. However, we usually face ever-changing environments real life. For instance, in investment option selection and portfolio management, fund managers want to select subset of good candidate portfolios. However, the market may be bullish, bearish, or in some other state. The transition between these states can be well-modelled as being stochastic. We wish to select portfolios that yield the best long-term option under such a piecewise stationary environment. Further examples such are discussed in detail Appendix A These motivate us to formulate and investigate a piecewise stationary linear bandit (PSLB) model.
based agriculture in the face of stochastically changing weather patterns
Our PSLB model is equipped with an arm set X, a context set and a deterministic but unknown sequence of changepoints C, At each changepoint, the environment samples a context 0 E θ from an
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

unknown probability distribution Pg. and the returns of arms may change when the context changes. The return of each arm under each context is determined by its feature x E X and the context 9. In particular, the expected return of an arm is the weighted sum Ms = r, [a: 0.. While the sequence of changepoints, as well as the distribution and latent vectors of contexts are not known, the agent samples an arm and observes the corresponding return at each time step so that it can identify the best arm arg max, Ue up to some tolerance with probability 2 1 - and with as few samples as possible. The agent's 's behavior does not affect the sequence of contexts that is drawn from Po.
Main Contributions. We are the first to study the fxxe-confidence best arm identification (BAI) problem in piecewise stationary bandits (PSB). Given 5 > 0, we say the arm with the highest expected return μr¹ is the best, and an arm is e-optimal if its expected return is least μ E. We seek to design an (z, 5)-PAC algorithm which can identify an e-optimal arm with probability 2 1 - 8 in as few time steps as possible, i.e., with minimal sample complexity.
Our first contribution concerns the formulation of novel PSLB model, where we measure the quality of an arm according to its expected return p Pg Pa [xr T O] for the following reasons. Consider that an arm is measured by its average return across time, which is a generalization of the definition in stationary bandits (SB). A notable feature of PSB models that the context changes as time evolves, and hence the arm's 's average return across time also changes, in general. Hence, we aim to identify an arm whose average return across contexts high, and benefits the agent for interacting with the environment in the long run after the arm identification task. We are thus inspired to introduce the distribution of contexts under the PSLB model, define the expected return Pa for each arm. and use this ensemble (non-time varying) statistic as the benchmark for what we seek to learn. The BAI task using this statistic meaningful but challenging, as the agent needs to reliably estimate the context vectors, changepoints, and context distribution.
s-BAI+ (PS=BAI+), an algorithm designed to tackle the BAI problem in our PSLB model. We prove that it is 0)-AC and bound its sample complexity. PS=BAI+ samples arms according suitably defined G-optimal allocation, and runs two algorithms: NAÎVE E- BAI (N=BAI) and BSB as subroutines in parallel to achieve efficiency and attain a bound on the sample complexity in expectation.
Secondly, we propose
Being a baseline but naive algorithm, the complexity of NeBAI grows linearly with the maximum length between two changepoints Lmax. motivating us to design a more efficient algorithm, PS=BAI, to reduce the impact of Lmaxx-
PS=BAI is equipped with two delicately designed subroutines LINEAR- DETECTION (LCD) and LLNEAR-CONTER contexts with those observed in the previous time steps respectively. Concretely, in terms of the design, PS:BAI determines whether samples from two intervals are under the identical context via sliding window mechanism, and detects changepoints and aligns contexts accordingly; this facilitates the estimation of context vectors and their distribution. Combining these elements into the design of BS=BAI and analyzing them requires some care. On the theoretical side, we prove PS= AI identifies an s-optimal arm faster than BBBAI with high probability. The success of PS=BAI relies on the LCD and LCA subroutines, while minor drawback is that they require a non-vanishing failure probability budget which does not allow us to bound the sample complexity of PS& BA in expectation. To achieve a complete theoretical understanding, we delicately design the PS=BAI+ algorithm whose efficiency is inherited via the LCD and LCA procedures in PS=BAI as well as the effective utilization of running PS:BAI and NeBAI in parallel.
ALIGNMENT (LCA) actively detect changepoints and align
Thirdly, we derive lower bound on the complexity of any (s, 8PCAC algorithm in PSLB models. To derive this bound, we first lower bound the complexity of an algorithm when the contextual information (and changepoints) are available, and then quantify the number of arm samples (and realized contexts) required to reliably infer an E-best arm. We compare the upper bound of BSI and this generic lower bound in several instances. The matching (up to logarithmic terms) of bounds illustrate that our BAI algorithm is almost asymptotically optimal.
Lastly, we demonstrate the efficiency of PS& with numerical experiments. The first half of our experiment shows that PS=BAI+ is (e, 8PC and with significantly lower sample complexity compared to BAI corroborating our theoretical findings. In the second half, we compare PSB to BAI and two other benchmarks DISTRIBUTION e-BAI (D=BAI) and D=BAIg. While contexts and changepoints are not available to PS=BAI* + and NeBAI, they are observed by D=BAI and DeBAIg. Nevertheless, PS=BAI+ is still competitive compared to DEBAI and D=BAIg in our
2

---

empirical experiments. Hence. both experiments justify the necessity of the change detection and context aligmment procedures for boosting the learning of contexts and their distributions, as well as the identification of the best arm. We also show empirically that misspecifications to the knowledge of T.min and mmx do not affect the performance of our algorithm significantly.
Related work. Best arm identification (BAI) and regret minimization (RM) are two fundamental problems in multi-armed bandits. In stationary linear bandits, [ focus on BAI and 3 aim to solve the RM problem. An efficient algorithm can choose the G-optimal allocation or X')-allocation
rule to quickly identify a good arm 5 Besides, 6 7
focus on e-optimal arm identification, which
is a generalization of the standard BAI problem.
The BAI and RM problems are also studied in thr non-stationary bandits (NSB), where in contrast to the SB model, the context varies with time 8 6-10. NSB can be largely divided into two classes: the drifting bandit (DB) model, where the context changes at each step [8]. and PSB, where the context changes less frequently 10]
11 provides an extensive discussion on the definition of NSB models.
On the other hand, concerning the BAI task in DB models, [14 investigated BAI with a fixed-horizon, where the best arm has the highest average return over this horizon; [15] assumes the best arm remains setting. Besides, when the
On one hand, the RM problem have been investigated extensively in DB models 02 13
unchanged after certain time step and explores the contextual information in NSB models is available, NSB models are known contextual bandit (CB) models [6)18]. . [66] showed that the contextual information accelerates the best arm identification process. More discussions on DB and CB models are presented in Appendix C
Moreover, the context can drift dramatically in a DB model while remains unvarying a SB model. Straddling between the DB and SB models, PSB models assume there is an interim stationary interval between each two consecutive changepoints, where the context remains unchanged. The context changes can be characterized in different ways and affect the performance of proposed algorithms in PSB models. For instance, a changepoint signals the return of at least one arm shift as in 100, and indicates the best arm changes as in [19.
In PSB models, a large body of works focus on RM. While 10 20
22
equip their algorithms with
changepoint detection techniques to handle the context changes, 2 actively checks the quality of each arm. However, there is no existing work on the fixed-confidence BAT problem in a PSB model. To fill this gap in the literature, we design PSEBAI+ for s-optimal arm identification in our proposed PSLB model. We show PSEBAI+ is almost asymptotically optimal by comparing its complexity to a generic lower bound of all algorithms, and validate its efficiency through numerical experiments.
2 Problem Setup
For m E N, let [m] := (1,2..... m}. For finite set S, let As denote the |S]-dim probability simplex on S. Let A(q) := ExEx QxE be the matrix induced by E Ax with X' C Rd. An instance of piecewise stationary linear bandit is tuple A = (X, 9, Po. C). Specifically, x E Rd is an arm (vector) and the arm set X C IRd is composed of | = K arms that spans Rd. The latent vector matrix θ = (oi...., , 0x) E RdxN contains N latent column vectors where the jth column 07 associated with context j E [N]. For the sake of normalization, we assume |x: T 001 S for all x E X,j j. E [N]. Let Pa denote the distribution (probability mass function) of the latent vectors and pj- = Pe ].]0 We represent the probabilities of latent vectors as p (P PN) AN. The fixed but unknown sequence of changepoints C := C2..... is an sequence of increasing positive integers 1 = c1 < C2 < ..., characterizing all the changepoints (time steps).
The return of arm æ under latent context is a random variable Y = x ==0; + n7 where n is a zero-mean random variable (noise) supported on 1), and the expected return of arm x is Nr Ea-r, (xr 0 Σ,= Po(07]0 0j. The best arm, which we assume is unique, is denoted as x arg max P with mean μ* plz Given slackness parameter >> 0, we define the set of e-best arms X == (ar EX : Ma 2 Jr - e). For each pair of arms (x, E X define the
contextual mean gap between and ă under latent context j as (y Z) == (x i) 03 and the
mean gap between x and i as A(x, = P P2.
Given E N, the interval (ct, C41 - 1) known as the 1th stationary segment and its length is L1 = C+1 Qt We assume Lmin < L S Lmax. Let I == maxil: q t) denote the number of
3

---

stationary segments up to time step t. At time step t E [T'] (see Dynamics 1
(i) If E C, the environment samples a latent vector 0% according to Po. that is, generates a
(latent) context sample with Po: otherwise the latent vector remains unchanged. i.c. 07. = 0 The
contexts (0), HEN are sampled i.i.d. from Po at each changepoint {aieeen
(ii) The agent pulls an arm 3y and observes the stochastic return Ye.z, = xy 0z + 7/t, where 7/t is drawn independently from a distribution supported on [-1,
The agent uses an online algorithm π := {(Te, Tt, Tz) heN to actively interact with the instance A and only has access to the arm set X, number of latent vectors N, the bounds on the length of each segment Lmin and maxx the slackness parameter E, and the confidence parameter 8.
sampling rule T Hi = ((x7, Ya,r7) )) sE[t-1] + X' samples an arm x based on the observation history H.T and observe the corresponding random return Y
stopping rule Ti H {STOP, CONTINUE) decides whether to stop or continue to execute given the observation history H The stopping time under algorithm π is denoted as -"; recommendation rule r, H X' recommends an arm 1 based on HG++ upon termination.
The stopping time -" the sample complexity of the algorithm æ under instance The expected sample complexity is [E[r"]. where the expectation is taken w.r.t. the random returns, the realization of the contexts governed by the latent vector distribution Pg. and the randomness of the algorithm т.
An algorithm и is (s, 6PAA (Probably Approximately-Come
if
P[s" E Xx) 2 1 5.
Our overarching goal in this paper is to devise an (e. 6)-PAC algorithm that minimizes 7" with high probability (w.h.p.) and in expectation.
3 Algorithms
3.1 A Naïve Baseline: NeBAI
We first devise the NAIVE 6- BEST ARM IDENTIFICATION (or NeBAI) algorithm (presented in Algorithm p In the design of NeBAI, only the choice of confidence radius ýe takes the potential context changes into consideration. Even though B&BAI does not attempt to detect potential changes in the context, it can identify an s-optimal arm w.h.p. and is with finite expected sample complexity.
Proposition 3.1. Let Amin min x
Axx x).
d
1
Liax In 1
In 5
and T
(e + Amin)
(e +
Amin) 8"
The NeBAI algorithm is (E, and its expected sample complexity is Ö + D
The upper bound in Proposition 3.1 (also see Appendix F) consists of two main terms. (i) As BABAI samples arms according to the G-optimal allocation (see Appendix D). the amount of samples needed to estimate the average of latent vectors Σ'= 02 contributes T. (ii) TN quantifies how fast. E'= /t converges to the expectation of context vectors Σ P}=1,,
The sample complexity of N=BAI grows linearly with LInaxs but we surmise that the sample complexity of a close-to-optimal algorithm should have reduced dependence Lmax-
3.2 Piecewise-Stationaayy B-Best Arm Identification
The algorithm
STATIONARY E- BEST ARM IDENTIHCATION (or PS=BAI) is presented in Algorithm [ By using a sliding window mechanism, PS:BAI actively detects the change- points and aligns the current latent context with contexts observed in the previous time steps via LINEAR CHANGEE DETECTION (or LCD) and LINEAR -OOEEETT ALIGNMENT (or LCA),, which presented in Algorithms 3 [ App. D.2.2. respectively. PS=BAI consists of three phases:
(i) Exploration phase (Exp): Estimate latent vectors and their distribution Po (Lines 8 to T1 and 25
(ii Change Detection phase (CD): Detect changepoints (Lines 12 I6]:
(iii) Context Alignment phase (CA): Evaluate the current context and align with the contexts
observed in previous time steps (Lines 17 to 21

---

and P. (fc.1...., Pr.NN' respectively We denote the empirical mean gap between æ and i under context j as (z, 8) = (x B) TT. 6..j
At time t, we estimate è and with θ, = -...1...., (r.v)
PS:BAI first computes the G-optimal allocation [1 X on the arm set and its maximum possible stopping time r" (Line 2). It initializes CD sample and CAia- CDamplle collects samples to detect changepoints and CAda maintains a dictionary of {latent context index identification samples) pairs (Line 3 CAaa [j] is the sequenee of CD samples used to identify latent context j. It also initializes Te.j. the collection of time indices in [t] in the Exp phases under estimated context j. Define
T== = U Ttj. JEIN]
T. = TTa
Trj = |Tasl
Vj E
(3.1)
Algorithm PIRCEWISE-STATIONNER g E-BEST ARM IDENTIFICATION (PS=BAI)
1: Input: arm set N. size of the set of latent
14:
Update Je Ji-1, Tai T(-1. for all
vectors N, bounds on the segment lengths
j E [N].
Luuin and Tmmax, slackness parameter fidence parameter 5, sampling parameter y 16: and window size w, threshold b.
15:
if |CD sample! 2 then
if LCD(X, w, b, CDsamplel- (- then
2: Initialize: Compute the G-optimal allocation
17:
CD CDaample = []. [ 1+ 2, LCA 1, lCD +00. jt, CA = (,C w, b, CAaa).
X and T" 38/100 In (80)N Liuux In N Kumss
18:
62
3: Set CD Casmmlee
[ CAia = }. Set
19:
ICD +CC.
4: Set Tr,
and initialize Tr, Te.j Ty
20:
if j: = N + then break.
with 3..1 for all ST j [N].
21:
Revert Tr.i T w(x jj for all
5: Sample @ arms {-,)== ~ X and ob-
j [N].
22:
end if
serve the associated returns ( ". Lc4 = 2'
23:
end if
24:
end
6: CA = {1 (x., Y. a. 1
1. =
25:
Update the estimates using 33.1
3.2
7:
while < do
and (333
8:
t= ++1
26:
if Condition 3.4 is met and tcD +00
9:
Sample an arm 24 x and observe return Yt...
then
27:
Record f.- arg m T..p.
10:
if mod (t - ICA, 7) * then
28: tcD = CD samplel
11:
Update 3. = jt-1. Te.j = T--1j.
29: else if tcD CCD sample! then
(1), Tr.j T for Jt.
30: Recommend arm &e.
31: break
12:
else
CD sample CD sample + [2 V Ne,.))
32:
end
33:
end while
then collects " samples and stores them in CAia, which is then used to identify the first latent 5 context (Lines (Lines55too [).
In the Exp phase, PS:BAI firstly samples an arm I, with X and observes the return Yr,,, at 07 + (Line 9.. It then updates the estimated context index and time collectors (Line 11 It also updates the estimates of value and probability of each context j (Line 25) with
Σ O0.5 TEd sET
1
and
Tej Pr.j
(3.2)
T.
'The empirical latent vector-probabilityy pairs f can only approximate the unknown pairs ((0t))) ((CG)))P())) > up permutation [N] [N]. which determined the occurrence order of latent vectors. Thus assume the latent vectors appear order of increasing indices. 'A sample in CD is a CD sample: A dictionary has a pairing structure [key:value] and dictionary(key) = value. [a:]a= denotes sequence of elements a)...., On.
5

---

where 0.g- = 0 T.. O. We define as, Et, St.j. and An (a,,)) in Appendix D.2.1 For each pairs of arms (z) R). the confidence radius of Axx, T) at time step t is
N
(c(z, 2(ar + Et) +
Σ 5=1
Bes
A (z, σ) (o(x,
(3.3)
BSB actively enters the CD phase every time steps (Line 12 It firstly adds a CD sample
to CDaample (Line 13 Next, if there are sufficient CD samples (Line 15 the LCD subroutine (presented in Algorihh B) is called and utilizes the most recent CD samples to check whether changepoint just occurred (Line PS=BAr steps into the CA phase if a changepoint is detected, and skips the CA phase otherwise, which is illustrated by Figures T(b) ((a) respectively.
Context
Context
Changy Detustion Phases
Exploration Plaaes
Chanpe Detection Plases
Explontion Phanes
Active CD samples Insctive CD samples
Active samples
Contest Alignment Photes
No change alarm raised
Inactive CD sumples
Step stopping rules Step 3: Statt new Eap phase
Step Revert the statistics
6
Step aligns context
7 1- samples Esq plans
ur activve CD samples
Step 4: Start as new Ext phase
Step LCD raises diange alarm
Time stop
Time step
(a)
(b)
Figure 1: (a) No change alarm is raised during a stationary segment. The active CD samples are the input to the I.CD subroutine at current time step I. (b) A changepoint detected by LCD, followed by a CA phase and statistics reversion step.
In the CA phase, PSeBAI starts by resetting CDaample (Line 17), updating the count of time steps and recording the ending time of this CA phase (Line Thereafter, the CA subroutine (presented in Algorithm 4) is invoked, which estimates the current latent context index je and updates CAaa (Line 19p. If = N + 1, i..., PS=BAI identifies N + 1 latent contexts, which is incorrect under instance A, it terminates and fails to identify an g-optimal arm (Line 20). Lastly, all empirical statistics are reverted to those from (w(7 + 1)/2) time steps ago, i.e., the most recent (wr/2) samples in the Exp phases are abandoned (Line 2T).
The stopping rule is described in Lines 26 to 32
(I) If the following condition is satisfied (Line 26):
2L
2 J..T.
min 2
Âc(xi, x) - Pe x) 2 -E and Ti 2 9
In
(3.4)
where the empirical mean gap (x x²) == (aj - x)) T.pp, and ot = arg max,x.. x' O.pt. PS records the arm with the highest empirical mean &. and the number of CD samples tcD (Lines 27 and 28) but does not terminate immediately. Besides, mild forced arm pull procedure is in the second line of (3.4). which is inspired by Lemma 1 and to ensure the performance of BAI. (II) BAI will execute for another (w>/2) time steps in which w/2 CD samples are collected; if no changepoint is detected with these w/2 CD samples, the recorded arm á is recommended and BSIBAI terminates (Lines 29 to p0). Part (II) of the stopping rule assures BSBBAI does not terminate when changepoint has occurred but has not been detected, PS:BAI may fail to identify an e-optimal arm otherwise.
We remark that even though PS:BAI uses the knowledge of Luax, our experiments show that the performance of PS:BAI robust to small misspecifications Lmax (see Appendix 0.2) Furthermore, the computational complexity of PS=BAll is computed in detail in Appendix D.4 The derived computational complexity indicates the proposed algorithm depends in natural manner on the problem parameters such as d, K, N, and Lastly, thanks to the LCD and LCA subroutines, slightly modified variant of PSBBAl can also solve the "s-Best Arm Tuple identification problem", which aims to identify z- b-bt arm under each context; Appendix Q for details.

---

3.2.1 Theoretical guarantee of PSEBAI
To facilitate the analysis of PS=BAI, we propose the following assumptions. Note that our PS:BAI algorithm may still succeed to identify an e-optimal arm w.h.p. when the assumptions do not hold.
Assumption 1 (Distinuiishabiliy Condition). The agent can choose w, 7 and such that (1) S A is the minimum gap between two contexts; and (2)
where De == mins; #0; max |xc [0} - 01)1
3wy Timin A possible choice is
8d b
+V VV( 8d
2 )
24d
2 ÓPAB
76
where ÓFAE
(3.5)
3w
ŌFAB
3w
ÓPAB
4(T*)2
This assumption guarantees (i) PS=BAI will not abandon all samples during the reversion procedure (Line of Algorithm D) (ii) each two latent vectors can be distinguished if the window size w is sufficiently large (e.g., m 6). We clarify that this assumption is only for the rigor of theoretical guarantees and it holds provided that each stationary segment is sufficiently long; this is feature of
PSB models and similar assumptions are also present existing works for their analyses 21 10 22
We demonstrate the robustness of PSeBAl to these parameters using experiments in Section 6
Theorem 3.2. Define the context distribution estimation (DE) hardness parameter
L Liax
HDE(FE, = (A(x), x) + E)²
H (TE,
where H Hz 2) ==
Σ
j=1 V min {16p,, |/4 (Z + =l)². Under Assumption
1 with proba-
bility at least PS:BAl identifies an s-optimal arm and its sample complexity is
d
NLmax Axr ()),,)++ +
max 2e E.E x
(A(** + + (aE( x)
In
(3.6)
(v
TD(#e.m)
TR(#)
The upper bound comprises three terms which serve distinct purposes:
(i) Latent vector estimation (VE): Ô (Tv(z)) quantifies the bulk of samples needed to obtain good estimate of latent context vectors such that the returns of Øe and x can be distinguished, where Ia is an e-best arm and & X is suboptimal arm. Tv(x) recovers the sample complexity in the stationary linear bandits in [. indicating that BS=BAI estimates latent vectors efficiently.
(ii) Context distribution estimation (DE): Ô (TD( characterizes the bulk of samples needed to learn the distribution of latent context vectors.
(iii) Residual estimation (RE): Ô (TR (x)) counts the remaining samples needed for VE and DE, in addition to Ô (Tv + TD).
Besides, the max operator is applied to exclude all suboptimal arms. We also see that Ty(x) and TD(x,, are similar to TV and Tø in Proposition respectively.
Firstly, the bound in (36p implies that, in an instance with smaller relaxed mean gap A(x* .z) PS=BAI terminates after larger number of time steps; in other words, it is more difficult to identify an e-optimal arm. In difficult instances with small A(x", xx) tE, the different orders of this term in (x),,, To (x and (I)) indicate that, TR (R(x)) is small compared to Tv (zx and (T),,.))
Secondly, DE solely utilizes context samples generated with Pa and they generated only changepoints in C, while all the observations in Exp phases facilitate VE. From this perspective, there are less samples that can be used for DE than for VE as PS=BAl processes, and hence Tp (x æ) is supposed be with larger order than Tv (z).
Moreover, for the purpose of DE, PS:BAI needs to observe context samples at δ M(( (A(=" In 1) Ō Hpg(z...) In }t) changepoints where Lmax is the maximum length of Lemax
stationary segment, leading to Tp(x2. x). Close examination of the definition of H (xe, 2) reveals that both the vectors and their probabilities influence the number of samples needed for DE. The comparison between TD( .)) and T in Proposition cleeryy indicates that PSe mitigates the influence of T-max by detecting changepoints and aligning the detected context with observed
ones, while NeBAI does not do so.
7

---

3.3 PSEBAI* + = PS=BAI U NEBAI
The design of PSEBAI (Line of Algorithm I indicates that PS:BAI will not recommend any arm if it does not terminate time 7", This result is nontrivial, as the high-probability result Theorem 3.2 depends on the success of change detection (Algorithm 3 and context alignment (Algorithm
We have provided a probabbroy result for PS:BAI in Theorem 3.2
which requires non-vanishing failure probability (e.g., 6/2). Thus, we cannot derive an upper bound on the expected sample complexity of PSABAI. We devise a solution by designing the
g-Best
Arm Identification* (PS&BAI+) algorithm with a simple but effective trick.
The PS=BAI+
algorithm samples one arm with the G-optimal allocation X at each time step, with which Algorithms I and L are executed in parallel (detailed in Algorithm This is feasible since PSEBAI and NeBAI algorithms have the same sampling rule.
Theorem 3.3. The PS=BAI+ algorithm (e, 6PPAC and its expected sample complexity is
o( min
((min
TV (v(x) + TD( + TR(x)), T + T
max
PS:BAI inherits the superiority of PS:BAI adapt the piecewise stationary environment, and employs the stopping rule of BeBAI to maintain finite expected sample complexity. As result, the expected complexity of PSBBAI+ in Theorem 3.3 is of the same order as the high-probability one of PScBAl in Theorem 3.2 and is not larger than the complexity of NeBAI in Proposition [.1 We show how our results particularize to the stationary linear bandits BAI problem, as well as additional discussions on the upper bound, in Appendix P
4 Lower Bound on the Sample Complexity
Given A (X, θ, Po, C), define the alternative instance A' -2 ('' Por,C) w.r.t. A, where O' (0,,..., , 0,) E Rdx. Po [0]] = Po [o]]] and there exists x E X' \ Xe. such that x Egr- 10'] < Egr [0' for all He E Xz. Let (A) be set of all alternative instances (w.rt. A). Theorem 4.1. For all (s, 8PC algorithm n, there exists an instance A (X' θ Po. C) such that
1
E [ 2 max
Te(A) In
CNe {
2.48*
where
(x (NT (07-0,))²
(0)
(A()) max
min
Σ Pjuj,
and
(u,) A' (A)
2
(rr"
No == max zf2"
In
(A(x*xx)+ +)²
46"
Recall that CNe is the Ne-th changepoint in the changepoint sequence C, which lower bounded by Ne Eiin and is No Lmnax in the worst case. To derive the lower bound in Theorem 4.1 we investigate two environments different from the one defined in Section 2 (and as in Dynamics
the agent observes the index of current context je (i.c., contextual linear bandits); Dynamics the agent observes the changepoints in and context vector 07, 's, and hence she solely needs to estimate the distribution of contexts.
Dynamics 2
We bound the sample complexity of an (s, 5)-BAI algorithm in Dynamics 2 and 3 respectively, which when combined, yield the lower bound Theorem 4.1 this is detailed Appendix M
Note that T, (A) -1 in the lower bound generalizes [16 to the setting of linear bandits. In addition,
Theorem 4. can be reduced bound in stationary linear bandits with one latent vector 24 (see
the discussion leading to (5)).).
On the Asymptotic Optimality of PSEBAI+
To illustrate the efficiency of our PS=BAI+ algorithm, we compare the upper bound on its expected and the generic lower bound in Theorem under specific
sample complexity in Theorem 3.3
instances below and in Appendix N We also gain further insight into our PS=BAI algorithm.
8

---

16/3
1000
DEDAI
DeBAI
NOHAI
Namber of Content Sumpkee
-00-111
R00
Sample complesity
800
NrBAJ
500
400
900
10
100
10
11
Instance
Siquared relassed
(a) Sample complexity of PS=BAI* vs. NeBAL
(b) Number of context samples needed for BAL
Figure 2: Experimental results
Example 1. Instance A = (x, is with (i) 2d - arms: 2(1) = e1, = ei, ((d+i-1)
C1 cos + e, sin o for all E (2.....d] where o E [0, π 7/4), (ii) 2d contexts: 8j = e1 cos o Cj+1 sin for all j E [d - 1], (iii) Context distribution: Pj = //N for all j E [M]
Under the instance defined in Example F(() for all i * 1 is inferior to 2(1) under all contexts and T((+d) for all E [d 1] is marginally better than T(1) by cos é only under context 0j and A (()())+((+))) = cos é cos? ø. We expect PS:BAI* to discover this feature of the instances and quickly identify e-optimal arm with course estimation of the context distribution.
Corollary 5.1. For the instance defined in Example we have HDE (I x) = Ö(N for all (Z2, E Xe (X)) (ee). In addition, if (cos @) cos Φ). we have
[[[]]
&Ô @((++(()) (Aayy +0)2
d
(5.1)
In(1/8)
where B[T]" is the minimal expected sample complexity over all (e, 8)- algorithms and f R satisfies f()) + 0 as + 0+ The upper bound (5.b achieved by PS=BAIt.
The order of HDE in Corollary 5.1 indicates that T((z()) Ö Lmax In(1/6)) is not dominating the sample complexity of PS=BAI+, suggesting that coarse estimation of the context distribution is sufficient when é is small. In other words, PS:BAI- exploits the feature of instances and utilize samples mostly for estimate context vectors, which is again expected.
Corollary [5T implies that under such instances, the upper and lower bounds on the sample complexity of BAT match up to logarithmic factors, that is, the performance BS=BAI+ is near optimal. Besides, the bound of NeBAI in Proposition 3.1 is with an extra additive term Lmax compared to the lower bound in Corollary [.I] illustrating that BaBAI is suboptimal and again emphasizing the significance of detecting changes and aligning contexts for PS=BAI+ to reduce the impact of Lmax-
6 Numerical Experiments
We now evaluate the empirical performance of PS=BAI+, We utilize the instance defined in Example D with d = 2, = -//8. We generate a changepoint sequence such that C++1 = Cj + L with Lmin 3 x 10 Linax 5 10a PIL, [miu] 0.8, PIL, Luax] 0.2, and fix throughout the whole set of experiments. We set the confidence parameter = 0.05 and vary the 0.03 x 1.35 for k [12). We set 7 6, the window size w = Lmin/ (3n) and compute b via (.55 in Assumption I For each choice of algorithm and instance, we run 20 independent trials. All the code reproduce experiments can be found at httttts:///gtthhi
slackness parameter from 0.04 to 0.6 (i.e.,
comm Hou/ Hou/BAI- BAI- -nAI-in-PSt PSLB. git
We first compare P and N=BAL Both algorithms succeed to identify s-optimal arm, while empirically, the complexity of PS= < 1% of that N=BAI. The empirical averages and standard deviations of the sample complexities of both algorithms are presented in Figure 2(a)
'we clarify that 3.5 in Assumption 1 is only for our theoretical guarantees. In practice, our algorithm has shown robustness w.r.t. the parameters and safely neglect the constants in the formula.

---

illustrates that empirically, the termination and amn recommendation of PS=BAI* are determined by the execution of PS=BAI as a subroutine, suggesting that in Theorem 3.3 the first term resulting from PS:BAI actually determines the complexity of PSaBAIT.
Figure ((a)
Next, we test the efficacy of PSc BAI - to learn and exploit the latent vectors and the distribution of contexts, Specifically, we run PS=BAI and B&B under Dynamics | where neither the index nor the vector current context is visible to the agent. We also run benchmark algorithms: D&BAI and its variant DeBAIg under Dynamics 3 where context vectors and changepoints are all observed; these two algorithms are detailed and analyzed in Appendix 0.4
As the changepoint sequence is fixed in a given instance and t/ Lmaxx 34 5 5t Lmin for all t E N, regard the number of context samples 4, as a proxy of the sample complexity т. We present the number of context samples need by PSeBAI+, NeBAI, DeBAI and DeBAI for arm identification w.r.t. 1/(4 + +)² in Figure 2(b)
Figure 2(b) contains three messages, First, the complexity of PS=BAI+ scales as 1/(Amin + +))² corroborating Theorem 3.3. Second, although PS=BAI+ has access to neither context vectors nor changepoints, it needs roughly the same number of context samples as D=BAI and D= suggesting that it is competitive compared to these algorithms that have oracle information about the environment. Third, D&BAI uses the confidence radius in (3.3) and terminates with fewer context samples compared to D&BAI, implying that the confidence radius is well-designed.
Furthermore, when & decreases from 0.03 x 1.35 to 0.03 x 1.35", the complexity of PS almost remains unchanged while that of N=BAI increases rapidly as presented in instances 9 to 12 in Figure 2(a) Meanwhile, the number of context samples need by two algorithms are shown to be with the same pattern in Figure 2(b) This contrast indicates that the cost of distribution estimation (Zb in (3.6)) for PS=BAI+ has been significantly minimized compared to NeBAI.
To summarize, emphasize that the empirical superiority of PS=BAI* over NeBAI implies that the efficacy of PS=BAI* is inherited BSI Our experiments show that actively exploiting the context information, via changepoint detection and context alignment (as in PS=BAI+ and PSaBAI) facilitates identifying the e-optimal arm efficiently.
algorithm requires Assumption aand the knowledge of Lmax- These may not available in practice. Thus, we conduct more experiments in Appendix to exhibit the robustness of BAI+. Specifically, in Appendix O.2] we conduct experiments for the case in which Lmax is misspecified. In Appendix O0.3 alter the change detection frequency y that and change accordingly. In both sets of experiments, the overall sample complexity of PS=BAI* does not vary significantly and retains its superiority over NeBAI. We conclude that PS=BAI* is robust to slight misspecifications in these parameters, as long as Assumption D is not severely violated. Please refer to Appendix O for further details and experiments.
Similar many existing algorithms in piccewise-stationar bandits 221 10 22
7 Conclusion and Future Work
We proposed a novel PSLB model and designed the PS=BAI+ algorithm to identify an e-optimal arm with probability 2 1 8. The efficacy of PS:BAI+ has been demonstrated both empirically and theoretically. We argued that this is due to the embedded change detection and context alignment procedures. There are several directions for further exploration.
Firstly, our PS=BAI+ algorithm provides fairly general framework for algorithm design. For instance, in addition to utilization the G-optimal allocation to sample arms as in PScBAI+ the xll-allocation and adaptive X'yaallocation | can also be considered. In other words, our PS:BAI* algorithm can be generalized to form an entire class of algorithms for BAI in PSLB models. In addition, deriving instance-dependent guarantees also of great interest.
Secondly, most of the literature on piccevise-stationary bandits 21 10 22
make assumptions to provide theoretical guarantees. It would be interesting to remove or reduce these assumptions under our s- B-BAI problem setup, and yet still be able to provide similar theoretical guarantees.
Finally, we believe that it is possible to adapt our PS=BAI+ algorithm to the fixed-budget setting, ie., to identify an c-optmall arm with high probability in a fixed time horizon in PSLB models.
10

---

This work is funded by the Singapore Ministry of Education AcRF Tier 2 grant (A-8000423-00-000 and Tier grants (A-8000189-01 and A-8000980-00-00),
Acknowledgemmnts::
References
[1] Marta Soare, Alessandro Lazaric, and Rémi Munos. Best-arm identification in linear bandits. In Proceedings of the 27th Advances in Neural Information Processing Systems, volume 27, pages 828-8 036, 2014.
[2] Junwen Yang and Vincent Tan. Minimax optimal fixed-budget best arm identification in linear bandits. Proceedings of the 36th Advances in Neural Information Processing Systems, 35:12253-12266, 2022.
[3] Yasin Abbasi-yadkon Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Proceedings of the 24th Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc., 2011.
[4] Mare Abeille and Alessandro Lazaric. Linear thompson sampling revisited. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pages 176-184. PMLR, 2017.
[5] Tanner Fiez, Lalit Jain, Kevin G Jamieson, and Lillian Ratliff. Sequential experimental design for transductive linear bandits. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché-Be Buc. E. Fox, and R. Gamett, editors, Proceedings of the 32nd Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[6] Mare Jourdan, Rémy Degenne, and Emilie Kaufmann. An e-best-arm identification algorithm for fixed-confidence and beyond, November 2023. arXiv:2305. 160441.
[7] Rémy Degenne and Wouter M Koolen. Pure exploration with multiple correct answers. Pro- ceedings of the 32nd Advances in Neural Information Processing Systems, 32, 2019.
[8] Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed aradd--aii- non-stationary rewards. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Proceedings of the 27th Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014.
bandit problem with
[9] Aurélien Garivier and Eric Moulines. On upper-confidence bound policies for switching bandit problems. In Jyrki Kivinen, Csaba Szepesvári, Esko Ukkonen, and Thomas Zeugmann, editors, The 22nd International conference on Algorithmic learning theory, pages 174-188, Berlin, Heidelberg, 2011. Springer Berlin Heidelberg.
[10] Yang Cao, Zheng Wen, Branislav Kveton, and Yao Xie. Nearly optimal adaptive procedure with change detection for piccewise-stationay bandit. In Proceedings of the 22nd International Conference Artificial Intelligence and Statistics, pages
PMLR, 2019.
[11] Yueyang Liu, Xu Kuang, and Benjamin Van Roy. A definition of non- stass-tttoorryyyy bandits, Feb 2023. 23v.2322.222222
[12] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Learning optimize under non- stationarity. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 1079-1087. PMLR, 2019.
[13] Jonathan Shapiro, Carlos M Carvalho, and Pradeep Ravikumar. Thompson sampling in switch- ing environments with bayesian online change point detection. In Proceedings of the 16th International Conference on Artificial Intelligence and Statistics, pages 442-450. Microtome Publishing, 2013.
[14] Zhihan Xiong, Romain Camilleri, Maryam Fazel, Lalit Jain, and Kevin Jamieson. A/B testing and best-arm identification for linear bandits with robustness to non- con-stationarit. In Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238, pages 1585-1592 PMLR, 2023.

---

[15] Robin Allesiardo, Raphaël Féraud, and Edalric-Ambry Maillard. The non non-stationary stochastic multi-armest bandit problem. International Journal of Data Science and Analyties, 3:267-283, 2017.
[16] Masahiro Kato and Kaito Ariu. The role of contextual information in best arm identification, 2021. #tXiv:2106.44077
[17] Yoan Russac, Christina Katsimerou, Dennis Bohle, Olivier Cappé, Aurélien Garivier, and Wouter M Koolen. A/B/n testing with control the presence of subpopulations. Proceedings of the 34th Advances in Neural Information Processing Systems, 34:25 01:251000-255 25110, 2021.
[18] Andrea Zanette, Kefan Dong, Jonathan N Lee, and Emma Brunskill. Design of experiments for stochastic contextual linear bandits. Proceedings of the 34th Advances in Neural Information Processing Systems, 34:22720-222 22731, 2021.
[19] Yasin Abbasi- Yadkori, András György, and Nevena Lazić. A new look at dynamic regret for non-stationary stochastic bandits. Journal of Machine Learning Research, 24(288): 1-77, 2023.
[20] Jia Yuan Yu and Shie Mannor. deccevise-stationan bandit problems with side observations. In Proceedings of the 26th International Conference on Machine Learning, ICML '09, page 1177-1184. Association for Computing Machinery, 2009.
[21] Fang Liu, Joohyun Lee, and Ness Shroff. A change-detection based framework for piecewise- stationary multi-armed bandit problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[22] Lilian Besson, Emilie Kaufmann, Odalric-Ambrym Maillard, and Julien Seznec. Efficient change-point detection for tackling piecewise-stationary bandits. The Journal of Machine Learning Research, 23(1):3337-3376 2022.
[23] Peter Auer, Pratik Gajane, and Ronald Ortner. Adaptively tracking the best bandit arm with an unknown number of distribution changes. In Proceedings of the 32nd Conference on Learning Theory, pages 138-158. PMLR, 2019.
[24] Yassir Jedra and Alexandre Proutiere. Optimal best-arm identification in linear bandits. In H. Larochelle, M. Ranzato, Hadsell, M.F. Balcan, and H. Lin, editors, Proceedings of the 34th Advances in Neural Information Processing Systems, volume 33, pages 10007-10017. Curran Associates, Inc., 2020.
[25] Peng Zhao, Lijun Zhang, Yuan Jiang, and Zhi-Hua Zhou A simple approach for non-stationary linear bandits. In The 23rd International Conference on Artificial Intelligence and Statistics, pages 746-755, PMLR, 2020.
[26] Masahiro Kato, Masaaki Imaizumi, Takuya Ishihara, and Toru Kitagawa. Asymptoti- cally optimal fixed-budget best arm identification with griaace-dependeen bounds, 2023. arXiv:2302.02988.
[27] Chao Qin and Daniel Russo. On adaptivity and confounding in contextual bandit experiments. In NewrlPS 2021 Workshop on Distribution Shifts: Connecting Methods and Applications, 2021.
[28] Yasin Yadkori, Peter Bartlett, Victor Gabillon, Alan Malek, and Michal Valko. Best of both worlds: Stochastic & adversarial best-arm identification. In Proceedings of the 31st Conference Learning Theory, pages 918-949. PMLR, 2018.
[29] Tor Lattimore and Csaba Szepesvári. Bandit Algorithmss Cambridge University Press, 2020.
[30] Byang-Sung Jun, Kevin G Jamieson, Robert D Nowak, and Xiaojin Zhu, Top arm identification in multi-armed bandits with batch arm pulls. In Proceedings of the 19th International Conference on Artificial Intelligence and Statisties, pages 139-148, 2016.
[31] Emilie Kaufmano, Olivier Cappé, and Aurélien Garivier. On the complexity of best arm identification multi-armed bandit models. Journal of Machine Learning Research, 17:1-42, 2016.
12

---

[32] Mare Jourdan and Rémy Degenne. Choosing answers in epsilon apsilon-best-anseen best-answer identification for linear bandits. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 10384-10430. PMLR, 17-23 Jul 2022.
[33] Michael J. Todd. Minimum- Volume Ellipsoids: Theory and Algorithms. SIAM, 2016.
13

---

Appendices
The contents of the appendices organized follows:
Appendix
we provide further motivating examples for our problem.
In Appendix
we discuss the limitations of our method.
Appendix
we review more related works on drifting and contextual bandits.
In Appendix
we provide more details about our algorithms
Appendix
pseudo-code of Ne BAI in Algorithm 2
Appendix
D.2 more details of PS:BAI including the precise definition of the confidence radius
Pt and details of LCD and L.A subroutines.
Appendix
D.3
pseudo-code of PS=BAI* in Algorithm 5
Appendix D.4 the computational complexity of PS:BAT in Algorithm
In Appendix
provide useful lemma for estimating the expected return of any in linear
bandits when the sampling rule is according to the G-optimal allocation.
In Appendix F
proof the upper bound the expected sample complexity of N&BAI
we detail the analysis of PSEBAI, i.e., we provide the proof of the upper bound its complexity in Theorem 3.2
In Appendices [
Appendix G
outline of the proof.
Appendix H analysis of the Change Detection (CD) and Context Alignment (CA) procedures. Appendix analysis of the estimation error by decomposing it into three terms: Vector- Estimation Error (VE), Distribution-Estimation Error (DE), and Residual Estimation Error
(RE).
Appendix proof of Theorem 3.2 based on the analysis above.
Appendix K proof of technical lemmas that are utilized in the analysis of PS:BAL.
Appendix
L
we prove the upper bound on the expected sample complexity of PS=BAI* based
on the analysis of NsBAI I and PS:BAI.
Appendix M we derive the lower bound on the expected sample complexity of any algorithm,
i.e., proof Theorem [.]
Appendix N we provide more examples to compare the derived upper and lower bounds on the expected sample complexity, and illustrate the efficacy of our PS=BAI* algorithm.
Appendix we provide more details of numerical experiments. In Appendix
provide more discussions
the related methods for BAI nonstationary bandits,
the getance-dependee upper bound,
the connection between the piecewise-stttionaayy linear bandits model to the stationary linear bandits model,
the special case where N =
Appendix Q we provide analytical results on the "Best Arm Tuple Identification Problem"'.
A Further Motivating Examples
We elaborate on the some concrete real-life examples that motivate our problem setup of identifying the ensemble best arm in piecewise-stationary linear bandits.
In scenarios such as investment option selection and portfolio management also mentioned by [10] there is multitude of options for fund managers choose from and typically, they want to find, in the initial pure exploration process, a small subset of candidate portfolios (or even the "best" portfolio) based on various economic indicators and the market performance of individual stocks before further exploitation. market, more portfolios tend to generate gains. The transition between these two contexts can be effected by stochastic factors, e.g., the weather, or the outbreak of a pandemic, making the market conditions (contexts) stochastic. In the face of these uncertainties (in the contexts and rewards), wish to design and analyze algorithms that selected portfolio to yield the best long-term option under such piecewise-statiine stationary environment.
bearish market, more portfolios tend to incur losses; while in bullish
Crop rotation is another example. Since crop yields can influenced by various factors, such as weather conditions (analogous to our stochastically generated contexts), selecting the most suitable crop to grow and harvest from is crucial. Given several candidate crops, crops of similar types (e.g.. potatoes and sweet potatoes) correlated they tend to favor similar conditions, thus, they can be
14

---

modelled by bandits with a linear reward structure. Contextual factors, like weather conditions, are well-modelled as being stochastic. A fixed weather condition will last period of time and it will not change suddenly. Domain knowledge from historical data/records provides us with prior knowledge on Timin and mmax- These observations dovetail with our model. Our objective is to choose the crop that offers the near-highest yield potential over a long time period (an ensemble g-best arm) and is adaptable to local environment factors, such as weather patterns.
B Limitations
Similar to existing works piecewise stationary bandits [1] 22 tions to provide theoretical guarantees for PS=BAI+ although PS=BAI+ has shown to be robust even in the absence of these assumptions. Since an algorithm may not need differentiate with close latent vectors for identifying an e-optimal arm, we surmise it is possible to weaken these assumptions. For this purpose, we will consider clustering the contexts into a few classes based on the distances between their latent vectors and design an algorithm that only aims to detect the change of context class, instead of the change of context.
introduced some assump-
contexts
C More Related Work
In drifting bandits (DB), the regrets of algorithms are affected by the level of nonstationarity of the environment, which can measured by various quantities, such as the total variation of the context sequence and the number of time steps when the return of at least one arm changes 23
25
In contextual bandits (CB), where the contextual information is visible the agent. 16 26
aim to identify the best arm with the assumption that the context changes at every time step according fixed distribution, and the return of an arm is averaged across all contexts. We see that the context distribution is involved to measure the quality of arms. However, while the agent in CB models can observe the context information, the agent has no access to the contexts but still aims identify an e-optimal arm in our piecewise stationary linear bandit (PSLB) model.
In adversarial bandits, existing works pertaining the BAI problem only explored the fixed-horizon setting (28). Due to the difference between the fixed-confidence and fixed-horizon setting and the difference between adversarial and piecewise stationary bandits. their results cannot be trivially extended to solve the fixed-confinn confidconeeeece BAI problem in piecewise stationary bandits.
D More Details of Algorithms NEBAI, PS=BAI and PSEBAI
All proposed algorithms make use of the well known G-optimal allocation (design) I 29 which is widely used in the linear bandits literature. The G-optimal allocation minimizes the maximal mean-squared prediction error all directions M. Given an arm set X, the G-optimal allocation X is distribution over the arm set, which is the minimizer of g(A) = maxxex || ( where
A(A) = Enex \(x)xx and À E Ax. Interested readers may refer to Chapter 21 in 29
D.1 The NAIVE BBST ARM IDENTIFICATION (N&BAI) Algorithm
BeBAI samples an arm with the G-optimal allocation at each time steps; its stopping rule is grounded on the property of G-optimal allocation (see Lemma E.T and affected by the maximum length of single stationary segment Lmax-
As presented in Algorithm 2
15

---

Algorithm 2 NAIVE E- ARM IDENTIFICATION (N&BAI)
1: Input: the arm set X, the phase length bounds Lmins Lmaxs the slackness parameter E, the confidence parameter
2: Initialize: Compute the G-optimal allocation X*
3: Compute C3 = =En=1 33 and t" = 3d In (6dKCC//))
4: Sample t arms {I, [= ~ X and observe the associated returns (Ye,,, Let t = t".
5: Compute
0.
arg max 8c.
#EX
(D.1)
8Lmax 4KCa13 In 8 5V In
4K
Pt
6: while 2T Pe + E < max TT. Pe do
7: Sample an arm ~ X and observe return Yi,, and let = ++1 1.
8: Update 0,, it; and Pr with (D.T.
9: end while
10:
Recommend arm d.- 222
D.2 Details about PS:BAI
D.2.1 Confidence radius utilized in PSEBAI
For each pair of arms (ar, i),, the confidence radius of A Axx, 8) time step is
N
(= 8) = 2(or + & +
Σ
clip (xr 3t + Ce 3)), Å
)=1
where a clipp == min max((a -2,, denotes the value of a that is clipped to the interval [-2, and
Nimax
2
= 5/ T. In
25
In
Óy.T.
Te 8m.
{
2 Linax
2
Bug min
In
2
Ti
δd,T.
25 Lmax
2
01,j = min
max
pt.j: 4 Tí
SA.T.
4
8
80.7, 15KT 8m,7; 15KNT SA.T.
15NT
(e(x, 2) minimizes the last summation. In the final theoretical upper bound on the sample complexity, we take G(2,, Ø) E for simplicity. In the experiment, we utilize
E/ Br. A.,
(x, 8)
arg min
Σ Be.( 3) + ((x,)))
(RR j=1
Σ5= Brs
for a simple and effective analytic expression in the experiment.
D.2.2 Subroutines of PS:BAI
In the LCD subroutine (Algorithm two estimates 0 and 0g of the latent vectors are independently computed from the first and second halves of the input CD samples (Line LCD only raises an alarm of changepoint (Line 4 when the difference between B and 8, is sufficiently large (Line and indicates changepoint occurs w.h.p.
The I.C subroutine (Algorithm 4 estimates the latent vector of current context and updates the dictionary CAid- Specifically, it firstly samples w/2 samples with X (Line 2). It then checks
16

---

Algorithm 3 LINEAR-CHANN CHANGE DETECTION (LCD)
1: Input: arm set X. detection window w, threshold and arms with the associated observations [[01, Ys.,,)..... (Tw, Yu, )-
2: Compute 01 2 - ((x))-1a,ee and 02
2 w D A(2*)-1a,yY,
3: if' 3r X, s.t./x' _ (02 0,)1 then
4: Return True
5: else
6: Return False
7: end if
Algorithm 4 LINEAR-CONTEXT ALIGNMENT (LCA)
1: Input: arm set X, detection window threshold and context ids CAid-
2: Sample 2 arms {āz]ez ~ X and observe the associated returns (Ya,a, Je=1 where
((1,, Y,,,,))s 7+1 (Ts; 1,,,,
3: for J E CAjd do
4: if not LCD(X, w, b, [( Y., + CAaaii) then
5: CAiali] = [ Y )1.-1
6: Return j, CAsd.
7: end if
8: end for
9: index = len +1.
[iia(index] [5xx v,,5, 1
11: Return index, CAja-
whether the current latent context has been visited in previous time steps by scanning through CAia (Line 3). In order learn if the current context can be aligned with context j. the LCD subroutine is called with the w/2 recent samples and Ca as input:
(i) If the current context is aligned with CAaa [i] (Line 4. the current latent context is w.h.p. Thus the LCC subroutine updates Ci and returns the index (Lines 5 to 6). which would be j. in Line 19 Algorithm| [ Note that in Lines 10 and of Algorithm | all the collected samples will be assigned to context je (until the next changing alarm) and will used estimate J. and py's. 's.
Therefore, aligning contexts allows PS=BAI to make good use of observation history.
(ii) If the current context is not aligned with any observed context, i.c., it has not been visited, CA gets extended with new samples pair and is returned along with the new index (Lines 9 to ITI.
17

---

D.3 The PIECEWISE- PIECEWISE-STATIONAR STATIONARY E- B-BEST ARM IDENTIFICATION (PS=BAI*) Algorithm
To help understand PS=BAI* algorithm, we highlight the differences between PS:BAI and PS=BAI* and the differences between subroutines LINEAR-CONTEE ALIGNMENT* (LCA*).
ALIGNMENT (LCA) and
Algorithm 5 PIECEWISE-STATIONARY B-BEST ARM IDENTIFICATION" (PS=BAI*)
1: Input: arm set Xt number latent vectors N, bounds on the segment lengths Lmin and I Lunax slackness parameter e, confidence parameter 6, sampling parameter window size and threshold
2: Initialize: Compute the G-optimal allocation X and T 38400 (n(8)) Lemax In N2K
Oc 3: Set CDemmple = []. CAia J. fcD = +oc. Set Tz. and initialize Te. Tr,, T3 with 3.2 for all t Σ T², i
[]. [N].
4: Compute C3 -==1 n and t" = 3d IndIn(Gen (6dKKCs//))
5: Sample w/2 arms m// X* and observe the associated returns (Ya,e, 1w/2 1=11
6: Set 2. ICA = ww/2, CA {1 [< Ys.,, ) mm/2] je = 1.
7: Set é; = 0. Pt 2e and de oc. Compute 0g with D.1
8: while True do
9:
==t+1
10:
Sample an arm X and observe return Y
11:
Compute ,e, de, Pe EU(t, 0,-1, Cz).
12:
if 1 Po maxz4$; 02 Pt then
13:
d2 =2-
Break
15:
end if'
if 7" then
17:
Continue end if
19:
if mod (L (4- ICA, + 0 then
20:
Update Je Jc-1, Teas. T--13. U [t}, [t],Te, Teg T--1s for # 30.
21:
else
22:
CD ssample CD sample + [(xre, 2r.z.)
23:
if CD sample 2 w then
24:
if LCD(X, w, CD Caammlel w then
25:
CD sample
26:
t= 2 tCA = t, tCD = t00.
27:
3. CA LCA+ (X, w. b, CAia)
28:
if i N + 1 then break.
29:
Revert T = T =izu,, for all E [N].
30:
end if end if
31:
32:
end if
33:
if &. # -00 then
Break end if
35:
Update the empirical estimates by 3.2) and
3.3
37:
if condition (3.4) is met and tcp = oc then
38:
Record & arg max_ext x O.p:
tCD
CC sample
40:
else if tcD = CD samplel 2 then
de A=
42:
Break
end if
44:
end while
45: Recommend f. Sc.
18

---

Algorithm 6 EESTIMATE UPDATE (BU)
1: Input: time step t, vector 01-1. threshold t* and constant Cs.
2: Compute 0, (1 1)0,-1 + x. 8t 0, Pt 28.
3: t 2 t" then
4: Compute dhe arg max Be, Pt 8 In 8 =EA
4KC
d In
4k
5
5: end if
6: Return 0e, de, Pt.
Algorithm LLNEAR-CONTEN ALIGNMENT* (LCA+)
1: Input: arm set X, detection window w, threshold b, context ids CAia, time step t, vector O.. threshold t" and constant C3.
2: Set 0, d2 = -00
3: for w/2 do
4: 8 8= ==1+1,1=1+ 11
5: Sample an arm H.
X* and observe return Ya,,,-
6: Set (It, = =
Y,,.)
7:
Compute 0e, de, = =U(L, O C3).
8:
if i O, Pt + max 0, + then
9:
2e = Ø4, index = (CA()) +
10: Return index, CAia, de. Oz.
11: end if
12:
end for
for E CAja do
14: if not LCD(w, b, (( Y,,,, 11 CAiali)) then
CAaali] (0., Na,a, 112m1.
16:
Return j, CAjd. end if
18:
end for index len(CCii)) 1.
20:
CAa[[index] [( )1,
Return index, CAjd, $2. 0q.
D.4
Computational Complexity of PSEBAI
We provide analysis for the computational complexity of PS&BAI in this subsection.
We consider the number of these operations: arithmetic (addition and multiplication) operations, logic operations and comparison operations and we also regard In(.), vf and sampling from distribution as one step of operation.
We decompose the main loop of Algorithm as follows, where the lines with O(1) operations are omitted:
Exploration phase (Lines 8 to 11): O(1).
Change Detection phase (Lines 12 16):
The L.D subroutine in Line 16 needs (wwd + Kd) operations.
Context Alignment phase (Lines 17 to 21):
The LCA subroutine in Line 19 needs ((wd + Kd)N) operations, as the LCD subroutine will be invoked N times the worst case in Line of LCA.
The reversion procedure in Line 21 needs O(ywd) operations.
The updating procedure and the stopping rule checking (Lines 25 32):
Updating 0., needs O(d)) operations, as we need to incorporate the latest sample into the estimate.
19

---

Updating Pt.j.j E [N] requires N operations.
Updating the confidence radius and the empirical best arm need O(KN) operations.
The stopping condition in Equation (3.4) requires O(K) operations.
We remark that some intermediate results can be stored avoid repeated computations and believe the algorithm is efficient overall. In particular, since the reward structure is linear, there are K arms, and N contexts, (dd), O(K), and ( operations probably cannot be avoided.
From the above analysis, the decreasing order of the number of operations:
The Change Detection phase requires the most budget as it will be invoked every 7 time steps.
The Context Aligument phase requires the second many operations. While requires many operations when it is implemented, it will not be called during stationary segment.
The updating procedure uses small portion of the operations, as w usually much greater than K and N.
The exploration phase demands constant operations each loop.
E Auxiliary results
Lemma E.1. Let X be the arm drawn with the G-optimal allocation X at time step s and Ya
x. 07 + Tys be the corresponding return with la,, O, |x. 07,1 S and mml S Then we have
A(X) xx Y.Y. - x x007, 0r 2 2ō
for all
1 In 2/8 +
In
Ad In Z In addition, if 2 In ?
have
d 2
P
Σ x A(X-)
-00 2 25 5V
In
5 8
8
Proof. Note that the arms are selected according to the G-optimal design, and thus BE-A [x ] A(X). Therefore, for all E [n],
E r T A(x)) YYYY,,, - x __00j_ =0
(E.1)
and
A(A")- x. Y, xx TT,
(E.2)
< r A(X*) A(X0)~1x,0 22
0- + +|- T A(X0)_1x,11 +
b= A(X-)-1 sr, [ 02 |x A(X)) ||
$ 2/ A(A²)-1ar, +1
< |||=|||(0))-1 (|= +1
3d
where we make use of the property of the G-optimal allocation in the last inequality
| d, Vr e X.
(E.3)
Additionally,
(x A(A²) x A(X')-1xaYaa Y.,,) )
(E.4)
(x ((A)) (x. 03, + n1a))
= (x TA(') ((AAA)('2,a) -2 00,) + (0 A((*) -2an)))
+ [x "TTA(()) - 07,- x (1x*)~12.7)
(a)
(x A(X*)-112)) (xT |]
+ 112 (x T A(Aa)=1axe)*
20

---

(8)
I 2E (a'
@ 2x A(x")-1x
(4)
S 2d
where we make use of the fact that "it is zero-mean and independent of other random variables in (a); |2__ # allocation
< 1 and IP !n? 1 = in (b); X in (c); and the property of the G-optimal
in (d).
According to the Bernstein's inequality with
E. and E.4
P
A(X*))'xxYa..
x 03 2
(ne)}
< 2 exp
nl 2d + dne
nE²
= 2 exp
4d + 2de
In order to upper bound the error probability by 8, we need
(- nE²
eexp
5
4d + 2de
d
2
d
2
4d
In
+
+
n
72
In addition, if n 2 $ In
2.
we have
2
4d
d
/
2
4d
5
max
8
ln
n
n
n
This finishes the proof.
Analysis of NEBAI
To analyze the theoretical performance of N=BAI, we first show that it can identify an e-optimal arm with probability - å and derive a high-probability upper bound on its stopping time in Lemma F.
Lemma F.1 (High-probabbility upper bound of N&BAI). With probability 5, the NeBAI algorithm identifies e-optimal arm after at most
δ
Limxx + In 3 (E + A Amiu)
12
time steps, where Amin min
( xi).
1
Next, we prove that after a sufficiently large number of time steps, the probability that NeBAI does not terminate is small in Lemma F2
Lemma F2. Let
768 25d) (E Amin)
768KCa(8Lmas + 25d)
To =
In (E + Amin)²
with C3 = m== steps is (a-1)C
3 For 2 To, the probability that NeBAL does not terminate before i time
Lastly, we apply Lemmas F. and F.2 to prove Proposition
3.1
21

---

Proposition 3.1. Let Amin min
A(x"2))
1
Lmax
In 8
and
TO
(E + A } In 8"
( + Amiu)
The NeBAI algorithm is (s, PPPCC and its expected sample complexity is Ö + +
The detailed analysis is presented as below.
F.1
Detailed analysis of NeBAI
Proof of Lemma
F.I
The result is to be proven with the following procedures.
First step: Prove
P3 x xT0, can be bounded with high probability,
Let 0. = 7 E. 0- (1) For all E > 0, we have,
N2
l |x Ea 0r TT =P
to E T
Σ
L Ja
te
1=1
N₂
(a)
12g2
=P
Σ
La (x
Ba - Lix _ jajaa)
> te
< exxp
(
2 No
(2L1)²
i=1
(b)
t
1 2 exp
8LLmax
Since (x: T Eaw 01 < and x
ja S 1 for all 1, we obtain (a) by applying Hoeffding's 's inequality.
We obtain (b) from the fact that Ei Li f and Li S Lmax for all I. In other words, for all å > 0.
x Bampo xTo 88 8Lmax
2 x
<
(ii) Besides, according to Lemma
E.1
ift > In 3. we have
d 2 8
d 2
P x Ü. x xT0, 5/
PP Σ
-0,
In
S 8.
(iii) For all / > all E X, since
x Ea-r, x 0e s 1x. Bonro -xx x
x. 02 x 0:
To
we have
IP Ea-r, -x x. Tāo p((aa]] s KCata
t> 4KCata
d ln
when
4 8
where
(a(a) = / 88mmax 4KCata
d 4KC,ta
8 na a a> 2.
+ +5/
C. =
Σn
8
For simplicity, we set a = 3 and write (3) as Pe in the following analysis. We now show that 1. 2 - In 4KC,1" holds when / > 3dIn BdKCa with the following lemma (the proof of which is presented by the end of Appendix[F.1 F.I).
Lemma F.3. Let a, b, and 2 1/2, then t max(2a Inb, 4ac In(2ac)) 2 In
With
4KCa
4KC'
a
b
c a = 3.
4'
6
22

---

Lemma F33
implies that
6dKC3
2 4ac (n(2ab)) = 3d In
= 2 max 4acIn(2ac)} + t 2 a lntt).
Define event E, n {1=
x
B
x rTo s pr(a) } for t 2 t" and E =
n
Eg.
We have
ZEA
12
Bi S Σ
8 Coto
P P
E
2 8
6.
KCata
C.
10
ZEN
1=1
We assume P. holds in the second and third steps in this proof.
Second step: Prove NeBAI recommends an E-optimal arm when it stops.
the algorithm terminates and returns dे * x², we have
& 02 Pr. + 8 2 max x T 0. + Pr-
Since
$ 1 0. Pr and
max x O. + ve 242,
max x0 af2.
Bon 2 x² EB
we have
$ Pg + 2 x² T Egn Po0,
implying that & E X. Hence, we always have i E Xe.
Third step: Derive the stopping time of NEBAI.
(i) Let T(2) = arg _8x, I' PE 0 and Amin minlar A(x* -2) (x* I(2)) P. We apply the following lemma to show that NEBAI stops when Pe is sufficiently small.
Lemma F.4 (130 Lemma 3)). Denote by i the index of the item with empirical mean i-th largest: ie., (1) 2 ... 2 (().. Assume that the empirical means of the arms are controlled by i.e.
Vi, (i) w(i) < E. Then,
Vi, vi) - S m())) S v((1++ +
Lemma implies that
a7 P. + 2 x² TT.. Eg- 2p. + 6 ==x72 Po 2p, + Amin and
max x 0, + P. S T Po P. + 2pr.
172
When Pe S (e + A Amiu) /4, we have
1 0 - p. + 2 2T2 0. +
Amin
2 T 0.
2p: 2 max x T 0, + Pr.
2
which will lead to the termination of NeBAI.
(ii) According to the definition of Pt. we have
Pe(a)= < + Amin)/4
81 8L In 8
4
d
4KCat
In
< < Amin)/4
In 4KCata 8
(V8lmax +5vd)
(5 Amin)/4
(8Lmmux + +5vd)
2
In 4KCata
e 12
(6 + Amin) #/16
8
32(8 (2 Lmax + +25d)
4KCat"
ln
(E + A Amin)
8
23

---

192 + 25d)
C6 + 25dd
(e + A m
(e Amiu) )
We apply Lemma
F.3 to invert the last line above. With
32 32 25d)
4KC₂
a (e Amin)
c= c= = 3,
Lemma F3
indicates that
2 4ac (n(2bc)) 384(87 + 25d)
768K C3 (8T.max + 25d) (s + Amin) 2
In
(s Amin)
max ln 4ac (ncln(2ac)}
= 2 a (bbt").
Altogether, we show that with probability 8, BsBAI identifies e-optimal arm after at most
384(8 max 25d)
768K C3 (8 + 25d)
In
A Amin) )²
(e Amin) 28
time steps.
Proof of Lemma F22
To begin with, let
Tu 768(8 768(8Lmma 25d)
768K (8 25dd
(E Amin)
(E + Amin) 28
For any T To, let T [T/2].
(I) If N&BAI terminates within T time steps, there nothing to prove.
Assume NeBAI does not terminates within T time steps. According to the analysis the proof if NsBAI does not terminate before T time steps, i.c., the stopping time satisfies
of Lemma ET
T-1
that 2 T, then event
n T=+1
Eg does not hold. This indicates
T-1
T-1 Σ
8
5
T
P T TT P
E
P
<
t dt
Cata
Co
[=T+1
t=T
t=T
8
(a)
5
(a 1)Ca
(T)
Ta
(a aa-
()-1))a(T/22
(a) results from the fact that T 72 T/2.
Altogether, for T To. the probability NeBAI does not terminate before T time steps is
(a (2-
Proof of Proposition
3.1 First, Tonelli's Theorem implies that
+oo
E E > 2) dr /
+00
E|r] = E
1 dr
E
I(r [(>>x) x) dr
P(r > x) dr.
Next, we apply Lemma
to show
ET < To 1|7T7
To + 1] P/r 2 To + To
PPT 2 x) dx
To
<To To (a 1)C, (= dr To + (a-1)(a (T 2 (F.1)
Besides, Lemma El indicates that N=BAI can identify e-optimll amm with probability 1 1 6. 0
24

---

Proof of Lemmal F.3 For x >> 0, let
1- ald
acin r
f(z) = z In(bbr) = - -a-anb--ase achn
Since
aln
x 2 2a Inb
f(x) 20 =
acIn
2acIna
2
Let 2ac, x = ddn(dy): then
x 2 2ac x = dnn + d'In(dy) 2 d(n(dIn(dy)) = In(dy) 2 In(dIn(dy)) + y 2 In(dy).
Since 2.4 > In = for all 2 2 1, we have In(dy) S (dy) I dy and
y 1nlyy = 2 / dy = y ッ
when yd 2 1. Hence, when ac 2 1/2. d= 2ac 2 1, we have y z In(dy). Furthermore, for such that 2 m2u In b, 4ac (2ac)), we have ((x) 2 0.
G Proof Outline of Theorem 3.2
proof outline of Theorem 3 is provided in this section. consists of three steps:
Step 1: PS= AI (Algorithm depends on the success of change detection and context alignment (Algorithm and 4). We firstly upper bound the failure probability of these two subroutines via Lemma G.1 Lemma
Lemma G.3 and summarized in Lemma G.4 More details about these
two subroutines are provided Appendix D.2.2] and the proof the Lemmas are postponed to Appendix F+]
Step 2: Subsequently, conditioned on their success, we provide a theoretical guarantee for the choice of the confidence radius Pr (r .) for A(r, 7) at time step t in Lemma G.5 The proof is detailed in Appendix[[
Step 3: Lastly, utilizing the above elements, we provide a sufficient condition for the stopping rule, and upper bound the number of time steps in Exp phases T, via Lemma G.6 whose proof presented in Appendix ! As the total number of time steps T is upper bounded by a constant multiple of Tr, the prabbbitbbbilttyy upper bound on the stopping time is obtained. This finishes the proof of Theorem (please refer to Appendix
Step 1: We borrow the terminology in hypothesis testing to define the errors. Let the null hypothesis be: the algorithm has undergone a changepoint within the last w CD samples. For Algorithm 3 we will characterize the type I error: the algorithm has experienced changepoint within the last w CD samples but it fails to raise changing alarm, and the type II error: changepoint has not occurred but Algorithm raises a changing alarm. We refer the event Failed Alarm (FF) and the event False Alarm Error (FAE) as that type I eтror occurs and that type II еттоr occurs, respectively:
FA2 == {a type error occurs at changepoint ) 1 E N, FAE; {a type II error occurs time step t), t TEAE,
EA =
U FA and FAE = U FAE, (baSr)
(ETRAB
where TEAE == {t : t in CD phase, & < T wy, t nC = 0} and T is the stopping time. In term of Algorithm 4 define the event MI; = {Algorithm misidentifies 03,}, I E N and MI
U(herr)) MI,. Define the good event
Good == (FA* FAE A MT
(G.1)
We upper bound the failure probability of Goodin Lemma G.I the results Lemma G.4
Lemma G.2 Lemma G.3 and conclude
25

---

Lemma G.1. For any ÔEAE E (0, }}, with b 2
8d In
Sd
In
24
dln 2
L.D
3w
3r0
SEAE
DFAE
makes no false alarm before the stopping time with probability at least
PFAE 21 K KŌFAE.
Lemma G.1 can also be stated as, fix
IP [[AE]] I 2K exp
min {
3wb wb²
20d
150d
which indicates can always decrease the probability by enlarging the window size Assume Or observable, i.e., 0)), * "لسسا and denote as the alarm time of e from Algorithm
Lemma G.2. Conditional on FAES, for any ŌFA E (0.1). if A. 2
d In
BPA
d In 2
1d In 2 +
OFA
W7 Pasasa+ c 2 a 2 ŌFA 2
In addition, P [[AA
LFFA.
Lemma G.2 guarantees a prompt change alarm will be raised within time steps after changepoint 2 samples are abandoned at line 16 of Algorithm so that Tr. only
occurs. This also explains why w7, keeps samples from context j.
Lemma G.3. Conditional on FAE and FA5, based on the conditions in Lemma G.1 and Lemma G.2
P [MI]FAAE FAT] 1 [[N 1)6FA + K KÖFAF]
The intuition of Lemma G.3 is simple: change alarm should not be raised when the samples from the same context and, change alarms should be raised when the samples are from the other (N - 1) contexts. The error made by Algorithm and can be concluded follows
Lemma G.4. Assume the instance satisfies Assumption
7
[Good] 2
2r 2
2
Step 2: To give an upper bound on T,, we firstly prove that the estimate of A (z, T) at time f is within distance (z(x, Z) from the ground truth w.h.p. Define the event CI as the estimates of all the mean gaps locate in the high-probe high-robbability Confidence Interval
CL2 := { ((((z, - A(x,ū) &
and CT
:= = Ng CT,, where P: is defined in (3.
Lemma G.5. T, 2 2bmax In 2
da.re
PP Good] 2 - (Kō., Nō K KNomm.)
In addition.
8 2
P
[CT] [Tod] 2
In addition to an estimation over the latent vector which is sufficient under the stationary case (ar in Pc), also need control the derivation between the empirical distribution p. and the ground truth (Be in Pt). as well as the interactions between the latent vectors and the distribution (E, in pc). This is reflected by K K&..T. T. NN and KN (NN6m.2 which bound the the failure probability of Vector Estimation, Distribution Estimation and Residual Estimation, respectively.
Step 3:
Lemma G.6. Conditional Good and CI, the recommended arm & E X and when Algorithm 1 terminates, the order of ; upper bounded by (3.6).
The detailed proof is presented in Appendix
26

---

H
Analysis of PS:BAl: Change Detection and Context Alignment
As the output of Algorithms B and depends on random samples, the output may not meet our expectation with some probabilities. We will characterize the probabilities of the three "bad" events: FAE Appendix [..] FA in Appendix H.2 and MI in Appendix H.3) and finally upper bound the failure probability of the good event Good in this section.
Lemma G.4. Assume the instance satisfies Assumption 7
P [Good] 2 1- 2r* 2
2
Some notations are introduced first
1 ) is the latent vector sequence.
è indicates the time step when we raise alarm for the (th changepoint.
According to the dynamics (see Dynamics 1 of the problem, at a changepoint a E C, the next latent vector will be sampled from Pa. Therefore, may happen that f% = 8% 1 ie, this changepoint ci hidden and these two consecutive stationary segments are observed as one stationary segment. In order to upper bound the errors made by Algorithm 3 we make the following assumption, which yields the worst-case scenario in terms of the error probability.
Assumption 2. Given f1:0 and the changepoint sequence C, 0% * +0; 0i44, 1I N.
In this section, do consider the randomness of 01:0. i.e., consider realization of the sequence The results do not involve any parameter depending on the specific sequence and thus can be applied to any latent vector sequence.
H.1 False Alarm Error
Lemma G.1. For any SEAE E (0, 1), with b δeam
8d In
SPAR
+
dn LCD w
dPaR
makes no false alarm before the stopping time with probability least
P[FAE]] 2 T K KÖFAE.
Proof of Lemma G.I Note that within a stationary segment of length f, the observations are i.i.d., and thus the time segments between two consecutive false alarm time {& 2 (where â = 0) are i.i.d. i.., it is renewal process. Thus, it is sufficient to bound the error probability under the stationary case, i.e. C 0 and 0 1:00 (0), 07, )=
Assume that we are under stationary segment of length We wish to upper bound the error P[FAE] P(c1 t]. This is given by Lemma H.1
Lemma H.1. Given w CD samples from the same context [(t,, V. in CD phase at time step t, Algorithm 3 makes a false alarm error with probability upper bounded by K KθEAE. i.e.
P [[FAE]] < KPFAE
b 2
8d 310
8d 3er
+ 24 dln 2
BRAR
OPAR
BPAR"
Assume y divides t. In the case a stationary segment, the input samples to Algorithm
are
[I(Tays Yey w 11 [==1 if no changing alarm is raised (We ignore the initialization at Line in Algorithm for simplicity). Denote r₁(t) = (le = mod w, ko S t), = 0, 1, 1......... Given any O....,. W for any kn * hb E (())), the two list of samples, [(xte Yoy..., } 1
... w
s=h1
and [Kay Yoy,.,, Mo do overlap (thus, they are independent). Therefore, Pk Pl
'This can also be taken as, we are conditioning on 01.0.. as the realization of the sequence is independent from the behavior of any agent/algorithm.
27

---

by by E [t(t) is geometric distribution with parameter upper bounded by KOFAE. We have P(c1 E ET(())] < (1 - KδPAB) (F(())
(.FAE)FF(0))
Hence, the cumulative false alarm error is
P[FAE]
P [2 S
W
(1 KŌFAE) [.(00] (.00))
KOFAE
Proof of Lemma H.1 According to Algorithm
3
given w CD samples from the same context
[T Y 22,,))=== and x E X, we need to bound
s Σ
P
x
ATAA E.Y.,
Σ x A'AA())-1a)) T.Ya,
2
W -1 b
2
+1
The proof is similar to Lemma
E.1 For any s E [ and 3 = 2
E
a A(X²) 2 Yo x A(A")- =0
and
x: T A(A*)
x A(X")-
x -2, 07, T A(A*)- ++=
< 4d.
By making use of E.4
(x T A(A*) ".Y.,,. -
- ( )"]
E [o= ((aTA(A)- A(A7))+,,YY..) + E (x 1 "]
2F [x.
YY... x T -23
< 4d + 2E [|xe T0, x 07,1
S 6d.
According to the Bernstein's inequality.
P
Σ
x T -AA*))=a,xx - x A(T) - Yo4 2
)
w
==1
2 ( 2
< exx
W 6d
2
2
= exp
12d
8d F
In order to upper bound the error probability by SEAE. we need
2
2 exp
S ÓPAE
12d +
&d
28

---

4d
2
4d
2 ÒFAE
2 ÓFAE
In
+
In
+ 12
d
3
ÖFAE
3
By the choice of b
In
+
|
In
24 d In
we have
3m
ÓPAB
3w
SPAR
ÓFAR
2
2
PP
A(x))
Σ
x
A
2 ÓPAE-
$=
A union bound over the K arms yields the final result.
H.2
Failed Alarm
Lemma
G.2.
Conditional
FAE,, for any ōFa E (0.1), if A
In
to
dPA
In
4d
In
OFA
w
ŌFA
P plsassar
w à ạ 2 1 -8AA
In addition, P FAA < LLFA
Conditioned on FAES, the detection at the changepoints is independent. Thus we can assume there only one changepoint ej within certain number of consecutive time steps.
Proof of Lemma G.2
Algorithm ijis given w CD samples which are collected under two different context. Without loss of generality, we assume the sample selected time e₁ is among the CD samples (otherwise, we can regard the time step of the first sample from the second context as cj). We wish to bound
P
c S é S +
70 2 è
which is the probability of the event that, after changepoint occurs, a changing alarm will be raised within 72 time steps (or CD samples). Here, è C₁ can be guaranteed as we are conditioning on that there is no false alarm error (FAF").
The event er I à S ci
THe indicates, at least one of the CD sample list in 2
(( Kk)
will trigger the changing alarm in Algorithm 3 In particular, in Lemma H.2 we consider the failed arm probability when the CD samples are composed by exactly half samples from each contexts,
(Gfo+((-1--))) Yo +0-- (s-11-))haajic -4-)
Lemma H.2. Given w CD samples from the two different contexts [(t. )l in CD phase, where [i., )1 is from latent vector 07 and [ā., Ys,a, )l 4+1 is from latent vector f Algorithm 3 raises changing alarm with probability lower bounded by
1 1-ŌPA
if / ōEg + In
4d In 2 where Ae maxrex Jx: [xT 09)1 and it is w
w
dew
dra
assumed be greater than b.
By making of Lemma
H.2
P a S S + 47 29
-P [Kk E { +I, wl,
LCD (w, (lFb,(FFette-t Ye, Ya
Ki 1o- ny, )1==1)) True 2 2 c1
29

---

2 LCD w. (( th Ya +(- -0 +6o-1 4n |= Truefe 2 a
2 1 ÖFA
where 4. max |x' (0} - -g)) and 07. 05 are the latent vectors. Hence,
IP |AE - FA FAE] < - (1 ōFa)" S 1FA
Proof of Lemma H.2
According to the design of LCD, there exists an I E X,
2
T A(A)) J.Y.,E. Σ T A(A))
T. Y
2
W
s=1
+1
Σ
W xJ A(X
[03 07)
T
2
== +1
2 ạ 103 03}
Σ (x T A(A*)
H.Y. x =x10))
Σ
x -AAx")-2_,1
x xxTz))
x (0) 83)|
2
ŌFA
where the last inequality holds as 2
2 d In SPx
+
In
2 dox
1d In
H.3
Context Alignment
Lemma G.3. Conditional on FAE and FA", based on the conditions in Lemma G.1 and Lemma G.2
P |M FA S 1 [(N - 1)5FA + KòPAE]
Proof of Lemma G.3 The error of the context alignment procedure can be derived from the FAE and FA analyses. Conditioned on FAE FA and that the previous ( contexts are correctly identified, i... Di=l MIg, we have the following statements.
Firstly, according to Lemma H.1 the change alarm at Line in Algorithm 4 will not be triggered with probability at least (1 KŌFAE) if the current context is context j. This error has been taken into account in the FAE (see Remark H.3)
Secondly, if the current context is not (which will occur at most N times), a change alarm will be raised with probability at least 1 ŌFA by Lemma G.2
Therefore, the error probability at is upper bounded by
P |MEE, FA5, .ass.nn-110 M[g S (N - 1)ōgA + KθEAE and by union bound, the cumulative error probability bounded by
F [MI]FAE" FA - IP [MI[IFAEs FAA]
(H.I)
- (1 (N 1)6FA KÖFAE)* < l, ((N 1)8FA + KÓFAB).
Remark H.3. Note that (1) we will only bound the FAE when the CD samples are from the same context; (2) in the analysis of FAE, we bound the error probability the whole horizon up time t
30

---

as we assume there is no changepoint. In particular. there will be unused and redundant KOFAE ervors budget for FAE at each changepoint, which accumulates 1 7 K ÖyAa before time step Therefore, the second error term in (H.1). I, KÖYE,, can be covered by the unused 1, w KEyA error budget from FAE, and thus it can be neglected in HH.1
2
Proof of Lemma G.4 According to Lemma G.1
G.2
G.3
Assumption and Remark
H.3 given
time T, the total failure probability is upper bounded by
P P(oood") = P |FAE U FA MT]
(H.2)
< KOFAE + L,PPA + + (N 1)6PA
KOFAE + LÖFA
In particular, when 7 is upper bounded by T" Line 2 of Algorithm 1
NLmax 2 X2KLmax/E
TS T
In
22
8
where cp = 6--0440 In 6400. The number of changepoints till T is upper bounded by ly- S By Assumption when the conditions of Lemma G.I are met. And upper bound 7/4 K ŌFAB by & S 4.
= Iimin'
3w
Span
+
3w
8d
In
8PAm
24 dln ōpan and ÒFAE
w
4(r
By making use of Assumption and setting SFA = 4N1, we have dPA > SPAE and
A-
b
4d
2
4d
2
6
2
In
In
In
2
3w
ÓFAE
3w
ÓFAE
w
ÓFAE
d
2
d
2
2
4d
2
In
V
In
In
W
ŌFA
w
SEA
w
ÓFA
Thus, Lemma G.2 can be applied. 1,- NOFA can be upper bounded by IF
4
Therefore, according
H..2
P(Good]
8
2r
I Analysis of PS:BAI: Estimation Error
Lemma G.5 is proved in this section. We will upper bound these three error terms (see LT) ): VE
error in App DE error in App 1.2 RE error in App [.3] and finally will prove Lemma G.5 which upper bounds the failure probability CI at the end this section.
Lemma G.5. T 2
2b In 6amr!'
9
Good] 2 1 - (Kopm + NOAT, + K K&
In addition,
P [Co]] 2
2
Given any two arms I E X. by the triangular inequality, the deviation between Á,(x, .) and A (z, 2) can be upper bounded by three terms: the Eestoo--stimttion Error (VE) term, the Distribution- Estimation Error (DE) term, and the Residual Estimation Error (RE) term:
A [x, Ø) - A [x, Ø)1
(L.I)
(z σ) '. (x x) -=)Tep Opl
31

---

N
N
(I, - (,(2, 2) Pr.s
Σ
clips (x, TP(us - -pi)
+
==1
j=1
VE term
DE term
(x, A (z) (Dis Pi)
RE term
where <liip cl)py(a) = m mma 22,, 2} is shorthand notation for the value of that
clipped to the interval [- 2]. The reason the value A .) clipped the ground truth | (zr Ø < 2.
Recall the event CI
CL. ( saC, X7,
CI = 0 Cl,
and the confidence radius
(e(x, 2(a + +x) +
Σ
Be, A
clips
(x, x) + G((z,
(I.2)
j=1
d In
2
5
B In
where
a₁ a= 5
Beg
Tr δd,T.
N Limax
25 Lmax In Oijj == min { 4 (r... 4 T. 8a,7. 4 2
2
1
== 2
In
and (e(x, 2) E I can be any value. In particular, it can be the value that minimizes Σe= Bt, | 1.j (z, fe( or it can be taken as E. For simplicity, we will take (e(a,
arg wigminn,cc [ (x) Σ/n1
Ei Ai, (m,5)) for a simple and effective E Beg
analytic expression in the algorithm.
1.1
Fistma-Estimation Error
For the VE term
Σ
j=1 (1,(,,))A,,,,,3 Pes note that
N
N
Σ
(t)
(x,, ()) mes 1x (θ. O)dd + + (Ô, O))eel
Lemma I.1. Given x E X and Ti 2 $ In 2
p|x [ O)prl 2 04 Good s 6u.7
Proof of Lemma L.I By the definition of the estimators in 3.2
x T() - e)p: = Σe
(0r. - Pt.
j=1
Tt.j
A(X")-12
-07
Th. T
T/
j=1
1
Σ Σ
x 12x))-22,y...
-
-x
T SE
32

---

By Lemma E.1
PP |a> (Ó. O) 2 at 01:00 Good] I 8,,
By the property of conditional probability, we have the desired result.
Therefore, conditional on Good, with probability at least KōU,T VE S 20z for any 2, 5 E X.
1.2
Distributtion-Pstimatti Error
Lemma 1.2. Given Good and T, 2 2kraax In ōa.z, foraany/ any j [N],
[lpe.s - -Pyl 2 Rr.5 Good] S da.
Additionally, with probability NNd,T
N clpp (fm,s - pi) S Σ
N
A
B B (x, (x, + (((x,))
==1
where (1 2)) can be any value.
Proof of Lemmal
T.2 Given any j E [NV] and the stationary segment we denote X₁,1 == L = 0j} - p T4, where i is the total length of the Exp phases the Ith stationary segment. Note that E[X,,ıl [ Good] 0, X & Lmax and Var(X,,llid Good] p, P,) s
(1 P2) I By Bernstein's inequality,
Xyrl 2 ef Good
2
P
< 2exp
2 Bar[X,]GGood + L
1=1
T762
X5, 2 dfta)// Good
2ex
2 Σ ii=
Var[X Good)
Temax T2e
As
Teg E'= i, (0 =
tn and E/r îg =T,, we have
T?c²
P
Piis p,l 2 elfietie Good] 2eep
2 Var Var(X, | Good + 2 Lmax
T?c
$ 2exp
2 D P,(1 p;) L Lma
T/62
$ 2exp
2p,(1 Pÿ) Lumxx I
As the last bound is independent of (L. we have
[lpr.s - pýl 2 E Good 2xxp (- 2p, - Py) Liuxx + Lmaxe
Tic²
(-
If we want to upper bound the above by 8d,1, E (0, 1), i.c.
eexp (- 22,((1 (1 - p + 2 Limaxe
T₁
< Sa.
we require
Lmax In 2 + v (t In
2
+ 2TTPP P.) L In Ja.za
hars
(I.3)
Ti
33

---

In particular,
5
Limxx 37,
2
2p, (1 Pí) Li)xmax In
2 Sd.T.
Brg 2
max
In
ōd,
Tb
satisfies the condition, we have
P Pi. -Pyl 2 Best Good] S 8d.
(I.4)
problem here is we do not have access to pj during the dynamics, therefore, we adopt Lemma to further upper bound Brj by Be.j.
K.
Lemma K.1. Given any j [N] and Te 2 24aax
In 2 Bes S Br.j.
9
Therefore,
P [l P5l 2 Br,g Good] S da,Te
In addition, with probability at least - - Nō..T, we can upper bound DE term as:
clip (r, (frrs -pi)
clip (a. + Ce(x,, 8)) (fr. p.))
(I.5)
N
Be. A ا
clips (x. 3) + (e(x)))
S
where (x B) E IR be any value.
1.3 Residual-Estimation Error
RE is composed by the product of two deviations, i.c., (A, - A (x, and (pr. ps).
as the time stept becomes large, we expect will converge to zero fast. Thus, it sufficient to have coarse estimation of it.
Lemma I.3. For any X, conditional on that (it. Pyl s Beg. Vj [N].
P
Σ
(1, - A (sr, (z) (Des pi) & Good < No
where & = 25 Nanax In 8
T.
Proof of Lemma
1.3 According Lemma E.I for any E X,J [N] we have
d In
2 Good
IP
x (0] ا..) 2 5,
8m,Ti
(1.6)
Te,j
8m,11
if Tej 2 d In
2 Note the fact that (, .:) E [-2, 2/. hence,
k...I""
(x, 2)
Aclipe (x) = (,) 2) D..s (z, a) s1x 1 1 -..))- (L.7)
And |xe [03- - d1,5) < 3d with probability 1. Denote
1h.. == max { ( 4T, In
2 5M. 1/ = max { (in::
25 Lmax In
2
3 } (1.8)
T.
34

---

We have
(x, -
-
-
R) (pes ps)
Σ (A)((,,)) ب (s. k) Besl +
Σ
(A)(o, 2 (z. 83) Bes
Σ
(A)(2,)) - (2, (I, B3) Pei
In
Σ
(A)(I,)) - (z, (z, Brs +
Σ
(A)(e,))-
A 5) Beol
Σ
x IT (07 - - + [07 Benl
(I.9)
Σ
5
2
Imax In
2
2
T
8d,
d
2
5.
5v2
Lmax
2
min
4,2
5l
In
In
Ted
dm...
2
2
Te
Sg.
j.Pi Puss 0t.j
d
5
8pt. Imnax
2
Σ
2.5
In
In
Te.
8m
2
Ti
8d,
j.V.,..==
Σ
2
Limax
In
2
Te
ōa.T.
d
25v2
Linax
2
min 4, 10
In
Te.j
8
8
Te
ōa,ra
VdLmax
2
Σ
50v2
In
(L.10)
T
8m,7%
< 50v2"" Lmax
Tr Ōm. 25.
where (a) adopts (L7) and (b) is obtained by the following derivations:
(1) V1..11 > Pt.j indicates Pr. <
d 2
25 Lmax In 2
4 T da.r," and thus Brg s
5 2
7T:
Jm.ni
5V2 Lanx In 2__nn In addition 2t Ja.r
A x) - Acipp (xx 2) S 4.
(2) vr.1.1 = Pt.j indicates Pr.j I In 2 and 2h. > Pr.j implies Pr.j <
25 Lygas In 2 4 T.
thus
4T.
Bm.
85,
(.6] can be applied and Br, <
5v2
Lmax In
2 T. 8a.
*The last inequality can be loose. When each context has been visited at least once, the first summation in (L.0)) can be ignored. For empirical performance. (1.10) should be used, while is adopted for theoretical guarantees.
"This demonstrates the usefulness of the clipping technique. Without the clipping technique, we can only get upper bound of 6d utilizing [B.2 which introduces another factor Et.
35

---

(3) V1.j.2 = Pi.j indicates Pt,j 2
25
Linax T:
In
2 6a.7
2
In
can be applied and 2 thus (.6)
16
AT.
6m.7,"
Big 2/ 180,, In 3.
Therefore, conditional on Good, with probability at least K KN6m. RE < 2
Proof of Lemma G.5
By Lemma I.1 and
conditional on Good, with probability at least (ax B) S pı(z, Ø). This finishes the proof of
1 - (Kô,, + NåÆ.I, + KN6 the first result in Lemma G.5
A [z,
We then accumulates all the error probabilities. By the choices of d0,2; = 15K7. 6a, =
15N27' 5m = 15KNTT"
0
20
K8 + NdaT, + KN6
+N.
KN.
15KT
15NT,
15K
7=
00
35
1577
7=
Note that there is an reversion step at Line 18 Algorithm for each T E N, there are at most two time steps t < t2 with Tú, Tig. Therefore,
Kd + Nōa,7. KN6 5
Kōo,n + N8a. + KN6 22
Σ
t=1
T,=1
This proves the second statement.
J Upper Bound of PS:BAL: Proof of Theorem 3.2
Theorem 3.2 is proved in this section by three steps.
Firstly, show that the recommended arm & an e-best arm upon the termination of the algorithm in Lemma [
Secondly, we present sufficient condition for the termination of the algorithm in terms of T, in Lemma G.6
Lastly, show that T, bounded by a constant fraction of and thus, obtain an upper bound on
Step 1:
CI holds with probability 1-(K 6., + NNā,T, + KKN6m, Conditional on the good event Good (.. and event CI, (the mean gaps are well approximated at time step t), expect the recommended arm will be an e-optimal arm. This is formalized in the following lemma
According Lemma G.5
Lemma J.1. Conditional on Good and CI, if the algorithm stops at time step t, the reconmended
arm S.g xt is 8-best
Proof of Lemma J.1 f x². the lemma holds.
fe + x,, according to the termination condition (3.4)
min Áe( antce
pc( > -5
we have
A(#,,x") 2 (e( pr
min Ar( x) - pi (
where the first inequality holds due to Cl, This indicates A(x", $c) S and thus the recommended arm f. 2² is e-best arm.
36

---

Step 2:
Lemma G.6. Conditional Good and CI, the recommendedd arm &g E Xg and when Algorithm 7 terminates, the order of T, upper bounded by (3.6).
Proof of Lemma G.6
By Lemma I.1 Kg E X. Note that for any x + Ge, when
[p, (2, te) (xx, k2) tE, Le + x² and x = x²,
(I.1)
pc(0ss x) + Pe(2", , S axx ,x) +e, otherwise.
By utilizing CI2, we have
x((0),x") - Pe( 2 A( (t) p=( 2 Aela" 222) 2pr(x" ,Te) 2 -E,
&e # x² and I x¹, (r( (e( 2 Sc(x*, x) pe(tt: 2 A(x",2) - pe(x" x)) p ( e otherwise.
Therefore, if J.1 hold for all a + Se, the algorithm must have stopped, i.e., is sufficient to have the following for any + fec:
pe(a" (t) A(r" (c) +e
f x² and x x²,
A ,x) .p(( x)
A(x" x) + otherwise.
2
Lemma 1.2 gives an upper bound the total number of time steps in Exp phases at which J.1 must hold for any two arms Ve E Xx, E X (xe).
Lemma J.2. For any two arms T). where x + Tz, x", when
6400 6400 d In Kd/ (A(x*, x)) +))² T.
(A(z* x) + +E)
+ 6400 In 6400 HDE(I,, x) In NHDE(EE,
8 KNLax A(x"
3200 3200 N maxx
(J.2)
A(x (x*,x) +
6
d
1 + HDE
1
N Lmax
1
In j (A(a*, x) + +)²
In 0
In
A(r
A
where
Liax
N
1 (E)) +el
HDE(Le, = (A(x", x)) +8)
min 16ps 7
we must have
A(x (x),x))+ +
pe( x) <
2
By taking the maximum of J.2 over all s-best arms and the suboptimal arms, we get
6400 In 6400 d In Kd/ (A(x*, +) e)²
T :==
max
2. E.
(A (A
=)²
+ 6400 In 6400 HDE x) In NHDE(IIE x)
8 KNL
3200 3200 N NLmax
A(a ,2)+
In
(J.3)
A(x", ,x) +
=
max
d
In 5
1
+ Hon 1) In 1 N Lemax In
1
(A(x", x)) + E)
A(x", x)) 4
37

---

Proof of Lemina J.2 Let Cd. Cm (0,1) be constants, satisfying co + + 20m 1. By the
definition of pe (ee 1) in (.3). is sufficient to have
A(x", +E
20 S Co
2
A(*",x) +e
Brg A (Ee, x) + (e(xe, & (ca + Cm)
2
j=1
, +e
2 S Cm
where we take x) = E for theoretical simplicity, but we adopt ((
arg min (t, Σソ Prss(r.,)) (z,,(z, G((, = Σn (15aa)) in the algorithm, which Σn= R6,
still enjoys the theoretical guarantee.
VE Term According the definition of az, need to bound:
(xx", .x) +E
a4 C.
d 2
21x*x)) +E
5
S Co
T
By coarse estimation, is sufficient to have a,d
In Kd/ (A xx" x)
d
Kd/ (A(x" x) + e)
T, (A(x" 2²) + te)
=0
In
5
(A(x*, x)) + +
8
where c,
6400 In
<
+
DE Term The difficulty lies at the DE term.
N
Begl
clipa 1s
(Ir: + (x)
N
Beg i
Aclipa
clipa bd
(Iz, 2) El
Σ
Besld Aclips
clips (5z, + el b.
Σ
Begl (Is, + +el + Be, A (x D, (x),
Σ
(2(++
Σ
Be, A
(Ee, Aclip
clipa
(5 x)
ja
jahes P
Σ
+el
26,
+
Σ
(Ze +
j. PLj
We will upper bound 2 by Cm analyzed later. Therefore, it is sufficient to have
first; the second term will be included in the RE term and
A(x", xx) +
Σ j.P. F
Be.l x) +sl S cd
(J.4)
2
38

---

By the definition of Br, in (.2 and Lemma
K.3
we get
2 Lmnax
2 min
{16p;, } Lmax In
2
B = 2/ Tt
In
(1.5)
dd.T.
2
T.
8d.r%
Lemma K.3. Iftbe.j Pt.j. then
1 Veg I min { 16ps, 4
Therefore, in order for J.4) to hold, it is sufficient to have
Σ
5
2 min (16p;, 2 Lmax
In
2 dd.
A (1), + cd
xx)" +
2V
j.0 Pe,
2 In
1
A +
Σ
min 16p;, 4 (1)( + + Scd
T Jd,Te 1-
2
2Tmaxx
N
A(x", +e
V
T dd.T.
In
min
16p;. 4
+el cd
2
j=1
( =0 (HDD((Z2,22)
NHDE( x)
T, E HDE (Fe, x)) In
8
where čạ
RE Term By the definition of & in
1.2 it is sufficient to have
25 Lmax
2
A(x", ;x) +E
In
S Cm
Ti dm,
2
KNL
KN te
cm N L
A(z*,a)+
N L In
T
In
0
A .)
8
A(x* x) +
400 2 where C.
In 400v2
cm
cm
By taking C. 3. Ca and cm 5. the upper bound on Ti can be concluded as
6400 In 6400 d In (A(x* x) + s)²
Kd/ (A(x", + =)² + 6400 In 6400 HDE( x) In NHpg (x., x)
8
3200 In 3200 2. N Namax +
KNL
In
2)
A(r x) +E
8
d
Kd/ ((xx", x) +e)²
In
(A (((ttxx) .x) +))²
8
KNLaxxx
NHDE(Ee,
NLmax In A(x*, 2x) +e
Al," ,2)+
+ HHDE(TE, x) In
8
5
= (A(x x)) + t))²
d
1 In + H (Ze, x) In 3
NLmax In
+
A(x +
Step 3:
Theorem 3.2. Define the context distribution estimation (DE) hardness parameter
L Luax
HDE(x,, = (A(x* + 8)
H xx)
39

---

where (ze, 2 j=1 v min {16p,, Ay + =l)² Under Assumption
1 with proba-
bility at least 1 8, PS:BAI identifies an e-optimal arm and its sample complexity is
d
1
N Nmmax
max E,EA,
In + HDE
x) In
+
In
(3.6)
(A(x", x) + aF
8
A A x)) +E
(v(
Tb(ae,))
Ta(x)
Proof of Theorem 3.2
By Assumption | and the choice of the parameters, Lemma
G.4 indicates
Good guaranteed with probability at least
Note that some arm pulls are not counted in Ty:
In every y time steps, Algorithm 1 enters the CD phase select CD sample.
When a changepoint is detected, Algorithm Tearithmmsteee steps into the CA phase, where wi arms are sampled in Algorithm|4 (4]
During the CA phase, we abandon MT
samples.
Therefore, when t is large (or after the first stationary segment)
Jamin t s T. 7 Lmin why
7
? T Linin
T:
(J.6)
3wy 7 7- TTmin 2
As 7 and wry set to be upper bounded by Lmiin so the fractions above is upper bounded by an absolute constant 4, e.g., with y and w م the constant is 4. Therefore, is of the same order as T, By Lemma G.6 3.6 holds with probability 1-8.
K
Analysis of PS:BAI: Technical Lemmas
Lemma K.1. Given any j [N] and T, > 21max In 2 Bes S Br.g.
Da.Te
Proof of Lemma
K.1
Recall
Φbj min 4 { (ps:
25 Lmmx In 8d.
2 1
prss
4
T.
'
The proof is scheduled in 2 steps.
Step 1: Upper bound
2p, (1 p,
Tinns In 2
T.
When Lmax 3T.
da. 1
2p,( D,
).
we have
Te
3a.r.
5
2p;
Tamax Pÿ
2
Bij
In
T.
dA.
As Pj (1 pU) < 1 Vp, E (0, 1). this naive bound gives Brg S
5 21
2.
Tmmax
In
If Ti > 0, according to Lemmal K.2
5 2/
2p pú))
Lumax In
2
B
T.
dd.T.
2p, Di,sT.s Lmax
2
In
2V
TiTis
8..T.
5
2D., Lmmax max
25 Liax
2
2
1,
In
In
Tr
Tej
54,T.
40

---

thus we have
5
201. Imnax In 2
Bag
(K.1)
2
Te
Sd,T.
Tr O, i.c., the latent context j has never been observed and Pt.j
have
2p, Pi)
BBs =
In
Ti
ōd,7.
5
2 (1- BB, Lmax In 2
- 2
Tb
Öd,T.
Lmax In 0d.72
25
L Lmax In
2
(t v
T +
25 Tmax In
2
8
Tí
ōd.T. 25
Take the trivial bound into consideration and observe that or min Tí
In da.
11 and that
25
Liax
In 2
25 In
j In
8 T.
ÒA.T.
27:
dA.T.
2
Tr ōa.T.
Thus, K.
also holds for Te, = 0.
To conclude, we have
5
Limax
2
2p - Pÿ) -Pj) Immx In
2
Bes max
In
2
3T,
8a,1. V
8d,7
5
LImax
2
20r., Lmax In
2
2
max
3T,
In
V
Ti
8d.
Step 2: Simplify the bound. Recall that
{ pess 4 T.
25 Lmmx In
2
1
Dtjj
min 4maxx
Sd,
As Tg 2 2bmaax In 2
we have
9 60.
Tamax
2
2 Lmmxx
2
S
In
5d.7.
Te
8d.7
According to the definition of Φs if Pt.j
Luax 1:
In have
6a.
Lmax
5v 2L2mx In
4pr. Lmax
2
In
S
In
3T,
ōd
da.T.
To
dA.T.
Pr.j S
25 Lmpax
In
we have
4 T.
Ka.r.
Lmax 3T,
2
25 L.max
2Lmax
2
Lmax
In
In
In
25
In
84.7;
To
8d.
V
dd.
T,
8
Thus
Lixxx
2
20r,, Linxx
2
20r Lmax
max
3T:
In
JA.T.
V
T.
In
Sa.
T
In
d
This gives the desired result.
Lemma K.2. When Beg V/ 2p; (1-p) Linos In dam
2 and T2. 0, we have
Pi max {
{1,
25 Lmax
2
T Te
16 T
JA.TT
41

---

Proof of Lemma K.2
Pj
PsTe
Te.
Te.Ti
Pi. Te + 3
5.
2p,(1
P5) Te In ka.r
Te.
1 5 Pj
Pj
2Lmax
2
Te
4V
Tτ.j
Tt.j
Tt.
Te
5d.
Pj
25 Lmax
2
Te.
Te
max
1,
16 Ti.
In
8d,
Lemma K.3. If the = Pr.j. then
1
Ve S min 16ps
4
Proof of Lemma K.3
Recall to the definition of Φi, in and Vhe in (.8.
25 Limxx
2
25 Lmax In
2 Sd.
min
max
Pr.j.
In
4 t/i = max Pe..
4
T.
δa,T. In
4 T.
we have
25
Lmax
2
1
pt.
Dij min 40ras 4
4
Tr
ōd,
We only need to upper bound Pt.j.
By
L.4
Limxx
2p,
Ps
Lmax
Vh.i = Prj S + max
In
In
37.
da.
T,
dd.
8
7 14.5 S + 2
max
Weij 1 Pjí1 - pii)
V..55
75
25
4
= Pý + max
Whij V 2p5(1 - ps5 ps)/bss 15
7 1/.. S 4pj
Thus Pr.j the,j < 4pj. and Φr I min (16p;, 1
L Upper Bound of PS:BAI : Proof of Theorem 3.3
Theorem 3.3. The PSEBAI*
algorithm (e, 6)- and its expected sample complexity is
δ
Tv(x) + TD(x,, 2) + TR(x), T + T rT))
min
max a.E.
Proof. We let Ti denote the stopping time of PS=BAI, 72 denote the stopping time of NsBAI, and denote the stopping time of PS=BAI+ when identical sequence of samples and returns applied to them. By the design of these algorithms, we have
T S min(71.
Part I: Prove that PP & xx) < 8.
Let event & 1(m )2) n1 (P returns arm se when it terminates]. Recall that i denotes the recommended arm of NEBAI when it terminates and & denotes the recommended arm of
42

---

PS=BAI* when it terminates. The design of algorithms indicates that:
c Is when &₁ occurs, and & = - when & occurs.
Moreover, with the performance guarantees BA and PS=BAl(shown in Proposition 3. and Theorem 3.2mm...2mmmm indiiuliil..llly we have
P(i. $ X-1
P(ž & X,| P[E,] + P(ù, $ X.JEf)-
P(re & X - + P( & X.lEf) PPEj]
s à P[& + 8 [P(E]] = 5 (P[() + P(εi) = 6.
Part I: Derive the expected sample complexity of PS:BATT.
We first derive the conditional expectation of the stopping time of PS:BAI. By the same argument as in (J6). T; S < 47, for any t. Therefore, it is sufficient to upper bound K[T,]] and [B[T]] can be upper bounded by ]
According to Lemma G.6 and Lemma G.6 when both events Good and CI occur, PS:BAI terminates
with Tr, satisfying T,, S T, where T is defined in (.3) and as below:
6400 In 6400 d In Kd/ (A(x", x) + +))²
T := He Eee
max
(A(x", x) + +)²
+ 64 6400 HDE x)In (HDE(FE, x)
8
KNL A(=*,a)+
In N LLmax In
A(x 2) +
Given time step with T, 2 2T (thus t 87)), will upper bound P/ t in the following. We firstly upper bound IP [Tr, > Te]. Note that
T 2
Tz +1
[T, > T* P T T.
2
+
P
T 2
2
Ti
Te 2
+ PP
Tm > T.
+1
P
T <
+1 1
TB
PP Tn > T: >
+1
If PS:BAI fails to terminate with Tú < 2 it implies that event Good n (NEEZ Cl,) fails, where
I= :s: 2 +1 < T, < T.}. Hence,
T 2
PTT T P P
TA Te Tr
Tr. 2
< P
Good U
U sE
CIe
< P Good +
Good n
U Crς sEI
< P |Good
flood!+? +P
UCrg NeEZ
Good
(4)
8
Tı Σ
+
(Kō,,1, + NN0T,, KN&
2T
T.=T./++1
(h)
Te
T: 8
8
38
+2 2
+2
dr
27
5T
27
T//2
5
27
5T?
T
T,=T//2+
43

---

where (a) is obtained by applying Lemma G.5 to time steps in I n Tp (i.e., the Exp time steps in Z) and note that there are most two time steps ti tz with In Tτ due the reversion step; (b) is
derived by substituting Se,T. 15KTę 6d,T, 15NT? 8 15KN2? which are used to define
the confidence radius in 3.3 By using the fact that 47, 2 Tı, for any T. z 2T' we have
0
36
P m
4T
S
PT
>
T
+ 5T?
2r
5
38
P
47,
+ +
i i 0, 1,2,
2T
5T?
488
VST <IST.
2r
5(t
4)2
This indicates for 2 87, the probability that PSEBAI does not stop after time steps is 2+ + 5(1-4)2 Therefore, by Tonelli's Theorem, we have
488
B(m/87 <n ST)S Σ
Plm
> 4
Σ
+
2r
5(t
4)2
t=87
(=87
488
1+
dl
2.
(L.1)
5(1
4)2
Next, we bound Er, the expected sample complexity of PS:BAI+, Er can be decomposed as below:
Er E 8/ + E|T/8T < STST + E[T/T > r"}.
(L.2)
Since r = min 12) and Pfmin(71: m2) > 1) P/n > 1] for all 4, we have
B|rlST <TST"=
Σ P(r 1] Σ
Pimin (11, 1]
t=x/
t=
Σ Pln < >| - 87 51 S <*'.
(L.3)
t=8t
Besides, since PS:BAI will terminate after 7" time steps, i.e., P(Ti ST¹) = 1. We have
B| 2T|] Σ 1 Σ
Pl 2 = 1 + E/22/22 > >T
(L.4)
t=
Lemma F.1 indicates that P(122 2 t 1 (a- (22 for all t 2 To. where
5
To 768(8Lmax + 25d) 768KCc(8L, + 25d)
C3
(E + A Amin)²
(e Amin) '² 5
Since the order of To is apparently larger than r", have To S r" Then, with the same method as in the proof of Proposition 3.1 the conditional sample complexity of NeBAI can be bounded as follows:
+00
dx 8
<
P(12 2 x)) dr <
(L.5)
(a 1)Ca(z/2)²
Ogr*
Substituting terms in with
and
L.5)
we have
Er < 87 + 3 +
Cz
Besides,
(a)
6
Er < ETg
S To +
(a - 1)(a - 2)(6/22)a
Where (a) is shown in
44

---

Altogether, we have
8
δ
Er < min 8T 3 +
88
+
OzT*
C3
M Analysis of Lower Bound: Proof of Theorem 4.1
The dynamics for under our PSLB model is displayed in Dynamics
Dynamics Dynamics for piecewise-statioary linear bandits
1: The instance: A (X, θ Po: C)
2: while the algorithm does not stop at time step t do
3: if' & E C then
4:
The environment samples Oj. ~ Pa
5:
else
6:
0r = -O,,, (the environment does not change)
7:
end if'
8:
The agent samples an arm 2; based on the history up to time 1.
9: The reward Yt,x, = x 0J. + Te is revealed to the agent.
end while
11:
Recommend an E b-bett arm f...
To derive the lower bound in Theorem we investigate two environments different from the one defined in Section 2 (and as in Dynamics
Dynamics 2 the agent observes the index of current context jr. and the environment reduces to contextual linear bandits; the definition Dynamics and the lower bound under are detailed in Appendix M.
Dynamics the agent observes the changepoints in C and context vector 0%, 's, and hence she solely needs to estimate the distribution of contexts; the definition of Dynamics 3 and the lower bound under are detailed in Appendix M.2
We first derive a lower bound for (e, -BA algorithms in Dynamics 2 that is, in contextual linear bandits.
Corollary M.1. For any (8, (e,C)-PAC algorithm there exists instance A (X, O, Po.C) with Dynamics such that
E[T] 2 (A) log 2.48
N
(x Tx 0,))²
where Te(A)-1
max (vyEAx)) i (EAlee(
min
Σ
Pj
Uj
2
j=1
FEX
is defined in Theorem 4.1 In addition, when [e =
Ej 131|1=" - 10l A(15)(1))-1
(A(A)
min (uyEAx
max zyta
(A(x", + +))
This lower bound generalizes the result of [16] to the linear bandit setting.
We next study Dynamics In this setting, the agent solely needs estimate the distribution of contexts Py with context samples. Once the agent obtains a good estimate of Pg. she can identify an e-optimal arm w.h.p. Hence, the lower bound on the complexity of (e, ()-A algorithm is the product of the minimum length of stationary segment and the minimum number of context samples/changepoints needed for distribution estimation.
Corollary M.2. For any (e, PPAC algorithm n. there exists instance A (X, O Po, C) with Dynamics 3 such that ET 2 CNe, where eN is the Nthh changepoint in the changepoint sequence C.
45

---

Altogether, the sample complexity of an (e,6)-BAI algorithm in Dynamics 2 and build up the lower bound Theorem
M.1 Lower Bound for e-BAI in Contextual Linear Bandits
In this section, we consider a sub-problem where the index of the current context J: is revealed at each time step t. The original secceiss-sstaiinna problem becomes contextual problem whose dynamics is presented in Algorithm 2
As more information is provided to the agent, the lower
Dynamics Dynamics for contextual linear bandits
1: The instance: A (X, θ Po:C) C)
2: while the algorithm does not stop at time step / do
3: if' E C then
4: The environment samples 0z, Pa
5: else
6:
0j. -O,,, (the environment does not change)
7:
end if'
8:
Reveal Je the agent.
9: The agent samples an arm 2s based on the history to time - 1.
The reward Yt,,, = z 6J. + ne revealed the agent.
11: end while
Recommend an g-best arm fe..
bound for this sub-problem is smaller than the one for the original problem. Corollary M.1. For any (E, 8)AAC algorithm x, there exists an instance A = (X' Po, C) with Dynamics such that
1
B[T] 2 Ta(A) log 2.48
N
(x (07 0)))
where TE(A)-1=
max min (m)EAx) MEAle (A)
Σ
Pj
2
5=1
BEN
is defined in Theorem 4.1 In addition, when [Nel 1,
Σ/ Py 1|2" - x11A(11))-
(A(
min [.
max zF
(A(r" ,,*),)) +)²
For simplicity, consider the noise model is the Clipped Gaussian Distribution CN i.e., 1) ~ C1)(1) or P, CN)
Definition M.3. random variable x follows the Clipped Gaussian Distribution with parameter a, denoted by (o), if has the probability distribution function
x.2
f(x) (20(o) - 1) V2TØ"
exp
Va E [-11]]
20
where (xx) is the cumulative distribution function of the standard Gaussian distribution.
Some notations are introduced here:
Given an instance A = (X, O Pe. C), define the alternative instance A' = Pa, with respect to A, where O' = (B'...., 0y,)) E Rd N and Pe [6%] = Po Po107] s.t. there 3r X Xe. Vxg E Xe, s.t., _.T...EE Egr-Ps < <x TT - E. We denote the set containing all the alternative instance (W.r.t. A) as (Ate
H4 = (Xi, 1a))) 1--1 is the observation history up to but not include time L.
is the number of times arm in which x is sampled under context j. And N2(t)= = Ex Nz, (t) is the number times in which context j appears.
(t) Σr - 1[r, I.J.
kl(p.g) g) = KT. (Ber((()))) Bern(q)) is the KT. divergence between two Bernoulli distributions with parameters p and g.
46

---

Therefore, the probability of the observation history Me+1 = (I V x Jo) is
11-1
PRA (I Y Then the log- likelihood between the two instance up to time t, given the observed data, is L (1.ss Vo..an
Je) 11
Polo
II
a Hot (a Tatte ja.
==0
Px
(I :2)
log
PFN
(Ios Y Na [8) 1
I PolB
1==0
T [T +o ( P P(Yc |aatss (7
(a) log
I Po 10'0
Li-1
(T +s (Hats P(Y (oaa+taaattt Feat O' 17
I1 -
x )r,) I Pr 2 (
Py
log
4 La-1
exp(-nneyt exp(-nex+s/2)
log
exp( (app--(leett (Wle 2///2)
-Yasto - T )2 +²+ (Y (Yttoaat 2
t=1
Fe 0jg (2 + T tatt
2
where (a) utilizes Po(o; Pe Po (b) makes use of the relationship between the arm and observation and in (c) 03., = 0f 0/2- Thus, the expectation of the log-likelihood is (in the following, the expectation is taken under instance A and algorithm m)
4
TT vT jug (2 + Neyts
B[Lc] =
2
JJ. Te a Dieg
E
8=0
14-1
F
Σ
Ne Nertstert ttts
Ojn
Jap
N (Detts 2²)
4. fiat =
4-11
Σ FEX
Σ
Σ
ST
Σ
TestoTeett Dim
jq
j=1
1=1
o=0
5N U. xx To,
2
2 ZEX
1=1
(N) E
E EN J. (t) ([N,( #ex
F
Σ
J.. xx To,
(M.8)
As the lengths of all the stationary phases are upper bounded, i.e., La S Lmaxer Vl E N, then by Wald's Lemma,
E
(N)
E/ [07]
Po[07] = Pj
(M.9)
E
E[J]
47

---

The above also holds for t = 7 where is stopping time. According to Lemma 19 in 31
E [ 2 sup kl(Pax]E), (a))
(M.10)
EEF,
where F, (HH In addition, let ع {the recommended arm & & Xe the algorithm is 5-PAC, then
[+]) 2 kl(1 - -6,) 2 log 2.48
(M.11)
From
M.8
M.
M.10
and M.II
we conclude that
E (T) [[N
1
B(r]
Pj
of T0, 2 log
2
2.48
j=1
ZEN
(T))
(EAlta(A)
min
2
E
P5
E[N,(T)]
03 xx. T0 2 log 2.45
==1
EEA
N
max
min (A)
[[[T]
Σ
Σ
Tzzz00 xx
xx 0j 2 log 2.45
[1,EAx IN
2
j=1
ZEX
Elr] 2 (A) 2.45
where
1 T=(A)-1= (1,6Axl MEAlta (A) 2
min
Σ P3 j=1
0z xxx" 0z. ZEX
Σ
The solution to the above optimization problem is in general intractable, even for the stationary case [32]. We can establish a connection of the above problem the stationary g-best identification problem in linear bandits when we assume the change of the latent vectors are the same, i.c., 01 ..... 0NN
M.1.1 Connection with the Stationary Case
In the alternative instance (A)) 3z E X \ Xxs for any arm x, E X, s.t.
N
ToTT Σ Ps 03 4 < Σ
Dj T
(M.12)
1=1
Σ Py(xx- - =2 +E<0
N
Σ Py(Ze - T0) + Σ
pイ - x) >
Σ
p xx) T0 +
1=1
j=1
1=1
N Σ
N
Py(ee= - T) >
Σ
pf( - =x)T0 + A(ze, x) +
1=1
1=1
Thus,
AAte(A)
N
(x,
3x E X Xx,
Ep, - =) > A(ze,t) + + Vas E Ne
1=1
Define resttieettd C Alte(A), with the additional constraint that 0, = 00 =...=A! =dx- Then
have
Alt(A) Att(A)eestricted restricted
48

---

(x, (x: 03 d1, 3r X X, Σ (s A(Ee, s, Vee E Xs
Note that in stationary linear bandits, the instance can be characterized by the arm set X C Rd and the latent vector 0 Rd. Define the alternative instance in linear bandits [32 for the instance (X, Ra () Alt((X' Eg 8) sttationary
{(X 8¹)) :0 = EaNPo 01. (Ie - x)) Tu > (Ie - x) EanPo + + Vag E Nz}
Note that
max min 1x A= (AAlte(A)
[5[T] Σ Pj j=l
Uj xx Joj
TEA
min {or (Ax)) M (EAlt(A)
max
Σ
py
1
DEA
jml
"EAx (A) cewstrinted 2 B
max min
Σ 2,200
max eE A'EAAI((X. Bo ()lesattonaayy
min
B[T]OT
Σ FEX
01
other words, the max-min problem becomes the one for the b-best arm identification problem stationary linear bandits. According to (2). the solution to the last optimization problem above is in general intractable.
where in (a) we denote 0 ;= Σ P Py as a mixture of {uy)
However, the optimization problem can be simplified under some simple cases, e.g., the set of e-best arm is a singleton [32). In the next subsection, a lower bound for the original problem with X₂ being a singleton will be derived.
M.1.2 A Simple Case: [Xel =
Assume that the set of s-best arm is singleton, i.e., X = f0"}, we will solve the original optimization problem:
min MEAlte
Σ P3
Σ
T 0, xx 02
2
j=1
we extend the procedures in (1] to the piecewise-sttaionnayy setup. Lemma M.4.
N
To, 2 min (A(x", ,x))
Σ Pj
Σ
min (AA
2
2 az
E/= 1/ - x x112 =((
j=1
Tex
Proof. Note that A' differs from A in the context matrix O By the derivations in M.12 there exists arm x # x², s.t.,
- -x) > A(xe, +e
Therefore, the optimization problem becomes
N
1
min
P
Ui ] xx xxTT) T0,
19
2
j=1
TEN
N
s.t. REE {x*},
Σ
Pj (xx - -x) > a(x",))+e+++ (xte(x", (M.13)
j=1
49

---

where a > O. The Lagrangian function for this problem is
N
I(O1.....,NN.
1
_
Pj
Σ
xx T 02y + A(-
-z) -z) Aatele" ,2))
m
Then
aL
Σ
UjaTt' 0, >pp - z) =0 + A(v;)1120, = -AA(1))-1/22 -1/2()) - x)
+ Pj
00;
ZEX
0L
N
0
Σ
Py(a* -x) =0) =o+tex"'
0x
j=1
This indicates that
N
N
Σ
Σ
Pj (10011130ss)) Ujz0 xx xxxT0; Tou Σ
Pj
j=1
ZEN
j=1
Eg 1 Pil (o:lA(rs))l<** - }
2
Σタ= wg - x1l((ces)-+
2 Σ)= j=1 (,0 x2) )
(x*
j= Pj Pý||æ* x=1 =1(2(01))-
(Aa+s(I" xx),
Pÿ Pp||=* =x113 =112((15)~>
Let a - 0, we have
N
(A(x* xz) + x)²
Σn, Pj
xx 05
T
0j 2
Σ N
Σ== Py || - x =112(1))-1
j=1
#EX
Due to M.13). we only require there exists + x², such that the constraint is satisfied, therefore,
2 min (A(z" =E) 2 xチzz"
1
Σ Σj= Ps x ((A(s)))
By Lemma M.4 the stopping time can be lower bounded as
Σ/ 1/ x A(w))) max E[T] 2 2 log 2.45 (oyEAx) afx"
1
min
(A(x*, x)) + 2)²
This lower bound indicates that, (1) good algorithm should actively detects and makes use of the contextual information to facilitate the arm identification process. (2) our lower bound extends the result of [16] to the linear bandits case.
The above lower bound can be further lower bounded if we restrict Vi _... UN.
Lemma M.5. Let SPD(d) := (A: Ae R A > 0} denote the set of SPD matrices of dimension d x d. Given any Rdd define the function f (dD((d) TR, f(A) = x A-1x, then f is convex.
Proof of Lemma M.5 Given any A, B E SPD(d). define
g: E R: A IB E SPD + R. R()(() = T (A 1B)
suffice to prove g is convex.
g'(1) = xx T (A + ((A (A B(A
B(A g'(() 2x (A tB) B(A tB) B +
+B)
50

---

= (A++ (BIA+ 2 0
Therefore, is convex.
Given Lemma M.5
we have
N Σ
N
ps psll=* - x =lla(1=)) = =xx" -x)
Σ
Pj PjA(w))
(x*
==1
-1
2 (x -x)
Σ Pj P}A(1z)
(x* -x)
N
(0 - 2²
Σ
Pj
Σ
Uj
(x* x))
/=1
DEN
(x - =)
Σ Psu
xx
(x* xx)
MEX
(x x) (TT) (x" x)
where ú = E= Pjuj / x and the inequality becomes equality when 11 U/a Thus,
E P,ll=" xl1 x112(10))11
1
B[T] 2 2 2og
max 2.45 (e,EAx) afa"
min
(A(x*, + z)²
||= = min max 2.45 e sfæ"
2 2 2og
(M.14)
(A(z*, x) + +=)²
The last term mimics the lower bound in the stationary linear bandits with the latent vector Eg~
In addition, if we let P1 = 1 and Pj for all j * the instance, our lower bound can be simplified to the lower bound in stationary linear bandits with latent vector 03 24
ΣS pill= - =
E(r] 2 2 log
min max
2.45 (e,EAx)
axt""
(A(x* + =)²²
1 min max
||2" x 2112(1m))2
2 log 2.45
(M.15)
wY oFE"
(Ai x)) + E)
M.2 Lower Bound the Number of changepoints
In this section, we consider an even easier problem: all the contextual information is known to the agent, except for the distribution Po. The dynamics displayed in Dynamics
Dynamics Dynamics for an casier problem
1: The instance: A (X', θ, C)
2: while the algorithm does not stop at time step t do
3: if E C then
4: The agent acknowledges E C.
5:
The environment samples 0), ~ Pg
6:
else
7:
8 = 07
(the environment does not change)
8: end if
9: The agent observes 0
10: end while
11:
Recommend e e-best arm f..
51

---

We are going to consider the alternative instances with respect to the distribution on 8, i.e., A' = (X, O p.. C). where Ez X' Xe. Vx, E Xe s.t., 2g Eu-Py x r"E Ep-r; E. Denote the set of all the alternative instance (w.r.. A) as AA),(A), According to the Pinsker's inequality, let E = {the recommended arm &e & x, then for any ô-PAC algorithm x,
PRA + 1RA 2 2 exp (-KL( 46 2 exp (-KL(PRA Pa, AA' E (A)
VA' E (A))
(L(PAA, PFN) 2 46
AA' E (l)
1
min (AAlI)(A)
KL(P+A PAA))
In
46
1
E44
min (AEAlte(A)
KL(Po, Pb) 2 In
48
E4 min (P,, Pb) 45
In
(M.16)
We will give an upper bound on the denominator. Note that
min (A))
(T,(Po, Pb) min min KT. (Po, Pg) =EXiX AS
(M.17)
where A, is an alternative instance with distribution PT s.t. x Bg 0 - > x Ba 0, Vx,
N
Given any x & Xx. we denote the shorthand notation Lj = Po(0)] We have
Σ 9 (x, 2 E + a, for any a 0, ag E X
Fix > 0 which is sufficiently small, we have the following optimization problelm:
Σ Pj
In Pj
min 9
N
4j
N
s.t.
Øj =
j=1
N
Σ
qj (FE,) + 0, E X
j=1
If such alternative distribution y exists, let L denote the augmented Lagrangian function
N
E(g, X, (aaxs) Σ
In
Ps
A
Σ qj 1) + Σ (t +
qj
j=1
C.
By the KKT conditions, we have:
aL
Pi
X
Σ =) Vje
(M.18)
0g;
4j
Z.EN
0L
N
9 -
-1=0 0
0x
j=1
aL = Σ
N
&
0re,
1=1
or >r, for some Ee Xe, which indicates some conditions not satisfied. The equations
above give
Dj 4j = 1+ ex, da, (A, + +c+a)'
Vj E [N]
(M.19)
52

---

By solving
Σ 1+ Exex. Xz (A, 2) + + +
Pj
1
(M.20)
which is a polynomial with N degree. Thus, an explicit solution for any instance not applicable. However, there are some cases where we can get estimate of X
Lemma M.6. Denote ju = arg JE((N Az(x", x)) and ji arg jE[N] Ay(x",2) z). When
[x_ = 1, Ao (x"""² x) 2E > An (x", x) > E and Ej= Py(4) x) + + a)² S 0, the solution
to M.20 is upper bounded by
A x) +
Ey (x+ (,)===))====>0 + aa)²
Proof of Lemma M.6
When the s-best arm set singleton, M.20 becomes (where a sufficiently
small)
Σ
Pj 1+ A (A,(2* x) + + -1
1=1
As M.19 a probability distribution, we need + Am (Aio (x x) + e a) 2 0, which indicates
Az. (z 2)(=a))+++a
+)+s+a By the condition on jo and jı, 2 (A, A,(x" .x) + a) 1, Vj E [N].
Therefore, by using + x
for |a| < 1, we can expand the equation as 1t
follows
Pj
1 A (A) ac
j=1
N
2
Σ
((1 - Am ( + (A +e++
j=1
(Az (A)((1, (++"x))++++)))))
N
02 Σ xT) Ar- (0)()
j=1
5=1
N
Σ (2 +
1=1
j= Py (x +
Ax2" x + a
A
5= Py (4, (x 2)) 2) a) jj= Pj ( xx 2) +
In general, when we get the {Au, Iaexx and plug it in (M119). the alternative distribution q is obtained. Finally, we let a + 0.
This gives the lower bound for the number changepoints that need to observed. coarse estimation of the KI. divergence without solving (M.20) can be done as follows
Σ
PJ In
Pj Pý In
Σ
+
Σ An, (Me, +0) E.t
4
Pj Σ
X (2) +
3
T.E
Σ
AM. (A +
53

---

Note that the solution of Xz, depends on A(re, 2) (e.g. Lemma M. so the final solution is of order (A) for a given x & X. This the solution to the inside minimization problem in (M.17).
The final lower bound will be
min KI(Po, Pb) = min min KL(Pee Pg) (AA
ZER' As
S min Σ
Xa. (2 x) +)).
zg FpEd
The lower bound is
1
B[4] 2 max a
x) + In
2x, ex, Aoo (A (A
40
where Xx, is the solution to M.20).
With the setup in Lemma M.6 we have
min (A)
KL(Po, Pa)
min min (Po, Po)) x Ar
(A(x*, 2)) + =)2
min 2f
N Σド=1 Pj (A, (x ,x) + +)
and the lower bound
N E (y ,2)
1
ELJ
max zfZe
In 48
(A(x* + +)²
Remark M.7. We give some comments on the existence and uniqueness of the solution to M.20 Existence:
It is possible that (M.0 does not have solution. For instance, consider three-arm instance: T(1) = (1,,.5), I(2) = (0.5, 1), x(() = (.6), (1,0),05 = (0, 1), Pa (0.5, 0.5), 0.1. We have I(t) Eg-Pr = I(2: Eg = 0.75 and I(3) 'g = 0.6, thus T(3) is not an
e-best arm. Furthermore, there does not exist alternative distribution q. such that 2(()) is the
best arm and neither 2(2) is e-best. Under such case, the lower bound [[(]] is 0 (we regard minzeo fxx) +00 by convention).
It is possible that (M.20) does not have solution and is unnecessary to estimate Po. For instance, consider two-arm instance: T(1) = (1,0 x22) (0.5, 0.1,,,0))00, 07 (1,0), 03 (0, 1), Pe (0.5,0.5). = 0.1. Arm œ(1) is better than arm I(2) under all contexts. Therefore, no matter what Pg is, arm I(1) is the e-best arm. Under such cases, there may exist an algorithm and is sufficient for it to determine the best arm if the context vectors are well-approxmmated. There is need to estimate Po-
A necessary condition for the existence of the solution of (M.20) is: there exists x & Xe, for any other words, for each e-best arm Teg there is at least one context in which the alternative arm is better than Kg by at least E.
Ig E &Xg, there Bj(x,) E [N], j.z.A)zz.) x))
-c. <c.
A sufficient condition for the existence of the solution of (M.20) is: there exists x & Ne and j E [N]. s.t. ,,,,,(x,))) < -E, Vxz Xz. In other words, x is better than any e-best arm under context j. In the alternative instance, we can lift P/ 1871 close to so that arm x becomes the E-best arm and
X n X= =
Uniqueness:
The uniqueness of the solution is not guaranteed, as the KKT conditions (.18) is only necessary condition for the solution. We need to look the solution that minimizes the KL divergence.
A sufficient condition for the uniqueness of the solution is (if it exists, which indicates 3j
[N], s.t.A; (x=xx)) < -E): [xl Specifically, denote f(xx)) == EE I+A.- s)+eto)
we have
0f
-1 Ag- (A (x +E+
1 A,. ( (x+ +8+a)
j=1
54

---

f
N (A,(2 + + a))
2x
+ Am- (A,(*,, +
j=1
As f(0) , a1
8² 0, there is exactly solution Ax- 0. (0) -1 and
DA
xx
N More Examples and Details
In this section, we firstly provide one more example to illustrate the tightness of our derived upper bound lower bounds, indicating the efficiency of our PS:BAI* algorithm. In addition, can observe how the upper and lower bounds are affected by the level of piecewise non-stationarity and whether our PS=BAI+ algorithm can reduce the influence manifested by Lmax- After that, present a proof sketch of the results in Corollaries 5.1 and N.11 in Appendix N.I
Example Instance A (X' O Po. C) is with
d arms: z(t) = =,, E [d].
N = d confexts: 04 = (a,, 0, 0, O0), 0 = (a, b, ....b.b................ .)......TT -bej.j 2 2, where b > >
E, b a > E
Context distribution: Pj = P.j 2 and = = (N - 1)p, where E (0, (N-2)5)
Under Example have
((r()) (1 (N 2)p) (N 2)p (b (b- a)
((() = - - a -E, 12 2,j+ #
Thus, (1) ((1) is the unique e-best arm; (2) {
equivalent, and A (Z)()) (3)
for any i 2 2, (()) can an e-optimal arm under some alternative distributions.
Corollary N.1. Firstly, for the instances defined in Example 2
we have
16(N - -2)
HDE
(a (a+ (b ab-a-
(Amin +)²²
and the sample complexity of the PSEBAI+ tight up to (N NTmaax/ Tsmin) and I We also further observe some specific instances: (i) when p 0+, with Amin min axx", xx).
we have
E[r]* In(1/8)
E c min
d
NLmax
Lmmax + d
+ Amin + (Amin + +)²
(Amin + s)²
Lunin (b - a - E)
n max
(Amin + +8)²
Amin +
(ii) When p +
a-c)
and (a + E)2 + (b - =)==) we have HDE =1(11,
N.max
[N-
(A())))
and
El7]" Ō
c0(min min HDE, d + Imax
})
d++ Imnin
ln(1/5)
The upper bounds are achieved by the PSeBAI+ algorithm.
We can observe from Corollary N.1 that
case (i), when p - O-, P: (N ()--e) and Pj
and thus the instance tends
(N-2)b
[N [N-
to be non-stationary and Amin We will obtain
Er
d (Amin + 8)2
E θ
ln(1/)
indicating that our algorithm can also reduce the impact of Liaxx
55

---

In case (ii), the upper and lower bounds are with the same order, and the difference is solely manifested by a additive term Lmax min, suggesting that PS:BAI+ is near optimal and again. PS&BAI* mitigates the impact of Lmaxx
N.1 Analysis of examples
Recall the instance A = (X, O, in Example 1
Example 1. Instance = (X, O C) with (i) 2d arms: =(1) e1, (() = ei, J(dti-1)) =
ej cos @ c2 sin o for all E (2.....d) d} where E [0, x x/4), (ii) 2d 2 contexts: 03+ = e1 cos
Cj+1 sin ó for all j [d - 1], (iii) Context distribution: Pj 1/N for all j E [N]]
Corollary 5.1. For the instance defined in Example
we have (Te, x) =
for all
(Z), E Ng x (X') Ng). In addition, if < (cos cos Φ). we have
_ ((L+ (Arn) +E)2
d
(5.1)
In(1/6)
where El[r] is the minimal expected sample complexity over all (c, 8)C algorithms and f R - RR satisfies f()) 0 ++ The upper bound in 551 achieved by PSEBAI+.
Proof of Corollary 5.7 As (ra) cos Φ), (o(()) 0, Mz(tt) = cos² & for 2...., , d and & E (1 cos o, cos Φ), T(1) the best arm and r(i). = 2, 2.... are not e-best arms and F(ate), i ,....,d are e-best arms. Amin = cos Φ - cos² Φb.
When E < cos o - cos? o= Amiu. 2(1) is the unique e-best arm. By solving MM.14), we see that there exists a continuous function f()) such that f(Ø) - as @ + 0 and we can get the lower bound for the VE term
Ω (1+
A (z x()+1)) + =)² In mn²²)
(N.1)
As ( - x
for i 2, d. E |d 11, z(i cannot be an e-best arm under any alternative distribution, we only need to consider ((d+i) i = ..... any F(a+e), by solving (M.00). we can upper bound
...,, d, which are equivalent. Given
min + sin
Xara -(A+ (F()) + (2) (d))) +e)
and thus the number of change points or context samples can be lower bounded as
B (E (d- (()))) (
+
(Amin + + sin? Φ) Amin +e)
(1 - cos ò {1 + cos 6 - cos o + 1 cos @ - O(1).
(Amin + sin? (Amin + +e)
Amin +
According to Theorem
3.3
the upper bound is
N L 8 A(a()) +E 8
1)
(A (A(z()) (((+1)) + E)² 8 + HDE(A
d
+ N In Amin + 7
1
=
In g
+ HDE(A( m(n))
A min +e²²
where
16N Lmmxx
3 2> 1 - -cos
HDE (A(((()) =
16N Lmaxx A + + 2(1 - cos (088)/NY3
< 1 cos ②
(Amin + E)²
As Amin = cos cos" 0 = cos o(1 cos cos@), Φ), thus 1 - cos Φ HDE(A(Z1), < 144N for any choice of e.
Amin cos
< v 24 min. and
56

---

Hence, the upper bound is
d
1
N L 1 8
E =
In + NN N.NNus
In
In
(A + E)2
8
8
Amiu + E
d
NTmax 1
In
+
In
(Amin +)²
8 Amin + 8)
As Φ - O, the first term (the VE term) dominates and it matches the lower bound in (N.I) Therefore, the upper bound is asymptotically tight up to logarithmic terms.
Corollary N.1. Firstly, for the instances defined in Example 2 we have
16(N - -2)Lmax
HDE
(a (a+ (b- (bb-))))
(Amin + +0²²
and the sample complexity of the PS&BAI+ is tight up (N Lynax/ Lmmin) and logarithmic factors. We also further observe some specific instances: (i) when - 0*, with Amin = min (xx", x),,
we have
E|r]* In(1/8)
E min
d
NTmax
Timax + d })
+ Amiu + (Amin + =)²
(Amin + +E)²
Lunin (b a E)
n max
+8)2² (Amin=t)²
Amin +E
(ii) When p +
a-c)
and (a + E)2 + (b - a - =E) -2(.. we have HDE (A(())
N.
[N6
and
Eir]* E Ö min {
HDE, d Lmax ))
d Luuin
ln(1/5)
The upper bounds are achieved by the PS:BAI* algorithm.
Proof of Corollary N.1 Under Example 2 we have
A (111)) (1 (N 2)p) (N - 2)p (b -b-a0 a) >
A,(r(), = b
-E, 2.j 1,
Thus, (1) 4(1) is the unique e-best arm; (2) ( are equivalent, and Amin = A ( m()): (3)
for any i 2, (()) can be an e-best arm under some alternative distributions.
For any 2 by solving (M20 with v. Z(1), x I(i), obtain AEEA alternative distribution
(b+s)(b-a-s) and the
Pa10
Pj I+ Am
()( +E)
The lower bound on the expected number of changepoints is
(a e) 8)
4
ELL+) Z
In
(A(x ((0 + E) 8"
Thus the time complexity is lower bounded by
(a + 8) (b 8) (A(x)), +
4
In Furthermore, by solving M.14.. we obtain the lower bound on the expected sample complexity when the context index je is revealed:
E
Lmin
1
1 +
1 VddI++1>
E 2 2 log
min max BEAN ##1
2 2 2log 2.48 (1( + e)²
2.45
(A( ((6) + +)
d
1
22log 2.45
(() + +)²
57

---

We get the lower bound on the expected sample complexity:
Limin + E)(b a - 8)
4 In 8
B
max
2
(N.2)
(Amin + 2)²
2.48*
(Amin + +=)²
According to Theorem 3.3
the upper bound on the expected sample complexity is
δ min
+ HDE In 5
1 + Amin +
Limxx + d NLmax In 8' (Amia + +5²²
In 8 }
(N.3)
min + z)²
8
NLmax (a E)2 + (b -a a =)²²
In 1
1
Ò min
In 8
(miin
+ 8)
(Amin + 8)²
N Linax
1
Liaa + In 11) (Amin + E)² 8 55)
In 8¹
A min +
where we utilize
Lmax (Amin +)²²
(mmin 16ps. 2) a + el
min 16p, 1) la + el
(16p,
HDE
2
1 min (16p, 11
+ (N -2
16p, 4/ 3 1bb-0 -el
16(N I
(a +) + =)²
(N.4)
(Amin + =)²
By comparing the lower bound in N.2) and the upper bound (N.3) we conclude that
the sample complexity of PS:BAI+ is tight up to Nimass and logarithmic factors.
When the mean gap is small, the sample complexity of PSeBAI* is dominated by the former term, i.e., the design of PS:BAI.
When p > 0+, then Pı + 1,p;
for 2 2, so the instance tends to be stationary and
A min a. The lower bound in N.2b becomes
Limin - In
[ 2 max
2 2oo 2.48 Amin + 5
(Amin + +)²
and the upper bound N.3 turns into
N NLmax In Lmax + d 1 8 }
ò min (Amin +)) +
Amin + 8¹ (Amin +e)²
The vector estimation term dominates the sample complexity and our upper bound is tight.
When + [N- then P1 + +1
e-e)
(N-1)(a-e and p, +
(N-2)6 so the instance tends to
o-g
(N-2)²
be non-stationary and Amin - E. The lower bound in (N.2) becomes
d
1
Lmmi e)(b
E 2 max
2 log
In 5
4e
2.45'
4e2
and the upper bound N.3
turns into
d In
N NLmax
Luuxx + d
1 11
δ min
HDE
In
In
In
4=2
2c
8'
4=2
where HIEE is upper bounded by (1) If (a++e) e)² + (b e)²
(4c + NL.mx)). DE is independent of e and VE increases e decreases, thus the expected sample complexity is dominated by vector estimation term when is small;
(2) If (a + e)2 + (b a - -)})) 2(1), the expected sample complexity is dominated by
58

---

distribution estimation term. Under both scenarios, our upper bound is tight.
Experimental Details
For the computation of the G-optimal allocation, we adopt the Wolfe-Atwood Algorithm with the Kumar-Yildirim start introduced in [3), where the input the function is the set and the output the G-optimal allocation. All experiments are conducted via MATLAB R2021b on a MacBook Pro with Apple MI Pro chip and 16 GB memory.
To shorten the execution time,
Before PS=BAI stops, PS=BAI and NEBAI are conducted in parallel (i.e., we run PS=BAI*). After PS stops, NeBAI continues and run a batch manner, i.e., we sample Lminn samples according to the G-optimal allocation one time and update the statistics. As the sample complexity of NeBAI is of order least 10" and each stationary segment is of order 10?, the effect of this be largely ignored.
batch sampling procedure
D&BAI and BsBAIg are both conducted in segments, because the latent context vector can be observed by the two algorithms and the latent vector does not change within stationary segment. As the experiment in Section 6 illustrats that PS BAI outperforms N&BAI and dominates the PS=BAI* algorithm,
PS=BAI instead of PS:BAI* for the addition experiments in Section O.2 and Section 0.3
To increase the robustness of the algorithm, the window size for LCD is doubled. Note that this will only influence an absolute constant in the sample complexity the proposed algorithm and the order of the sample complexity remains.
0.1 Modification of Confidence Radii in PS:BAI and PS:BAI+
During the proof of the upper bound, have relaxed the absolute constants in the confidence radii simplify the proof and increase the readability. In the experiments, we utilize the tighter confidence radii gain better empirical performance. Note that when these tighter confidence radii are utilized by our algorithm, it still enjoys the current theoretical guarantee. The choice of confidence radii are as follows:
a according to Lemma L1 and Lemma
H.1 (x can be tightened to be
d
2
2
4d
d
2 8
In
In
In
5
In
T.
S0.7
T
80,1,
Te
8
Te
Bug according (I.) and Lemma K.1 Be, be tightened be
3 Lmax In 2 +
( LLmxx
In
2
2d., Lmnxx In Na.Ta
Gale = min
du.r.
Ta.te
1
Ti
max { Past 4
25 Lmax
2
1 1
where Φr.j = min
In
T.
8a,7, {
& instead of using 25 2/ Lamax In am.r."
we turn bound the residual error by
(.9
T.
alg St.
Σ
gull
Σ
min
4, 2 }
j.aas = Buss 2e.
Σ
10
d
In
2
galg
Tejj
8
59

---

10
PS:BAI w/ == 0.8
PSeBAI
PS:BAI w/V= 1.2
NeBAI
Sample complexity
10
10
1
2
3
4
5
7
8
9
10
11
12
Instance k
Figure Misspeficied Lmax and Lmiin
where
2
Lmax In
Vt.j,1 = max
=max
ph.
In
Wt.jj. = max pi.j.
4T,
8m,
Te dd,T.
žalk St.j
V
d
2
+
4d
S 5
In
2
Te.
8m.
Tei
5m,
T
5m,T.
Tt.j
8m,
zalg is obtained in similar manner at als cals characterizes the confidence radii of each context St.j at a finer level.
These finer confidence bounds can save constant of 2.5 when is large.
O.2 Misspecified Luax and Lmiu
As PS=BAI+ requires the knowledge of Lmax. we empirically test the robustness of the algorithm towards Lmax on the instances 6 We run PS=BAI with Lmin VLLmin and Lmuxx L where / = 0.8 or 1.2. An E-best arm is recommended in all experiments. The sample complexities are presented in Figure 3 The result indicates that PS (thus PS=BAI+) robust towards the knowledge of T.max and its superiority over NeBAI is maintained.
0.3 Robustness towards w and
According the distinguishability condition (Assumption 1b. point (2) indicates we can w Luxin 37
where y the change detection frequency, and (3.5) indicates w and are coupled. We denote Lania
To exam the robustness towards w and 6, we choose to vary the choice of y, thus, w and will change accordingly. Specifically, we select 7 E {2, 3, 6, 12} and the corresponding w {3w, 2 W. @ The other parameters remain unchanged. The experiment result is presented Figure When Assumption severely violated and the result is not desirable.
y 18,
The result indicates that, while smaller and greater w can result in slightly greater sample complexity, the overall sample complexity does not vary much and the superiority of our algorithm over the naive uniform sampling algorithm NeBAT is maintained. We conclude that our algorithm is robust against these choices, long Assumption I is not severely violated.
60

---

10
PSEBAI W/ W/O 3
PSEBAI w/w 0/2
PSEBAI W W/U 2
NeBAI
10
PSEBAI W/ W/U 1B
Sample complexity
10
10
106
10
5
6
8
10
12
Instance
Figure 4: Robustness towards w and b.
0.4 Benchmarks: DeBAland D=BAIg
We present the Distribution E-Best Arm Identification (D=BAI) in Algorithm S and its variant DsBAI, in Algorithm 9 According to Dynamics 3 the agent has access to the context vector 0% and the changepoint EC. Thus only the distribution Pe remains unknown and the agent needs to estimate it via the observed contexts.
Algorithm 8 DISTRIBUTION e-BEST ARM IDENTIFICATION (D=BAI)
1: Input: the arm set X, the latent vector matrix O the slackness parameter E, the confidence parameter d.
2: Initialize: Compute the G-optimal allocation X
3: Compute C3 >n= n
4: Observe 8
5: Compute
l/c, = =G} 4
Ptu
2. arg max T Op: sEX
(0.1)
2C,NI3
3.
In
()) = Be min
A (3, + [(#,,))
24,
((2..))R
6: while min (0,- x) T Op; 8: -5 -r do
7: Observe 69, and 1[t C} update t+
8: Update Tn and ọr with (0.I) and update 4 if e C.
9:
end while
10:
Recommend arm x = Tt.
The design is straightforward except for ((+,, v). It minimizes the summation C(ü,, x) arg min ER Σnn A (ū,, a) x)), This trick has also been utilized in the design of PS= (see 11.5 It helps to better exploit the structure of the latent vectors O and facilitates the identification
process. For easy implementation, x)), = En ()
choose proxy ((E,, xx) arg min (A,
61

---

Algorithm 9 DISTRIBUTION e-BEST ARM IDENTIFICATION-2 (D=BAlg)
Input: the arm set X, the latent vector matrix O, the slackness parameter E, the confidence
parameter 8.
2: Initialize: Compute the G-optimal allocation X*
3: Compute C3 2 '1 -3
4: Observe "
5: Compute
Lr, 1a, c₂}
Pr.j
Σ
2, arg max Op:: aEX
(0.2)
Lmax In 2 + (H
In 0,) 2)²
2
20r, Lmaxx
In dx
91, min
1
t
25 Imax
2
1
P1, = min
4max Pt.j' 4 t
In
5.
66.
4
C2Nt3
Pr (()1
min
A ( (Te, x) + <(2,z))
((
6: while min apts (or Op, P. < - do
7: Observe 0j, and 1(t C} and let = I.
8: Update te and P. with (0.2)
9: end while
10: Recommend arm De = Zt.
D=BAIg utilizes the techniques have used to bound the deviation between the true dis- tribution Pj and the estimated ones Pt.j for all j E [N]. Similarly, we let x( = DN aigmin ((,)))R MN (Tt, - Pr, E (,(,.)) for efficient computing. Ex &,
As the theoretical guarantee of D=BAIg can derived following similar manner as the proof the DE tern of PS:BAI in Appendix I.2) and in the proof of Lemma G.6 for simplicity, we just present the result and omit the proof here here.
Theorem O.1. DeBAIg identifies an E-best arm within
L (Fe, x) In
max 2.
(Amin + E)2
time steps with probability at least - 8 and in expectation, where We present theorem, along with a proof sketch, for the theoretical guarantee of DEBAI below.
min ) f + ((
H (x) == min (),,,)EER
Theorem O.2. D:BAI identifies e-best arm within
Tomax H2 (are x) In In m (Amin + 8)²
Ô max 3e E
time steps with probability at least 1 - and in expectation, where (( = mi) EØ=1 | (ã., x) z))..
62

---

Proof. For the sake of conciseness and simplicity, only a proof sketch is provided for this Theorem.
Similar results can be found the referred contents. The proof composed by 4 steps.
Step 1: bound the deviation of Po Po[ by Lemma O.3 and Remark O.4
Step 2: prove the recommended arm is an e-best amm. Conditional on Step 1, we can prove this
following the procedures in Lemma J.1
Step 3: give sufficient condition and then obtain high probability upper bound. This can be seen from and by solving
N
A (Tz, x) + ((E,, S Amin +
x)) = B,
Σ
2
12 (Ze, x)
4=0
Amii + E)2 8
Lmmxlt H2 (I 2
1= (Amin + 8)2
The high probability result is obtained by maximizing the above over 2, E Xx * Ze, x", Step 4: the expected result can be derived in similar method as in the proof of NEBAI in Appendix The expected sample complexity and the high-probability sample complexity is the same order.
Lemma O.3. With probability at least 1 - 6, suPje[N] lps - Pt.ll I Be for all t E N, where 3
1. In 2 and ōi, C
2
b.
Proof. We may define the cumulative distribution function (CDF) and the empirical CDF for Pa as E/ Po(0 and F((j) = Ei 1aa, = Cy,Le j} respectively for j E [N]. According
Fo(j)
to the DKW inequality, we have
[i(j)) F() 20 ] 2ex (-21,²))
P
sup JE(N]
By the implication
S 1pj PrJl = (F()) F(j-1) 1) +G0 1)
$ [F(1)) - (.(0))+FF( - 1) - Fi(j 11]
[F() F.(5) 2 _ or [F( 1) - RO -1]1 2''
we have that
2 (-21, (5) 2)
P
sup JE(N]
[p, - Peol
2 E P sup
[jE[N]
FiG) FG)
2
(
4e2
exp
2
This is equivalent to
IP sup
[p5
ir. 2 Br
S Sh.
JE(N]
A union bound gives upper bound of the failure probability Σi, 81, =
Remark 0.4. The use of the DKW inequality gives a union bound over the deviation of the distribution estimation all contexts. This avoid the N factor in the logarithm in Bg and is beneficial when the number of contexts N is large.
63

---

When there are few contexts, it is also possible to directly bound the deviation for each context via Azuma- Hamm--Hoffding inequality, i.e.,
P P(DB3- - Pc,ll - - Et.
A union bound gives that with probability least 1 1- 1p, for all t E N.j [N]. As this new confidence radius is the same as the one in Lemma 0.3 up to constant and logarithmic terms, the sample complexity should be of the same order.
where B. := 21e In NC,
pr.l S 3
We adopt this confidence radius 3.
21. In 2C
the experiment.
P Additional Discussions
In this section, we provide additional discussions
the related methods for BAI in the nonstationary bandits literature in subsection
the upper on the sample complexity in Theorem 3.2 and Theorem 3.3 in subsection P.2
the connection between the piecewise-stationary linear bandits model to the stationary linear bandits
model in subsection P3
the special case where the number context N = 1 subsection P.4
P.1 Discussion the Related Methods in Nonstationary Bandits
To the best of our knowledge, there is limited literature investigating the BAI in the nonstationary bandits setup (there is comparatively a much richer literature for regret minimization in non- stationary environments): [14] studies BAI in the fixed-horizon setup and [15] assumes the best arm remains unchanged after certain time step and explores the fixed-confidence setting. Both of the works are not directly comparable to our proposed piecewise-stationay setup.
Additionally, we provide strong baselines algorithms DE and DeBAlg in Section 6 which are detailed in Section 00.4 These two baselines are given oracle information about the context (see Dynamics 3), while PS= is not. As indicated by Figure 2(b) PS=BAI+ is competitive compared to these strong baselines and is much better than the naive approach.
P.2 More Discussions on the Upper Bound
Firstly, we emphasize that the sample complexity in Theorem 3.2 and Theorem 3.3 are instance- dependent, in particular, the term HDE characterizes the difficulty in estimating the distribution of the context. Furthermore, the presence of the gaps ((x, x*) also underscores that our upper bounds functions of the instance.
Secondly, algorithm adopts the G-optimal design, which is minimax optimal for the BAI in standard linear bandits problem [1. Although we have not proved it, we believe that the sample complexity of the proposed algorithm may not be instance-dependent optimal.
Lastly, we provide some remarks on the instance-dependent optimal algorithms:
(1) The G-optimal design is the cornerstone for the more efficient and adaptive rules like X'-- allocation and Xyy-Adaptive Allocation in 1. Therefore, our algorithm provides framework for more sophisticated algorithms in the piecewise-stational linear bandits problem with the BAI task. Empirically, one can attempt to replace the G-optimal design by the XYyallocation during implementation, which can possibly yield empirical benefits.
(2) The current lower bound established with two simpler problems (see Section 4 which is sufficient to show our algorithm is minimax optimal. However, a tighter instance-dependent lower bound based on the original problem may be required if one wishes to show an algorithm instance- dependent optimal. This can be challenging because the distribution of the arms, the contexts and the changepoints are unknown, and the characterization of the "alternative instance" (i.e., the e-best arm set is changed) is difficult.
To conclude, we believe an instance-dependent optimal algorithm is appealing and can lead to future research.
64

---

P.3 Connections to the Stationary Bandits
Firstly, we would like to clarify that, the piecewise-stationary linear bandits model, the instance tends towards stationary when maXje(N] Pj - 1, instead of the scenario in which Lmax co.
When Lmin and Lmax are large, estimating each latent vector becomes easier since there are more observations in a single stationary segment. However, the overall reward of an arm also depends on Po. the distribution of latent context vectors, which is also assumed to be unknown in the setup. In order to estimate Po. learning agent can get one (unobservable) sample from Po only at the (unobservable) change points. In other words, Lmx charaterizes the "sparsity" of the context samples: the larger Lmax is. the sparser the context samples are. A larger Lmax indicates that samples from Po are likely to be generated less frequently, which will result in the increase the overall sample complexity. Consider an extreme example of Dynamics 3 where the context vector is revealed at every time step and Liin and Lmax are very large. at least L, context samples from Po are required to identify the best arm, then sample complexity of L, Lmin is unavoidable in the our setup under this extreme case.
Secondly, while [ Pj is important in characterizing the (non)stationarity of the instance, we would like to emphasize that both the distribution Po and latent context vectors are essential in characterizing the sample complexity, as shown in the term H (z,, z) in Theorem 3.2 To further illustrate this, we provide a simple but illuminating instance as follows: The instance is composed by N 3 contexts and K = 2 arms, and A, denotes the mean gap between arm 1 and arm under context j & [N] (to be specified below) and A := ΣjE[N] P3 م denotes the weighted mean gap between arm and arm 2. The probability of context 1 is p1 = maxje[N] P; = 1 P2 p3. and pı is close to 1. Let & denote the empirical version of the statistics in the following arguments.
In such case, consider this question: if an algorithm has only detected context in the first time steps and t is large, should it stop or not?
As no change point has occurred, the current dynamics behaves similarly that of stationary bandit
environment up till now. Thus the empirical probabilities of the 3 contexts are ý = 1, 1,12 = - = 0
and the empirical mean gap under context 1 Á is close to A Consider the following two cases:
Case 1: A P2 and A2 A3 -P1- The true weighted mean gap between arm 1 and arm 2 is A = Σ JENN) = -PP33 < 0, and thus arm 2 is the best arm. This indicates that, in order to estimate 22 and A3, an algorithm needs to observe contexts 2 and 3 despite their small probabilities. But currently Pa2 = -3- = 0, = Â terminate.
A
> 0, so the algorithm should not
Case 2: A = 1 and 42, As E 2, Thus å R A
2p2 2ps O. This indicates there is no need to observe contexts 2 and 3, because arm is the best even in the worst case (A2 = Aa 2). In this case, as long as the algorithm gets good estimate of A, it can confidently terminate.
As these two cases indicate, in addition to Pg. the latent vectors (which determine the means of the arms) are equally important for the stopping time. Our algorithm takes both factors into account, as reflected by the summation term in equation (3.4) and A, x) in (3.5) for the algorithm design, and by H (z æ) for the theoretical upper bound.
We conclude that
The unknown distribution Pa and the latent vectors jointly determine the sample complexity. H (I., x) in Theorem 3.2 characterizes their roles, where the contexts with larger probabilities have commensurately greater influence on the sample complexity of the algorithm.
When max Pj + with other parameters fixed, the piecewise-stationary linear bandit instance reduces stationary one. HDw(s,, .>) in Theorem 3.2 becomes Immx//4 which implies that constant number of change points need to be observed, and thus (D( x) can be regarded as a constant. The dominant term in our upper bound, the Tv (x) term, recovers the upper bound in the
stationary bandits, that is, maxaga" (A(w x))+)² ln(1/5] 32
65

---

P.4 Special Case: N = 1
We only consider N > the bandit model is only truely sracewise-stationall when N 1. Thus, we did not specifically derive upper and lower bounds for the extreme case where N = 1. Nevertheless, analysis can cover this case due the following reasons:
The (minimax) lower bound in Theorem 4.1 is not directly applicable since it not derived for this extreme instance. However, if we step back to the analysis equation (M.16), the feasible set in the optimization problem is empty, and thus the lower bound on E.4] (Ne in Theorem is O. In this case, the lower bound in Theorem[4.) reduces to the lower bound in the stationary bandits.
Regarding the upper bound in Theorem 3.2 when N = 1, we have p1 1 and HDE 4 In this case, as DE does not depend on the mean gaps and the mean gaps are among the fundamental quantities to characterize the difficulty of an instance, the T'D term can be regarded as constant. Therefore, the dominant term in the upper bound is Tv. This recovers the bound in the stationary setup.
addition, as we assume N is an imput to our algorithm, when we are aware N = 1, we can actually adopt the algorithms for the stationary setting, e.g., the G-allocation or X''-allocation rule
E-Best Arm Tuple Identification Problem
In the main paper, we consider the identification of an e-best arm in terms of the "ensemble" quality Me := Eg-Po [x 0] ード Pol0]]æ 0j. The curious reader may wonder whether we can identify the e-best arm tuple X Xtuple = (ff,..., ITy). ), where æ5 an e-best arm under context j. i.c..
r3 E f 2 max x BJ - E}. Given the tools we developed in this manuscript, we answer this problem in the affirmative.
Intuitions: Let 25 == arg max x 0z and Aj == min (ata) We expect to have an upper bound taking the form of
Linax
max JEIN]
In )
Pj
Lmiu
d where O (a Aaii occur once among every Pj
In })) is upper bound on the number of context samples j and context j will
contexts in expectation.
The change detection and context alignment subroutines only effective within -" time steps (Line 2 in Algorithm [ However, context is with small occurrence probability Pj, it may not appear before 7* time steps.
Analysis of the problem:
Regarding this scenario, we only expect to obtain a higb-probabillity upper bound on the sample complexity, whereas the expected sample complexity requires more techniques beyond our parallel execution trick (which is used design PS:BAI+) and is an interesting direction left for future research.
Besides, is more feasible consider the identification of e-best arms under contexts with high occurrence probability, i.e., we aim to identify
xtuple
{ar Pj p)
where p is a threshold on the occurrence probability of contexts. Let O₂ = [0] : Ps > p} denote those context with high occurrence probability.
Goal: We aim to devise an algorithm with the minimum sample complexity (arm pulls) to ascertain either (1) an e-best arm under context j. or (2) 0j & O₁-
With the above goal, expect to identify c-best arm for all j with 07 0g: for those j with 07 Op. either s-best arm identified 03 & O is ascertained.
propose Algorithm 10 for this problem, which quite similar to Algorithm except for a few
changes:
66

---

Algorithm 10 SAICEWISE-STATIONAN 8-BEST ARM TUPLE IDENTIFICATION
1: Input: arm set X, size of the set of latent vectors N. bounds on the segment lengths Lmin and
Luaxx slackness parameter E, confidence parameter 6, sampling parameter y and window size w, threshold b, probability threshold
2: Initialize: Compute the G-optimal allocation X and 38400 In NLmma
In N N Lunx and
dr
Flag = [N] and Hold [ and Output = =[].
Set CD sample []. CA ] Set tcD +00.
4: Set Tr. = 0 and initialize Tr. Tt.j. T, with (3.1) for all & S
5: Sample arms { ~ > and observe the associated returns {Y 1= 1 2: t.A 1
2
6: CAd = {1: [T 2l, 8-1 1) =
7:
while 1. 7" and Flag + #00 do
8:
t= -=++ ++++1
9:
Sample an arm 22 X and observe return Y
10:
if mod (t - ICA. 7) * 0 then
11:
Update Je = jt-1, Te.j. 1.. Utt. Tep = Ti-1, for j # Jc.
12:
else
CD sample CD sample + [(1r,, Y(,2))
Update je = Sc-1, Te.j = Ti for all j E [N].
15:
if CD sample 2 w then
16:
LCD w, CDsamplel -w w :) then
17:
CD sample []. o = 2 ICA = t, tCD = t00.
18:
19:
3. CA = LCA(X, w.b, CA
20:
if i: N + 1 then break.
21:
Revert Tt.j = T 1 for all E [N].
22:
end if end if
23:
24:
end if
25:
Update the estimates with 33. 3.2 and Q..
26:
if 3j Flag condition (Q.2) met for and lCD +oo then
27:
for j E Flag do
28:
if min An, r) and 2 - then
29:
Record j and 4, == arg max DEX x 0rs in Hold.
Flag Flag [i} and fCD @ammpllll.
31:
else if β0 + B.. < p then
32:
Record and $j. NAN in Hold.
33:
Flag Flag| [5} and tcp = CDsamplel
end if
35:
end for
36:
else if (CD = CD samplel - then
37:
for (j. in Hold do
38:
Output [j] $5
39: end for
40: end if
41:
end while Recommend Output
42:
On Line 7, the algorithm stops when e-best arm or P; S 5 identified for contexts.
On Line 25, it computes the confidence radii for the arms in context j, as well as the confidence radii for the occurrence probabilities
d In
2
2 5
4d
2
Ot.j
ln
In
(Q.1)
J
8
67

---

2 Immax
Br. == min
In
Tr
ŌA.T.
25 T.max
2 1
where (r.j = min max
pt.
In 6d,1, :
4 T.
On Line 26 to 40, the stopping rule is changed: Stopping condition (I) on Line 26
min zurff],
Ans(Fig::0 2)) Os.j 2 - or P3 Brg <D)
(Q.2)
and
T. 2 (2T/max// 99) In 1n(2/5d,T.)
where oi.j == arg ma 0..j.
Lines 27 to 35: identify an g-best arm or ascertain pj S P among the remaining contexts, and
record these observations in Hold for easy access in stopping condition (II..
Lines 36 40: the recommended e-best arm is recorded, where we adopt NAN flag those contexts with small occurrence probabilities.
Theorem Q.I. Given an instance with probability at least e-best arm for all context E Og with sample complexity
6, Algorithm 10 can recommend an
d
In(1/6)
min {pi, 1 Lmax In (n(16) 64
max
0
max
Limax:
Pj
07/0,/2
(pj p)
d
In(1/o)
min {pj, 01 Tmnax In (1(1/8)
max 60
min
max Liaxx
(Az + E)
Pj
(F) - p)2
which can be simplified as
d
In In(1/8)
δ max Lmax
e² p
Proof of Theorem Q.1
We provide concise proof sketch for this theorem.
By adapting the stopping rule for best arm identification stationary linear bandits to e-best arm identification, observe that the number of arm pulls needed for e-best arm identification under context j is
Tr 0 (Aj +E)
( In 1
d
The remaining problem is to determine how many context samples/changepoints are needed such that the above number of arm samples can be achieved.
Recall that Pr.j
Te. 3. and Lemma I.2 we have
P [Tii
Tepp 2 Tr [iBr,/Good]] s 8d.T.
In addition, we have an upper bound on 9r.j as in J.5 so there would be sufficient arm samples for 8-best arm identification under context if
5 2 min (16p,, }} Tinax In
2
2 ò 0 (Aj + +e)
d
In 1 }
T
-
2\
Ti
dd.
By solving this inequality terms of T,, we obtain
d
In(1/5)
T, = δ max
Lmaxx
(A) + E)
Pj
68

---

As we aim to identify the e-best arms under each context 0j Dg. the upper bound is at least
d
In(1/6)
T, δ max max
Tmmax (Az + +))
(Q.3)
6960p
(A)+
Pj
even the set 3 is given.
Similarly, for those contexts with small occurrence probability 03 & Op. by Lemma 1.2 and J.5 we can identify them when
5
2 2iin (16pj, 7 Limax
2
Pj +
In
2
T.
δ..T.
== Ô min {py: 0 } Limax In(1/6)
(p) - p)2
Careful readers may notice that the denominator depends on "probability gap". which can very small. In practice, if we can actually identify the e-best arm in those contexts, it is also acceptable. Therefore, we instead only choose not identify the e-best arm those contexts #3 ppp2. which yields an upper bound
min {py, 63) Limax In(1/8)
T, =
max 0/40p/2
(Q.4)
(p, p)
In this case, the bound most Ô Timax In(1/8) For the contexts 03 & p/2 1p, either identifying the e-best arm or ascertaining its small occurrence probability suffices, that is,
F
d In(1/8) min {Pj, 04 Tmmax (n(1/5) (p, - 7)2
T ò max min 07e0p/a
max
Linaxo (4j +)
Pj
(Q.5)
The above bound upper bounded by Ô max { Lmax, 2² In(1/8)
By taking the maximum of (Q.3) Q4.4 and Q.5). we can obtain a high-probability problem- dependent upper bound on the sample complexity. In addition, can get high-probability
problem-indeppenden upper bound
In(1/5)
max
Liax.
E2
By setting the threshold ý carefully, the algorithm is guaranteed to terminate before 7* given the good event Good (G.1)
69

---

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

---

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

---

The authors should provide scripts to reproduce all experimental results for the new reproducible, they Answer: [Yes]
Justification:
The code is released. Please refer to Section G
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips) cc/ for more details.
pruidessCodeSSubmsssiiiiii
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https htt////ddduuiiiiiinnneeeee
//nips. //nips.cc/publll// peppuliccguideee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
proposed method and baselines. If only subset of experiments
should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized ver- sions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please refer to Section Gand Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that necessary to appreciate the results and make sense them.
The full details can be provided either with the code, in appendix, or supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars (standard deviations) are included in all experiment results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1 I-sigma error bars, but one should state it. The authors should preferably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
72

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please see Appendix O
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
The authors conform with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure preserve anonymity (e.g., if there is special consideration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: The work is mainly theoretical, thus there is no identifiable societal impact.
Guidelines:
The answer NA means that there is societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact
or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g.. deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology being used as intended and functioning correctly, harms that could arise when the technology is
73

---

being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses addition to attacks, mecha- nisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The work is mainly theoretical.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse dual-use should be released with necessary safeguards to allow for controlled use the model, for example by requiring that users adhere to usage guidelines or restrictions access the model implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
The MATLAB code for the computation of G-optimal allocation used existing code, and has been mentioned and cited in Appendix O
Justification:
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include a URL.
The name of the license (c.g.. CC-BY 4.0) should be included for each asset.
For scraped data from particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi theode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Question:
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
74

---

Researchers should communicate the details of the dataset/code/moodl as part of their sub- missions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with
human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
75


Reviews:
[{"review_id": "EEUivkLYQB", "reviewer": "Reviewer_5EBt", "summary": "The paper proposes a new model called PSLB, where the underlying parameter $\\theta$ in the common linear bandit model is sampled from an unknown distribution at fixed but unknown time steps. The authors propose a naive algorithm and a sophisticated algorithm for this problem, along with their sample complexity guarantees for best arm identification or $\\epsilon$-best arm identification. A lower bound is also proposed, with a specific instance demonstrating its near-minimax optimality.", "questions": "1. In most of the linear bandit best arm identification literature, for example, references 1-5, the sample complexities end up being instance-dependent quantities, which have been shown to be optimal in many cases. Is it fair to say that the sample complexity of this work is loose in the sense that it does not reveal much instance dependency? \n\n2. It seems very critical to assume bounded noise and normalized rewards. What would happen if we assume general sub-Gaussian noise? I am considering a case where for one of the contexts, $\\theta$ can result in a very high reward for certain arms, but the context has a very low probability of occurring. How would the algorithm behave in this scenario?", "limitations": "The work does not have any limitations due to negative societal impact. The main limitation is clarity, which has been mentioned in the weaknesses section.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The new model makes a significant step towards making linear bandits more general, in the sense that it can model non-stationary environments, which is often true for many real-world applications. The analysis is very comprehensive from many perspectives. For example, it provides a naive algorithm whose sample complexity serves as a good comparison with the later, more complicated algorithm. The sample complexity of the more sophisticated algorithm shows an interesting dependency on the environment parameter $L_{max}$.", "weaknesses": "Typo: dynamics --> algorithm?\n\nMotivating Example: I am not sure if investment is a reasonable example to motivate the model, as the model assumes fixed changing points, which clearly goes against the non-stationary market dynamics.\n\nPresentations: Perhaps the biggest concern of mine is the presentation. The algorithm is overly tedious, and I am still not fully clear on it even after reading it multiple times.\n\nIt is not clear to me what $\\tilde{O}$ hides or if it is intended to hide the same things throughout the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Typo: dynamics --> algorithm?\n\nWe are sorry for the confusion. There might be a cross citation problem in the manuscript which will be fixed in the revised version. \n\nThe \"Dynamics\" refers to the dynamics of the problem. Specifically, Dynamics $1$ on page 43 describes the dynamics of the proposed problem. Dynamics 2 on page 44 and Dynamics 3 on page 49 are the dynamics of two easier problems, which are used in the proof of the lower bound result in Theorem 4.1 of Section 4.\n\n>Motivating Example\n\nThanks for the question concerning the motivation for our problem setting. We believe our problem setting is sufficiently general to encompass a variety of practical situations. Indeed, we assume that the sequence of change points $c=(c_1, c_2,\\ldots)$ is deterministic and fixed beforehand. Our results, however, do not depend on the exact sequence, but rather the lower and upper bounds on the lengths of each stationary phase, i.e., on $L_{\\min}= \\inf_{i \\in \\mathbb{N}} (c_{i+1}-c_i)$ and $L_{\\max}= \\sup_{i \\in \\mathbb{N}} (c_{i+1}-c_i)$. The investment example, or any other example, fits into this framework as long as $0<L_{\\min}\\le L_{\\max}<\\infty$. In fact, our results continue to hold even if the sequence of change points $c=(c_1, c_2,\\ldots)$ is **random** as long as, almost surely, $0<L_{\\min}\\le L_{\\max}<\\infty$.\n\nBeyond specific applications and motivating examples, we believe that our model is fundamental in understanding the fundamental performance limits of best arm identification algorithms in certain controlled non-stationary environments. \n\n>Presentations\n\nWe thank the reviewer for the feedback. As we wish to reveal all the details in the algorithm design, the presentation of Algorithm 1 may look complicated. We will provide a more high-level pseudocode of our algorithm in the revised version to resolve this issue (see the attached file in the global response).\n\nBased on the high-level pseudocode and Figure 1 in the manuscript, we provide a high-level explanation as follows: \nAfter the initialization, the algorithm design can be largely divided into 3 phases (as in Lines 177 to 179 of the manuscript): \n- **Exploration phase** (the thin blue line segments in Figure 1): the algorithm will be in the exploration phase in approximately $\\frac{\\gamma-1}{\\gamma}$ of the total time steps. The algorithm collects samples which will be used to estimate the current latent vector $\\theta_{\\hat{j}\\_t}^*$ and the distribution $P_\\theta$ in Equation (3.2).\n- **Change Detection phase** (the diamonds in Figure 1): the algorithm enters this phase in every $\\gamma$ time steps. It collects one sample each time and does changepoint detection via the $LCD$ subroutine.\n- **Context Alignment phase** (the thick brown line segment in Figure 1(b)): the algorithm enters this phase only when a change alarm is raised in the Change Detection phase. It does context alignment via the $LCA$ subroutine. The output $\\hat{j}_t$ is the estimated index of the new context.\n\nLastly, the algorithm updates the estimates and checks the stopping rule.\n\nThe high-level pseudocode offers an overview of the algorithm design and we sincerely hope it can clarify the algorithm design. \n\n\n>It is not clear to me what $\\tilde{O}$ hides.\n\nThe $\\tilde{O}$ notation hides the constants and logarithmic terms throughout the paper for easier comparison. Specifically, \n- for the upper bound of the naive algorithm in Proposition 3.1, the original non-asymptotic bound is presented in eqution (F.1) on page 22, where $T_0$ is defined in Line 650. The constants and the logarithmic term $\\ln\\frac{KL_{\\max}}{(\\Delta_{\\min}+\\varepsilon)^2}$ are hidden.\n- for the upper bound of $PS\\varepsilon BAI$ in Theorem 3.2, the original non-asymptotic bound is presented in Equation (J.3) on page 35. The constants and logarithmic terms $\\ln\\frac{Kd}{(\\Delta(x^*,x)+\\varepsilon)^2}$, $\\ln (NH_{DE}(x_\\varepsilon,x))$ and $\\ln\\frac{KNL_{\\max}}{\\Delta(x^*,x)+\\varepsilon}$ are hidden.\n\n>Instance-dependent sample complexity and optimality\n\nWe ask the reviewer to kindly refer to the global response.\n\n>(1) Assumption on bounded noise and normalized rewards.\n(2) What would happen if we assume general sub-Gaussian noise?\n(3) Special case: high reward but low occurrence probability.\n\nWe thank the reviewer for the questions. \n\n(1) The assumption on the normalized rewards (i.e., the rewards are within $[0,1]$) is common in the linear bandits literature [3] and the nonstationary bandits literature [10,14]. If the rewards are bounded in $[0,B]$, we can normalize the observed rewards $y$ by $\\tilde{y}=y/B$.\n\nThe assumption on the bounded noise is also common [1,14]. In our analysis, the bounded noise assumption is adopted to accommodate the randomness in the sampling rule in Line 9 of Algorithm 1, which simplifies the analysis.\n\n(2) In this case, Lemma E.1 does not hold as Bernstein's inequality has been used. In order to remedy this, one can choose the deterministic version of the G-optimal design like Figure 2 in [1], i.e., sample $x_t = \\arg\\min_{x\\in\\mathcal{X}} \\max_{\\tilde{x}\\in\\mathcal{X}} \\tilde{x}^\\top(A_{t-1,\\hat{j_t}}+xx^\\top)^{-1}\\tilde{x}$ where the design matrix $A_{t,j} = \\sum_{s\\in\\mathcal{T}_{t,j}}x_s x_s^\\top$. Then Proposition 2 in [1] can replace Lemma E.1, which provides concentration guarantees for the empirical means. With some addition computational efforts, we believe we can obtain similar bounds as the current results (up to the sub-Gaussian parameter $\\sigma$ factors).\n\n(3) Our algorithm indeed takes this critical scenario into account. We quantify the influence of the reward under each context and the corresponding occurrence probability of the context in $\\bar{H}(x_\\epsilon,x)$ in Theorem 3.2. The algorithm will stop when sufficient evidence is accumulated to infer an $\\varepsilon$-best arm. \n\nWe have provided more discussions and concrete examples in Lines 1453 to 1478 of the manuscript, where Case 1 is the scenario the reviewer is curious about.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ulgv7bjQge", "reviewer": "Reviewer_comL", "summary": "The paper introduces a piecewise stationary linear bandit (PSLB) model and presents the PSεBAI+ algorithm for identifying the best arm with minimal sample complexity. The PSLB model accounts for environments where contexts change at unknown points and are drawn from an unknown distribution. The PSεBAI+ algorithm, combining PSεBAI and NεBAI subroutines, aims to detect changepoints and align contexts. Theoretical analysis indicates that PSεBAI+ achieves an expected sample complexity close to the optimal. The paper also includes numerical experiments comparing PSεBAI+ with baseline algorithms.", "questions": "- Is $\\theta_j^*$ sampled IID from $P_{\\theta}$ each time? If so, it should be clearly stated \"IID\"", "limitations": "Discussion on limitations can be improved, with designated section.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Introduces a new framework for best arm identification in piecewise stationary environments.\n- The proposed PSεBAI+ algorithm combines changepoint detection and context alignment.\n- Provides proofs that the expected sample complexity of PSεBAI+ is nearly optimal.\n- Includes numerical experiments showing the algorithm's performance relative to baseline methods.", "weaknesses": "- The justification for using a piecewise stationary model could be more robust, as real-world scenarios may involve more complex conditions.\n- The discussion on computational complexity is limited. The authors should discuss the computation required for each major step of the proposed algorithm.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">The justification for using a piecewise stationary model could be more robust, as real-world scenarios may involve more complex conditions.\n\nWe agree that the real-world scenarios may involve more complex conditions. However, even under our relatively benign setup, the proposed solution is already sufficiently complicated. Given the limited literature on Best Arm Identification under the nonstationarity (the only ones we know are [14] and [15]), we believe our work would be of great interest to the community and hope it can inspire more works towards this direction which encompass more complex scenarios or which produce tighter results.\n\n>The computational complexity for each major step of the proposed algorithm.\n\nWe thank the reviewer for the suggestion to discuss the computational complexity of each subroutine within $PS\\varepsilon BAI$.\n\nWe consider the number of these operations: arithmetic (addition and multiplication) operations, logic operations and comparison operations and we also regard $\\ln(\\cdot)$, $\\sqrt{\\cdot}$ and sampling from a distribution as one step of operation.\n\nWe decompose the main loop of Algorithm 1 as follows, where the lines with $O(1)$ operations are omitted:\n- Exploration phase (Lines 8 to 11): $O(1)$.\n- Change Detection phase (Lines 12 to 16): \n    - the $LCD$ subroutine in Line 16 needs $O(wd^2+Kd)$ operations.\n- Context Alignment phase (Lines 17 to 21): \n    - the $LCA$ subroutine in Line 19 needs $O((wd^2+Kd)N)$ operations, as the $LCD$ subroutine will be invoked $N$ times in the worst case in Line 4 of $LCA$.\n    - the reversion procedure in Line 21 needs $O(\\gamma w d)$ operations.\n- The updating procedure and the stopping rule checking (Lines 25 to 32):\n    - updating $\\hat{\\theta}_{t,j}$ needs $O(d^2)$ operations, as we need to incorporate the latest sample into the estimate.\n    - updating $\\hat{p}_{t,j}, j\\in[N]$ requires $N$ operations.\n    - updating the confidence radius and the empirical best arm need $O(KN)$ operations.\n    - the stopping condition in Equation (3.4) requires $O(K)$ operations.\n\nWe remark that some intermediate results can be stored to avoid repeated computations and we believe the algorithm is efficient overall. In particular, since the reward structure is linear, there are $K$ arms, and $N$ contexts, $O(d^2)$, $O(K)$, and $O(N)$ operations probably cannot be be avoided.\n\nFrom the above analysis, in the decreasing order of the number of operations:\n1. the Change Detection phase requires the most budget as it will be invoked every $\\gamma$ time steps.\n2. the Context Alignment phase requires the second many operations. While it requires many operations when it is implemented, it will not be called during a stationary segment.\n3. the updating procedure uses small portion of the operations, as $w$ is usually much greater than $K$ and $N$.\n4. the exploration phase demands constant operations in each loop.\n\nWe thank the reviewer for the suggestion again and we will incorporate these discussions into the revised manuscript.\n\n>Is $\\theta_j^*$ sampled IID from $P_\\theta$ each time? If so, it should be clearly stated \"IID\"\n\nWe are sorry for if there was any confusion caused. At each changepoint, a new context is **independently** sampled from $P_\\theta$. We will highlight this setup in Line 140 in the revised version.\n\n>Discussion on limitations can be improved, with designated section.\n\nWe thank the reviewer for the suggestion. We will describe the limitations in a designated section in the revised version. We have some discussions in Section B on page 11. Similar to [10,21,22] in the literature, our work has introduced assumptions to provide theoretical guarantees for the algorithm, the algorithm is robust when the assumptions are violated though. We hope to weaken these assumptions via exploiting the latent clustering structure within the contexts, which can lead to future work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "cB4m4aKzHm", "reviewer": "Reviewer_tHAq", "summary": "he paper introduces a novel algorithm, PSεBAI+, designed for ε-Best Arm Identification in Piecewise Stationary Linear Bandits (PSLB). The algorithm addresses the challenge of identifying an arm with an average return close to the optimal under varying contexts and unknown changepoints. It incorporates change detection and context alignment mechanisms to adapt to the non-stationary nature of the environment efficiently. The paper provides theoretical guarantees for the algorithm's performance and supports these claims with empirical results.", "questions": "1. About the context alignment:\n- When a new distribution is detected, how does the algorithm decide when to perform context alignment?\n- What methods are used to judge the similarity between the new context and existing ones? The concept of context alignment is common, but the paper lacks a detailed description of the design specifics.\n- How does the algorithm confirm the reliability of the estimated new context feature vectors?\n\n2. Could the authors elaborate on the specific application of the G-optimal design in the algorithm?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper proposes a new algorithm that combines change detection and context alignment in a PSLB setting. The algorithm is optimized to identify ε-optimal arms with a minimal number of samples, which is crucial for practical applications.\n2. It offers a thorough theoretical analysis, including a proof of the algorithm's high-probability performance and sample complexity bounds.\n3.The paper backs up the theoretical findings with empirical experiments, demonstrating the algorithm's efficiency and robustness.", "weaknesses": "1. The paper does not provide a comparison with the current state-of-the-art methods, which is essential for establishing the novelty and superiority of the proposed approach.\n\n2. Parameter Sensitivity Analysis:\n- There is no ablation study on the parameters w and b, which, based on past experiences replicating reference [10], could have a significant impact on the algorithm's performance.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": ">Comparison with the current state-of-the-art methods.\n\nWe thank the reviewer for the question. As we stated in Line 101 in the manuscript, to the best of our knowledge, there is limited literature investigating the BAI problem in the nonstationary bandit setup (there is comparatively a much richer literature for regret minimization in non-stationary environments): [14] studies BAI in the **fixed-horizon** setup and [15] assumes the **best arm remains unchanged** after certain time step and explores the fixed-confidence setting. Both of the works are not directly comparable to our proposed piecewise-stationary setup.\n\nAdditionally, we provide strong baseline algorithms $D\\varepsilon BAI$ and $D\\varepsilon BAI_\\beta$ in Section 6, which are detailed in Section O.3 on page 58. These two baselines are given oracle information about the context (see Dynamics 3 on page 49), while $PS\\varepsilon BAI^+$ is not. As indicated by Figure 2(b), $PS\\varepsilon BAI^+$ is competitive compared to these strong baselines and is much better than the naive approach.\n\n>Ablation study on the parameters w and b\n\nWe thank the reviewer for the suggestion and we design an experiment to study the choice of $w$ and $b$.\n\nAccording to the distinguishability condition (Assumption 1 on page 6), point (2) indicates we can set $w=\\frac{L_{\\min}}{3\\gamma}$, where $\\gamma$ is the change detection frequency, and point (3) indicates $w$ and $b$ are coupled. In the original experiment, we have fixed $\\gamma=6$ (see Line 327) so $w = \\tilde{w}:=\\frac{L_{\\min}}{18}$.\n\nIn the ablation study on $w$ and $b$, we choose to vary the choice of $\\gamma$, and thus, $w$ and $b$ will change accordingly. Specifically, we select $\\gamma\\in\\\\{2,3,6,12\\\\}$ and the corresponding $w\\in\\\\{3\\tilde{w},2\\tilde{w},\\tilde{w},\\frac{\\tilde{w}}{2}\\\\}$. The other parameters remain unchanged. The experiment result is presented in the attached file in the global response. When $\\gamma=18,w = \\frac{\\tilde{w}}{3}$, Assumption 1 is severely violated and the result is not desirable.\n\nThe result indicates that, while smaller $\\gamma$ and greater $w$ can result in slightly greater sample complexity, the overall sample complexity does not vary much and the superiority of our algorithm over the naive uniform sampling algorithm $N\\varepsilon BAI$ is maintained. We conclude that our algorithm is robust against these choices, as long as Assumption 1 is not severely violated.\n\nWe thank the reviewer for the valuable suggestion again and we will incorporate the above discussions in the revised manuscript.\n\n\n\n>About the context alignment:\n(1) When to perform context alignment?\n(2) What methods are used to judge the similarity between the new context and existing ones? Detailed description of the context alignment design.\n(3) How does the algorithm confirm the reliability of the estimated new context feature vectors?\n\n(1) We believe the reviewer is asking \"When a new **context** is detected, how does the algorithm decide when to perform context alignment?\"\n\nWhen a new context is detected, i.e., Line 16 of Algorithm 1 is True (Step 1 in Figure 1(b)), the algorithm immediately enters the Context Alignment phase in Lines 17 to 22 (Step 2 in Figure 1(b)).\n\n(2) The methods used to judge the similarity between the new context and the existing ones are encompassed in the $LCA$ subroutine. Due to the page limit, we postpone the detailed description of $LCA$ to page 15 with vivid explanations in Lines 565 to 576. We politely ask the reviewer to kindly refer to the description therein.\n\n(3) The estimated index $\\hat{j}\\_t$ of the new context is given by the $LCA$ subroutine, whose performance is guaranteed by Lemma G.3 on page 23. With the estimated context index, the new samples (up to the next changepoint) are collected by the corresponding time indices collector $\\mathcal{T}\\_{t,\\hat{j}\\_t}$ in Line 11 of Algorithm 1, which are later used to estimate the context feature vectors in Line 25. We adopt the concentration Lemma E.1 in the proof of Lemma I.1 on page 30, which quantifies how well the estimated context vectors concentrate around the groundtruth.\n\n>Could the authors elaborate on the specific application of the G-optimal design in the algorithm?\n\nWe thank the reviewer for the question. As there can be two interpretations of the proposed question, we answer both of them to avoid any misunderstandings. One interpretation concerns the exact **implementation** of the G-optimal design; the other concerns the **theoretical justification** for why we use the G-optimal design within $PS\\varepsilon BAI$. \n\nIn terms of the **implementation** of the G-optimal design, as stated in Line 1288, we adopt the Wolfe--Atwood Algorithm with the Kumar--Yildirim start introduced in [33]. We kindly ask the reviewer to kindly refer to the description therein. In Algorithm 1, the G-optimal allocation is computed in Line 2 and is stored in $\\lambda^*$. A new arm will be sampled according to $\\lambda^*$ in Line 9.\n\nPerhaps the reviewer is wondering why we use the G-optimal design at all in our algorithm. From a **theoretical justification**, we make use of properties of the G-optimal design (i.e., Equation (E.3) on page 18) in the proof the concentration lemmas (Lemma E.1 on page 17 and Lemma H.1 on page 25), which have been further used in the proof of the upper bound (e.g., Lines 851 and 880) and in the guarantees of the $LCD$ and $LCA$ subroutines (e.g. Lemma G.1). \n\nWe note that the G-optimal design has been widely used in the linear bandits literature [1,2,14]. The G-optimal design takes the geometry of the arm set into account and reduces the uncertainty of the estimated latent context vector in all directions uniformly, thus enhancing overall efficiency/sample complexity. Therefore, we are inspired to incorporate the G-optimal design into our algorithm design and the proposed algorithm achieves the minimax optimality, as expected (but requires work to prove).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
**We would like to thank all the reviewers for their valuable suggestions and we sincerely hope their concerns have been properly resolved by the detailed response provided below.**

>In most of the linear bandit best arm identification literature, for example, references 1-5, the sample complexities end up being instance-dependent quantities, which have been shown to be optimal in many cases. Is it fair to say that the sample complexity of this work is loose in the sense that it does not reveal much instance dependency?

We thank Reviewer 5EBt for the question.

Firstly, we emphasize that the sample complexity in our results (Theorem 3.2 and 3.3) are instance-dependent, in particular, the term $H_{DE}$ characterizes the difficulty in estimating the distribution of the context. Furthermore, the presence of the gaps $\Delta(x,x^*)$ also underscores that our upper bounds are functions of the instance.

Secondly, we acknowledge that there are algorithms that are instance-dependent optimal for the BAI problem in standard linear bandits literature, e.g., [24,32]. Our algorithm adopts the G-optimal design, which is minimax optimal for the BAI in standard linear bandits problem [1,2]. Although we have not proved it, we agree that the sample complexity of the proposed algorithm may not be instance-dependent optimal.

Additionally, we would like to make some remarks about the instance-dependent optimal algorithms:
- The G-optimal design is the cornerstone for the more efficient and adaptive rules like $\mathcal{X}\mathcal{Y}$-allocation and $\mathcal{X}\mathcal{Y}$-Adaptive Allocation in [1]. Therefore, our algorithm provides a framework for more sophisticated algorithms in the piecewise-stationary linear bandits problem with the BAI task. Empirically, one can attempt to replace the G-optimal design by the $\mathcal{X}\mathcal{Y}$-allocation during implementation, which can possibly yield empirical benefits.
- Currently, the lower bound is established with two simpler problems (see Section 4), which is sufficient to show our algorithm is minimax optimal. However, a tighter instance-dependent lower bound based on the original problem may be required if one wish to show an algorithm is instance-dependent optimal. This can be challenging because the distribution of the arms, the contexts and the changepoints are unknown, and the characterization of the "alternative instance" (i.e., the $\varepsilon$-best arm set is changed) is difficult.

We agree that an instance-dependent optimal algorithm is appealing and can lead to future research.

Meta-review: This paper proposes the piecewise stationary linear bandit (PSLB) model, where the weight parameter of the linear reward model changes at some unknown time step but is sampled from the same distribution. This model extends stochastic linear bandits to a nonstationary setting and is novel in the literature. The authors proposed an algorithm, PS$\epsilon$BAI+, to identify the best arm that has the highest return averaged over all context parameters. They presented an instance-dependent sample complexity analysis and showed the proposed algorithm is asymptotically optimal, validated by a lower bound on the sample complexity. Experiments are also provided to demonstrate the performance of the proposed BAI algorithm.

The reviewers unanimously voted to accept this paper due to its novelty and solid analysis, which I agree with. In the camera-ready version, the authors should address the most prominent questions brought up during the discussion, such as the discussion on computational complexity and motivating examples of the proposed model. It would also be beneficial to compare the proposed algorithm to nonstationary BAI algorithms, even though they deal with a larger class of problems, as they should still be applicable in the PSLB model.
Decision: Accept (poster)