Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits

Authors: yunlong  hou
vincent y f tan
zixin  zhong
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-11 11:55:45

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.

Main paper: 
 introduction: 
 In stochastic multi-armed bandits (MABs), an 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 a stationary environment where the expected return of each arm remains unchanged over time. However, we usually face ever-changing environments in real life. For instance, in investment option selection and portfolio management, fund managers want to select a 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 as one based on agriculture in the face of stochastically changing weather patterns are discussed in detail in Appendix A. These motivate us to formulate and investigate a piecewise stationary linear bandit (PSLB) model.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 θ ∈ Θ from an unknown probability distribution P θ , 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 ∈ X and the context θ. In particular, the expected return of an arm is the weighted sum µ x = E P θ [x ⊤ θ]. 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 x µ x up to some tolerance ε with probability ≥ 1 -δ and with as few samples as possible. The agent's behavior does not affect the sequence of contexts that is drawn from P θ .Main Contributions. We are the first to study the fixed-confidence best arm identification (BAI) problem in piecewise stationary bandits (PSB). Given δ > 0, we say the arm with the highest expected return µ * is the best, and an arm is ε-optimal if its expected return is at least µ * -ε. We seek to design an (ε, δ)-PAC algorithm which can identify an ε-optimal arm with probability ≥ 1 -δ in as few time steps as possible, i.e., with minimal sample complexity.Our first contribution concerns the formulation of a novel PSLB model, where we measure the quality of an arm x according to its expected return µ x = E θ∼P θ [x ⊤ θ] 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 is that the context changes as time evolves, and hence the arm's average return across time also changes, in general. Hence, we aim to identify an arm whose average return across contexts is 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 µ x 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 is meaningful but challenging, as the agent needs to reliably estimate the context vectors, changepoints, and context distribution.Secondly, we propose PIECEWISE-STATIONARY ε-BAI + (PSεBAI + ), an algorithm designed to tackle the BAI problem in our PSLB model. We prove that it is (ε, δ)-PAC and bound its sample complexity. PSεBAI + samples arms according to a suitably defined G-optimal allocation, and runs two algorithms: NAÏVE ε-BAI (NεBAI) and PSεBAI as subroutines in parallel to achieve efficiency and attain a bound on the sample complexity in expectation.• Being a baseline but naïve algorithm, the complexity of NεBAI grows linearly with the maximum length between two changepoints L max , motivating us to design a more efficient algorithm, PSεBAI, to reduce the impact of L max .• PSεBAI is equipped with two delicately designed subroutines LINEAR-CHANGE DETECTION (LCD) and LINEAR-CONTEXT ALIGNMENT (LCA) to actively detect changepoints and align 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 a 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 PSεBAI and analyzing them requires some care. On the theoretical side, we prove PSεBAI identifies an ε-optimal arm faster than NεBAI with high probability. The success of PSεBAI relies on the LCD and LCA subroutines, while a minor drawback is that they require a non-vanishing failure probability budget which does not allow us to bound the sample complexity of PSεBAI 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 NεBAI in parallel.Thirdly, we derive a lower bound on the complexity of any (ε, δ)-PAC 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 ε-best arm.We compare the upper bound of PSεBAI + and this generic lower bound in several instances. The matching (up to logarithmic terms) of bounds illustrate that our PSεBAI + algorithm is almost asymptotically optimal.Lastly, we demonstrate the efficiency of PSεBAI + with numerical experiments. The first half of our experiment shows that PSεBAI + is (ε, δ)-PAC and with significantly lower sample complexity compared to NεBAI, corroborating our theoretical findings. In the second half, we compare PSεBAI + to NεBAI, and two other benchmarks DISTRIBUTION ε-BAI (DεBAI) and DεBAI β .While contexts and changepoints are not available to PSεBAI + and NεBAI, they are observed by DεBAI and DεBAI β . Nevertheless, PSεBAI + is still competitive compared to DεBAI and DεBAI β in our empirical experiments. Hence, both experiments justify the necessity of the change detection and context alignment 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 L min and L max 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, [1, 2] focus on BAI and [3, 4] aim to solve the RM problem. An efficient algorithm can choose the G-optimal allocation or X Y-allocation rule to quickly identify a good arm [1, 5] . Besides, [6, 7] focus on ε-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] [9] [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 one hand, the RM problem have been investigated extensively in DB models [12, 13] . 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 unchanged after certain time step and explores the fixed-confidence setting. Besides, when the contextual information in NSB models is available, NSB models are known as contextual bandit (CB) models [16] [17] [18] . [16] 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 it remains unvarying in 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 [10] , and indicates the best arm changes as in [19] .In PSB models, a large body of works focus on RM. While [10, [20] [21] [22] equip their algorithms with changepoint detection techniques to handle the context changes, [23] actively checks the quality of each arm. However, there is no existing work on the fixed-confidence BAI problem in a PSB model. To fill this gap in the literature, we design PSεBAI + for ε-optimal arm identification in our proposed PSLB model. We show PSεBAI + is almost asymptotically optimal by comparing its complexity to a generic lower bound of all algorithms, and validate its efficiency through numerical experiments. 
problem setup: 
 For m ∈ N, let [m] := {1, 2, . . . , m}. For a finite set S, let ∆ S denote the |S|-dim probability simplex on S. Let A(q) := x∈X q x xx ⊤ be the matrix induced by q ∈ ∆ X with X ⊂ R d . An instance of piecewise stationary linear bandit is a tuple Λ = (X , Θ, P θ , C). Specifically, x ∈ R d is an arm (vector) and the arm set X ⊂ R d is composed of |X | = K arms that spans R d . The latent vector matrix Θ = (θ * 1 , . . . , θ * N ) ∈ R d×N contains N latent column vectors where the j th column θ * j is associated with context j ∈ [N ]. For the sake of normalization, we assume |x ⊤ θ * j | ≤ 1 for all x ∈ X , j ∈ [N ]. Let P θ denote the distribution (probability mass function) of the latent vectors and p j = P θ [θ * j ]. We represent the probabilities of latent vectors as p = (p 1 , . . . , p N ) ∈ ∆ N . The fixed but unknown sequence of changepoints C := (c 1 , c 2 , . . .) is an sequence of increasing positive integers 1 = c 1 < c 2 < . . ., characterizing all the changepoints (time steps).The return of arm x under latent context j is a random variable Y = x ⊤ θ * j + η, where η is a zero-mean random variable (noise) supported on [-1, 1], and the expected return of arm x is µx := E θ∼P θ [x ⊤ θ] = N j=1 P θ [θ * j ]x ⊤ θ * j .The best arm, which we assume is unique, is denoted as x * := arg max x∈X µ x with mean µ * := µ x * . Given a slackness parameter ε > 0, we define the set of ε-best arms X ε := {x ∈ X : µ x ≥ µ * -ε}. For each pair of arms (x, x) ∈ X 2 , define the contextual mean gap between x and x under latent context j as ∆ j (x, x) := (x -x) ⊤ θ * j and the mean gap between x and x as ∆(x, x) := µ x -µ x.Given l ∈ N, the interval (c l , . . . , c l+1 -1) is known as the l th stationary segment and its length is L l := c l+1 -c l . We assume L min ≤ L l ≤ L max . Let l t := max{l : c l ≤ t} denote the number of stationary segments up to time step t. At time step t ∈ [T ] (see Dynamics 1), (i) If t ∈ C, the environment samples a latent vector θ * jt according to P θ , that is, it generates a (latent) context sample with P θ ; otherwise the latent vector remains unchanged, i.e., θ * jt = θ * jt-1 . The contexts {θ * jc l } l∈N are sampled i.i.d. from P θ at each changepoint {c l } l∈N .(ii) The agent pulls an arm x t and observes the stochastic return Y t,xt = x ⊤ t θ * jt + η t , where η t is drawn independently from a distribution supported on [-1 , 1] .The agent uses an online algorithm π := {(π t , τ t , r t )} t∈N to actively interact with the instance Λ and only has access to the arm set X , number of latent vectors N , the bounds on the length of each segment L min and L max , the slackness parameter ε, and the confidence parameter δ.• sampling rule π t : H π t := (x π s , Y s,x π s ) s∈[t-1] → X samples an arm x π t based on the observation history H π t and observe the corresponding random return Y t,x π t ; • stopping rule τ t : H π t+1 → {STOP, CONTINUE} decides whether to stop or continue to execute given the observation history H π t+1 . The stopping time under algorithm π is denoted as τ π ; • recommendation rule r τ : H π τ +1 → X recommends an arm xπ based on H π τ +1 upon termination. The stopping time τ π is the sample complexity of the algorithm π under instance Λ. The expected sample complexity is E[τ π ], where the expectation is taken w.r.t. the random returns, the realization of the contexts governed by the latent vector distribution P θ , and the randomness of the algorithm π.An algorithm π is (ε, δ)-PAC (Probably Approximately-Correct) ifP[x π ∈ X ε ] ≥ 1 -δ.Our overarching goal in this paper is to devise an (ε, δ)-PAC algorithm that minimizes τ π with high probability (w.h.p.) and in expectation.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 1 is needed for theoretical proof and the proposed algorithm is 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 in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless 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 on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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, a 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 to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
algorithms 3.1 a naïve baseline: nεbai: 
 We first devise the NAÏVE ε-BEST ARM IDENTIFICATION (or NεBAI) algorithm (presented in Algorithm 2). In the design of NεBAI, only the choice of confidence radius ρt takes the potential context changes into consideration. Even though NεBAI does not attempt to detect potential changes in the context, it can identify an ε-optimal arm w.h.p. and is with a finite expected sample complexity. Proposition 3.1. Let ∆ min = min x̸ =x * ∆(x * , x),T N V = d (ε + ∆ min ) 2 ln 1 δ and T N D = L max (ε + ∆ min ) 2 ln 1 δ .The NεBAI algorithm is (ε, δ)-PAC and its expected sample complexity isÕ(T N V + T N D ).The upper bound in Proposition 3.1 (also see Appendix F) consists of two main terms. (i) As NεBAI samples arms according to the G-optimal allocation (see Appendix D), the amount of samples needed to estimate the average of latent vectorst s=1 θ * js /t contributes to T N V . (ii) T N D quantifies how fast t s=1 θ * js /t converges to the expectation of context vectors t j=1 p j θ * j .The sample complexity of NεBAI grows linearly with L max , but we surmise that the sample complexity of a close-to-optimal algorithm should have a reduced dependence on L max .The algorithm PIECEWISE-STATIONARY ε-BEST ARM IDENTIFICATION (or PSεBAI) is presented in Algorithm 1. By using a sliding window mechanism, PSεBAI actively detects the changepoints and aligns the current latent context with contexts observed in the previous time steps via LINEAR-CHANGE DETECTION (or LCD) and LINEAR-CONTEXT ALIGNMENT (or LCA), which are presented in Algorithms 3 and 4 (see App. D. At time t, we estimate Θ and p with Θt = ( θt,1 , . . . , θt,N ) and pt = (p t,1 , . . . , pt,N ) ⊤ , respectively. 1 We denote the empirical mean gap between x and x under context j as ∆t,j (x, x) := (x -x) ⊤ θt,j .PSεBAI first computes the G-optimal allocation [1] λ * on the arm set X and its maximum possible stopping time τ * (Line 2). It initializes CD sample and CA id . CD sample collects samples to detect changepoints and CA id maintains a dictionary of {latent context index : identification samples} pairs (Line 3); 2 CA id [j] is the sequence of CD samples used to identify latent context j. It also initializes T t,j , the collection of time indices in [t] in the Exp phases under estimated context j. Define T t = j∈[N ] T t,j , T t = |T t |, T t,j = |T t,j |, ∀j ∈ [N ]. (3.1) Algorithm 1 PIECEWISE-STATIONARY ε-BEST ARM IDENTIFICATION (PSεBAI)[(θ * σ(j) , p σ(j) )] N j=1 up to a permutation σ : [N ] → [N ],which is determined by the occurrence order of latent vectors. Thus we assume the latent vectors appear in order of increasing indices. 2 A sample in CD sample is a CD sample; A dictionary has a pairing structure {key:value} and dictionary[key] = value. [ai] n i=1 denotes a sequence of elements a1, . . . , an.where θt,j = 0 if T t,j = 0. We define α t , ξ t , β t,j , and∆clip 2 t,j (x, x) in Appendix D.2.1.For each pairs of arms (x, x), the confidence radius of ∆(x, x) at time step t is In the CA phase, PSεBAI starts by resetting CD sample (Line 17), updating the count of time steps and recording the ending time of this CA phase (Line 18). Thereafter, the CA subroutine (presented in Algorithm 4) is invoked, which estimates the current latent context index ĵt and updates CA id (Line 19). If ĵt = N + 1, i.e., PSεBAI identifies N + 1 latent contexts, which is incorrect under instance Λ, it terminates and fails to identify an ε-optimal arm (Line 20). Lastly, all empirical statistics are reverted to those from (w(γ + 1)/2) time steps ago, i.e., the most recent (wγ/2) samples in the Exp phases are abandoned (Line 21). The stopping rule is described in Lines 26 to 32. (I) If the following condition is satisfied (Line 26):ρ t (x, x) := 2(α t + ξ t ) + N j=1 β t,EQUATIONwhere the empirical mean gap ∆t (x * t , x) := (x * t -x) ⊤ Θt pt and x * t := arg max x∈X x ⊤ Θt pt , PSεBAI records the arm with the highest empirical mean as xε and the number of CD samples t CD (Lines 27 and 28) but does not terminate immediately. Besides, a mild forced arm pull procedure is in the second line of (3.4), which is inspired by Lemma E.1 and to ensure the performance of PSεBAI. (II) PSε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 xε is recommended and PSεBAI terminates (Lines 29 to 30). Part (II) of the stopping rule assures PSεBAI does not terminate when a changepoint has occurred but has not been detected, as PSεBAI may fail to identify an ε-optimal arm otherwise.We remark that even though PSεBAI uses the knowledge of L max , our experiments show that the performance of PSεBAI is robust to small misspecifications in L max (see Appendix O.2). Furthermore, the computational complexity of PSεBAI is computed in detail in Appendix D.4. The derived computational complexity indicates the proposed algorithm depends in a natural manner on the problem parameters such as d, K, N , and γ. Lastly, thanks to the LCD and LCA subroutines, a slightly modified variant of PSεBAI can also solve the "ε-Best Arm Tuple identification problem", which aims to identify an ε-best arm under each context; see Appendix Q for details.To facilitate the analysis of PSεBAI, we propose the following assumptions. Note that our PSεBAI algorithm may still succeed to identify an ε-optimal arm w.h.p. when the assumptions do not hold.Assumption 1 (Distinguishability Condition). The agent can choose w, γ and b such that (1) EQUATIONThis assumption guarantees (i) PSεBAI will not abandon all samples during the reversion procedure (Line 21 of Algorithm 1); (ii) each two latent vectors can be distinguished if the window size w is sufficiently large (e.g., L min /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 a feature of PSB models and similar assumptions are also present in existing works for their analyses [21, 10, 22] . We demonstrate the robustness of PSεBAI to these parameters using experiments in Section 6.Theorem 3.2. Define the context distribution estimation (DE) hardness parameterH DE (x ε , x) := L max (∆(x * , x) + ε) 2 H(x ε , x)whereH(x ε , x) := N j=1 min {16p j , 1/4}|∆ j (x ε , x) + ε| 2 .Under Assumption 1, with probability at least 1 -δ, PSεBAI identifies an ε-optimal arm and its sample complexity isEQUATIONThe upper bound comprises three terms which serve distinct purposes: (i) Latent vector estimation (VE): Õ (T V (x)) quantifies the bulk of samples needed to obtain a good estimate of latent context vectors such that the returns of x ε and x can be distinguished, where x ε is an ε-best arm and x / ∈ X ε is a suboptimal arm. T V (x) recovers the sample complexity in the stationary linear bandits in [1] , indicating that PSεBAI estimates latent vectors efficiently. (ii) Context distribution estimation (DE): Õ (T D (x ε , x)) characterizes the bulk of samples needed to learn the distribution of latent context vectors. (iii) Residual estimation (RE): Õ (T R (x)) counts the remaining samples needed for VE and DE, in addition to Õ (T V + T D ). Besides, the max operator is applied to exclude all suboptimal arms. We also see that T V (x) and T D (x ε , x) are similar to T N V and T N D in Proposition 3.1 respectively. Firstly, the bound in (3.6) implies that, in an instance with smaller relaxed mean gap ∆(x * , x) + ε, PSεBAI terminates after a larger number of time steps; in other words, it is more difficult to identify an ε-optimal arm. In difficult instances with small ∆(x * , x) + ε, the different orders of this term inT V (x), T D (x ε , x) and T R (x) indicate that, T R (x) is small compared to T V (x) and T D (x ε , x).Secondly, DE solely utilizes context samples generated with P θ and they are generated only at 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εBAI processes, and hence T D (x ε , x) is supposed to be with larger order than T V (x).Moreover, for the purpose of DE, PSεBAI needs to observe context samples at ÕH(xε,x) (∆(x * ,x)+ε) 2 ln 1 δ = Õ HDE(xε,x)Lmax ln 1 δ changepoints where L max is the maximum length of a stationary segment, leading us to T D (x ε , x). Close examination of the definition of H(x ε , x) reveals that both the vectors and their probabilities influence the number of samples needed for DE. The comparison between T D (x ε , x) and T N D in Proposition 3.1 clearly indicates that PSεBAI mitigates the influence of L max by detecting changepoints and aligning the detected context with observed ones, while NεBAI does not do so.+ = PSεBAI ∪ NεBAIWe have provided a high-probability result for PSεBAI in Theorem 3.2. The design of PSεBAI (Line 7 of Algorithm 1) indicates that PSεBAI will not recommend any arm if it does not terminate at time τ * . This result is nontrivial, as the high-probability result in Theorem 3.2 depends on the success of change detection (Algorithm 3) and context alignment (Algorithm 4), which requires a non-vanishing failure probability (e.g., δ/2). Thus, we cannot derive an upper bound on the expected sample complexity of PSεBAI. We devise a solution by designing the Piecewise-Stationary ε-Best Arm Identification + (PSεBAI + ) algorithm with a simple but effective trick.The PSεBAI + algorithm samples one arm with the G-optimal allocation λ * at each time step, with which Algorithms 1 and 2 are executed in parallel (detailed in Algorithm 5). This is feasible since PSεBAI and NεBAI algorithms have the same sampling rule. Theorem 3.3. The PSεBAI + algorithm is (ε, δ)-PAC and its expected sample complexity isÕ min max xε∈Xε,x̸ =xε,x * T V (x) + T D (x ε , x) + T R (x), T N V + T N D .PSεBAI + inherits the superiority of PSεBAI to adapt to the piecewise stationary environment, and employs the stopping rule of NεBAI to maintain a finite expected sample complexity. As a result, the expected complexity of PSεBAI + in Theorem 3.3 is of the same order as the high-probability one of PSεBAI in Theorem 3.2 and is not larger than the complexity of NεBAI in Proposition 3.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.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes]• 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 in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
lower bound on the sample complexity: 
 Given Λ = (X , Θ, P θ , C), define the alternative instanceΛ ′ = (X , Θ ′ , P θ ′ , C) w.r.t. Λ, where Θ ′ = (θ ′ 1 , . . . , θ ′ n ) ∈ R d×N , P θ ′ [θ ′ j ] = P θ [θ * j ], and there exists x ∈ X \ X ε , such that x ⊤ ε E θ ′ ∼P θ ′ [θ ′ ] < x ⊤ E θ ′ ∼P θ ′ [θ ′ ] -ϵ for all x ε ∈ X ε . Let Alt Θ (Λ)be set of all alternative instances (w.r.t. Λ). Theorem 4.1. For all (ε, δ)-PAC algorithm π, there exists an instance Λ = (X , Θ, P θ , C) such thatE[τ π ] ≥ max T ε (Λ) ln 1 2.4δ , c N C ,whereT ε (Λ) -1 := max {vj } N j=1 min Λ ′ ∈AltΘ(Λ) j,x p j v j,x (x ⊤ (θ * j -θ ′ j )) 2 2, andN C := max x̸ =x * j p j (∆ j (x * , x)+ε) 2 (∆(x * , x) + ε) 2 ln 1 4δ .Recall that c N C is the N C -th changepoint in the changepoint sequence C, which is lower bounded by N C L min and is N C L max 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 1):• Dynamics 2: the agent observes the index of current context j t (i.e., contextual linear bandits);• Dynamics 3: the agent observes the changepoints in C and context vector θ * jt 's, and hence she solely needs to estimate the distribution of contexts. We bound the sample complexity of an (ε, δ)-BAI algorithm in Dynamics 2 and 3 respectively, which when combined, yield the lower bound in Theorem 4.1; this is detailed in Appendix M.Note that T ε (Λ) -1 in the lower bound generalizes [16] to the setting of linear bandits. In addition, Theorem 4.1 can be reduced to a bound in stationary linear bandits with one latent vector [24] (see the discussion leading to (M.15)). 
on the asymptotic optimality of psεbai +: 
 To illustrate the efficiency of our PSεBAI + algorithm, we compare the upper bound on its expected sample complexity in Theorem 3.3 and the generic lower bound in Theorem 4.1 under specific instances below and in Appendix N. We also gain further insight into our PSεBAI + algorithm. Under the instance defined in Example 1, x (i) for all i ̸ = 1 is inferior to x (1) under all contexts and x (i+d) for all i ∈ [d -1] is marginally better than x (1) by 1 -cos ϕ only under context θ * i+ and ∆(x (1) , x (i+d) ) = cos ϕ -cos 2 ϕ. We expect PSεBAI + to discover this feature of the instances and quickly identify an ε-optimal arm with a course estimation of the context distribution.Corollary 5.1. For the instance defined in Example 1, we haveEQUATIONwhere E[τ ] * is the minimal expected sample complexity over all (ε, δ)-PAC algorithms and f : R → R satisfies f (ϕ) → 0 as ϕ → 0 + . The upper bound in (5.1) is achieved by PSεBAI + .The order of H DE in Corollary 5.1 indicates that T D (x (1) , x (d+1) ) = Õ(N L max ln(1/δ)) is not dominating the sample complexity of PSεBAI + , suggesting that a 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 5.1 implies that under such instances, the upper and lower bounds on the sample complexity of PSεBAI + match up to logarithmic factors, that is, the performance PSεBAI + is near optimal. Besides, the bound of NεBAI in Proposition 3.1 is with an extra additive term L max compared to the lower bound in Corollary 5.1, illustrating that NεBAI is suboptimal and again emphasizing the significance of detecting changes and aligning contexts for PSεBAI + to reduce the impact of L max . 
numerical experiments: 
 We now evaluate the empirical performance of PSεBAI + . We utilize the instance defined in Example 1 with d = 2, ϕ = π/8, We generate a changepoint sequence C such that c l+1 = c l + L l with L min = 3 × 10 4 , L max = 5 × 10 4 , P[L l = L min ] = 0.8, P[L l = L max ] = 0.2, and fix it throughout the whole set of experiments. We set the confidence parameter δ = 0.05 and vary the slackness parameter ε from 0.04 to 0.6 (i.e., ε = 0.03 × 1.35 k for k ∈ [12] ). We set γ = 6, the window size w = L min /(3γ) and compute b via (3.5) in Assumption 1. 3 For each choice of algorithm and instance, we run 20 independent trials. All the code to reproduce our experiments can be found at https://github.com/Y-Hou/BAI-in-PSLB.git.We first compare PSεBAI + and NεBAI. Both algorithms succeed to identify an ε-optimal arm, while empirically, the complexity of PSεBAI + is ≤ 1% of that of NεBAI. The empirical averages and standard deviations of the sample complexities of both algorithms are presented in Figure 2(a) .Figure 2 (a) illustrates that empirically, the termination and arm 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 PSεBAI + .Next, we test the efficacy of PSεBAI + to learn and exploit the latent vectors and the distribution of contexts. Specifically, we run PSεBAI + and NεBAI under Dynamics 1 where neither the index nor the vector of current context is visible to the agent. We also run benchmark algorithms: DεBAI and its variant DεBAI β under Dynamics 3 where context vectors and changepoints are all observed; these two algorithms are detailed and analyzed in Appendix O.4.As the changepoint sequence C is fixed in a given instance and t/L max ≤ l t ≤ t/L min for all t ∈ N, we regard the number of context samples l τ as a proxy of the sample complexity τ . We present the number of context samples need by PSεBAI To summarize, we emphasize that the empirical superiority of PSεBAI + over NεBAI implies that the efficacy of PSεBAI + is inherited from PSεBAI. Our experiments show that actively exploiting the context information, via changepoint detection and context alignment (as in PSεBAI + and PSεBAI) facilitates identifying the ε-optimal arm efficiently.Similar to many existing algorithms in piecewise-stationary bandits [21, 10, 22] , our algorithm requires Assumption 1 and the knowledge of L max . These may not be available in practice. Thus, we conduct more experiments in Appendix O.2 to exhibit the robustness of PSεBAI + . Specifically, in Appendix O.2, we conduct experiments for the case in which L max is misspecified. In Appendix O.3, we alter the change detection frequency γ so that w and b change accordingly. In both sets of experiments, the overall sample complexity of PSεBAI + does not vary significantly and retains its superiority over NεBAI. We conclude that PSεBAI + is robust to slight misspecifications in these parameters, as long as Assumption 1 is not severely violated. Please refer to Appendix O for further details and experiments. 
conclusion and future work: 
 We proposed a novel PSLB model and designed the PSεBAI + algorithm to identify an ε-optimal arm with probability ≥ 1 -δ. 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 a fairly general framework for algorithm design. For instance, in addition to utilization the G-optimal allocation to sample arms as in PSεBAI + , the X Y-allocation and adaptive X Y-allocation [1] 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 is also of great interest.Secondly, most of the literature on piecewise-stationary bandits [21, 10, 22 ] make assumptions to provide theoretical guarantees. It would be interesting to remove or reduce these assumptions under our ε-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, i.e., to identify an ε-optimal arm with high probability in a fixed time horizon in PSLB models.[  
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 of 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 make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
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 no 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 to 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 be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: The contents of the appendices are organized as follows:• In Appendix A, we provide further motivating examples for our problem.• In Appendix B, we discuss the limitations of our method.• In Appendix C, we review more related works on drifting and contextual bandits.• In Appendix D, we provide more details about our algorithms -Appendix D. • In Appendix P: we provide more discussions on -the related methods for BAI in nonstationary bandits, -the instance-dependent upper bound, -the connection between the piecewise-stationary linear bandits model to the stationary linear bandits model, -the special case where N = 1.• In Appendix Q: we provide analytical results on the "Best Arm Tuple Identification Problem".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, 20] , there is a multitude of options for fund managers to 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. In a bearish market, more portfolios tend to incur losses; while in a bullish 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), we wish to design and analyze algorithms that selected portfolio to yield the best long-term option under such a piecewise-stationary environment. Crop rotation is another example. Since crop yields can be 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) are correlated as they tend to favor similar conditions, thus, they can be 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 a period of time and it will not change suddenly. Domain knowledge from historical data/records provides us with prior knowledge on L min and L max . 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 ε-best arm) and is adaptable to local environment factors, such as weather patterns.Similar to existing works on piecewise stationary bandits [21, 10, 22] , we introduced some assumptions 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 to differentiate two contexts with close latent vectors for identifying an ε-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.In drifting bandits (DB), the regrets of algorithms are affected by the level of nonstationarity of the environment, which can be 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 to the agent, [16, 26, 17, 27] aim to identify the best arm with the assumption that the context changes at every time step according to a 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 to identify an ε-optimal arm in our piecewise stationary linear bandit (PSLB) model.In adversarial bandits, existing works pertaining to 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-confidence BAI problem in piecewise stationary bandits.All proposed algorithms make use of the well known G-optimal allocation (design) [1, 29] , which is widely used in the linear bandits literature. The G-optimal allocation minimizes the maximal mean-squared prediction error in all directions [1] . Given an arm set X , the G-optimal allocation λ * is a distribution over the arm set, which is the minimizer of g(λ) = max x∈X ∥x∥ 2 A(λ) -1 , where A(λ) = x∈X λ(x)xx ⊤ and λ ∈ ∆ X . Interested readers may refer to Chapter 21 in [29] .As presented in Algorithm 2, NεBAI 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.1) and affected by the maximum length of a single stationary segment L max .1: Input: the arm set X , the phase length bounds L min , L max , the slackness parameter ε, the confidence parameter δ. 2: Initialize: Compute the G-optimal allocation λ * .3: Compute C 3 = ∞ n=1 n -3 and t * = 3d ln(6dKC 3 /δ). 4: Sample t * arms {x s } t * s=1 ∼ λ * and observe the associated returns {Y s,xs } t * s=1 . Let t = t * . 5: Compute θt = 1 t t s=1 A(λ * ) -1 x s Y s,xs , ẋt = arg max x∈X x ⊤ θt , ρt = 8L max t ln 4KC 3 t 3 δ + 5 d t ln 4KC 3 t 3 δ . (D.1) 6: while ẋ⊤ t θt -ρt + ε < max x̸ = ẋt x ⊤ θt + ρt do 7:Sample an arm x t ∼ λ * and observe return Y t,xt and let t = t + 1.Update θt , ẋt and ρt with (D.1). 9: end while 10: Recommend arm ẋε = ẋt .For each pair of arms (x, x), the confidence radius of ∆(x, x) at time step t isρ t (x, x) := 2(α t + ξ t ) + N j=1 β t,j | ∆clip 2 t,j (x, x) + ζ t (x, x)|,where a clip 2 := min{max{a, -2}, 2} denotes the value of a that is clipped to the interval [-2, 2] andEQUATIONL max T t ln 2 δ d,Tt , 1 4 , δ v,Tt = δ 15KT 3 t , δ m,Tt = δ 15KN T 3 t , δ d,Tt = δ 15N T 3 t .ζ t (x, x) minimizes the last summation. In the final theoretical upper bound on the sample complexity, we take ζ t (x, x) = ε for simplicity. In the experiment, we utilizeζ t (x, x) = arg min ζt(x,x)∈R N j=1 β t,j ( ∆t,j (x, x) + ζ t (x, x)) 2 = - N j=1 β t,j ∆t,j (x, x) N j=1 β t,jfor a simple and effective analytic expression in the experiment.In the LCD subroutine (Algorithm 3), two estimates θ1 and θ2 of the latent vectors are independently computed from the first and second halves of the input CD samples (Line 2). LCD only raises an alarm of changepoint (Line 4) when the difference between θ1 and θ2 is sufficiently large (Line 3) and indicates a changepoint occurs w.h.p.The LCA subroutine (Algorithm 4) estimates the latent vector of current context and updates the dictionary CA id . Specifically, it firstly samples w/2 samples with λ * (Line 2). It then checks1: Input: arm set X , detection window w, threshold b and w arms with the associated observations s=1 , where[(x 1 , Y s,x1 ), . . . , (x w , Y w,xw )]. 2: Compute θ1 = 2 w w 2 s=1 A(λ * ) -1 xs Y s,xs and θ2 = 2 w w s= w 2 +1 A(λ * ) -1 xs Y s,xs . 3: if ∃x ∈ X , s.t.|x ⊤ ( θ2 -θ1 )| > b{(x s , Y s,xs )} t s=t-w 2 +1 = {x s , Y s,xs } w 2 s=1 . 3: for j ∈ CA id do 4: if not LCD(X , w, b, [(x s , Y s,xs )] w 2 s=1 + CA id [j]) then 5: CA id [j] = [(x s , Y s,xs )] w 2 s=1 . 6:Return j, CA id .end if 8: end for 9: index = len(CA id ) + 1.10: CA id [index] = [(x s , Y s,xs )] w 2 s=1 . 11: Return index, CA id .whether the current latent context has been visited in previous time steps by scanning through CA id (Line 3). In order to learn if the current context can be aligned with context j, the LCD subroutine is called with the w/2 recent samples and CA id [j] as input: (i) If the current context is aligned with CA id [j] (Line 4), the current latent context is j w.h.p. Thus the LCA subroutine updates CA id [j] and returns the index j (Lines 5 to 6), which would be ĵt in Line 19 of Algorithm 1. Note that in Lines 10 and 11 of Algorithm 1, all the collected samples will be assigned to context ĵt (until the next changing alarm) and will be used to estimate θ * ĵt and all p j '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.e., it has not been visited, CA id gets extended with a new index-samples pair and is returned along with the new index (Lines 9 to 11).To help understand PSεBAI + algorithm, we highlight the differences between PSεBAI and PSεBAI + , and the differences between subroutines LINEAR-CONTEXT ALIGNMENT (LCA) and LINEAR-CONTEXT ALIGNMENT + (LCA + ).Algorithm 5 PIECEWISE-STATIONARY ε-BEST ARM IDENTIFICATION + (PSεBAI + )1: Input: arm set X , number of latent vectors N , bounds on the segment lengths L min and L max , slackness parameter ε, confidence parameter δ, sampling parameter γ, window size w and threshold b. 2: Initialize: Compute the G-optimal allocation λ * and τ * = 38400 ln(80)N Lmax ε 2 ln N 2 KLmax δε 2 . 3: Set CD sample = [ ], CA id = { }, t CD = +∞. Set T t,j = ∅ and initialize T t , T t,j , T t with (3.2) for all t ≤ τ * , j ∈ [N ]. 4: Compute C 3 = ∞ n=1 n -3 and t * = 3d ln(6dKC 3 /δ). 5: Sample w/2 arms {x s } w/2 s=1 ∼ λ * and observe the associated returns {Y s,xs } w/2 s=1 . 6: Set t = w 2 , t CA = w/2, CA id = {1 : [(x s , Y s,xs )] w/2s=1 }, ĵt = 1. 7: Set ẋt = 0, ρt = 2ε and ẋε = -∞. Compute θt with (D.1). if mod (t -t CA , γ) ̸ = 0 then 20:Update ĵt = ĵt-1 , T t, ĵt = T t-1, ĵt ∪ {t}, T t,j = T t-1,j for j ̸ = ĵt .else 22:CD sample = CD sample + [(x t , Y t,xt )]. 23: if |CD sample | ≥ w then 24:if LCD(X , w, b, CD sample [-w : ]) then 25:CD sample = [ ].26:t = t + w 2 , t CA = t, t CD = +∞. 27:ĵt , CA id = LCA + (X , w, b, CA id )28:if ĵt = N + 1 then break.Revert T t,j = T t-w(γ+1),j for all j ∈ [N ]. s = s + 1, t = t + 1.Set (x t , Y t,xt ) = (x s , Y s,xs ). 7: Compute θt , ẋt , ρt = EU(t, θt-1 , t * , C 3 ). 8: if ẋ⊤ t θt -ρt + ε ≥ max x̸ = ẋt x ⊤ θt + ρt then 9:ẋε = ẋt , index = len(CA id ) + 1.Return index, CA id , ẋε , θt .11:end if 12: end for 13: for j ∈ CA id do 14:if not LCD(w, b, [(x s , Y s,xs )] w 2 s=1 , CA id [j]) then 15: CA id [j] = [(x s , Y s,xs )] w 2 s=1 . 16:Return j, CA id . 17:end if 18: end for 19: index = len(CA id ) + 1. 20: CA id [index] = [(x s , Y s,xs )] w 2s=1 . 21: Return index, CA id , ẋε , θt .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 ln(•), √ • and sampling from a distribution as one step of operation.We decompose the main loop of Algorithm 1 as follows, where the lines with O(1) operations are omitted:• Exploration phase (Lines 8 to -Updating θt,j needs O(d 2 ) operations, as we need to incorporate the latest sample into the estimate.-Updating pt,j , j ∈ [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 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.From the above analysis, in the decreasing order of the number of operations:• The Change Detection phase requires the most budget as it will be invoked every γ time steps.• 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. • The updating procedure uses small portion of the operations, as w is usually much greater than K and N . • The exploration phase demands constant operations in each loop.Lemma E.1. Let X s be the arm drawn with the G-optimal allocation λ * at time step s and Y s,xs = x ⊤ s θ * js + η s be the corresponding return with Eη s = 0, |x ⊤ s θ * js | ≤ 1 and |η s | ≤ 1. Then we haveP 1 n n s=1 x ⊤ A(λ * ) -1 x s Y s,xs -x ⊤ θ * js ≥ ϵ ≤ δ for all ϵ ≥ d n ln 2 δ + d n ln 2 δ 2 + 4d n ln 2 δ . In addition, if n ≥ d 4 ln 2 δ , we have P 1 n n s=1 x ⊤ A(λ * ) -1 x s Y s,xs -x ⊤ θ * js ≥ 5 d n ln 2 δ ≤ δProof. Note that the arms are selected according to the G-optimal design, and thusE x∼λ * [xx ⊤ ] = A(λ * ). Therefore, for all s ∈ [n], E x ⊤ A(λ * ) -1 x s Y s,xs -x ⊤ θ * js = 0 (E.1) and x ⊤ A(λ * ) -1 x s Y s,xs -x ⊤ θ * js (E.2) ≤ x ⊤ A(λ * ) -1 x s x ⊤ s θ * js + x ⊤ A(λ * ) -1 x s η s + 1 ≤ x ⊤ A(λ * ) -1 x s x ⊤ s θ * js + x ⊤ A(λ * ) -1 x s η s + 1 ≤ 2 x ⊤ A(λ * ) -1 x s + 1 ≤ 2∥x∥ A(λ * ) -1 ∥x s ∥ A(λ * ) -1 + 1 ≤ 3dwhere we make use of the property of the G-optimal allocation in the last inequality∥x∥ 2 A(λ * ) -1 ≤ d, ∀x ∈ X . (E.3)Additionally,E x ⊤ A(λ * ) -1 x s Y s,xs 2 (E.4) = E x ⊤ A(λ * ) -1 x s (x ⊤ s θ * js + η s ) 2 = E x ⊤ A(λ * ) -1 x s x ⊤ s θ * js 2 + E x ⊤ A(λ * ) -1 x s η s 2 + 2E x ⊤ A(λ * ) -1 x s x ⊤ s θ * js • x ⊤ A(λ * ) -1 x s η s (a) = E x ⊤ A(λ * ) -1 x s 2 x ⊤ s θ * js 2 + E η 2 s x ⊤ A(λ * ) -1 x s 2 (b) ≤ 2E x ⊤ A(λ * ) -1 x s 2 (c) = 2 x ⊤ A(λ * ) -1 x (d) ≤ 2dwhere we make use of the fact that η t is zero-mean and is independent of other random variables in (a); |x ⊤ s θ * js | ≤ 1 and P η 2 s ≤ 1 = 1 in (b); x s ∼ λ * in (c); and the property of the G-optimal allocation (E.3) in (d).According to the Bernstein's inequality with (E.1), (E.2) and (E.4),P 1 n n s=1 x ⊤ A(λ * ) -1 x s Y s,xs -x ⊤ θ * js ≥ ϵ ≤ 2 exp - 1 2 (nϵ) 2 n • 2d + dnϵ = 2 exp - nϵ 2 4d + 2dϵ.In order to upper bound the error probability by δ, we need2 exp - nϵ 2 4d + 2dϵ ≤ δ ⇒ ϵ ≥ d n ln 2 δ + d n ln 2 δ 2 + 4d n ln 2 δ .In addition, if n ≥ d 4 ln 2 δ , we have5 d n ln 2 δ = 5 2 max d n ln 2 δ , 4d n ln 2 δ ≥ d n ln 2 δ + d n ln 2 δ 2 + 4d n ln 2 δ .This finishes the proof.To analyze the theoretical performance of NεBAI, we first show that it can identify an ε-optimal arm with probability 1 -δ and derive a high-probability upper bound on its stopping time in Lemma F.1.Lemma F.1 (High-probability upper bound of NεBAI). With probability 1 -δ, the NεBAI algorithm identifies an ε-optimal arm after at mostÕ L max + d (ε + ∆ min ) 2 ln 1 δ time steps, where ∆ min = min i̸ =i * ∆(x * -x i ).Next, we prove that after a sufficiently large number of time steps, the probability that NεBAI does not terminate is small in Lemma F.2.Lemma F.2. LetT 0 = 768(8L max + 25d) (ε + ∆ min ) 2 ln 768KC 3 (8L max + 25d) (ε + ∆ min ) 2 δ with C 3 = ∞ n=1 n -3 .For t ≥ T 0 , the probability that NεBAI does not terminate before t time steps isδ (α-1)C3(t/2) 2 .Lastly, we apply Lemmas F.1 and F.2 to prove Proposition 3.1.Proposition 3.1. Let ∆ min = min x̸ =x * ∆(x * , x), T N V = d (ε + ∆ min ) 2 ln 1 δ and T N D = L max (ε + ∆ min ) 2 ln 1 δ .The NεBAI algorithm is (ε, δ)-PAC and its expected sample complexity isÕ(T N V + T N D ).The detailed analysis is presented as below.Proof of Lemma F.1. The result is to be proven with the following procedures.First step: Prove x ⊤ E θ∼P θ θ -x ⊤θt can be bounded with high probability.Let θt = 1 t t s=1 θ * js . (i) For all ε > 0, we have,P x ⊤ E θ∼P θ θ t -x ⊤ θ > ε = P tx ⊤ E θ∼P θ θ -x ⊤ Nt l=1 L l θ * j c l > tε = P Nt l=1 L l x ⊤ E θ∼P θ θ -L l x ⊤ θ * j c l > tε (a) ≤ 2 exp - t 2 ε 2 2 Nt l=1 (2L l ) 2 (b) ≤ 2 exp - tε 2 8L max .Since |x ⊤ E θ∼P θ θ| ≤ 1 and x ⊤ θ * j c l | ≤ 1 for all l, we obtain (a) by applying Hoeffding's inequality. We obtain (b) from the fact that Nt l=1 L l = t and L l ≤ L max for all l. In other words, for all δ > 0,P x ⊤ E θ∼P θ θ -x ⊤ θ > 8L max t ln 2 δ ≤ δ.(ii) Besides, according to Lemma E.1, if t ≥ d 4 ln 2 δ , we haveP x ⊤ θt -x ⊤ θt ≥ 5 d t ln 2 δ = P 1 t t s=1 x ⊤ A(λ * ) -1 x s Y s,xs -x ⊤ θ * js ≥ 5 d t ln 2 δ ≤ δ.(iii) For all t > 0, all x ∈ X , sincex ⊤ E θ∼P θ θ -x ⊤ θt ≤ x ⊤ E θ∼P θ θ -x ⊤ θ + x ⊤ θt -x ⊤ θt ,we haveP x ⊤ E θ∼P θ θ -x ⊤ θt > ρt (α) ≤ δ KC α t α when t ≥ d 4 ln 4KC α t α δ ,whereρt (α) = 8L max t ln 4KC α t α δ + 5 d t ln 4KC α t α δ , C α = ∞ n=1 n -α , α > 2.For simplicity, we set α = 3 and write ρt (3) as ρt in the following analysis. We now show that t ≥ d 4 ln 4KCαt α δ holds when t ≥ 3d ln 6dKC3 δ with the following lemma (the proof of which is presented by the end of Appendix F.1).Lemma F.3. Let a, b, c > 0 and ac ≥ 1/2, then t ≥ max{2a ln b, 4ac ln(2ac)} ⇒ t ≥ a ln(bt c ). With a = d 4 , b = 4KC α δ = 4KC 3 δ , c = α = 3, Lemma F.3 implies that t ≥ 4ac ln(2abc) = 3d ln 6dKC 3 δ ⇒ t ≥ max{2a ln b, 4ac ln(2ac)} ⇒ t ≥ a ln(bt c ). Define event Ẽt = x∈X x ⊤ E θ∼P θ θ -x ⊤ θt ≤ ρt (α) for t ≥ t * and Ẽ = t≥t *Ẽt . We haveP Ẽc t ≤ x∈X δ KC α t α = δ C α t α , P Ẽc ≤ ∞ t=t * P Ẽc t ≤ ∞ t=1 δ C α t α = δ.We assume Ẽ holds in the second and third steps in this proof.Second step: Prove NεBAI recommends an ε-optimal arm when it stops.If the algorithm terminates and returns ẋε ̸ = x * , we haveẋ⊤ ε θt -ρt + ε ≥ max x̸ = ẋε x ⊤ θt + ρt . Since ẋ⊤ ε E θ∼P θ θ + ε ≥ ẋ⊤ ε θt -ρt + ε and max x̸ = ẋε x ⊤ θt + ρt ≥ max x̸ = ẋε x ⊤ E θ∼P θ θ ≥ x * ⊤ E θ∼P θ θ, we have ẋ⊤ ε E θ∼P θ θ + ε ≥ x * ⊤ E θ∼P θ θ, implying that ẋε ∈ X ε . Hence, we always have ẋε ∈ X ε .Third step: Derive the stopping time of NεBAI.(i) Let x (2) = arg max x̸ =x * x ⊤ E θ∼P θ θ and ∆ min = min x̸ =x * ∆(x * -x) = (x * -x (2) ) ⊤ E θ∼P θ θ.We apply the following lemma to show that NεBAI stops when ρt is sufficiently small. Lemma F.4 ([30, Lemma 3] ). Denote by î the index of the item with empirical mean is i-th largest: i.e., ŵ( 1) ≥ . . . ≥ ŵ( L). Assume that the empirical means of the arms are controlled byε : i.e., ∀i, | ŵ(i) -w(i)| < ε. Then, ∀i, w(i) -ε ≤ ŵ( î) ≤ w(i) + ε. Lemma F.4 implies that ẋ⊤ t θt -ρt + ε ≥ x * ⊤ E θ∼P θ θ -2ρ t + ε = x ⊤ (2) E θ∼P θ θ -2ρ t + ε + ∆ min and max x̸ = ẋt x ⊤ θt + ρt ≤ x ⊤ (2) E θ∼P θ θ + 2ρ t .When ρt ≤ (ε + ∆ min )/4, we haveẋ⊤ t θt -ρt + ε ≥ x ⊤ (2) θt + ε + ∆ min 2 ≥ x ⊤ (2) θt + 2ρ t ≥ max x̸ = ẋtx ⊤ θt + ρt , which will lead to the termination of NεBAI.(ii) According to the definition of ρt , we haveρt (α) ≤ (ε + ∆ min )/4 ⇔ 8L max t ln 4KC α t α δ + 5 d t ln 4KC α t α δ ≤ (ε + ∆ min )/4 ⇔ 1 t ln 4KC α t α δ 8L max + 5 √ d ≤ (ε + ∆ min )/4 ⇔ t ≥ √ 8L max + 5 √ d 2 (ε + ∆ min ) 2 /16 ln 4KC α t α δ ⇐ t ≥ 32(8L max + 25d) (ε + ∆ min ) 2 ln 4KC α t α δ ⇐ t ≥ 192(8L max + 25d) (ε + ∆ min ) 2 ln 768KC 3 (8L max + 25d) (ε + ∆ min ) 2 δ .We apply Lemma F.3 to invert the last line above. Witha = 32(8L max + 25d) (ε + ∆ min ) 2 , b = 4KC α δ , c = α = 3, Lemma F.3 indicates that t ≥ 4ac ln(2abc) = 384(8L max + 25d) (ε + ∆ min ) 2 ln 768KC 3 (8L max + 25d) (ε + ∆ min ) 2 δ ⇒ t ≥ max{2a ln b, 4ac ln(2ac)} ⇒ t ≥ a ln(bt c ).Altogether, we show that with probability 1 -δ, NεBAI identifies an ε-optimal arm after at most384(8L max + 25d) (ε + ∆ min ) 2 ln 768KC 3 (8L max + 25d) (ε + ∆ min ) 2 δtime steps.Proof of Lemma F.2. To begin with, letT 0 = 768(8L max + 25d) (ε + ∆ min ) 2 ln 768KC 3 (8L max + 25d) (ε + ∆ min ) 2 δFor any T ≥ T 0 , let T = ⌈T /2⌉.(I) If NεBAI terminates within T time steps, there is nothing to prove.(II) Assume NεBAI does not terminates within T time steps. According to the analysis in the proof of Lemma F.1, if NεBAI does not terminate before T time steps, i.e., the stopping time τ satisfies that τ ≥ T , then eventT -1 t= T +1Ẽt does not hold. This indicatesP τ ≥ T |τ ≥ T ≤ P   T -1 t= T +1 Ẽc t   ≤ T -1 t= T P Ẽc t ≤ T -1 t= T δ C α t α ≤ δ C α T T t -α dt ≤ δ (α -1)C α 1 ( T ) α-1 - 1 T α (a) ≤ δ (α -1)C α (T /2) α-1 .(a) results from the fact that T ≥ T /2.Altogether, for T ≥ T 0 , the probability NεBAI does not terminate before T time steps isδ (α-1)Cα(T /2) α-1 .Proof of Proposition 3.1. First, Tonelli's Theorem implies thatE[τ ] = E τ 0 1 dx = E +∞ 0 I(τ > x) dx = +∞ 0 E [I(τ > x)] dx = +∞ 0 P(τ > x) dx.Next, we apply Lemma F.2 to showEτ ≤ T 0 + E[τ |τ ≥ T 0 + 1] • P[τ ≥ T 0 + 1] ≤ T 0 + +∞ T0 P(τ ≥ x) dx ≤ T 0 + +∞ T0 δ (α -1)C α (x/2) α-1 dx = T 0 + δ (α -1)(α -2)(T 0 /2) α-2 . (F.1)Besides, Lemma F.1 indicates that NεBAI can identify an ε-optimal arm with probability 1 -δ.Proof of Lemma F.3. For x > 0, let G Proof Outline of Theorem 3.2f (x) = x -a ln(bx c ) = x -a ln b -ac ln x = x 1 - a ln b x - ac ln x x . Since f (x) ≥ 0 ⇐        a ln b x ≤ 1 2 ac ln x x ≤ 1 2 ⇔    x ≥ 2aA proof outline of Theorem 3.2 is provided in this section. It consists of three steps:Step 1: PSεBAI (Algorithm 1) depends on the success of change detection and context alignment (Algorithm 3 and 4). We firstly upper bound the failure probability of these two subroutines via Lemma G.1, Lemma G.2, Lemma G.3 and summarized in Lemma G. 4 . More details about these two subroutines are provided in Appendix D.2.2 and the proof of the Lemmas are postponed to Appendix H.Step 2: Subsequently, conditioned on their success, we provide a theoretical guarantee for the choice of the confidence radius ρ t (x, x) for ∆(x, x) at time step t in Lemma G.5. The proof is detailed in Appendix I.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 is presented in Appendix J. As the total number of time steps τ is upper bounded by a constant multiple of T τ , the high-probability upper bound on the stopping time τ is obtained. This finishes the proof of Theorem 3.2 (please refer to Appendix J).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 a changepoint within the last w CD samples but it fails to raise a changing alarm, and the type II error: a changepoint has not occurred but Algorithm 3 raises a changing alarm. We refer to the event Failed Alarm (FA) and the event False Alarm Error (FAE) as that a type I error occurs and that a type II error occurs, respectively: We upper bound the failure probability of Goodin Lemma G. P[FAE c ] ≥ 1 - τ γ Kδ FAE .Lemma G.1 can also be stated as, fix b,EQUATION150d , which indicates we can always decrease the error probability by enlarging the window size w.Assume c l is observable, i.e., θ * jc l ̸ = θ * jc l+1, and denote ĉl as the alarm time of c l from Algorithm 3.Lemma G.2. Conditional on FAE c , for any δ FA ∈ (0, 1), if ∆c-b 2 ≥ d w ln 2 δFA + d w ln 2 δFA 2 + 4d w ln 2 δFA , P c l ≤ ĉl ≤ c l + wγ 2 ĉl ≥ c l ≥ 1 -δ FA .In addition, P FA FAE c ≤ l τ δ FA .Lemma G.2 guarantees a prompt change alarm will be raised within wγ 2 time steps after a changepoint occurs. This also explains why wγ 2 samples are abandoned at line 16 of Algorithm 1 so that T t,j only keeps samples from context j. Lemma G.3. Conditional on FAE c and FA c , based on the conditions in Lemma G.1 and Lemma G.2,P [MI|FAE c , FA c ] ≤ l τ [(N -1)δ FA + Kδ FAE ] .The intuition of Lemma G.3 is simple: change alarm should not be raised when the samples are 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 3 and 4 can be concluded as follows Lemma G.4. Assume the instance satisfies Assumption 1,P [Good] ≥ 1 - δ 2τ * ≥ 1 - δ 2 .Step 2: To give an upper bound on T τ , we firstly prove that the estimate of ∆(x, x) at time t is within distance ρ t (x, x) from the ground truth w.h.p. Define the event CI as the estimates of all the mean gaps locate in the high-probability Confidence IntervalCI t := { ∆t (x, x) -∆(x, x) ≤ ρ t (x, x), ∀x, x ∈ X }and CI := t CI t , where ρ t is defined in (3.3).Lemma G.5.If T t ≥ 2Lmax 9 ln 2 δ d,T t , P CI t Good ≥ 1 -(Kδ v,Tt + N δ d,Tt + KN δ m,Tt) . In addition,P CI Good ≥ 1 - δ 2 .In addition to an estimation over the latent vector which is sufficient under the stationary case (α t in ρ t ), we also need to control the derivation between the empirical distribution pt and the ground truth p (β t in ρ t ), as well as the interactions between the latent vectors and the distribution (ξ t in ρ t ). This is reflected by Kδ v,Tt , N δ d,Tt and KN δ m,Tt which bound the the failure probability of Vector Estimation, Distribution Estimation and Residual Estimation, respectively.Step 3:Lemma G.6. Conditional on Good and CI, the recommended arm xε ∈ X ε and when Algorithm 1 terminates, the order of T t is upper bounded by (3.6) .The detailed proof is presented in Appendix J.As the output of Algorithms 3 and 4 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 in Appendix H.1, 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 1,P [Good] ≥ 1 - δ 2τ * ≥ 1 - δ 2 .Some notations are introduced first• θ 1:∞ := (θ * jt ) ∞ t=1 is the latent vector sequence. • ĉl indicates the time step when we raise alarm for the l th changepoint.According to the dynamics (see Dynamics 1) of the problem, at a changepoint c l ∈ C, the next latent vector will be sampled from P θ . Therefore, it may happen that θ * jc l = θ * jc l -1 , i.e, this changepoint c l is 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. In this section, we do not consider the randomness of θ 1:∞ , i.e., we consider a realization of the sequence. 4 The results do not involve any parameter depending on the specific sequence and thus can be applied to any latent vector sequence. P[FAE c ] ≥ 1 - τ γ Kδ FAE .Proof of Lemma G.1. Note that within a stationary segment of length t, the observations are i.i.d., and thus the time segments between two consecutive false alarm time {ĉ l -ĉl-1 } t l=1 (where ĉ0 = 0) are i.i.d. i.e., it is a renewal process. Thus, it is sufficient to bound the error probability under the stationary case, i.e. C = ∅ and θ 1:∞ = (θ * jt = θ * j1 ) ∞ t=1 . Assume that we are under a stationary segment of length t. We wish to upper bound the errorP[FAE] = P[ĉ 1 ≤ t]. This is given by Lemma H.1.Lemma H.1. Given w CD samples from the same context [(x s , Y s,xs )] w s=1 in a CD phase at time step t, Algorithm 3 makes a false alarm error with probability upper bounded by Kδ FAE , i.e.P [FAE t ] ≤ Kδ FAE if b ≥ 8d 3w ln 2 δFAE + 8d 3w ln 2 δFAE 2 + 24 w d ln 2 δFAE .Assume γ divides t. In the case of a stationary segment, the input samples to Algorithm 3 are[(x sγ , Y sγ,xsγ )] k+w-1 s=k t γk=1 if no changing alarm is raised (We ignore the initialization at Line 5 in Algorithm 1 for simplicity). Denote Γ i (t) := {kγ : k ≡ i mod w, kγ ≤ t}, i = 0, 1, . . . , w -1.Given any i = 0, . . . , w -1, for anyk 1 ̸ = k 2 ∈ Γ i (t), the two list of samples, [(x sγ , Y sγ,xsγ )] k1+w-1 s=k1 and [(x sγ , Y sγ,xsγ )] k2+w-1 s=k2, do not overlap (thus, they are independent). Therefore,P[k] := P[ĉ 1 = kγ + i, ĉ1 ∈ Γ i (t)] is a geometric distribution with parameter upper bounded by Kδ F AE . We haveP [ĉ 1 ∈ Γ i (t)] ≤ 1 -(1 -Kδ FAE ) |Γi(t)| .Hence, the cumulative false alarm error isP[FAE] = P [ĉ 1 ≤ t] = w-1 i=0 1 -(1 -Kδ FAE ) |Γi(t)| ≤ w-1 i=0 |Γ i (t)|Kδ FAE ≤ t γ Kδ FAE .Proof of Lemma H.1. According to Algorithm 3, given w CD samples from the same context [(x s , Y s,xs )] w s=1 and x ∈ X , we need to boundP   w 2 s=1 x ⊤ A(λ * ) -1 xs Y s,xs - w s= w 2 +1 x ⊤ A(λ * ) -1 xs Y s,xs ≥ w 2 b   .The proof is similar to Lemma E.1. For any s ∈ [ w 2 ] and s = s+ w 2 E x ⊤ A(λ * ) -1 xs Y s,xs -x ⊤ A(λ * ) -1 xs Y s,xs = 0 and x ⊤ A(λ * ) -1 xs Y s,xs -x ⊤ A(λ * ) -1 xs Y s,xs ≤ x ⊤ A(λ * ) -1 xs x⊤ s θ * js + x ⊤ A(λ * ) -1 xs η s + x ⊤ A(λ * ) -1 xs x⊤ s θ * js + x ⊤ A(λ * ) -1 xs η s ≤ 4d.By making use of (E.4),E x ⊤ A(λ * ) -1 xs Y s,xs -x ⊤ A(λ * ) -1 xs Y s,xs 2 = E x ⊤ A(λ * ) -1 xs Y s,xs 2 + E x ⊤ A(λ * ) -1 xs Y s,xs 2 -2E x ⊤ A(λ * ) -1 xs Y s,xs • x ⊤ A(λ * ) -1 xs Y s,xs ≤ 4d + 2E |x ⊤ θ * js • x ⊤ θ * js | ≤ 6d.According to the Bernstein's inequality,P   w 2 s=1 x ⊤ A(λ * ) -1 xs Y s,xs -x ⊤ A(λ * ) -1 xs+ w 2 Y s+ w 2 ,x s+ w 2 ≥ w 2 ϵ   ≤ 2 exp - 1 2 w 2 ϵ 2 w 2 • 6d + 4d 3 w 2 ϵ = 2 exp - w 2 ϵ 2 12d + 8d 3 ϵ.In order to upper bound the error probability by δ FAE , we need 2 exp - w 2 ϵ 2 12d + 8d 3 ϵ ≤ δ F AE ⇒ ϵ ≥ 4d 3 • w 2 ln 2 δ FAE + 4dP   2 w w 2 s=1 x ⊤ A(λ * ) -1 xs Y s,xs - 2 w w s= w 2 +1 x ⊤ A(λ * ) -1 xs Y s,xs ≥ b   ≤ δ FAE .A union bound over the K arms yields the final result.Lemma G.2. Conditional on FAE c , for any δ FA ∈ (0, 1),if ∆c-b 2 ≥ d w ln 2 δFA + d w ln 2 δFA 2 + 4d w ln 2 δFA , P c l ≤ ĉl ≤ c l + wγ 2 ĉl ≥ c l ≥ 1 -δ FA .In addition, P FA FAE c ≤ l τ δ FA .Proof of Lemma G.2. Conditioned on FAE c , the detection at the changepoints is independent. Thus we can assume there is only one changepoint c 1 within a certain number of consecutive time steps.Algorithm 3 is given w CD samples which are collected under two different context. Without loss of generality, we assume the sample selected at time c 1 is among the CD samples (otherwise, we can regard the time step of the first sample from the second context as c 1 ). We wish to boundP c 1 ≤ ĉ1 ≤ c 1 + γw 2 ĉ1 ≥ c 1which is the probability of the event that, after a changepoint occurs, a changing alarm will be raised within wγ 2 time steps (or w 2 CD samples). Here, ĉ1 ≥ c 1 can be guaranteed as we are conditioning on that there is no false alarm error (FAE c ).The event c 1 ≤ ĉ1 ≤ c 1 + γw 2 indicates, at least one of the CD sample list in(x c1+(s-k)γ , Y c1+(s-k)γ,x c 1 +(s-k)γ ) w s=1 w k= w 2 +1will 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, (x c1+(s-1-w 2 )γ , Y c1+(s-1-w 2 )γ,x c 1 +(s-1-w 2 )γ ) w s=1P c 1 ≤ ĉ1 ≤ c 1 + wγ 2 ĉ1 ≥ c 1 = P ∃k ∈ { w 2 + 1, . . . , w}, LCD w, b, [(x c1+(s-k)γ , Y c1+(s-k)γ,x c 1 +(s-k)γ )] w s=1 = True ĉ1 ≥ c 1 ≥ P LCD w, b, [(x c1+(s-1-w 2 )γ , Y c1+(s-1-w 2 )γ,x c 1 +(s-1-w 2 )γ )] w s=1 = True ĉ1 ≥ c 1 ≥ 1 -δ FA where ∆ c = max x∈X |x ⊤ (θ * j -θ * j )| and θ * j , θ * j are the latent vectors. Hence,P FA FAE c = 1 -P FA c FAE c ≤ 1 -(1 -δ FA ) lτ ≤ l τ δ FA Proof of Lemma H.2.According to the design of LCD, there exists an x ∈ X ,P   2 w w 2 s=1 x ⊤ A(λ * ) -1 xs Y s,xs - 2 w w s= w 2 +1 x ⊤ A(λ * ) -1 xs Y s,xs ≥ b   ≥ 1 -P w 2 s=1 x ⊤ A(λ * ) -1 xs Y s,xs - w s= w 2 +1 x ⊤ A(λ * ) -1 xs Y s,xs - w 2 x ⊤ (θ * j -θ * j ) ≥ w 2 b - w 2 x ⊤ (θ * j -θ * j ) = 1 -P w 2 s=1 x ⊤ A(λ * ) -1 xs Y s,xs -x ⊤ θ * j - w s= w 2 +1 x ⊤ A(λ * ) -1 xs Y s,xs -x ⊤ θ * j ≥ w 2 b - w 2 x ⊤ (θ * j -θ * j ) ≥ 1 -δ FAwhere the last inequality holds as P [MI|FAE c , FA c ] ≤ l τ [(N -1)δ FA + Kδ FAE ] .Proof of Lemma G.3. The error of the context alignment procedure can be derived from the FAE and FA analyses. Conditioned on FAE c , FA c and that the previous l -1 contexts are correctly identified, i.e., l-1 k=1 MI c k , we have the following statements. Firstly, according to Lemma H.1, the change alarm at Line 4 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 j (which will occur at most N -1 times), a change alarm will be raised with probability at least 1 -δ FA by Lemma G.2.Therefore, the error probability at c l is upper bounded byP MI l |FAE c , FA c , ∩ l-1k=1 MI c k ≤ (N -1)δ FA + Kδ FAE and by a union bound, the cumulative error probability bounded byP [MI|FAE c , FA c ] = 1 -P [MI c |FAE c , FA c ] (H.1) ≤ 1 -(1 -(N -1)δ FA -Kδ FAE ) lτ ≤ l τ ((N -1)δ FA + Kδ FAE ) .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 on the whole horizon up to time t as we assume there is no changepoint. In particular, there will be unused and redundant w 2 Kδ FAE errors budget for FAE at each changepoint, which accumulates to l τ w 2 Kδ FAE before time step τ . Therefore, the second error term in (H.1), l τ Kδ FAE , can be covered by the unused l τ w 2 Kδ FAE error budget from FAE, and thus it can be neglected in (H.1).Proof of Lemma G.4. According to Lemma G.1, G.2, G.3, Assumption 1 and Remark H.3, given a time τ , the total failure probability is upper bounded byP [Good c ] = P [FAE ∪ FA ∪ MI] (H.2) ≤ τ γ Kδ FAE + l τ δ FA + l τ • (N -1)δ FA = τ γ Kδ FAE + l τ N δ FA .In particular, when τ is upper bounded by τ * in Line 2 of Algorithm 1 τ ≤ τ * = c 0 N L max ε 2 ln N 2 KL max /Lemma G.5 is proved in this section. We will upper bound these three error terms (see (I.1)): VE error in App I.1, DE error in App I.2, RE error in App I.3, and finally we will prove Lemma G.5 which upper bounds the failure probability of CI at the end of this section.Lemma G.5.If T t ≥ 2Lmax 9 ln 2 δ d,T t , P CI t Good ≥ 1 -(Kδ v,Tt + N δ d,Tt + KN δ m,Tt) . In addition,P CI Good ≥ 1 - δ 2 .Given any two arms x, x ∈ X , by the triangular inequality, the deviation between ∆t (x, x) and ∆(x, x) can be upper bounded by three terms: the Vector-Estimation Error (VE) term, the Distribution-Estimation Error (DE) term, and the Residual Estimation Error (RE) term:| ∆t (x, x) -∆(x, x)| (I.1) = |(x -x) ⊤ Θt pt -(x -x) ⊤ Θp| ≤ N j=1 ∆t,j (x, x) -∆ j (x, x) pt,j VE term + N j=1 ∆clip 2 t,j (x, x)(p t,j -p j ) DE term + N j=1 ∆ j (x, x) - ∆clip 2 t,j (x, x) (p t,j -p j ) RE term, where a clip 2 := clip 2 (a) := min{max{a, -2}, 2} is a shorthand notation for the value of a that is clipped to the interval [-2, 2]. The reason the value ∆t,j (x, x) is clipped is the ground truth |∆ t,j (x, x)| ≤ 2.t := { ∆t (x, x) -∆(x, x) ≤ ρ t (x, x), ∀x, x ∈ X }, CI := t CI t ,and the confidence radiusρ t (x, x) := 2(α t + ξ t ) + N j=1 β t,j | ∆clip 2 t,j (x, x) + ζ t (x, x)|, (I.2)whereα t := 5 d T t ln 2 δ v,Tt , β t,j := 5 2 2ϕ t,j L max T t ln 2 δ d,Tt , ξ t := 25 √ 2 N L max T t ln 2 δ m,Tt, ϕ t,j := min 4 max pt,j , 25 4EQUATIONand ζ t (x, x) ∈ R can be any value. In particular, it can be the value that minimizes N j=1 β t,j | ∆t,j (x, x) + ζ t (x, x)| or it can be taken as ε. For simplicity, we will take ζ t (x, x) = arg min ζt(x,x)∈R N j=1 β t,j ( ∆t,j (x, x)+ζ t (x, x)) 2 = -N j=1 βt,j ∆t,j (x,x) N j=1 βt,j for a simple and effective analytic expression in the algorithm.For the VE term N j=1 ∆t,j (x, x) -∆ j (x, x) pt,j , note thatN j=1 ∆t,j (x, x) -∆ j (x, x) pt,j ≤ |x ⊤ ( Θt -Θ)p t | + |x ⊤ ( Θt -Θ)p t | Lemma I.1. Given x ∈ X and T t ≥ d 4 ln 2 δ v,T t , P |x ⊤ ( Θt -Θ)p t | ≥ α t Good ≤ δ v,TtProof of Lemma I.1. By the definition of the estimators in (3.2),x ⊤ ( Θt -Θ)p t = N j=1 x ⊤ ( θt,j -θ * j )p t,j = N j=1 x ⊤   1 T t,j s∈Tt,j A(λ * ) -1 x s Y s,xs -θ * j   T t,j T t = 1 T t N j=1 s∈Tt,j x ⊤ A(λ * ) -1 x s Y s,xs -x ⊤ θ * j By Lemma E.1, P |x ⊤ ( Θt -Θ)p t | ≥ α t θ 1:∞ , Good ≤ δ v,TtBy the property of conditional probability, we have the desired result.Therefore, conditional on Good, with probability at least 1 -Kδ v,Tt , VE ≤ 2α t for any x, x ∈ X . Proof of Lemma I.2. Given any j ∈ [N ], and the stationary segment l, we denote X j,l := Ll 1{θ * j l = θ * j } -p j Ll , where Ll is the total length of the Exp phases in the lth stationary segment. Note thatIE[X j,l |{ Ll } lt l=1 , Good] = 0, |X j,l | ≤ L max a.s. and Var[X j,l |{ Ll } lt l=1 , Good] = p j (1 -p j ) L2 l ≤ p j (1 -p j ) Ll L max . By Bernstein's inequality, P | lt l=1 X j,l | ≥ ϵ { Ll } lt l=1 , Good ≤ 2 exp - ϵ 2 2 lt l=1 Var[X j,l |Good] + 2 3 L max ϵ ⇒ P | 1 T t lt l=1 X j,l | ≥ ϵ { Ll } lt l=1 , Good ≤ 2 exp - T 2 t ϵ 2 2 lt l=1 Var[X j,l |Good] + 2 3 L max T t ϵ As T t,j = lt l=1 Ll 1{θ * j l = θ * j }, T t = lt l=1Ll and lt l=1 Ll = T t , we haveP |p t,j -p j | ≥ ϵ { Ll } lt l=1 , Good ≤ 2 exp - T 2 t ϵ 2 2 lt l=1 Var[X j,l |{ Ll } lt l=1 , Good] + 2 3 L max T t ϵ ≤ 2 exp - T 2 t ϵ 2 2 lt l=1 p j (1 -p j ) Ll L max + 2 3 L max T t ϵ ≤ 2 exp - T t ϵ 2 2p j (1 -p j )L max + 23 L max ϵ As the last bound is independent of { Ll } lt l=1 , we haveP |p t,j -p j | ≥ ϵ Good ≤ 2 exp - T t ϵ 2 2p j (1 -p j )L max + 23 L max ϵ If we want to upper bound the above by δ d,Tt ∈ (0, 1), i.e.,2 exp - T t ϵ 2 2p j (1 -p j )L max + 2 3 L max ϵ ≤ δ d,Ttwe requireϵ ≥ 1 3 L max ln 2 δ d,T t + 1 3 L max ln 2 δ d,T t 2 + 2T t p j (1 -p j )L max ln 2 δ d,T t T t (I.3)In particular,ϵ = βt,j := 5 2 max L max 3T t ln 2 δ d,Tt , 2p j (1 -p j )L max T t ln 2 δ d,Ttsatisfies the condition, we have P |p t,j -p j | ≥ βt,j Good ≤ δ d,Tt .(I.4)A problem here is we do not have access to p j during the dynamics, therefore, we adopt Lemma K.1 to further upper bound βt,j by β t,j .Lemma K.1. Given any j ∈ [N ] andT t ≥ 2Lmax 9 ln 2 δ d,T t, βt,j ≤ β t,j .Therefore,P |p t,j -p j | ≥ β t,j Good ≤ δ d,Tt .In addition, with probability at least 1 -N δ d,Tt , we can upper bound DE term as:N j=1 ∆clip 2 t,j (x, x)(p t,j -p j ) = N j=1 ∆clip 2 t,j (x, x) + ζ t (x, x) (p t,j -p j ) (I.5) ≤ N j=1 β t,j ∆clip 2 t,j (x, x) + ζ t (x, x)where ζ t (x, x) ∈ R can be any value.RE is composed by the product of two deviations, i.e., ∆ j (x, x) -∆clip 2 t,j (x, x) and (p t,j -p j ), as the time step t becomes large, we expect it will converge to zero fast. Thus, it is sufficient to have a coarse estimation of it.Lemma I.3. For any x ∈ X , conditional on that |p t,j -p j | ≤ β t,j , ∀j ∈ [N ],P   N j=1 ∆ j (x, x) - ∆clip 2 t,j (x, x) (p t,j -p j ) ≥ ξ t Good   ≤ N δ m,Ttwhereξ t := 25 √ 2 N Lmax Tt ln 2 δ m,T t .Proof of Lemma I.3. According to Lemma E.1, for any x ∈ X , j ∈ [N ] we haveP |x ⊤ (θ * j -θt,j )| ≥ 5 d T t,j ln 2 δ m,Tt Good ≤ δ m,Tt (I.6) if T t,j ≥ d 4 ln 2 δ m,T t. Note the fact that ∆ j (x, x) ∈ [-2, 2], hence, ∆ j (x, x) -∆clip 2 t,j (x, x) (p t,j -p j ) ≤ j:ψt,j,1> pt,j ∆ j (x, x) -∆clip 2 t,j (x, x) β t,j + j:ψt,j,1= pt,j , ψt,j,2> pt,j ∆ j (x, x) -∆clip 2 t,j,2 (x, x) β t,j + j:ψt,j,2= pt,j∆ j (x, x) - ∆clip 2 t,j (x, x) ≤ ∆ j (x, x) -∆t,j (x, x) ≤ |x ⊤ (θ * j -θt,j )| + |x ⊤ (θ * j -θt,EQUATION≤ j:ψt,j,1> pt,j ∆ j (x, x) -∆clip 2 t,j (x, x) β t,j + j:ψt,j,1= pt,j , ψt,j,2> pt,j Proof of Lemma G.5. By Lemma I.1, I.2 and I.3, conditional on Good, with probability at least 1 -(Kδ v,Tt + N δ d,Tt + KN δ m,Tt ), ∆t (x, x) -∆(x, x) ≤ ρ t (x, x). This finishes the proof of the first result in Lemma G.5.EQUATIONWe then accumulates all the error probabilities. By the choices ofδ v,Tt = δ 15KT 3 t , δ d,Tt = δ 15N T 3 t , δ m,Tt = δ 15KN T 3 t , ∞ Tt=1 Kδ v,Tt + N δ d,Tt + KN δ m,Tt = ∞ Tt=1 K • δ 15KT 3 t + N • δ 15N T 3 t + KN • δ 15KN T 3 t = ∞ Tt=1 3δ 15T 3 t ≤ δ 4Note that there is an reversion step at Line 18 Algorithm 1, for each T ∈ N, there are at most two time steps t 1 < t 2 with T t1 = T t2 . Therefore,∞ t=1 Kδ v,Tt + N δ d,Tt + KN δ m,Tt ≤ 2 ∞ Tt=1 Kδ v,Tt + N δ d,Tt + KN δ m,Tt ≤ δ 2This proves the second statement.J Upper Bound of PSεBAI: Proof of Theorem 3.2Theorem 3.2 is proved in this section by three steps.• Firstly, we show that the recommended arm xε is an ε-best arm upon the termination of the algorithm in Lemma J.1. • Secondly, we present a sufficient condition for the termination of the algorithm in terms of T t in Lemma G.6. • Lastly, we show that T τ is bounded by a constant fraction of τ and thus, obtain an upper bound on τ .Step 1:According to Lemma G.5, CI t holds with probability 1-(Kδ v,Tt +N δ d,Tt +KN δ m,Tt ). Conditional on the good event Good in (G.1) and the event CI t (the mean gaps are well approximated at time step t), we expect the recommended arm will be an ε-optimal arm. This is formalized in the following lemma.Lemma J.1. Conditional on Good and CI t , if the algorithm stops at time step t, the recommended arm xε = x * t is an ε-best arm.Proof of Lemma J.1. If xε = x * , the lemma holds.If xε ̸ = x * , according to the termination condition (3.4)min x:x̸ =xε ∆t (x ε , x) -ρ t (x ε , x) > -ε we have ∆(x ε , x * ) ≥ ∆t (x ε , x * ) -ρ t (x ε , x * ) ≥ min x:x̸ =xε ∆t (x ε , x) -ρ t (x ε , x) > -εwhere the first inequality holds due to CI t . This indicates ∆(x * , xε ) ≤ ε and thus the recommended arm xε = x * t is an ε-best arm.Step 2:Lemma G.6. Conditional on Good and CI, the recommended arm xε ∈ X ε and when Algorithm 1 terminates, the order of T t is upper bounded by (3.6).Proof of Lemma G.6. By Lemma J.1, xε ∈ X ε . Note that for any x ̸ = xε , when2ρ t (x, xε ) ≤ ∆(x, xε ) + ε, xε ̸ = x * and x = x * , ρ t (x ε , x) + ρ t (x * , x) ≤ ∆(x * , x) + ε, otherwise. (J.1)By utilizing CI t , we have         ∆t (x ε , x * ) -ρ t (x ε , x * ) ≥ ∆t (x * , xε ) -ρ t (x ε , x * ) ≥ ∆ t (x * , xε ) -2ρ t (x * , xε ) ≥ -ε, xε ̸ = x * and x = x * , ∆t (x ε , x) -ρ t (x ε , x) ≥ ∆t (x * , x) -ρ t (x ε , x) ≥ ∆(x * , x) -ρ t (x * , x) -ρ t (x ε , x) ≥ -ε, otherwise.Therefore, if (J.1) hold for all x ̸ = xε , the algorithm must have stopped, i.e., it is sufficient to have the following for any x ̸ = xε :     ρ t (x * , xε ) ≤ ∆(x * , xε ) + ε 2 , xε ̸ = x * and x = x * , ρ t (x ε , x) ≤ ∆(x * , x) + ε 2 , ρ t (x * , x) ≤ ∆(x * , x) + ε 2 , otherwise.Lemma J.2 gives an upper bound on the total number of time steps in Exp phases at which (J.1) must hold for any two arms x ε ∈ X ε , x ∈ X \ {x ε }.Lemma J.2. For any two arms (x ε , x), where x ̸ = x ε , x * , whenT t = 6400 ln 6400 • d (∆(x * , x) + ε) 2 ln Kd/ (∆(x * , x) + ε) 2 δ + 6400 ln 6400 • H DE (x ε , x) ln N H DE (x ε , x) δ + 3200 √ 2 ln 3200 √ 2 • N L max ∆(x * , x) + ε ln KN Lmax ∆(x * ,x)+ε δ (J.2) = Õ d (∆(x * , x) + ε) 2 ln 1 δ + H DE (x ε , x) ln 1 δ + N L max ∆(x * , x) + ε ln 1 δwhereH DE (x ε , x) := L max (∆(x * , x) + ε) 2   N j=1 min 16p j , 1 4 |∆ j (x ε , x) + ε|   2 ,we must haveEQUATIONBy taking the maximum of (J.2) over all ε-best arms and the suboptimal arms, we getT := max xε∈Xε,x̸ =xε,x * 6400 ln 6400 • d (∆(x * , x) + ε) 2 ln Kd/ (∆(x * , x) + ε) 2 δ + 6400 ln 6400 • H DE (x ε , x) ln N H DE (x ε , x) δ + 3200 √ 2 ln 3200 √ 2 • N L max ∆(x * , x) + ε ln KN Lmax ∆(x * ,x)+ε δ (J.3) = Õ max xε∈Xε,x̸ =xε,x * d (∆(x * , x) + ε) 2 ln 1 δ + H DE (x ε , x) ln 1 δ + N L max ∆(x * , x) + ε ln 1 δ . Proof of Lemma J.2. Let c v , c d , c m ∈ (0, 1) be constants, satisfying c v + c d + 2c m = 1. By the definition of ρ t (x ε , x) in (3.3), it is sufficient to have                  2α t ≤ c v ∆(x * , x) + ε 2 N j=1 β t,j | ∆clip 2 t,j (x ε , x) + ζ t (x ε , x)| ≤ (c d + c m ) ∆(x * , x) + ε 2 2ξ t ≤ c m ∆(x * , x) + ε 2 where we take ζ t (x ε , x) = ε for theoretical simplicity, but we adopt ζ t (x, x) = arg min ζt(x,x)∈R N j=1 β t,j ( ∆t,j (x, x) + ζ t (x, x)) 2 = - N j=1 βt,j ∆t,j (x,x) N j=1 βt,jin the algorithm, which still enjoys the theoretical guarantee.VE Term According to the definition of α t , we need to bound:EQUATIONBy a coarse estimation, it is sufficient to haveT t ≥ cv d (∆(x * , x) + ε) 2 ln Kd/ (∆(x * , x) + ε) 2 δ = O d (∆(x * , x) + ε) 2 ln Kd/ (∆(x * , x) + ε) 2 δwhere cv = 6400c 2 v ln 6400 c 2 v .The difficulty lies at the DE term.N j=1 β t,j | ∆clip 2 t,j (x ε , x) + ζ t (x ε , x)| ≤ N j=1 β t,j | ∆clip 2 t,j (x ε , x) + ε| ≤ j:ψt,j > pt,j β t,j | ∆clip 2 t,j (x ε , x) + ε| + j:ψt,j = pt,j β t,j |∆ j (x ε , x) + ε| + β t,j | ∆clip 2 t,j (x ε , x) -∆ j (x ε , x)| ≤ j:ψt,j > pt,j β t,j (2 + ε) + j:ψt,j = pt,j β t,j | ∆clip 2 t,j (x ε , x) -∆ j (x ε , x)| + j:ψt,j = pt,j β t,j |∆ j (x ε , x) + ε| ≤ 2ξ t + j:ψt,j = pt,j β t,j |∆ j (x ε , x) + ε|We will upper bound 2ξ t by c m ∆(x * ,x)+ε 2 first; the second term will be included in the RE term and analyzed later. Therefore, it is sufficient to have j:ψt,j = pt,jβ t,j |∆ j (x ε , x) + ε| ≤ c d ∆(x * , x) + ε 2 (J.4)By the definition of β t,j in (I.2) and Lemma K.3, we getEQUATIONTherefore, in order for (J.4) to hold, it is sufficient to have j:ψt,j,2= pt,j 5 22 min 16p j , 1 4 L max T t ln 2 δ d,Tt |∆ j (x ε , x) + ε| ≤ c d ∆(x * , x) + ε 2 ⇔ 5 2 2L max T t ln 2 δ d,Tt j:ψt,j,2= pt,j min 16p j , 1 4 |∆ j (x ε , x) + ε| ≤ c d ∆(x * , x) + ε 2 ⇐ 5 2 2L max T t ln 2 δ d,Tt N j=1 min 16p j , 1 4 |∆ j (x ε , x) + ε| ≤ c d ∆(x * , x) + ε 2 ⇐ T t ≥ cd H DE (x ε , x) ln N H DE (x ε , x) δ = O H DE (x ε , x) ln N H DE (x ε , x) δwhere cd = 100c 2 d ln 100 c 2 d .RE Term By the definition of ξ t in (I.2), it is sufficient to have25 √ 2 N L max T t ln 2 δ m,Tt ≤ c m ∆(x * , x) + ε 2 ⇐ T t ≥ cm • N L max ∆(x * , x) + ε ln KN Lmax ∆(x * ,x)+ε δ = O N L max ∆(x * , x) + ε ln KN Lmax ∆(x * ,x)+ε δ where cm = 400 √ 2 cm ln 400 √ 2 cm . By taking c v = 3 4 , c d = 18 and c m = 1 8 , the upper bound on T t can be concluded asT t = 6400 ln 6400 • d (∆(x * , x) + ε) 2 ln Kd/ (∆(x * , x) + ε) 2 δ + 6400 ln 6400 • H DE (x ε , x) ln N H DE (x ε , x) δ + 3200 √ 2 ln 3200 √ 2 • N L max ∆(x * , x) + ε ln KN Lmax ∆(x * ,x)+ε δ = O d (∆(x * , x) + ε) 2 ln Kd/ (∆(x * , x) + ε) 2 δ +H DE (x ε , x) ln N H DE (x ε , x) δ + N L max ∆(x * , x) + ε ln KN Lmax ∆(x * ,x)+ε δ = Õ d (∆(x * , x) + ε) 2 ln 1 δ + H DE (x ε , x) ln 1 δ + N L max ∆(x * , x) + ε ln 1 δ .Step 3: Theorem 3.2. Define the context distribution estimation (DE) hardness parameterH DE (x ε , x) := L max (∆(x * , x) + ε) 2 H(x ε , x)where H(x ε , x) := N j=1 min {16p j , 1/4}|∆ j (x ε , x) + ε| 2 . Under Assumption 1, with probability at least 1 -δ, PSεBAI identifies an ε-optimal arm and its sample complexity isÕ max xε∈Xε x̸ =xε,x * d (∆(x * , x) + ε) 2 ln 1 δ TV(x) + H DE (x ε , x) ln 1 δ TD(xε,x) + N L max ∆(x * , x) + ε ln 1 δ TR(x).(3.6)Proof of Theorem 3.2. By Assumption 1, and the choice of the parameters, Lemma G.4 indicates Good is guaranteed with probability at least 1 -δ 2 . Note that some arm pulls are not counted in T t :• In every γ time steps, Algorithm 1 enters the CD phase to select a CD sample.• When a changepoint is detected, Algorithm 1 steps into the CA phase, where w 2 arms are sampled in Algorithm 4.• During the CA phase, we abandon wγ 2 samples. Therefore, when t is large (or after the first stationary segment)t ≤ T t • γ γ -1 L min L min -wγ -w 2 ≤ T t • γ γ -1 L min L min -3wγ 2 .(J.6)As γ ≥ 2 and wγ are set to be upper bounded by Lmin 3 , so the fractions above is upper bounded by an absolute constant 4, e.g., with γ = 2 and w = Lmin 6 , the constant is 4. Therefore, t is of the same order as T t . By Lemma G.6, (3.6) holds with probability 1 -δ. EQUATIONThe proof is scheduled in 2 steps.Step 1: Upper bound If T t,j = 0, i.e., the latent context j has never been observed and pt,j = 0, we have2pj (1-pj )Lmax Tt ln 2 δ d,T t . When Lmax 3Tt ln 2 δ d,T t ≤ 2pj (1-pj )Lmax Tt ln 2 δ d,T t , we have βt,j = 5 2 2p j (1 -p j )L max T t ln 2 δ d,Tt As p j (1 -p j ) ≤ 1 4 , ∀p j ∈ (0,EQUATIONL max T t ln 2 δ d,TtTake the trivial bound into consideration and observe that ϕ t,j = min{ 25Lmax Tt ln 2 δ d,T t , 1 4 } and that 25 8L max T t ln 2 δ d,Tt ≤ 25 √ 2L max 2T t ln 2 δ d,Tt = 5 2 2ϕ t,j L max T t ln 2 δ d,Tt.Thus, (K.1) also holds for T t,j = 0.To conclude, we have= 5 2 max L max 3T t ln 2 δ d,Tt , 2p j (1 -p j )L max T t ln 2 δ d,Tt ≤ 5 2 max L max 3T t ln 2 δ d,Tt , 2ϕ t,j L max T t ln 2 δ d,TtStep 2: Simplify the bound. Recall that ϕ t,j = min 4 max pt,j , 25 4EQUATIONAs T t ≥ 2Lmax 9 ln 2 δ d,T t, we haveL max 3T t ln 2 δ d,Tt ≤ 2 • 1 4 L max T t ln 2 δ d,TtAccording to the definition of ϕ, if pt,j ≥ 25 4 Lmax Tt ln 2 δ d,T t , we haveL max 3T t ln 2 δ d,Tt ≤ 5 √ 2L max T t ln 2 δ d,Tt ≤ 2 • 4p t,j L max T t ln 2 δ d,Tt If pt,j ≤ 25 4 Lmax Tt ln 2 δ d,T t , we have L max 3T t ln 2 δ d,Tt ≤ 25 √ 2L max T t ln 2 δ d,Tt = 2L max T t ln 2 δ d,Tt • 25 L max T t ln 2 δ d,Tt Thus max L max 3T t ln 2 δ d,Tt , 2ϕ t,j L max T t ln 2 δ d,Tt = 2ϕ t,j L max T t ln 2 δ d,TtThis gives us the desired result. and T t,j > 0, we haveEQUATIONEQUATIONEQUATIONEQUATIONProof of Lemma K. Thus pt,j = ψ t,j ≤ 4p j , and ϕ t,j ≤ min 16p j , 1 4 .L Upper Bound of PSεBAI + : Proof of Theorem 3.3Theorem 3.3. The PSεBAI + algorithm is (ε, δ)-PAC and its expected sample complexity isÕ min max xε∈Xε,x̸ =xε,x * T V (x) + T D (x ε , x) + T R (x), T N V + T N D .Proof. We let τ 1 denote the stopping time of PSεBAI, τ 2 denote the stopping time of NεBAI, and τ denote the stopping time of PSεBAI + when an identical sequence of samples and returns are applied to them. By the design of these algorithms, we have τ ≤ min{τ 1 , τ 2 }.Part I: Prove that P(x ε / ∈ X ε ) ≤ δ.Let event E 1 = 1{τ 1 < τ 2 } ∩ 1{PSεBAI returns arm x ε when it terminates}. Recall that ẋε denotes the recommended arm of NεBAI when it terminates and xε denotes the recommended arm of PSεBAI + when it terminates. The design of algorithms indicates that: xε = x ε when E 1 occurs, and xε = ẋε when E c 1 occurs. Moreover, with the performance guarantees of NεBAI and PSεBAI(shown in Proposition 3.1 and Theorem 3.2 individually), we haveP[x ε / ∈ X ε ] = P[x ε / ∈ X ε |E 1 ] • P[E 1 ] + P(x ε / ∈ X ε |E c 1 ] • P[E c 1 ] = P[x ε / ∈ X ε |E 1 ] • P[E 1 ] + P[ ẋε / ∈ X ε |E c 1 ] • P[E c 1 ] ≤ δ • P[E 1 ] + δ • P[E c 1 ] = δ • (P[E 1 ] + P[E c 1 ]) = δ.Part II: Derive the expected sample complexity of PSεBAI + .We first derive the conditional expectation of the stopping time of PSεBAI. By the same argument as in (J. According to Lemma G.6 and Lemma G.6, when both events Good and CI occur, PSεBAI terminates with T τ1 satisfying T τ1 ≤ T , where T is defined in (J.3) and as below:T := max xε∈Xε,x̸ =xε,x * 6400 ln 6400 • d (∆(x * , x) + ε) 2 ln Kd/ (∆(x * , x) + ε) 2 δ + 6400 ln 6400 • H DE (x ε , x) ln N H DE (x ε , x) δ + 3200 √ 2 ln 3200 √ 2 • N L max ∆(x * , x) + ε ln KN Lmax ∆(x * ,x)+ε δ .Given time step t with T t ≥ 2 T (thus t ≥ 8 T ), we will upper bound P[τ 1 > t] in the following. We firstly upper bound P [T τ1 > T t ]. Note thatP [T τ1 > T t ] = P T τ1 > T t |T τ1 ≥ T t 2 + 1 P T τ1 ≥ T t 2 + 1 + P T τ1 > T t |T τ1 < T t 2 + 1 P T τ1 < T t 2 + 1 ≤ P T τ1 > T t |T τ1 ≥ T t 2 + 1 .If PSεBAI fails to terminate with T τ1 ≤ Tt 2 , it implies that event Good s∈I CI s fails, whereI = {s : Tt 2 + 1 ≤ T s ≤ T t }. Hence, P [T τ1 > T t ] ≤ P T τ1 > T t T τ1 ≥ T t 2 + 1 ≤ P Good c s∈I CI c s ≤ P [Good c ] + P Good s∈I CI c s ≤ P [Good c ] + P s∈I CI c s Good (a) ≤ δ 2τ * + 2 Tt Ts=Tt/2+1 (Kδ v,Ts + N δ d,Ts + KN δ m,Ts ) (b) ≤ δ 2τ * + 2 Tt Ts=Tt/2+1 δ 5T 3 s ≤ δ 2τ * + 2 Tt Tt/2 δ 5x 3 dx = δ 2τ * + 3δ 5T 2 t ,where (a) is obtained by applying Lemma G.5 to time steps in I ∩ T t (i.e., the Exp time steps in I) and note that there are at most two time steps t 1 < t 2 with T t1 = T t2 due to the reversion step; (b) is derived by substituting δ v,Tt = δ15KT 3 t , δ d,Tt = δ 15N T 3 t , δ m,Tt = δ 15KN T 3 twhich are used to define the confidence radius ρ in (3.3) . By using the fact that 4T τ1 ≥ τ 1 , for any T t ≥ 2 T , we haveP [τ 1 > 4T t ] ≤ P [T τ1 > T t ] ≤ δ 2τ * + 3δ 5T 2 t ⇒ P [τ 1 > 4T t + i] ≤ δ 2τ * + 3δ 5T 2 t , i = 0, 1, 2, 3 ⇒ P [τ 1 > t] ≤ δ 2τ * + 48δ 5(t -4) 2 , ∀8 T ≤ t ≤ τ * .This indicates for t ≥ 8 T , the probability that PSεBAI does not stop after t time steps is δ 2τ * + 48δ 5(t-4) 2 . Therefore, by Tonelli's Theorem, we haveE[τ 1 |8 T < τ 1 ≤ τ * ] ≤ τ * -1 t=8 T P[τ 1 > t] ≤ τ * -1 t=8 T δ 2τ * + 48δ 5(t -4) 2 ≤ 1 + τ * -1 8 T -1 48δ 5(t -4) 2 dt ≤ 2. (L.1)Next, we bound Eτ , the expected sample complexity of PSεBAI + . Eτ can be decomposed as below:Eτ ≤ 8 T + E[τ |8 T < τ ≤ τ * ] + E[τ |τ > τ * ]. (L.2) Since τ = min{τ 1 , τ 2 } and P[min{τ 1 , τ 2 } > t] ≤ P[τ 1 > t] for all t, we have E[τ |8 T < τ ≤ τ * ] = τ * -1 t=8 T P[τ > t] = τ * -1 t=8 T P[min{τ 1 , τ 2 } > t] ≤ τ * -1 t=8 T P[τ 1 > t] = E[τ 1 |8 T < τ 1 ≤ τ * ]. (L.3)Besides, since PSεBAI will terminate after τ * time steps, i.e., P(τ 1 ≤ τ * ) = 1. We haveE[τ |τ ≥ τ * ] = ∞ t=τ * P[τ ≥ t] ≤ 1 + ∞ t=τ * +1 P[τ 2 ≥ t] = 1 + E[τ 2 |τ 2 > τ * ]. (L.4) Lemma F.1 indicates that P[τ 2 ≥ t] ≤ δ (α-1)C3(t/2) 2 for all t ≥ T 0 , whereT 0 = 768(8L max + 25d) (ε + ∆ min ) 2 ln 768KC 3 (8L max + 25d) (ε + ∆ min ) 2 δ , C 3 = ∞ n=1 n -3 .Since the order of T 0 is apparently larger than τ * , we have T 0 ≤ τ * . Then, with the same method as in the proof of Proposition 3.1, the conditional sample complexity of NεBAI can be bounded as follows:E[τ 2 |τ 2 > τ * ] ≤ +∞ τ * P(τ 2 ≥ x) dx ≤ +∞ τ * δ (α -1)C 3 (x/2) 2 dx = δ C 3 τ * . (L.5)Substituting terms in (L.2) with (L.1), (L.3), (L.4) and (L.5), we haveEτ ≤ 8 T + 3 + δ C 3 τ * . Besides, Eτ ≤ Eτ 2 (a) ≤ T 0 + δ (α -1)(α -2)(T 0 /2) α-2 ,Where (a) is shown in (F.1).Eτ ≤ min 8 T + 3 + δ C 3 τ * , 8 T + 3 + δ C 3 τ * .M Analysis of Lower Bound: Proof of Theorem 4.1The dynamics for under our PSLB model is displayed in Dynamics 1.Dynamics 1 Dynamics for piecewise-stationary linear bandits 1: The instance: Λ = (X , Θ, P θ , C) 2: while the algorithm does not stop at time step t do3: if t ∈ C then 4:The environment samples θ * jt ∼ P θ 5: end ifThe agent samples an arm x t based on the history up to time t -1.The reward Y t,xt = x ⊤ t θ * jt + η t is revealed to the agent. 10: end while 11: Recommend an ε-best arm xε .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 1):• Dynamics 2: the agent observes the index of current context j t , and the environment reduces to contextual linear bandits; the definition of Dynamics 2 and the lower bound under it are detailed in Appendix M.1.• Dynamics 3: the agent observes the changepoints in C and context vector θ * jt 's, and hence she solely needs to estimate the distribution of contexts; the definition of Dynamics 3 and the lower bound under it are detailed in Appendix M.2.We first derive a lower bound for (ε, δ)-BAI algorithms in Dynamics 2, that is, in contextual linear bandits. Corollary M.1. For any (ε, δ)-PAC algorithm π, there exists an instance Λ = (X , Θ, P θ , C) with Dynamics 2 such thatE[τ ] ≥ T ε (Λ) log 1 2.4δ.whereT ε (Λ) -1 = max {vj ∈∆ X } N j=1 min Λ ′ ∈AltΘ(Λ) N j=1 p j x∈X v j,x (x ⊤ (θ * j -θ ′ j )) 2 2is defined in Theorem 4.1. In addition, when|X ε | = 1, T ε (Λ) = min {vj ∈∆ X } N j=1 max x̸ =x * N j=1 p j ∥x * -x∥ 2 A(vj ) -1 (∆(x * , x) + ε) 2 .This lower bound generalizes the result of [16] to the linear bandit setting.We next study Dynamics 3. In this setting, the agent solely needs to estimate the distribution of contexts P θ with context samples. Once the agent obtains a good estimate of P θ , she can identify an ε-optimal arm w.h.p. Hence, the lower bound on the complexity of an (ε, δ)-BAI algorithm is the product of the minimum length of a stationary segment and the minimum number of context samples/changepoints needed for distribution estimation. Corollary M.2. For any (ε, δ)-PAC algorithm π, there exists an instance Λ = (X , Θ, P θ , C) with Dynamics 3 such that Eτ ≥ c N C , where c N C is the N th C changepoint in the changepoint sequence C.Altogether, the sample complexity of an (ε, δ)-BAI algorithm in Dynamics 2 and 3 build up the lower bound in Theorem 4.1.In this section, we consider a sub-problem where the index of the current context j t is revealed at each time step t. The original piecewise-stationary problem becomes a contextual problem whose dynamics is presented in Algorithm 2. As more information is provided to the agent, the lower Dynamics 2 Dynamics for contextual linear bandits 1: The instance: Λ = (X , Θ, P θ , C) 2: while the algorithm does not stop at time step t do3: if t ∈ C then 4:The environment samples θ * jt ∼ P θ 5: Reveal j t to the agent.The agent samples an arm x t based on the history up to time t -1.The reward Y t,xt = x ⊤ t θ * jt + η t is revealed to the agent. 11: end while 12: Recommend an ε-best arm xε . bound for this sub-problem is smaller than the one for the original problem. Corollary M.1. For any (ε, δ)-PAC algorithm π, there exists an instance Λ = (X , Θ, P θ , C) with Dynamics 2 such thatE[τ ] ≥ T ε (Λ) log 1 2.4δ.whereT ε (Λ) -1 = max {vj ∈∆ X } N j=1 min Λ ′ ∈AltΘ(Λ) N j=1 p j x∈X v j,x (x ⊤ (θ * j -θ ′ j )) 2 2is defined in Theorem 4.1. In addition, when|X ε | = 1, T ε (Λ) = min {vj ∈∆ X } N j=1 max x̸ =x * N j=1 p j ∥x * -x∥ 2 A(vj ) -1 (∆(x * , x) + ε) 2 .For simplicity, we consider the noise model is the Clipped Gaussian Distribution CN (1), i.e., η ∼ CN (1) or P η = CN (1). Definition M.3. A random variable x follows the Clipped Gaussian Distribution with parameter σ, denoted by x ∼ CN (σ), if it has the probability distribution functionf (x) = 1 (2Φ(σ) -1) • √ 2πσ 2 exp - x 2 2σ 2 , ∀x ∈ [-1, 1]where Φ(x) is the cumulative distribution function of the standard Gaussian distribution.Some notations are introduced here:• Given an instance Λ = (X , Θ, P θ , C), define the alternative instance Λ ′ = (X , Θ ′ , P θ ′ , C) with respect to Λ, whereΘ ′ = (θ ′ 1 , . . . , θ ′ n ) ∈ R d×N and P θ ′ [θ ′ j ] = P θ [θ * j ], s.t. there ∃x ∈ X \ X ε , ∀x ε ∈ X ε , s.t., x ⊤ ε E θ ′ ∼P θ ′ < x ⊤ E θ ′ ∼P θ ′ -ε.We denote the set containing all the alternative instance (w.r.t. Λ) as Alt Θ (Λ).• H t = (x s , Y s,xs , j s ) t-1s=1 is the observation history up to but not include time t. • N j,x (t) = t s=1 1{x s = x, j s = j} is the number of times arm in which x is sampled under context j. And N j (t) := x∈X N j,x (t) is the number of times in which context j appears. • kl(p, q) = KL(Bern(p), Bern(q)) is the KL divergence between two Bernoulli distributions with parameters p and q.Therefore, the probability of the observation historyH t+1 = (x s , Y s,xs , j s ) t s=1 is P πΛ (x s , Y s,xs , j s ) t s=1 = lt l=1 P θ [θ * jc l ] L l -1 s=0 π(x c l +s |H c l +s )P η (Y c l +s,xc l +s |x c l +s , θ * jc l )Then the log-likelihood between the two instance up to time t, given the observed data, isL t (x s , Y s,xs , j s ) t s=1= logEQUATION= logEQUATION= lt l=1 L l -1 s=0 x ⊤ c l +s ϑ jc l (2η c l +s + x ⊤ c l +s ϑ jc l ) 2 where (a) utilizes P θ [θ * jc l ] = P θ ′ [θ ′ jc l], (b) makes use of the relationship between the arm and observation and in (c)ϑ jc l := θ * jc l -θ ′ jc l. Thus, the expectation of the log-likelihood is (in the following, the expectation is taken under instance Λ and algorithm π)E[L t ] = E lt l=1 L l -1 s=0 x ⊤ c l +s ϑ jc l (2η c l +s + x ⊤ c l +s ϑ jc l ) 2 = E lt l=1 L l -1 s=0 ϑ ⊤ jc l x c l +s x ⊤ c l +s ϑ jc l 2 = 1 2 E lt l=1 ϑ ⊤ jc l L l -1 s=0 x c l +s x ⊤ c l +s ϑ jc l = 1 2 E   x∈X 1{x c l +s = x} N j=1 1{j c l = j} lt l=1 ϑ ⊤ jc l L l -1 s=0 x c l +s x ⊤ c l +s ϑ jc l   = 1 2 x∈X N j=1 E [N j,x (t)] ϑ ⊤ j xx ⊤ ϑ j = 1 2 E[t] N j=1 E[N j (t)] E[t] x∈X E [N j,x (t)] E[N j (t)] ϑ ⊤ j xx ⊤ ϑ j (M.8)As the lengths of all the stationary phases are upper bounded, i.e., L l ≤ L max , ∀l ∈ N, then by Wald's Lemma,E[N j (t)] E[t] = E[t]P θ [θ * j ] E[t] = P θ [θ * j ] = p j (M.9)The above also holds for t = τ where τ is a stopping time. According to Lemma 19 in [31] ,E[L τ ] ≥ sup E∈Fτ kl(P πΛ [E], P πΛ ′ [E]) (M.10)where F τ = σ(H τ +1 ). In addition, let E = {the recommended arm xε / ∈ X ε }, as the algorithm π is δ-PAC, thenkl(P πΛ [E], P πΛ ′ [E]) ≥ kl(1 -δ, δ) ≥ log 1 2.4δ (M.11)From (M.8), (M.9), (M.10) and (M.11), we conclude that1 2 E[τ ] N j=1 p j x∈X E [N j,x (τ )] E[N j (τ )] ϑ ⊤ j xx ⊤ ϑ j ≥ log 1 2.4δ ⇒ min Λ ′ ∈AltΘ(Λ) 1 2 E[τ ] N j=1 p j x∈X E [N j,x (τ )] E[N j (τ )] ϑ ⊤ j xx ⊤ ϑ j ≥ log 1 2.4δ ⇒ max {vj ∈∆ X } N j=1 min Λ ′ ∈AltΘ(Λ) 1 2 E[τ ] N j=1 p j x∈X v j,x ϑ ⊤ j xx ⊤ ϑ j ≥ log 1 2.4δ ⇔ E[τ ] ≥ T ε (Λ) log 1 2.4δ where T ε (Λ) -1 = max {vj ∈∆ X } N j=1 min Λ ′ ∈AltΘ(Λ) 1 2 N j=1 p j x∈X v j,x ϑ ⊤ j xx ⊤ ϑ j .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 to the stationary ε-best identification problem in linear bandits when we assume the change of the latent vectors are the same, i.e., ϑ 1 = . . . = ϑ N .In the alternative instance Alt Θ (Λ), ∃x ∈ X \ X ε , for any arm x ε ∈ X ε , s.t.N j=1 p j x ⊤ ε θ ′ j + ε < N j=1 p j x ⊤ θ ′ j (M.12) ⇔ N j=1 p j (x ε -x) ⊤ θ ′ j + ε < 0 ⇔ - N j=1 p j (x ε -x) ⊤ θ ′ j + N j=1 p j (x ε -x) ⊤ θ * j > N j=1 p j (x ε -x) ⊤ θ * j + ε ⇔ N j=1 p j (x ε -x) ⊤ ϑ j > N j=1 p j (x ε -x) ⊤ θ * j + ε = ∆(x ε , x) + ε Thus, Alt Θ (Λ) =    (X , Θ ′ , P θ , C) : θ ′ j = θ * j -ϑ j , ∃x ∈ X \ X ε , N j=1 p j (x ε -x) ⊤ ϑ j > ∆(x ε , x) + ε, ∀x ε ∈ X ε    . Define Alt(Λ) restricted ⊂ Alt Θ (Λ), with the additional constraint that ϑ 1 = ϑ 2 = • • • = ϑ N . Then we have Alt(Λ) restricted =    (X , Θ ′ , P θ , C) : θ ′ j = θ * j -ϑ 1 , ∃x ∈ X \ X ε , N j=1 p j (x ε -x) ⊤ ϑ j > ∆(x ε , x) + ε, ∀x ε ∈ X ε    .Note that in stationary linear bandits, the instance can be characterized by the arm set X ⊂ R d and the latent vector θ ∈ R d . Define the alternative instance in linear bandits [32] for the instance (X , E θ∼P θ θ)Alt((X , E θ∼P θ θ)) stationary = (X , θ ′ ) : θ ′ = E θ∼P θ θ -ϑ 1 , (x ε -x) ⊤ ϑ 1 > (x ε -x) ⊤ E θ∼P θ + ε, ∀x ε ∈ X ε . Note that max {vj ∈∆ X } N j=1 min Λ ′ ∈AltΘ(Λ) 1 2 E[τ ] N j=1 p j x∈X v j,x ϑ ⊤ j xx ⊤ ϑ j ≤ max {vj ∈∆ X } N j=1 min Λ ′ ∈Alt(Λ) restricted 1 2 E[τ ]ϑ ⊤ 1   x∈X   N j=1 p j v j,x   xx ⊤   ϑ 1 (a) = max v∈∆ X min Λ ′ ∈Alt(Λ) restricted 1 2 E[τ ]ϑ ⊤ 1 x∈X vi xx ⊤ ϑ 1 = max v∈∆ X min Λ ′ ∈Alt((X ,E θ∼P θ θ))stationary 1 2 E[τ ]ϑ ⊤ 1 x∈X vi xx ⊤ ϑ 1where in (a) we denote v := N j=1 p j v j as a mixture of {v j } N j=1 . In other words, the max-min problem becomes the one for the ε-best arm identification problem in stationary linear bandits. According to [32] , the solution to the last optimization problem above is in general intractable.However, the optimization problem can be simplified under some simple cases, e.g., the set of ε-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.ε | = 1Assume that the set of ε-best arm is a singleton, i.e., X ε = {x * }, we will solve the original optimization problem:min Λ ′ ∈AltΘ(Λ) 1 2 N j=1 p j x∈X v j,x ϑ ⊤ j xx ⊤ ϑ jwe extend the procedures in [1] to the piecewise-stationary setup. Lemma M.4.min Λ ′ ∈AltΘ(Λ) 1 2 N j=1 p j x∈X v j,x ϑ ⊤ j xx ⊤ ϑ j ≥ 1 2 min x̸ =x * (∆(x * , x)) 2 N j=1 p j ∥x * -x∥ 2 A(vj ) -1Proof. Note that Λ ′ differs from Λ in the context matrix Θ. By the derivations in (M.12), there exists arm x ̸ = x * , s.t.,N j=1 p j (x * -x) ⊤ ϑ j > ∆(x ε , x) + εTherefore, the optimization problem becomesmin ϑ1,...,ϑ N 1 2 N j=1 p j x∈X v j,x ϑ ⊤ j xx ⊤ ϑ j s.t. ∃x ∈ X \ {x * }, N j=1 p j (x * -x) ⊤ ϑ j ≥ ∆(x * , x) + ε + a =: ∆ a+ε (x * , x) (M.13)where a > 0. The Lagrangian function for this problem isL(ϑ 1 , . . . , ϑ N , λ) = 1 2 N j=1 p j x∈X v j,x ϑ ⊤ j xx ⊤ ϑ j + λ(- N j=1 p j (x * -x) ⊤ ϑ j + ∆ a+ε (x * , x)) Then ∂L ∂ϑ j = 0 ⇒ p j x∈X v j,x xx ⊤ ϑ j -λp j (x * -x) = 0 ⇒ A(v j ) 1/2 ϑ j = λA(v j ) -1/2 (x * -x) ∂L ∂λ = 0 ⇒ N j=1 p j (x * -x) ⊤ ϑ j = ∆ a+ε (x * , x)This indicates thatN j=1 p j x∈X v j,x ϑ ⊤ j xx ⊤ ϑ j = N j=1 p j ∥ϑ j ∥ 2 A(vj ) ≥ N j=1 p j ∥ϑ j ∥ A(vj ) ∥x * -x∥ A(vj ) -1 2 N j=1 w j ∥x * -x∥ 2 A(vj ) -1 = N j=1 p j ϑ ⊤ j (x * -x) 2 N j=1 p j ∥x * -x∥ 2 A(vj ) -1 = (∆ a+ε (x * , x)) 2 N j=1 p j ∥x * -x∥ 2 A(vj ) -1Let a → 0, we haveN j=1 p j x∈X v j,x ϑ ⊤ j xx ⊤ ϑ j ≥ (∆(x * , x) + ε) 2 N j=1 p j ∥x * -x∥ 2 A(vj ) -1Due to (M.13), we only require there exists x ̸ = x * , such that the constraint is satisfied, therefore,1 2 N j=1 p j ∥ϑ j ∥ 2 A(vj ) ≥ 1 2 min x̸ =x * (∆(x * , x) + ε) 2 N j=1 p j ∥x * -x∥ 2 A(vj ) -1By Lemma M.4, the stopping time can be lower bounded asE[τ ] ≥ 2 log 1 2.4δ min {vj ∈∆ X } N j=1 max x̸ =x * N j=1 p j ∥x * -x∥ 2 A(vj ) -1 (∆(x * , x) + ε) 2This lower bound indicates that, (1) a 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 restrictv 1 = . . . = v N . Lemma M.5. Let SPD(d) := {A : A ∈ R d×d , A > 0} denote the set of SPD matrices of dimension d × d. Given any x ∈ R d , define the function f : SPD(d) → R, f (A) = x ⊤ A -1 x, then f is convex.Proof of Lemma M.5. Given any A, B ∈ SPD(d), defineg : {t ∈ R : A + tB ∈ SPD(d)} → R, g(t) = x ⊤ (A + tB) -1 xIt is suffice to prove g is convex.g ′ (t) = -x ⊤ (A + tB) -1 B(A + tB) -1 x g ′′ (t) = 2x ⊤ (A + tB) -1 B(A + tB) -1 B(A + tB) -1 x = 2 x ⊤ (A + tB) -1 B (A + tB) -1 B(A + tB) -1 x ≥ 0Therefore, g is convex.Given Lemma M.5, we haveN j=1 p j ∥x * -x∥ 2 A(vj ) -1 = (x * -x) ⊤   N j=1 p j A(v j ) -1   (x * -x) ≥ (x * -x) ⊤   N j=1 p j A(v j )   -1 (x * -x) = (x * -x) ⊤   N j=1 p j x∈X v j,x xx ⊤   -1 (x * -x) = (x * -x) ⊤   x∈X   N j=1 p j v j,x   xx ⊤   -1 (x * -x) = (x * -x) ⊤ A(v) -1 (x * -x)where v := N j=1 p j v j ∈ ∆ X and the inequality becomes equality whenv 1 = • • • = v n . Thus, E[τ ] ≥ 2 log 1 2.4δ min {vj ∈∆ X } N j=1 max x̸ =x * N j=1 p j ∥x * -x∥ 2 A(vj ) -1 (∆(x * , x) + ε) 2 ≥ 2 log 1 2.4δ min v∈∆ X max x̸ =x * ∥x * -x∥ 2 A(v) -1 (∆(x * , x) + ε) 2 . (M.14)The last term mimics the lower bound in the stationary linear bandits with the latent vector E θ∼P θ θ.In addition, if we let p 1 = 1 and p j = 0 for all j ̸ = 1 in the instance, our lower bound can be simplified to the lower bound in stationary linear bandits with latent vector θ * 1 [24]E[τ ] ≥ 2 log 1 2.4δ min {vj ∈∆ X } N j=1 max x̸ =x * N j=1 p j ∥x * -x∥ 2 A(vj ) -1 (∆(x * , x) + ε) 2 = 2 log 1 2.4δ min v1∈∆ X max x̸ =x * ∥x * -x∥ 2 A(v1) -1 (∆ 1 (x * , x) + ε) 2 . (M.15)In this section, we consider an even easier problem: all the contextual information is known to the agent, except for the distribution P θ . The dynamics is displayed in Dynamics 3.1: The instance: Λ = (X , Θ, P θ , C) 2: while the algorithm does not stop at time step t do 3:if t ∈ C then 4:The agent acknowledges t ∈ C.The environment samples θ * jt ∼ P θ 6: The agent observes θ * jt 10: end while 11: Recommend an ε-best arm xε .We are going to consider the alternative instances with respect to the distribution on θ, i.e., Λ ′ = (X , Θ, where Λ x is an alternative instance with distribution P x θ s.t.P ′ θ , C). where ∃x ∈ X \ X ε , ∀x ε ∈ X ε , s.t., x ⊤ ε E θ∼P ′ θ < x ⊤ E θ∼P ′ θ -ε.x ⊤ E θ∼P x θ θ -ε > x ⊤ ε E θ∼P x θ θ, ∀x ε ∈ X ε . Given any x /∈ X ε , we denote the shorthand notation q j = P x θ [θ * j ]. We haveN j=1 q j ∆ j (x, x ε ) ≥ ε + a, for any a > 0, x ε ∈ X εFix a > 0 which is sufficiently small, we have the following optimization problem:min q∈∆ N N j=1 p j ln p j q j s.t. N j=1 q j = 1 N j=1 q j ∆ j (x ε , x) + ε + a ≤ 0, ∀x ε ∈ X εIf such alternative distribution q exists, let L denote the augmented Lagrangian functionL(q, λ, {λ xε } xε∈Xε ) = N j=1 p j ln p j q j + λ N j=1 q j -1 + xε∈Xε λ xε (q j ∆ j (x ε , x) + ε + a)By the KKT conditions, we have:∂L ∂q j = -p j q j + λ + xε∈Xε λ xε ∆ j (x ε , x) = 0, ∀j ∈ [N ] (M.18) ∂L ∂λ = N j=1 q j -1 = 0 ∂L ∂λ xε = N j=1 q j ∆ j (x ε , x) + ε + a = 0, ∀x ε ∈ X εor λ xε = 0 for some x ε ∈ X ε , which indicates some conditions are not satisfied. The equations above giveq j = p j 1 + xε∈Xε λ xε (∆ j (x ε , x) + ε + a) , ∀j ∈ [N ] (M.19)By solvingN j=1 p j 1 + xε∈Xε λ xε (∆ j (x ε , x) + ε + a) -1 = 0 (M.20)which is a polynomial with N -1 degree. Thus, an explicit solution for any instance is not applicable. However, there are some cases where we can get an estimate of λ xε Lemma M.6. Denote j 0 = arg min j∈[N ] ∆ j (x * , x) and j 1 = arg max j∈[N ] ∆ j (x * , x). When |X ε | = 1, -∆ j0 (x * , x) -2ε > ∆ j1 (x * , x) > ε andλ i * ≤ ∆(x * , x) + ε + a N j=1 p j (∆ j (x * , x) + ε + a) 2Proof of Lemma M.6. When the ε-best arm set is a singleton, (M.20) becomes (where a is sufficiently small)N j=1 p j 1 + λ x * (∆ j (x * , x) + ε + a) -1 = 0As (M. 19 ) is a probability distribution, we need 1 + λ x * (∆ j0 (x * , x) + ε + a) ≥ 0, which indicates λ x * ≤ -1 ∆j (x * ,x)+ε+a . By the condition on j 0 and j 1 , 0 < λ x * (∆ j (x * , x)+ ε + a) < 1, ∀j ∈ [N ].Therefore, by using 1 1+x = 1 -x + x 2 -x 3 + x 4 1+x for |x| < 1, we can expand the equation as follows1 = N j=1 p j 1 + λ x * (∆ j (x * , x) + ε + a) ≥ N j=1 p j 1 -λ x * (∆ j (x * , x) + ε + a) + (λ x * (∆ j (x * , x) + ε + a)) 2 -(λ x * (∆ j (x * , x) + ε + a)) 3 ⇔ 0 ≥ -λ 2 x * N j=1 p j (∆ j (x * , x) + ε + a) 3 + λ x * N j=1 p j (∆ j (x * , x) + ε + a) 2 - N j=1 p j (∆ j (x * , x) + ε + a) ⇒ λ x * ≤ N j=1 p j (∆ j (x * , x) + ε + a) N j=1 p j (∆ j (x * , x) + ε + a) 2 = ∆(x * , x) + ε + a N j=1 p j (∆ j (x * , x) + ε + a) 2 .In general, when we get the {λ xε } xε∈Xε and plug it in (M. 19 ), the alternative distribution q is obtained. Finally, we let a → 0.This gives the lower bound for the number of changepoints that need to be observed. A coarse estimation of the KL divergence without solving (M.20) can be done as followsN j=1 p j ln p j q j = N j=1 p j ln 1 + xε∈Xε λ xε (∆ j (x ε , x) + ε) ≤ N j=1 p j xε∈Xε λ xε (∆ j (x ε , x) + ε) = xε∈Xε λ xε (∆(x ε , x) + ε).Note that the solution of λ xε depends on ∆(x ε , x) (e.g. Lemma M.6), so the final solution is of order (∆(x ε , x) + ε) 2 for a given x / ∈ X . This is the solution to the inside minimization problem in (M.17). The final lower bound will be min The lower bound isE[l t ] ≥ max x / ∈Xε 1 xε∈Xε λ xε (∆(x ε , x) + ε) ln 1 4δwhere λ xε is the solution to (M.20).With the setup in Lemma M.6, we have minΛ ′ ∈Alt P (Λ) KL(P θ , P ′ θ ) = min x∈X \Xε min Λx KL(P θ , P x θ ) ≤ min x̸ =xε (∆(x * , x) + ε) 2 N j=1 p j (∆ j (x * , x) + ε) 2and the lower bound isE[l t ] ≥ max x̸ =xε N j=1 p j (∆ j (x * , x) + ε) 2 (∆(x * , x) + ε) 2 ln 1 4δ .Remark M.7. We give some comments on the existence and uniqueness of the solution to (M.20).Existence:• It is possible that (M.20) does not have a solution. For instance, consider a three-arm instance:x (1) = (1, 0.5), x (2) = (0.5, 1), x (3) = (0.6, 0.6), θ * 1 = (1, 0), θ * 2 = (0, 1), P θ = (0.5, 0.5), ε = 0.1. We have x (1)⊤ E θ∼P θ = x (2) ⊤ E θ∼P θ = 0.75 and x (3) ⊤ E θ∼P θ = 0.6, thus x (3) is not an ε-best arm. Furthermore, there does not exist an alternative distribution q, such that x (3) is the best arm and neither x (1) , x (2) is ε-best. Under such case, the lower bound on E[l t ] is 0 (we regard min x∈∅ f (x) = +∞ by convention).• It is possible that (M.20) does not have a solution and it is unnecessary to estimate P θ . For instance, consider a two-arm instance: x (1) = (1, 0.5), x (2) = (0.5, 0.1), θ * 1 = (1, 0), θ * 2 = (0, 1), P θ = (0.5, 0.5), ε = 0.1. Arm x (1) is better than arm x (2) under all contexts. Therefore, no matter what P θ is, arm x (1) is the ε-best arm. Under such cases, there may exist an algorithm and it is sufficient for it to determine the best arm if the context vectors are well-approximated. There is no need to estimate P θ .• A necessary condition for the existence of the solution of (M.20) is: there exists x / ∈ X ε , for any x ε ∈ X ε , there ∃j(x ε ) ∈ [N ], s.t.∆ j(xε) (x ε , x) < -ε. In other words, for each ε-best arm x ε , there is at least one context in which the alternative arm x is better than x ε by at least ε.• A sufficient condition for the existence of the solution of (M.20) is: there exists x / ∈ X ε and j ∈ [N ], s.t.∆ j (x ε , x) < -ε, ∀x ε ∈ X ε . In other words, x is better than any ε-best arm under context j. In the alternative instance, we can lift P ′ θ [θ * j ] close to 1 so that arm x becomes the ε-best arm andX ′ ε ∩ X ε = ∅.Uniqueness:• The uniqueness of the solution is not guaranteed, as the KKT conditions (M.18) is only a necessary condition for the solution. We need to look for the solution that minimizes the KL divergence. • A sufficient condition for the uniqueness of the solution is (if it exists, which indicates ∃j ∈[N ], s.t.∆ j (x * , x) < -ε): |X ε | = 1. Specifically, denote f (λ x * ) := N j=1 pj 1+λ x * (∆j (x * ,x)+ε+a) , we have∂f ∂λ x * = N j=1 -p j (1 + λ x * (∆ j (x * , x) + ε + a)) 1 + λ x * (∆ j (x * , x) + ε + a) ∂ 2 f ∂λ 2 x * = N j=1 2p j (1 + λ x * (∆ j (x * , x) + ε + a)) 2 1 + λ x * (∆ j (x * , x) + ε + a) > 0 As f (0) = 1, ∂f ∂λ x * (0) = -1 and ∂ 2 f ∂λ 2x * > 0, so there is exactly 1 solution λ x * > 0.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, we 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 L max . After that, we present a proof sketch of the results in Corollaries 5. Under Example 2, we have∆(x (1) , x (i) ) = (1 -(N -2)p) • a -(N -2)p • (b -a) > ε ∆ j (x (1) , x (i) ) = -b + a < -ε, i ≥ 2, j ̸ = 1, iThus, (1) x (1) is the unique ε-best arm; (2) {x (i) } i≥2 are equivalent, and ∆ min := ∆(x (1) , x (i) ); (3) for any i ≥ 2, x (i) can be an ε-optimal arm under some alternative distributions.Corollary N.1. Firstly, for the instances defined in Example 2, we haveH DE ≤ 16(N -2)L max (∆ min + ε) 2 (a + ε) 2 + (b -a -ε) 2 ,and the sample complexity of the PSεBAI + is tight up to (N L max /L min ) and logarithmic factors. We also further observe some specific instances: (i) when p → 0 + , with ∆ min = min x̸ =x * ∆(x * , x), we haveE[τ ] * ln(1/δ) ∈ Õ min d (∆ min + ε) 2 + N L max ∆ min + ε , L max + d (∆ min + ε) 2 Ω max d (∆ min + ε) 2 , L min (b -a -ε) ∆ min + ε . (ii) When p → a-ε) (N -2)b - and (a + ε) 2 + (b -a -ε) 2 = Ω(1), we have H DE = N Lmax (∆(x(1),x(i))+ε) 2 and E[τ ] * ln(1/δ) ∈ Õ min H DE , d + L max ε 2 Ω d + L min ε 2 .The upper bounds are achieved by the PSεBAI + algorithm.We can observe from Corollary N.1 that• In case (i), when p → 0 + , p 1 → 1 -(N -1)(a-ε) (N -2)band p j → a-ε) (N -2)b , and thus the instance tends to be non-stationary and ∆ min → ε. We will obtain 2 , indicating that our algorithm can also reduce the impact of L max .Eτ ln(1/δ) ∈ Θ d (∆ min + ε)• In case (ii), the upper and lower bounds are with the same order, and the difference is solely manifested by a additive term L max -L min , suggesting that PSεBAI + is near optimal and again, PSεBAI + mitigates the impact of L max .Recall the instance Λ = (X , Θ, P θ , C) in Example 1:Example 1. Instance Λ = (X , Θ, P θ , C) is with (i) 2d -1 arms: x (1) = e 1 , x (i) = e i , x (d+i-1) = e 1 cos ϕ + e i sin ϕ for all i ∈ {2, . . . , d} where ϕ ∈ [0, π/4), (ii) 2d -2 contexts: θ * j± = e 1 cos ϕ ± e j+1 sin ϕ for all j ∈ [d -1], (iii) Context distribution: p j = 1/N for all j ∈ [N ].Corollary 5.1. For the instance defined in Example 1, we have When ε < cos ϕ -cos 2 ϕ = ∆ min , x (1) is the unique ε-best arm. By solving (M.14), we see that there exists a continuous function f (ϕ) such that f (ϕ) → 0 as ϕ → 0 and we can get the lower bound for the VE term asEQUATIONΩ (1 + f (ϕ)) • d (∆(x (1) , x (d+1) ) + ε) 2 ln 1 δ . (N.1)As (x (1) -x (i) ) ⊤ θ * j± > 0 for i = 2, . . . , d, j ∈ [d -1], x (i) cannot be an ε-best arm under any alternative distribution, we only need to consider x (d+i) , i = 2, . . . , d, which are equivalent. Given any x (d+i) , by solving (M.20), we can upper boundλ x (1) ≤ ∆ min + ε + sin 2 ϕ -(∆ i+ (x (1) , x (d+i) ) + ε)(∆ i-(x (1) , x (d+i) ) + ε) ,and thus the number of change points or context samples can be lower bounded asE[l τ ] ≥ -(∆ i+ (x (1) , x (d+i) ) -ε)(∆ i-(x (1) , x (d+i) ) + ε) (∆ min + ε + sin 2 ϕ)(∆ min + ε) = (1 -cos ϕ -ε)(1 + cos ϕ -2 cos 2 ϕ + ε) (∆ min + ε + sin 2 ϕ)(∆ min + ε) = 1 -cos ϕ -ε ∆ min + ε = O(1).According to Theorem 3.3, the upper bound isÕ d (∆(x (1) , x (d+1) ) + ε) 2 ln 1 δ + H DE (∆(x (1) , x (d+1) ) ln 1 δ + N L max ∆(x (1) , x (d+1) ) + ε ln 1 δ = Õ d (∆ min + ε) 2 ln 1 δ + H DE (∆(x (1) , x (d+1) ) ln 1 δ + N L max ∆ min + ε ln 1 δ where H DE (∆(x (1) , x (d+1) ) =    16N L max , ε ≥ 1 -cos ϕ 16N L max (∆ min + ε + 2(1 -cos ϕ)/N ) 2 (∆ min + ε) 2 , ε < 1 -cos ϕAs ∆ min = cos ϕ -cos 2 ϕ = cos ϕ(1 -cos ϕ), thus 1 -cos ϕ = ∆min cos ϕ ≤ √ 2∆ min , and H DE (∆(x (1) , x (d+1) ) < 144N L max for any choice of ε.Hence, the upper bound isE[τ ] = Õ d (∆ min + ε) 2 ln 1 δ + N L max ln 1 δ + N L max ∆ min + ε ln 1 δ = Õ d (∆ min + ε) 2 ln 1 δ + N L max ∆ min + ε ln 1 δ .As ϕ → 0, the first term (the VE term) dominates and it matches the lower bound in (N.1). Therefore, the upper bound is asymptotically tight up to logarithmic terms.Corollary N.1. Firstly, for the instances defined in Example 2, we haveH DE ≤ 16(N -2)L max (∆ min + ε) 2 (a + ε) 2 + (b -a -ε) 2 ,and the sample complexity of the PSεBAI + is tight up to (N L max /L min ) and logarithmic factors.We also further observe some specific instances: (i) when p → 0 + , with ∆ min = min x̸ =x * ∆(x * , x), we haveE[τ ] * ln(1/δ) ∈ Õ min d (∆ min + ε) 2 + N L max ∆ min + ε , L max + d (∆ min + ε) 2 Ω max d (∆ min + ε) 2 , L min (b -a -ε) ∆ min + ε . (ii) When p → a-ε) (N -2)b - and (a + ε) 2 + (b -a -ε) 2 = Ω(1), we have H DE = N Lmax (∆(x(1),x(i))+ε) 2 and E[τ ] * ln(1/δ) ∈ Õ min H DE , d + L max ε 2 Ω d + L min ε 2 .The upper bounds are achieved by the PSεBAI + algorithm.Proof of Corollary N.1. Under Example 2, we have∆(x (1) , x (i) ) = (1 -(N -2)p) • a -(N -2)p • (b -a) > ε ∆ j (x (1) , x (i) ) = -b + a < -ε, i ≥ 2, j ̸ = 1, iThus, (1) x (1) is the unique ε-best arm; (2) {x (i) } i≥2 are equivalent, and ∆ min := ∆(x (1) , x (i) ); (3) for any i ≥ 2, x (i) can be an ε-best arm under some alternative distributions.For any i ≥ 2, by solving (M.20) with x ε = x (1) , x = x (i) , we obtain λ x (1) = ∆(x (1) ,x (i) )+ε (a+ε)(b-a-ε) and the alternative distributionP ′ θ [θ * j ] = p j 1 + λ x (1) (∆ j (x (1) , x (i) ) + ε) .The lower bound on the expected number of changepoints isE[l τ ] ≥ (a + ε)(b -a -ε) ∆(x (1) , x (i) ) + ε 2 ln 4 δ .Thus the time complexity is lower bounded byE[τ ] ≥ L min • (a + ε)(b -a -ε) ∆(x (1) , x (i) ) + ε 2 ln 4 δ .Furthermore, by solving (M.14), we obtain the lower bound on the expected sample complexity when the context index j t is revealed:E[τ ] ≥ 2 log 1 2.4δ min v∈∆ K max i̸ =1 1 v1 + 1 vi ∆(x (1) , x (i) ) + ε 2 ≥ 2 log 1 2.4δ ( √ d -1 + 1) 2 ∆(x (1) , x (i) ) + ε 2 ≥ d ∆(x (1) , x (i) ) + ε 2 • 2 log 1 2.4δ.distribution estimation term. Under both scenarios, our upper bound is tight.For the computation of the G-optimal allocation, we adopt the Wolfe-Atwood Algorithm with the Kumar-Yildirim start introduced in [33], where the input to the function is the arm set and the output is the G-optimal allocation. All experiments are conducted via MATLAB R2021b on a MacBook Pro with Apple M1 Pro chip and 16 GB memory.To shorten the execution time,• Before PSεBAI stops, PSεBAI and NεBAI are conducted in parallel (i.e., we run PSεBAI + ). After PSεBAI stops, NεBAI continues and is run in a batch manner, i.e., we sample L min samples according to the G-optimal allocation one time and update the statistics. As the sample complexity of NεBAI is of order at least 10 7 and each stationary segment is of order 10 4 , the effect of this batch sampling procedure can be largely ignored. • DεBAI and DεBAI β 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 a stationary segment. • As the experiment in Section 6 illustrates that PSεBAI outperforms NεBAI and dominates the PSεBAI + algorithm, we run PSεBAI instead of PSεBAI + for the addition experiments in Section O.2 and Section O.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 of the proposed algorithm and the order of the sample complexity remains.During the proof of the upper bound, we have relaxed the absolute constants in the confidence radii to simplify the proof and increase the readability. In the experiments, we utilize the tighter confidence radii to 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:• α t : according to Lemma I.1 and Lemma E.1, α can be tightened to beEQUATION• β t,j : according to (I.3) and Lemma K.1, β t,j can be tightened to beEQUATION      , where ϕ t,j := min 4 max pt,j , 25 4EQUATION• ξ t : instead of using 25√ 2 N Lmax Tt ln 2 δ m,T t, we turn to bound the residual error by (I.9): As PSεBAI + requires the knowledge of L max , we empirically test the robustness of the algorithm towards L max on the instances in section 6. We run PSεBAI with Lmin = νL min and Lmax = νL max where ν = 0.8 or 1.2. An ε-best arm is recommended in all experiments. The sample complexities are presented in Figure 3 . The result indicates that PSεBAI (thus PSεBAI + ) is robust towards the knowledge of L max and its superiority over NεBAI is maintained.ξ alg t = j:ψt,j,1> pt,jAccording to the distinguishability condition (Assumption 1), point (2) indicates we can set w = Lmin 3γ , where γ is the change detection frequency, and (3.5) indicates w and b are coupled. We denote w := Lmin 18 . To exam the robustness towards w and b, we choose to vary the choice of γ, thus, w and b will change accordingly. Specifically, we select γ ∈ {2, 3, 6, 12} and the corresponding w ∈ {3 w, 2 w, w, w 2 }. The other parameters remain unchanged. The experiment result is presented in Figure 4 . When γ = 18, w = w 3 , Assumption 1 is severely violated and the result is not desirable. 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 NεBAI is maintained. We conclude that our algorithm is robust against these choices, as long as Assumption 1 is not severely violated. = c j } l t , ẍt = arg max x∈X x ⊤ Θp t (O.1) βt = 1 2l t ln 2C 3 N l 3 t δ , ρt (ẍ t , x) = βt min ζ(ẍt,x)∈R N j=1 |∆ j (ẍ t , x) + ζ(ẍ t , x)| 6: while min x̸ =ẍt (ẍ t -x) ⊤ Θp t -ρt < -ε or t / ∈ C do 7:Observe θ * jt and 1{t ∈ C} update t = t + 1.Update ẍt and ρt with (O.1) and update l t if t ∈ C. 9: end while (∆ j (ẍ t , x) + ζ(ẍ t , x)) 2 = -1 N N j=1 ∆ j (ẍ t , x) Algorithm 9 DISTRIBUTION ε-BEST ARM IDENTIFICATION-β (DεBAI β )1: Input: the arm set X , the latent vector matrix Θ, the slackness parameter ε, the confidence parameter δ. 2: Initialize: Compute the G-optimal allocation λ * .EQUATIONEQUATIONObserve θ * jt and 1{t ∈ C} and let t = t + 1. x ε = • x t .DεBAI β utilizes the techniques we have used to bound the deviation between the true distribution p j and the estimated ones• p t,j for all j ∈ [N ]. Similarly, we let ζ( • x, x) = arg min ζ( • x,x)∈R N j=1 • β t,j (∆ j ( • x t , x) + ζ( • x, x)) 2 = - N j=1 • β t,j ∆j ( • xt,x) N j=1 • β t,jfor efficient computing.As the theoretical guarantee of DεBAI β can be derived following a similar manner as the proof of the DE term 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. DεBAI β identifies an ε-best arm withinÕ   max xε∈X ,x̸ =xε,x * L max • H 2 (x ε , x) (∆ min + ε) 2 ln 1 δ   ,time steps with probability at least 1 -δ and in expectation, where• H(x ε , x) := min ζ( • xε,x)∈R N j=1 min{16p j , 1 4 }|∆ j ( • x ε , x) + ζ( • x ε , x)|.We present a theorem, along with a proof sketch, for the theoretical guarantee of DεBAI below. We only consider N > 1 as the bandit model is only truely piecewise-stationary when N > 1. Thus, we did not specifically derive upper and lower bounds for the extreme case where N = 1. Nevertheless, our analysis can cover this case due to the following reasons:• The (minimax) lower bound in Theorem 4.1 is not directly applicable since it is 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[l t ] (N C in Theorem4.1) is 0. In this case, the lower bound in Theorem4.1 reduces to the lower bound in the stationary bandits. • Regarding the upper bound in Theorem 3.2, when N = 1, we have p 1 = 1 and H DE = Lmax 4 . In this case, as H 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 a constant. Therefore, the dominant term in the upper bound is T V . This recovers the bound in the stationary setup.• In addition, as we assume N is an input 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 Y-allocation rule [1] .In the main paper, we consider the identification of an ε-best arm in terms of the "ensemble" quality µx := E θ∼P θ [x ⊤ θ] = N j=1 P θ [θ * j ]x ⊤ θ * j .The curious reader may wonder whether we can identify the ε-best arm tuple X tuple ε := (x ε 1 , . . . , x ε N ), where x ε j is an ε-best arm under context j, i.e.,x ε j ∈ {x : x ⊤ θ * j ≥ max x∈X x ⊤ θ * j -ε}.Given the tools we developed in this manuscript, we answer this problem in the affirmative.Intuitions: Let x * j := arg max x∈X x ⊤ θ * j and ∆ * j := min x̸ =x * j ∆ j (x * j , x). We expect to have an upper bound taking the form ofÕ max j∈[N ] L max p j • d ∆ * j + ε 2 L min ln 1 δ where O( d (∆ * j +ε) 2 Lmin ln 1 δ) is an upper bound on the number of context samples j and context j will occur once among every 1 pj contexts in expectation. Analysis of the problem: The change detection and context alignment subroutines are only effective within τ * time steps (Line 2 in Algorithm 1). However, if a context is with small occurrence probability p j , it may not appear before τ * time steps.Regarding this scenario, we only expect to obtain a high-probability upper bound on the sample complexity, whereas the expected sample complexity requires more techniques beyond our parallel execution trick (which is used to design PSεBAI + ) and is an interesting direction left for future research.Besides, it is more feasible to consider the identification of ε-best arms under contexts with high occurrence probability, i.e., we aim to identify X tuple ε, p := {x ε j : p j > p} where p is a threshold on the occurrence probability of contexts. Let Θ p = {θ * j : p j > p} denote those context with high occurrence probability.We aim to devise an algorithm with the minimum sample complexity (arm pulls) to ascertain either (1) an ε-best arm under context j, or (2) θ * j / ∈ Θ p.With the above goal, we expect to identify an ε-best arm for all j with θ * j ∈ Θ p; for those j with θ * j / ∈ Θ p, either an ε-best arm is identified or θ * j / ∈ Θ p is ascertained.We propose Algorithm 10 for this problem, which is quite similar to Algorithm 1, except for a few changes: Proof of Theorem Q.1. We provide a concise proof sketch for this theorem.βBy adapting the stopping rule for best arm identification in stationary linear bandits to ε-best arm identification, we observe that the number of arm pulls needed for ε-best arm identification under context j isT t,j = Õ d ∆ * j + ε 2 ln 1 δ .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 pt,j = Tt,j Tt (3.2) and Lemma I.2, we have P |T t,j -T t p j | ≥ T t β t,j Good ≤ δ d,Tt .In addition, we have an upper bound on β t,j as in (J.5), so there would be sufficient arm samples for ε-best arm identification under context j if (Q.5)EQUATIONThe above bound is upper bounded by Õ max L max , d ε 2 • ln(1/δ) p .By taking the maximum of (Q.3), (Q.4) and (Q.5), we can obtain a high-probability problemdependent upper bound on the sample complexity. In addition, we can get a high-probability problem-independent upper boundÕ max L max , d ε 2 • ln(1/δ) p .By setting the threshold p carefully, the algorithm is guaranteed to terminate before τ * given the good event Good (G.1).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 clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.Justification: The authors conform with the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).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 we can safely neglect the constants in the formula.This can also be taken as, we are conditioning on θ1:∞, as the realization of the sequence is independent from the behavior of any agent/algorithm.The last inequality can be loose. When each context has been visited at least once, the first summation in (I.10) can be ignored. For empirical performance, (I.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 an upper bound of 6d by utilizing (E.2) which introduces another d factor in ξt. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: Typo: dynamics --> algorithm?

Motivating 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.

Presentations: 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.

It is not clear to me what $\tilde{O}$ hides or if it is intended to hide the same things throughout the paper.
questions: 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? 

2. 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: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: - The justification for using a piecewise stationary model could be more robust, as real-world scenarios may involve more complex conditions.
- The discussion on computational complexity is limited. The authors should discuss the computation required for each major step of the proposed algorithm.
questions: questions: - Is $\theta_j^*$ sampled IID from $P_{\theta}$ each time? If so, it should be clearly stated "IID"
limitations: limitations: Discussion on limitations can be improved, with designated section.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.

2. Parameter Sensitivity Analysis:
- 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.
questions: questions: 1. About the context alignment:
- When a new distribution is detected, how does the algorithm decide when to perform context alignment?
- 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.
- How does the algorithm confirm the reliability of the estimated new context feature vectors?

2. Could the authors elaborate on the specific application of the G-optimal design in the algorithm?
limitations: limitations: Yes.

Comments: comment: Thanks reviewers for your acknowledgements of our rebuttals. Thanks for your positive assessment of our work.
Thank you very much for the detailed response. My concerns and questions are all adressed. I have no more questions.
Thanks for addressing my questions with great details. Would like to see this work being presented.
Thanks for the authors' detailed feedback which answers my questions! I have no further questions.
Dear reviewers,

Thank you for your assessment of our paper "Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits". We have clarified your doubts and addressed your questions. Please let us know if our responses are satisfactory. We appreciate your time and efforts in assessing our paper and would be happy to engage in any discussions and further clarifications, if any. 

Regards,

Authors of 4521