# Decentralized Blind Spectrum Selection in Cognitive Radio Networks Considering Handoff Cost
## 3 Problem Formulation and Policies  
Blind spectrum selection in decentralized cognitive radio networks can be formulated as a decentralized MAB problem for multiple distributed SUs [8; 9; 12; 13; 14], and in this paper the terms \"channel\" and \"arm\" are used interchangeably. Denote \(\pi_{j}\) as the decentralized policy for SU \(j\) and \(\pi=\left\{\pi_{j},1\leq j\leq M\right\}\) as the set of homogeneous policies of all users. Arm \(i\) yields reward \(X_{i}(t)\) at slot \(t\) according to its distribution, whose expectation is \(\theta_{i}\), \(\theta_{i}\in\Theta\). Thus, the sum of the actual reward obtained by all users after \(T\) slots following policy \(\pi\) is  
\[\sum_{t=1}^{T}S^{\pi}(t)=\sum_{t=1}^{T}\sum_{i=1}^{C}\sum_{j=1}^{M}X_{i}(t) \mathbb{I}_{i,j}(t) \tag{1}\]  
where \(\mathbb{I}_{i,j}(t)\) is defined to be 1 if user \(j\) is the only one to play arm \(i\) at slot \(t\); otherwise, it is 0. In the ideal scenario where the availability statistics \(\Theta\) are known, the SUs are orthogonally allocated to the \(\mathcal{O}_{M}^{*}\) channels, where \(\mathcal{O}_{M}^{*}\) is the set of \(M\) arms with \(M\) largest expected rewards. Then, the expected reward after the \(t\) slots is  
\[\sum_{t=1}^{T}S^{*}(t)=T\sum_{i\in\mathcal{O}_{M}^{*}}\Theta_{i}. \tag{2}\]  
Figure 2: Cognitive radio frame structure. Then, we can define the performance of the policy \(\pi\) as regret \(R_{M}^{\pi}(\Theta;T)\):  
\[R_{M}^{\pi}(\Theta;T)=T\sum_{i\in\mathcal{O}_{M}^{*}}\theta_{i}-\mathbb{E}^{\pi} [\sum_{t=1}^{T}S_{\pi}(t)] \tag{3}\]  
where \(\mathbb{E}[\cdot]\) is the expectation operator. We call a policy \(\pi\) uniformly good if for every configuration \(\Theta\), the regret satisfies  
\[R_{M}^{\pi}(\Theta,T)=o(T^{a})\ \ \text{for}\ a>0. \tag{4}\]  
Such policies do not allow the total regret to increase rapidly for any \(\Theta\). This problem is widely studied and several representative policies that are uniformly good are proposed: the distributed \(\varrho^{\text{PRE}}\) policy [8], the SL(K) policy [9], and the \(k\)th-UCB1 policy [11]. The distributed \(\varrho^{\text{PRE}}\) policy based on the \(\varepsilon_{n}\)-greedy policy, which prescribes to play the highest average reward arm with probability \(1-\varepsilon_{n}\) and a random arm with probability \(\varepsilon_{n}\), and \(\varepsilon_{n}\) decreases as the experiment proceeds. However, one parameter of the policy requires prior evaluation of the arm reward means. To avoid this problem, the SL(K) policy is proposed based on the classical UCB1 policy of the MAB problem. Through it guarantees logarithm regret in the long run, it leads to a larger leading constant in the logarithmic order. The \(k\)th-UCB1 policy makes a good tradeoff on both policies. ```
1.//Define: \(n_{i}(t)\): the number of arm \(i\) is played after \(t\) slots. \(\hat{\theta}_{i}(t)\): sample mean availabilities after \(t\) slots. \(\varepsilon_{t}:=\min[\frac{\beta}{t},1]\), where decay rate \(\beta\) is prior valuated according to the arm reward means //Init: play each arm once  For \(t=1\) to \(C\)  Play arm \(i=t\) and let \(n_{i}(t)=1\), \(\hat{\theta}_{i}(t)=X_{i}(t)\)  EndFor //Main loop For \(t=N+1\) to \(T\)  Step1: play the arm of the \(K\)th highest index values in \(\{\hat{\theta}_{i}(t)\}\) with probability \(1-\varepsilon_{t}\) and play a channel uniformly at random with probability \(\varepsilon_{t}\)  Step2: Update \(n_{i}(t)\), \(\hat{\theta}_{i}(t)\) and \(\varepsilon_{n}\)  EndFor
```  
**Algorithm 1**\(\varrho^{\text{PRE}}\) policy for the user with rank \(K\). ```
1. //Define: \(n_{i}(t)\): the number of arm \(i\) is played after \(t\) slots. \(\hat{\theta}_{i}(t)\): sample mean availabilities after \(t\) slots. 2. // Init: play each arm once  For \(t=1\) to C  Play arm \(i=t\) and let \(n_{i}(t)=1\), \(\hat{\theta}_{i}(t)=X_{i}(t)\)  EndFor
3.