Quickest change detection for multi-task problems under unknown parameters
Authors: Firas Jarboui
Vianney Perchet
Venue:  (2021)
Keywords: Quickest Change detection
Parametric approach
Multi-task

Abstract: We consider the quickest change detection problem where both the parameters of pre- and post- change distributions are unknown, which prevent the use of classical simple hypothesis testing. Without additional assumptions, optimal solutions are not tractable as they rely on some minimax and robust variant of the objective. As a consequence, change points might be detected too late for practical applications (in economics, health care or maintenance for instance). 
Other approaches solve a relaxed version of the problem through the use of particular probability distributions or the use of domain knowledge. 

We tackle this problem in the more complex Markovian case and we provide a new scalable approximate algorithm with near optimal performance that runs in $\mathcal{O}(1)$. 

Under review as a conference paper at ICLR 2021
QUICKEST CHANGE DETECTION FOR MULTI-TASK PROBLEMS UNDER UNKNOWN PARAMETERS
Anonymous authors Paper under double-blind review
ABSTRACT
We consider the quickest change detection problem where both the parameters of pre- and post- change distributions are unknown, which prevent the use of classical simple hypothesis testing. Without additional assumptions, optimal solutions are not tractable as they rely on some minimax and robust variant of the objective. As consequence, change points might be detected too late for practical applications (in economics, health care or maintenance for instance). Other approaches solve a relaxed version of the problem through the use of particular probability distributions or the use of domain knowledge. We tackle this problem in the more complex Markovian case and we provide a new scalable approximate algorithm with near optimal performance that runs in (1))
INTRODUCTION
Quickest Change Detection (QCD) problems arise naturally in settings where latent state controls observable signals (Basseville et al., 1993). In biology. it is applied in genomic sequencing (Caron al. 2012) and in reliable healthcare monitoring (Salem al. (2014). In industry, it finds application in faulty machinery detection (Lu et al. 2017 Marti et al. 2013)) and in leak surveillance (Wang et al. 2014). It also has environmental applications such as traffic-related pollutants detection (Carslaw
et al. 2006).
Any autonomous agent designed interact with the world and achieve multiple goals must be able to detect relevant changes in the signals it is sensing in order to adapt its behaviour accordingly. This particularly true for reinforcement learning based agents multi-task settings as their policy is conditioned some task parameter (Gupta et al. 2018: Teh al. 2017). In order for the agent to be truly autonomous, it needs to identify the task at hand according to the environment requirement. For example, robot built assist cooks in the kitchen should be able recognise the task being executed (chopping vegetables, cutting meat, ..) without external help to assist them efficiently. Otherwise, the agent requires higher intelligence (one of the cooks for instance) control it (by stating the task to be executed). In the general case, the current task is unknown and has to be identified sequentially from external sensory signals. The agent must track the changes as quickly as possible adapt its environment. However, current solutions for the QCD problem when task parameters are unknown, either do not scale impose restrictive conditions on the setting. (i.i.d. observations, exponential family distributions, partial knowledge of the parameters, etc.).
In this paper, we construct a scalable algorithm with similar performances to optimal solutions. For this purpose, we use the change detection delay under known parameters as a lower bound for the delay in the unknown case. This improves our estimations of the parameters and thus improves our change point detection. We consider the case where the data is generated by some Markovian processes as in reinforcement learning. We assess our algorithm performances on synthetic data generated using distributions parameterised with neural networks in order match the complexity level of real life applications. We also evaluate our algorithm on standard reinforcement learning environment.
2 QUICKEST CHANGE DETECTION PROBLEMS
Formally, consider a sequence of random observations (X₂) where each X, belongs to some ob- servation space X' (say, Fuclidean space for simplicity) and is drawn from fo, (-1Xt-1), where

---

