Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper analyzes online change point detection. A user can play actions that reveal information about the post-change distribution. Some actions reveal more information that others. The post change distribution belongs to a set of possible distributions and is unknown apriori. The authors provide an algorithm that estimates the post-change distribution out a priori known set, and then plays the most informative action such that sequential testing can terminate quickly. They analyze "delay" - time after the changepoint when change is certified by their algorithm. They provide lower and upper bounds for their algorithm and compare it to some other baselines. 
main_review: Problem 
-------------
I think the studied problem has a clear structure and is very practically relevant as well as to NeurIPS community. Many real-world applications follow this pattern. I enjoyed the problem statement and was not aware of instantiation of the linear bandit model in this context.

Clarity 
-------------
While I was able to follow the paper on a general level and I think authors made across what they wanted.  I had hard times to follow 
- 190-198 - why this is the right likelihood - perhaps at least reference to some review text that gives context to people not familiar with this matter
- 267-275 - its not clear to me what exactly is the statement about the second term and what is the interpretation of this distance
- 287-291 - It's not clear to me what implications this selection of “m” has on the practicality of the problem. It seems to me the first term would dominate only if the distance between the two parameters was very small, much smaller than distances within the \Theta^(1) set. I would like this to be clarified.
- 313 - ??
- In many places I was not sure if \nu = 1

The introduction seemed like a lot of concerts which were not properly defined and I was unable to benefit from it. I could only understand it after reading later sections. 

Novelty
-------------
I am unfortunately not familiar with the related literature that authors mention. I cannot comment on the novelty of this approach, but it seems to me that on some level this problem should be addressed by something from prior literature, at least in the non-adaptive case. The fact no non-trivial baseline algorithms are provided seems a little suspicious (see below) to me but I leave other authors familiar with related works to comment on this. 

Execution and Questions
----------------------------------
- Triggering the algorithm too early is also not desired, yet it's not captured in the delay metric. Would it not be more meaningful to induce this in the metric somehow? 
From Theorem 2 it seems to me that the early detection is controlled via the parameter “m” which defines beta = O(m). Also, it seems to me that there is no clear cut choice of m since the true \nu is not known? How do you address the choice of m in practice?
-  Theorem 2 assumes \nu = 1? Or is this just for the sketch proof?

-  Similarly is lower bound for \nu = 1 or more general?

- In general I am not sure what is the influence of larger \nu in the context of the theory. It seems to me that the larger the \nu the more difficult is it for the likelihood test to finish since the longer time it will take the likelihood estimator to saturate or am I wrong? Could you comment on this, I am not familiar with general changepoint literature which may address this?

 - I actually liked the proof sketch intuition and the reduction for the largest drift identification. I do not know all the details and I am not familiar with queuing theory, but I followed in on a high level this makes sense to me.

- However it seems to me that Theorem 2 as stated does not reveal much about the problem (at least as stated in the main text). I think it makes sense to provide a specialized result (for linear bandits) and context. I found little value in the actual statement of Theorem 2 since the second term was left very vague. 

-Addition of a baseline: What about D-experimental design for the linear case as baseline; or a specific form of G-experimental design where one would take a supremum over all possible responses in \Theta^(1)-\theta_0. This is a better baseline than just uniformly at random, and yet seems to be an obvious choice. If the main point is adaptivity I am sure this baseline will be worse sometimes, but might be more difficult to beat in practice due to the simple nature of the algorithm.

-The approach seems to me to be rather suboptimal at the cost of being theoretically analyzable. Namely the differentiation of Q^(1) and Q^(2) seems to me to be purely theoretical such that one can split the proof technique for t_1 and t_2. First under Q^(1) one finds once the true optimal parameter is identified and then with Q^(2) this concentrates. It seems to me that one could have only one sequence and adapt the GLR test to account for it. It seems that you also use a variant of stopping rule that is not as in the algorithm but you do not describe in detail in the main paper. Can you comment on these aspects?

-Not a humble opinion that should be taken with a grain of salt: While I might be underestimating the true difficulty of the problem since I am not familiar with all the mathematical tools. This strategy seems to be very simple. Even too simple given what we know at least for linear bandits.


