# Deep Reinforcement Learning for Routing in Uncertain DTNs with Graph Neural Networks

Valentin Negrelli, Renato Cherini, Juan Andrés A Fraire

► To cite this version:

Valentin Negrelli, Renato Cherini, Juan Andrés A Fraire. Deep Reinforcement Learning for Routing in Uncertain DTNs with Graph Neural Networks. WiSEE 2025 - IEEE International Conference on Wireless for Space and Extreme Environments, Oct 2025, Halifax, Canada. pp.1-6, 10.1109/WiSEE57913.2025.11229839. hal-05413586

HAL Id: hal-05413586

https://hal.science/hal-05413586v1

Submitted on 12 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Deep Reinforcement Learning for Routing in Uncertain DTNs with Graph Neural Networks

Valentin Negrelli*, Renato Cherini†, Juan A. Fraire‡§,

*Facultad de Matemática, Astronomía, Física y Computación (FAMAF), Universidad Nacional de Córdoba, Argentina

†Facultad de Ciencias Exactas, Físicas y Naturales (FCEFyN), Universidad Nacional de Córdoba, Argentina

‡CONICET - Universidad Nacional de Córdoba, Córdoba, Argentina

§Inria, INSA Lyon, CITI, UR3720, 69621 Villeurbanne, France

**Abstract**—We address the routing optimization problem in Delay/Disruption Tolerant Networks under uncertain contact plans, where contact time bounds are known but link availability is probabilistic and subject to failures. We propose GROGU (Graph-based Routing for Optimizing under GNN-driven Uncertain DTNs), a novel decentralized routing algorithm that models forwarding decisions as a partially observable Markov decision process and leverages Deep Reinforcement Learning with a Graph Neural Network architecture. GROGU learns a single, reusable routing policy deployable across all nodes, using Monte Carlo-driven simulated experiences to maximize the successful delivery probability while adapting to topology changes such as node or link failures without retraining. We evaluate GROGU on synthetic and realistic satellite network topologies, comparing it against state-of-the-art methods including RUCoP, Lightweight Scheduler Sampling, Q-learning, and Contact Graph Routing. Results show that GROGU achieves competitive delivery performance, robust adaptability to unforeseen link outages, and fast convergence, albeit at higher training costs.

**Index Terms**—Delay-Tolerant Networking, Contact Graph Routing

## I. INTRODUCTION

The Delay-Tolerant Networking (DTN) architecture enables robust data exchange in environments with long delays, frequent disruptions, and no persistent end-to-end paths, such as near-Earth and deep-space networks [1]. It overcomes these challenges via a store-carry-and-forward paradigm that relaxes the need for continuous connectivity. The Bundle Protocol [2] is its primary realization, with proven deployments in terrestrial, aerial, and space systems [3].

In DTNs, connectivity is defined by contacts—finite intervals when two nodes can exchange data. In space networks, these contacts are often predictable, enabling scheduled DTNs. Using orbital propagators and communication models, operators can precompute a contact plan that encodes the future topology. This plan guides centralized or onboard routing, forming the basis of state-of-the-art schemes such as Contact Graph Routing (CGR) [4].

Perfect knowledge of the contact plan is rarely achievable. Interference, node failures, ephemeris errors, and environmental factors can disrupt predicted contacts. Uncertain DTNs address this by assigning probabilistic availability to contacts, enabling multi-copy forwarding to improve successful delivery probability (SDP). However, prior work on probabilistic DTNs [5] does not fully capture the impact of incomplete or

inaccurate plans, and extending scheduled routing like CGR to handle such uncertainty remains challenging [6].

Routing in uncertain DTNs has been modeled using Markov Decision Processes (MDPs), enabling optimal multi-copy forwarding under probabilistic link failures [7]. While provably optimal with global state knowledge, these methods suffer from exponential state-space growth and prohibitive computational and memory costs, making them impractical for large-scale or real-time use. Global information policies are further hindered in partitioned networks, where only local knowledge is available. Although statistical and learning-based approximations [8], [9] offer partial solutions, efficient and formally grounded routing under uncertain contact plans remains unresolved.

