# A Novel Relay Selection Scheme Based on Q-Learning in Multi-Hop Wireless Networks
## 3 Proposed Relay Selection Scheme  
### Q-Learning Theory  
Reinforcement learning (RL) is defined as a machine learning scheme that is concerned how software agents should take actions in an environment. The purpose of the RL is to maximize the cumulative rewards. The machine learning can be divided into three types. Supervised learning means learning getting the right answer and getting feedback immediately. Unsupervised learning is a solving problem like classification with no correct answer. RL does not know the correct answer, but it learns from trial and error since agent knows the reward of its action. When information about the environment does not exist, it acts randomly. However, as learning progresses, more regular actions are repeated and can find a goal. RL has several schemes such as state-action-reward-state-action (SARSA), Q-learning, deep Q-network (DQN), deep deterministic policy gradient (DDPG) and asynchronous advantage actor-critic algorithm (A3C). Among them, the Q-learning scheme is the most widely known algorithm. When the learning is completed, the destination learns the optimal policy which is a rule of the actions that maximizes the reward. In other words, the purpose of the Q-learning is to find an optimal policy. Q-learning is a suitable algorithm for unknown environment and can be used in future wireless cooperative communication where the environments are changed rapidly. Figure 3 shows the Q-learning agent-environment model. Agent takes action in environment and receives the feedbacks from the environment to find an optimal policy and the Q-function is also part of the agent. In the feedback process, an immediate reward is defined as \(r(s_{t},a_{t})\). A reward for the future situation caused by present action is received by using Q-value (\(Q(s_{t+1},a_{t+1})\)). The purpose of the Q-learning takes an action that can update the Q-table consisting of Q-values and maximize the reward from environment [14]. The formula of the Q-function is as follows,  
\[ \begin{split} Q(s_{t},a_{t})&\gets Q(s_{t},a_ {t})+\alpha(r(s_{t},a_{t})\\ &\quad+\gamma\max Q(s_{t+1},a_{t+1})-Q(s_{t},a_{t})),\end{split}  \tag{4}\]  
where the \(s_{t+1}\) denotes the next state when it takes an action \(a\) in the current state \(s\). The \(a_{t+1}\) means action that can be taken in next state \(s_{t+1}\). Furthermore, the \(\gamma\)\((0<\gamma<1)\) is a discount factor which is the weight of the current and future reward. The \(\alpha\)\((0<\alpha<1)\) is a learning rate which indicates whether the learning depends on the current or future learning information. As the learning is progressed, the Q-value is updated at each iteration and is stored in a Q-table. Table 1 shows the Q-table of Q-learning algorithm. Table 1 represents the situation where the \(N\) actions exist. First, the Q-table is initialized to zero and the Q-values are stored as time goes by. Therefore, optimal actions in given environment are founded through the learning in Q-learning algorithm. Furthermore, this paper uses the decaying-greedy algorithm for exploration and exploitation in order to choose the optimal action. In the generally known Q-learning algorithm, the destination selects an action by exploration and exploitation [15]. Exploration takes a random action to achieve more knowledge of the reward and the exploitation selects the best possible action based on the current knowledge of rewards. The action in this situation is as follows,  
\[a=\arg\max(Q(s,a)), \tag{5}\]  
\[a_{t}=\left\{ \begin{array}{cc}p,&\textit{probability}\ \varepsilon\\ \pi(s_{t}),&\textit{probability}\ 1-\varepsilon\end{array} ,\right. \tag{6}\]