# Stable Reinforcement Learning with Unbounded State Space

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jun 2020.

## Built on by (most cited first, 8 of 8)

- [Learning and Information in Stochastic Networks and Queues](https://mlsanity.com/paper/2105.08769/) (2021)
- [Performance of NPG in Countable State-Space Average-Cost RL](https://mlsanity.com/paper/2405.20467/) (2024)
- [Differentiable Discrete Event Simulation for Queuing Network Control](https://mlsanity.com/paper/2409.03740/) (2024)
- [Can an AI agent hit a moving target?](https://mlsanity.com/paper/2110.02474/) (2021)
- [Online Learning and Optimization for Queues with Unknown Demand Curve and Service Distribution](https://mlsanity.com/paper/2303.03399/) (2023)
- [QGym: Scalable Simulation and Benchmarking of Queuing Network Controllers](https://mlsanity.com/paper/2410.06170/) (2024)
- [Learning to Stabilize Online Reinforcement Learning in Unbounded State Spaces](https://mlsanity.com/paper/2306.01896/) (2023)
- [Semi-Gradient SARSA Routing with Theoretical Guarantee on Traffic Stability and Weight Convergence](https://mlsanity.com/paper/2503.14927/) (2025)

## Abstract (arXiv)

We consider the problem of reinforcement learning (RL) with unbounded state space motivated by the classical problem of scheduling in a queueing network. Traditional policies as well as error metric that are designed for finite, bounded or compact state space, require infinite samples for providing any meaningful performance guarantee (e.g. ℓ_∞ error) for unbounded state space. That is, we need a new notion of performance metric. As the main contribution of this work, inspired by the literature in queuing systems and control theory, we propose stability as the notion of "goodness": the state dynamics under the policy should remain in a bounded region with high probability. As a proof of concept, we propose an RL policy using Sparse-Sampling-based Monte Carlo Oracle and argue that it satisfies the stability property as long as the system dynamics under the optimal policy respects a Lyapunov function. The assumption of existence of a Lyapunov function is not restrictive as it is equivalent to the positive recurrence or stability property of any Markov chain, i.e., if there is any policy that can stabilize the system then it must possess a Lyapunov function. And, our policy does not utilize the knowledge of the specific Lyapunov function. To make our method sample efficient, we provide an improved, sample efficient Sparse-Sampling-based Monte Carlo Oracle with Lipschitz value function that may be of interest in its own right. Furthermore, we design an adaptive version of the algorithm, based on carefully constructed statistical tests, which finds the correct tuning parameter automatically.