## 9 Quickest Spectrum Sensing
### Infinite Horizon Case  
A drawback of the finite horizon case is that we need to compute a cost-to-go function for each combination of time and state. For the case of \(M=2\), we have four non-trivial states. Therefore, if we consider a time window of 500 time slots, we need to compute 2000 cost-to-go functions, which brings substantial computational cost to the system. Meanwhile, the assumption of finite horizon is unreasonable since the spectrum sensing may last for any arbitrarily long period of time.  
Therefore, it is more desirable to study the infinite horizon case, i.e., \(\Gamma\rightarrow\infty\). An advantage of considering infinite horizon case is that we can ignore the subscript of time in the cost-to-go functions because it is easy to show that, as \(\Gamma\rightarrow\infty\),  
\[J_{t}\left(S_{m}^{\Omega}|\mathbf{p}_{t}\right)\to J\left(S_{m}^{ \Omega}|\mathbf{p}_{t}\right),\qquad\forall t \tag{78}\]  
By considering infinite horizon, the number of cost-to-go functions is reduced to 4 when \(M=2\). We can further simplify the cost-to-go functions using the following two features (the details can be found in [158]):  
* **Symmetry** : frequency bands are symmetric, the permutation of the frequency bands yields the same cost-to-go function.
* **Argmin**: If transiting to another frequency band, the secondary node should always choose the frequency band having the largest _a posteriori_ probability.  
After simplifying the cost-to-go functions, we can apply the Bellman's equation to compute the optimal cost-to-go functions and the corresponding optimal control policy.  
Combating the Curse of Dimensions  
Although we have simplified the cost-to-go functions, the number of states still becomes intolerably large when \(M\) becomes large. The discretization of the \(M\)-vector \(\mathbf{p}_{t}\) adds more dimensions to the cost-to-go functions. Such a curse of dimensions is an inherent difficulty for Markovian decision process. Therefore, it is desirable to apply techniques in approximate dynamic programming such as Rollout, approximate cost-to-go function, open look feedback control or model prediction control.  
In [156], two simple principles are applied to obtain simplified control policy:  
* Limited lookahead policy (LLP): in standard dynamic programming, the optimal control policy needs to look into the future; we can relax this requirement and look ahead for only limited time slots.
* Certainty equivalent control (CEC): we can replace the random variables in the optimization problem with their expectations. Surprisingly, such an operation still yields the optimal control policy for linear control problems. Since our problem is non-linear, the resulted control policy is suboptimal.  
By using the LLP principle, we consider only two most 'dangerous' channels, i.e., the channel being monitored and the channel having the largest _a posteriori_ probability that the primary user has emerged among the channels not being sensed (for simplicity, we assume that they are channel 1 and channel 2). Then, we reduce the problem to a much simpler case of \(M=2\). By applying the CEC principle, we compute the expected time of primary user emergence over channels 1 and 2, denoted by \(\bar{T}_{1}\) and \(\bar{T}_{2}\)Since we need to consider the impact of false alarm and transition time \(d_{s}\), we compensate these two expectation by  
\[\tilde{T}_{1}^{t}=\bar{T}_{1}^{t}+\frac{1}{c}(1-\left(\mathbf{p}_{t}\right)_{1}) \tag{79}\]  
and  
\[\tilde{T}_{2}^{t}=\bar{T}_{2}^{t}+\frac{1}{c}(1-\left(\mathbf{p}_{t}\right)_{2} )+d_{s} \tag{80}\]  
Then, we consider the compensated times as their true values. A heuristic decision rule is given by  
* If \(\tilde{T}_{1}^{t}\leq t\), stop the communication over channel 1 (the current channel) and switch to channel 2;
* If \(\tilde{T}_{1}^{t}\geq\tilde{T}_{2}^{t}\geq t\), stop sensing channel 1 and switch to sense channel 2.
* If \(\tilde{T}_{2}^{t}\geq\tilde{T}_{1}^{t}\geq t\), continue to sense channel 1;  
The three cases are illustrated in Figure 44.