Bandit Quickest Changepoint Detection
Authors: Aditya Gopalan
Braghadeesh Lakshminarayanan
Venkatesh Saligrama
Venue: NeurIPS 2021 Poster (2021)
Keywords: Bandit
Changepoint detection
CUSUM
Quickest change detection
Detection delay
Adaptive sensing

Abstract: Many industrial and security applications employ a suite of sensors for detecting abrupt changes in temporal behavior patterns. These abrupt changes typically manifest locally, rendering only a small subset of sensors informative. Continuous monitoring of every sensor can be expensive due to resource constraints, and serves as a motivation for the bandit quickest changepoint detection problem, where sensing actions (or sensors) are sequentially chosen, and only measurements corresponding to chosen actions are observed. We derive an information-theoretic lower bound on the detection delay for a general class of finitely parameterized probability distributions. We then propose a computationally efficient online sensing scheme, which seamlessly balances the need for exploration of different sensing options with exploitation of querying informative actions. We derive expected delay bounds for the proposed scheme and show that these bounds match our information-theoretic lower bounds at low false alarm rates, establishing optimality of the proposed method. We then perform a number of experiments on synthetic and real datasets demonstrating the effectiveness of our proposed method.

Bandit Quickest Changepoint Detection
Aditya Gopalan
Braghadeesh Lakshminarayanan Electrical Communication Engineering
Electrical Communication Engineering
Indian Institute of Science, Bengaluru 560012 adi adityaiiin ic.
Indian Institute of Science, Bengaluru 560012
braghaddeshh94@gmail.. com
Venkatesh Saligrama
Electrical and Computer Engineering Boston University, Boston, MA 02215 srvbbu.. edu
Abstract
Many industrial and security applications employ a suite of sensors for detecting abrupt changes in temporal behavior patterns. These abrupt changes typically manifest locally, rendering only a small subset of sensors informative. Continuous monitoring of every sensor can be expensive due to resource constraints, and serves as a motivation for the bandit quickest changepoint detection problem, where sensing actions (or sensors) are sequentially chosen, and only measurements corresponding to chosen actions are observed. We derive an information-theoree lower bound on the detection delay for a general class of finitely parameterized probability distributions. We then propose a computationally efficient online sensing scheme, which scamlessly balances the need for exploration of different sensing options with exploitation of querying informative actions. We derive expected delay bounds for the proposed scheme and show that these bounds match our inftrmmtiion-theoree optimality of the proposed method. We then perform number of experiments on synthetic and real datasets demonstrating the effectiveness of our proposed method.
lower bounds at low false alarm rates, establishing
Introduction
We propose a framework for bandi quickest change detection (BQCD). Specifically, we are given a multi-dimensional online data stream, which can be sequentially probed by means of actions belonging to an action set (for instance, only few among all of the data stream components can be observed at any time, or linear combination can be acquired). The online data stream can exhibit abrupt statistical changes, at any time, and only among a few arbitrary components. Our task is to sequentially probe the data stream by adaptively choosing valid actions based on past bandi observations associated with past actions. Our objective is to detect change, if has happened, with minimum detection delay.
Example Scenarios.
Surveillance systems [HCI]] are equipped with suite of sensors that can be switched and steered focus attention on any target or location over a physical landscape (see Fig. T to detect abrupt changes at any location. On the other hand, sensor suites are resource limited, and only a limited subset, among all the locations, can be probed at any time. As such,
By 'bandit' generally
adaptive sampling with partial information.
"This is different from classical quickest change detection (TNB14). where all of the multiple streams are observed at each time, and the only adaptive decision is to declare whether or not a change has happened.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

we face fundamental dilemma: Focusing attention at any one location can compromise change detection at other locations. Although we describe scenario in surveillance, the problem of BQCD is general and arises in intrusion detection [Bas99], J. social networks [Vis+14], disease outbreaks and epidemics [QSC14 YSK15), manufacturing processes [Pur+19a| Din+06], energy limited sensor networks OGR TO ESTOJ, and vital health monitoring [Vil+17].
In this paper, we derive a fundamental characterization for the delay performance of BQCD, and make explicit, the fundamental tradeoff between delay and false-alarm in the low-false alarm regime. We specifically make the following contributions.
Information-theoretii Lower Bound. We prove a lower bound on the expected detection delay that any BQCD algorithm must suffer at fixed false alarm rate. The lower bound exhibits a fundamental tradeoff between early stopping (false-alarm) and detection delay (time to detect abrupt change). It offers the key insight that the quickest way to detect change, any false-alarm rate, is by playing the 'most informative action', of an 'oracle' who a priori knows the post-change distribution. This suggests that to quickly identify changepoints, we must direct our effort towards rapidly identifying informative actions. On technical level, we develop a change-of-measure argument for nonstationary, adaptive change detection, that allows for relating the divergences between random trajectories until stopping to the divergence of probability laws under each action for any two problem instances.
e-Greedy Change Detector (c-GCD). We pro- pose e-GCD, which, at a high level, uses a small amount of forced exploration to identify infor- mative actions. The forced exploration allows for rapid convergence towards informative ac- tions, and playing these actions minimizes de- tection delay. Our e-GCD is based on the gen- eralized max- waxx-ikelihoo//ikeliiie ciple which is utilized to estimate parametric changes. To prove detection delay bounds we draw upon key insights of e-GCD. We first inter- pret the scheme in terms of competing parallel "queues", where each queue corresponds to a can- didate post-change parameter, collects 'arrivals' which are log-likelihood ratios of observations, and cannot go negative. The true parameter is the queue which enjoys the highest growth rate after change, and the detection delay is the time required for to dominate and become the 'longest queue'. The dynamics of the queues can be related to nonstationary random walks with drifts. Using these insights, we prove that the expected detection delay of c-GDD at low false alarm rates mirrors information theo- retic lower bounds thus establishing optimality of our method.
Time Series at Node 1
Abrupt change
M
t
ratio prin-
N
N-1
steerable sensor
5
Time Series Node k æ1
chanhe
Experiments. We perform numerical experi- ments of e-GDD on synthetic and real datasets and show that under variations of changepoints, anomalies, and action sets, we realize gains due to adaptive sensing.
Figure 1: Example BQCD Scenario. There are N spatial-locations that are monitored. The steerable sen- sor capable of rapidly switching modes-grev and red beams as shown-and collect aggregated signal from mul- tiple locations at low signal-to-noise ratio (SNR) or fo- cus attention narrowly on single location at high SNR. Locations can exhibit abrupt change, which manifests as the depicted time-series (see top). Due to resource constraints, at any time, only a limited set of locations can be observed with high SNR. BQCD aims to learn a policy adaptively steer and switch modes to different locations and detect abrupt changes if any, quickly.
2 Related Work
Classical quickest change detection, dating back to the pioneering works of Page [Pag54) and Lorden [or71], studies the problem of decid- ing when to stop (akin to declaring a change) while sequentially observing data stream. In this context, the CUSUM algorithm [Pgg44), in
2

---

which a change is announced as soon as likelihood ratio statistic exceeds a threshold, has been shown to enjoy optimal performance.
Our work is motivated by constraints on data collection in multi-stream time-series data, necessitating the design of adaptive sampling rule in addition to the stopping rule. Similar to our work, Zhang and Mei (ZM20) also propose a sequential sampling method for quickest change detection based Saeraee---ober--Poeee
scheme (see, e.g., [BN93]. However, their theoretical analysis is rather limited in its scope. In particular, they argue "in principle" that their method will control false alarms for sufficiently large thresholds, and will eventually (i.e., after infinite time) choose sensors where changes manifest, without any explicit characterization of detection delays. In contrast, we derive fundamental detection delay under a false alarm rate constraint, thus fully characterizing the BQCD problem. Additionally, their framework is not general enough to handle correlated or structured anomalies, which is a significant aspect of both our theoretical and experimental investigations.
on the well-known
In other related work, Gundersen al [Gun+21] propose to extend the framework of Bayesian Online Change Detection (BOCD) [AM07] to incorporate costs in making decisions for real-time data acquisition in multi-fidelity sensing scenarios. Different from this perspective, our approach is frequentist, and does not impose action-specific costs and distributional constraints on the underlying latent parameters or on the changepoints. Furthermore, we derive finite-time performance bounds, which is not focus of this work.
3 Problem Setup
General Setup. We consider the following discrete-time model for the bandit quickest changepoint detection problem. At each decision round E N := {1, the parameter O, governs the distribution of the observation taken in that round. Let E N denote the round which the change in behavior occurs, so that 0₂- = 0, for & and 0g 0 E ( for 1 v. At each round a learner decides to either (1) stop and output that a change has taken place, denoted by the random variable U,- = 1, (2) continue (denoted by U, 0) and play an action sensing decision A, from action set A. Upon playing this action the learner obtains an observation X,, sampled independent of the past, from a probability distribution Ps,, [-I.c]. which depends on both the current system parameter O, and the current action Ar. The stopping decision and sensing action (U, and A,) are assumed to be chosen in causal manner, i.e., depending on all past information Un. A1, X1, U1.... .i...... At-1- Ae-1-- Xt-1- along with potentially independent internal randomness. The learner is aware, priori, of the pre- change parameter Og. the post-change parameter set (1)) and the observation distribution structure, i.c., {IFo [- |a],,, with a E A denotes fixed actions. Crucially, the change time v and the specific post-change parameter 0" are not known in advance and must be 'learnt' in order to perform well.
The stopping time of the learner is defined to be T = min(! 2 0 U. = 1}, and the main performance metric that we are interested in is the detection delay, which is the random variable (T -) = max(r - 1/ 0}. Specifically, we are interested in designing sampling and stopping rules so that (a) when no change occurs (vr oo), should be at least a specified time delay with high probability, which is a measure of false alarm rate, and (b) when a change occurs (v < oo), the expected detection delay should be small implying quick detection of change.
Illustrative Example. For illustration, we elaborate on the scenario depicted in Fig. T We consider N 'locations' as shown, and the observation at location j at time t follows:
(t) = e [22])ees + Wt((), te Z+, j [N],
where (W)(t)),s g,e is a collection of standard normal random variables and 1 denotes the indicator function. This is a temporal extension of the model in [QSC14]. The model with the parameter 0 + 0 + locations S C [N). The learner is agnostic 0.
signifies an elevated mean after time & the time v as well as which set S among a family of known subsets S C (0, 1, exhibits elevated activity. The learner at time can probe locations by means of sensing actions A, E A C (0, 1
and observe scalar measurement, X, P. ( A.) N (,, |A.NS
with 0, for t <
and for &. 2 v, 0, = 0 E ( = R \ (0). The normalization factor v VIA expresses the fact that the same SNR is maintained across different probes A, (see [QSC14)).
3

---

General (Structured) Scenarios. Depending on the application, locations maybe endowed with a neighborhood network structure, and change maybe observable in a K neiiihhboooooo of the target location, and in such cases, S are constrained to be K-neighborly sets. Similarly, to allow for diverse probing modes, we could allow the action set to include actions that aggregate signal across multiple locations.
Notation. For post-change parameter 0 E O(1, we use a a0) denote the most informative action for 0 w.r.t. o("), i.e., a" (0) E argmax D (IPu [|]]] [Pa, [-la)), where D (-I1-) stands for the Kullback- Leibler divergence. To lighten notation, in the sequel we often abbreviate the distribution Fo [||] to 8(a), and thus D (IF [- [a] [[Fe, [-aa]) to D (()))) The simultaneous subscript- superscript notation 2! is often used to represent the sequence (Z,, Ei-.....,; 22). For any E @ and n e N. we use Ip(n.() to denote the probability measure on the process Uo. A1, X1, U1: A2, X2.... induced by the learner's decisions, when the pre-change parameter O, changes to I at time We also denote by Po()) the probability measure as above under the no-change situation (v oc).
We define the filtration (Fe)r20 to be the o-algebra generated by all the past random variables up to time I, i.e., F, ({(A,, X,), 0 < S ()) An (admissible) change detector is an algorithm for which the stopping decision U, {0, 1} and action A, E A are Ft-1 measurable at all rounds t.
Objective Specification. Our BQCD framework involves a false alarm rate constraint specified by a tuple (m, a),, where m E Z denotes
priori fixed time such that the probability of an admissible change detector stopping before time m under the null hypothesis (no change) is at most a E (0, 1), namely, p(a)) [T < m] I a. This kind of false alarm duration specification for the stopping time (2 with probability 2 1- a) has been commonly employed in the literature classical (non- adaptive) change detection (see e.g.. [Lai98), to ensure that the comparative performance rules out early triggering algorithms. Let Dm,, be the class of admissible change detectors with the (m, a) property stated above. As such, our goal is to find detectors in Dm, that minimize the detection delay when change indeed occurs.
Informal Statement of Our Results. Our main result is a sharp "optimal characterization" for expected detection delay in the limit of vanishing false alarms (a + 0, m + oo). The result, stated (c-GCD) algorithm in which, in each round t,
below, involves the new GGreedy-change-deteeee choose action uniformly random from the set A with probability or choose an action that is 'most informative' for an estimated post-change parameter with probability 1 c. Objective Specification. Our BQCD framework involves false alarm rate constraint specified by a tuple (m,ax) where m E Z denotes an a priori fixed time such that the probability of an admissible change detector stopping before time m under the null hypothesis (no change) is at most a E (0, 1), namely, PP(O)) i m] a. This kind of
Theorem 1 (informal). Consider the limiting situation as -> O and m = w (log 2) + oc. Then, any admissible change detector in Dmn must suffer
10(v00) [(( - -v}+]
lim inf a-
log
max (()))))))))))))
On the other hand, the e- G-GDD algorithm, suitably tuned to be in D Dm,.o achieves
R(v,8") [[T -)++]
8
1
lim sup
a-+u
log 1
(1 max. ((0~(a))000))))))
4 Fundamental lower bounds on bandit change detection performance
Before embarking upon the design of bandit changepoint algorithms, it is worth understanding what the limits of bandit change detection performance are, due the stochastic and partial nature of the problem's information structure. We expose in this section a universal lower bound on the detection delay of any bandit changepoint algorithm with a false alarm rate above given level.
Theorem 2. Let < a v 1 and m 2 For any bandit changepoint algorithm satisfying
1O
p(ox) [F < m] $ a, we have E(L [T] 2 min
26 log 1 max. E.A D( (a)])
m
V8* E (
The result implies that in the 'small' false alarm rate (a) regime with 'large" = w(lo (1/g)))))).. e.g.. (L/a), we have that any algorithm meeting the false alarm rate property |p(x0) [r 2 m] 2

---

log a 1 a must suffer a detection delay least maxa5. (100(a)])000 when a change occurs at
time 1 (a similar, 'anytime" lower bound holds for detection delay at v E N, see appendix).
False alarm-detection Delay Tradeoff. Theorem 2 shows that basic tradeoff exists between the false alarm rate or early stopping rate in case of no change, on one hand, and the detection delay after true change occurs, on the other. Specifically, is impossible stop 'too early', i.e., before time
log 2
Ω
after a true change if one wishes to stop 'too late' under no change, maX (1))
i.e., P(00) [ 2 21 We also note that when there is no adaptive sampling of actions (i.e., |A| = 1), then the lower bound reduces to the form of a standard lower bound for the classical changepoint detection problem [Lai98].
Information Structure. This is perhaps the most valuable implication of the lower bound. The quantity D (0" (a)llo()((a)) in the denominator, can be interpreted as the amount of informa- tion that playing an action provides (on average) in order to detect a change from d to H". Consequently, the quickest way detect change is by playing the 'most informative action', argmax A D (8* knows the post-change parameter 6 in advance. Unfortunately, this information is not known a priori for a causal algorithm. However, we will see that this can fact be learnt along the trajectory and the lower bound can be attained order-wise by a suitable learning algorithm that we propose.
(a)). This can be viewed as the sampling strategy of an 'oracle' who
Proof Sketch for Theorem The main idea is measure change argument, adapted our non- stationary change point setting, from literature on sample complexity bounds for bandit best arm identification [GK16]. On one hand, if the algorithm in consideration very 'lazy' to begin with, i.e. p(1,0)) [T m] is least a constant, say 1/2, then immediately get ((1,0)) [T] 2 1 m. On the other hand, if the algorithm is 'active", i.e., p(1.0") [T < m] 2 1/2, then the KL divergence between the laws of the indicator random variable {T m] in the instances (1, 01, and (oo,-) is 'large' (at least a constant times (1))) owing to the hypothesis that (p(c)) [T < m] is 'small' (at most a). But by the data processing inequality, this divergence bounded above by the divergence between the distributions of the entire trajectory Uo, X1, U1, Ag, X2.... under the two instances, which can be seen to be equivalent to the quantity EneA D (6" (a)l(((a) E(1,0") (a)), and which is further bounded above by EE(,0") [r] maXas D (0* (a)). See appendix for complete proof.
5 GCGD Algorithm
We describe the c-GCD adaptive sensing algorithm for the bandit quickest change detection problem. The lower bound in Section Suggests that it is beneficial infer the target post-change parameter, so that playing the most informative action for it can yield the best possible detection delay performance. This is the key principle underlying the design of the e-GCD algorithm (Algorithm D.
At a high level, e-GCD uses a small amount of forced exploration along with 'greedy' exploitation to play sensing actions. Specifically, it computes, at each round t, maximum likelihood estimate (MLE) of the post-change parameter based on the generalized likelihood ratio test (GLRT) principle. It then plays either randomly chosen action, if the current slot is exploration slot, 'greedy', ie., most informative, action for the estimated post-change parameter, it is an exploitation slot.
The MLE of the post-change parameter, in round t, admits an interpretation as the longest 'queue' corresponding to some parameter in (1)). To see this, no- tice that the MLE for the pair (v, given all previous data in exploration rounds can be written as argmax IseS I1==1 fe, (XelAr) II= (o()))A)) (Ae)
argmaxgeew..sss EE-LE Ee log Jag (x)) with fe(-la) taken to be the probability density or mass function of the distribution (P(()))) (assuming one exists). Observe now that for each candidate post-change parameter O, the inner maximum over v. (()(0) := argmax El=1 11 Eg log (o(XelAs)
Jo (X) evolves as 'queue with arriving work
(A()) at time slot f; in other words, Q (0) Eg log Jop (XelAz)
@ (0) + E,, log Teg (X()at)
fo(X.AA))
This is also known the Lindley recursion equation in queueing theory.
5

---

We define the algorithm using general 'processing' functions ge in place of the log oog-likelhood ratios fo above. Broadly speaking, the functions should ideally be chosen with the hope that (a) log Jog Ae) is negative in expectation before the change time (L < v), and (b) ge (Xe, Ae) is large and positive in expectation for 0 0*, the true change parameter, after the change (2 2 1/)
The stopping rule that c-GCD uses based on the generalized likelihood ratio (GLR)-type statistic. is the largest of an ensemble of evolving exploitation-data queues Q²2 (0), which mirrors the definition of (0) but with 1 E, instead of E,.
5.1 Theoretical guarantees for the c-GCD algorithm
In this section, present and discuss theoretical guarantees the false alarm rate and detection delay performance of the e-GCD algorithm of Section
Algorithm c-GCD
We make the following assumptions on the pa- rameter space and observation distributions in order to derive performance bounds for the al- gorithm.
1: Input: E [0, 0o. 0()) 8 2 1, Obser-
vation function go( u) v(0,x,,) a) E O x
X' x A.
2: Init: Q ()) + - Q (0) + 0 vo Q(1)
Assumption 1. The post-change parameter set (1) is finite, i.e., (0()
{ (CUSUM statistics for exploration and ex-
ploitation per 0}
This assumption is made primarily for ease of analysis, whereas the algorithm is defined even for arbitrary parameter spaces. Specifically, it allows for easy control of the fluctuations of an ensemble of (drifting) random walks via union
3: for round 1,2, 3...3..... do
4: if max Q, (0) 2 log / then
5:
break
Stopp sampling and exit)
6: end if
7: Sample E, ~ Ber(e) independently
bound over the parameter set. While we believe
8:
if E, 1 then
that this can be relaxed to handle general param- eter spaces via appropriate netting or chaining arguments, this chiefly technical task is left to future investigation.
9: Play action A, independently (Ex- plore)
10:
Get observation X, O
Set VO
(0+1())
Q
Assumption Every post-change parameter is detectable by some action, i.e., vo E ( 3a E A : D (((a))((()(())
(of go(,,, A.)
(Update
(a)) ) > O. Moreover, any two post-change parameters are separable by some action, iee. 40,0' E ((() 3a E A 13: D (((()))(((())) > 0.
exploration CUSUM statistics
12:
else
Compute 6, = argmax Q." (0)
[Most likely post-change distribution based on exploration data) action
This is basic identifiability requirement of the setting, without which some parameter changes could be completely undetectable. Put differ- ently, one can only hope to detect changes that the sensing set can tease apart.
14:
Play
A
argmax dEA D (B (a)l((())) Get observation X, Set
15:
16:
A0
E (
1 (0) +
Assumption 3 (Bounded marginal KL diver- gences). There is a constant Daax satisfying D (a)(())))aa) S Dmax for each E A. 01, 02, O(1).
(o + (X.,
(Update
exploitation CUSUM statistics]
17: end if
18:
end for
This assumption is easily met, for instance, all log likelihood ratios are bounded, or the ob- servations modelled as Gaussians. In this case log likelihood ratios linear functions of the observation.
Assumption 4. Every observation probability distribution Pp [-]a], for a E A and 0 E (1) U (0o). has either density or mass function, denoted by fol-la). Moreover, there exists > 0 such that for any 8, 8', 8" E (()) U {0o}. and a E A, the log likelihood ratio (x(X)a), is r-subgaussian under X ~ Pa [-la].
(X]o)
'with respect standard reference measure, e.g, Lebesgue measure A random variable X is r-subgaussian under X PifVX R: EI--XX)) ST22

---

This assumption is common in the statistical inference literature; we use it to be able to control the fluctuations of the exploration and exploitation CUSUM statistics in the algorithm via standard subgaussian concentration tools. A concrete example of a setting that meets Assumptions | 4 is the
linear observation model described in Section 3 and Fig. T We are now in position to state our key theoretical result.
Theorem (False alarm and detection delay for general change point), Under assumptions following conclusions hold for e-GD (Algorithm | run with the log- log-likelihood observation junction fa(ala)
4 the
go(2, a) = log Jap (2]
1. (Time to false alarm) Let a E (0, 1) and E N. If the stopping threshold is set as 3 m m then the stopping time satisfies ppx0) [T < m] S a.
2. (Detection delay) For a change from 0g to 0" E @(1) occurring at time v E N.
B((00)) > [[T [1]+ - (1 - e) maxa D (a)(
8 8log 3
0 pplly (2) 1o(o [Qw)] .P)
(1)
provided r(ag)) > O, with Q!" == (Q)((8) Beeu: denoting the explore queue statistics for all parameters and P = (Pe (e))))))))) all the observation distributions.
Remark. We note that ,3 is an internal, algorithmic parameter, whose setting is spelt out in order that the (m, a)) false alarm constraint can be met. Thus, the first part of Theorem 3 is a 'correctness' statemen
Interpretation of the Detection Delay Bound. The first term in the detection delay bound (T) can be interpreted the time for oracle fixed-action strategy (c.g., CUSUM), that always plays the most informative action for 0*, to stop. The second term, on the other hand, is a bound on the time taken by the algorithm to learn to play the most informative action for 0* (details follow in proof sketch). We omit the precise dependence of the second term on the problem structure here for brevity, but detail it explicitly in the appendix. Specifically, for small forced exploration rates c, the second term depends on the information geometry of the problem approximately as 3a A3
1 Here, for each
candidate post-change parameter O E ( its 'gap" Aş is a measure of how difficult it is for the algorithm to eliminate 0 as an estimate for the true post-change parameter 6* during this parameter- learning phase. We formally define it as A == Do- 2 (D 9o + (Do-.o, Do- ) where Dø- == EPEA T(a) D (0* (a)) (a)) is the average information divergence between parameters 0r, 9 offered by playing from the exploration distribution æ. With finer analysis, the dependence on gaps and could be improved. We omit it for simplicity.
We now turn to the (additive & linear; see the appendix) dependence on E(oo) [Q00 of the second term. The insight to why this arises is as follows. The 'learning' phase for 0*, after change takes place at time v, can be seen as a 'race" between competing log- log-likelihood queues of all the parameters vying to become the MLE 0,. At the change time, each non- oonouru truth queue Q (2) (I) is, on average, QQth 1) (0)
at level [(0o)
representing its initial 'advantage' over the ground-trutt queue Q! (8*)
which in the worst case could be at level O. Thus, the difference (=x) Q (0) ((0))(([000) (0*) S (0)
the extra amount of 'time work' that the 0* queue must do to overcome the queue. special case of the result is for v = 1 in which case all queues start out at O. For general v. one can establish that E(())
Q (0) must be finite, by noticing that each queue is non-negative and accumulates arrivals
with negative mean before the change, and applying standard queueing stability arguments. This also indicates that the detection delay bound is roughly invariant given the location of the change point v.
Optimality at low false-alarms. The result implies that in the 'small' time false alarm regime, ie., a + 0, m = (loo((//a)) and log(m) = o(log(a)), the detection delay when is set as
'This is, at a high level, akin to specifying a PAC algorithm's correctness requirement and measuring its sample complexity on the other hand, i.c., insist that its returned answer be e-correct with probability at least 1 8, and then analyze how long it takes to learn and return an answer. The former corresponds to the false alarm constraint and the latter to measuring detection delay here
7

---

above is dominated by the first term: E(u00)) [-]= (1 max, (a)
log 9
This matches,
prder-wise, the universal lower bound of Theorem uup to the algorithm algorithm-dependen dependent multiplicative factor 1/(1- - c), which may be interpreted as a 'penalty' for the forced exploration mechanism.
Benefits of Adaptivity. Let us consider a concrete setting to elucidate the detection delay bound. In this example, there are d sensing actions, represented by the canonical basis vectors in g The pre-change parameter is 0 E IRd, and there are d candidate post-change parameters, each of which canonical basis vector eq, i [d]. multiplied by constant ò. The observation from applying action a at system parameter 0 is Gaussian distributed with mean (a, 0) and variance 1. Thus, the aim is to detect (sparse) change of magnitude ó in one of the d coordinates in 9g = 0, when at any time only single coordinate can be noisily sensed. Suppose 6 = òe1 without loss of generality, for which the most informative action (in fact, the only informative one) is ag. = c1. The first term
in the detection delay given by Theorem 3 is then O [[on(1/)) This a factor of d smaller than
(11<))8²)
2 (d. lug(1/a)) would achieve this is seen by applying the lower bound (Theorem 2 to the case of single (trivial action) where the divergence in the denominator reduces to the average divergence across all coordinates: 0(82/d), For estimating the second term, we calculate that for each 8 = de, with
[I-e)ø=) that a standard CUSUM rule with non-adaptive uniform sampling over coordinates
i A 1, Ag Dø- (Do + (Do. Do-
g2
&e Thus, 4a
2
2d
2
the second term representing the time to learn the optimal sensing action scales as O
(d-1)d
c
o c05
Although we have not optimized dependence on d, e and ö, the overall bound still gives
an idea of how the active sensing problem gets harder as the dimension d grows or as the minimum change amount d changes, making it akin to finding 'needle in haystack'.
Sketch of the Proof of Theorem 3 This section lays down the key arguments involved in the proof of Theorem 3 for bounding the false alarm time and detection delay of the e-GCD algorithm.
1. Bounding the probability of early stopping under no change. The stopping time for e-GCD, by line 4 in Algorithm []] is equivalent to the first instant t when the worst- case (over (1)) CUSUM statistic computed over exploitation data, i.e., max ((2)(())) =
[o(Xe)A)) (1)))) exceeds the level B3 2 1. Under no change, each (X.1a))
max maxiça5i IT=
observation X₃ is distributed as Fe, [A]d given Ac. and the product I= ( [o(XelAe)) (I-Fe)
Jog (x,
over
t= s, s + 1, s 2,..... behaves as a (standard) likelihood ratio martingale with unit expectation under the appropriate filtration. Hence, the chance that the largest among this ensemble of martingales, one for each 0 E (1) and starting time E [m], rises above 3 before time m is bounded using union
bound and Doob's inequality for each individual martingale, yielding the probability bound m (
2. Control of the detection delay. Suppose that the change takes place at time v = 1 to the post- change parameter 6* E (1). The proof strategy is to show, with high probability, that r is no more than 1 + f2, where
4 is an upper bound for the time taken for the plug-in estimate ò. of the post-change parameter, to 'settle' to 0", In other words, we show that after time 4 is very unlikely that an action other than ag. = argmax D (a)) (a))))))))))))))))(( is played in every exploitation round.
1/ is an upper bound for the time taken for the worst-case CUSUM statistic maxgee o.2) to grow to the level B assuming that the optimal (i.e,, most informative) action ag. is always played at all exploitation rounds.
For clarity of exposition, we will assume that we are in the setting of linear measurements in Rd with additive standard Gaussian noise - this makes KL divergences easy to interpret as Euclidean distances and that the changepoint is at 1.
Step 1: Finding l (time to learn 0*). We observe that the MLE 0 at time /. can be written as the parameter associated with the largest stochastic process max 1- ==1 log J Ju,t-1 one for each 0:
(A(()A)) Ee
0. argmaX max log (,), where 10) Mm= (Xeee)))
8

---

Under the post-change distribution p(,,0"), log Ju,t (0) can be seen to evolve (as a function of as random walk with drift <(110 011; ||0 Here, II-1I is the usual matrix-weightedd Euclidean norm in R., governed by how much different directions are explored in expectation by the exploration distribution क: EnEA x x(a)aa". Note that ||0 - 0ll here is the KL divergence between the distributions of the observation that results when an action sampled from π is played, under parameters 8 and 0.
The preceding discussion implies that the drift is the largest (and positive) for the random walk corresponding to the true post-change parameter 8 0" The remainder of this part of the proof uses martingale concentration tools (subgaussian Chernoff and maximal Hoeffding bounds) to find the time ( which the fastest-growing random walk, log (0,) dominates all other 'competing' random walks log (0). 0 + 0"
Step 2: Finding 12 (time to stop under optimal action plays). In manner similar to that of Step I, we observe that the logarithm of the log-likelihood ratio for 0* w.r.t 8n computed over
[o((xlAA) 1-Er
evolves as random walk with drift rate || A Chernoff bound can then be used to control the probability of the 'bad' event that (1 c) <)
only exploitation rounds, i.e., log I
Jeg (XelAt)
this growing random walk has not crossed the level log / in a certain time duration ty (tz does not appear explicitly in the main derivation).
Experiments
Our goal in this section is to illustrate var- ious aspects of our theory through exper- iments on synthetic environments, and to explore the performance of the proposed e-GCD algorithm on setting based on a real-world dataset. All experiments were performed on a laptop with Intel Core i5 CPU and 8GB of RAM, and take under an hour to execute. The closely related prior works on this topic (ZM20) Gun+21] are more specific and are not compatible with many of our structured scenarios (see Sec. 2 and Appendix Dj. As alternatives, we propose several natural baselines and compare against method to benchmark performance.
Size
Oracle
c-GCD+
e-GCD
URS
10
30 + 5
98 + 62
112 + 74
306 + 76
15
31 +
129 + 95
158 + 119
460 = 115
20
31 +
163 + 128
196 156
616 + 153
25
31
5
191 + 154 253 + 216
764 + 194
Table 1: Observed mean and standard deviation for the simu- lated stopped time for varying graph-sizes with pointy action set A1, for change occurring at v = 40.
Uniform Random Sampling (URS). At every round we sample each action in A uniformly at random. Our goal with URS is to calibrate adaptation gains.
c-GCD (Ours). This is our proposed scheme. A point to be noted here (as seen from Algorithm | is that the data used for making a stopping decision (" ("exploitation)) and that for estimating the changed distribution ("exploration") are non-overlapping. and as such leads to inefficient data usage. c-GCD+. To reduce the aforementioned data inefficiency, we consider the variant, the parameter estimation part also utilizes both data collected during exploration rounds and the data collected for the exploitation rounds.
Oracle. Here we consider an omniscient strategy in that the algorithm is aware of both the pre-change and post-change distributions ahead of time, and consequently does not require exploration to estimate the post-change parameter. On the other hand the method has no knowledge of stopping time, and thus the problem reduces to the conventional quickest change detection. The Oracle characterizes the gold-standard in that no adaptation is required, and it gives the absolute smallest detection delay for any BQCD problem.
Synthetic Experiments. We conduct synthetic experiments for the model introduced in Section 3 under the bold item titled "illustrative example." " We explore how average detection delay varies under controlled variation of various parameters such as changepoint location, dimensionality and structure of the ambient space, and the type of action sets. Our objective is twofold: (a) Illustrate gains due to adaptivity of proposed e-GCD over the non non- -dn-addptive method, where actions are chosen uniformly at random; (b) Demonstrate "near" optimality by baselining against Oracle.
This matrix also arises commonly in linear design of experiments the Kiefer- Wolfowitz matrix LS20

---

We report results for the case when the ambient space is line graph (see Illustrative example in Sec. 3. Nodes are interpreted as physical locations, and take values in [N]. Nodes j. k are connected if 1. Each node n E [N] offers a Gaussian-distributee observation depending on the changepoint v N.
Isolated and Structured Anomalies. The vector of change parameters 0 = =00,] are of two types: (a) Isolated singleton change, namely, On E {0, 1} and EnE[N] On 1; (b) Structural changes, i.e.,
[N]
(u = {n E [N] 0% # 0} is k-connected set with 0 E {0,
Diffuse and 'Pointy' Action sets. In parallel fashion consider two types of action sets. The set A1, is pointy, namely. Supp(AA)] = I. which allows probing only single nodes. The set A is diffuse where only a connected subset of nodes be queried. In either case, the observation received on an action is as described in Sec.
Key Findings. We report results for pointy ac- tions and isolated anomalies, and defer other settings to the appendix. We choose o² 0.5, such that the false alarms are about 1% for the Oracle, and forced exploration rate 0.2. Our results are averaged over 5000 Monte-Carlo runs. With this choice for 3 we did not observe false alarms in any of the algorithms.
Utitornly Randem Selecion
aciiee Selection
Gains from Adaptivity. The fact that we perform substantially better than URS uniformly across all of the experiments demonstrates our gains through adaptive sampling.
Data Inefficiency. The fact that the proposed method closely tracks e-GCD+ suggests that our decoupled scheme is capable of fully lever- aging the observations, and the cost of decou- pled exploration is small.
Optimality. The fact that the proposed method tracks Oracle qualitatively across all experiment setups indicates that our method is close to op- timal. This is because through adaptivity we achieve performance similar to competitor who requires no adaptation (recall that oracle knows the change parameters and thus does not need to explore). In point of fact we note in passing that any other method would at best lie between our proposed method and the Oracle.
Figure 2: Audio based change detection of machine
anomaly: Histogram of stopping times by URS, Oracle, and e-GCD. Histograms for Oracic and c-GDD demon- strates clear adaptivity gains.
Variation with Changepoint v. For a fixed graph size, we observed that the average expected delay is relatively constant for all methods, which is consistent with Theorem 3
Audio based recognition of machine anomalies. We experiment using the MIMII audio dataset [Pur+19b). Detailed specifics are in the appendix. The dataset has four machines each equipped with audio sensors recording the health of the machine. There are three types of anomaly (rail damage, loose belt, no grease) which can occur at any time, in any machine. Corresponding to each anomaly there is an audio stream, and the anomaly occurs in one of the four machines an arbitrary time. For each machine, the dataset contains audio-streams of 1000 normal and 300 abnormal files, and each audio-stream is about 10 seconds long.
Audio Processing. For each audio -areio--tteam we train autoencoders on normal data using mel- speccrrooorr features, and Gaussians to the reconstruction errors. This results in pre- and post-change parameters for each machine's 's autoencoded reconstruction error score, corresponding to normal and abnormal operation.
Experiment. To simulate BQCD, we introduced anomalies in machine hearing ID00 as follows. We concatenated 6 normal files and 54 abnormal files chosen uniformly at random from machine ID00. For the other machines we concatenated 60 normal files at random. The 60 files correspond to 600 seconds. Our changepoint corresponds 6th file, which we denote as v 6 and our task is to detect this change. Note that the machine ID and the changepoint are both not known to the learner. Our results are depicted as histograms for changepoints of anomaly detection in Fig. 2 As observed, we notice that c-GCD's performance is close to Oracle both in mean and distribution, while URS exhibits larger delay and significant variance. Appendix DJ presents histograms for a larger changepoint.
10


Reviews:
[{"review_id": "raaBWggrK2S", "reviewer": "Reviewer_r9YP", "summary": "The paper considers the problem of minimising the delay in detection of a changepoint in the distribution of sequentially observed data, subject to a constraint on the rate of false alarms. In particular, this paper is focussed on a bandit-like version of the problem, where a decision-maker must choose what facet of the data to observe at each time point. An example of such a situation is where the sequentially observed data are multivariate, and the decision-maker may only observe one co-ordinate per time-point and must sequentially choose which co-ordinates to observe at which time points, with a view to accurately and rapidly detecting changes. The classical quickest changepoint detection problem may be recognised as a special case of this framework where the decision-maker always has the option to observe all dimensions of the data. The paper has three main contributions: i) a characterisation of the bandit quickest changepoint detection via a lower bound on the detection delay of any algorithm for a given upper bound on the desired false positive rate ii) an algorithm ($\\epsilon$-GRD) for the bandit quickest changepoint detection problem, and iii) a theoretical guarantee on the performance of $\\epsilon$-GRD, showing its desirably small detection delay and its order with respect to the magnitude of the change, structure of the action set, and desired false positive rate. The paper concludes with a numerical study of the algorithm on an open source dataset.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I am quite satisfied with the quality and significance of the theoretical and practical work, and would, overall recommend acceptance of the paper – but I would also recommend certain regards in which the presentation could be improved, in particular so as to make the nature of the problem clear from the outset.\n\nORIGINALITY: The authors do a good job of contextualising their work within the existing literature, drawing parallels to quickest changepoint detection and bandit best arm identification works. The contribution of the paper is original in the sense that the algorithm is new for the problem and that a finite-time analysis of the problem is novel. I am satisfied that the approach and analysis provide a sufficiently original contribution to the literature.\n\nQUALITY: What I have read of the theoretical work is mostly sound, and I appreciate the provision of detailed proof sketches. The assertion that the argmax is a queue on line 197 is confusing to me. Could you provide some more detail here as to what is meant?\n\nI read the Appendix containing theorem 1 in more detail and have two questions, the answers to which should perhaps be made clearer in the paper: on line 602, why is it the case that decisions are independent of the distribution? I would have expected this to have some affect for certain algorithms, certainly for $t>\\eta$, in line 605, how has the $P^(\\infty)(E)$ term been removed so that we arrive at the statement of Lemma 3. I’d also suggest in this section helping the reader out by more specifically referencing the result ported from [GMS19] – e.g. via an equation number of Theorem reference.\n\nCLARITY: Generally the writing is accurate and clear. However I do feel there is work that could be done to present the setting more clearly from the outset. In particular, the description in the introduction is somewhat ambiguous. In the section beginning on line 28 it is not obvious what the nature of the actions in \\mathcal{A} is likely to be – I appreciate the generality of the theory but it is perhaps intimidating in the first instance. It is similarly unclear if X is univariate or multivariate, or if it matters, how the decision-maker reports a change, whether there is a single change or multiple, and (later) why it is realistic to assume that the initial parameter is known. I think a concrete example used at this point (e.g. imagine a sensing network where data … is observed, and actions take the form of … etc) would be beneficial in several regards – providing an example to hang the thinking of, clarity in terms of what is meant by a sensing action etc, and motivating the relevance of the problem. I suspect a yet more useful situation would be to merge the problem specification in section 2 with the initial introduction and use the full precision from the outset in combination with comments as to the intuition, but this may be too much to promise in the rebuttal.\n\nA couple of more minor points are that the equation in lines 193-4 would be much easier to read in an equation display environment, and that similarly Algorithm 1 would be better presented over the full page width.\n\nSIGNIFICANCE: I am not expert in the technologies where this model and its solutions are likely to find use so am unqualified to speak confidently to the realism of the motivating examples. However, it seems very plausible that this bandit-like version of quickest changepoint detection should be a problem encountered in practice, and from a theorists point of view I found the problem and the paper interesting – so I would assess the paper as providing a suitably significant contribution.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "considered sufficiently.", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "oMh-Nkz0yk", "reviewer": "Reviewer_FMqm", "summary": "This paper proposes a bandit quickest change detection framework under resource constraints for data collection. An adaptive online data selection framework is proposed by using a small amount of forced exploration along with greedy exploitation. Theoretical lower bounds to the detection delay are provided and the proposed \\epsilon-GCD algorithm is proved to match the lower bound at low false alarm rates.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The main contribution is the theoretical lower bound for the online change detection through adaptive data selection, and the near-optimality of the proposed epsilon-GCD algorithm. These are new additions to the bandit change detection theory and are consistent with classical theories.\n\nIt seems that there are some inconsistencies between the threshold \\beta used in the algorithm and the theorems:\nFor theorem 2, the threshold \\beta is not consistent with the \\beta used in algorithm 1 -- in theorem 2, since the detection delay is roughly (log\\beta)/KL, this means that the beta here refers to the threshold when using the likelihood ratio as detection statistic (without taking the log, as shown in the appendix), while the detection statistic in algorithm 1 is the cumulative log-likelihood ratio. In other words, the first term in detection delay should be beta/KL for threshold beta used in algorithm 1. \n\nThe numerical experiments are a bit weak: in the numerical results Table 1, better presents the mean and deviation for the simulated detection delay, and the same for Figure 1. Also, it would be interesting to see the tradeoff curves between the false alarm rate and the detection delay.\n\nMinor issues:\n(1) Line 197: should be sum E_\\ell and X_\\ell, A_\\ell in the subscript; and E_\\ell is not defined when introducing the likelihood in Line 193.\n(2) Line 313: Line number missing (??) for Algorithm 1 mentioned\n(3) Line 350: missing equation number (??)", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "oE5wAjX4UsV", "reviewer": "Reviewer_Fs8Y", "summary": "The paper provides a fundamental analysis of delay in the bandit change-point detection problem given a false alarm constraint. The authors propose a variant of CUSUM algorithm [Pag54], which is proven to asymptotically achieve the fundament limit of detection delay given well selected hyperparameter and a set of assumptions. Beside the theoretical analysis, they also provide interesting numerical experiments showing superiority over uniformly random selection strategy.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "It is clearly interesting to have such a fundamental limit analysis and algorithm achieving it. However, my major concern are the impractical assumption and the limited justification (theoretical and numerical), in particular, compared to existing ones as the considering problem is not new. I leave questions, comments and suggests in what follows.\n\n- I believe the authors are also aware of exiting works showing optimality and optimal algorithm in similar bandit change-point detection problem. However, it is unfortunate that there is no clear comparison with them in neither theory nor experiment. At least, the algorithm in  [ZM20] seems comparable to the proposed algorithm.\n\n- The framework of considering false alarm probability may be able to be converted/connected to the framework of piecewise-stationary bandit, ​e.g., Cao et al. \"Nearly Optimal Adaptive Procedure with Change Detection for Piecewise-Stationary Bandit\", 2019. Any discussion on these two frameworks would be helpful.\n\n​- I don't think the example of cameras with local view is really motivating the proposed framework, in which $\\theta^{(0)}$ and $\\Theta^1$ are known in advance. Such a set of prior knowledge seems hard to be obtained in practice. In addition, there is no connection to the trade-off between the detection and sensor activity budget.\n\n- There are a number of typos (e.g., $\\theta_0$ or $\\theta^{(0)}$) and editorial errors (especially, broken references). The notation system overuses super/sub-scriptions. I don’t understand what $(1)$ means in $\\Theta^{(1)}$.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": ".", "review_text": "", "extra_scores": {"ethical_concerns": ".", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "12"}, "extra_text": {}}, {"review_id": "ChiZtqMNiss", "reviewer": "Reviewer_P4K6", "summary": "This paper studies the bandit changepoint detection problem, where the observation ($X_t$) depends on multi-dimension action (sensing action ($A_t$)). The distributions associated with the problem change once at the unknown time $\\nu$. The distributions before time $\\nu$ are called pre-change distributions, and after $\\nu$ are called post-change distributions. The goal is to design a policy to identify the change in the distributions as soon as possible.\n\nThe authors develop and analyze algorithms named $\\epsilon$-Greedy Change Detector ($\\epsilon$-GCD). Experimental results verify the performance of the proposed algorithm.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: A new algorithm $\\epsilon$-GCD is proposed and analyzed for adaptive changepoint detection. The lower bound at a low false alarm rate for the changepoint detection problem is also given in the paper.\nThe authors have adequately cited the prior work and differentiated their work from previous contributions.\n\nQuality: I find the results given in the paper technically sound, but I have not checked all the theoretical proofs in the Appendix.  Although the authors' claims are supported by theoretical analysis and experimental results, I find the following issues with the paper (depending on the authors' response, I may change my score):\n1. Abstract (Lines 4-6) and Introduction (Lines 26-27) suggest that the authors want to minimize the sensing cost with detection delay. But they only focus on minimizing the detection delay (Line 34 and the way sensing actions are selected (Line 165) implies that the goal is to reduce the detection delay, whatever the sensing cost is).\n2. Even though the distribution of the observations $(X_t)$ depends on sensing action $(A_t)$, but it is not clear how $X_t$ and $A_t$ are related. If there are no constraints, then they may be independent.\n3. The pre-change distributions and possible post-change distributions (set) are known, which may not be possible in practice.\n\nClarity: The paper is well-organized, but the writing is needed to improve the readability of the paper. There are a few minor comments:\n1. $E_l$ in Line 193 is used before defining it.\n2. Line 197: subscript $t$ --> subscript $l$ \n3. Missing references in Line 313 (fixed in supplementary) and Line 350.\n\n\nSignificance: Other researchers may find some ideas in the paper useful for their future work on similar problems.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Since this work is a theoretical paper, I do not find any direct negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "I do not find any ethical issue with the paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "13"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a borderline paper. After thorough discussions among Reviewers, I would lean towards a rejection. 

Reviewers have posted many excellent advices which I hope the authors would be able to take advantage of in their revision. The following additional comments are my own read: 

The paper considers distributed quickest section, where the trade-off between sensing cost and detection delay is optimized in a bandit feedback setting. First, an information theoretic lower bound is derived on the detection delay for parameterized probability distributions. Then a computationally simple sensing scheme  that has optimal expected detection delay at low false alarm rates is proposed, and the empirical performance is tested on real and synthetic datasets. 

Some of the results, especially the lower bounds for distributed detection are interesting.  Some concerns are raised below:

#. The framework is not clearly defined. There should be a trade-off between the cost of information acquisition and the informativeness of the signal received. This is a natural trade-off. Perhaps a trade-off between number of sensor pulls (crude measure of informativeness) and detection delay would have made for a clearer framework. 	

#.	The reason for not using regret as a performance measure is poorly motivated. This makes the problem very similar to classical change detection with a known likelihood, and renders the contribution incremental. This perhaps weakens the contribution of the lower bounds as well, as [Lai98] already establishes a lower bound in a similar setting.  

#.	It is not clear what the dimension of $\theta$ is? It seems just pulling one arm alone provides information as to whether there is a change or not? Why bother exploring? Also, It is not clear what `more informative’ means here. Are there better sensors in the group that always provide more information? 

#.	In step 13, the parameter is calculated using an MLE based on the whole history. This makes the policy to choose the `action’ in step 14, non-indexable. How is this addressed? 

#.	Having a common parameter for all arms means that pulling any arm would provide information about all arms. How is the correlation information used?   

Some other concerns:

#. Parametric quickest detection procedures, while interesting theoretically, are a serious limitation in an applied bandit framework, where the distributions are usually unknown or chosen by an adversary. How to extend the results to a non-parametric/ or perhaps a semi-parametric setting? To an adversarial setting?

#. Can $epsilon-$QCD be used for detecting transients? 

$. Why is there no comparison with simple non-parameteric detection algorithms?
Decision: Accept (Poster)