# Reinforcement Learning-Based Routing Protocols in Flying Ad Hoc Networks (FANET): A Review
## 3 Fundamentals of Reinforcement Learning (RL)
### Markov Decision Process  
Reinforcement learning is known as an experience-based method. This means that the agent experiences various actions in a trial-and-error manner to improve its future choices. This problem can be formulated as a Markov decision process (MDP) [17; 18]. The important definitions of RL are presented as follows:  
**Definition 1**. : _MDP includes a tuple \((S,A,P,R,\gamma)\):_  
* \(S\) _indicates the state space._
* \(A\) _indicates the action space._
* \(R\) _is the reward function, which is defined as_ \(R=\mathbb{E}[R_{t+1}|S_{t}=s,A_{t}=a]\)_._
* \(P\) _is defined as the state transition probability_ \(P=\mathbb{P}[S_{t+1}=s^{\prime}|S_{t}=s,A_{t}=a]\)_._
* \(\gamma\) _indicates the discount factor, where_ \(\gamma\in[0,1]\)_._  
_In MDP, the next state depends only on the current state and does not depend on the previous states._  
\[\mathbb{P}[S_{t+1}-S_{t}]=\mathbb{P}[S_{t+1}-S_{1},...,S_{t}]. \tag{1}\]  
_In finite MDP, there are a limited state set, a finite action set, and a dynamic environment. Furthermore, the probability of each next state-reward pair such as \((s^{\prime},r)\) based on the current state-action pair \((s,a)\) can be formulated as follows:_  
\[p\big{(}s^{\prime},r|s,a\big{)}\doteq\Pr\{S_{t+1}=s,R_{t+1}=r|S_{t}=s,A_{t}=a\}. \tag{2}\]  
_In the learning process, the agent is responsible for maximizing \(G_{t}=R_{t+1}+R_{t+2}+\cdots+R_{T}\), so that \(G_{t}\) is the sum of the rewards obtained from the learning process and \(T\) reflects the last time step. If there is an episodic task, meaning that this task includes a final state, the mentioned function is used for calculating \(G_{t}\). However, if there is a continuous task, meaning that this task has no final state, i.e., \(T=\infty\), we can not use the mentioned function._  
**Definition 2**. : \(G_{t}\) _means the sum of discounted feedback received from the environment in the long term. It is calculated according to Equation (3):_  
\[G_{t}=\sum_{k=0}^{\infty}\gamma^{k}R_{t+k+1} \tag{3}\]  
_where, \(G_{t}\) is the long-term feedback. \(\gamma^{k}\in[0,1]\) represents the discount factor and \(R_{t+k+1}\) indicates the reward obtained from environment at the moment \(t+k+1\)._  
**Definition 3**. : _In RL, policy defines the results of a state and a certain action. When the agent is in a particular state, it must select its next action based on this policy \(\pi\), which is a probability distribution on the actions performed in the given states._  
\[\pi(a|s)\doteq\mathbb{P}[A_{t}=a|S_{t}=s] \tag{4}\]  
_where, \(\pi\) is the policy, which determines the probability of performing the action \(a\) in the state s. Based on the policy \(\pi\) and the feedback \(G_{t}\), two value functions with regard to the expected feedback can be obtained._  
**Definition 4**. : _State-value function (\(v_{\pi}(s)\)) represents the expected feedback when the agent is in the state s and follows the policy \(\pi\)._  
\[v_{\pi}\doteq\mathbb{E}_{\pi}[G_{t}|S_{t}=s]=\mathbb{E}_{\pi}\Bigg{[}\sum_{k =0}^{\infty}\gamma^{k}R_{t+k+1}|S_{t}=s\Bigg{]}. \tag{5}\]  
**Definition 5**. : _Action-value function (\(q_{\pi}(s,a)\)) indicates the expected feedback in the state s when the agent chooses the action \(a\) and follows the policy \(\pi\)._  
\[q_{\pi}(s,a)\doteq\mathbb{E}_{\pi}[G_{t}|S_{t}=s,A_{t}=a]=\mathbb{E}_{\pi} \Bigg{[}\sum_{k=0}^{\infty}\gamma^{k}R_{t+k+1}|S_{t}=s,A_{t}=a\Bigg{]}. \tag{6}\]_Both value functions are calculated based on the Bellman equation:_  
\[v_{\pi}(s)=\sum_{a}\pi(a|s)\sum_{s^{\prime},r}p\big{(}s^{\prime},r|s,a\big{)} \big{[}r+\gamma v_{\pi}\big{(}s^{\prime}\big{)}\big{]},\ \ \forall\ s\in S. \tag{7}\]  
_The RL algorithm converges when the agent finds the optimal policy \(\pi^{*}\) for all available policies in a certain state. The optimal policy \(\pi^{*}\) is used to calculate the optimal state-value function and the optimal action-value function._  
**Definition 6**.