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 informmtiion-therreee 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--Poee
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.... .1...... At-1- Ae-1--0 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 j,t 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 0, |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/()) 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. E--LE Ee log Jog (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 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 ~ Po [-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- togliikelhhod 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]+ -
8 8log 3
0 pplly (2) 1o(o [Qw)] .P)
(1 - e) maxa D (a)(
(1)
provided r(agg) > 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- oonogruun truth queue Q (1) (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)) (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, 4n
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 1. 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. argma 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 -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": "jaXt83DHSQC", "reviewer": "Reviewer_Qkr9", "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.", "questions": "", "limitations": "", "rating": 7, "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": "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.\n2. 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?\n3. 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. \n4. 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.\n5. 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. \n\nThe 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are no negative societal impacts in this theoretical paper that focuses on changepoint detection under bandit feedback.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "Y4sXwobKXs", "reviewer": "Reviewer_p3ra", "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.", "questions": "", "limitations": "", "rating": 5, "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": "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?\n\nI 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.\n\nThe 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.\n\nThe 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.\n\n\nMinor comments:\n- 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.\n- What is ‘the most informative action’ as described? Is there some connection to a partial monitoring problem? \n- the formatting of Algorithm 1 is strange, there should be a line space below.\n-  Is Q^(2) ever defined in Algorithm 1?\n- Is N_tau(a) defined on line 178?\n- I don’t see the relevance of the queuing in section 4", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "9"}, "extra_text": {}}, {"review_id": "Br9uxQqlY2", "reviewer": "Reviewer_R5bK", "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. ", "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": "Problem \n-------------\nI 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.\n\nClarity \n-------------\nWhile 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 \n- 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\n- 267-275 - its not clear to me what exactly is the statement about the second term and what is the interpretation of this distance\n- 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.\n- 313 - ??\n- In many places I was not sure if \\nu = 1\n\nThe 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. \n\nNovelty\n-------------\nI 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. \n\nExecution and Questions\n----------------------------------\n- 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? \nFrom 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?\n-  Theorem 2 assumes \\nu = 1? Or is this just for the sketch proof?\n\n-  Similarly is lower bound for \\nu = 1 or more general?\n\n- 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?\n\n - 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.\n\n- 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. \n\n-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.\n\n-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?\n\n-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.\n\n\nCurrent Verdict\n--------------------\nWhile 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. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This is mainly theoretical work and the sociatal impact were not analyzed. ", "review_text": "", "extra_scores": {"ethical_concerns": "None I identified.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)