In this work, we introduce GROGU (Graph-based Routing for Optimizing under GNN-driven Uncertain DTNs), a novel decentralized routing algorithm for uncertain DTNs that leverages Deep Reinforcement Learning (DRL) with a Graph Neural Network (GNN) architecture. GROGU combines Monte Carlo (MC) episode simulation with GNN-based state-action encoding, enabling the policy to adapt to varying topologies and link uncertainties. We evaluate the method on both synthetic and realistic satellite network topologies, comparing it against state-of-the-art approaches such as RUCoP, Lightweight Scheduler Sampling (LSS), Q-learning, and CGR. Our results show competitive delivery performance and strong adaptability to unforeseen network changes, albeit at higher training costs.

The remainder of this paper is structured as follows. Section II reviews the relevant background on MDP, existing uncertain-contact routing approaches, and DRL methods. Section III presents our proposed DRL-based routing architecture. Section IV details our experimental setup, scenarios, and results. Finally, Section V summarizes our findings and discusses future research directions.

## II. BACKGROUND

### A. Markov Decision Processes (MDP)

MDPs provide a mathematical framework capturing the interaction between non-deterministic and probabilistic choices [10], appropriate for modeling decision making under probabilistically quantified uncertainty.
<figure><img src="image_2.png" /><figcaption>Figure 1: Example of an uncertain contact plan.</figcaption></figure>

An MDP is defined by the tuple $(S, A, T, s_0)$, consisting of a finite set of states $S$, a finite set of actions $A$, the transition probability function $T: S \times A \times S \to [0, 1]$, and an initial state $s_0 \in S$. Usually, the goal is to maximize the probability of reaching a target subset of states from $s_0$. In particular, we are interested in determining the decisions leading to such maximizing value. A policy or scheduler is a function $\pi: S \to A$ that defines such decisions, solving any possible non-determinism.

Consider an uncertain contact plan like the one illustrated in Fig. 1. A state in $S$ is defined by the number of copies held by each node at a specific time slot. An action in $A$ specifies the number of data copies to transmit—including zero—over a contact occurring during that time slot, represented by the arrows in the figure. Each contact is annotated with its failure probability, captured by the transition function $T$. We assume that the sender node can detect whether the transmission succeeded; accordingly, it deletes the transmitted copies upon success or retains them if the transmission fails (i.e., acknowledged communication).

Optimal global schedulers can be computed using probabilistic model checkers [11], [12], [13] that explicitly generate and store the entire MDP state space, solving reachability via Bellman equation-based linear programming or iterative algorithms [14], [15]. However, these generic tools lack optimizations for DTN routing and suffer from state space explosion in complex networks [16].

Schedulers derived this way rely on full global system knowledge, requiring nodes to know the location of all message copies—including remote or disconnected nodes—which is infeasible in highly partitioned DTNs. Consequently, routing decisions must be made in a distributed manner based on partial local information [17], a scenario not addressed by these model checking tools.

## B. RUCoP

RUCoP (Routing under Uncertain Contact Plans) [18] provides an analytical method to determine routing decisions that optimize the SDP under an uncertain contact plan. Its core insight is that, by including the current time slot in the state representation, the resulting MDP becomes acyclic. Leveraging this property, RUCoP constructs only the “optimal” part of the MDP by recursively applying the Bellman equations in reverse order, traversing the contact plan backward and retaining only the transitions that maximize the objective.

RUCoP computes optimal routing by first identifying goal states in the final time slot, then iteratively working backward through time. At each step, it examines previously explored states and builds all possible transitions that can reach them without failed contacts. It then updates the set of predecessor states, selecting the best decision for each and computing the associated delivery probability. At completion, RUCoP provides all reachable states with non-zero delivery probability, the optimal action in each state (usable for routing tables), and their success probabilities. Although RUCoP allows multiple transmissions per slot—introducing potential cycles—it removes them since they reduce the SDP, yielding an acyclic MDP. While RUCoP ensures optimal decisions under global knowledge, its local variant must be used for decentralized schedulers.

## C. Lightweight scheduler sampling (LSS)

For discrete-time Markov chains (DTMCs)—MDPs with at most one enabled action per state—Monte Carlo simulation or Statistical Model Checking (SMC) [19] estimates reachability probabilities by sampling $n$ random paths and averaging successes. This yields statistically correct results with constant memory, assuming efficient simulation without storing the entire state space. SMC is also easily parallelizable.