Current Verdict
--------------------
While I like the applications and the problem statement is indeed very interesting, there are some definiciences and clarifications that need to be addressed before acceptance. 

limitations_and_societal_impact: This is mainly theoretical work and the sociatal impact were not analyzed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose an adaptive algorithm for quickest change detection under bandit feedback. Their proposed epsilon greedy algorithm learns the most informative action, and is able to achieve minimal delay. The authors provide theoretical guarantees for their scheme, as well as an information theoretic lower bound to show optimality in the small false alarm regime. Experimental validation is provided on synthetic and real datasets.
main_review: 1. The distribution pi is not discussed, yet seems to be of moderate relevance to the additive error terms. It is also not specified how pi is selected for the numerical experiments. Additional clarification on the impacts of pi would be helpful.
2. Some oddities with numerical results; Table 2, URS for size = 20 mean is 236 while standard deviation is 1. Any intuition or explanation for the generally lower std dev of epsilon-GCD  (and URS for diffuse actions) versus Oracle?
3. The condition in 269 seems to be brittle and potentially very large. For example, if one possible parameter was theta’ = theta*+w for small perturbation w, and a*(theta*) + w was another possible action (i.e., this new theta’ had a different most informative action than theta*), then it seems as though the delay would scale with how long it takes for \hat{\theta}\_t to settle to theta* (the quantity t_1), which is unnecessary. Is there a clear way to avoid this issue of an alternate theta’ with arbitrarily small \Delta_{\theta’}, and a different optimal action? I understand the overlap with the future work of extending to continuous parameter spaces. 
4. Discussion and future work should be in the main text, not in the appendix; with the extra page allotment, it wold be good if this could be brought to the main text.
5. Minor errata: It is stated that a* may not be unique in 136, however in 326 it is assumed to be. The exploration indicator E_l is not defined prior to its use in 193. In assumption 4, the log is missing in front of the log likelihood ratio in 245. Appendix: Line 764, URS corresponds to epsilon=1. Lines 313 and 350 have missing cross references. 

The authors clearly mention the limitations of this approach in their discussion section, most critically to more adaptive procedures, when \theta_0 is unknown, and extending their results to continuous parameter spaces. The motivation for the paper is natural, the approach is well thought out, and the lower bound is fundamental.
limitations_and_societal_impact: There are no negative societal impacts in this theoretical paper that focuses on changepoint detection under bandit feedback.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper studies the problem of trying to detect a change in a multivariate time series when only a subset of the time series can be queried at a time. The authors consider the case where the initial parameter is known and we wish to minimize the time until we detect a potential change in it, whilst also making sure that there is a low probability of detecting a change when there is not one. The authors present an epsilon-greedy algorithm, which when exploring samples an action randomly and when exploiting selects the action that maximizes the KL divergence between the initial distribution and the distribution with the current maximum likelihood. This is a natural algorithm and the authors are able to prove theoretical guarantees on its performance when used with a likelihood ratio stopping criteria. By means of a lower bound, the authors also show that the proposed algorithm can be near optimal in some specific cases. Finally, they show that their algorithm outperforms a very naive baseline experimentally.
main_review: It was quite difficult to understand the problem which is being studied in this paper. In the introduction/abstract several terms were used without being defined which made it quite hard to follow. Some terms in the problem definition were also not rigorously defined (e.g. X_t was just defined as an observation, no details were given on which values this can take, what dimension it has etc.). It would also have been very helpful to see a concrete example of how one of the motivating problems can be written using this notation making specific the actions and observations. Is the general idea that the actions are just choosing a subset of the streams to observe (in which case the problem could be viewed as non-stationary combinatorial bandits with piecewise constant functions) or can the actions be a mixture of different streams? The fact that the learner knows the pre-change parameter seems like a very strong assumption but is not discussed/justified. Additionally, the aim is just to detect one change which seems quite restrictive. What happens when there is some error in our knowledge of the pre-change parameter?

