Fixed-Confidence Multiple Change Point Identification under Bandit Feedback

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.

---

Extension to the Continuous Setting:

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

It 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).

We will include more discussion of the extension to continuous action spaces in the camera ready version. Thank you for the suggestion.

---

References:

[1] Kleinberg, Robert, Aleksandrs Slivkins, and Eli Upfal. "Bandits and experts in metric spaces." Journal of the ACM, 2019

[2] Bubeck, Sébastien, et al. "X-Armed Bandits." Journal of Machine Learning Research, 2011.

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.

---

Other Strengths and Weaknesses:

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

---

Other Comments Or Suggestions:

Thank you for pointing these out, we will update the paper accordingly.

---

Questions For Authors:

1. (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.
2. 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.
3. 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.
4. 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.
5. 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.

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.

---

Related Literature:

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

---

Order of the arms:

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

Section 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].

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

We hope this addressed your main concern and you may consider raising your score.

---

Complexity of our setting vs best arm identification:

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

---

Regret Extension:

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

---

Definition:

Indeed $\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.

---

References:

[1] Aziz, Maryam, Emilie Kaufmann, and Marie-Karelle Riviere. "On multi-armed bandit designs for dose-finding trials." JMLR, 2021

[2] Magureanu, Stefan, Richard Combes, and Alexandre Proutiere. "Lipschitz bandits: Regret lower bound and optimal algorithms." COLT, 2014.