# Semi-Gradient SARSA Routing with Theoretical Guarantee on Traffic Stability and Weight Convergence

arXiv: https://arxiv.org/abs/2503.14927 · HTML: https://mlsanity.com/paper/2503.14927/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 43 references that are in the map.
- First posted on arXiv 19 Mar 2025.

## Builds on (most cited first, 13 of 13)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Finite-Time Analysis of Asynchronous Stochastic Approximation and Q-Learning](https://mlsanity.com/paper/2002.00260/) (2020)
- [Finite-Sample Analysis of Nonlinear Stochastic Approximation with Applications in Reinforcement Learning](https://mlsanity.com/paper/1905.11425/) (2019)
- [Interpretable and Explainable Logical Policies via Neurally Guided Symbolic Abstraction](https://mlsanity.com/paper/2306.01439/) (2023)
- [Actor-Critic Reinforcement Learning for Control with Stability Guarantee](https://mlsanity.com/paper/2004.14288/) (2020)
- [Queueing Network Controls via Deep Reinforcement Learning](https://mlsanity.com/paper/2008.01644/) (2020)
- [RL-QN: A Reinforcement Learning Framework for Optimal Control of Queueing Systems](https://mlsanity.com/paper/2011.07401/) (2020)
- [Stable Reinforcement Learning with Unbounded State Space](https://mlsanity.com/paper/2006.04353/) (2020)
- [Analysis of stochastic approximation schemes with set-valued maps in the absence of a stability guarantee and their stabilization](https://mlsanity.com/paper/1701.07590/) (2017)
- [Stability of Fluid Queuing Systems with Parallel Servers and Stochastic Capacities](https://mlsanity.com/paper/1604.02008/) (2016)
- [Stabilizing Queuing Networks with Model Data-Independent Control](https://mlsanity.com/paper/2011.11788/) (2020)
- [On Joint Convergence of Traffic State and Weight Vector in Learning-Based Dynamic Routing with Value Function Approximation](https://mlsanity.com/paper/2404.09188/) (2024)

## Abstract (arXiv)

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.