Spatial-Temporal Reinforcement Learning for Network Routing with Non-Markovian Traffic

📄 arXiv: 2507.22174v2 📥 PDF

作者: Molly Wang, Kin. K Leung

分类: cs.LG, cs.AI

发布日期: 2025-07-27 (更新: 2025-07-31)

💡 一句话要点

提出空间-时间强化学习(STRL)框架，解决非马尔可夫网络流量下的路由问题。

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 强化学习 网络路由 非马尔可夫流量 空间-时间模型 深度学习

📋 核心要点

  1. 传统强化学习在网络路由中依赖马尔可夫假设，无法有效处理实际网络中非马尔可夫流量带来的挑战。
  2. 论文提出空间-时间强化学习(STRL)框架，通过建模网络拓扑的空间结构和流量的时间依赖性来优化路由决策。
  3. 实验结果表明，STRL在非马尔可夫流量环境下，训练阶段性能提升超过19%，推理阶段提升7%。

📝 摘要（中文）

强化学习(RL)已被广泛应用于通信网络中的数据包路由，但传统RL方法依赖于马尔可夫假设，即当前状态包含决策所需的所有必要信息。然而，现实中的互联网流量是非马尔可夫的，过去的状态确实会影响路由性能。此外，常见的深度RL方法使用函数逼近器（如神经网络），但它们没有对网络拓扑中的空间结构进行建模。为了解决这些缺点，我们设计了一个具有非马尔可夫流量的网络环境，并引入了一个用于数据包路由的空间-时间RL (STRL)框架。我们的方法在训练期间优于传统基线19%以上，并且在网络拓扑发生变化的情况下，推理性能也提升了7%。

🔬 方法详解

问题定义：论文旨在解决通信网络中数据包路由问题，现有基于强化学习的方法通常假设网络流量满足马尔可夫性质，即当前状态包含了所有决策所需的信息。然而，实际网络流量具有非马尔可夫性，历史状态对路由性能有显著影响。此外，传统深度强化学习方法忽略了网络拓扑的空间结构，导致路由策略无法充分利用网络信息。

核心思路：论文的核心思路是利用空间-时间强化学习(STRL)框架，同时考虑网络流量的时间依赖性和网络拓扑的空间结构。通过引入时间维度，模型可以学习到流量的历史信息对未来路由决策的影响。同时，通过建模网络拓扑结构，模型可以更好地利用网络中的空间信息，从而做出更优的路由决策。

技术框架：STRL框架主要包含以下几个模块：1) 网络环境建模：构建一个具有非马尔可夫流量的网络环境，模拟真实网络流量的复杂性。2) 状态表示：设计一种能够捕捉网络流量时间依赖性和网络拓扑空间结构的状态表示方法。3) 强化学习算法：选择合适的强化学习算法，例如深度Q网络(DQN)或策略梯度算法，用于训练路由策略。4) 奖励函数设计：设计一个能够反映路由性能的奖励函数，例如延迟、丢包率等。

关键创新：论文的关键创新在于提出了空间-时间强化学习(STRL)框架，该框架能够同时处理非马尔可夫流量和网络拓扑空间结构。与传统的强化学习方法相比，STRL能够更好地适应真实网络环境，并做出更优的路由决策。

关键设计：论文中关键的设计包括：1) 如何有效地表示网络状态，使其能够捕捉流量的时间依赖性和网络拓扑的空间结构。这可能涉及到使用循环神经网络(RNN)来处理时间序列数据，以及使用图神经网络(GNN)来建模网络拓扑结构。2) 如何设计奖励函数，使其能够准确地反映路由性能，并引导模型学习到最优的路由策略。3) 如何选择合适的强化学习算法，并调整其参数，以获得最佳的训练效果。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

实验结果表明，所提出的STRL框架在非马尔可夫流量环境下，训练阶段的性能比传统基线方法提升了超过19%。更重要的是，即使在网络拓扑发生变化的情况下，STRL在推理阶段的性能仍然比基线方法提升了7%。这表明STRL具有良好的泛化能力和鲁棒性。

🎯 应用场景

该研究成果可应用于各种通信网络，例如互联网、数据中心网络、无线网络等。通过优化数据包路由策略，可以显著提高网络性能，降低延迟、减少丢包，并提升用户体验。此外，该方法还可以应用于流量工程、网络安全等领域，具有重要的实际价值和广阔的应用前景。

📄 摘要（原文）

Reinforcement Learning (RL) has been widely used for packet routing in communication networks, but traditional RL methods rely on the Markov assumption that the current state contains all necessary information for decision-making. In reality, internet traffic is non-Markovian, and past states do influence routing performance. Moreover, common deep RL approaches use function approximators, such as neural networks, that do not model the spatial structure in network topologies. To address these shortcomings, we design a network environment with non-Markovian traffic and introduce a spatial-temporal RL (STRL) framework for packet routing. Our approach outperforms traditional baselines by more than 19% during training and 7% for inference despite a change in network topology.