Fixed-Confidence Multiple Change Point Identification under Bandit Feedback
Authors: Joseph Lazzaro
Ciara Pike-Burke
Venue: ICML 2025 poster (2025)
Keywords: bandits
pure exploration
fixed confidence
change points
Primary area: theory->online_learning_and_bandits

Abstract: Piecewise constant functions describe a variety of real-world phenomena in domains ranging from chemistry to manufacturing. In practice, it is often required to confidently identify the locations of the abrupt changes in these functions as quickly as possible. For this, we introduce a fixed-confidence piecewise constant bandit problem. Here, we sequentially query points in the domain and receive noisy evaluations of the function under bandit feedback. We provide instance-dependent lower bounds for the complexity of change point identification in this problem. These lower bounds illustrate that an optimal method should focus its sampling efforts adjacent to each of the change points, and the number of samples around each change point should be inversely proportional to the magnitude of the change.
Building on this, we devise a simple and computationally efficient variant of Track-and-Stop and prove that it is asymptotically optimal in many regimes. We support our theoretical findings with experimental results in synthetic environments demonstrating the efficiency of our method.

Fixed-Confidence Multiple Change Point Identification under Bandit Feedback
Joseph Lazzaro! Ciara Pike-Burke
Abstract
or in Oceanology we may wish to map out the edge of a cliff the seafloor (Hayashi et al., 2019). In all these settings, data is expensive to collect due to the cost, time, compute of each experiment. Moreover, there are often health or safety constraints which mean that we need to have high confidence in our results. This motivates us to develop se- quential methods which can learn about the locations of these change points efficiently and with high confidence.
Piecewise constant functions describe a variety of real-world phenomena in domains ranging from chemistry manufacturing, In practice, it is often required to confidently identify the loca- tions of the abrupt changes in these functions as quickly as possible. For this, we introduce a fixed-confidence piecewise constant bandit prob- lem. Here, we sequentially query points in the domain and receive noisy evaluations of the func- tion under bandit feedback. We provide instance- dependent lower bounds for the complexity of change point identification in this problem. These lower bounds illustrate that an optimal method should focus its sampling efforts adjacent to each of the change points, and the number of samples around each change point should be inversely pro- portional to the magnitude of the change. Build- ing this, we devise simple and computation- ally efficient variant of Track-and-Stop and prove that it is asymptotically optimal in many regimes. We support our theoretical findings with experi- mental results in synthetic environments demon- strating the efficiency of our method.
In this paper consider a multi-armed bandit setting in which the expected rewards are piecewise constant across an action space A, see Figure for an example. In each round = 2,,.... we select an action in our action space and observe the mean reward at that action plus some random noise (see Section for more details). We assume the mean reward function is stationary across time, but piecewise con- stant across A. The objective of the learner is to confidently identify the locations of the N change points/jumps in the mean reward function with the fewest number of samples possible. While there exist methods for locating the mini- mum a smooth or convex function under bandit feedback (e.g. Kleinberg et al., 2008: Srinivas et al., 2010: Bubeck et al., 201 I), the abrupt changes in the mean reward function across the action space make these methods inapplicable to our setting. There has been work on identification of single change point across the action space with bandit feed- back, under a fixed- budget constraint (Hall & Molchanov, 2003; Lan et al., 2009; Lazzaro Pike-Burke, 2025). How- ever, in practice is often necessary to continue sampling until we are sufficiently confident we have identified N 2 1 change points correctly, at which point stop playing. For example, in material development we need to identify the phase transitions of an unfamiliar new material with high confidence for the sake of both production and safety pre- cautions (Park et al., 2021; 2023). It is therefore important to study this fxee-confidence variant of the problem, which we will refer as the fixed-confidence piecewise constant bandits problem.
1. Introduction
There are variety of settings where it is necessary to con- fidently identify the location of change points in a piece- wise constant function via sequential queries. For example, in communication and computer system engineering, the system can become overloaded and we need to determine the point at which this happens (Lan et al., 2009); during material development it essential to find the experimen- tal conditions under which the behavior of new material changes abruptly between phases (Park et al., 2021; 2023);
'Department of Mathematics, Imperial College London, London, England. Correspondence to: Joseph Lazzaro <joseph.lazzaro 1entaaro1@@h @iiiseeialllacc...mm.
In this paper we provide a comprehensive study of the fixed- confidence piecewise constant bandits problem. We firstly study the complexity of searching for N change points, when the true number of change points is known to ex- actly N (see Definition 5.1). However, in practice, there may be an unknown number of additional changes present and it
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Coned-Confieenee Multiple Change Point Identification
and Top-Two methods by Garivier & Kaufmann, 2016; Jour- dan et al., 2022, resp.). Our method is variant of the Track-and-Stop approach (Garivier & Kaufmann, 2016). Normally, when using Track-and-stop methods, the actions played are chosen after solving an optimisation problem in each round. As these optimisation problems often have to be solved numerically, the choice of action in each round can be somewhat unintuitive and potentially computationally expensive. However, in the proposed change point identi- fication setting, we can explicitly solve the corresponding optimisation problems to provide a computationally efficient and intuitive variant of Track-and-Stop. This is discussed in more detail in Section 4.
A
22
There has also been recent work on fixed confidence Clus- tering Bandits (Yang et al., 2022; Thuot et al., 2024; Yavas et al., 2025), where there wards which any arm in the action space can have. The objective is to partition the action space into N sets of arms, such that each set contains arms with the same mean reward. Unlike the problem presented in this paper, in the clustering bandits problem there no (piecewise constant) structure of the mean rewards across the action space. Hence these methods are significantly suboptimal when applied to the -xeddcooniieece piccewise constant bandit problem. Fur- thermore we additionally consider settings where we do not know the number of change points/clusters N. We discuss this further in Section 6.
Figure/ I. Example of an environment with piecewise constant ex- pected rewards μ across the action space A. Here the expected rewards for different actions in the action space are represented by blue dots. There are three change points in this environment at vi, . and zī. We additionally plot noisy rewards obtained from 10 arbitrary actions that have been played in A and represent these with red crosses.
exactly N distinct mean re-
is important to develop methods robust to this. For example, when looking for a cliff on the sea floor, there may be other smaller changes in the sea-depth elsewhere. Hence, we also study the complexity of finding any N change points out of an unknown number of changes m 2 N (see Definition 5.3). In both cases we prove a lower bound on the expected sample complexity (Theorems 5.2, 5.5), which provides some key insights. Firstly, it tells us that an optimal method should focus most of its sampling efforts on actions imme- diately adjacent to each of the change points. Secondly, the number of samples adjacent to each change should be inversely proportional to its magnitude. We use these in- sights to construct the Multiple Change Point Identification (MCPI) policy (Algorithm 2), a variant of Track-and-Stop (Garivier& & Kaufmann, 2016), which we show to be asymp- totically optimal (Theorem 5.7, for both objectives). Unlike some other variants of Track-and-Ser Stop (Garivier & Kauf- mann, 2016; Juneja & Krishnasamy, 2018), MCPI is simple and computationally inexpensive. In Section 6 we conduct experiments in synthetic environments illustrate MCPI is optimal and that it outperforms existing related works in Clustering Bandits (Yang et al., 2022).
Change points & Non-Stationary Bandits There is a vast literature in statistics devoted to the detection of change points in given data set (for survey Aminikhanghahi & Cook, 2017). Change points have appeared in the bandit lit- erature in the context of non-stationary environments where the expected rewards from the actions change over time (e.g. Garivier & Moulines, 201 1; Auer et al., 2019; Chen et al., 2019; Gopalan et al., 2021; Hou et al., 2024). We emphasize that this is distinct from the setting considered in this paper where the environment is stationary across time with abrupt changes in the expected rewards of the actions across the action space.
Change Points Across The Action Spaces Anytime methods have been proposed to identify change points or actively learn an entire piecewise smooth function under bandit feedback (Gramacy & Lee, 2008; Park al., 2021; 2023; Hayashi et al., 2019). These methods use variants of Bayesian Optimization, but have only been assessed em- pirically and are not accompanied by theoretical analysis. In this paper we focus on deriving computational efficient policies that are also theoretically optimal.
2. Related Work
Fixed Confidence Pure Exploration The most well- studied fixed-confidence pure exploration problem is best- arm identification where the learner aims to identify the action with the largest mean reward. While some works have focused on minimax optimal sample complexity (see Jamieson& & Nowak, 2014), these methods are often instance- dependent asymptotically suboptimal. More recent works have focused asymptotic optimality (e.g. Track-and-Stop
Other works have also studied settings with change points across the action space under a fixed budget assumption, where the total number of samples the learner can make is bounded by a fixed I > 0. For example, Castro et al. (2005)
2

---

Multiple Change Point Identification
proposed an (instance-independeet)) nearly minimax opti- mal two-stage method for active learning of whole piece- wise constant function in R8.. Similarly, Lan et al. (2009); Hall & Molchanov (2003) provided multistage- meatiss methods with asymptotic guarantees (as T + oo) for single change point (or change surface) identification in the fixed budget setting. Recently, Lazzaro & Pike- BueeB (2025) provided non-asymptotic minimax optimal binary search methods for identifying a single change point in the fixed budget setting. In contrast, we consider fixed-confidence methods for identi- fying change points. Moreover, most prior work has focused on settings with exactly one change point (or surface), while we consider identifying N 2 change points.
fine. We use v(i) to denote the reward distribution of arm i in environment e, namely N( 1), and D (::)) to denote the KL-divergence between two distributions. We addition- ally denote the size of the change in mean at the jth change point in environment U, Fogg as
D = |uu,zt Hu
Finally, we denote =e,(1) as the change point with the i'th largest magnitude and denote its magnitude by (i,())
Hence, A.,01) 2 2 AV.(N- We will drop the notation when it is clear which environment we are considering.
In the fixed confidence setting we consider, the learner will be given a small fixed confidence level E (0, 1) and an objective for their change point estimates to be "correct". There are several natural objectives we can consider in this problem, as outlined in Sections 4 and 5. The goal of the leaner is to satisfy this objective with probability greater than 1 5, while minimizing the number of samples re- quired to do so. In particular, we propose methods which sequentially select actions to play in each round until they are confident of the location of the change points, at which point they return the estimated change points. More for- mally, we define policy ι to consist of three rules:
3. Problem Setting
We consider multi-armed bandit setting where there are K' arms (A = [K]) with mean rewards (14) Note that this is equivalent to discretization of the continuous action analogue of the problem, see (Lazzaro & Pike-Burke, 2025). We assume that the mean rewards are piecewise constant. Let x² C [K- - 1] be the set of N change points with l='| = N. We use the convention that if there a change point at i E zz, then the mean reward changes between the ith and (i + 1)st arm, i.e. 14 * pi+1- Conversely, for any arm that is not a change point, i.e. i E [K - 1],,=,, we have 14 = 14;-1- In each round = 1,2,... we play an action a, E [K] and observe a reward y/ = Ma. + c,. where the noise e, ~ N (0,, o²) is i.i.d. Gaussian with mean zero and variance o² e R4.. We assume that the noise variance is known and x² 1 for simplicity. The assumption of known variance (proxy) is common in the fixed-confidence pure exploration literature (e.g. Chen et al., 2014; Jamieson et al., 2014; Barrier et al., 2022).
1. Sampling Rule:
A procedure to determine which ac- tion to play in each round, given the sequence of ac- tions and rewards observed so far.
2. Stopping Rule:
A rule defining a stopping time at which point we determine we have collected sufficient data and the policy stops.
3. Recommendation Rule: A rule to return our final estimate for the set of change points. After stopping time T, we denote the estimate as 2..
We define KNN as the set of environments with piecewise constant mean rewards when there is a total of K actions and N change points. In partieular, for any e E VK,N we K and the set of denote the mean rewards in (H change points in v as
A good policy will return an estimate i, that satisfies our objective with a small expected stopping time (i.c. sample complexity). Ex, [7), and stops almost surely in finite time, (T. < oc) = 1. Here, we define I Fx,e to be the measure induced by all interactions between a policy and an envi- ronment v, dropping the subscripts when it is clear which policy and environment we refer to.
- = ( E K
Me. + Post1).
We denote the elements of the set of change points as
x = [x" x
4. Warm-Up: Exactly One Change Point
such that they are indexed from left to right, namely x1,1 < < N. Furthermore, we assume that the change points separated by at least one action, namely
Although our aim is to develop methods to confidently iden- tify N change points, we begin by considering the case where there is single change point. This allows us to present the key insights that we will build upon in the mul- tiple change point setting in Section 5. In this section, we additionally assume that the learner knows there is exactly one change point. In Section 5, we will show that a single algorithm can be optimal in this setting as well when as
Vie E |K- - 1], " + < T2,411-
This is reasonable when considering our finite action space as a discretization of continuous one which is sufficiently
'eere we denote [K] = K).
3

---

Soxed-Confidene Multiple Change Point Identification
there are potentially multiple change points, but just want identify one.
to solve (Degenne al., 2019), we are able solve (3)
explicitly to show the unique optimal weights
4.1. Instance Dependent Lower Bound
(v) { 1/2 if ifi= or +1
(4)
0
otherwise.
Suppose that we are in an environment with exactly one change point and the learner is given this information. Namely, it is known that |z*| 1. In this simple setting, we want our policy to return an estimate for the change point (after stopping) which is equal to the true change point with probability greater than 1 ò. This should happen after a finite number of samples almost surely. We refer to a policy which satisfies this objective as an Exact-(1, policy.
This leads to
c² (v) = A//80²
This proves Corollary 4.3 below. This suggests that an optimal Exact-(L, 8) policy will asymptotically focus all of the samples immediately either side of the change point, and will play these two actions equally often. This observation motivates the algorithms we develop in subsequent sections. See Appendix C for the proof of Corollary 4.3.
Definition 4.1. Exact-(1, 5) Policy: For any o E VK,1, an Exact- (1, policy with stopping time т returns an estimate & [K satisfying
Corollary 4.3. For any Exact- (1, 8) policy with stopping time T, lower bound for the expected stopping time in environment V E VK,1 with a single change in mean of magnitude is
(a, = t > 1-66,
(1)
(T. < 00) =1
(2)
For any Exact-(1, 6) policy, we provide the following non- explicit, instance-depender lower bound on its expected stopping time, which is a modification of the general lower bound first described by Garivier & Kaufmann (2016). See Appendix B for the proof.
80
1
log
A
48
4.2. Track-and-Stop Approach and Upper Bounds
In other fixed confidence bandits settings, there are two pop- ular methods to attain asymptotic optimality. The first Track-and-Sre methods (e.g. Garivier & Kaufmann, 2016; Degenne et al., 2019; Degenne & Koolen, 2019; Juneja & Krishnasamy, 2018) which focus on first developing lower bounds and then playing actions according to approxima- tions of the optimal proportions a* (which appear in the lower bounds). Secondly, in Top-Two methods (e.g. Russo, 2016; Qin et al., 2017; Jourdan et al., 2022) the learner alternates between playing 'leader' action and 'chal- lenger' action which represent potential positions of the target/objective in the action space. Since we have shown in Corollary 4.3 that for our problem the optimal proportions a' have a simple closed form expression, is natural to consider Track-and-Sto Stop approaches rather than Top-Two methods. Furthermore, Track-and-Stop methods have been studied in settings with multiple correct answers (Degenne & Koolen, 2019; Chen et al., 2025), leading us to believe they will be more suited to the multiple change point setting than Top-Two methods which have only been studied in settings where is required to return one action. Finally, the main downside to Track-and ano-Stop methods in other settings is their potentially very large computational complexity, This is not issue in our setting since we can explicitly solve the optimization problem in Corollary 4.3. We now show how to adapt Track-and anck--nndStopp methods, using Corol- lary 4.3, to construct our policy called Single Change Point Identification (CPI) which is Exact-(1, (1, 6) and has optimal sample complexity. CPI is stated explicitly in Algorithm
Theorem 4.2. For any Exact-(11 8) policy a with stopping time T in environment U E VK,1 we have
1
BT,u(T] 2 c² (v) log
48
where we define
c())
sup inf aePx w'el VEVRR((
Σ anD (v(i) o')))))))))))))))))))))))))))' (3)
Here Vali (I%) denotes the set of environments in VK.1
which have change point not equal to xy and Pk is the standard K X-dimensional simplex.
From (Garivier& & Kaufmann, 2016) we know that solving the optimization problem in (3) can be informative both for understanding the complexity of the problem as well as for understanding what an optimal strategy would be. Let a (u) be the weights which solve the optimization problem (3), namely
c² c())) inf v'VVll
Σ (c)
These az, (v) determine the optimal proportion of samples we should allocate to each action, i e [K]. in environment v. While this optimization problem (3) is typically expensive

---

Coned-Confieenee Multiple Change Point Identification
4.2.1. SAMPLING RULE
(e.g. Garivier et al., 2018; Yang et al., 2022). For this, if at any time f, we have action i [K] that has been played less than vt times, then we play that action (breaking ties arbitrarily) as seen in Algorithm 1 lines 5-6. The idea is that this forced exploration is large enough to force our es- timates for the change point and optimal proportions to be close to their true values of x² and a². Simultaneously, this forced exploration should not be so large that our policy becomes overly exploratory and suboptimal. We will show in Theorem 4.5 that this combination of tracking and forced exploration is sufficient to achieve asymptotic optimality.
Suppose we knew we were in environment v. Then from our lower bound in Corollary 4.3 and equation (4), we would optimally play half of our actions adjacently either side of the change point 2; (i.e., we would play actions 24 and F. + 1 each half of the time and not play any other actions). However, in practice we do not know the environment o and therefore we do not know which actions a and x + to play. Hence, we propose the following tracking and forced exploration rules, which are of the general form of D-Tracking introduced by Garivier & Kaufmann (2016) for best-arm identification. We note that there are alternative tracking rules in the Track-and and-Stop literature such as C- tracking and proportional tracking, however these have been shown to be less effective empirically (Garivier & Kauf- mann, 2016; Degenne et al., 2019).
4.2.2. STOPPING TIME
We now present the second component of CPI, the stop- ping rule. We give an explicit definitionn for the stopping time and show that policy using it satisfies the first con- dition (equation (1)) of Definition 4.1 for Exact-(1, 6) policy, We emphasize that, unlike in many prior track-and- stop works, the condition for the stopping time can also be checked explicitly and directly, rather than needing to solve the optimization problem as in ( (10) (e.g. Yang et al., 2022; Garivier & Kaufmann, 2016). In particular, for our proposed stopping time defined in Proposition 4.4, we only need to check if the threshold has been exceeded in (7). No numerical optimization is required for checking this in each round, making it computationally efficient. This makes our proposed approach simple and further computationally efficient.
Tracking For the tracking component, first estimate the change point in each round 6, åt. We propose to use the following simple estimator for the change point which selects the action corresponding to the largest empirical change in mean, namely
(S) = argmax argmax.esllaa()) - (aa+1
(5)
Here S is the set of potential change points, which in this case is [K- 1], but may change when we consider multiple change points in Section 5. Here (t) is the empirical mean of the rewards obtained from playing action a up to time f. We choose this estimator due to its simplicity, but we expect alternative estimators, such as least squares, could also lead to similar results.
Proposition 4.4. Define the stopping time in Algorithm 1
TB min {t: 2(Th, (t) + T2.+1(t)
T2, (t)T.) (t)
AA, 2 S1..00] (7)
Once we have an estimate for the change point in round f, ft we can establish the tracking criteria by noting that if it were the true change point then we would want to play equally either side of this change in mean. Consequently, we estimate the optimal proportions for each action at time as (1) = 1/2 if i (. 1), and otherwise. Using these estimates, with the proportion of plays furthest below the estimated optimal proportions in round I. Let (1) be the total number of times we have played action i up to round t. Then in round f, we play
with
=2 (1) - (1)
We define the threshold
B(t, 6) log (t>(K - 1)/6) + log - 1)/8)
tracking criteria is to play the action
(8)
with 7 20 log(3). Then in any environment v VK,N where N 2 1 and any policy with stopping time T8, we have
( & x2) 56.
99)
Ti(1) at = -rggmnn (E
(I:() t - ai(1)
(6)
Proof. For a full proof see Appendix D. This stopping time is motivated by Chernoff stopping times (Kaufmann Koolen, 2021) of the general form
This is cquivalent to playing whichever arm has been played least out of (#r, + 1), namely ag vggnin.g(sa.++t))iii Ti((), as in Algorithm I line 8.
min {
t: inf Σ (T(DD(E B(t, VEVEI
Forced Exploration If we only do the above tracking, the quality of our estimates i; may improve slowly over time (if at all). Hence we additionally include some forced ex- ploration across the action space, similar to previous works
(10)
Since it is optimal to only play either side of the change point, we demonstrate that it is sufficient to only consider the sum in (10) over actions i E (#,, Rr + 1}.
5

---

Fixed-Confiee -excd-Confieence Multiple Change Point Identification
Algorithm 1 Single Change Point Identification (CPI)
5. Identifying Multiple Change Points
1: Input: confidence 5 E (0, 1)
While identifying a single change point is important, in practice we may need to confidently identify N change points. Hence, we extend our results and methods from Section 4 to consider multiple change point identification.
2: Play each action once
3: while (t) < B(t, 6) do
> Stopping time (7)
4: Update (a(t), ât, &t
5: if mi...( 3 (t) vi then
6:
Play action dr argmin (e (I.....K)) Ti())
7: else
5.1. Known number of changes
8:
Play = g 2,,
Suppose that we are in an environment with exactly N change points and the learner is given this information. In this case, we want to return estimate for the set of N change points which is equal to the true set of change points with probability greater than - ó. We refer to a policy that does this as an Exact-(NVo) 6) policy.
9: end if
10: end while
11: Return: 27
Interestingly, the form of the stopping time in (7) is rem- iniscent of common tests in offline change point analysis literature (e.g. see the GLR test statistic CUSUM seen in Chen & Gupta, 2012; Verzelen et al., 2020). Our algorithm CPI is given explictly in Algorithm 1, where we denote
Definition 5.1. Exact-(NV, 6) policy For any v E VK.N= an Exact-(NN () policy x with stopping time T returns an estimate &, satisfying
((t) = (1) = T (t))
(1)T
E
(11)
P Pa =E²)== 1-6,
P PT < <00= 11
4.3. Asymptotic Upper Bound
By starting with a general bound (as in Theorem 4.2), we can prove the following lower bound on the expected sample complexity of any Exact-(N, 6) policy.
We prove an asymptotic upper bound for the expected sam- ple complexity of CPI (Algorithm 1). The broad idea for the analysis is to firstly prove that: if the empirical mean reward from each action is well concentrated, then, due to the forced exploration, our estimates for the change point and optimal proportions (f,, âe) should get closer to their true values (x", a²) over time. Hence, due to the tracking, the number of times we have played actions x= and x" + 1 adjacent to the change point should quickly increase and get closer to 1/2. Subsequently, the values of 2()) in our stopping time should increase quickly, passing the threshold and stopping the algorithm. The analysis for our upper bounds focuses on understanding the rate which this oc- curs. We state the upper bound in Theorem 4.5 with the proof detailed in Appendix E.
Theorem 5.2. For any Exact-(N,0) 5) policy with stopping time T, lower bound for the expected stopping time in environment E VK,N is
E E 2 (3(u)log
(12)
46
N
1
1
2 40 log
Σ
(13)
48
A
where we define
K ax D(,; uf)
())
sup inf aEPR WEVell
(14)
Theorem 4.5. For any u E VK,1, using algorithm π de- scribed in Algorithm 1, we can upper bound the expected sample complexity as
Here VRN (x,((*))) (x+)) denotes the set of environments in VK.N whose set of change points are not equal to It and Px is the standard K -ddimensional simplex.
ET, [T)
lim sup 8-+0 log( (1/8)
S c² (v).
If the learner knows that there is exactly N change points, then knowledge regarding the location of one change point can be informative for the location of an adjacent change point. Incorporating this information means that the optimal proportion of actions we should play near one change point longer just depends on that change point, but also on adjacent change points. Because of this, the optimization problem in equation (14) becomes more complicated and finding a general closed form solution becomes more chal- lenging than the Exact-(1, (1,, case in (3) where we do not have this coupled effect. However, we are able to lower
This demonstrates that CPI (Algorithm 1) an asymptot- ically optimal Exact-(1, 6) policy according to the lower bound in Corollary 4.3. We emphasize that this optimality is tight in terms of the constants that appear in both the asymp- totic upper bound and the lower bounds. In Section 5 we will illustrate that, due to the explicit solutions found for the optimization problems (3) and (10), we are able to construct simple and interpretable non-asymnaa asymptotic upper bounds for the sample complexity of our methods as well.
6

---

Multiple Change Point Identification
bound (v) to provide the final lower bound (13) in The- orem 5.2. Note that the lower bound in (13) is the sum of the complexities of finding a single change point (shown in Theorem 4.3) in N different settings, up to a factor of 2. Furthermore as we will see from the rest of Section 5, compared to settings where we do know the true number of change points (Theorem 5.2), the cost of not knowing the true number of change points is asymptotically at most a factor of two in the expected stopping time (Theorems 5.4, 5.5, and 5.7).
Now, suppose our aim is to confidently identify N change points out of set of m 2 N change points. In this case, intuitively the complexity of finding any N change points is lower bounded by the complexity of finding the N most easily identifiable change points, (* (N)) This is formalized in Theorem 5.5 where the first sum in (18) is over the largest changes mean. See Appendix for a proof.
Theorem 5.5. For any (ny time T, the expected stopping time in environment E VV..m for N S m < K is lower bounded by
5) policy a with stopping
5.2. Unknown number of changes
N Σ
When we want to confidently identify N change points in our environment, it is important to provide methods which are robust to the presence of additional change points. In particular, we would like to develop policies which are able to identify N change points out of an unknown number of change points. In this case, we want to return an estimate for a set of N change points which is in the set of true change points 2, where |=,|l
E [T 280 - 5) log
48
A
i==1
12og(2)
Σ A?
1
(18)
Note that, as - 0 the lower bound in Theorem 5.5 be- comes similar to the lower bound for the Exact- 8) poli- cies in Theorem 5.2 up to a constant factor of 2. Further- more, the lower bound in Theorem 5.5 becomes similar to Theorem 5.4, except we are summing over the N largest change points rather than all of them. In Section 5.3 we provide a policy which is simultaneously Exact-(NN 5) and Any-(N, 8). This policy is asymptotically optimal when the true number of change points is unknown (m 2 N) and optimal up to a factor of 2 when the learner is given the exact number of true change points in the environment.
2 N, with probability greater than 1 - 8. We refer to policy that achieves this Any-(N, 5) policy.
Definition 5.3. Any-(N, 5) Policy For any E Vx. where m 2 N, an Any-(N, 5) policy a with stopping time т returns an estimate 2, of size N satisfying
P' (2, 5 > 1 1--1- 5,
(15)
Pr (T. < 00) = 1.
(16)
Suppose that we had an Any-(N, 8) policy π and, for now, additionally suppose that there are exactly N change points in the environment (note that this is different to the Exact- (N, 6) setting considered in Section 5.1 where the learner knows there are exactly N change points). In this case, we can show that the optimal proportions become
5.3. Sequential Approach and Upper Bounds
Motivated by Binary Segmentation methods from offline change point analysis (e.g. Fryzlewicz, 2014; Scott& & Knott, 1974) and and the single change point setting studied in Section 4, we propose the Multiple Change Point Identi- fication algorithm (MCPI, Algorithm 2). MCPI works by sequentially identifying one change point at a time until we have found N. In particular we repeatedly run the loop in CPI (Algorithm 1 lines 3-10), which identifies one change point, total of N times. After each loop, we will have stopped and identified one change point. We then remove this action from the set of potential change points and add this action to the set of change points we will return at the end (Algorithm line 17). After this we repeat the process until we have identified N change points in total.
aj = j+1
(17)
2
AZ
for j E . zt.N J. and zero for all other aj values. This intuitively suggests that constructing an optimal policy requires (asymptotically) sampling most of our actions ad- jacent the changes in mean. The proportion of samples around each change in mean should be inversely propor- tional to the size of the change squared. This allows us to prove the lower bound in Theorem 5.4 below, detailed in Appendix G.
Edge Case (Multiple Equally Sized Changes) Suppose we had an Any-(1, 6) policy, which confidently identifies one change point, and there are multiple equally sized changes in the environment. For example A,,(1) = (2) We see from Theorem 5.5 that the lower bound only includes the complexity from finding the position of any single one of the largest changes. Hence, an optimal policy would sim- ply focus its sampling efforts around any one of the largest
Theorem 5.4. For any Any-(N, 6) policy a with stopping time T, a lower bound for the expected stopping time in environment U E VK.N is
1 46
N
1
Er,e [T] 2 800
8022og log
Σ iml
A7
7

---

Ceeed-Coniieene Multiple Change Point Identification
Algorithm 2 Multiple Change Point Identification (MCPI)
define A (m+1)) = O. We also let argmax N (i) A(N) > (() be such that Age) is the next largest change in mean strictly smaller than ((N) Intuitively, (1 repre- sents the time taken for forced exploration to provide good estimate for the positions of the change points in environ- ment v. Additionally, (6) represents the time taken for our tracking to put enough samples around the true change point for us to be confident in its position and stop. Using these definitions we provide the following non-asymptotic upper bound for the expected stopping time of MCPI.
1: Input: confidence 5 E (0, 1)
2: Input: number of changes to look for, N
3: Initialize + [K- - 11, + <
4: Play each action once
5: for phase j in {,,.... N do
6: while [t) < B(t, 6/N) do
P Stopping time (7)
7:
Update (t( āi
8:
if ji, E [K - 1] s.t. (19) holds then
9:
Update 8. = (S) > Simple estimator (5)
10:
end
11:
if (1...) (t) < v then
Proposition 5.6. For any environment E VK for 2 N, the expected sample complexity for Algorithm 2 is bounded by
Play action ar argmin ef ()
13:
else
14:
Play az =
(1)
15:
end if
B[Tal S To(0) + (v)
+ 2eK.
16: end while
17: Σ. S
18:
end for
Subsequently, by considering 6 - 0, we provide an asymp- totic upper bound for the sample complexity of MCPI and show that it is simultaneously Exact-(NV, 6) and Any-(N, 8).
Return: +
changes. By simply running CPI in this edge case, there is a risk that our estimate &, will fluctuate between different change points of equal size and therefore our actions will not be focused around just one change point. To avoid this, in MCPI we include condition that we only update our estimate d when one empirical change in mean reward is sufficiently larger than another. In particular, when there exists i.j E [K 1] such that
Theorem 5.7. MCPI (Algorithm 2) an Exact-(NN 8) pol- icy and an Any-(N, 5) policy. For any E VK. where 2 N, can upper bound the expected sample complex- ity of MCPI as
N
lim sup E [T8] 8-+ log (1/0
Σ 1%
1 )
S 80
(19) holds (with rt) defined in (20)). we update our estimated change point to be (S). (19) does not hold in round t then we do not update our estimate, namely dt + - This is included in lines 8-9 of MCPI (Algorithm 2). Note however, that if we know that there is exactly one change point or that there are no changes of equal size, then we do not need to check (19) before updating our estimate for the change point and this can be omitted.
(px(t) - (+) > (t)(t) - P (f) + rt))
We see that the sample complexity for MCPI asymptotically matches the lower bound for any Any- 5) policy (The- orem 5.5) with the correct constants. Furthermore we see that MCPI simultancously matches the lower bound for any Exact- (oect-N [N, 8) policy (Theorem 5.2) asymptotically up to (at most) constant factor of 2. Note that we could remove this constant by directly tracking and numerically approximat- ing the optimal proportions from (14), however this could be computationally very expensive and would not be robust to an unknown number of changes, unlike MCPI. In the special case where there is exactly N = change point and this is known to the learner, MCPI is also optimal with correct constants (Theorem 4.3).
We now provide a non-asymptotic upper bound for the ex- pected stopping time of MCPI. To do so, we define
r(1) Alog(t) + (ogg((2og(()) + 1/2
(20)
- (2)
We note that another alternative approach to identifying any N change points could be to extend CPI by directly tracking (as in (6)) with respect to an estimate of our optimal proportions (17). We suspect this alternative approach will also attain optimal upper bound asymptotically. However, this will lead to identifying all of the change points at the same rate. Whereas if there is one change point that is significantly larger than the rest, it may be advantageous for a practitioner to quickly identify this change first. This is what the proposed MCPI algorithm does.
N
83 5/N)
T((6) = min
T T - 2KTT 2
( (T))
1=1
(1) = min TeN:r(T) A(N) - A
4
Here 3 is the threshold function defined in equation (8). If there are exactly m change points in the environment we
8

---

Coeed-Confidenc Multiple Change Point Identification
dependent lower bounds the expected stopping time of policies with different objectives, illustrating how the mag- nitude of the change points affect the complexity of our problem. Additionally, we constructed the computationally efficient MCPI algorithm to sequentially locate N change points with fixed confidence. By proving non-asymptotic and asymptotic upper bounds we showed that MCPI asymptotically optimal under different objectives.
8000
CPI
7000
lower bound
6000
Stopping
4000
A related problem is the task of identifying all changes greater than some >> 0. This would be relevant in settings where there is no domain-specific or contextual knowledge of an appropriate number of change points to search for. We expect that would be possible to extend MCPI to this set- ting, but we leave this to future work. Another direction for future work extend our setting try to identify change points between piecewise smooth regions of continuous action space (e.g. A [0, 1). We could also consider differ- ent objectives such as minimizing the simple regret (i.e. the bias of our change point estimates) or maximizing the cumu- lative rewards in this piecewise constant setting. For now, we have filled a gap in the change point identification litera- ture by providing an in-depth study of the fixed-confidence multiple change point identification problem.
2000
1000
20
50
log(1/0)
Figure run the MCPI and algorithm a range of values for in environment vi. At each confidence level we repeat 100 nuns and plot average stopping time with 90 percent confidence intervals. We also plot the lower bound in Theorem 5.5.
6. Experiments
To complement our theoretical results we conduct experi- ments to test our proposed algorithms in synthetic environ- ments. In Figure 2, we consider an environment V with only one change point with means μ 2, 2, 2, 2, 2, 1, 1).. our proposed policy MCPI (setting N = 1) and range of choices for 5. At each of these choices for we run MCPI 100 times and plot the average stopping time. We also plot our lower bound from Theorem 5.5 on the same axes. From Figure we see that the our ex- pected stopping time increases parallel the lower bound, supporting our theoretical demonstration of the asymptotic optimality of MCPI. On the same figure plot the stop- ping times when, instead of tracking with respect to our estimated optimal proportions (4), we sample with respect to the oracle optimal proportions of the Bandit Online Clus- tering (BOC) algorithm (Yang et al., 2022). In particular, we provide BOC with the true number of change points (required as an input of BOC) as well as the oracle optimal proportions a" described in (Yang et al., 2022) for cluster- ing in d1. Despite the additional information provided to BOC, it does not take advantage of the piecewise constant structure of 01- Hence we see that BOC's sample com- plexity increases at a much faster rate than MCPI and the lower bound, emphasizing the sub optimality of BOC in the fixed confidence piecewise constant bandits setting, See Appendix A for further simulations with multiple change points.
A Acknowledgments
In this case,
The authors would like to thank Professor Niall Adams for support and insightful discussions about this problem. The authors would also like thank the anonymous reviewers and area chairs for their feedback and suggestions during the review process. Joseph Lazzaro supported by Roth Scholarship from the Department of Mathematics, Imperial College London.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
Aminikhanghahi, S. and Cook, D. A survey of methods for time series change point detection. Knowledge and Information Systems, 2017.
Auer, P., Gajane, P., and Ortner, R. Adaptively tracking the best bandit arm with unknown number of distribution changes. In Proceedings of the Thirty-Second Conference on Learning Theory, 2019.
7. Discussion and future work
In this paper we have studied the fixed confidence piecewise constant bandits problem. We proved multiple instance-
Barrier, A., Garivier, A., and Kocák, A -on-asymptotic approach to best-arm identification for gaussian bandits.

---

Coned-Confidecce Multiple Change Point Identification
In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, 2022.
Garivier, A., Ménard, P., Rossi, L., and Menard, P. Thresh- olding bandit for dose-ranging: The impact of monotonic- ity, 2018. URL https: /arxiv. org/ orgg/bal abs/1711. 04454.
Bauer, H. Minimalstellen von funktionen und ex- tremalpunkte. Archiv der Mathematik, 9:389-393, 1958.
Gopalan, A., Lakshminarayanan, B., and Saligrama, V. Ban- dit quickest changepoint detection. Advances in Neu- ral Information Processing Systems 34 (NeurIPS 2021), 2021.
Bubeck, S., Munos, R., Stoltz, G., and Szepesvári, C. X- armed bandits. Journal of Machine Learning Research, 2011.
Gramacy, R. and Lee, H. Adaptive design and analysis of supercomputer experiments. Technometrics, 51, 2008.
Castro, R. M., Willett, R. M., and Nowak, R. D. Faster rates in regression via active learning. In Neural Information Processing Systems, 2005.
Hall, P. and Molchanov, I. Sequential methods for design- adaptive estimation of discontinuities in regression curves and surfaces. The Annals of Statistics, 2003.
Chen, J. and Gupta, A. K. Parametric Statistical Change Point Analysis: With Applications to Genetics, Medicine, and Finance; 2nd ed. Springer, 2012.
Hayashi, S., Kawahara, Y., and Kashima, H. Active change- point detection. In Proceedings of The Eleventh Asian Conference on Machine Learning, 2019.
Chen, S., Lin, T., King, I., Lyu, M. R., and Chen, W. Com- binatorial pure exploration of multi-armed bandits. In Proceedings of the 28th International Conference on Neu- ral Information P Processing Systems Volume 1, 2014.
Hou, Y., Tan, V. Y. F., and Zhong, Z. Almost minimax optimal best arm identification piecewise stationary linear bandits. In The Thirly-eighth Annual Conference Neural Information Processing Systems, 2024.
Chen, Y., Lee, C.-W., Luo, H., and Wei, C.-Y. A new algorithm for non-stationary contextual bandits: Efficient, optimal and parameter-free. In Proceedings of the Thirty- Second Conference on Learning Theory, 2019.
Jamieson, K. and Nowak, R. Best-arm identification algo- rithms for multi-armed bandits in the fixed confidence setting. In 2014 48th Annual Conference Information Sciences and Systems (CISS), 2014.
Chen, Z., Karthik, P., Chee, Y. M., and Tan, V. Y. Optimal multi culti-objecctvve best arm identification with fixed confi- dence. In The 28th International Conference on Artificial Intelligence and Statistics, 2025.
Jamieson, K., Malloy, M., Nowak, R., and Bubeck, lil' ucb An optimal exploration algorithm for multi-armed bandits. In Proceedings The 27th Conference on Learn- ing Theory, 2014.
Degenne, R. and Koolen, W. M. Pure exploration with mul- tiple correct answers. In Neural Information Processing Systems, 2019.
Jourdan, M., Degenne, R., Baudry, D., de Heide, R., and Kaufmann, E. Top two algorithms revisited. Advances in Neural Information Processing Systems, 2022.
Degenne, R., Koolen, W. M., and Ménard, P. Non- asymptotic pure exploration by solving games. In Neural Information Processing Systems, 2019.
Juneja, S. and Krishnasamy, S. Sample complexity of parti- tion identification using multi-armed bandits. In Annual Conference Computational Learning Theory, 2018.
Fryzlewicz, P. Wild binary segmentation for multiple change-point detection. The Annals of Statistics, 42, De- cember 2014.
Kaufmann, E. and Koolen, W. M. Mixture Martingales Revisited with Applications Sequential Tests and Con- fidence Intervals. Journal of Machine Learning Research, 2021.
Garivier, A. and Kaufmann, E. Optimal best arm identifi- cation with fixed confidence. In 29th Annual Conference on Learning Theory, 2016.
Kleinberg, R., Slivkins, A., and Upfal, E. Multi-armed bandits metric spaces. In Proceedings of the Fortieth Annual ACM Symposium Theory of Computing. 2008.
Garivier, A. and Moulines, E. On upper-confidence bound policies for switching bandit problems. In Algorithmic Learning Theory, 2011.
Lan, Y., Banerjee, M., and Michailidis, G. Change-point estimation under adaptive sampling. The Annals of Statis- tics, 2009.
Garivier, A., Ménard, P., and Stoltz, G. Explore first, ex- ploit next: The true shape of regret in bandit problems. Mathematics of Operations Research, 2016.
Lattimore, T. and Szepesvári, C. Bandit Algorithmss Cam- bridge University Press, 2020.
10

---

Coleed-Cneeeeece Multiple Change Point Identification
Lazzaro, and Pike-Burke, C. Fixed-budget change point identification in piecewise constant bandits. In The 28th International Conference Artificial Intelligence and Statistics, 2025.
Magureanu, S., Combes, R., and Proutiere, A. Lipschitz bandits: Regret lower bound and optimal algorithms. In Proceedings of The 27th Conference on Learning Theory, 2014.
Park, C.,, Qiu, P., Carpena-Núññez, J., Rao, R., Susner, M., and Maruyama, B. Sequential adaptive design for jump re- gression estimation. In ArXiv Preprint ArX1v:1004.01448, 2021.
Park, C., Waelder, R., Kang, B., Maruyama, B., Hong, S., and Gramacy, R. Active learning of piecewise gaussian process surrogates. In ArXiv Preprint ArXtv:2301.08789 2023.
Qin, C., Klabjan, D., and Russo, Improving the expected improvement algorithm. In Proceedings of the 31st Inter- national Conference Neural Information Processing Systems, 2017.
Russo, D. Simple bayesian algorithmss for best arm identifi- cation. In 29th Annual Conference on Learning Theory, 2016.
Scott, A. J. and Knott, M. A cluster analysis method for grouping means in the analysis of variance. Biometrics, (3):507-512, 1974.
Srinivas, N., Krause, A., Kakade, S., and Seeger, M. Gaus- sian process optimization in the bandit setting: No re- gret and experimental design. In ICML 2010 Proceed- ings, 27th International Conference on Machine Learn- ing, 2010.
Thuot, V., Carpentier, A., Giraud, C., and Verzelen, N. Active clustering with bandit feedhack, 2024. URL https:/ //arxiv///xvv...// org/ abs /2w..2206...2 11485.
Verzelen, N., Fromont, M., Lerasle, M., and Reynaud- Bouret, P. Optimal change- point detection and local- ization. The Annals of Statistics, 2020.
Yang, J., Zhong, Z., and Tan, V. Y. F. Optimal clustering with bandit feedback. J. Mach. Learn. Res., 2022.
Yavas, R. C., Huang, Y., Tan, V. Y., and Scarlett, A gen- eral framework for clustering and distribution matching with bandit feedback. IEEE Transactions Information Theory, 2025.

---

Fixed-Con Confodeenee Multiple Change Point Identification
Appendix
A. Additional Experiments
In addition to the experiments shown in Section 6, we simulate our methods environments with more than one change point. For example, Figure we consider and environment D2 with K 19 actions and 2 change points with mean rewards Meg (2, 2, 4, 4, 4, 4, 0, 0,0,0, 0,000, 0). In Figure we again plot the average stopping time when running the MPCI algorithm inputting N = 2 100 times at different values for log(1/0). We also run BOC with oracle weights. We again see that the stopping time for BOC increases at much faster rate than MCPI (which stays approximately parallel to the lower bound from Theorem 5.5). We see similar results when running the same experiment but using environment 1y K = 9 actions and with N = 3 change points. Here the mean rewards are Hoy = 3, 4). The results from simulations on this environment are Figure 4.
BOC
2000
lower bound
Stopping Time
1500
1000
500
0-
20
40
60
70
90
100
log/1/6)
Figure 3. We the MCPI and BOC algorithm range of values for ō in environment v2. each confidence level repeat 100 runs and plot the average stopping time with 90 percent confidence intervals. We also plot the lower bound in Theorem 5.5.
8000
MCPI
BOC
7000
lower bound
6000
Stopping Time
5000
4000
3000
2000
1000
0
20
30
40
50
60
70
90
100
log(1/5)
Figure 4. We run the MCPI and BOC algorithm at a range of values for 5 in environment Us. At cach confidence level we repeat 100 runs and plot the average stopping time with 90 percent confidence intervals. We also plot the lower bound Theorem 5.5.
12

---

Fixed-Corie CC--fideneeeeee Multiple Change Point Identification
also run MCPI in environment 04 with (2, 2, 2.5, 2.5, 2,5,
Finally,
5 change points Meg
1.5, 1.5, 1.5, 1.5, 1.25, 1.25). In this case, however only input N 1 into MCPI such that MCPI will search for only one change point. In this case, where there are additional 4 change points present, simulate the performance of MCPI 1000 ties at each of a range of values. We then plot our average observed stopping time and compare this with the lower bound Theorem 5.5 with N 1. We again see that the average stopping time MCPI approximately parallel the lower bound, supporting our theoretical results that MCPI is an asymptotically optimal any-(N, 8) policy which robust to an unknown number of additional change points present the environment.
2500
MCPI
lower bound
2000
Stopping Time
1500
1000
40
70
90
log(1/6)
Figure We run the MCPI algorithm with N 1 at a range of values for in environment d4 At each confidence level we repeat 100 and plot the average stopping time with 90 percent confidence intervals. We also plot the lower bound in Theorem 5.5.
13

---

Fixed-Con Cexcd-Confieence Multiple Change Point Identification
Proofs for Section 4
B. Proof Sketch of Theorem 4.2
The proof of this Theorem can seen both Theorem of (Garivier Kaufmann, 2016) and Theorem 33.5 of (Lattimore Szepesvári, 2020), where the difference that we include additional structural assumptions on the mean rewards in our environments and we have different objective from best arm identification. In particular, reiterate the infimum in Theorem 4.2 is over the "alternative' set of piecewise constant environments e' which have exactly one change point which is not equal to z.
We repeat the two important steps here for clarity and motivation. Firstly, using a change of measure argument and considering any v' Valt
K,1 (rt), they show that
K
Σ
E. (x,,)((()))(,,, vf) 2 log(1/46)
(21)
Secondly, they use (21) and definition of e² (v) show the following steps
ETr,u[Ta] (²(v)
K
BT, sup
inf aEPk de VeVlll (1rg)
Σ
a Duis 2/)
==1
K
Em,oo (Ti(T)) D(
2 [T v'EVal((zg)
inf
(22)
ET
inf (EVale(at) i-1 (rro(T((
Σ
1og((/46)
The proof is then complete.
Recall the definition of a" the solution of the optimisation problem in equation (4.1). Then observe that the only way to achieve equality equation (22) for o: _r.
(Ta)) to hold. Hence, to asymptotically achieve the lower bound
presented in Theorem 4.2, we want to have the proportion of times we play each action equal to a", Hence, we often refer to a" as the vector of optimal proportions.
14

---

Conel-Coofieence Multiple Change Point Identification
C. Proof of Theorem 4.3
show that we can explicitly solve the following optimization problem for c²(v)-
K
e (v)
sup inf VEEV
Σ
o. D (1))
aEPR
First, suppose we fix some Pk. Then we try to choose v' Volt (xt) minimize
D(D,
(23)
Denote the mean rewards in environment v as ( and the mean rewards in environment as (41)
Case 1: Consider some r' such that x.. > z. Then, we can rewrite the sum in (23) as
K
dy a; o() +
K
a (1,, of) = Σ
Σ
o; 2(e,)))))) +
Σ
a; of)
1=1
im +1
K
adlm 12)2 +
adlux - 1/)2+
+
Σ 1=x
ag(ux - 12x)2
(24)
2x
i=
Where (24) comes from the definition of the KL divergence between two Gaussian distributions. In order to minimize the third term in (24), we choose ''x= JA.. In order to minimize the first two terms, we choose
E1zz++1 ag
1 + (UX 11)
Σ
Ogi + E1 04
We plug these choices for 14, uxx into (24) to get
2
Σ
Li=l 0i
Ei= 0i
Σ ay D(v,
(25)
202
E ag + 2i=0z+1 ai)
which is minimised when xy x + 1.
Case 2: Now, consider some o' such that v x; Similar to case 1, we minimise the sum in (23) by setting
11 m
E +1 0g
Px in + (px 11)
Σ +1 03 Eizzz+1 Oi
K
th, xr
attain
15

---

Fixed-Con Conlloonnedeeeee Multiple Change Point Identification
K
A
E Limzy si az) (I (Zimag+) Ois
0 (u; 1/))
(26)
202 Lim +1 O4 + 2izaz+1 a3)
Combining Cases To Find at: The above arguments show that the 'closest' environments to v are when we shift the change point by either the left or the right. We therefore have that the unique maximizing choice for a will minimize the minimum of (25) and (26).
& Σ
A²
Di=1 0i) (azg+1)
A (ax;)
k Zi 04
argmax inf aEPk (xt))
a; (0,,) = argmax min
aEPk-1
2x²
2i=1 0i + aaz+1
202 anz
2i Oii
K K
1/2 i { x
1}
0
otherwise
Hence, we have attained (4). This also proves the Theorem by plugging this back into (23) and subsequently our calculation for c² (v) into Theorem 4.2.
16

---

Fixed-Confidenc Multiple Change Point Identification
D. Proof of Proposition 4.4
Before starting the proof, we note that in previous works using Track-and-Stoc methods, a Chernoff stopping time was used (Garivier& Kaufmann, 2016). This stopping time stops the algorithm when an infimum of a normalzzd sum (Kaufmann & Koolen, 2021; Lattimore & Szepesvári, 2020) crosses some threshold 3. The general form of these stopping times are
Σ TTOD(O0) 2(.00)
min L: inf (.
(27)
where ê an estimate for the environment, However, our setting since it is optimal to only play either side of the change point, we demonstrate that is sufficient to only consider the self- normalized sum over actions i E {#z, 2g + 1] since we expect the contribution from these terms dominate. Namely, we will define our stopping time to be
21+1
Σ ((AD()()))0) (0000)22(0) PCt.01
min t: inf ('E 2=
(28)
We now prove that (28) is appropriate stopping time. Fix environment E VK, and a policy æ with the stated stopping time (28). Denote IR* the mean reward vector in environment Use any estimate for the change point. We then have the following sequence of inequalities, where the first steps are motivated by the Track-and-Stop analysis for best arm identification in Lattimore & Szepesvári (2020).
P Px,0 (#+ # xt)) P Fr,e Vall (i+))
S Prx x
[Tg (T) (T) - )2,) ) + Te, (1() - +22+ 2)(T))))
(29)
< xx,00
3s E CONNtt ,3k E jK - 1]: [Tx(s) - 22x + (=)++(()
MK+1)7 2 B(s,
K-1
1 [1((())(((())
P T.
+ TT++ - - 2(,,0))))
k=1 s=1
2 ((ss,) +11 exp(-B(ss,0)
exp(3)
(30)
2
Where (29) comes form the definition of our stopping time (28) and the final inequality (30) comes from Theorem 2 of (Magureanu al., 2014). Now, we will make similar arguments Garivier al. (2018) complete the proof. We first point out some helpful observations.
Lemma D.1. The following inequalities hold for all 2 1 and 6 (0,1) 1)
(i) 8),, < 9 log
Ly(K -1)
(ii) log(t) S 8)
(ii) 8(t, 2 1
Proof. These results follow from the definition of our threshold B, defined in equation (8) and the fact that >( - 1)/8 2
17

---

Fixed-Con Conedd-oneeeeeeeeeeee Multiple Change Point Identification
Now, by plugging in our definition for 3(1,6) into equation (30), get the following sequence of inequalities.
cxp(3)
(3(s, (5(s,, 5) log(s) 1))
P Px # xx)) S
48y (K 1)
(s - 1)/6)
1
cxp
4 (3(s,8))
(31)
km ==1 4s7 (K<
log" (s7(K 1)/6)
9 log (z(k)-1)
K-1
cxp(3)0
8
(32)
487(K IK 1) log" (sy(K - 1)/6)
exp(3)o
g6
sy(K - 1) log (0>(K - 1)/6)
9o (3)
7(K 1) 2=1 l (sy(K - 1)/8)
90 exp(3))
(33)
7(K -1)
8 log 2 (3s)
9o cxp(3)5
2
(34)
7(K 11 log(3)
Where equations (31) and (32) come from using the facts from Lemma D.I. Furthermore, the inequality in (33) is true since we have 7(K 1)/5 2 3 from our definition of y. Inequality (34) is true by using an upper bounding integral.
1
1
2
llog" (3s)
1og²(3)
log (3s)
log²(3)
3log(3)
log(3)
The final equation comes from our definition of y. We have therefore proven that the stopping time (28) is appropriate stopping time.
Finally, by using similar steps as in the proof of Theorem 4.3 in Appendix C we can prove the following lemma. Lemma D.2. The solution to the optimization problem within stopping time is (28) is
d++1
Te, (t)TT,+110 A2 (t), + 1
inf V'EVeIL
(c))6((()))
By plugging this into equation (28), recover the form of the stopping time in Proposition 4.4 and the proof complete.
18

---

Fexed-Confidene Multiple Change Point Identification
E. Proof of Proposition 4.5
For this asymptotic upper bound our will stay somewhat close the structure of the original track and stop analysis from (Garivier& & Kaufmann, 2016). The following Lemma is consequence from Lemma 6 in (Degenne al., 2019), the idea being that we define the good event ËT to be when all of the empirical means for all the arms are well behaved all times up to time T.
Lemma E.1. Define the event
E = Ys St [K] (Pa(s) - Hal? 1log(1) + 2 2ogg(2 (2 log(())
(35)
(s(s)
Then
logt
+oc
AA 223, 3, Pn(Ef) S 2eK
Σ
P P((()) S 2eK.
and
+00 (ET) < 2eK
logt t2
log x 4000 f
S
2eK
dx 2eK.
#=1 x²
t=3
Now, if the good event E₁ holds and our empirical mean rewards for all the arms are well behaved, then we know that even our simple estimator é, for the change point will eventually always be correct after some time Tj. We write this formally in the following proposition.
Now, by defining
4 log(T) 2 2og (ogg())))))))))))))))))))))))))) + (v( min T:
A A2/4
(vT - K)+
we get the following useful proposition.
Proposition E.2. For any T' 2 Ti, on the event ET, have that our estimate is correct. 7T x²
Proof. Under event Er and for T > (1) we have that the empirical means at time T well concentrated Va [K] (T) 121 < 2²/4. This is true since our forced exploration will enforce that Vs E N (a(8) 2 (V8 K)+ Hence, by our definition for our simple estimator (5), we know that the estimate for the change point at time T will be correct.
Hence, if we are always correct in our estimate for the change point after time Ti then our estimate for the optimal proportions will be correct after time Ti (v). Therefore, due to our tracking procedure, the proportions of samples we make for each action will get closer the optimal proportions at the following rate.
Proposition E.3. There exists a constant Ti (v) E N4 (which depends only on the environment) such that for any T 2 Ti, on the event ET, we have
T, max (T(()/t-a - -ail 1 (K (v)
21
Now, if the proportion of plays for each action getting closer to the optimal proportions as described in the above lemma, then we know that the number of times we play actions x² and x + will get closer to 1/2 and therefore the value of Z. (defined in (11) for our stopping time equation (7)) will get larger. Hence, we are able to provide lower bound for Z,. In order do so, first make the following definition.
Definition E.4. Let
((t) 1+ (K - (v)
21 (t) Alog(t) + 2 1ogg(2 +1
(Vt K)+
19

---

Coned-Confieence Multiple Change Point Identification
Then we define E(l) as the following quantity.
a(t := 0.5 (1/2-((()))) 2 1+2((t)
(A (A-r
Noting that as t + 0o, we have E(t) Theorem 4.3 defined in (3).
4" 5 c²()) which was the optimal coefficient defined for the lower bound
Then, as a concequence of our true proportion of plays approaching the optimal ones, we can write the following lower bound for Ze. Proposition E.5. Under event (c) we have for all t >> VT when T 2 (v) we have
Z: 2 tō(t).
Proof. Recall the definition of Z,, namely
(1)T2.2 (t) A Z, (t) + (t)
where we define 2 := 1ي (t) (t) The result then comes from our well behaved proportions under our well behaved event (e) from Proposition E.3 as well as the concentration assumptions from event (T(E) directly to lower bound Á 2
Now, using similar steps to the original track and stop analysis of (Garivier & Kaufmann, 2016), we have:
For T 2 (v) and assuming E, holds:
min VT + Σ 1(88>11
t=VT
SVT + Σ
1(2, S B(1,))
t=vT
T
<VT+ + Σ
l(t((t) s ((t,0)}
t=
SVT+ + Σ ((t(vT) ((T
t=
< VT + 3(T,5)
T(VT)
Hence, by defining the quantity
To(o) = min (TENt : VT+ 3(T,8)
T(vT) <T
we have that for any T max (Ta)) (T) then we have Ex + (TA S T), and therefore
P(Ta > T) < 2cK log(T)
T
20

---

Coee--Confidence Multiple Change Point Identification
Subsequently, we have
E B/r] Σ P(T8 >1
$ TT(() + +2T(2)) +
P( > t)
20
2eK log(t)
S (b()) + 22T(2) (6))
< To()) + 27) (v) 2eK
(36)
From this upper bound on the expected stopping time, we not that the only dependence on 5 in To(o) hence we focus on studying this since the other two terms will vanish when we divide through by log(1 /8) (asymptotically)) We can now use some arguments from (Garivier et al., 2018), where we restate their useful Lemma E.6 below, and by using our own definition for the threshold 3 we can carry out the following steps to upper bound (ō). First we define the two events
He(e) = min TEN+ :T - VT 2 T/(1 +
+
A
A
H₂(e) = min :TENt:aTT) a(VT) E
+
8
8
which allows to initially simplify the definition for To) follows where denote C = A2
5
(6) = min TENN= VT + B(T,O)
$T)
((VT)
TENT ((T,0) ((VT)T 1+c
< (c) + min
TEN+ ((T,8) S C.T
< (c) + H2(e) + min
[+c]
C.T)
I (e) + -12(c) + min
TEN+ log (T>(K - 1)/6) + 8 8log log((T((( - 1)/6) s
I+e]
(1+ Cτ
log (e(1+c) - log (1+ ( -1))
5
< (c) + H2(c) + max
7(K -1 exp (g(c/8))
C28
C28
(37)
Where for equation (37) we have used Lemma E.6. Hence, by plugging in the upper bound from (37) into (36), and observing the dependence of the upper bound on we attain the asymptotic upper bound stated in the theorem. Hence CPI has asymptotically optimal expected sample complexity.
Helpful Lemma
We state the following helpful lemma from (Garivier al., 2018). For 0 < < S 1/c, let be the function defined by
g(v) log
log
From this definition they state the following inequality in Lemma 10 (Garivier et al., 2018).
Lemma E.6. Let A, B > O, then for all e E (0, 1) such that (1 + e)/A < e and B/e > e, for all x > max (g(A/(1 + exp(g(e/BB) we have
log(x) + B log log(z) S Ar
21

---

Coeed-Confieenc Multiple Change Point Identification
Proofs for Section 5
F. Proof of Theorem 5.2
We first note that the proof of the first inequality (12) similar to Theorem 4.2 in Appendix B, except we now restrict to the
set of environments with exactly N change points (i.e. VK,N). ). In order to prove the second inequality (13) we simplify and only consider the set of alternative environments in which we shift one of the change points in by to the left the right.
Consider the following two sets of alternatives {ış}ī=1, {u C VK.v and we shift only the left/right mean reward adjacent to each of the change points in v. In particular, we define
Mo,t+1 for i i= Ho, otherwise
Me',a"
Me,i11 for i= +
Pv"
Mo,.
otherwise
Now, by denoting V {u,} Kリm
Valt K,N K,N
(2t).
We have that from the definition of cg(v) that
K
(()))
inf aEPk VVaa (2))
sup
Σ
a
D(D
of)
i=1
s sup inf oc aEPx e'EV'
Σ
ar (u;,))) uf)
1=1
A
A3
sup min PcPx
min
20 Ozii,
20
Og
+1
(38)
Hence, by substituting (38) into equation (12) of Theorem 5.2 we get the following.
1
log
46
< E Ex, [T]
sup aEPx
min
min
20
Out
20
azi
+1
1]
Ex, [T]
4a2
E
I
E,, [7] > 40 log
Σ A?
As required.
G. Proof of Theorem 5.4
Consider any alternative environment o' E VK.m where m 2 N such that the change points in are not a subset of the change points in v', namely x g .y. Then, since æ is an Any-(N, 6) policy and equation (15), we have that x;, g z implies that a = z is a failure event environment o' occurring with small probability less than
8 2 Pr = x.).
(39)
Furthermore, again due equation (15), we have that under environment v we have e, + 2 occurring with small probability less than
8 > P ( # x
(40)
22

---

Fixed-Con Conl-Cnnnedeeee Multiple Change Point Identification
Combining equation (39) and (40) gives the following, where apply the Bretagnolle-Huber Inequality (Theorem 14.2 Lattimore & Szzpesvári, 2020) in equation (41).
26
, ( + Ini) + P. (2r 2.o)
2 expl
(- DD(P n,u; P P,,,T)))
(41)
2 exp
Bu (())))))))))))))))0)
K
log
B (v)))
(42)
48
Now, consider a set of N alternative environments {1]]a=1 C Vn. where m > N. Let environment v/ have mean rewards equal to e everywhere except for actions aj ;= Lū.j and bj = Eej + such that there is no longer a change point there. In particular, for some l E [Mu.ays by, we set
eg when i= aj or i= bj
otherwise
Now, since equation (42) holds for any of the alternative environments in the set {1/) we have that the following set of inequalities.
K ()(())))((()))))))))))))))))))))
1
log
min
inf
E
48
Bx, [T]
sup
min
inf E
or D (v())
aEPx j
A
Og 0g
[r,
sup min oePx
(43)
20 Oig..
+ Okgin
-R,elT]
802
E
E, [T]
80 log
46
A7
Where in equation (43) have chosen the minimizing choice for lj in each environment v/.. Furthermore, we can show that the choice for which attains the supremum in equation (43) is
aj = jtt
2 2Σ A
for {zt " N. and for all other az values. for j {l,...,,, m). and zero for all other a* values, The proof is then complete.
23

---

Fixed-Con Con--onnndeeeee Multiple Change Point Identification
H. Proof of Theorem 5.5
will use a similar approach to the proof of Theorem 5.4 in Appendix G, except we will firstly use a slightly different change measure argument instead of the Bretagnolle- Huber inequality, Recall from Lemma I in (Garivier et al., 2016) we have that
D(F 2 (I( 2
(44)
for some event Where k1, y) is the Kl.-divergence between two Bernoulli distributions with parameters æ and y. Recall also that
kl(x,v) 2 x log(1/v) log(2)
(45)
Let E Vi.m where m > and let n an Any-(N, 5) policy. Now, for j [m]] define
A₂ = (+ E }
Furthermore, let environment v', E VK,++1 be equal to everywhere except in ( Fo,0+11 where the mean reward is equal to lj. namely
Hog, = () for i t " 0.0
(uii otherwise
Using the transportation lemma (44), we have for any j [m]] and for any E that
kI (A)), (A,,)) S D 7, v: I m,,;))
Σ E. (T.((T))))
(46)
However, since (46) applies for any choice ly in environment v/y, we can take the following infimum over the RHS.
K
kl (()P (Aj)) < inf
E (1))
1
i=1
-
= E
Ta. Tai
(T) + Txx Trim (7)
(47)
80
Now, (47) holds for any j [m]. Hence, if we define ky (C(P,,o(Ag)). (A,)) and t,
Eg.v Ta: (T) + Te. vin (r) then from (47) gives us
ty t 03 800k
min je mm
( 80
sup
min
(48)
G mm f S....el 5E(m]
Ex [7]
(49)
m S
Here (48) comes from taking a supremum over the potential values for ty. taking into account that their sum is upper bounded by FF,,o (7] and (49) comes from finding the explicit solution this supremum (similar other lower bound proofs
24

---

Fixed-Confidene Multiple Change Point Identification
in this paper). Now, we try to lower bound the denominator of (49).
80
kj
8 kl(P (A)), n. (Az))
(50)
A
j=1
_ (Pn,((A)))og( n,,g (Az)) - log(2))
(51)
(i)
m
S
(Ag) log(1/0) log(2))
(52)
m
8
m 8
P
F.
log(2)
(53)
(5)
j=1
(
Here (50) comes from the definition of kj, (51) comes from using the trick in (45), and (52) comes from the Any-(N, 6) assumption on I.. Now, by defining ps = (, = 5), we note that
Px P =A. Pa,o E = E
psl(at) = 2
Σ
psl(tl) =
Sc(K]
SC(K]
Hence we can lower bound the first sum on the right hand side of (53) by a linear function of the variables {ps |S| S C 2,), namely
80 Σ
8
A2 P (A)) 2
log (1/)
E psltri e S = c x.).
(54)
SC[K]
Since the right hand side of (54) is a linear function of the ps variables and by the fact that æ is Any-(N, 5) we have 1- 8 & ΣI[S = S C =t} S 1. Hence, by Bauer's ' Maximum Principle (Bauer, 1958), the right-hand--a of (54) is minimized at an extrema of the set of potential ps variables (i.e. ps 5 for some 2 and ps = otherwise). In particular we get
80 2
Sa²
P PT.u(A) log(1/)) 2
min Scg..15|=N
(1 - 8)
log( (1/8).
A
())
1=1
(
N 8g
= (1 11-00 6)
log(1/6).
(55)
The, by plugging (55) back into (53). Then plugging (53) back into (49) we get our lower bound.
25

---

Tixed-Confidence Multiple Change Point Identification
I. Proof of Proposition 5.6
We have the following concentration inequality as a consequence Lemma 6 in (Degenne et al., 2019).
Lemma I.1. Define the event
1.4 88 S S1 [K] (ia(s) - pal2=
llg(()) 2 log(2 log (()) + 1
(56)
(s(s)
Then
logt
+00
v9 2. Pa(E)) S 2eK
Σ Pu(E)) - 2eK.
and
toc Σ (E)) S 2eK t=3
log t t2
+00 log x
- 2cK
dx 2cK.
x²
1=3
x=1
Now, if we define
4 Alog(t) + 2 log log(()) + 1/2
r(t)
(t1/4
K)+
then have that
{ Ys E 2). [K] (Aa(s) pal
E, - =
- puls
This is true since, for E [12/2, 1], our forced exploration in MCPI means that (s) 2 (52/2 K)+ (11/4 K)+. We now state a useful Lemma which consequence of the definition of our simple estimator (5) and the event Ey Lemma 1.2. Define
[1(0) min TTENT: :r(T) ANN - -
4
Then, for 2 Tile), we have that
Ys E 11212, ,1, E (=a))..., mmn)
E - B:
Note that event B, implies that all tracking actions (see line 14 Algorithm 2) that are played in rounds E [e//2, []]] will be in the set
a, E (at + L.... z(N). z(N) + 1}
We can now present the following Lemma.
Lemma L.3. The total number of tracking actions MCPI will play in rounds s E [t1/2, e) before stopping, under event E,, is al most
N
8(1, 5/N)
A ()) 2r(1))²
Proof. Let us denote nj to be the number of tracking actions in which we have played action j between rounds 21/4 and t. Also let
N₂ = min min (Mrigy +1 be the smallest number tracking actions played by iig) or zz)) + 1.
Now, let s [t1/2, t). If we then define
Toi, (s)Ta; 2; (1(s)
2,(5) 2(To;, (s) + Te: +1 (s))
12 1/ (s).
26

---

Conel-Coofieence Multiple Change Point Identification
Then since T2i (o), (3) +1() 2 Ny. have
N A (s). 2(s)
2g(0) 2 2(N, +N₂)
Therefore, under our event E,,
N₂ (A6) 2r(1))²
2,(5) 4
(57)
Note, by the definition of our stopping time ( see (7) and line Algorithm 2) and since B(t, ( > B(s, 8/N); when
2,(s) 2 5/t,
occurs, we will never play actions " or =G)) + when tracking again. Hence, from (57), if
N
(58)
holds then we will never play actions = ((y) + when tracking again. By isolating the Nj values in (58) and summing through j E [NV] (i.e. summing over the total number of tracking action we can mae before stopping), we get the restul in the lemma.
Now, in rounds [1,t] there will at most K V forced exploration actions. Hence in rounds [t!/2, there will be least (t 2K vt) tracking actions. We therefore get the following lemma.
Lemma 1.4. Ift > (v) and > To( = min TTENT :T 2KT
2 EM
88(T,8/N) (A 2-(())
}. Then
E +1
Now, putting everything together using Lemma 1.4 and Lemma 1.1 gives us the following high probability upper bound for stopping time MCPI.
Theorem I.5. Let t max max(Ti (T) (o))) then
2cK log(t)
P(r <) < P(E))
< f2
Then, as consequence of Theorem 1.5
20
Birl Σ P(r8 >)
<T((0) +T
Σ
P(T8
(TT
8
2eK log(t)
Tb()) + T
Σ
(=Ta())+T,
S (T()) Ti + 2eK
As required.
27

---

Fixed-Con Conffddeee Multiple Change Point Identification
J. Proof of Theorem 5.7
Now, to prove the asymptotic upper bound on the expectation. Note that the final two terms of the non-asymptotic upper bound (Theorem 5.6) do not depend on ó and hence they will vanish when diving through by log(1/6). Hence, we focus on studying the first term (6). To do so, define the following, where E2, e > 0 are any small real number.
Te(e2) min EE ST-2KT5 T(1 } }
N
N
Ts(es) = min TEN+:
(A()) 2r(T))²
-
2
+
E3
i=1
i=1
We can then write
N
+63 {
To( s T2((2 + Ts((s) min
TENt : T(1 (2) 88(T,8/N)
Σ
1
(/)
T2((2) + (esss) min
TENt T(1 e2) 1og(1/8) (8(T,6/N)
log(1/6)
Σ
N
1 (3)
63
Hence, we have
E[r]
lim sup 8-0
min
T TENT: : T(1 e2) 2 8 8log(1/8)
Σ
+ Eg
log(1/0)
(18)
A (6)
8l0g(1/5)
Σ AZ
+ Eg
log(1/0)(1 - 2
N
8
Σ
+
62
A
However, 62 and 63 were arbitrary hence we can send them to zero 62, 63 -> 0 to attain the upper bound.
28

---

Coxcd-Confidence Multiple Change Point Identification
K. Additional Discussion
K.1. Complexity Comparison With Best Arm Identification
In order to compare the complexity of best arm identification and change point identification we construct a simple example in which there unique 'best arm' (with largest mean) and exactly one change point follows. Suppose we are in an environment with arms (o*-Gaussian) with mean rewards (M, p.....,... J,, μ + A) for some Je R. From (Garivier & Kaufmann, 2016), the complexity of the best arm identification problem in this environment will asymptotically be of order
1
K A
log
Now, from our Corollary 4.3 the change point identification problem complexity of order
log
2
We no longer have linear dependence K the change point identification problem since we can use our piecewise constant structure and information from across action space to confidently locate the change in mean. On the other hand, in the best arm identification problem, we have to sample each of the individual K arms sufficiently to confidently identify the arm with the highest mean reward.
29


Reviews:
[{"review_id": "wf1k0t1MEI", "reviewer": "Reviewer_tqCG", "summary": "This work introduces a fixed-confidence piecewise constant bandit problem, and provides instance-dependent lower bounds for the complexity of change point identification in this problem. This work also devises a computationally efficient algorithm as a variant of track-and-stop and prove its asymptotic optimality.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed, constructive comments and we are glad that you found the problem novel. We provide some responses to your comments below.\n\n---\n\n**Related Literature:**\n\nYou are correct that most of the literature on bandits with change points is focused on non-stationary environments which change over time and these exploit online change point analysis methods. One of the novelties of our work is that we instead consider a discontinuity in the action space and assume that the mean rewards are stationary across time. This is motivated by several real world problems (see below). This was discussed in Section 2, however we will include further discussion earlier in the paper to avoid confusion and emphasise the novelty of our work. Thank you for the suggestion. \n\n---\n\n**Order of the arms:**\n\nOur goal in this paper is to develop algorithms for settings in which there is structure in the mean rewards across the action space. This is motivated from experimental settings in which the order of arms have a spatial or experimental meaning. For example, in material development we may want to identify under what experimental conditions new materials abruptly change between different physical behaviours (Park et al., 2021). Hence, we could test the behaviour of a new material at different pressure levels. There is a natural ordering of pressure levels. Moreover, we expect similar behaviour from the material as we increase the pressure until we observe abrupt changes in its behaviour. To find the location of the changes it is necessary to consider the fixed natural ordering of pressure levels. In this setting, and many others, it would not make sense to randomize the order of the arms as this would distort the meaning of the problem. \n\nSection 1 discusses several other real world settings where there is a change point in an action space with fixed ordering. We also point out that there are many other well-studied bandit problems which consider fixed orderings of arms, for example montone bandits [1] and continuum armed bandit problems such as Lipchitz bandits [2]. \n\nWe finally note that the problem where we do not care about arm ordering and aim to group arms into clusters with the same reward is known as Clustering Bandits (Yang et al., 2022). As discussed in Section 2, this is a different problem to the one we study, and we show that exploiting the structure present in our problem can lead to improved performance.\n\nWe hope this addressed your main concern and you may consider raising your score.\n\n---\n\n**Complexity of our setting vs best arm identification:** \n\nAs suggested, suppose there are K arms ($\\sigma^2$-Gaussian) with mean rewards $(0,...,0,\\Delta)$ such that there is a unique ‘best-arm’ and one change point. From [Garivier & Kaufmann, 2016] the complexity of the best-arm identification problem will asymptotically be of order $K\\frac{\\sigma^2}{ \\Delta^2}   \\log(1/\\delta)$ and from our Corollary 4.3 the change point identification problem has order $\\frac{\\sigma^2}{ \\Delta^2}   \\log(1/\\delta)$. We no longer have a linear dependence on K since we can use our piecewise constant structure and information from across our action space to confidently locate the change in mean, whereas in best arm identification we have to sample each of the K arms sufficiently to confidently identify the arm with the highest mean reward. We will include further discussion of this in the paper, thank you for the suggestion. \n\n---\n\n**Regret Extension:**\n\nWhile the pure exploration set-up of this paper and the regret-minimisation set-up in other works are distinct, it would be interesting to consider extensions of our setting to the latter. As you allude to, an outcome of our learning methods could be the identification of regions in the action space with high mean reward. However, our current methods are designed to specifically locate the change points in piecewise constant structures, regardless of the adjacent rewards. Therefore modifications to our methods and analysis would be necessary in order to focus on regret minimisation. Hence, for now we leave these ideas for interesting future work and will include a discussion of this in the paper, thank you for the suggestion.\n\n---\n\n**Definition:** \n\nIndeed $\\hat{\\Delta}$ was defined later in line 1011. This should have been included earlier and this will be rectified, thank you for bringing this to our attention.\n\n---\n\n**References:**\n\n[1] Aziz, Maryam, Emilie Kaufmann, and Marie-Karelle Riviere. \"On multi-armed bandit designs for dose-finding trials.\" JMLR, 2021\n\n[2] Magureanu, Stefan, Richard Combes, and Alexandre Proutiere. \"Lipschitz bandits: Regret lower bound and optimal algorithms.\" COLT, 2014.", "claims_and_evidence": "yes", "methods_and_evaluation_criteria": "yes", "theoretical_claims": "partially, the theoretical claims seem to be correct", "experimental_designs_or_analyses": "yes, this work uses a simple and straightforward experimental design, but I have some questions for the setup, especially for ordering K arms, see \"Other Comments Or Suggestions\" below.", "relation_to_broader_scientific_literature": "The key contributions of this paper is related to multi-arm bandit problems, but I think the scope might be a bit narrow --- there is no concrete application examples provided to justify the setup, also the change-point defined in this work is a bit confusing since it requires a perfect ordering of the arm indexes. And the work is less related to change-point detection literature which instead focuses more on temporal changes.", "essential_references_not_discussed": "I am only familiar with a few key papers in this area, and I am not aware of other works studying the same problem, so to the best of my knowledge, no.", "other_strengths_and_weaknesses": "strengths: a novel problem for identifying change-point within arms, and theoretical lower bounds on sample complexity are provided; moreover, the practical algorithms that can achieve asymptotic optimality are also proposed. \n\nweakness: the motivation for the problem setting considered is a bit vague, and it is not clear whether such change-point identification can lead to some downstream task performance improvements such as reward maximization, etc. Also it seems to be a strict assumption (or need certain prior knowledge) that the ordering of the arm indexes satisfies the N change-point assumption/definition in this work.", "other_comments_or_suggestions": "For the scenario with one or multiple change-points, the formulation presented in equations on lines 120 and 129 assumes a \"correct\" ordering of K arms, such that the change-points are defined in terms of the arm index j∈{1,…,K}. Could the authors justify why such an ordering always exists or can be assumed in practice? For example, without such pre-knowledge of the correct ordering {1,1,1,2,2,2}, I could perhaps order the arms to be {1,2,1,2,1,2} in their mean reward, and does the proposed method still work in such random ordering?\n\nTo elaborate further on this point, a change-point refers to a specific time index at which the distribution changes (as commonly seen in non-stationary, piecewise constant bandit problems). However, in this work, the change-point refers to a spatial index. A key open question is thus how one should define an appropriate spatial ordering to preserve a \"piecewise constant\" structure for the mean reward function. Providing a more concrete practical example would help clarify this setup. In general multi-arm bandit problems, each arm may have a different mean reward, and even after grouping similar rewards together, these arms may not necessarily be neighbors in the given indexing. For instance, the example provided in Appendix A assumes a very restrictive scenario: without prior knowledge of reward means, the 19 arms are already ordered in a way resulting in exactly N=2 change-points (yielding the sequence 2,...,2, 4,...,4, 0,...,0). A random ordering of these arms, however, would produce significantly more change-points according to the definition used in this paper.\n\nMoreover, how does the problem considered differ from the best-arm identification problem in multi-arm bandits when there is only one change-point (or equivalently, when there are only two possible reward distributions: low and high)? A comparison of sample complexity between these two settings would be helpful. Additionally, since this work primarily focuses on the expected sample size (stopping time) required to accurately identify the “change-point,” it implicitly serves as an indirect approach to eventually maximizing the reward. This aspect naturally broadens the scope of the proposed algorithm. Thus, I am curious about how the eventual reward compares to traditional algorithms, such as UCB-type approaches. It would greatly clarify the practical utility of the proposed approach if the author(s) could briefly discuss this comparison.\n\nIn equations (7) and (11), the notation $\\hat\\Delta$ appears but is not defined.", "questions_for_authors": "see above", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "69ajl5UGiv", "reviewer": "Reviewer_gtRr", "summary": "Goal is to identify with high confidence the change points in the mean reward of the actions across the action space, by using as few samples as possible. A new Track-and-Stop algorithm is proposed for this task with asymptotic optimality. Matching lower-bounds are also proven.\n\n-- update after rebuttal --\n\nThe authors' clarification of the novelty of their work wrt Gairiver & Kaufmann 2016 is convincing and helpful. I decide to keep my score.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the detailed review and for your constructive questions. We are glad that you found the paper well-written and that you think our work would be interesting for the bandits/change point community. We respond to your comments below.\n\n---\n\n**Other Strengths and Weaknesses:**\n\nWe will include further discussion earlier in the paper on the distinction between our setting and non-stationary bandits, emphasising the novelty of our work. Thank you for the suggestion.\n\n---\n\n**Other Comments Or Suggestions:**\n\nThank you for pointing these out, we will update the paper accordingly.\n\n---\n\n**Questions For Authors:**\n\n1. (Gairiver & Kaufmann, 2016) is a seminal work and their tracking ideas have motivated the class of track-and-stop strategies and theory for a wide variety of works, including our own. This is because the lower bounds they construct for best arm identification are also applicable to a wide variety of other pure exploration bandits problems (Ch33.2, Lattimore & Sepesvari, 2020). However, the bounds they present are in implicit form (i.e. as the solution of an optimisation problem). Hence, their tracking methods are computationally expensive and somewhat unintuitive. In our work we are able to build off the bounds from (Garivier & Kaufmann, 2016) to provide intuitive instance-dependent lower bounds which can then, in turn, be used to define computationally efficient and intuitive tracking procedures for our setting. We will include additional discussion in the paper to clarify the novelty of our results.\n2. Having the additional knowledge of the true number of change points in the environment makes the learning problem easier than when the learner does not know the exact true number of change points. Intuitively, when the number of change points is known and we have some information about a subset of them, this could be informative regarding the location of the other change points. For example, suppose we knew there are exactly three change points $x_1 < x_2< x_3$ in an environment and suppose a learner has sampled around $x_1$ and $x_3$ sufficiently such that they are confident of their respective locations. These samples would then also be informative about the location of $x_2$ and will help identify $x_2$ with fewer samples, since we know there is only one change point remaining. Incorporating this information means that the optimal proportion of actions we should play near one change point no longer just depends on that change point, but also on adjacent change points. Because of this, the optimization problem in equation (14) becomes more complicated and finding a general closed form solution becomes more challenging. However, Theorem 5.2 tells us that the cost in sample complexity of not knowing the true number of change points is at most a factor of 2 asymptotically. Moreover, even when the number of change points is known, we can run the same computationally efficient algorithm, MCPI. This algorithm avoids solving the complex optimization problem and obtains sample complexity within a factor of 2 of the optimal (non-closed form) rate asymptotically.  We will improve the writing of this section of the paper to clarify this and include additional discussion, thank you for highlighting this.\n3. We believe that the theoretical (asymptotic) performance of MCPI (Algorithm 2) and the alternative approach we mentioned would be similar. However we re-emphasise that MCPI will quickly identify very large changes when they are easy to identify, whereas the alternative approach will identify all change points at the same rate due to the tracking methods used. More importantly, we believe Algorithm 2 is much easier to extend to the case where we have no knowledge about the number of change points as different/new change points can be approached sequentially. We will clarify this in the paper.\n4. We only update the $\\hat{\\mu}$ values after playing each of the actions once in both algorithm 1 and 2. Hence, the change point estimate will be initialised only after the initial set of observations have been made across the whole action space. We will update the paper to discuss initialisation, thank you for pointing this out.\n5. Define $\\hat{\\mu}_ {i:j}$ and $T_ {i:j}$ as the empirical means and the number of samples made from arms i to j inclusive, respectively. Then the CUSUM statistic for exactly one change point can be written (Eq 3, Verzelen et al., 2020) as $C_j = [\\hat{\\mu}_ {1:j} - \\hat{\\mu}_ {j+1:K}] \\sqrt{T_ {1:j}T_ {j+1:K}/T_ {1:K}}$. If we square this $C_j$ statistic, we see that its form is very similar to (11) except we consider only the samples adjacent to the change point rather than all actions to the left and right of the change point. This exclusion is important for settings in which the true number of changes is unknown, as considered later in our paper. We will add further discussion of this to the appendix.", "claims_and_evidence": "The paper is well-written, with matching upper and lower bounds presented for both the single changepoint and multiple changepoints settings.", "methods_and_evaluation_criteria": "Simulation result shows that the stopping time of the proposed algorithm follows the lower bound pretty closely.", "theoretical_claims": "I only checked the theoretical claims intuitively, but didn't check the proofs in detail. \n\nline 318-323: is the coupled effect helpful or unhelpful? it’s unclear from the writing here. What I find counterintuitive is that you say that it’s harder to obtain closed-form expressions for $\\alpha^*$ when N is known than when N is unknown (where you obtained (17)) Why is this the case?", "experimental_designs_or_analyses": "Can you compare the performance of Algorithm 2 with the alternative approach described in lines 415-417? This would be an informative result to have.", "relation_to_broader_scientific_literature": "An interesting work for the bandits community and changepoint detection community.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Presentation is clear, and I particularly appreciate how the authors always devote a sentence or two after each theoretical claim to explain its significance and implications. \n\n\nI think the distinction between the present setting and the non-stationary bandits setting described in lines 58-62 (right) should probably be moved to earlier on. This is important.", "other_comments_or_suggestions": "line 272 (right): it might be clearer to refer to Theorem 4.1 instead of Corollary 4.3\n\nnitpick: line 138 (right) it’s clearer to first define Exact-(N, $\\delta$) and then substitute in N=1 \n\nnitpick: can combine (11) into Prop 4.4 to simplify (7) and stay consistent with line 3 of Algorithm 1", "questions_for_authors": "Addressing the following questions would enhance my understanding of the presented results, and I will update my evaluation accordingly:\n\n1. Garivier & Kaufmann 2016 is cited quite a few times in the paper, could you elaborate the novelty of the present work as compared to GK2016? In particular, it seems quite a few results in this paper (e.g. Theorem 4.22, D-tracking) are specialised form of results from GK2016.\n\n2. line 318-323: is the coupled effect helpful or unhelpful? it’s unclear from the writing here. What I find counterintuitive is that you say that it’s harder to obtain closed-form expressions for $\\alpha^*$ when N is known than when N is unknown (where you obtained (17)) Why is this the case?\n\n3. Can you compare the performance of Algorithm 2 with the alternative approach described on line 415-417?\n\n4. eq (5): how do you initialise?\n\n5. line 237 (right): can you elaborate how Z(t) relates to the CUSUM statistic, by giving exact expressions? I'm not suggesting to add this to the paper, but just to help me appreciate your results better.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gWShFxXBMa", "reviewer": "Reviewer_wH8k", "summary": "This paper investigates the problem of identifying multiple change points in a piecewise constant function under bandit feedback, ensuring a fixed level of confidence in the results.\nThe authors consider two scenarios: 1)  known number of $N$ change points, and 2) unknown number of change points ($m \\geq N$).\nThey establish instance-dependent lower bounds on the sample complexity of identifying change points.\nBuilding on this, they design a computationally efficient algorithm inspired by Track-and-Stop, which achieves asymptotic optimality.\n\n---\n### **Update After Rebuttal**\n\nThe authors have successfully addressed my concerns, so I will maintain my positive score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your review of our work. We appreciate that you found the claims in the paper clear, that the theoretical claims were strong and well-reasoned, and that the experimental results were supportive of our theoretical contributions. We also are hopeful that the proposed methods will contribute to addressing additional interesting problems, as you point out. We respond to some of your comments below.\n\n---\n\n**Extension to the Continuous Setting:**\n\nIf the action space were continuous, then we cannot expect to identify a change point exactly. In this case, it would be reasonable to introduce some acceptable ‘tolerance’ $\\eta$ in error between our identified change points and their true locations. This would naturally lead to a uniform discretization with gaps of size $2\\eta$ meaning that there are $K = \\lceil 1/2\\eta \\rceil$ arms (note that this is similar to the setting considered by Lazzaro & Pike-Burke, 2025). The tolerance level $\\eta$ can either be set using domain-specific knowledge of an acceptable tolerance; or $\\eta$ can be set by assuming that there is some minimum distance between the change points. This is reasonable as we cannot expect to detect changes if they are arbitrarily close to each other.\n\nIt would be interesting to consider approaches more focused on this continuous analogue of our problem, such as adaptive discretisation/Zooming which are popular in continuous action spaces [1]. However, this would **still** need some reason/knowledge or domain-specific guidance on when to stop for this fixed confidence setting. This is because there could be changes in mean that occur over an arbitrarily small region of the action space (i.e. changes could occur arbitrarily close to each other). Hence there will be some change points that we may inevitably miss if we want to stop in finite time in general. This is normally avoided in regret-minimisation settings by assuming that the mean reward function is sufficiently smooth across the action space [1,2]. However, in our abruptly-changing setting there are no such smoothness assumptions. Therefore, to stop in finite time in our setting, we would need to make an assumption on the distance between adjacent change points (mentioned above) or a restriction on the number of change points (‘m’, which you point out). \n\nWe will include more discussion of the extension to continuous action spaces in the camera ready version. Thank you for the suggestion.\n\n---\n\n**References:**\n\n[1] Kleinberg, Robert, Aleksandrs Slivkins, and Eli Upfal. \"Bandits and experts in metric spaces.\" Journal of the ACM, 2019\n\n[2] Bubeck, Sébastien, et al. \"X-Armed Bandits.\" Journal of Machine Learning Research, 2011.", "claims_and_evidence": "The overall claims in the paper are clear and well-supported by both theoretical analysis and empirical results.", "methods_and_evaluation_criteria": "Overall, the  proposed methods make sense for the problem setting.", "theoretical_claims": "The theoretical claims are strong and well-reasoned. While I didn’t go through every detail of the proofs, they seem correct.", "experimental_designs_or_analyses": "The experimental designs are sound and sufficiently support the theoretical results.", "relation_to_broader_scientific_literature": "As discussed in Section 7, I agree that identifying all change points whose magnitudes exceed a threshold $\\epsilon >0$  is a more practical and interesting problem setting. I hope that the methods and insights from this paper can also contribute to addressing this more practical setting.", "essential_references_not_discussed": "I think the paper covers the related work quite thoroughly.", "other_strengths_and_weaknesses": "**Other Strengths:** \n1. The proposed algorithms are computationally efficient. \n2. The empirical results clearly strengthen the paper.\n\n**Other Weaknesses:**\n1. In the setting where the number of changes $m$ is unknown ($N \\leq m \\leq K$) and the original action space is continuous, the practical choice of $K$ is unclear. Specifically, if the true number of changes $m$ is unknown, it is impossible to confidently select an appropriate number of actions $K$ since $K$ must be at least $m$. This ambiguity limits the practicality of the algorithm, as one cannot set $K$ without prior knowledge of $m$.", "other_comments_or_suggestions": "No other comments.", "questions_for_authors": "Regarding the \"other weakness,\" can you provide any practical method to address the issue of determining $K$ (the number of discretization points) when $m$ is unknown?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper discusses a variant of fixed-confidence pure exploration problems where a finite sequence of arms is given and the objective is to detect the set of arms such that the expected reward is different from the next arm. Problem-dependent lower bounds are derived and the algorithms asymptotically achieving this bounds are also proposed. Several questions and concerns are raised for this paper, such as the validity and the required knowledge on the formulation and relation with existing work on BAI. These concerns seem to be mostly solved by the rebuttal, and I expect that the authors polish the paper by carefully revise the discussed points in the final version.

My small concern is that, while the algorithms and the theoretical guarantees are solid, they seem to be mostly within the already established framework of fixed-confidence BAI. So I think the justification and practical usefulness of the problem are very important, and the significance would be strengthened if there are experiments for more realistic scenarios.
Decision: Accept (poster)