## 3 Reinforcement and Q-Learning in Routing  
Reinforcement learning (RL) is a machine learning (ML) technique based on the exploration of the solution space by learning agents. These agents interact with the environment or _state_ through actions that produce a reward. These rewards serve as feedback to inform the agent about the appropriateness of the action in the given scenario, allowing it to learn a policy to produce optimal behavior. Designing an RL system consists of defining the 4-tuple \(<~{}S\), \(A\), \(P\), \(R\)\(~{}>\), where \(S\) and \(A\) are the sets of states and actions; \(P:S\times A\to S\) is a transition matrix, potentially stochastic. \(S\), \(A\), and \(P\) define a Markov decision process (MDP) described as \(s_{i+1}\leftarrow\delta(s_{i},a_{i})\)which can be either deterministic or not. \(R:S\times A\times S\rightarrow\mathbb{R}\) is the reward function that assigns a state transition value. Rewards themselves can also be either deterministic or not. Because the rewards are obtained from a single state transition, but the agent is expected to produce an effective sequence of actions, a mechanism to calculate a global reward \(V\) is also needed. Thus, the RL problem can be described as finding the optimum policy \(\pi:S\to A\) to select the best action in a given state, as to maximize a cumulative reward \(V^{\pi}:S\rightarrow\mathbb{R}\) where the \(S\) indicates the starting state for applying the policy \(\pi\). The sequence of states evaluated by \(V^{\pi}\) must be produced by iteratively evaluating \(\delta\) with the available actions in each moment. The reward itself is usually computed as the discounted cumulative reward from the produced sequence of states, starting from a state \(s_{0}\), as:  
\[V^{\pi}(s_{0})\rightarrow\sum_{i=0}^{\infty}\gamma^{i}r_{i} \tag{1}\]  
where \(0\leq\gamma<1\) is a parameter that controls an exponential reduction in the weight given to instant rewards \(r_{i}\) further from the starting state. This problem is challenging because to evaluate \(V^{\pi}\), the state sequence produced by \(\delta\) and the resulting rewards must be known, which is not always possible. In particular, the state transitions caused by actions or the resulting rewards might be non-deterministic. To overcome the difficulty of optimizing a policy for an unknown sequence of states, actions, and rewards, Q-learning [13] proposes using a particular evaluation function:  
\[Q(s,a)\gets r(s,a)+\gamma\max_{a^{\prime}}Q(\delta(s,a),a^{\prime}) \tag{2}\]  
This function says that the evaluation of an action is the sum of the immediate reward and the best achievable evaluation from the action's target state. Notice that this is a recursive definition and that both \(r(s,a)\) and \(\delta(s,a)\) can be observed as they are only evaluated once in the present state \(s\) (they are sampled). This equation iteratively approximates the \(Q\) function and obtains the associated policy in the process. For this, a learning agent stores the learned \(Q(s,a)\) values in a table. Then, it repeatedly evaluates policies in _epochs_. After selecting an action \(a\) in state \(s\), it updates the \(Q\) as follows:  
\[ \begin{split} Q(s,a)&\leftarrow(1-\alpha)Q(s,a)\\ &+\alpha(r(s,a)+\gamma\max_{a^{\prime}}Q(\delta(s,a),a^{\prime}) \end{split}  \tag{3}\]  
where \(\alpha\) is a learning parameter controlling the convergence speed. As all actions for all states are sampled repeatedly, the \(Q\) estimation converges to the value of Equation (2) [13]. During the system's training, the optimal known policy is to select the highest valued action in any state. As usual in ML, a balance must be found between exploitation (using the highest valued actions) and exploration (evaluating alternate actions). The fact that Q-learning correctly takes into account the future effect of actions, and provides a policy that does not depend on previous knowledge or domain model, made it very useful for attacking the problem of routing in dynamic networks [14; 15].