提出新型路由算法，保障交通稳定且权重收敛。
Semi-Gradient SARSA Routing with Theoretical Guarantee on Traffic Stability and Weight Convergence
- 用通用基函数近似无界状态空间的价值函数。
- 理论证明系统稳定，权重几乎必然收敛至近优解。
- 仿真显示比神经网络方法更快收敛，误差小。
我们研究平行服务器上的动态路由交通控制问题，该问题广泛存在于交通与数据传输等工程系统中。提出一种半梯度、在线策略的算法，通过使用通用基函数和可调权重来近似无界状态空间下的价值函数。由于训练过程缺乏梯度的Lipschitz连续性、时序差分误差的有界性以及遍历性的先验保证，现有强化学习理论标准前提不成立。为此，结合李雅普诺夫方法与常微分方程分析，联合刻画交通状态与近似权重的演化行为。理论分析证明该训练方案能保证交通状态稳定，并确保权重几乎必然收敛至近似最优。仿真结果表明，该算法在逼近误差极小的前提下，收敛速度显著优于基于神经网络的方法。
原文摘要 · Abstract (English)
We consider the traffic control problem of dynamic routing over parallel servers, which arises in a variety of engineering systems such as transportation and data transmission. We propose a semi-gradient, on-policy algorithm that learns an approximate optimal routing policy. The algorithm uses generic basis functions with flexible weights to approximate the value function across the unbounded state space. Consequently, the training process lacks Lipschitz continuity of the gradient, boundedness of the temporal-difference error, and a prior guarantee on ergodicity, which are the standard prerequisites in existing literature on reinforcement learning theory. To address this, we combine a Lyapunov approach and an ordinary differential equation-based method to jointly characterize the behavior of traffic state and approximation weights. Our theoretical analysis proves that the training scheme guarantees traffic state stability and ensures almost surely convergence of the weights to the approximate optimum. We also demonstrate via simulations that our algorithm attains significantly faster convergence than neural network-based methods with an insignificant approximation error.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。