# Low-Cost Active Anomaly Detection with Switching Latency
## Appendix A Proof for Theorems
### The Expected Cumulative Cost of DMSC Policy  
In the DMSC policy, the detection procedure is divided into \(L\) or \(M-L\) stages, depending on whether the decision-maker chooses to probe the process with the highest sum-LLRs \(m^{1}(n)\) or the process with the lowest sum-LLRs \(m^{-1}(n)\). Here, we analyze the asymptotic performance of the DMSC policy on the expected cumulative cost at each stage. Summing the expected cost of each stage will yield the expected cumulative cost of the entire detection procedure. Inspired by (4), we analyze the number of observations and switchings at each stage to obtain the expected cumulative cost. Let \(N_{d}^{k}\) and \(N_{s}^{k}\) denote the observation times and the switching times during the \(k\)-th stage, respectively. Note that differing from the subscript \(m\) of \(N_{\tau_{m}}^{d}\) and \(N_{\tau_{m}}^{s}\), which represents the index of the process, the superscript \(k\) of \(N_{d}^{k}\) and \(N_{s}^{k}\) represents the index of the stage. Figure 1 visually shows the relationship between these parameters. For example, consider the anomaly detection problem among a system consisting of \(M=3\) processes (denoted as process \(1,2,3\)) and \(L=2\) abnormal processes (for example, process \(1,3\) are abnormal). We assume that the decision-maker chooses \(m^{1}(n)\) to probe and once the number of processes declared as abnormal reaches \(L\), the detection procedure terminates. Suppose that the decision-maker identifies the abnormal processes in the order of \(\{1,3\}\). Hence, the entire detection procedure will be divided into two stages. The stage 1 is from the beginning of the detection procedure \(n=0\) to the stopping time \(\tau_{1}\) of process 1, where the stopping time \(\tau_{1}\) can be expressed as \(\tau_{1}=N_{\tau_{1}}^{d}+sN_{\tau_{1}}^{s}\), and the duration of stage 1 can be expressed as \(N_{d}^{1}+sN_{s}^{1}\). Similarly, the stage 2 is from the stopping time \(\tau_{1}\) to the stopping time \(\tau_{3}\). The stopping time \(\tau_{3}\) can be expressed as \(\tau_{3}=N_{\tau_{3}}^{d}+sN_{\tau_{3}}^{s}\), where \(N_{\tau_{3}}^{d}=N_{d}^{1}+N_{d}^{2}\) and \(N_{\tau_{3}}^{s}=N_{s}^{1}+N_{s}^{2}\) are the summation of the observation times and the switching times in two stages, respectively. The duration of stage 2 can be expressed as \(N_{d}^{2}+sN_{s}^{2}\). In addition, once the state of abnormal process is identified, the corresponding process stops incurring cost. Thus, the cost incurred by process 1 is \(c\tau_{1}\) and the cost incurred by process 3 is \(c\tau_{3}\), while process 2 does not incur any cost because it is in a normal state. As a conclusion, the cumulative cost incurred during the entire detection procedure is given by \(c\tau_{1}+c\tau_{3}\). Then, we upper bound the expected cumulative cost by analyzing the number of observations and switchings at each stage for Case I and Case II. Since the condition of Case II in DBS policy and DMSC policy are the same, we can apply ([26], Lemma 5 and Lemma 6) to our model in Case II and yield:  
\[E(N_{d}^{k}|\text{Case II})\leq(1+o(1))\frac{B}{D(f||g)}\text{ as }\alpha \to 0, \tag{10}\]  
and there exists \(T_{s}\in(0,\infty)\) such that  
\[E(N_{s}^{k}|\text{Case II})\leq T_{s}. \tag{11}\]  
However, it is not feasible to apply the conclusion (10) and (11) directly to the Case I of DMSC policy since the condition of Case I of DMSC is more complicated. Therefore, it remains to upper bound the observation times and switching times for Case I of DMSC policy. For Case I, we can upper bound the observation times \(N_{d}^{k}\) and switching times \(N_{s}^{k}\) of each stage by analyzing three last passage times of each stage \(k\) on the assumption that the ratio \(s\) is equal to zero, and the obtained upper bounds are applicable to the case where \(s\) is greater than zero.