# Graph Neural Networks for Routing Optimization: Challenges and Opportunities
## 5 Reinforcement Learning for Routing Optimization  
### Overview  
Compared to supervised learning, reinforcement learning is more favorable for routing optimization because of its modest usage of memory and computational resources [11; 108]. Many network nodes have limited energy and communication resources, for example,  
\begin{table}
\begin{tabular}{p{56.9 pt} p{56.9 pt} p{56.9 pt} p{56.9 pt} p{56.9 pt} p{56.9 pt}} \hline \hline
**Study** & **Scenario** & **Proposed Solution** & **Performance** & **Routing Policy** &
\begin{tabular}{c} **Deployment** \\ **Mode** \\ \end{tabular} \\ \hline
[53] & \begin{tabular}{c} Computer \\ Network \\ \end{tabular} & \begin{tabular}{c} GQNN \\ (GG-NN-based) \\ \end{tabular} & \
\begin{tabular}{c} GQNN achieves accuracies \\ of 98\% and 95\% for shortest \\ path and min-max routing, respectively. \\ \end{tabular} &
\begin{tabular}{c} Shortest path or \\ min-max fair \\ routing \\ \end{tabular} & Distributed \\ \hline
[104] & \begin{tabular}{c} Computer network \\ \end{tabular} & \begin{tabular}{c} GN-based model \\ \end{tabular} & \
\begin{tabular}{c} The proposed model \\ achieves 61.0\% accuracy for predicting the routing table of the genetic algorithm, with a 150\(\times\) faster \\ prediction time. \\ \end{tabular} &
\begin{tabular}{c} Bandwidth \\ utilization \\ maximization \\ \end{tabular} & Centralized \\ \hline
[105] & \begin{tabular}{c} Computer \\ Network \\ \end{tabular} & \begin{tabular}{c} GADL \\ (Graph-aware \\ convolutional-based) \\ \end{tabular} & \begin{tabular}{c} GADL achieves an accuracy \\ of 86.55\% for predicting the next forwarding node and a lower average network \\ latency than OSPF. \\ \end{tabular} & \
\begin{tabular}{c} GADL achieves an accuracy \\ of 86.55\% for predicting the \\ next forwarding node and a \\ lower average network \\ latency than OSPF. \\ \end{tabular} &
\begin{tabular}{c} Latency \\ minimization \\ \end{tabular} & Centralized \\ \hline
[106] & \begin{tabular}{c} Computer network \\ \end{tabular} & NGR (GNN-based) & \
\begin{tabular}{c} NGR achieves 100\% routing \\ reliability and gain \\ performance close to the \\ optimal solutions. \\ \end{tabular} &
\begin{tabular}{c} Shortest-path \\ routing or load \\ balancing \\ \end{tabular} & Distributed \\ \hline
[107] & \begin{tabular}{c} Satellite network \\ \end{tabular} & \begin{tabular}{c} GLR (GCN-based) \\ \end{tabular} & \
\begin{tabular}{c} GLR outperforms \\ brute-force and shortest \\ path routing algorithms in \\ terms of end-to-end &
\begin{tabular}{c} Delay \\ minimization \\ \end{tabular} & Centralized \\ \multicolumn{4}{p{56.9 pt}}{} \\ \multicolumn{4}{p{56.  
those in wireless sensor networks or satellite networks, which require a routing algorithm to achieve faster convergence to optimal decision-making.  
By following the general RL scheme shown in Figure 5, the state space is defined using historical traffic status measurements, such as end-to-end delay, throughput, and energy efficiency, which are periodically collected by the agent from the network environment. In various studies, it can be formulated as a matrix or vector of different variables. The action space is defined as the routing policy performed by the agent. Examples of specific action choices include the split ratio for multipath routing and the weight matrix of individual links. GNN models are used within the agent to generate the routing decision. The reward function is defined as the optimization objective of the routing algorithms, for example, the different QoS parameters. Some examples of reward function design for routing include energy-saving optimization, end-to-end delay minimization, throughput maximization, and average flow completion time minimization. The reward function is important in RL-based routing solutions because it promotes solution convergence.