## 3 Reinforcement and Q-Learning in Routing
The first and most influential application of Q-learning to routing is _Q-routing_[16]. As in most RL routing protocols, the learning agent is a network node, and the Q-learning is applied in a distributed manner where each node \(x\) maintains a \(Q_{x}\) table. Q-routing introduced several design decisions that were later applied by many other algorithms. First, Q-routing reduces a distance metric instead of maximizing a reward; \(Q_{x}(d,y)\) is defined as the node \(x\)'s estimation of the latency from node \(y\) to destination \(d\). Furthermore, instead of exploring the solution space by sending data packets through sub-optimal paths, Q-learning introduced a separate channel for exchanging neighboring nodes' best Q values. When a node needs to recompute its own \(Q\) table, it will request \(T_{y}=\min_{z\in N_{y}}Q_{y}(d,z)\) from all neighbors. That makes the algorithm somewhat similar to classical Bellman-Ford. Finally, node \(x\) updates its table as:\[Q_{x}(d,y)\leftarrow(1-\alpha)Q_{x}(d,y)+\alpha(q+s+T_{y}) \tag{4}\]  
where \(q\) and \(s\) are the local queue and transmission times. Notice that because the \(Q\) value represents a latency that is not subject to discounting for further away nodes, \(\gamma=1\) is used. Q-learning-based routing has been adapted to various networks [17]. We will briefly mention some of the algorithms applied to ONs. One of the most influential Q-learning ON routing is _Delay Tolerant Reinforcement-Based_ (DTRB) [18]. DTRB is a flooding-based algorithm wherein messages are replicated, maximizing a reward computed by a dedicated distance-table gossiping algorithm. In DTRB, nodes maintain two tables, a table with the distances to every known node in the network and a table of rewards for every known message destination node. The distance stored in the first table is an estimation of the time needed to propagate a message to the target node. These temporal distance tables are maintained by exchanging time-stamped control messages. These messages flood information about the last time a given node was met in the network. Then, nodes use the time elapsed as a distance measure. This learned distance value is then used to compute a reward used in a conventional Q-learning scheme (see Equation (5)). A node computes the one-hop reward \(R\) for a given neighbor as \(e^{-k}\), where \(k\) is the time-distance measure stored in the distance table or 0 if the entry is older than a configuration parameter. Then, a Q _practicability of delivery_ value is computed as an estimation of the future rewards after taking a particular action. The discount factor \(\gamma_{x}\) is dynamic, getting smaller the faster that the neighborhood of \(x\) changes. This means that the algorithm favors nodes with low mobility. \[Q_{c}(d,x)\leftarrow(1-\alpha)Q_{c}(d,x)+\alpha(R+\gamma_{x}\times\max_{y\in N _{x}}Q_{x}(d,y)) \tag{5}\]  
The computed rewards are distributed in the same control messages mentioned and are subject to further exponential aging. Finally, messages are replicated to nodes with higher computed Q-values than their own. The basic idea of the algorithm is to distribute a routing metric through control messages and then use it as the immediate reward in a Q-learning scheme. The resulting Q-values are used as an estimation of the global cost of an opportunistic delivery path. An alternative is to integrate the routing metric within the Q-tables. For example, CARL-DTN [19] is a flooding protocol that uses Q-learning to learn a Q-value associated with every destination. Q-values are updated when nodes meet or go out of range. The Q-value combines the hop count with other node characteristics such as TTL, node popularity, or remaining power. This combination is achieved using a fuzzy logic controller (FLC). The update function for node \(c\) when meeting node \(x\), for destination \(d\) is:  
\[ \begin{split} Q_{c}(d,x)&\leftarrow(1-\alpha)Q_{c}( d,x)\\ &+\alpha(R(d,x)+\gamma\cdot FuzzTO\cdot\max_{y\in N_{x}}Q_{x}(d,y)) \end{split}