# Enhanced Routing Algorithm Based on Reinforcement Machine Learning--A Case of VoIP Service
## 2 Theoretical Review  
### Reinforcement Learning  
RL is a Machine Learning technique in which there is an agent that interacts with the environment through actions and receives rewards for the actions taken. The RL problem can be summarized as, an agent interacting with an environment in order to maximize the accumulated reward over time [35].  
The generalization of the RL interaction process [35] is shown in Figure 1, where the Agent interacts with the Environment through an \(a_{t}\) action. This interaction leads to a new \(s_{t+1}\) state and generates a reward for the Agent.  
Figure 1: Generalized Reinforcement Learning Scheme.  
Through the rewards the agent estimates the action taken, and this knowledge is then used by the agent to adapt future decisions, which is usually controlled by the estimated value \(Q\). In general, the estimated value defines how good a given action is.  
The formulation of the RL optimization process can be represented as a Markov Decision Process (MDP) [35], introducing 4 sets \(S\), \(A\), \(P\), \(R\), where, \(S\) is a set of possible states of the agent; \(A\) represents the set of possible actions that an agent can take; \(P\) is defined as set of probabilities, in that an agent in a state \(s\), advances to a state \(s^{\prime}\) when opting for an action A. And finally the reward function \(R\), which generates the reinforcement that the agent receives for choosing action A.  
According to MDP the transition probabilities from \(s\) to \(s^{\prime}\) after taking action \(a\) (\(P_{ss^{\prime}}\),\(a\)), can be described as follows:  
\[{P_{ss^{\prime}}}^{a}=Pr\big{\{}s_{t+1}=s^{\prime}\mid s_{t}=s,a_{t}=a\big{\}}. \tag{1}\]  
The estimation reward values (\(E\)) for action \(a\) (\(R_{ss^{\prime}}\),\(a\)), from state \(s\) to \(s^{\prime}\), is defined by:  
\[{R_{ss^{\prime}}}^{a}=E\{r_{t+1}\mid s_{t}=s,a_{t}=a,s_{t+1=s^{\prime}}\}. \tag{2}\]  
The sets \(S\) and \(P\) can be defined by a set of estimation values \(Q\), which is dependent on the reward value obtained from an environment, and also from the current moment \(t\), when the corresponding action has been performed. The estimation function values are presented as follows:  
\[Q_{k+1}=Q_{k}+\alpha*[r_{k+1}-Q_{k}], \tag{3}\]  
where \(Q_{k}\) represents the estimation value on the previous step; \(Q_{k+1}\) is the current estimation value; \(r_{k+1}\) define the reward value for an action performed on the current step; \(\alpha\) represents step size parameter; and \(k\) is the current step number.  
One of the main questions about RL is to take advantage of the current actions that generate greater rewards or explore new actions in order to be able to obtain even better rewards. In order to maximize the rewards received, the agent must balance the need to explore new actions or take advantage of current ones.  
In RL, the most common methods for action selection are greedy, e-greedy and softmax methods [45]. The greedy selection of the action with the maximum estimation value all the time. The e-greedy selection of action with the maximum estimation almost every time, however, sometimes it explores new actions at random. The Softmax method [46] provides a dynamic change of selection probabilities of the actions. This change of selection probabilities of the actions occurs according to a predefined probability function, such as the Gibbs-Boltzmann distribution [35].