LSS [20] extends SMC to general MDPs while maintaining constant memory. It samples a set $\Sigma$ of $m$ schedulers, heuristically selects the one $\sigma_{max} \in \Sigma$ with the highest estimated reachability, and performs SMC on the MDP combined with such scheduler to estimate success probability. However, unless $\Sigma$ contains an optimal scheduler identified by the heuristic, this produces only an underapproximation with statistical error. LSS performs well if near-optimal schedulers are frequent in the sampling space, but poorly if success requires many precise decisions.

While LSS targets global-information schedulers, it can be adapted to local-information schedulers [8].

## D. Q-learning

Reinforcement learning (RL) [21] is a machine learning approach in which agents learn to take actions that maximize cumulative reward in stochastic environments. The interaction between an agent and its environment is typically modeled as MDP: the agent selects actions, and the environment determines state transitions and associated rewards.

The well-established RL method, Q-learning [22], maintains a Q-function $Q: S \times A \to \mathbb{R}$, typically a table, assigning a score to any possible actions $a$ in a given state $s$. At each time step, the agent chooses to execute an action, according to a parameter $\epsilon$, either randomly or greedily based on the current estimate of $Q$. Then, the agent observes the resulting state and updates $Q$ using a Temporal Difference (TD) rule, derived from the Bellman optimality equation:

