# Reinforcement Learning Based Relay Selection for Underwater Acoustic Cooperative Networks
## 3 RL Based Relay Selection Method for UWA Cooperative Networks
### SA Optimized RL Relay Selection Strategy  
According to the values in Q-table, optimal relay can be selected by \(\varepsilon\)-greedy algorithm to avoid being trapped in a local maximum. The \(\varepsilon\)-greedy selection strategy can be expressed as  
\[\pi(s|a^{\prime})=\left\{\begin{array}{rl}\arg\max Q\Big{(}s^{(t)},a^{\prime} \Big{)},&\text{probability }1-\varepsilon\\ \text{random action},&\text{probability }\varepsilon\end{array}\right. \tag{19}\]  
where \(\varepsilon\) is the greedy factor. In state \(s\), the \(\varepsilon\)-greedy algorithm selects the action corresponding to the maximum Q-value with probability \(1-\varepsilon\), and selects random action with probability \(\varepsilon\). \(\varepsilon\) is an invariant constant in classical \(\varepsilon\)-greedy algorithm.  
For invariant constant \(\varepsilon\), even when the rewards turn to be stable, the selection strategy will still explore other possible actions with probability \(\varepsilon\), which will cause the reward to fluctuate. Therefore, this paper exploits the thought of SA algorithm to optimize the strategy of relay selection dynamically. The agent will fully explore all of the actions at the beginning of RL with a high value \(\varepsilon\). With the number of iteration rounds increasing and reward converges to be stabilized, the value of \(\varepsilon\) will decrease, which indicates that the agent will explore random action with lower probability.  
In this paper, the action selection strategy is optimized by Metropolis criterion based SA algorithm. The greedy factor \(\varepsilon\) is related to the exploration rate, and it can be dynamically adapted by SA optimization through the temperature decline rate. Meanwhile, the temperate decline rate will regulate the probability to accept the new solution of Q-values. In each round, the new solutions of Q-value will be generated by RL, and whether to accept new solution is determined by Metropolis criterion under certain temperature. The greedy factor \(\varepsilon\) of RL is corresponding to the temperate in SA algorithm, and \(\varepsilon\) is gradually reduced to the lowest temperature until the end of iteration.  
The flowchart of SA-RL algorithm is shown as Figure 5, and the specific implementation steps are described as follows.  
**Step 1:** Initialize the solution \(Q_{0}\), \(V\) and temperate \(T_{0}\). The elements of initial Q-table are set to 0. For each state, \(V\) is defined as Equation (19). The initial temperature for SA is set to 1.  
**Step 2:** In \(t\) time round, calculate a new solution \(Q_{new}\) by RL algorithm.  
**Step 3:** Implement Metropolis criterion to decide whether to accept the new solution under temperature \(T_{t}\) of SA. Define \(\Delta E=V-Q_{new}\), which represents the difference between the maximum value \(V\) in the current state and the generated new Q-value \(Q_{new}\). If \(\Delta E\leq 0\), then the new solution will be accepted. If \(\Delta E\geq 0\), the new solution will be accepted with a probability given by \(Pr(\Delta E)=\exp(-\Delta E/KT_{t})\), where \(K\) is Boltzmann constant, and usually can be set to 1.  
**Step 4:** Cooling schedule. The cooling schedule represents the procedure to reduce the temperature as the convergence is reached, which means the agent will explore the random action with lower probability. In this paper, the temperature reduces according to \(T_{t+1}=\lambda T_{t}\), where \(\lambda\) is the cooling rate which decides the decreasing speed of the temperature. The value of cooling rate is less than 1. In SA-RL, the temperature is set to be greedy factor.  
**Step 5:** If the stop criteria is met, stop the algorithm, or else go to Step 2. The termination condition is set to stop the algorithm when the temperature reaches the minimum value or the algorithm reaches the number of iterations. In this paper, the algorithm will be terminated when the number of iterations reaches the scheduled number.