Drift Detection in Episodic Data: Detect When Your Agent Starts Faltering
Authors: Ido Greenberg
Shie Mannor
Venue:  (2021)
Keywords: Reinforcement learning reliability
Reinforcement learning stability
Drift detection
Degradation test
Bootstrapping

Abstract: Detection of deterioration of agent performance in dynamic environments is challenging due to the non-i.i.d nature of the observed performance. We consider an episodic framework, where the objective is to detect when an agent begins to falter. We devise a hypothesis testing procedure for non-i.i.d rewards, which is optimal under certain conditions. To apply the procedure sequentially in an online manner, we also suggest a novel Bootstrap mechanism for False Alarm Rate control (BFAR). We demonstrate our procedure in problems where the rewards are not independent, nor identically-distributed, nor normally-distributed. The statistical power of the new testing procedure is shown to outperform alternative tests - often by orders of magnitude - for a variety of environment modifications (which cause deterioration in agent performance). Our detection method is entirely external to the agent, and in particular does not require model-based learning. Furthermore, it can be applied to detect changes or drifts in any episodic signal.

Under review as a conference paper at ICLR 2021
DRIFT DETECTION IN EPISODIC DATA: DETECT WHEN YOUR AGENT STARTS FALTERING
Anonymous authors Paper under double-blind review
ABSTRACT
Detection of deterioration of agent performance in dynamic environments is chal- lenging due the non-i.i.d nature of the observed performance. We consider an episodic framework, where the objective is to detect when an agent begins to falter. We devise a hypothesis testing procedure for non-i.i.d rewards, which is optimal under certain conditions. To apply the procedure sequentially in an online man- ner, we also suggest a novel Bootstrap mechanism for False Alarm Rate control (BFAR). We demonstrate our procedure in problems where the rewards are not independent, nor identically- power of the new testing procedure is shown to outperform alternative tests often by orders of magnitude- for a variety of environment modifications (which cause deterioration in agent performance). Our detection method is entirely external to the agent, and in particular does not require model-based learning. Furthermore, it can be applied to detect changes drifts in any episodic signal.
nor normally-distributed The statistical
INTRODUCTION
Reinforcement learning (RL.) algorithms have recently demonstrated impressive success in a variety
of sequential decision-making problems (Badia af., 2020, Hessel et al. 2018). While most RL. works focus on the maximization of rewards under various conditions, key issue in real-world RL.
tasks is the safety and reliability the system Dbulac-Arnole et al. 2019 Chan et al. 2020), arising in both offline and online settings.
In offline settings, comparing the agent performance in different environments important for generalization (c.g., in sim-to-real and transfer lcarning). The comparison may indicate the difficulty of the problem or help to select the right learning algorithms. Uncertainty estimation, which could help to address this challenge, is currently considered hard problem in RL, in particular for model- free methods (Yu et al.) 2020).
In online settings, where fixed, already-trained agent runs continuously, its performance may be affected (gradually or abruptly) by changes in the controlled system or its surroundings, or when reaching new states beyond the ones explored during the training. Some works address the robust- ness of the agent to such changes (Lecarpentier & Rachelson 2019 Lee et al., 2020). However, noticing the changes may be equally important, as allows to fall back into manual control, send the agent to re-train, guide diagnosis, or even bring the agent to halt. This is particularly critical in real-world problems such as health care and autonomous driving (Zhao et al. 2019), where agents are required to be fixed and stable: interventions in the policy are often limited or forbidden (Mat-) sushima et al. 2020), but any performance degradation should be detected as soon as possible.
Many sequential statistical tests exist for detection of mean degradation in random process. How- ever, common methods (Pagel 1954 Lan 1994, Harel al. 2014) assume independent and iden- tically distributed (i.i.d) samples, while in RL the feedback from the environment is usually both highly correlated over consecutive time-steps, and varies over the life-time of the task (Korenkevych et al. 2019). This is demonstrated in Fig.
A possible solution is to apply statistical tests to large blocks of time-steps assumed to be i.i.d (Dit- Zler et al.) 2015). Since many RL applications consist of repeating episodes, such blocks-partition can be applied in a natural way (Colas et al. 2019). However, this approach requires complete episodes for change detection, while faster response is often required. Furthermore, naively ap-

---

