We consider the problem of quickest change detection (QCD) in a signal where its observations are obtained using a set of actions, and switching from one action to another comes with a cost. The objective is to design a stopping rule consisting of a sampling policy to determine the sequence of actions used to observe the signal and a stopping time to quickly detect for the change, subject to a constraint on the average observation-switching cost. We propose an open-loop sampling policy of finite window size and a generalized likelihood ratio (GLR) Cumulative Sum (CuSum) stopping time for the QCD problem. We show that the GLR CuSum stopping time is asymptotically optimal with a properly designed sampling policy and formulate the design of this sampling policy as a quadratic programming problem. We prove that it is sufficient to consider policies of window size not more than one when designing policies of finite window size and propose several algorithms that solve this optimization problem with theoretical guarantees. For observation-dependent policies, we propose a $2$-threshold stopping time and an observation-dependent sampling policy. We present a method to design the observation-dependent sampling policy based on open-loop sampling policies. Finally, we apply our approach to the problem of QCD of a partially observed graph signal and empirically demonstrate the performance of our proposed stopping times.
翻译:我们在一个信号中考虑最快速变化探测(QCD)的问题,该信号的观测是通过一套行动获得的,而从一种行动转换到另一种行动则需要一定的成本。我们的目标是设计一个停止规则,由抽样政策组成,以确定用于观察信号的行动顺序和为变化快速探测的停止时间,但以平均观测开关费用为限制条件。我们提出一个开放环抽样政策,即窗口的有限尺寸和普遍可能性比率(GLR)累积总和(Cusum)停止QCD问题的时间。我们表明,GLR Cusum停止时间与适当设计的取样政策相比是极其理想的。我们提出一种方法,用以设计基于观察-CD的取样政策,作为四面形规划问题。我们证明,在设计有限的窗口规模政策时,只要考虑一个不大于一个的窗口尺寸的政策就足够了,并提出若干算法,用理论保证解决这一最优化问题。关于观察依赖的政策,我们提出一个$$2$-小时的停止时间和观察依赖抽样的政策。我们提出了一个方法,用以设计我们所观察到的基于观测-Q检验的抽样政策,最后展示我们所观察到的检验的进度。