Under review as a conference paper at ICLR 2021
the parameter Or belongs to some task parameter space @ and {fe, O E ) is a parametric prob- ability distribution family (non trivial, in the sense that all fo are different). The main idea is that, at almost all stages, 0e+1 = 02 but there some "change points" where those two param- eters differ. Let us denote by la the different change points and, with a slight abuse of notations, by 0k the different values of the parameters. Formally, the data generating process is therefore: X₂- Σ for (x
The overarching objective is to identify as quickly as possible the change points tq and the associated parameters fg. based on the observations (Xt). Typical procedures propose to tackle iteratively the simple change point detection problem, and for this reason we will focus mainly on the simpler setting of single change point, where K = 2, to = 0, t1 = À and l2 = oc, where is unknown and must be estimated. For a formal description of the model and the different metrics, we will also assume that the parameters (0u, 01) are drawn from some distribution F over O As a consequence, the data generating process we consider boils down to the following system
1
8o: 01 F and {
Xx+1 ~ So (.),) if 15 Xe+1 ~ (x))
if
1>>
2.1 CRITERIA DEFINITIONS
As mentioned, the objective is to detect change points as quickly as possible while controlling the errors. There exist different metrics to evaluate algorithm performances; they basically all minimise some delay measurements while keeping the rate of type errors (false positive change detection) under a certain level. We will describe later on different existing definitions of these criteria (type I error and delay). In order to evaluate probability of error and an expected delay, we obviously need to define relevant probability measures first. Traditionally, there are two antagonistic ways to construct them: the MIN-MAY and the BAYESIAN settings (Veeravalli & Banerjee 2014).
First, we denote by Pn, (resp. E,)) ) the data probability distribution (resp. the expectation) conditioned to the change point happening at À n. This last event happens with some probability ıı(A n) with the notation that bold characters designate random variables-, and we denote by IP (resp. E²) the data probability distribution (resp. the expectation), integrated over pt, i.e., for any event Ω it holds that P*(S)) = En saA = (S2). In the following, we describe the major existing formulations of the QCD problem where the goal is to identify an optimal stopping time T:
BAYESIAN formulation: In this formulation, the error is the Probability of False Alarms (PFA) with respect P The delay is evaluated as the Average Detection Delay (ADD) with respect to E
(FA(T) P"(T A) and ADD(T) = E A) > A]
In this setting, the goal is to minimise ADD while keeping PFA below a certain level ar (as Shiryaev formulation (Shiryaev 1963)). Formally, this rewrites into:
{ Va arg min ADD(T) A. = (T: PFA(T) <a}
(SHRyyaV)
(2)
The MIN-MAX formulation disregards prior distribution over the change point. As a consequence, the eтror is measured as the False Alarm Rate (FAR) with respect to the worst case scenario where no change occurs (P so). As for the delay, two possibilities are studied: the Worst Average Detection Delay (WADD) and the Conditional Average Detection Delay (CADD). WADD evaluates this delay with respect to the worst scenario in terms of both the change point and the observations. CADD is less pessimistic evaluation as it only considers the worst scenario in terms of change point. Mathematically they are defined as:
Min-Max formulation:
F and {
WADD(T) = sup, esssupx In m)+ [X"]
FAR(T)
CADD(T) = sup, E.,((T - nn)
where X designates all observation up to the 12th one. In this setting, the goal is to minimise either WADD (Lorden formulation (Lorden et al. 1971)); ); or CADD (Pollak formulation (Pollak) 1985)
while keeping FAR below a certain level a. Formally, these problems are written as follows:
{
Va arg min WADD(T) and (POLLAK) {
Vo = arg min EA CADD(T)
(LORDEN)
A. (T: FAR(T) <a)
Aa = (T FAR(T) < <a)
(3)
2

---

Under review as a conference paper at ICLR 2021
3 TEMPORAL WEIGHT REDISTRIBUTION
Under known parameters, optimal solutions for the QCD consist in computing some statistics, denoted by S80.81 along with a threshold a., The stopping time Va is the first time 5% exceeds Ba. We provide more detailed description in Appendix A.1
3.1
ASYMPTOTIC BEHAVIOUR OF THE SOLUTION TO THE BAYESIAN FORMULATION
The SHIRYAEV algorithm (Shiryaev 1963) is asymptotically optimal in the i..dd case Tartakkvsky & Veeravalli 2005). This result extended to the non i.i.d. case under the following assumption:
Hypothesis
Given fo, and Jor there exists q IR and E IN such that for any k N:
D fe, (X)) (X++1(((
reguishly n-++000 9
(4)
Under Hypothesis 1 and with exponential heavy tail prior, the SHIRYAEV algorithm is asymp- totically optimal (Tartakovsky Veeravalli] 2005). addition, the moments of ADD satisfy the following property for all S Tartakovsky & Veeravalli 2005):
[M - -> ^| 0 E"[ > a=0
[lo((a) q+d
T
(5)
where v is the SHIRYAEV algorithm stopping rule and d = lim,, log P(A > n 1)/n. Our approach the QCD problem under unknown parameters relies on the asymptotic behaviour from Equation (5) up to the second order (r = 2). We use it as a lower bound for the detection delay, providing natural segmentation to our data when approximating the parameters. We will discuss this more in details in what follows.
3.2 RATIONAL FOR TEMPORAL WEIGHT REDISTRIBUTION
In the following, we denote the true parameters by 0 and 07 and the corresponding stationary distributions by 11 and II; (that are well defined for irreducible Markov Chain). The purpose of this section is to devise algorithm learning the parameters Oj and 0j using the asymptotic behaviour of the detection delay under known parameters. The delay predicted Equation (5) is performance lower bound in setting (otherwise it would contradict the optimality of the SHIRYAEV algorithm).
Intuitively, the idea to learn 0i using the last [log(o)] observation and to learn O using previous observation. This simple technique happens to be efficient and computationally simple.
q+-d
Parameters optimisation: The optimal S/0.00 called the SHIRYAEV statistic - has a specific form (see Equation (2) in Appendix) and the QCD problem under unknown parameters is equivalent to:
Va arg min, (t) (t)SSo..r Ba) where {
0g arg ming so 0+)
0 = arg max f000 0)
fa, (X.+1 (x)) and (80, 0¹) are random initialisation parameters, fo(O.. 0,) Eg log
(0 01)
(X...
Ej [lo fo, (Xe4: (X+) and (0.1) is the expectation with respect to the probability distribution
Te, (X.
PA (Xe, = (X),)ee (X)+1lx).. In fact, the solution to Equation 6 is the optimal
stopping time under the true parameters. This is consequence of the following Lemma
Lemma 8% and Of verifies the following for any 0,,0;:
85 arg ming fo(0, 01) and 07 arg maxy (fu.
In order to solve the equivalent QCD problem of Equation 6 good approximation of the functions fu and fi given the observations (X₂)² is required. This implies the ability to distinguish pre-change intractable. They
samples from post-change samples and this is precisely why optimal solutions compute the statistics for any possible change point and consider the worst case scenario. Previous approximate solutions simplify the setting by using domain knowledge to infer the pre-change
3

---

Under review as a conference paper at ICLR 2021
distribution and by using sliding window evaluate the post-change distribution. The window size w is an irreducible cost in the expected delay.
With known parameters, optimal algorithms have an average detection delay proportional to the error threshold a and to the inverse of the KL divergence between the pre and post change distributions. Given the optimal stopping time Va. it's possible to evaluate the posterior distribution of the change point P(A = t/p = n), which in turn a good classifier of the pre and post change observation:
P(X, ~ fa V/- = n) x P(A > t/va = n) P(X, ~ fo, I/- = n) x P(A < t|y n)) (8)
The objective of this section is to exploit this classifier to construct family of functions that approximate well fo and fi. Consider the following family of functions:
(6.. 01) = F. log( fo1 [X)+1|X+7] and f(" (Ou, 01) = ET [og( Too
fo Too
(X+++((x)))
where both the observations X2 and the indicies are random variables. The observations are generated using Equation ① with a finite horizon 12. The indicies are sampled with respect to ~ P(A T/P n - P(A > ilva n) in Eg while they are sampled with respect to P(A T n// EL P(A< ilv = n) in ET.
The family of functions f are a re-weighted expectation the log- ratio of the observations using P' = 12). Basically, under the assumption that the optimal detection happens at f n, we associate to each observation X, weight proportional to P(A > T/V, n) when estimating fo (and respectively proportional to P(x < T/Va n) when estimating f1). In addition, this family of functions is practical as we can approximate asymptotically P( V/a = n) using the theoretical delay behaviour the SHIRYAEV algorithms presented in Equation
Lemma 2 For any given parameters (fu. 01), the following convergences hold:
If X oc, then: lim I.f (0o. 01) - fo(Oo. (000))))=== = lim (ff. 01) fo 01)1
If X < oc, then:
limm, f (0o 0₂) f1000.
lim
1 (0. 02) - f10.. 01)
=
lim fi (Bo: 02) f1 01)
For any integer E IN, ift2 A then: -oo 180 fol = O.
major implication of Lemma| 2 is that with enough observations, f6" and f will eventually converge to the functions fo and J1. In fact, fú approaches fo up to %a and then start degrading (as ends up converging to fi) whereas f becomes a better and better approximation of fi around v. and improves asymptotically. As such, are going consider the following problem proxy to the original QCD problem (Equation (6).
{ 0 arg min, fa --))
ia = arg min, (1/5,5.0 (
B.)
where
0 arg max [(((0-1111)
(9)
The rational behind this choice is that around the change point, 5/6.i converges to Sffo0 Having access perfect evaluation of the functions fo and f1 guarantees the fastest possible detection. In fact, Va the optimal stopping time under known parameters - is a lower bound to the detection delay in this setting. In practice, only the first observation are accessible evaluate f and fi. This introduces approximation errors to the estimates 0j and 0g. thus delaying the detection. However, this is not detrimental the evaluation of the stopping time. Indeed:
Before va: : 8 is good estimator of Bj and 0 is a bad estimator of 07. In fact, the fraction of pre- change observations used learn 8 is of the order of min(1, A/t). This helps maintaining low log-likelihood ratio (equivalently maintain sfh below the cutting threshold), the estimation of 0r will converge to a parameter close to 0%
After Va: 8f is a good approximation of 01, but 6, is a noisy estimation of 6 (as post-change observations are used to learn it). The fraction of the data generated using 0f but used to learn 0j is proportional to t_Me, This favours - up to a certain horizon higher log- likelihood ratio estimates (equivalently an incremental behaviour of the sequence s. We will discuss further the performance issues of solving Equation (9) in the following.
4

---

Under review as a conference paper at ICLR 2021
Distribution Approximation: In order to exploit the previously introduced results, need good approximation of P(A)// = =)). If the observation satisfy Hypothesis then the moments of P(A n) up to the TThh order satisfy Equation (
When r = oc, this is equivalent to the Hausdorff moment problem. which admits a unique solution. The generalised method of moments can be used to approximate this distribution. In the remaining of this paper, we will restrict ourselves to the case where r = 2. There is an infinite number of distributions that satisfy Equation (5) in this case; however, given a parametric family, we can compute analytically a solution of the problem so we consider the Logistic distribution. For a given Oo, O,,
approximate P a
=n) with flo.01 Logistic(u,, s) where μ
Dan ( 1o, )+d and
[lo[(a)
8 Log(a) [e Ie, J+4) Verifying that fl satisfies Equation (5) for m S 2 is straightforward.
As a consequence, P(T > t/T ~ flb.01 is a fair approximation of PP A > t/p = n).
Solving the problem given by Equation ( unfortunately yields poor performances for extreme values of the error threshold a. This is due to a degraded log likelihood estimation both before À and as t + co. In fact, the log- logeliiel ratios Ly and Lł defined as:
Limitations:
fej (X1+1(Xx) and (x(X++1 = log (Xi+1(Xt),
fet
(X = log Fog
Jog
satisfy the following lemma:
Lemma The log- bog-likeldhood ratio L, and L2 admit the following asymptotic behaviours: lim Ex|2a| < O but Lx on, 0: lim Ex[Li|A oo] > 0 but Le 2
0..
0
(10)
1-000
20+0000
Practically, this means that before the change point, the log likelihood ratio is over-estimated (as it should be smaller than 0), while after the change point, the log likelihood ratio is eventually under-estimated (as it should exceed 0). This is a consequence of Lemma In fact, for / >> (respectively for S. A), both functions fú and fí are approaching fi (respectively fo). Thus in both cases of and 0f converge the same value. However, combined with the behaviour of fü and fi around Vaa from Lemma 2 we can expect the Kullback-Leible (KL) divergence Dxr (fez II fe; to converge to 0 before and after the change point while peaking around the optimal stopping time. We exploit this observation to mitigate the problems highlighted with Lemma
Annealing: The under-estimation of L; after the change point due to the use of post change observations (drawn from fo:) when estimating 0j. In practice, this is particularly problematic when the error rate must be controlled under a low threshold a (cquivalently a high cutting threshold Ba) or when the pre and post change distributions are very similar. When t approaches the optimal stopping time (t zs va), the minimising argument of fü is converging to 8-. As grows, the approximation få is degraded, while ff is becoming better approximation, thus ff starts converging 0J. This leads to an increase in the KL divergence. Our proposition is to keep optimising the version of fó that coincides with this increase (which in turn is fØ the best candidate identify 0j). As fix, we propose: 1- to shift the probability PP T|pS n) by replacing it with P(x A n) (where A is the 'delay" of the detection with respect to the Shiryaev stopping time: (n - -- +2)+), and anneal the optimisation steps of 0j as the KL divergence increases. These tweaks correct the objective function used to learn 0j and stop its optimisation when the observations start to deviate from the learned pre-change distribution. The delay can be formally introduced by replacing L6 with fó in Equation (9). In practice, A a delay heuristic that increases as the KL divergence increases. This reduces the noise when learning 0j- The second idea is to use probability Po = 1 Ae of executing a gradient step when learning the pre-change parameter. This anneals the optimisation of 0j-
The over-estimation of L; before the change point, is due to the exclusive use of pre change observation when estimating 07. This particularly problematic for application where high error threshold is tolerable (equivalently a low cutting threshold for the used statistic). This is also an issue when the pre and post change distribution are very different. As a solution, we penalise the log-likelihood using the inverse KI. divergence. Before the change point, both parameters converge to 0ū: this means that the KL divergence between the estimated distributions is around O. Inversely, after the change point, if the optimisation of 0 is annealed, the KL divergence between the estimated parameters must hover around DxL (foz (l Formally, penalising the log likelihood can be seen as using f., when computing the statistics S, where f. I, c/ (Ka fl;)) for some real c 0.
Penalisation:
5

---

Under review as a conference paper at ICLR 2021
We provide in the appendix ablation analysis well as experimental proof of the effectiveness of both annealing and penalisation.
Algorithm: In practice, only the first observations available in order to evaluate the param- eters (0) 0.). Hence, we design a stochastic gradient descent (SGD) based algorithm to solve
Equation (9. Consider the following loss functions, where I is set of time indices:
CB (1, 00, 01) = Eier P(T t/T ~ fllo.1) log( fer (X(+1(Xx)) Ino
(11)
(T, 01) = EiEr P(T t/ f log(
J0: (X
560
The quantity C% is an estimator of fk using the observations (Xe)sEI- The rational previously discussed implies that by re-weighting random samples from the observations we can approximate the functions f& using the familly of functions fk.
good approximation of og and of can be obtained with few SGD steps. These parameters are used to update the SHIRYAEV or the CUSUM statistic. The change point is declared once the threshold B, exceeded. The proposed procedure is described in Algorithm []] In addition to the classical SGD nyper-parameters (number of epochs, gradient step size, momentum, ...), we propose to control the penalisation and the annealing procedure using the coefficients c, respectively.
Algorithm 1 Temporal Weight Redistribution
1: Procedure: TWR(0" 0² (X, 12 Ne. Ba, 6, c)
2: Initialise S 0; 0, 01 + 0 00; A f- 0: and Pa +-
3: for t E [1, [z] do
4: for [1, N. do
5: Randomly sample I: a set of indices from [0,4]
6:
Oo + gradient update rule(0o. Ve, Ch (1, 0o, 01]) with probability po
7:
01 f gradient update rule(01, -o, Li, (1, (1, 01))
8:
end for
9:
S < statistic update rule(S,
fea
for (X++1
Daa(fa fag
10:
If S > Ba then declare change point and break
11:
If DKL, (fo > D then A &+A A
and po +- Po
12:
D + t-1 D- + DDu((fo,for
13: end for
RELATED WORKS
Existing solutions for the QCD problem under known parameters can be extended to the case of unknown parameters using generalised likelihood ratio (GLR) statistics. For example, an optimal solution for the Lorden formulation is a generalisation of the CUSUM algorithm using the GLR statistic for testing the null hypothesis of no change-poing based on (X,)8. versus the alternative hypothesis of a single change-pott prior to n. However, given n observation, this solution runs in O(n²). Others approached the problem from a Bayesian perspective by keeping track of the run length posterior distribution (the time since the last change point). Since in practice this distribution is highly peaked, the Bayesian Online Change Point Detection (BOCPD) algorithm (Adams & MacKay 2007) is namely a good alternative in the i.i.d. setting. In fact by pruning out run lengths with probabilities below or by considering only the K most probable run lengths, the algorithm runs respectively in Onn/c) and OKKn) without critical loss of performance. Extensions of BOCPD algorithm to the case of non i.i.d observations, namely the Gaussian Process Change Point Models run in (n (Saatchi et al. 2010). If pruning is applied, the complexity can be reduced to O(n R2 22/// /e) or O(K R2) where R is the typical unpruned max run length (Saatchi et al. 2010).
To avoid this complexity issue, multiple approximate solutions that run in ((1) have been proposed
over the years. However, common practice (Nikiforov 2000 Li et al. 2009 Unnikrishnan et al.. 2011 Singamasetty et al. 2017 Molloy & Ford 2018) is assume that pre-change parameters are known as this is not a major limitation in many applications (fault detection, quality control...) where the pre-change corresponds to nominal behaviour of process and can be characterised offline. sub-optimal solution (Nikiforov) 2000) is to track in parallel S% over a subset of possible post-change distributions and consider the worst scenario. Somewhat Similarly approach,

---

Under review as a conference paper at ICLR 2021
adaptive algorithms (Li et al. 2009 Singamasetty et al. 2017) attempt to improve this procedure by
tracking 5% where 01 arg max, fi (00, 0). Different from proceeding works, our contribution in this paper is an approximate procedure that can handle the case of unknown pre- and post- change parameters, runs in (1)), and have near optimal performances.
EXPERIMENTAL RESULTS
Detection delay on synthetic data: The distribution family fo used experimentally to simulate data given the pre/post change parameters and the previous observations relies on two deep neural network (dze. (x) used to evaluate the parameters of a Gaussian distribution such as: fo((1x) = ((,,,(0, 2)) & (f,x))) We compare our algorithm to three other possibilities: the optimal log- likelihood ratio (an oracle having access to the true parameters), the generalised log-likelihood ratio (GLR) and the adaptive log-likelihood ratio where the pre change parameters are learned offline (a fraction of pre-change observations are used to learn Bn).
We also introduce an alternative metric to the average detection delay: the regretted detection delay. An oracle with access to the true parameters will predict change as fast as the optimal algorithm under known parameters. In order put performances into perspective, for a given cutting threshold B, the regretted average detection delay RB((a) of an algorithm, is the additional delay with respect to the oracle. If we denote the oracle's optimal stopping time vB and the algorithm stopping time v2. then: (a( = [[v] - PB) ++|11] 1 2 VB 2 A]. This formulation of the regret is conditioned to 1/B 2 vB for the same reason that the measurement of the average detection delay is conditioned to MB 2 X. An algorithm that predicts change faster than the optimal one under known parameters, is over- wer-fitting the noise in the data to some extent. For this reason, when comparing performances, there no true added value in detecting changes faster than the optimal al algorithm in the known parameter setting.
We evaluate the performances using the SHIRYAEV update rule for the statistic (solution to the BAYESIAN setting). We provide in the appendix the analysis using the CUSUM update rule (solution to the MIN-MAX setting) with the same conclusions. We evaluate the regretted detection
Regreted detection
shiryaev statistic
adaptive
GLR
delay in the case where X' R θ = R 10 and (Φn. Φ.) are 5-layer deep, 32-neurons wide neural network. We use synthetic example where the KI. divergence between pre- and post- change distribution is DKL (s;; 33. This allows us to view performances in difficult settings. For higher KL divergence values, change detection becomes easier. We provide in the appendix the same analysis for the case where (fz lfo;) = 3. In Figure I we provide the average regret overs 500 simulations. Each simulated trajectory is 1000 long with a change point at the 500th observation. We use the full pipeline of our algorithm with penalisation coefficient (c = 0.01), and we allow the adaptive algorithm exploit 10% of the pre change observations. Our algorithm (the blue curve) achieves comparable performance to the GLR statistic (without requiring intensive computational resources) and achieves better and more stable results compared to the adaptive algorithm (without requiring domain knowledge).
30a
30.-
101a
1000
3000
30th
10
Figure 1: Regret as function of B.
Multi-task reinforcement learning: Consider a task space Q and for each task 0 E θ the associated Markov decision process Ma = (S. A, P, Re, 7 where S is the state space, A is the action space, is the environment dynamics, Rg the task specific reward function and y is the discount factor. We evaluate algorithms using the copycat agent scenario: a main agent is solving a set of unknown tasks (Q.)/ and switches from task to task at unknown change points (t,) We denote 0 = E, d, (t) the task being solved over time. Our goal is to construct a copycat agent predicting the main agent's tasks online through the observation of the generated state action (st, az) E S A. This scenario has many different real life applications: Users of any website can be viewed as optimal agents solving iteratively a set of tasks (listening to sets of music genre, looking for different types of clothes, ..). The state space corresponds to the different web-pages and the action space is the set of buttons available to the user. We argue that predicting the task being solved online is important feature for behaviour forecasting and content recommendation.
7

---

Under review as a conference paper at ICLR 2021
Log- Log-likelihodd between estimated parameters
Error of the latent parameters estimation
60
0.35
TWW
Lest
40
actual
detected
0.25
0.20
-20
0.30
Log Mielioood
actuual change point
0.05
-60
detected change point
0.00
(a) LLR between fag and foz
(b) Prediction error the task O2
Figure 2: Performance analysis of the copycat problem
In the following let Iz = (st, 0z) denote the observations and let Th denote the optimal pol- icy of Mg. The copycat problem is QCD problem where the observations are drawn from fo(#141 (2x) = P(s ax) (z) (T) (ar+ 1 1). However this implies that we have the optimal pol- icy zg. In practice it sufficient to either have access to the reward functions R. or set of task labelled observations. In both cases the problem of learning Tá is well studied. When Rg is known, then coupling Hindsight Experience Replay (Andrychowicz et 2017) with state of the art RL algorithms such as Soft Actor Critic (Haarnoja et al. 2018) can solve wide range of challenging multi-task problems (Plappert al. 2018). When history of observations are available, we can use generative adversarial inverse reinforcement learning (Ho & Ermon 2016) or Maximum Entropy Inverse Reinforcement Learning (Gleave & Habryka 2018 Yu et al, 2019) to learn x..
We evaluate our algorithm performances the FetchReach environment from the gym library. Each time the main agent achieves the desired goal. a new task is sampled. We run this experiment for 500 time step. Temporal Weight Redistribution (TWR) is used in order to evaluate the tasks online. Algorithm | is easily adapted to the multiple change point setting: each time a change point is detected, reinitialise the parameters A and pa and we the task parameters the previous post change parameters. As such, we use the running estimate O overtime to approximate the main agent task 0r. Experimental results are reported in Figure 2
We used the TWR algorithm with an annealing parameter e = 0.1 and a penalisation coefficient c= 0.01, and the CUSUM statistic with a cutting threshold Ba, 50. We designate the task change points of the main agent with dashed black lines and the detected change points with dashed red lines. On Figure 2a we observe that the log- likeliooddood ratio (LLR) log(fe; / / fag (z+) starts off negative, stabilises around 0 and becomes strictly positive after the actual change point. Once the change detected, we reset the TWR and the LLR falls down
negative value. This trend consistently reproduced with each new task. The main agent have small probability of making random action, this causes the LLR to peak sometimes before the change point. However this doesn't t cause the statistic exceed the threshold B., We provide on Figure 2b the estimation error of 67 The blue curve is the error of the TWR estimate |10] - 8, ||- As a baseline we estimate the task using the last 10 observation: 0, arg max, Σ (x:-fe( The error of this estimator | 01 plotted in green. The prediction of the TWR copycat agent are clearly more reliable. Additional experimental results for the Fetchpush and the PickAndPlace environments as well as an analysis of the impact of using learned policies when solving the copycat problem are provided in the appendix.
CONCLUSION
We studied the QCD problem under unknown parameters for Markovian process. Extending our techniques handle higher order Markov chains, (i.e., for some window parameter w > 0, fo de- pends of Xt-wet rather than just the last observation) is trivial, thus covering wide range of natural processes. We provide a tractable algorithm with near optimal performances that relies on the asymptotic behaviour of optimal algorithms in the known parameter case. This mitigates the performance-com dilemma providing the best of both worlds: a scalable procedure with low detection delay. Empirically, we were able outperform previous approximate procedure (adaptive algorithms) and approach the performances of prohibitively expensive ones (GLR). Interesting future direction include taking into account the delay caused by the generalisation error.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Ryan Prescott Adams and David J. C. MacKay, Bayesian online changepoint detection, 2007.
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong. Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In I. Guyon, U. V. Luxburg. S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances Neural Information Processing Systems 30, pp. 5048-5058. Curran Associates, Inc., 2017.
Michèle Basseville, Igor Nikiforov, et al. Detection of abrupt changes: theory and application, volume 104. prentice Hall Englewood Cliffs, 1993.
François Caron, Arnaud Doucet, and Raphael Gottardo. On-line changepoint detection and parameter estimation with application to genomic data. Statistics and Computing, 22(2):579-595, 2012.
David C Carslaw, Karl Ropkins, and Margaret C Bell. Change-poiis detection of gaseous and particulate traffic-related pollutants a roadside location. Environmental science technology, (1122):6912-6918 2006.
VP Draglia, Alexander G Tartakovsky, and Venugopal V Veeravalli. Multihypothesis sequential probability ratio tests. i. asymptotic optimality. IEEE Transactions on Information Theory, 45(7): 2448-22 246-,261, 1999.
Adam Gleave and Oliver Habryka. Multi-task maximum entropy inverse reinforcement learning, 2018.
Abhishek Gupta, Russell Mendonca, YuXuan Liu, Pieter Abbeel, and Sergey Levine. Meta- reinforcement learning of structured exploration strategies. In Advances in Neural Information Processing Systems, pp. 5302-5311, 2018.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor, 2018.
Martin Hairer. Convergence of markov processes. Lecture notes, 2010.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning, 2016.
Tze Leung Lai. On r-quick convergence and a conjecture of strassen. The Annals of Probability, pp. 612-627, 1976.
Tze Leung Lai. Asymptotic optimality of invariant sequential probability ratio tests. The Annals of Statistics, pp. 318-333, 1981.
Tze Leung Lai. Information bounds and quick detection of parameter changes stochastic systems. IEEE Transactions on Information Theory, 44(7):2917-2929, 1998.
Chengzhi Li, Huaiyu Dai, and Husheng Li. Adaptive quickest change detection with unknown parameter. In 2009 IEEE International Conference on Acoustics, Speech and Signal Processing, pp. 3241-3244. IEEE, 2009.
Gary Lorden et al. Procedures for reacting a change in distribution. The Annals of Mathematical Statistics,
1971.
Guoliang Lu. Yiqi Zhou, Changhou Lu, and Xueyong Li. A novel framework of change-poin detection for machine monitoring. Mechanical Systems and Signal Processing, 83:533-544 2017.
Luis Martí, Nayat Sanchez-Pi, José Manuel Molina, and Ana Cristina Bicharra Garcia, Anomaly detection based on sensor data petroleum industry applications. Sensors, 15(2):2774-7977, 2015.
Timothy L Molloy and Jason J Ford. Minimax robust quickest change detection in systems and signals with unknown transients. IEEE Transactions on Automatic Control, 64(7):2976-25 29822, 2018.

---

Under review as a conference paper at ICLR 2021
George V Moustakides et al. Optimal stopping times for detecting changes in distributions. The Annals of Statistics, 14(4):1379-1335) 1986.
Igor V Nikiforov. A suboptimal quadratic change detection scheme. IEEE Transactions on Informa- tion Theory, 46(6))2095-2107, 2000.
Matthias Plappert, Marein Andrychowiez, Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej. Peter Welinder, Vikash Kumar, and Wojeiech Zaremba. Multi-goal reinforcement learning: Challenging robotics environments and request for research, 2018.
Moshe Pollak. Optimal detection change in distribution. The Annals of Statistics, pp. 206-227, 1985.
Ya' acov Ritov. Decision theoretic optimality of the cusum procedure. The Arnals of Statistics, pp. 1464-1469, 1990.
Gordon J Ross. Sequential change detection in the presence of unknown parameters. Statistics and Computing, 2410):0017-1030, 2014.
Yunus Saatchi, Ryan Turner, and Carl Rasmussen. Gaussian process change point models, 08 2010.
Osman Salem, Yaning Liu, Ahmed Mehaoua, and Raouf Boutaba. Online anomaly detection in wireless body area networks for reliable healthcare monitoring. IEEE journal of biomedical and health informatics, 18(5):1541-1551 2014.
Albert N Shiryaev. On optimum methods in quickest detection problems. Theory of Probability & Its Applications, 8(1):22-46, 1963.
Vijay Singamasetty, Navneeth Nair, Srikrishna Bhashyam, and Arun Pachai Kannu. Change detection with unknown post-change parameter using kiefer-wolfowitz method. 2017 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 3919-3923, IEEE, 2017.
Alexander G Tartakovsky and Venugopal V Veeravalli. General asymptotic bayesian theory of quickest change detection. Theory of Probability & Its Applications, 49(3):458 497, 2005.
Alexander G Tartakovsky, Moshe Pollak, and Aleksey Polunchenko. Third-ordes asymptotic optimality of the generalized roberts changepoint detection procedures. Theory of Probability & Its Applications, 56(3):457-484, 2012.
Yee Teh, Victor Bapst, Wojciech M Czarnecki, John Quan, James Kirkpatrick, Raia Hadsell, Nicolas Heess, and Razvan Pascanu. Distral: Robust multitask reinforcement learning. In Advances in Neural Information Processing Systems, pp. 4496-4506, 2017.
Jayakrishnan Unnikrishnan, Venugopal V Veeravalli, and Sean Meyn. Minimax robust quickest change detection. IEEE Transactions on Information Theory, 17(3):1604-166) 2011.
Venugopal V Vecravalli and Taposh Banerjee. Quickest change detection. In Academic Press Library in Signal Processing, volume 3, pp. 209-255. Elsevier, 2014.
Kun Wang, Heng Lu, Lei Shu, and Joel JPC Rodrigues. A context-aware system architecture for leak point detection in the large-scale petrochemical industry. IEEE Communications Magazine, 52(6): 62-69, 2014.
Lantao Yu, Tianhe Yu, Chelsea Finn, and Stefano Ermon. Meta-inverse reinforcement learning with probabilistic context variables, 2019.
10

---

Under review as a conference paper at ICLR 2021
A SOLUTION FOR THE QCD PROBLEM UNDER KNOWN PARAMETERS
In this section, we assume that both the parameters dg and 02 in Equation I are known. We present in the following the main optimality existing results.
Min-Max formulation: In the i.i.d. case (i.e. when fo(. = fo(.). the CUSUM algorithm (Lorden)
al. 1971 is an optimal solution (Moustakides et al. 1986; Ritov 1990) for the Lorden formu- 1 However, even though strong optimality results hold, optimising WADD is pessimistic.
lation
With the delay criterion base on CADD (Pollak formulation), algorithms based on the SHIRYAEV-
ROBERTS statistic are asymptotically within a constant of the best possible performance (Pollak
1985: Tartakovsky et al. (012).
state of the art methods LLai 1998) are modified versions of the CUSUM algorithm that converge asymptotically to a lower bound of CADD (and thus a lower bound to WADD).
In the non 1.i.d.
Bayesian formulation: The SHIRYAEV algorithm (Shiryaev 1963) is asymptotically optimal in the i..d. case. This result is extended to the non i..dd case under Hypothesis (Tartakovsky & Veeravalli 2005
A.1 ALGORITHMS
In this section, we formally introduce the algorithms used to solve the change point problems under known parameters. A common trait of these algorithms is the computation of statistic 5% and the definition of a cutting threshold B The stopping time Vo is the first time the statistic exceeds the threshold. The value Ba is chosen such that PFA (respectively FAR) of the associated stopping time does not exceed the level a. the case the BAYESIAN formulation, the threshold is simplified into B,
The SHIRYAEV Algorithm: The general formulation of the statistic 5%o.0, is the likelihood ratio of the test of Ho x < n versus H1 Á given the observations Xign- In the general case, with prior (( = k) = Tg, this statistic writes as:
S% Enso Th II=I Ino (X++1 X²) II So (Xe+1
(12)
Σt Th II=_ for (Xi+1
In the case geometric prior with parameter p. the statistic is simplified into:
5%..6 (--)) Σi= - -) II> (000, 01) where L, 01) = Jop (Xe+1l77
fa, (X")
The statistic Sh0.0. can be computed recursively under this simplification:
So. 0 and Sn+
10000.01 L (0o. 01)
1-p
The SHIRYAEY-ROBER Algorithm: The statistic to be computed in this case can be seen as an extension of the one in the SHIRYAEV algorithm when p 0. The recursive formulation is indeed:
Sfa.f and 8 = (1+ + 0, ) 1001 01) n+1
The CUSUM Algorithm: The relevant statistic is defined as: Sho.0r maxisn and can be computed recursively by:
So 61 0 and Sto.0h (S + +log(Ln+)))+
B R-QUICK CONVERGENCE HYPOTHESIS
Hypothesis] I is not restrictive, and r-quick convergence conditions previously used estab- lish the asymptotic optimality sequential hypothesis tests for general statistical models (Draglia
al. 1999 Lai 1976. 1981.
11

---

Under review as a conference paper at ICLR 2021
signal time
KL divergence between estimated parameters
30
0.12
annealing wi arneatin
0.10
20
15
0.04
0.5
0.02
0.0
Mignal
change point
Lorden stapping time
Shiryaev stopping time
optimal CaSum statittc
10
optimal shiryaev statistic
Cusum statistic wio anneslng
shirynev statabic wis anneeling
CuSum statistic annealing
30
shiryeev statitic wi annealing
307
3074
10'
250
500
750
1000
1250
3500
1750
2000
250
500
750
1000
1250
1500
3750
2000
Figure 3: Annealing the optimisation of do
Using the law of large numbers, this hypothesis is satisfied for g Ex,=Je, Ser (X.) case. In the (ergodic) Markovian case, the convergence is achieved for irreducible Markov chains due to their ergodicity.
Sor (X.)
in the i.i.d.
However, the speed of convergence of Equation 4 depends on the speed of convergence to the stationary distribution of the Markov chain. Even though for any >> construction of Markov chains that satisfy assumption is possible (Draglia et al. 1999), providing a guarantee of this speed a trivial question (Hairer 2010).
C ALGORITHMIC ANALYSIS
C.I IMPACT ANALYSIS (ANNEALING AND PENALISATION)
In order to justify experimentally the use of annealing and penalisation to solve the issues highlighted with Lemma simulate simple examples where the phenomena amplified their extreme.
Annealing: We consider a one dimensional signal. The KI. divergence between the pre and post change distribution 0.06. As discussed the paper, the issue that after the change point we start using observations from the post change distribution to learn the pre change one. This leads to 0f and 0 converging the post change parameter 0f In fact, without the annealing procedure, the KL divergence DKL ( fe; (the blue curve, in the top right subplot in Figure 3) ends up collapsing to 0. This has the problematic consequence of slowing down the statistics. In fact, both the SHIRYAEV and the CUSUM statistics (the blue curves in the lower subplots of Figure start adjacent to the optimal statistic (in red) and slowly degrade in quality. On the other hand, implementing the annealing procedure -a described in the paper with step size 0.01- solves this issue. The KL divergence (green curve) hovers around the true value and the computed statistics are almost within a constant of the optimal one.
Penalising: We consider in this case one dimensional signal with a KL divergence of 2. The problem analysing in this setting is the exclusive use of pre change observations when learning the parameters before the change point. The optimal log- likelihhood ratio (LLR) before the change point is -2 (the red curve in the top right subplot of Figure 4 while the learned (in blue) is
12

---

Under review as a conference paper at ICLR 2021
signall
Log over
Sgral
0.6
change point
00
optimal LLA evaluated LLR penalised LLR 013
3000
Shiryaev stopping
stopping
1050
20.0
optimal shiryavv statisiic
opomal CuSum statistcc
eveluated sheryerv statisii
evaluated Cobum statabic
309
penalised shirysev statisticc
pensiised CuGum statistic
12.5
30
10.0
107
25
10
00
150
200
Figure 4: Penalising the Log Likelihood Ratio
around O. This is due to Of and 0f converging to the pre change parameter 07. This over-estimation of the LLR leads to higher estimate of the SHIRYAEV statistic. In the lower left subplot of Figure we have an increase of 100 fold compared to the optimal value. Penalising the LLR, using a coefficient 0.01, solves this issue without being detrimental the post change performance. In fact the penalised LLR (the green curve) is strictly negative before the change point and has a similar values to the optimal ones afterwards. The associated SHIRYAEV statistic (the green curve) is less prone to detect false positives as it has the same behaviour as the optimal one. This safety break (penalisation) comes with slight drawback for higher cutting thresholds penalising component. Interestingly, the CUSUM statistic does not have the same behaviour in this example. This explained with the nature of the LORDEN formulation. As minimises a pessimistic evaluation of the delay (WADD), the impact of LLR of 0 is less visible. However, on average, the same phenomena occurs. This will be observed in the ablation analysis, where on average, there was no notable differences between the different formulations.
induces additional delay due the
C.2 ABLATION ANALYSIS (ANNRALING AND PENALISATION)
Since the algorithm integrates different ideas to mitigate the issues discussed in the paper, an ablation
study is conducted to understand their contribution. We simulate the case where X' = 10 θ = 10 and (# Φo) are 5-layer deep, 32-neurons wide neural network. The penalisation coefficient is fixed to 0.01 and the annealing step is fixed to 0.02. In Figure the regretted detection delay is evaluated using 500 simulations. We consider mid-ground complexity case, with a KL divergence of 1.5, which is more realistic scenario in real life situations.
We provide the regret with respect to both the optimal performance under known parameters for both the BAYESIAN setting (SHIRYAEV statistic the left) and the MIN-MAX setting (CUSUM statistic on the right). We split the analysis of the curves to three scenarios: The low, the mid and the high cutting threshold cases. They correspond respectively categories of risk inclinations levels: the high, the mid and the low.
The high risk inclination: In the presented case, this correspond to cutting threshold B smaller than 20 in the shiryaev algorithm and than 50 in the CuSUM algorithm. This can associated to household applications and relatively simple settings with high reaction time. In this case, the
13

---

Under review as a conference paper at ICLR 2021
simplest version of the algorithm is sufficient to achieve relatively small regret values. In fact, the green curve (associated to the configuration without annealing) presents a relatively low regret with respect to the optimal delay.
The low risk inclination: In the presented case, this correspond to B higher than 1000 in the shiryaev algorithm and than 100 in the cusum algorithm. This can be associated to critical applications where precision outweighs the benefice of speed such as energy production. In this case, configurations without annealing (presented in green here) have poor performance. The best configuration is to perform annealing but without penalisation of the log likelihood.
The intermediate risk inclination: This coincides with the remaining spectrum of cases. For example, when the application is critical but requires high reaction time, or when the application has no reaction time constraints but doesn't 't require extreme safety measures. In this setting, we observe that the best performance require some amount of penalisation of the log likelihood. The choice of the coefficient should be guided by the KL divergence between the pre and post change distributions, with 0 when the change is subtle (small KL).
Regreter detechin dely therpee stattstic
Regreted detection
Cusim statishi
x-3 E3
0.31 persiletton
botten
40
30
20
10"
10"
3371
12t4
1000
100
129
101*
15
330
322
150
(a) (fggffglfo;) 1.5
Figure 5: Ablation analysis of the regret detection delay as a function of the cutting threshold
C.3 DIVERGENCE MEASURES BASED ALGORITHMIC VARIANT
In order to solve the QCD problem under unknown parameters, we propose in this paper to approxi- mate the log-likelihood ratio L; efficiently. We achieved this by optimising a surrogate of the KL divergence between the estimated parameters (0f, 6.) and the true parameters (07. BT). Algorithm | devises theoretically grounded weighting technique that approximates expectations under pre/post change distributions. For this reason, other divergence measure based loss functions can be used In particular, consider the following loss functions:
instead of the proposed ones in Equation [1]
CB (1 G1.g) = Eter P(T < t|T ~ ffo.01 )g( fax Joo S0j
(X,)
CT, 01,9) Eter P(r > t|r 1 8s ) Jng
(X++1l
For & E {0, 1}. the loss function (I, 9o G1.g) approximates Ex [9[ faz )] Under the assumptions Joo
that g is an increasing function with g(1) = and h(z)) x-g(x) is convex, LB becomes a proxy of the h-divergence measure Dr. (fo (lfes) (respectively D,, (Fez fl ) for LT). This formulation is coherent with the QCD objective as it minimises L, under the pre-change distribution and maximises it under the post change distribution and we can use it as a valid change point detection algorithm. The obtained parameters (0), 07) are the furthest apart with respect to the associated h-divergence. The KL divergence (associated with gxx) log(z)) is natural fit for setting as it simultancously ensures that the evaluated parameters converge to 0t).
We keep using the same hyper-parameter from the ablation analysis in order to asses the ADD of the TWR algorithm using different divergence measures. The experimental results are reported in Figure
6 In addition to the Ka-based version (dark blue curve), we consider the case where g(x) /2 1 (purple curve) and the case where g(Ø) = (x 1). log(z) (cyan curve). We also provide the adaptive (yellow) and GLR (green) average detection delay as a baseline.
14

---

Under review as a conference paper at ICLR 2021
The KL-divergence based approach provides comparable ADD to the GLR, outperforming both the adaptive algorithm and the other variant of the TWR.
Regreted detectton ay using shiryaev stalistic
Regreted delection delay using Cusum statistic
00
(sgrt)
20
20
18
10
3014
1003
20
300
(a) (og (o;;) =
Figure 6: Regretted average detection delay using different divergence measures
D PROOFS OF TECHNICAL RESULTS
Proof of Lemma 1: We start by observing the following:
{
fo(0,0:) En log( for )} Eg
log( f0b } fo
fog
f1 0) = Fs log(
fej
)]
fej ) E. log(
Top
Notice that both quantities Eo [log( fer )] and E1 [log( foj f0g
}] constants with respect to the param-
l0g
eter 6, and that:
Eo log fea Dxa (fo) 10
Fy log )]
DKa (o)
where DeL. the Kullback-Leibler divergence in the i.i.d case and Kullback-Leibler divergence rate in the Markov chains case, i.e.
DKI(foolfot) - { S. for (x) log( fea
(x)
Fo,
Sr [o(x)) J, fo, (u|z) log( for (yllz)
When well defined, D l.f,) is strictly positive except when far for- This allows us to conclude that:
arg ming fu(O, 01) arg ming DkL(Jo; (so) 05 arg maxx fi (fo, 0) arg max, DxI. (Jo (s) 0j
This concludes the proof of the Lemma.
Proof of Lemma 2: We denote no the initial distribution according to which Xo is sampled and pa the distribution of X,. We re-write the functions f as:
01) Ele
Ee P(ieA A Eo, [log[
P(ecA|p.=m)
f0
(XIX,)]
Feo
(1.0.01)= Ehe
Pits Alp. Er, [log
(X XX,]
E. P(i> Ues =n)
Fap
where Ex, taken with respect to (Xp, X) It's important notice for what follows that P(t X V/ n) (respectively P(l > Alva = n)) is
(Xx)) (Joz (XIX,) Soz (XIx))))))))))
15

---

Under review as a conference paper at ICLR 2021
decreasing (increasing) with respect to t. We also highlight that for any finite set I, have the following:
ElEr Σi P(icApp=R)
P(ecA|PEER)
n-22-00 0
Eler Ei P(t>A)
P((>A|/o.
n.32 2,22-200
Consider the case where = co. As X2 is irreducible Markov chain, we have that
a1T well --
where ||-|/rv is the total variation norm. This means that for any small value > 0, there exist T > 0 such that:
A T | Hellav Sc
Thus, the observation X, are bounded, we have for any continuous function f. there exist T, such that:
2 T, [[x,,((X]X,]] (x[S(X|X,,) S
This implies that when À = do then fo and f converges to fo. In fact for any there exist N and T3 such that for all n N:
Vt2 2 T2
ELST. E P(isA|u.
P(t>A/k.n)) S
ELST. Plec Ms =n)
V/2 2 72
Se
P(icAlu.=M (f - [x x,)]l Se
Vt2 2 T.
The case where À is finite can be deduced by considering the sequence X1>A- All the observation sampled according to Sey, and thus 1ō and SP converges to f1.
This result is also valid for fl fact, as P(t Alva = n) is increasing with respect to f, then for any fixed horizon H we have:
P(t A/2a n1
100000 0.
KC EL2 P(i Ava n)
As this remains true for H Te, we obtain that f" converges to f1.
For given integer n., if 12 = À + n, the convergence of fo to fo is achieved as À + co. In order establish this result, need prove that E En P(i< A(v,)
P(t<A|pe))
is decreasing with respect A.
This is consequence of (t Alva)) being decreasing with respect In fact:
P (1 (Pa) D DEX P() Alva) nl((> Alva) t= P < Alva) Z EE P(A < Alva) = AP(A < AlPa)
as consequence the following inequality holds:
42 P(I < Xla))
$ 1000
2 P(i Alva)
As such, for any e > 0, there exists An > such that:
AA An
E
lo P(eeAla)) Se
En P(iccA(Vo)
AV > T.
PlecAles Σ
PlisAlre)) Se [f Eoof(x|Xx))] Sc
AA T.
Proof of Lemma 3: We have l converges
A + xo (respectively S converges fi as t oo). Given that 07 minimises fo (respectively 0 minimises fi). then 0g and of satisfy the following:
0).
as
0 and 0 0 ト+ +
0
As such, we obtain the following result:
a.5 L
and
L
as
+00
16

---

Under review as a conference paper at ICLR 2021
On the other hand we have the following:
limx 20 Ex [ X 11g.
[ -DK.L(fo
lim Ex [ = E x,_ Xe
[ +Dx.(ffo;lfoo) >0
This concludes the proof of the lemma.
E ADDITIONAL EXPERIMENTAL RESULTS
E. HYPER-PARAMETE PARAMETER SELECTION
The algorithm we designed requires the selection few hyper- syper-parameters order run properly. In this section we address the issue of tuning them.
The first set parameters are for optimisation purpose, and thus we advise selecting them according to the complexity of the probability distribution family {fo, 0 E θ). In all the experimental settings we used a batch size of 32, a number of epoch equal to 25 and a gradient step size 0.001. The initial task parameters 8 and 0 are chosen randomly unless stated otherwise.
As for the cutting threshold, the penalisation and the anncaling coefficients, they depend on the KL divergence between the pre- and post- change distribution (thus the task sampling distribution F) and on the mixing times these distribution. Fine tuning using grid search the most efficient way to identify suitable candidates.
From our experimental inquiries, we advise low penalisation coefficient (e.g. c = 0.001) unless the threshold B, is smaller than 100 for the SHIRYAEV statistic and smaller than 10 for the CUSUM statistic. The annealing parameter depends on the mixing time of the Markov chain. In fact e reflects to what extent we keep learning the pre-change parameter once it's similar to the post-change one. In practice we found out that a small coefficient (e.g. = 0.01) is advised when the observations converge slowly the stationary distribution. On the other hand, when convergence occurs few observations, a higher coefficient is safer choice.
E.2 COPYCAT AGENT PROBLEM: COMPLEMENTARY RESULTS
In this section we further the analysis of the copycat agent problem. The Fetch set of environments provides a good mix of complexity and interpretabilityy The ability of the TWR algorithm to detect changes and solve the copycat agent problem in these environments is proof of it's robustness.
SHARED BEHAVIOURS
When different tasks are associated to a shared behavior, it becomes difficult evaluate the param- eter 0% This is true for the push and the PickandPlace environments. In both cases, the goal is to control robotic hand (through its joints' movements) in order interact with an object until it reaches final position (cither push it there or pick it and then place it there).
The task space in these problems is the set possible final positions. No matter what the task is, the main agent is going to reach to the object. The observations associated to this intermediate process of reaching are probably going yield poor estimation of the final position. However as the agent start to interact with the object, it starts to become clear what task is being executed. For this reason, an artificial change is detected between the reaching behaviour and the interaction one when using the TWR algorithm. Even though this detection is unwanted (in the sense that there was no actual change of behavior) it allows to reduce the estimation error ||0 0,1|-
In this section, the experiment we run consists of performing three randomly sampled tasks, each over a window of 20 observations. We estimate the running task 02 using the TWR algorithm and maximum log-likelihood estimator (MLE) over both the last and 10 observations. We average the errors over 500 trajectories and report the results in Figure 7 In both environments estimating the task with the running pre-change parameter of the TWR algorithm outperforms MLE, The gap grows narrower however in the PickAndPlace setting as the shared behaviour last longer. This makes estimations more difficult.
17

---

Under review as a conference paper at ICLR 2021
Error the latent parameters estimation
Error of the latent parameters estimation
0.22
0250
0.89
0225
0375
0158
0125
0150
8388
Jost
0128
TWR
(a) Prediction error in the Push problem
(b) Prediction error in the Pick&&lacee problem
Figure 7: Performance analysis of the copyeat problem
We also notice that the first task estimation of TWR is better than the MLE estimator despite the fact that all the observations are generated with a single parameter. This strange result is due to the detection of an artificial change after the "shared" behaviour. optimising only observations that are clearly correlated to a particular task, leads to better estimations. As for the gap in the first estimation, this is explained by built-in agnostic behaviour in the TWR algorithm. When the number of observation is less than the ADD the SHIRYAEV algorithm, the pre-change weight
term P(T t/T fn 1 of C3 is extremely small, and thus the estimation remains close to the initialisation. In addition, the tow target functions L and L are adversarial as they kind of optimise the opposite each other. This leads to smaller gradient updates. On the other hand, MLE tend to commit to particular estimate using observations from the 'shared' behaviour phase. This leads generally to a heavily over- fittini estimate.
The agnostic behaviour is more pronounced in Figure 7b (PickAndPlace) the robotic hand picks the object exactly the same way no mater what task is being solved. As long as there is few evidence of distinctive behaviour occurring, the TWR estimate remains close to the initialisation. In fact the tasks here are positions and the error is the distance between the true and predicted coordinates. In the PickAndPlace scenario, the target is randomly sampled in cube of edge length 0.3, in the Push scenario, it is sampled in square with the same edge length. with random initialisation we get an average error of 0.1 x /3 and 0.1 X 2 respectively with a random initialisation. This coincide with the TWR error (blue curve) in both environments given few observations proving that the learned task remained close to the initialisation.
In Figure 7a the improvement due the artificial detection of change between the shared behaviour and the task specific one is marked around the 5th observation. In fact once the robotic hand starts pushing the object in a particular way, the estimation error starts to decay faster.
PERFORMANCE COST OF LEARNING THE POLICY
Estimating the running task Or in the copycat problem with either the TWR algorithm or the MLE requires access to the probability distribution тÿ. However, in real life situations, can only learn an approximation of this distribution through historical observations.
In this section we evaluate experimentally the impact of using inverse reinforcement learning to construct an approximate policy it and using it as a substitute for тØ. We consider the Reach environment where the task is move the robotic hand a particular position. The main agent execute 5 different tasks, sampled randomly, each over a window of 20 time steps. We evaluate the running task with TWR and MI_E using the last 5 observations using the actual policy TØ and the learned one ite We average the estimation eиror over 100 simulations and we provide the experimental results in Figure g The approximate policy is constructed using the GAIL algorithm and a data-set of task labelled observations generated using xğ.
As established before, the TWR estimates using the true policy (in blue) outperform MLE based approaches. This trends remains true average when using ft. However, the true policy based MLE (in green) converges to a better estimation in the last observations before the change point, while the GAIL based TWR estimate (in red) well the GAIL based MLE (in orange) seem to be unable
18

---

Under review as a conference paper at ICLR 2021
Error the latent parameters estimation
0.30
TWR
TWR (GAIL policy)
0.5
last MLE (GAIL policy)
actual change point
0.20
0.10
0.05
0.00
20
40
60
80
100
Figure 8: Impact of learning the policy
to improve. This is the cost of using policy approximation. The additional error is built in due to estimation error of the learned policy.
E.3 COMPLEMENTARY PERFORMANCE ANALYSIS
In this section we provide complementary experimental results to the ones introduced in the paper. We keep using the same hyper-parameters (i.e. X' R100 θ R and (øps da) are 5-layer deep, 32-neurons wide neural network).
SINGLE CHANGE POINT PERFORMANCE
In Figure we provide the average regret overs 500 simulations in both the BAYESIAN (on the left) and the MIN-MAX (on the right) settings. Each simulated trajectory 1000 observation long with a change point at the 500th observation. We use the full pipeline of our algorithm with penalisation coefficient (c 0.01), and we allow the adaptive algorithm to exploit 10% of the pre change observations. Our algorithm (the blue curve) achieves comparable performance to the GLR statistic (without requiring intensive computational resources) and achieves better and more stable results compared to the adaptive algorithm (without requiring domain knowledge).
experiments and for all considered change detection algorithms, we observe a spike and a high variance of the average detection delay for low cutting threshold. This is direct consequence of the definition of Ba, In fact a low cutting threshold implies a high tolerance the type error. This implies that the optimal detection time is no longer reliable estimate.
MULTIPLE CHANGE POINTS PERFORMANCE
We reconsider in this section the multiple change points problem introduced early on in the paper. If the change points are sufficiently separated (i.e. f4 4--1 is big enough), they can be seen as independent single change point problems. However there no good reason believe that this is the case of real life applications. For this reason, the detection delay of the first change point t will probably reduce the accuracy at which we estimate the parameter 01, this in turn will affect the accuracy of estimating the log-likelihooe for the next change point /2. This behaviour will keep on snowballing until we reach breaking point which we will miss change point. Some attempts to deal with this issue have been made in the past to improve the convergence rate of the GLR algorithm order to reduce the impact of this problem (Ross) 2014). These approaches remain computationally extensive and thus not considered in comparison setting.
We provide however an analysis of the impact of the number of pre change observations on the average detection delay in the single change point setting. We keep using the same hyper-papne parameters where R 10 e R 10 and (d,,: Φx) are 5-layer deep, 32-neurons wide neural network. We parameters achieving KI. divergence of 1.5 between the pre and post change parameters, and
19

---

Under review as a conference paper at ICLR 2021
evaluate the average detection delay over 500 simulations where À 250. By varying À we simulate different multiple change point scenarios where the accumulated delay exhausts most of the available observations. The first thing to notice is that our algorithms (in the blue curve) has similar average detection delay to the GLR (green curve) in all presented cases. When we have sufficient observations (A = 250), all algorithms will have reasonable performances compared the optimal delay. However, for smaller horizon, the adaptive algorithm (the orange curve) is predicting change way before the optimal algorithm. This explained with the bad estimation of the pre change distribution due to reduced sample size. In fact for cutting threshold up to 1025, the adaptive algorithm predicting the change point before it happens. In addition, we observe that our approach varies less than the adaptive one as it's less prone to fit statistical fluctuations.
We provide an analysis of the impact of the number of pre change observations on the average detection delay in both the BAYESTAN (on the left) and the MIN-MAX (on the right) settings. We use parameters achieving a KI. divergence of 1.5 between the pre and post change parameters, and evaluate the average detection delay over 500 simulations where to + 250. By varying À simulate different multiple change point scenarios where the accumulated delay exhausts most the available observations. There is no notable variation in the algorithms behaviour when using either the SHIRYAEV or the CUSUM statistic. As for the impact of the number of available pre-change observation before the change point (A), the results presented in Figure [Qjllustateeeee how algorithm less prone than adaptive procedures to over fit the observation when their number is limited. In fact the blue curve (our algorithm) is closer than the adaptive one (orange curve) to the GLR (green curve) performances. All approaches end up having a constant regret with respect to the optimal detection given enough observations (A 250).
Regreted detection delay using shiryaev statistic
Regreted detection delay Cusum statistic
stspthv
unkmoun adistivc
unisown porams
GLR
QUR
20
20
3025
30a
1013
3001
1021
1017
10t0
10t0
30a0
(a) Dra(For (oo)
Regreted delay using shiryaev
Regreted delay using
300
100
QLA
30
80
10a
10
1014
10
10t0
3044
300
120
(b) Dra(fo foz)
Figure 9; Performance analysis of the regretted detection delay as function of the cutting threshold
20

---

Under review as a conference paper at ICLR 2021
Avwrayy delection delyy using slaryams viatistic
Aawrage deleciam dheyy shing Cueem statiaii:
ur pERTO
FM
180
60
27-
10
10'
32"1
32
10'
100
10"
12
10a
(a) À 20
dolyy using shiryovv
Average deay Cuzum statizic
adaptes en
sdagP
130
70
(b) À 50
Average dctoction delay using dhiryovv statiati
Average dotection delay usine Cusum statstic
140
drloeee 18316
147
GL2
GR
189
27
10-1
122
2,21
2221
1377
1079
339
10
(c) A = 100
Average detection dely using shiraev statietc
Average detectio delyy using Cusum statishir
olestee
125
300
135
150
175
(d) À 250
Figure 10: Performance analysis of the average detection delay as function of the cutting threshold
21

---

Under review as a conference paper at ICLR 2021
Regreted detection delay using shirywev statistic
Regreted delay using Casum statistic
20.
30.0
17.3
17.
10.0
75
15
5.-
TWR (Nl nominal behaviburt TWR (sf nominal behvniizur) adtpttivn norn vall bethaiiuur)
5.0
TWR nominal behlviour)
TWR nominaal berve beneriuur adaptrie fal nominal behasdout)
1004
10t4
10h0
1pt0
20ta
22
100
(a) DRL 1so7
Regreted eted detection delay using shiryaev statistic
Regreted detection delay using
100
100
TWR twt behevizur)
(elt behanitart ataptive
behavizuu))
CLR
20
380
120
(b) Dra(fo; [oo)= =3
Figure 11: Performance analysis of the regretted detection delay given nominal behaviour
PERFORMANCE GIVEN A NOMINAL BEHAVIOUR
In this section, we keep using the same hyper-parameter from the previous experiments. However we consider the setting where we have access to the pre-change parameter (which correspond to nominal behaviour). Beside the ADD of the GLR and TWR statistics (computed with prior knowledge the pre-change parameter), we computed the ADD the adaptive and TWR statistics using the prior knowledge of the true pre-change distribution.
The first notable thing is that the adaptive algorithm performances (yellow curve) did not improve by much compared the case where the parameter were estimated using 10% of the available observations. fact TWR statistics outperforms it even with no prior knowledge the nominal behaviour (dark blue curve). The second notable observation, that given the pre-change parameter, TWR statistic performance (light blue) is within a constant of the GLR statistic. These observations confirm again that using the asymptotic behaviour of the Shriyaev detection delay a very powerful approximation
22


Reviews:
[{"review_id": "q4BTjZuT-3l", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*****  Paper's Summary  *****\n\nThis paper considers the quickest change detection (QCD) problem where pre-change and post-change distributions are unknown. For such problems, the authors proposed approximate algorithms in MIN-MAX and Bayesian settings. The algorithms run in O(1) and have near-optimal performances. The performance of proposed algorithms is verified using synthetic data and a reinforcement learning environment.\n\n\n***** Paper's Strengths *****\n\nThe proposed algorithms are the approximate methods that have a near-optimal performance for QCD problems with unknown pre-change and post-change distributions. \n\nThe proposed algorithms are scalable and having low detection delays. Further, these algorithms work for a more general class of problems as they do not require restrictive conditions like IID samples, specific distributions, etc. on the problems.\n\nThe performance of proposed algorithms is better than existing algorithms. \n\n\n***** Paper's Weaknesses ***** \n\nThe proposed algorithms solve an optimization problem (depending on the setting) for minimizing the delay in change point detection. As no deep learning models (or even a variant) is used to solve the change point detection problem considered in the paper, this paper seems to be outside of the ICLR scope.\n\nI find it very difficult to understand the paper in even 2-3 read. The authors need to improve overall writing quality so that it becomes easier to read and understand. \n\n\n***** Comments ***** \n\nSome notations are not defined upfront e.g., Line 2 on Page 3: $S_n^{\\theta_0, \\theta_1}$ and $B_\\alpha$. \n\n\n*****  Questions for the Authors  *****\n\nPlease comments on how your paper fits the ICLR scope. \n\n\n*****   Post Rebuttal  *****\n\nThank you for your clarifications! After reading the rebuttal and comments of other reviewers, I am increasing my score.  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "i0U03TKMV3", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the quickest change detection for Markovian data, when both the parameters of pre- and post-change distributions are unknown. The main contribution is a scalable algorithm that sequentially estimates the unknown parameters and plug-in to classical detection schemes to get the stopping rule. A notable feature is that this is a joint estimation and detection framework. And the authors incorporate several tools, like SGD, annealing, penalization, into the detection task, which turns out to have good performance compared with existing benchmarks. \n\nOverall, this paper is clearly-written and well-organized, and the numerical examples support the claims made in the paper. \n\nMinor comments: \n1. Usually in classical change-point detection literature, people assume the pre-change distribution is known since it can be estimated from historical (nominal) data, and the framework proposed in this paper can obviously be applied in such a setting as well. Therefore, I think it might be interesting to add one comparison in such setting (i.e., only post-change parameters is unknown and need to estimated). In such a case, the GLR and adaptive methods do not need to learn theta_0 offline and we can have a fair comparison of the performance of learning post-change parameters and also the detection delay. \n\n2. In Appendix A.1, the introduction to SHIRYAEV Algorithm, it seems that there is a missing \\rho in the denominator of the statistics S. The reason is that only under this \\rho-scaled version of likelihood-ratio can the recursion in A.1 holds. \n\n--------- After rebuttal ---------\nThanks to the authors for the response and updated paper. I keep my original score and recommend acceptance for this paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "M-3FimTEc6", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The author(s) propose a quickest change detection technique under known parameter scenario. They use a Markovian dynamics to generate the pre and post change-point distributions and use a Shirayev test-statistic based on the asymptotic behavior of the optimal delay under know parameters. The proposed methodology is validated on synthetic data and a multitask reinforcement learning example. There are several issues which restricts the paper to reach an optimal level. These are highlighted below\n\n-Heavy dependence on Tartakovsky and Veeravalli (2005) results with known parameters. The contribution in the current paper seems a bit incremental.\n\n-The algorithm 1 looks promising however some of the hyper parameter choices such as c, $B_\\alpha$, $\\epsilon$ and $N_e$ are not clear.\n\n-For a practitioner which one is better to choose- Shirayev test-statistic or Cusum?\n\n-It was not quite clear to me why does one need both annealing and penalisation? I thought adjusting underestimation/overestimation of ${L_t}^*$ will be sufficient as behavior of pre-changepoint will complement the behavior post change-point.\n\n-Does other choice of entropy based loss functions matter instead of KL divergence or KL divergence is the most natural choice here?\n\n-", "extra_scores": {}, "extra_text": {}}, {"review_id": "2R6ORWKTMC", "reviewer": "AnonReviewer1", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies the change point detection problem. The classical studies in change detection problems are based on the known prior and posterior parameters, i.e., knowing the distribution (parameters) before and after the change points. Recently, people are extending the results to the case where the prior parameter is known and the posterior parameter is unknown (anomaly detection) or with some sampling cost constraints (data-efficient change detection). However, this work proposes an algorithm that generalizes the CUSUM approach to the case where the parameters are unknown. The idea is very interesting and I believe the impact of the algorithm could be of significance given its potential in real-world applications. Besides, I have the following comments.\n\n1) The paper title is for multi-rask problems. However, it seems to me that the proposed algorithm is very general for change detection problem. Except the one subsection in the experiments, I didn't see much connection to multi-task problems.\n\n2) The theoretical results are not very strong. There is no Theorem one can claim for the performance of the proposed algorithm. As the algorithm is an approximation to some optimal approach, one may provide a result in the form of competitive ratio or convergence rate. However, Lemma 3 is only some asymptotic behavior of the loglikelihood.\n\n3) How should one choose the hyperparameters like c and epsilon? Are the results in section 5 tuned by grid search and presented the best one?\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper treats a relevant and challenging problem in sequential learning scenarios -- how to detect distributional change over time when the pre- and post-change distributions are not known up to certainty. All reviewers more or less acknowledge that the paper presents a new approach towards solving this inference problem, where the high level idea is to approximately learn the pre- and post-change distribution parameters online using gradient descent and then apply well-known tests for change detection (e.g., the Shiryaev or CUSUM rules) with these assumed to be the pre- and post-change parameters.

However, beyond the concerns expressed by the reviewers, my finding after going through the manuscript myself is that the presentation of the paper's results leaves a lot to be desired in terms of clarity of exposition, comprehensiveness of performance benchmarking and comparison to existing approaches. Despite some of the reviwers' scores being revised upwards, the overall evaluation of the paper according to me is not adequate to merit acceptance, as per the concerns listed below. 

1. There are two settings assumed in the paper (beginning of Sec. 2): (a) a completely Bayesian one, with the pre- and post-change distributional parameters drawn from a prior \cal{F} and the change time lambda drawn from a prior pi, and (b) a minmax one, where everything is the same as in (a) except that there is no prior over the change time lambda. However, it is not at all clear, in the algorithm design of the paper, where the prior \cal{F} over the distributions is used in computing (or approximating) conditional probabilities such as P[lambda | v_alpha = n].

2. There seem to be meaningless (or ill-defined) expressions in the paper's crucial portion motivating the algorithm design, such as P(X_t ~ f_{theta_0} | v_alpha = n), P(X_t ~ f_{theta_1} | v_alpha = n). It is hard to understand what the event "X_t ~ f_{theta_0}" even means -- I find it impossible to relate it to a sample path property. This leads me to question the validity of the technical development in the paper.

3. Another undefined term is "r-quickly" in eq. (4); I had to dig through the classical work of Lai, and Tartakovsky-Veeravalli to get a formal definition for this term. This is not to be expected of a paper that attempts to develop a new change point detection procedure from scratch, especially to an audience (ICLR) that may largely be unfamiliar with classicalt change detection theory. 

4. There are several technical statements made without adequate formal proof, e.g., "Given the optimal stopping time \nu, it's possible to evaluate the posterior distribution of the change point P(lambda=t | v_alpha=n), which in turn is a good classifier of the pre and post change observation". What the precise meaning of the term "classifier" is, what its "goodness" is, and how exactly it is related to the posterior distribution of lambda given the value of v_alpha, is formally not spelt out for a paper that largely uses formal probability language to develop its main results.

5. While I understand that the final algorithm to detect the change involves several approximations and heuristics along the way, which may very well be intuitively appealing, I do not understand (even after repeated passes over the submission) several key aspects -- a concern also expressed by Reviewer 3. Why is it reasonable to assume that the conditional distribution of the change time lambda given the algorithm's stop time v_alpha would be logistic, and with the specific parameters mu and s given in the section "Distribution Approximation"? Moreover, it is hard to discern from the crucial Section 3.2 why the functions f_0^n, f_1^n should be useful in practice as proxies to the actual expected log likelihood ratios under the true parameters -- despite Lemma 2 showing that they converge to the true expectations (again, the sense in which this convergence occurs is omitted leading to imprecision in the statement), the rates as a function of n, t_2 may be slow. I agree in this regard with the same concern voiced by Reviewer 1, and do not see a satisfactory explanation to it in the paper's discussion.

6. Comparison to literature. Contrary to the general picture painted in the paper about the lack of sufficient investigation of the "unknown pre and post change parameter" case, there does seem to be a rigorous body of work existing in this line that is not discussed in the manuscript. For instance, "SEQUENTIAL CHANGE-POINT DETECTION WHEN THE PRE- AND POST-CHANGE PARAMETERS ARE UNKNOWN", Lai and Xing, 2009, and "A BAYESIAN APPROACH TO SEQUENTIAL SURVEILLANCE IN EXPONENTIAL FAMILIES", Lai-Liu-Xing, 2009, are both works that address this very setting and in a comprehensive manner with theoretical guarantees. What the current manuscript does, in the context of both these works, is highly unclear. Is it trying to suggest an approximate way of computing the natural posterior distribution of the change time lambda given all data up to now, using the proxy P(lambda | v_alpha = n), or using a completely different approach altogether, is not adequately discussed at all, which makes the motivating arguments for the algorithm vague.

7. Finally, but in no lesser measure, the Experimental Results section features a rather narrow set of (two) scenarios for which it presents numerics. For a paper that claims to demonstrate "experimental results (over a wide variety of settings)" [from the author response], this is quite telling as it renders the argument in favor of the paper's approach quite weak. Here again, for the first (synthetic) setting, I do not understand the relevance of the neural network adopted to fix the parameters of a Gaussian distribution. Moreover, the reported distributions of the "regretted detection delay" seem to be quite wide for all the approaches compared (unknown params, adaptive, GLR), precluding a reasonable comparison of their performance. The author(s) would do well to expand the scope of both synthetic and non-synthetic experiments to show the validity of their approach, and in each case carry out many more independent trials than just 500 for more accurate benchmarks.

I do note that more experimental results have been reported in the appendix, but I would presume that they have more value being in the main body after the algorithm design is explained in a more succinct and clearer manner. This can only come about by a significant rewriting and reorganizing of the paper, which I am confident the author(s) can carry out in order to make this into a much stronger submission. I wish the author(s) good luck on this, and hope to see the strengths of this new approach brought out in a more impactful manner in the next revision.

Decision: Reject