Under review as a conference paper at ICLR 2021
plying statistical test the accumulated feedback (e.g.. sum of rewards) from complete episodes, ignores the dependencies within the episodes and may miss vital information, leading to highly sub-optimal tests.
In this work, we devise an optimal test for detection of degradation of the rewards in an episodic RL task (or in any other episodic signal), based the covariance structure within the episodes. Even in absence of the assumptions that guarantee its optimality, the test is still asymptotically superior to the common approach of comparing the mean (Colas et al. 2019). The test can detect changes and drifts in both the offline and the online settings defined above. In addition, for the online settings, we suggest a novel Bootstrap mechanism control the False Alarm Rate (BFAR) through adjustment of test thresholds in sequential tests of episodic signals. The suggested procedures rely on the ability to estimate the correlations within the episodes, e.g., through a "reference dataset" of episodes.
Since the test is applied directly to the rewards, is model-free in the following senses: the underly- ing process is not assumed be known, be Markov, or be observable at all (as opposed to other works, e.g.. [Banerjee et al. (2016), and we require no knowledge about the process or the running policy. Furthermore, as the rewards are simply referred to as episodic time-series, the test can be similarly applied to detect changes in any episodic signal.
We demonstrate the new procedures the environments of Pendulum (OpenAT), HalfCheetah and Humanoid (MuJoCo; Todorov et al. 2012). BFAR is shown to successfully control the false alarm rate. The Novariance-based degradation-tes detects degradation faster and more often than three alternative tests in certain cases by orders of magnitude.
Section 3 formulates the offline setup (individual tests) and the online setup (sequential tests). Sec- tion Soon@introon introduces the model of an episodic signal, and derives an optimal test for degradation in such a signal. Section 5 shows how to adjust the test for online settings and control the false alarm rate. Section describes the experiments, Section discusses related works and Section g summarizes.
To the best of our knowledge, we are the first to exploit the covariance between rewards in post- training phase test for changes in RL-based systems. The contributions of this paper are (i) new framework for model-free statistical tests on episodic (non-i.i.d) data with trusted reference- episodes; (ii) an optimal test (under certain conditions) for degradation in episodic data; and (iii) a novel bootstrap mechanism that controls the false alarm rate of sequential tests on episodic data.
PRELIMINARIES
Reinforcement learning and episodic framework: A Reinforcement Learning (RL) problem is usually modeled decision process, where a learning agent has to repeatedly make decisions that affect its future states and rewards. The process is often organized as finite sequence of time- steps (an episode) that repeats multiple times in different variants, e.g., with different initial states. Common examples are board and video games (Brockman et al. 2016), as well as more realistic problems such as repeating drives in autonomous driving tasks.
Once the agent is fixed (which is the case in the scope of this work), the rewards of the decision process essentially reduce to (decision-free) random process (X,)²_ which can be defined by its PDF (f(x)),, R" > [0, oc) ). {X,} usually depend on each other: even in the popular Markov Decision Process (Bellman 1957), where the dependence goes only single step back, long-term correlations may still carry information if the states are not observable by the agent.
Hypothesis tests: Consider a parametric probability function p(X describing a random pro- cess, and consider two different hypotheses Ho, H determining the value (simple hypothesis) or allowed values (complex hypothesis) of f. When designing a test to decide between the hypotheses, the basic metries for the test efficacy are its significance P(not reject Hol Ho) - a and its power Prreject Hol HA) B. A statistical hypothesis test with significance 1 and power , is said to be optimal if any test with high significance 1 â 2 1 has smaller power 3 < 3
The likelihood of the hypothesis H 0 E θ given data X is defined as L(H[X)= = suppge>P(X X (8). According to Ssyman-Pearson Lemma (Neyman et al. 1933), threshold-test on the likelihood ratio LR(Ho. H XX) = [(HnlX) A is optimal. In a threshold-test. the threshold is uniquely determined by the desired significance level a, though is often difficult to calculate given a.
2

---

Under review as a conference paper at ICLR 2021
In many practical applications, hypothesis test is repeatedly applied the data change or grow, procedure known as sequential test. the null hypothesis Hg is true, and any individual hypothesis test falsely rejects Ho with some probability a, then the probability that at least one of the multiple tests will reject Hg is og > o, termed family-wise type-I error (or false alarm rate when associated with frequency). See Appendix K for more details about hypothesis testing and sequential tests in particular.
Common approaches for sequential tests, such as CUSUM (Page) 1954 Ryan 201 and a-spending functions (Lan 1994 Pocock, 1977). usually require strong assumptions such as independence or normality, as further discussed in Appendix
PROBLEM SETUP
In this work, we consider two setups where detecting performance deterioration is important quential degradation--estt and individual degradation-tests. The individual tests, in addition to their importance in (offline) settings such as sim-to-real and transfer learning, are used in this work as building-blocks for the (online) sequential tests.
Both setups assume fixed agent that was previously trained, and aim detect whenever the agent performance begins to deteriorate, e.g., due to environment changes. The ability to notice such changes essential in many real-world problems, as explained in Section
Setup 1 (Individual degradation-test) We consider a fixed trained agent (policy must be fixed but is not necessarily optimal), whose rewards in an episodic environment (with episodes of length T)) were previously recorded for multiple episodes (the reference dataset). The agent runs in new environment for n time-steps (both n < T and n 2 T are valid). The goal is to decide whether the rewards in the new environment are smaller than the original environment not. If the new environment identical, the probability of a false alarm must not exceed (..
in Setup D we consider fixed trained agent with recorded reference data of multiple episodes. This time the agent keeps running in the same envi- ronment, and at a certain point in time its rewards begin to deteriorate, c.g., due to changes in the environment. The goal is to alert to the degradation soon as possible. As long the environment has not changed, the probability of false alarm must not exceed an during run of h episodes.
Setup (Sequential degradation-test).
Note that while in this work the setups focus on degradation, they can be easily modified to look for any change (as positive changes may also indicate the need for further training, for example).
OPTIMIZATION OF INDIVIDUAL DEGRADATION-EEST
To tackle the problem of Setup I we first define the properties of episodic signal and the general assumptions regarding its degradation.
Definition 4.1 (T-long episodic signal). Let n, T N. and write n KT + To (for non non-negative integers K, To with To < T). A sequence of real-valued random variables {X,)= is T T-long episodic signal, if its joint probability density function can be written as
f(x,) (I))
II K=O
( (FATH) (KT-))
14x112, (E (1)
(where an empty product defined as 1). We further denote Ho E((XI, XT) E TxT.
Cov((X1,..,,X,) X..
Note that the episodic signal consists of i.idd episodes. but is not assumed to be independent or identically-distriuuue within the episodes. For simplicity focus one-dimensional episodic signals, although a generalization to multidimensional signals is straight-forward (see Appendix G
In the analysis below assume that both μo and En are known. In practice, this can be achieved either through detailed domain knowledge, or by estimation from the recorded reference dataset of Setup assuming satisfies Eq. (T). The estimation errors decrease as (11 (1/V/N) with the number N of reference episodes, and are distributed according the Central Limit Theorem (for means)
3

---

Under review as a conference paper at ICLR 2021
[HalfCheetah] Reference episodes
10
t1=0
t1=
Var[reward)
15
reward
Corr(C,
975
0.4
05
0.
129
177
22
22
39
67
72
77
87%
603
(b)
(a)
(c)
Figure 1: Parameters of am episodic signal of the rewards in HalfCheetah environment, estimated over 10000 episodes of T 1000 time-steps: (a) distribution of rewards per time-step: (b) variance per time-step; (c) correlation(1,, f2) to t.. The estimations were done in resolution of 25 time-step,, i.e., every episode was split 40 intervals of consecutive rewards, each sample the average over an interval.
and Wishart distribution (K V. Mardia & Bibby 1979) (for covariance). While in this work we up to N 10000 reference episodes, Appendix E shows that N 300 reference episodes sufficient for reasonable results in HalfCheetah, for example. Note that correlations estimation has been already discussed in several other RL works (Alt et al. all
Fig. [ demonstrates the estimation of mean and covariance parameters for a trained agent in the environment of HalfCheetah, from reference dataset of N = 10000 episodes. This also demon- strates the non-trivial correlations structure in the environment. According to Fig. Tb the variance in the rewards varies and does not seem reach stationarity within the scope of episode. Fig. [c shows the autocorrelation function ACF - t1) = corr(t1, f2) for different reference times t1. It evident that the correlations last for hundreds of time-steps, and depend on the time t rather than merely on the time-differene enough for the actual correlations structure.
f11 This means that the autocorrelation function is not expressive
Once the per-episode parameters po E RT, Ep E R are known, the expectations and covariance matrix the whole signal μ E T E E Raxx can derived directly: l consists of periodic repetitions of μo. and Σ consists of copies of Eg as T T blocks along its diagonal. For both parameters, the last repetition is cropped if n is not an integer multiplication of T'. In other words, by taking advantage of the episodic setup, can treat the temporal univariate non-i.id signal multivariate signal with casily-measurey mean and covariance even the signal is measured the middle of episode.
The degradation in the signal X {X,}r= }r= is defined through the difference between two hypothe- ses. The null hypothesis Ho states that X is a T-llog episodic signal with expectations No Rº and invertible covariance matrix Σg E RT Our first alternative hypothesis - uniform degradation states that X is T-long episodic signal with the same covariance E, but smaller expectations:
Be 2 6D, v1 < t < T' : (μ)) (Ho); e. Note that this hypothesis is complex (e 2 60), where 6o can be tuned according the minimal degradation magnitude of interest, In fact, Theorem 4.1 shows that the optimal corresponding test is independent of the choice of cg-
Theorem 4.1 (Optimal test for uniform degradation). Define the uniform-degradation weighted- mean Su)is(() = WX where == 1 -ー E RR" (and is the all-1 vector). If the distribution of X is multivariate normal, then a threshold-ters Sunsf is optimal.
Proof Sketch. According to Neyman- Peanson Lemma (Neyman et al. 1933). threshold-test on the likelihood-ratio (LR) between Ho and HA optimal. Since H. is complex. the LR minimum over e E [co. oc). Lemma [shows shows that 3sy Sunif 2 + e = En and Sunif S = e c(Sunit) ) The of the proof in Appendix[]suuu substittttes in both domains of Sunif to prove monotony of the LR in Sunif, from which we can conclude monotony in Sunif over all IR.
we define the Uniform Degradation Test (UDT) to be a threshold-ten on Sunif, i.e., "declare degradation if Sunif K² for pre-defined
Following Theorem 4.1
4

---

Under review as a conference paper at ICLR 2021
Recall that optimality of test is defined in Section as having maximal power given significance level. To achieve the significance a required Setup we apply bootstrap mechanism that randomly samples episodes from the reference dataset and calculates the corresponding statistic (e.g., S.nif). This yields a bootstrap-estimate of the distribution of the statistic under Hg, and the o-quantile of the estimated distribution is chosen the test-threshold (is qq (a(uii Ho)).
Note that Theorem 4.1 relies on multivariate normality assumption, which often too strong for real-world applications. Theorem 4.2 guarantees that if remove the normality assumption, is still beneficial to look into the episodes instead of considering them as atomic blocks; that is, on the simple mean Ssimp Σi=1 X,/n, n. Note that
UDT is still asymptotically better than "asymptotic" refers to the signal length + oo (while T remains constant), and is translated in the sequential setup into "very long lookback-horiznt h" (rather than very long running time).
Theorem 4.2 (Asymptotic power of UDT). Denote the length of the signal n K assume uniform degradation of size JK' and let two threshold-tests Tsimp on Ssimp and UDT on Sunif be tuned have significance a. Then
-ome (Teimp rejects Ho Ho) = 2 ( (00
eT
VI
Egl
(2)
S ( limm- P (UDT rejects Hol A
where T is the CDF of the standard normal distribution, and da is its a-quantile.
Proof Sketch. Since the episodes of the signal are ii.d, both Seimp and Sunif asymptotically normal according to the Central Limit Theorem. The means and variances of both statistics are calculated in Lemma P Calculation of the variance of Sunif relies writing Sunif ( and using the relation between E and Cg.
sum of
linear transformations of X (Sunif J shows that the inequality between the resulted powers equivalent to matrix-form of the means-inequality, and proves it by applying Cauchy- Saach-SSchwaz. inequality to En 1/2 and 1
we define G 2n '1)(1 Eol)
72 to be the asymptotic power gain of UDT, quantify it, and show that it increases with the heterogeneity of the spectrum of Eg-
Motivated by Theorem 4.2
Proposition 4.1 (Asymptotic power gain). G2 1+ ET, wey (); A >,)3, where {Ai)i= are the eigenvalues of Eg and {wis )r,z=1 are positive weights.
Proof Sketch. The result be calculated after diagonalization of Σg, and the weights {wiy) cor- respond to the diagonalizing matrix. See Appendix for more details.
So far we assumed a uniform degradation. In the con- text of RL, such model may refer changes in constant costs or action costs, as well as certain environment dy- namies whose change influences various states in a sim- ilar way. Fig. demonstrates the empiric degradation in the rewards of a fixed agent in HalfCheetah, following changes in gravity, mass and control-cost. It seems that some modifications indeed cause quite uniform degra- dation, while in others the degradation is mostly restricted to certain ranges of time.
mean reward- referencee
HalfCheetah
0.2
0.0
ccost110
ccost130
-0.2
grevity090
-0.4
gravity120
mass090
mass120
-08
800
1000
To model effects that are less uniform in time we suggest partial degradation hypothesis, where some (unknown) entries of No reduced by change. The number m = p T of the reduced entries is defined by parameter p (0, 1).
Figure 2: Rewards degradation of fixed agent in HalfChectah following changes gravity, mass, and control-cost, over N 5000 episodes per scenario.
O, and others do not
5

---

Under review as a conference paper at ICLR 2021
This time, calculation of the optimal test-statistic through the LR yields minimum over pos- sible subsets of decreased entries, which computationally heavy. However, Theorem 4.3 shows that if we optimize for small values of (where optimality is indeed most valuable), near-optimal statistic is Spart, which is the sum of the m = T smallest time-steps of (X - (4) after a E transformation (see formal definition in Definition [.IT]. We define the Partial Degradation Test (PDT) to be threshold-test on port with a parameter
Theorem 4.3 (Near-optimal test for uniform degradation). Assume that X is multivariate normal, and let Pa be the maximal power of hypothesis test with significance 1 - a. The power of threshold-tee test on sprrt with significance
O
Proof Sketch. The expression that is minimized is a sum two terms. One term is the sum of a subset of entries of - 14), which is minimized by simply taking the lowest entries (up to the constraint of consistency across episodes, which requires us to sum the rewards per time-step in advance). In Appendix ! we bound the second term and its effects on the modified statistic and the modified test-threshold. We show that the resulted decrease of rejection probability is (E)). O
BOOTSTRAP FOR FALSE ALARM RATE CONTROL (BFAR)
For Setup 2] we suggest sequential testing procedure:
individual degradation-test every d steps (i.c., F' = T'd test-points per episode), and return once any individual test declares degradation. The tests can run according Section 4 applied on the h recent episodes. Multiple tests may be applied every test-point, e.g., with varying test-statistics {8} or lookback-horizon {h}.
This procedure, as implemented for the experiments of Section described in Fig.
Sctup 2 limits the probability of a false alarm ag in a run of h episodes. To satisfy this condition, we set uniform threshold x on the p-values of the individual tests (i.e., declare once test returns p-val < R). The threshold is determined using Bootstrap mechanism for False Alarm control (BFAR, Algorithm[]]
While bootstrap methods for false alarm control are quite popular, they often rely on the data samples being i.i.d (Kharitonov et al.) 2015 Abhishek & Mannor 2017), which is crucial for the re-sampling to reliably mimic the source of the signal. address the non-i.i.d signal, we take advantage of the episodic framework and sample whole episodes. We then use the re-sampled sequence simulate tests on sub-sequences where the first and last episodes may be incomplete, as described below. This allows simulation of sequences of various lengths (including non-integer number of episodes) without assuming independence, normality, or identical distributions within the episodes.
Algorithm 1: BFAR: Bootstrap for FAR control
BFAR samples hmaz + episodes (where hmaz is the maximal lookback-horizon from reference data N episodes, to sim- ulate sequential data Y. Then individual tests are simulated for any test-point along h episodes, starting after 1mma episodes. The minimal p-value determines whether detection would occur in Y. The whole procedure repeats B times, creating a boot- strap estimate of the distribution of the min- imal p-value along he episodes. We choose the tests threshold be the on-quantile of this distribution, such that aq of the boot- strap simulations would raise a false alarm.
Input:
reference dataset E NxT; statistic
functions { lookback-horizons (hi,..., hmmn):
test length N; B E ag (0, 1);
Output: test threshold for individual tests; Initialize P = (1,...,
1]:;
for b in I:B do Initialize Y " thhmmat
for & in 0:(hmaaz+hh +h-1) do Sample uniformly from (1,....A) N); YIT + KT + + (I (I, TyT); for t in test-points do for h in lookback-honl horizzons and in
statistic functions do
Note that the statistic for the tests is given to BFAR as an input, making its choice in- dependent of BFAR. Additional details and time complexity are discussed in Appen- dices H
y - Ylt hT: f]:
p individual indiviidueeeesss.palllccceee .esluuly vs. s;
P + min(P()),p)) Return quantilea.(P) (P):

---

Under review as a conference paper at ICLR 2021
Sequential test for scenario H
Repeal for 1=100 different data-blocks
A episodes of random block of
block of N episodes of
Time between Individual tests
episode
h episodes
lookback byth episodes
Figure 3: A summary of the sequential degradation-tes procedure described in Section 6.1
EXPERIMENTS
6.1 METHODOLOGY
We run experiments standard Reinforcement Learning enviromments as described below. For every environment, we use Py PyTorh implementation (Kostrikov) (018)) of the standard A2C al- gorithm (Mnih ef al. 2016) to train an agent. We let the trained agent run in the environment for No episodes and record its rewards, considered the trusted reference data. We then define several scenarios, and let the agent run for M x N episodes in each scenario (divided later into A = 100 blocks of N episodes). One scenario is named Ho and is identical to the reference state randomization). The other scenarios are defined per environment, and present environmental changes expected to harm the agent's rewards. The agent is not trained to adapt these changes, and the goal is to test how long it takes for degradation- to detect its degradation.
(up to initial-
Individual degradation-testt of length (Setup D applied for every scenario the first time-steps of each block. Sequential degradation-tests (Setup 2 are applied sequentially on the episodes of each block. Since the agent is assumed to continuously the environment changes from Ho to an alternative scenario, each block is preceded by a random sample of Ho episodes, as demonstrated in Fig.
BFAR adjusts the tests thresholds have a false alarm with probability og 5% per 7 N episodes (where N is the data-block size). Two lookback- horizoos h1 h2 are chosen for every environment. The rewards are downsampled by factor d before applying the tests, intended to reduce the parameters estimation error and the running time of the tests. Table summarizes the setup of the various environments.
The experimented degradation-tests are a threshold-test on the simple Mean: CUSUM (Ryan, 2011}: Hotelling (Hotelling] 1931); UDT and PDT (with p 0.9) from Section 4 and a Mixed Degradation Test (MDT) that runs Mean, Hotelling and PDT in parallel applying all three in every pest-point (as permitted in Algorithm Tp. Further implementation details are discussed in Ap- pendix D
6.2 RESULTS
We run the in the environments of Pendulum (OpenAl). where the goal to keep one- dimensional pendulum pointing upwards; HalfChectah (Tooorov et al. (0122), where the goal is for
Table 1: Environments parameters (episode length (7), reference episodes (No), test blocks (M), episodes per black (N), sequential test length (h), lookback horizons (h,, f2z), tests per episode (F T/d))
Environment
T
Ng
M
N(= h)
h1, h2
F T/d
Pendulum-vd
200
3000
100
30
3,30
20
HalfCheetah-v3
1000
10000
100
50
5,50
40
Humanoid
200
5000
100
30
3,30
10
7

---

Under review as a conference paper at ICLR 2021
Pendulum
HairCheetah
Humanold
Detection Time (episodes)
Mean
UDT PDT HOT
100
25-
ccost110 ccost300
lond9o
len120
noiseos
ocost130 gravity30o gravity120 ccost1l0
len090
len120
Scenario
100 runs with different seeds) that ended with degradation detection, for various degradation-tests (corresponding to different colors). in sample of scenarios in Pendulum. HalfCheetah and Humanoid. Top: the distribution of time until detection for the runs that ended with detection. High detection rates usually go along with short detection times.
Figure 4: Bottom: percent of sequential tests (among
two-dimensional cheetah to fast possible; and Humanoid, where the goal is for person to walk without falling. In each environment we define the scenario ccostx of control cost increased x% of its original value, in addition scenarios of changed dynamics specified in Appendix D
In all the environments the rewards are clearly not independent, identically-distributeed or normally- distributed (see Fig. for example). Yet the false alarm rates are close to ao = 5% per episodes in all the tests, as demonstrated in Fig. 4 for HalfCheetah, for example. These results for the Ho scenarios indicate that BEAR tunes the thresholds properly in spite of the complexity of the data. Note that BFAR never observed the data of scenario Ho, but only the reference data.
In most of the non-Hy scenarios, our tests prove to be more powerful than the standard tests, often by extreme margins. For example, increased control cost in the environments and additive noise in Pendulum are all 100%-detected by the suggested tests, usually within few episodes (Fig. + whereas Mean, CUSUM and Hotelling have very poor detection rates. Mean did not detect degra- dation in Pendulum even after the control cost increased from 110% to (()%
Note that we run the tests with two lookback-horizons in parallel, as allowed by BFAR. This proves useful: with +30% control cost in HalfCheetah, for example, the short lookback-horizon allows fast detection of degradation; but with merely +10%, the long horizon necessary to notice the slight degradation over large number of episodes. This is demonstrated in Fig. 11 in Appendix C
The covariance-basee tests reduce the weights of the highly-varying (and presumably noisier) time- steps. In HalfCheetah they out to be in the later parts of the episode. As result, in certain scenarios, Mean (which ignores the different variances), CUSUM and Hotelling (which exploit them only in a heuristic way) do better in individual degradation-tests of 100 samples (out of T 1000) than they do in one or even 10 full episodes. This does not occur in UDT and PDT. Essentially, we that ignoring the noise variability leads violation of the principle that more data are better.
In Pendulum the ratio between variance of different steps may reach 5 orders of magnitude. This phenomenon increases the potential power of the covariance- basedd tests. For example, when the pole is shortened, negative changes in the highly-weighted time-steps are detected even when the mean of the whole signal increases. This feature allows us to detect slight changes in the environment before they develop into larger changes and cause damage.
On the other hand, challenging situation arises when certain rewards decrease but the highly- weighted ones slightly increase (as in longer Pendulum's 's pole), which strongly violates the assump- tions of Section 4 UDT doomed to falter in such scenarios. PDT proves somewhat robust this phenomenon since it is capable of focusing on subset of time-steps, demonstrated in increased gravity in HalfCheetah (see Fig. 4). However, it cannot overcome the extreme weights differences in Pendulum. The one test that demonstrated robustness to all the experimented scenarios, including modified Pendulum's 's length and mass, is MDT. MDT combines Mean, Hotelling and PDT and does not fall far behind any of the three, in any of the scenarios. Hence, it presents excellent results in some scenarios and reasonable results in the others.
Detailed experiments results are available in Appendix
8

---

Under review as a conference paper at ICLR 2021
7 RELATED WORK
Training in non-stationary environments has been widely researched, in particular in the frameworks
of MAB (Mukherjee & Maillard 2019 Garivier & Moulines 2011 Besbes al.. 2014 Lykouris ctt al. 2020 Alatur et al. 2020 Gupta et al. 2019 Jun et al. 2018). model-based RL (Lecarpentier & Rachelson 2019 Lee et al. 2020) and general multi-agent environments (Hernandez- 2019). Banerjee et al. (201)) explicitly detect changes in the environment and modify the policy accordingly. but assume that the environment is Markov, obsly-bbeervable. and its transition model is known- - three assumptions that we avoid and that do not hold in many real-world problems. Safe exploration during training in RI. was addressed by Garcia Fernandez 2013); Chow et al. (2018); Junges et al. (2016); Cheng et al. 2 Alshickh| (2017). Note that our work refers to changes beyond the scope of the training phase: it addresses the stage where the agent is fixed and required not train further, in particular not in online manner. Robust algorithms may prevent degradation in the first place, but when they fail or when their assumptions are not met a model-free monitor with minimal assumptions (as the one suggested in this work) is crucial.
a
Sequential tests were addressed by many over the years. Common approaches rely on strong as- sumptions such as samples independence (Pagel 1954 Ryan 2011) and normality (Pocock) 1977,
O'Brien & Fleming 1979). Generalizations exist for certain private cases (Lu & Jr. 2001] Xie & Siegmund [2011), sometimes at cost of alternative assumptions such as known change-size (Lund it al., 2007). Samples independence is usually assumed also in recent works based on numeric approaches (Kharitonov et al. 2015; Abhishek & Mannor 2017; Harel et al.] 2014). and is often justified by consolidating many data samples (e.g., an episode) together as single sample (Colas) al., 2019). DDizler et al. (2015) wrote that "change detection is typically carried out by inspect- ing i.i.d features extracted from the incoming data stream, e.g., the sample mean". Certain works address monitoring of cyclic signals (Zhou et al. 20055), but to the best of our knowledge, we are the first to devise optimal test for mean change in temporal non-i.id signals, and bootstrap-based false alarm control for such non-i.i. signals.
Our work be seen in part converting univariate temporal episodic signal into T- dimensional multivariate signal (with incomplete observations in mid-episodes). Many works ad- dressed the problem of changepoint detection in multivariate variables, e.g., using histograms com- parison (Boracchi et al. 20188. Hotelling statistic (Hotelling) 1931), and K-L. distance (Kuncheva) 2013). Hotelling in partieular looks for changed mean under unchanged covariance, similarly to our work. However, it is not derived optimally for mean change detection, and it also inherently ignores the sign of change. Our test is optimal under similar conditions to Hotelling test, is further proved to be robust to the normality assumption, and is shown to perform better in variety of experiments. We are not aware of any other work that derives an optimal test to either the uniform degradation or the partial degradation complex hypotheses.
8 SUMMARY
We introduce novel approach that is optimal (under certain conditions) for detection of changes in episodic signals, exploiting the correlations structure as measured in a reference dataset. In en- vironments of classic control (Pendulum) and MuloCo (HalfCheetah, Humanoid), the suggested statistical tests detected degradation faster than alternatives, often by orders of magnitude. Certain conditions, such combination of positive and negative changes in very heterogeneous signals, may cause instability in some of the suggested tests; however, this is shown to be solved by running the new test in parallel to standard tests with only small loss of test power.
We also introduce BFAR, a bootstrap mechanism that adjusts tests thresholds according to the de- sired false alarm rate in sequential tests. The mechanism empirically succeeded in providing valid thresholds for various tests in all the environments, in spite of the non-i.i.d data.
The suggested approach may contribute to development of more reliable RL-based systems. Future research may: consider different hypotheses, such as a permitted small degradation (instead of Hn) or a mix of degradation and improvement (instead of Ha): suggest additional stabilizing mecha- nisms for covariance-based tests; exploit other metrics than rewards for tests on model-based RL systems; and apply comparative tests of episodic signals beyond the scope of drifts detection.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Vineet Abhishek and Shie Mannor. A nonparametric sequential test for online randomized exper- iments. Proceedings of the 26th International Conference on World Wide Web Companion, pp- 610-6, 2017.
Pragnya Alatur, Kfrr Y. Levy, and Andreas Krause. JMLR, 2020.
Multi-player bandits: The adversarial case.
Mohammed Alshiekh. Safe reinforcement learning via shielding. Logic in Computer Science, 2017.
Bastian Alt, Adrian Sosic, and Heinz Koeppl. Correlation priors for reinforcement learning. NeurIPS, 2019.
Samaneh Aminikhanghahi and D. Cook. A survey of methods for time series change point detection. Knowledge and Information Systems, 51:339-367, 2016.
Adria Puigdomenech Badia et al. Agent57: Outperforming the atari human benchmark. ICML, 2020.
Taposh Banerjee. Miao Liu, and Jonathan How. Quickest change detection approach to optimal control in markov decision processes with model changes, 09 2016.
Richard Bellman. A markovian decision process. Indiana Univ. Math. J., 6:679-684, 1957. ISSN 0022-2518.
Donald A. Berry and Bert Fristedt. Bandit problems. Springer Netherlands, 1985. doi: 10.1007/ 978-94-015-3711-7
Omar Besbes, Yonatan Gur, and Assaf Zeevi. Stochastic multi-armed-bandit problem with non- stationary rewards. Advances Neural Information Processing Systems (NIPS), 27, 2014.
Giacomo Boracchi, Diego Carrera, Cristiano Cervellera, and Danilo Maccio. Quanttree: His-
tograms for change detection in multivariate data streams. Proceedings of Machine Learning Research, 80:639-648, 10-15 Jul 2018. URL httt::/pproceecingg/ wttp:/eeeiiiinm......oo..m. mlr mir.press//8C/
booaachii8a. html
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojeiech Zaremba. Openai gym, 2016.
D. Brook et al. An approach to the probability distribution of cusum run length. Biometrika, 59(3): 539-549, 1972.
Tom Bylander. Lecture notes:
Reinforcement learning. http://www. http:://wwwwws..u.ee. utsa. .tt.sedusaddd/
3x///anee///s2223/eeenfccmmeeeee Learninngn....i.nggnn..n.. pdf
Stephanie C.Y. Chan et al. Measuring the reliability of reinforcement learning algorithms. ICLR, 2020.
James Chen. Conditional value at risk httpss///wwwinnssssoood.aaaa e/conditional value at risk asp 2020.
Richard Cheng et al. End-to-end safe reinforcement learning through barrier functions for safety-
critical continuous control tasks. AAAI Conference Artificial Infelligence, 2019.
Yinlam Chow et al. A lyapunov-based approach to safe reinforcement learning. NIPS, 2018.
Cedric Colas, Olivier Sigaud, and Pierre-Yves Oudeyer. A hitchhiker's guide to statistical compar- isons reinforcement learning algorithms, 2019.
Bin Dai, Shilin Ding, and Grace Wahba. Multivariate bernuuli distribution. Bernoulli, 19(4): 1465-1483, 09 2013. doi: 10.3150/12 1--150//2-BEISPI... URL actps: :
:/ttss/////// //w////...////// http//ii..oor//// org/10. 3150/
12- REJSPP0
10

---

Under review as a conference paper at ICLR 2021
David A. Dickey and Wayne A. Fuller. Distribution of the estimators for autoregresssive time ries with a unit root. Journal of the American Statistical Association, 74(366a):427 1979. doi: 1979. 10482531
Gregory Ditzler, Robi Polikar, and Cesare Alippi. Learning in nonstationary environments: A sur- vey. IEEE Compulational Intelligence Magazine, 2015.
Gabriel Dulac- AolaccAmmod, Daniel Mankowitz, and Todd Hester. Challenges of real-world reinforcement learning, 2019.
Bradley Efron. Second thoughts on the bootstrap. Statist. Sci., 1802):135-140, 05 2003. doi: 10. 10.1214/s/11063394468. URL htttts:://....orrtt/tt 2ttp://0.121/////1133999438
Ari Freedman.
Convergence theorem for finite markov hra.:///0077/EEPPPeee/eeeemaaaa 2017.
chains.
http://maat..chhicgg.com
Javier Garcia and Fernando Fernandez. A comprchensive survey on safe reinforcement learning. JMLR, 2015.
Aurélien Garivier and Eric Moulines. upper-confidence bound policies for switching bandit problems. International Conference on Algorithmic Learning Theory, pp. 174-188, 10 2011. doi: 10.11077978--3-442220 16.
Megan Goldman.
Lecture notes in stat c141: The bonferroni correction. https//www..suu.brkkkee..e mgoldman/Secciion000..ppp 2008.
Anupam Gupta, Tomer Koren, and Kunal Talwar. Better algorithms for stochastic bandits with adversarial corruptions. Proceedings of Machine Learning Research, 2019.
Maayan Harel, Koby Crammer, Ran El- Elnia,, and Shie Mannor. Concept drift detection through resampling. International Conference on Machine Learning, pp. 11-1009-11-1017, 2014.
Peter Henderson et al. Deep reinforcement learning that matters. AAAI, 2017.
Pablo Hermandez-LLeal Michael Kaisers, Tim Baarslag, and Enrique Munoz de Cote. A survey of learning in multiagent environments: Dealing with non-stationarity. 2019.
Matteo Hessel, Joseph Modayil, Hado van Hasselt, Tom Schaul, Georg Ostrovski. Will Dabney, Dan Horgan, Bilal Piot, Mohammad Azar, and David Silver. Rainbow: Combining improvements in deep reinforcement learning. AAAI, 2018.
Harold Hotelling.
The generalization of student's ratio. Ann. Math. Statist., 2(3):300-37, 08 1931. doi: 10. 10.12144am//1117333999 URL
1177732979
Mark E. Irwin. Lecture notes: Convergence in distribution and central limit theorem. http: / //www2. stat www.eeewaaaaaaaaee /tti1///eeitnn3333 .fff 2006.
Kwang-Sung Jun al. Adversarial attacks on stochastic bandits. NewrIPS, 2018
Sebastian Junges al. Safety-constrainee reinforcement learning for mdps. International Confer- ence on Tools and Algorithms for the Construction and Analysis of Systems, 2016.
T. Kent K. V. Mardia and J. M. Bibby. Multivariate analysis. Academic Press, 1979.
Eugene Kharitonov, Aleksandr Vorobev, Craig Macdonald, Pavel Serdyukov, and Iadh Ounis. Se- quential testing for early stopping of online experiments. Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 473-482 2015. doi: 10.114577766662227777999
URL https:/ http:/:://oo..ro//...o.o 1451145/22220 62666626..1112666666666
2767729
Dmytro Korenkevych, A. Rupam Mahmood, Gautham Vasan, and James Bergstra. Autoregressive policies for continuous control deep reinforcement learning, 2019.

---

Under review as a conference paper at ICLR 2021
Ilya Kostrikov. Pytorch implementations of reinforcement learning algorithms.
https://
github. www/
2018.
Dirk P. Kroese, T. Brereton, T. Taimre, and Z. Botev. Why the monte carlo method is so important
today. Wiley Interdisciplinary Reviews: Computationaa Statistics, 6:386-392, 2014.
I. Kuncheva. Change detection in streaming multivariate data using likelihood detectors. IEEE Transactions on Knowledge and Data Engineering, 25(5):1155-1180) 2013. doi: 10.1109/TKDE. 2011.226.
David L. Demets K. K. Gordon Lan. Interim analysis: The alpha spending function approach. Statistics in Medicine, 13:1341-52, 1994.
Erwan Lecarpentier and Emmanuel Rachelson. Non-stationary markov decision processes: worst- case approach using model-based reinforcement learning. NeurIPS 2019, abs/1904.10090, 2019. URL htttt:/tp//aatt
org/ abs/ 100000
Kimin Lee et al. Context-aware dynamics model for generalization in model-based rl. JCML, 2020.
Chao- Meo Lu and Marion R. Reynolds Jr. Cusum charts for monitoring an autocorrelated process. doi: 10. 10800000224052220101111082
Journal of Quality Technology, 33(3):316-3344 2001.
URL httpt:tt////. /tt:://doi... org 10.
0tepa///00.110000022212220 0000000000002505 2001 11980082
Robert Lund, Xiaolan L. Wang, Qi Qi Lu, Jaxk Reeves, Colin Gallagher, and Yang Feng. Change- point Detection in Periodic and Autocorrelated Time Series. Journal of Climate, 20(20):5178- 5190, 10 2007. ISSN 0894-8755, doi: 10. 10.1155/CL1129111
1175/JCL1429..1
Thodoris Lykouris, Vahab Mirrokni, and Renato Paes Leme. Bandits with adversarial scaling. JCML, 2020.
Shie you)?
Mannor.
Why
does
reinforcement
learning not work (for
bttps ac wttp::nnn...../.......... wtt.ee...2222222222 41/2020/01/27/
2019.
WorkW
Conditional value-at-risk (evar). html
ciscoverr/connitt.ooall-lllll
Tatsuya Matsushima, Hiroki Furuta, Y. Matsuo, Ofir Nachum, and Shixiang Gu. Deployment- efficient reinforcement learning via model-based offline optimization. ArXiv, abs/2006.03647, 2020.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. Proceedings of Machine Learning Research, 48: 1928-197,, 20-22 Jun 2016.
MuloCo. Halfcheetah-v2.
Subhojyoti Mukherjee and Odalric-Ambrym Maillard. Distributionn-depnddent and time-uniform bounds for piecewise i.i.d bandits. arXiv preprint axXiv:/905.
Susan A Murphy, Mark van der Laan, and James M Robins, Marginal mean models for dynamic regimes. Journal of the American Statistical Association, 2001.
Ofir Nachum, Michael Ahn, Hugo Ponte, Shixiang (Shane) Gu, and Vikash Kumar. Multi-agent manipulation via locomotion using hicrarchical sim2real, PMLR, 100:110-121, 30 Oct-Ol Nov 2020. URL U mlr. http:///w........e..//ee///////a
NCSS. Cumulative sum (cusum) charts. /ttpc//sbeee////s////sssae
com/
WP Ccconttetttteeee//eeec
Jerzy Neyman, Egon Sharpe Pearson, and Karl Pearson. On the problem of the most efficient tests of statistical hypotheses. Philosophical Transactions of the Royal Society of London, 1933. doi: 10.1098/s 1933.0009.
12

---

Under review as a conference paper at ICLR 2021
Peter C. O'Breen and Thomas R. Fleming. A multiple testing procedure for clinical trials. Biomer-
rics, 35(3):59--556 1979. ISSN 0006341X, 15410420. URL http:// /www. jstorrtrrooooo orr//
stable/2530245
PennState College of Science. Lecture notes in stat 509: Alpha spending function approach.
https://on http://miiieeaa.....p...
stat stat..sattuuu... http:/dddtttt.t///oe/e//ooo/
OpenAl. Pendulum-vO. http:////////./...../aa/aa/////a
E. S. Page. Continuous Inspection Schemes. Biometrika, (1l-2))kka,,411112)0000000000000 06 1954. ISSN 0006-
3444. doi: 10.1093/biome/41111221000
1-2. 100
Fabio Pardo, Arash Tavakoli, Vitaly Levdik, and Petar Kormushev. Time limits in reinforcement learning. CoRR, abs/1712.00378, 2017.
org/ abs///b////// /1t.s//111... 00378
V. V. Petrov. Sums of Independent Random Variables. Nauka, 1972.
S. J. Pocock. Group sequential methods in the design and analysis of clinical trials. Biometrika, 64 (2)1191119, 08 1977. ISSN 0006-3444, doi: 10.1093/biomee/44...199
R. Tyreell Rockafellar and Stanislav Uryasev. Optimization of conditional value-at-risk. Journal of Risk, 2:21-41, 2000. doi: (0.21314/JOR.200000
Thomas P. Ryan. Statistical Methods for Quality Improvement. Wiley; 3rd Edition, 2011.
E. Todorov, T. Erez, and Y. Tassa. Mujoco: A physics engine for model-based control. 2012 JEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033, 2012.
A. Wald. Sequential tests of statistical hypotheses. Annals of Mathematiccal Statistics, 17
186, 06 1945. doi: 10. 10.1214/aoms/ 17773///
111131118
James Westgard, Torgny Groth, T Aronsson, and C Verdier. Combined shewhart-cusum control chart for improved quality control clinical chemistry. Clinical chemistry, 23:1881-7, 11 1977. doi: 10. 10.1093klinchem/23.1000 10t.hccheeee....88......
S. S. Wilks. The larpe-sample distribution of the likelihood ratio for testing composite hypotheses. Ann. Math. Statist., 91):60--2,, 03 1938, doi: 2 URL hhtpps:// doi.org/ 10. 121 20///m////3/
S. M. Williams al. Quality control: application of the cusum. BMJ: British medical journal, 304.68 38: 1359, 1992.
Yao Xie and David Siegmund. Weak thange-point detection using temporal correlation, 2011.
E. Yashchin. On the analysis and design of cusum-shewhee control schemes. IBM Journal of Research and Development, 29(4)3777-311, 1985.
Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization, 2020.
Xingyu Zhao et al. Assessing the safety and reliability of autonomous vehicles from road testing. ISSRE, 2019.
Shiyu Zhou, Nong Jin, and Jionghua (Judy) Jin. Cycle-based signal monitoring using directionally variant multivariate control chart system. Transactions, 37 -982, 2005. doi: 10. 1080/ 07408 0144087755002555. URL TRRLtER https: http::///......oo..o../////0///0
13


Reviews:
[{"review_id": "rcw069COy-b", "reviewer": "AnonReviewer3", "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": "The authors present a novel change detection test for non i.i.d. data motivated by applications in RL. At first, they provide an offline version of the test, then they extend it to the online setting.\n\nThe paper is clearly written and presents both theoretical results and convincing experimental results. My two concerns are about the novelty of what has been proposed w.r.t. standard CDT procedures and on the fact that a consistent part of the material of what has been proposed in the paper is deferred to the appendix.\n\nI would like to have more discussion on the difference between what has been proposed here and the standard multivariate CDTs, for instance:\nKuncheva, Ludmila I. \"Change detection in streaming multivariate data using likelihood detectors.\" IEEE transactions on knowledge and data engineering 25.5 (2011): 1175-1180.\nBoracchi, Giacomo, et al. \"Quanttree: histograms for change detection in multivariate data streams.\" International Conference on Machine Learning. 2018.\nA strong motivation of the novelty w.r.t. to the literature might make me increaese the paper score.\n\nIn my opinion, the paper is not self-contained. Not even the main theorem proof are included (the sketches are not useful in understanding the proof line) and the experimental setting is described in details only in the additional material. I think you should rearrange some of the material from the appendix to the main paper and viceversa.\n\nI would have appreciated a more detailed description of Algorithm 1. In this version of the paper it is difficult to understand the procedure you proposed, if you do not refer to the appendix for details.\n\nIn your setting the change in the episodic reward is only about the expected values. What happens if the new reward distribution changes in terms of covariance \\Sigma?\n\nMinor:\n\"in RL ... life-time of the task.\" I would have preferred a citation about this statement. Showing evidence using your experiment is a bit premature at this stage of the presentation.\nassume strong assumptions -> require strong assumptions\n\n--------------------------------------------------------------------------------------------------\nAfter rebuttals the authors significantly improved the presented work, including and discussing some relevant work which was previously missing. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "hryeiwwoaY7", "reviewer": "AnonReviewer4", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers the drift detection for episodic data, where data episodes are assumed to be i.i.d. but data within each episodic can be correlated. It is assumed that the pre-change (nominal) mean and covariance of each episodic is perfectly known or can be accurately estimated from reference data. The Uniform Degradation Test (UDT) and Partial Degradation Test (PDT) are proposed to detect the mean shift. Moreover, this paper uses bootstrap to control the false alarm rate by setting the threshold as empirical quantiles of the detection statistic computed from reference data. \n\nOverall, this paper is well written and well-structured. The most impressive part is that they include comprehensive details, covering almost every related aspect. And this paper has tried to make the problem as general as possible, such as considering non-Gaussian distributions, etc.\n\nHowever, the technical contribution is very incremental. And the problem itself, although is proposed in the reinforcement learning setting, is of no fundamental difference with the classical mean shift in change-point detection literature, for example, change-point detection for a mean shift in multivariate Gaussian distributions. And I didn't see the classical Hotelling T^2 test mentioned in this paper, which is a classical and also widely-used method to detect the change in mean/covariance, and it also utilizes the pre-change covariance matrix in the detection statistic. Moreover, the proposed Uniform Degradation Test methods are a direct consequence of the likelihood ratio test; the false alarm control by bootstrap is also widely used in change-point detection literature for problems where the theoretical characterization of false alarm rate (or average run length) is difficult to obtain. \n\nLooking forward, I think this paper may be improved by expanding the horizon of the problem set-up and possibly leading to new theoretical findings. \n\n================ After the author response, I raise my score by 1 ================\nThanks to the authors for the detailed response and extended discussion on theoretical results and experiments, and I have raised my score by 1. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "JqCNyuojeLA", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper designed a hypothesis testing procedure for detecting changes in episode sequential data.  For online operation, it also proposed a novel Bootstrap mechanism for False alarm rate control. The method is demonstrated based on a non-iid and non-Gaussian setting for reward signals.\n\nIn all the method is theoretically sound and seems useful for detecting changes, however there is no experiments provided to show that the method can help improving the performance in RL tasks. The strength of this paper would be significantly boosted if the proposed method can be used to solve an non-stationary RL problem.\n\nMoreover, it is a little unclear the specific setting of this work. Is the underlying sequential decision making problem based on Markov decision processes(MDPs)?\nThere is no surprise that the RL feedback from an environment is highly correlated over consecutive time-step if the underlying problem is an MDP. It seems that the paper mainly deal with per-step reward without considering state and action information when detecting changes. \nSome related work that also applies hypothesis testing procedure for non-stationary MDPs might worth mentioning. E.g,\n\nBanerjee et al. Quickest change detection approach to optimal control in Markov decision processes with model changes\n\n“In setup 2, … we consider a fixed trained agent … , “ It is unclear if the trained agent exhibit an optimal behavior or arbitrary behavior(sub-optimal)? \n\nIn figure 2, does each curve correspond to a fixed policy?\n\n=========after rebuttal===========\n\nI appreciate the authors’ effort to address my questions. I still think this paper is below my expectation especially if it is put into the context of RL.  I would expect to see how this method can solve or help solving a fundamental problem (e.g., reducing sample complexity) in RL or be applied to a novel application (e.g., nonstationary RL tasks). Otherwise I didn’t see why it is necessary to compare this method with other statistical testing methods in the context of RL, if they can be easily made in other non-iid settings without mentioning RL. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "JOgO2UeGt5_", "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": "The authors propose a sequential testing procedure for a fixed RL agent reward drift. \n\nMajor issues:\n\n1. The authors state in some places of the text that their method can be applied in statistic domain other than RL. However, for me, the entire proposed methodology does not relate to RL and is more general: it can be applied to any sequential statistics (series of random variables) that have a proper [auto]correlation structure (just see how the main statements). Due to this, I have concerns in the way how these proposed approaches are presented: I believe that a paper requires a notable refactoring to improve the presentation.\n\n\n2. Seem that the contribution is not enough for the current venue.  All the proposed statements (Theorem 4.1, Theorem 4.2) looks very straightforward. Possibly, there untrivial tricks in their proofs, but the current proofs (proof sketch) does not reflect them at all (see). I expect a clearer presentation in the main text why these results are non-trivial and non-incremental. As for now, the provided theoretical grounds looks as non-enough for publication @ ICLR.\n\n\n\nOther issues:\nPaper cites the paper\n [Vineet Abhishek and Shie Mannor. A nonparametric sequential test for online randomized experiments. Proceedings of the 26th International Conference on World Wide Web Companion, pp.\n610–6, 2017] \nwhere seq. testing is applied to A/B tests, but there is an earlier paper on this approach:\n [Eugene Kharitonov, Aleksandr Vorobev, Craig Macdonald, Pavel Serdyukov, and Iadh Ounis. Sequential testing for early stopping of online experiments. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR’15, pages 473–482, New York, NY, USA, 2015. ACM.]\n\n================\nAfter the author response, I raise my score by 1 (see my comment to them)", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper's initial evaluation was below par, but the author feedback helped clarify several crucial points after which two of the reviewers increased their scores by a point, bringing the current evaluation to borderline. 

The paper addresses a relevant and challenging problem in the RL domain. However, in my opinion, from the reviewers' and authors' remarks and from my own reading of the paper, there are concerns that need to be addressed before the paper can be publication worthy. Primary among these is the quantum of novelty -- as many reviews point out, the key idea of viewing an episodic trajectory as a multivariate (vector) sample for running hypothesis tests is not novel in itself, as is the claim that new tests have been devised. Another crucial issue is the (parametric) assumption of normality for the episodic reward sequence which is not adequately justified in the paper -- even a two time-step trajectory with normal rewards per state transition can exhibit a mixture-of-Gaussians type reward distribution for the second state, breaking the assumption. As it transpired from the reviews of Reviewer4, reducing environment shift/degradation to just a mean change problem, without even considering a change in the variances (2nd order statistics), seems to be too stylized to be effective. There are other, nonparametric approaches in statistics based on testing for changes in the distribution function (kernel density estimation approaches, for instance), which could perhaps be applied without normality assumptions and yield favourable results. The experimental results for detection delay often show significant overlaps of the delay distributions for different procedures (e.g., Hotelling vs. Mean vs. UDT etc.), which does not indicate an advantage of the proposed method. 

I would urge the author(s) to assimilate the feedback and delve deeper as to why and how parametric procedures based on normality assumptions may or may not succeed, so as to significantly strengthen the theoretical and practical message of this work.  
Decision: Reject