## 9 Quickest Spectrum Sensing
### Elements of Markov decision process  
For such a Bayesian quickest spectrum sensing, we can apply the framework of Markov decision process, whose elements are given below  
* State space: we denote a state by \(S_{m}^{\Omega}\), where \(\Omega\) denotes the set of bands being used for data communication and \(m\in\Omega\) denotes the band being sensed. When \(\Omega\) is an empty set, the state, denoted by \(S^{0}\), means that all frequency bands are not being used by the secondary user. The state transition diagram for the case of \(M=2\) (2 channels) is illustrated in Figure 42. For example, the transition from state \(S_{1}^{\{1,2\}}\) to state \(S_{2}^{\{2\}}\) means that the secondary user claims that primary user has emerged over channel 1, stops communication over channel 1 and then monitor channel 2; the transition from state \(S_{1}^{\{1,2\}}\) to state \(S_{2}^{\{1,2\}}\) means switching to monitor channel 2 without stopping the communications over channel 1. * Action space: for each state (except \(S^{0}\)), the secondary user can take three types of actions, which are illustrated in Figure 43, namely continuing transmitting and monitoring the current channel, switching to monitor another channel without stopping the communication over the current channel, and switching to monitor another channel while stopping the communication over the current channel. Figure 42: State transition diagram when \(M=2\). Figure 43: Three possible actions for each state. * Cost function: we define a single cost function which leads to the corresponding optimal control policy. As mentioned before, we need to consider the penalties incurred by both detection delay and false alarm. Therefore, we define the cost function as follows (note that all the probabilities are conditioned on the observations; for simplicity, we ignore the condition in the expression of probabilities): \[R = \sum_{m=1}^{M}P\left(T_{m}>T_{m}^{*}\right)+c\sum_{m=1}^{M}E\left[ \left(T_{m}^{*}-T_{m}\right)^{+}\right]\] \[= \sum_{m=1}^{M}P\left(T_{m}>T_{m}^{*}\right)+c\sum_{m=1}^{M}E\left[ \sum_{k=1}^{T_{m}^{*}-1}P\left(T_{m}\leq k\right)\right]\] where \(c\) is a weighting factor balancing the penalties from detection delay and false alarm and subscript \(m\) denotes the index of channels (recall that \(T^{*}\) means the time claiming the emergence of primary user and \(T\) is the actual emergence time). Therefore, for time slot \(k\) (suppose that the current channel is \(m\)), we have
* if not stopping communication over the current channel, we get penalty \(cP(T_{m}<k)\) (detecting delay);
* if stopping transmission over the current channel, we get penalty \(P\left(T_{m}>T_{m}^{*}\right)\) (false alarm). * Control policy: we consider a stationary control policy, i.e. the action is dependent on only the current state and is independent of time. It is well known that the optimal control policy of Markov decision process can be solved by dynamic programming [155, 156, 157]. A general formulation for a Markov decision process is  
\[s_{t+1}=f(s_{t},u_{t},w_{t}) \tag{71}\]  
where \(s_{t}\) is the state at time \(t\), \(u_{t}\) is the control policy and \(w_{t}\) is random perturbation. Suppose that the corresponding cost function is given by  
\[J=\sum_{t=1}^{\Gamma}E\left[g(s_{t},u_{t},w_{t})\right] \tag{72}\]  
where \(g\) is the function of cost for each time slot and \(\Gamma\) is the final time slot (here we consider finite horizon case). A fundamental concept in dynamic programming is cost-to-go function (also called value function if we use reward instead of cost), which is defined as the sum of cost from time \(t\) to \(\Gamma\), denoted by \(J_{t}(s)\) when the current state is \(s\), i.e.