$$Q(s, a) \leftarrow Q(s, a) + \alpha[r + \gamma \max_{a'} Q(s', a') - Q(s, a)]$$

The Q-function is updated based on the difference between the current estimate and a new estimate composed of the
immediate reward $r$ and a discounted future reward $\gamma$ from the estimated best next action. This error reflects the surprise of the outcome and drives learning. As training advances, the learning rate $\alpha$ and the exploration parameter $\epsilon$ are typically decayed, enabling convergence toward an optimal policy.

Q-learning, as previously described, learns a global-information scheduler by training a single agent with full system knowledge. In contrast, [9] proposes a multi-agent reinforcement learning approach where each DTN node acts as an independent agent learning from partial local information via concurrent learning [23]. Each agent updates its own Q-function based on local observations, resulting in a non-stationary environment due to other learners' actions, which breaks standard Q-learning convergence guarantees [24]. However, this approach reduces the Q-function size from exponential to linear in the number of nodes, as each agent's state space depends only on local components.

### E. Graph Neural Networks (GNN)

GNNs are machine learning models with a strong inductive bias for processing graph-structured data [25]. They are particularly suited for domains with sparse elements and irregular relationships. Unlike models tailored for linear or grid-like data—such as Multilayer Perceptrons (MPLs), Recurrent Neural Networks, or Convolutional Neural Networks—GNNs explicitly leverage the underlying graph structure during learning. Various architectures have been proposed, including Graph Convolutional Networks and Graph Attention Networks, effectively addressing tasks involving complex relational data using diverse learning strategies.

Gilmer et al. [26] introduced the Message-Passing Neural Network (MPNN) framework, which generalizes many GNN variants. In this framework, each graph element (node or edge) is initialized with input features and iteratively updates its state by aggregating information from neighboring elements, following the graph topology. Final states are then passed through a domain-specific function to produce the task output.

MPNNs propagate information via an iterative message-passing scheme. At each step $l$, a node $v$ aggregates messages from its neighbors $w \in N(v)$. Each message is computed by a shared function $M^l$ using the current states of $v$ and $w$ ($h_v^l, h_w^l$), and the edge state $e_{vw}^l$. The incoming messages are combined using a permutation-invariant aggregation function $\odot: m_v^{l+1} = \odot_{w \in N(v)} M^l(h_v^l, h_w^l, e_{vw}^l)$. The state of $v$ is updated by using the previous state $h_v^l$, aggregated messages $m_v^{l+1}$ and a shared update function $U^l: h_v^{l+1} = U^l(h_v^l, m_v^{l+1})$ where $M^l$ and $U^l$, which are specific for each iteration $l$, are learned differentiable functions, typically MLPs. Sharing the same functions across all nodes keeps the model size tractable and enables generalization to graphs with varying structures and sizes. After a fixed number of iterations, a *readout function*—typically an MLP—produces the output, which can range from a single value to a graph with node and edge attributes, depending on the task.

<figure><img src="image_3.png" /><figcaption>Figure 2: Graph representing available action in $t_0$.</figcaption></figure>

## III. METHODS

In contrast to classical Q-learning, which uses tabular TD updates, our method employs Deep Reinforcement Learning (DRL) with a GNN to represent the state-action space, combined with MC episode simulation for learning. A key advantage of GNNs is their ability to approximate and generalize functions, enabling a single model to operate across different nodes and scenarios in the satellite network. This eliminates the need for node-specific training and avoids the complexity of distributed learning, while still supporting decentralized decision-making at inference time. The model captures shared routing patterns and can be uniformly deployed across the network.

### A. Graph model

In GROGU, the graph has as many connected components as available actions at a given time. Each component encodes the local state of a node and one of its available actions, within the context of the future contact plan from the action's execution onward. Formally, at time $t$, the directed multigraph $G = \langle V, E \rangle$ has $V \in \mathbb{N} \rightarrow \mathbb{R}^n$, representing DTN nodes as attributed vertices, and $E \in \mathbb{N} \rightarrow \mathbb{R}^m \times \text{dom}(V) \times \text{dom}(V)$, representing timed contacts between nodes, occurring at any time $t' \ge t$, and the number of transmitted copies. Multiple edges between node pairs are allowed, as DTN nodes may have several contacts. Edges are directed, reflecting the often unidirectional or asymmetric nature of space communications.

Input graphs use 4-dimensional node vectors, encoding the node's role (sender, intermediate, or destination) using one-hot encoding, and its available copies as a normalized value between 0 and 1. Only one sender per component is allowed, and only its copy count is provided due to the locality constraint. Edges are also 4-dimensional, encoding single values for contact time, the number of transmitted copies (both normalized), transmission failure probability, and a bit indicating whether the transmission occurs during the contact. Edges are directed opposite to transmission to match GNN information flow. In each component, only one edge—outgoing from the sender and occurring at $t$—has the transmission flag set and specifies the number of transmitted copies. Fig. 2 shows the graph at $t_0$ derived from the contact plan in Fig. 1, using abstract attribute values.

Intermediate graphs use higher-dimensional features to support learning. In our experiments, 30-dimensional node vectors
sufficed, while edge dimensionality remained fixed. The output graph assigns each action a score, given by the 1-dimensional attribute of its sender node.

## B. Model architecture

Following the MPNN framework, GROGU consists of L stacked layers and a final readout function. Each layer updates node attributes by aggregating information from neighbors via a convolution operator. Specifically, given input features $h^l$ for each node v and its neighbors $w \in \mathcal{N}(v)$, the layer multiplies them by filter weights, merges the results, and computes the output features $h^{l+1}$. Crucially, the weights are conditioned on edge attributes, which encode essential routing information. The layer can be defined node-wise as:

$$h_v^{l+1} = \sigma(\Theta^l h_v^l) + \sum_{w \in \mathcal{N}(v)} h_w^l \cdot \Theta_{\text{MLP}}^l(e_{vw})$$

where $\Theta^l$ is a learnable weight matrix for node v, while $\Theta_{\text{MLP}}^l$ is a learnable MLP that filters neighbor contributions based on edge attributes $e_{vw}$. $\sigma$ denotes a non-linear activation. Each layer is encapsulated within an Antisymmetric Layer [27] to prevent oversquashing phenomena and, except for the final layer, is followed by Batch Normalization [28] and Pair Normalization to facilitate training and mitigate the typical oversmoothing observed in deep GNNs.

Recall that the network is designed to be able to select the best action, serving as a scheduler. After the final convolutional layer, a readout function maps source node attributes of each action to an N-dimensional vector, providing a score for each action. N is an upper bound on any node's number of neighbors, ultimately the total number of nodes in the network.

## C. Learning strategy methodology

Instead of TD updates, our training uses a MC approach. Each episode runs from the initial source node to successful delivery or termination, and the full trajectory is used to update the GNN. This is convenient given the typically short paths in satellite-based DTN routing. Unlike TD methods, which estimate returns using the current Q-function, the MC strategy uses the actual total return, yielding an unbiased, lower-variance estimate for each visited state-action pair. The Q-function update is given by:

$$Q(s, a) \leftarrow Q(s, a) + \alpha[G - Q(s, a)]$$

where G denotes the discounted empirical return, averaged over many independent runs of the full episode. This approach enables learning from complete trajectories—crucial in our setting, where rewards are sparse, delayed (only upon delivery), and probabilistic failures mask the effectiveness of otherwise good decisions.

To further stabilize learning, we use an Experience Replay buffer [29], initially filled with successful episodes to reduce the risk of early convergence to suboptimal policies caused by failure-dominated feedback. As training advances, older trajectories are gradually replaced. From the midpoint of

<figure><img src="image_4.png" /><figcaption>Figure 3: Binomial tree topology.</figcaption></figure>

training onward, experiences are constrained to avoid some of the actions with the highest return, thereby promoting a broader exploration of the solution space. This policy ensures continuous adjustment and enhances the adaptability of the resulting scheduler when facing unforeseen changes (as analyzed in Section IV-C).

To prevent overfitting, we incorporate an early stopping mechanism. After a burn-in period, training pauses periodically to evaluate the policy via simulated SDP. While training continues until completion, the final model is selected based on the parameters that yield the best SDP performance observed throughout the process.

# IV. EVALUATION

We adopt scenarios from [9] to preliminarily assess GROGU's performance, enabling comparison with the local versions of RUCoP, LSS, Q-learning discussed in Sec. II, and CGR as baselines. We evaluate the models using SDP as the primary metric, and briefly discuss memory usage and computation time. We also conduct a separate experiment to assess adaptability, measuring performance under unforeseen changes to the contact plan beyond its inherent uncertainty.

## A. Scenarios

To evaluate how increasing the topological complexity affects the efficacy of the routing policy, we use a family of contact plans with a binomial tree topology, as shown in Fig. 3. Contact timing follows a left-to-right, top-to-bottom order. As tree depth increases, so does the number of nodes and candidate paths. For instance, a 6-level tree yields 32 nodes and up to 32 simple paths per node; with 3-copy forwarding, over 91,000 actions must be considered.

We also employ a realistic ring road satellite topology exported from high-precision orbital propagators to assess effectiveness. Specifically, we use a low-Earth orbit Walker constellation of 16 satellites, as described in [30], equipped with inter-satellite links, allowing multi-hop routing between satellites and ground terminals.

## B. Experimental setup

Trained models are composed of 7 convolutional layers, each using a 2-layer MLP and Exponential Linear Unit as activation function. Training is performed by applying the
<figure><img src="image_5.png" /><figcaption>Figure 4: SDP for binomial networks with varying complexity.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 5: SDP for the ring road network.</figcaption></figure>

Huber loss, Adam stochastic gradient descent, and backpropagation, with a hard limit of 2500 episodes and early stopping enabled from episode 1000. The experience buffer holds 10,000 trajectories, batch size is set to 51,2, and learning rate to 0.0005. Training was performed on CPU, using an AMD EPYC 7532 (32 cores, 64 threads, 2.4-3.3 GHz) with 128 GB of memory.

Baseline results are from the original work, run on an Intel Core i5-5300U (2 cores/4 threads, 2.3-2.9 GHz) with 12 GB RAM. The LSS models use 1,000 scheduler samples, while Q-learning models are trained over 10,000 episodes.

### C. Analysis

Fig. 4 shows SDP results for binomial topologies with 4 to 8 levels, 3 copies, and a link failure probability of 0.1. In this case, we are interested in evaluating the performance with respect to increasing topological complexity. In all cases, our SDP results are averaged over a total of 900 runs, using three trained models.

GROGU variants perform comparably to the baselines. While they do not yield the highest SDP, performance remains stable as complexity increases. Time and memory costs, however, are significantly higher (additionally, one must account for the differences in hardware used in each case). Memory

usage ranges from 380 MB (4 levels) to 7.5 GB (8 levels). This high cost is due to each possible action being encoded using the full graph of the future contact plan. Training time varies from 24 minutes to 6 hours. These values are between one and two orders of magnitude higher than the costs associated with the LSS and Q-learning models. RUCoP, by contrast, becomes intractable beyond 7 levels and 3 copies.

We also evaluate a representative case of the ring-road topology scenario, varying failure probability from 0.1 to 0.8, and the number of copies from 1 to 3 (indicated in parentheses in the figure) In this case, a remote node transmits data through the constellation to the ground station (nodes 8 and 32 in [30]) over a 2-hour contact plan. Results in Fig. 5 show—similarly to the previous case—strong performance. Computational costs follow the same trends observed in the binomial topology case.

As expected, the complexity of GROGU is not comparable to models like LSS or classical Q-learning. However, we believe this added cost is justified by the flexibility of neural models to adapt to changing conditions. To assess this, after training the models under a given level of link uncertainty, we tested their performance over a modified contact plan where some links are unexpectedly down (i.e., failure probability set to 1). For the previous ring-road topology, we identified a set of links predominant in routing and evaluated both GROGU and LSS in cases where up to three of these key links fail simultaneously, while the remaining links retain their original failure probabilities. Fig. 6 shows the proportion of average SDP retained across different cases, varying both the failure probability and the number of copies. While both models perform similarly in the case of a single failed contact—with SDP always above 85%—GROGU maintains high and consistent performance as the number of failures increases, with minima close to 80%, significantly outperforming LSS.

## V. CONCLUSIONS

We presented GROGU, a decentralized routing algorithm that combines Deep Reinforcement Learning and Graph Neural Networks to deliver a single, reusable policy for all nodes. GROGU adapts to probabilistic link failures and topology changes without retraining, achieving delivery performance comparable to state-of-the-art methods while offering superior resilience to unforeseen outages. The main drawback is higher training costs in processing and memory, though the minimal network size for reliable operation remains to be determined. GROGU is best suited for large-scale DTNs where maintaining a long-lived, fault-tolerant policy is more valuable than minimizing training overhead.

## ACKNOWLEDGEMENT

This research has received support from the European Union's Horizon 2020 R&D program under the Marie Skłodowska-Curie grant agreement No 101008233 (MISSION project) and the French National Research Agency (ANR) under the STEREO project ANR-22-CE25-0014-01.
<figure><img src="image_7.png" /><figcaption>Figure 6: Average SDP retained with one (a), two (b), and three (c) downed contacts.</figcaption></figure>

REFERENCES

[1] L. Torgerson, S. C. Burleigh et al., "Delay-Tolerant Networking Architecture," RFC 4838, Apr. 2007.

[2] S. Burleigh, K. Fall, and E. J. Birrane, "Bundle Protocol Version 7," RFC 9171, Jan. 2022.

[3] R. L. Bull, R. M. Dudukovich, J. A. Fraire, N. Kortas, R. Kassouf-Short, A. Smith, and E. Schweinsberg, "Network emulation testbed capabilities for prototyping space DTN software and protocols," in *INFOCOM 2024*. IEEE, 2024, pp. 1–8.

[4] J. A. Fraire, O. De Jonckère, and S. C. Burleigh, "Routing in the space internet: A contact graph routing tutorial," *Journal of Network and Computer Applications*, vol. 174, p. 102884, 2021.

[5] A. Lindgren, A. Doria, E. B. Davies, and S. Grasic, "Probabilistic Routing Protocol for Intermittently Connected Networks," RFC 6693, Aug. 2012.

[6] S. C. Burleigh, C. Caini, J. J. Messina, and M. Rodolfi, "Toward a unified routing framework for delay-tolerant networking," in *WiSEE 2016*. IEEE, 2016, pp. 82–86.

[7] F. D. Raverta, J. A. Fraire, P. G. Madoery, R. A. Demasi, J. M. Finochietto, and P. R. D'Argenio, "Routing in delay-tolerant networks under uncertain contact plans," *Ad Hoc Networks*, vol. 123, p. 102663, 2021.

[8] P. D'Argenio, J. Fraire, and A. Hartmanns, "Sampling distributed schedulers for resilient space communication," in *NASA Formal Methods*, ser. Lecture Notes in Computer Science, R. Lee, S. Jha, and A. Mavridou, Eds. Germany: Springer, Aug. 2020, pp. 291–310.

[9] P. R. D'Argenio, J. Fraire, A. Hartmanns, and F. Raverta, "Comparing statistical, analytical, and learning-based routing approaches for delay-tolerant networks," *ACM Trans. Model. Comput. Simul.*, vol. 35, no. 2, Apr. 2025.

[10] M. L. Puterman, *Markov Decision Processes: Discrete Stochastic Dynamic Programming*, ser. Wiley Series in Probability and Statistics. Wiley, 1994.

[11] M. Kwiatkowska, G. Norman, and D. Parker, "Prism 4.0: verification of probabilistic real-time systems," in *Proceedings of the 23rd International Conference on Computer Aided Verification*, ser. CAV'11. Berlin, Heidelberg: Springer-Verlag, 2011, p. 585–591.

[12] C. Hensel, S. Junges, J.-P. Katoen, T. Quatmann, and M. Volk, "The probabilistic model checker storm," *Int. J. Softw. Tools Technol. Transf.*, vol. 24, no. 4, p. 589–610, Aug. 2022.

[13] A. Hartmanns and H. Hermanns, "The modest toolset: An integrated environment for quantitative modelling and verification," in *International Conference on Tools and Algorithms for the Construction and Analysis of Systems*. Springer, 2014, pp. 593–598.

[14] A. Hartmanns, S. Junges, T. Quatmann, and M. Weininger, "A practitioner's guide to mdp model checking algorithms," in *TACAS 2023, ETAPS 2023, Paris, France, April 22–27, 2023*. Berlin, Heidelberg: Springer-Verlag, 2023, p. 469–488.

[15] S. Haddad and B. Monmege, "Interval Iteration Algorithm for MDPs and IMDPs," *Theoretical Computer Science*, vol. 735, pp. 111–131, Jul. 2018.

[16] F. D. Raverta, R. Demasi, P. G. Madoery, J. A. Fraire, J. M. Finochietto, and P. R. D'Argenio, "A markov decision process for routing in space dtns with uncertain contact plans," in *2018 6th IEEE International Conference on Wireless for Space and Extreme Environments (WiSEE)*, 2018, pp. 189–194.

[17] S. Giro, P. R. D'Argenio, and L. M. Ferrer Fioriti, "Distributed probabilistic input/output automata: Expressiveness, (un)decidability and algorithms," *Theoretical Computer Science*, vol. 538, pp. 84–102, 2014, quantitative Aspects of Programming Languages and Systems (2011-12).

[18] P. G. Madoery, F. D. Raverta, J. A. Fraire, and J. M. Finochietto, "On the performance analysis of disruption tolerant satellite networks under uncertainties," in *2017 XVII Workshop on Information Processing and Control (RPIC)*. IEEE, 2017, pp. 1–6.

[19] G. Agha and K. Palmskog, "A survey of statistical model checking," *ACM Trans. Model. Comput. Simul.*, vol. 28, no. 1, Jan. 2018.

[20] A. Legay, S. Sedwards, and L.-M. Traonouez, "Scalable verification of markov decision processes," in *International conference on software engineering and formal methods*. Springer, 2014, pp. 350–362.

[21] R. S. Sutton and A. G. Barto, *Reinforcement Learning: An Introduction*, 2nd ed. The MIT Press, 2018.

[22] C. J. C. H. Watkins and P. Dayan, "Q-learning," *Machine Learning*, vol. 8, no. 3, pp. 279–292, May 1992.

[23] L. Panait and S. Luke, "Cooperative multi-agent learning: The state of the art," *Autonomous Agents and Multi-Agent Systems*, vol. 11, no. 3, p. 387–434, Nov. 2005.

[24] C. Claus and C. Boutilier, "The dynamics of reinforcement learning in cooperative multiagent systems," in *Proceedings of the Fifteenth National/Tenth Conference on Artificial Intelligence/Innovative Applications of Artificial Intelligence*, ser. AAAI '98/IAAI '98. USA: American Association for Artificial Intelligence, 1998, p. 746–752.

[25] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez et al., "Relational inductive biases, deep learning, and graph networks," 2018.

[26] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, "Neural message passing for quantum chemistry," *CoRR*, vol. abs/1704.01212, 2017.

[27] A. Gravina, D. Bacciu, and C. Gallicchio, "Anti-symmetric DGN: a stable architecture for deep graph networks," in *The Eleventh International Conference on Learning Representations*, 2023.

[28] S. Ioffe and C. Szegedy, "Batch normalization: Accelerating deep network training by reducing internal covariate shift," *CoRR*, vol. abs/1502.03167, 2015.

[29] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. A. Riedmiller, A. Fidjeland, G. Ostrovski, S. Petersen, C. Beattie, A. Sadik, I. Antonoglou, H. King, D. Kumaran, D. Wierstra, S. Legg, and D. Hassabis, "Human-level control through deep reinforcement learning," *Nat.*, vol. 518, no. 7540, pp. 529–533, 2015.

[30] J. Fraire, P. Madoery, S. Burleigh, M. Feldmann, J. Finochietto, A. Charif, N.-E. Zergainoh, and R. Velazco, "Assessing contact graph routing performance and reliability in distributed satellite constellations," *Journal of Computer Networks and Communications*, vol. 2017, pp. 1–18, 07 2017.