# Low-Cost Active Anomaly Detection with Switching Latency
## Appendix A Proof for Theorems  
### The Asymptotic Lower Bound on the Expected Cumulative Cost  
In this subsection, we establish the asymptotic lower bound on the expected cumulative cost that can be achieved by any policy.  
**Lemma A1** (The Asymptotic Lower Bound on the Expected cumulative cost).: _Let \(C^{*}_{LB}\) denote the asymptotic lower bound on the expected cumulative cost. Then,_  
\[C^{*}\geq C^{*}_{LB}, \tag{12}\]  
_where,_  
\[C^{*}_{LB}=c\cdot\min\left[\frac{L(L+1)B}{2D(g||f)}+s\frac{L(L-1)}{2},\frac{L (M-L)B}{D(f||g)}+sL(M-L-1)\right], \tag{13}\]  
_and \(B\) is a function of \(\alpha\) and \(B\approx\log\frac{1-\alpha}{\alpha}\)._  
Proof.: According to the objective function as (4), the cumulative cost consists of the cost incurred by the observations and the cost incurred by the switchings, and \(E(C_{d})\) and \(E(C_{s})\) denote the cost incurred by the observations and switchings respectively. It should be noted that once an abnormal process is identified, it will not continue incurring costs.  
When the total number of processes \(M\) and the number of abnormal processes \(L\) are known, there are two ways to declare the number of abnormal processes, one is to directly declare the \(L\) abnormal processes as abnormal, and the other is declaring \(M-L\) normal processes as normal one by one and declaring the remaining \(L\) processes as abnormal.  
When the states of the abnormal processes are declared directly, it is intuitive that probing normal processes before declaring the states of abnormal processes will increase the observation cost. Hence, to establish the lower bound on the expected cumulative cost, we assume that all the abnormal processes are tested before the normal ones. We apply ([22], Lemma 1), where an asymptotic lower bound on the expected cumulative cost considering only the observation cost was established under the same assumption, we have:  
\[\begin{split}\inf_{\Gamma}E(C_{d}|\Gamma)&\geq \sum_{l=1}^{L}c\sum_{i=1}^{l}\frac{B}{D(g||f)}\\ &=\frac{cL(L+1)B}{2D(g||f)}.\end{split} \tag{14}\]  
Furthermore, any additional switching will also increase the cost. Thus, we assume that each process must be probed continuously and switching is not performed until the state of the currently probed process is declared. Thus, at least \(L-1\) switchings will occur during the entire detection procedure and the cost incurred by the switchings can be lower bounded by  
\[\inf_{\Gamma}E(C_{s}|\Gamma)\geq\frac{csL(L-1)}{2}. \tag{15}\]  
Thus, the expected cumulative cost in this situation can be lower bounded by  
\[C^{*}=\inf_{\Gamma}E(C|\Gamma)\geq c\left(\frac{L(L+1)B}{2D(g||f)}+s\frac{L(L -1)}{2}\right) \tag{16}\]  
as \(\alpha\to 0\).  
When declaring the normal processes one by one, we assume that all the normal processes are tested before the abnormal process, and switching across processes is performed only when the state of the currently probed process is declared. Since \(\lim_{\alpha\to 0}E(N_{m}|H_{0})\to B/D(f||g)\)[1], and the number of abnormal processes incurring costs remains constantduring the detection procedure (because none of the abnormal processes are identified), we have:  
\[\begin{split} C^{*}=\inf_{\Gamma}E(C|\Gamma)&\geq\sum_{l= 1}^{L}c\sum_{i=1}^{M-L}\frac{B}{D(f||g)}+csL(M-L-1)\\ &\geq c\bigg{(}\frac{L(M-L)B}{D(f||g)}+sL(M-L-1)\bigg{)}\end{split} \tag{10}\]  
as \(\alpha\to 0\).  
Combining (11) and (10), the proof of Lemma 1 is completed.