# Virtual Network Function Embedding under Nodal Outage Using Deep Q-Learning
## 4 Deep Reinforcement Learning  
### Reinforcement Learning  
Reinforcement Learning is a learning process where, at each time-step, the agent observes a state \(S\), and, accordingly, an action \(A\) is executed. Based on this action, the environment provides reward and the next state, as shown in Figure 3.  
From the obtained observations (i.e., rewards and next state), the agent's goal is to improvise the decision strategy for achieving an optimal policy to attain an optimal solution. In other words, RL is a self-learning process where the models are trained with the help of online data, where these models optimize the problem by accumulating the rewards from the environment and avoiding receiving any penalties. These trained models will maintain the performance even during the network dynamformulated the optimization problem in terms of the Markov Decision Process (MDP) because MDP establishes a mathematical structure for examining the decision-making problems, this decision-making process is partially random and supervised by the agent. Thus, the RL technique uses MDP framework for solving the optimization problem [18]. RL's main aim is to find an optimal policy \(\pi^{*}=S\to A\) for the decision-maker (agent). This optimal policy for a state is obtained by maximizing the optimal action-value function, i.e.,  
\[\pi^{*}(s_{t})=\operatorname*{arg\,max}_{a}Q^{*}(s_{t},a_{t}) \tag{8}\]  
This action-value function is estimated using the Bellman Equation, i.e.,  
\[Q^{\pi}(s_{t},a_{t}) = \sum_{s_{t+1}}P(s_{t+1},r_{t}|s_{t},a_{t})(r_{t}(s_{t},a_{t})\,+\, \gamma\sum_{a_{t+1}}\pi(a_{t+1}|s_{t+1})(Q^{\pi}(s_{t+1},a_{t+1})) \tag{9}\]  
\(s_{t}\), \(a_{t}\), and \(r_{t}\) are the state, action, and reward obtained at time-step \(t\), respectively. Moreover, \(s_{t+1}\) and \(a_{t+1}\) are the state and action for next time-step, and \(P(s_{t+1},r_{t}|s_{t},a_{t})\) is the probability of next state and reward for a given current state and action. In addition, \(\pi(a_{t+1}|s_{t+1})\) is the probability of selecting the next action under a \(\pi\) policy with the \(\gamma\) discounting factor. However, to estimate the optimal action-value, the most efficient and commonly used literature approach is Q-Learning (QL) [10]. QL is an off-policy model-free algorithm, where the Target policy (This policy is used to estimate the action-value by the agent.) learns from the Behaviour policy (This policy is used for choosing an action by the agent.) to achieve an optimal solution. Thus, Equation (9) is modified as  
\[Q^{\mu}(s_{t},a_{t})=r_{t}(s_{t},a_{t})+\gamma\max_{a}Q^{\mu}(s_{t+1},a) \tag{10}\]  
under the \(\mu\) policy. In other words, the action-value (also known as Q value) is defined as an expected discounted reward when an action is executed for a state under a policy. QL agent intends to explore the unknown environment by executing an action at each time-step for the observed state. The learned values are stored in a form of table called a Q-table as shown in Figure 4. These Q-table values provide crucial information about the state-action pair, which supports in discovering the best action for the current state. Thus, the Q value is estimated in an iterative process, which will be effective for smaller-scale space but not for larger-scale space due to the curse of dimensionality [19]. Figure 3: Reinforcement Learning. In order to address the problem, Deep Reinforcement Learning (DRL) is implemented, where the Q-table is replaced with the Deep Neural Network (DNN) to approximate the Q values, as seen in Figure 5. RL is considered to be unpredictable or highly prone to divergence where a nonlinear function approximator such as a neural network is used to represent the Q-value function. This divergence is due to the correlation between the transitions, where a trivial variation to the Q value can impact the policy, causing a substantial effect on the Q value and target value [20].