I am a bit concerned about the limited comparison to the prior work. The problem studied in this paper seems very similar to that studied in [ZM20]. This is discussed a bit in the related work section, but the bounds obtained in this paper are not compared to those in [ZM20]. Additionally, there is no experimental comparison to this work. It seems that the results presented here are concerned with being able to stop early in the event of no change, as well as minimizing the delay in detecting a change, whereas prior work just concentrates on the detection delay. It should therefore be possible to compare the two approaches both theoretically and experimentally. It would also be helpful to include the experimental results for the actual algorithm that was theoretically analysed, not just the modification that the authors found worked better in practice.

The lower bound in Theorem 1 is nice, and it is pleasing that it shows a sort of trade-off between a false alarm rate and detection delay.

The algorithm that is presented seems to be a natural application of epsilon greedy. From reading the pseudo-code in Algorithm 1 it is possible to get a good understanding of what the algorithm is doing. I did not find the text in section 4 particularly helpful for understanding the algorithm. I also did not follow intuitively why the proposed algorithm would adapt to the no change setting. I am curious about the stopping threshold beta. In Theorem 2, it is stated that this should be tuned to be a linear function of the size of the parameter space. When the parameter space is large, this means that the stopping criteria will only be satisfied when there is a huge difference in the likelihoods, and so it seems like the algorithm will be very slow to stop (I also think that this means that the adaptation to infinite parameter space may be more involved than the authors claim). When we are in the so-called ‘low false alarm’ setting, it seems that the delay detection time is dominated by the first term in Theorem 2, but I don’t have any intuition for what the result will be in the other case. In particular the discussion in lines 276 to 286 was very difficult to follow and a lot of stuff seems to be hidden in the appendix. In the ‘low-false alarm’ setting, the upper bound in theorem 2 scales logarithmically with the size of the parameter space. This does not appear in the lower bound so I disagree with the claim that the only difference is the 1/(1-epsilon) penalty for epsilon-greedy. In many natural settings with large parameter spaces, this log(beta) term can represent a significant difference between upper and lower bounds. The example in line 292 considers a somewhat trivial example where the parameter space is just a basis. Does the improvement still hold for a more realistic parameter space (e.g. |theta| = a^d for some a)? I also found the proof outline of Theorem 2 very difficult to understand.


Minor comments:
- The authors propose to use the ‘detection delay’ as the performance metric instead of the classical regret. This is fine, but it could be motivated better. From the introduction it is also unclear what this detection delay is actually measuring, more intuition should be given.
- What is ‘the most informative action’ as described? Is there some connection to a partial monitoring problem? 
- the formatting of Algorithm 1 is strange, there should be a line space below.
-  Is Q^(2) ever defined in Algorithm 1?
- Is N_tau(a) defined on line 178?
- I don’t see the relevance of the queuing in section 4
limitations_and_societal_impact: The limitations of this work could be made clearer. The societal impact is not discussed, but this is probably OK for this paper.
review_title: null

Meta-review: The paper studies the problem of change point detection in a multi-sensor setting, where the learner can read observations from a set of available sensors to monitor whether any change in observation distribution happened or not. While this problem is clearly connected with change point detection in the offline setting and to bandit in non-stationary environments, it has an interest on its own and it poses very specific challenges that need to be carefully analyzed, starting from an accurate definition of the performance measure. The proposed algorithm builds on solid intuitions and some known techniques (such as CUMSUM) and it is shown to achieve near-optimal performance in the limit where false rate tends to zero. I think these contributions are valuable and they represent a very interesting step into understanding this problem. For this reason, I'm proposing acceptance.

Nonetheless, the paper generated a considerable amount of discussion and the authors provided very much needed clarification on some points including the interpretation of the theoretical results and the gap between upper and lower bound. In particular, the latter point shows an existing gap depending on the dimensionality d between the upper and lower bound. While it is perfectly fine to have such a gap, the authors should clearly state in the revised this aspect so that other people can understand where the limitations of the current work lie. Overall, the paper would greatly benefit from integrating the additional insights provided during the rebuttal into the final version of the paper.


Decision: Accept (Poster)