Research map / Reinforcement learning / Policy gradient and actor-critic
Learning to Stabilize Online Reinforcement Learning in Unbounded State Spaces
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes STOP, which combines Lyapunov-based cost shaping with symmetric state transformations so online average-reward PPO learns stable policies in unbounded queuing and traffic control domains without transition-model knowledge.
Problem
Online deep RL in unbounded state spaces (e.g., stochastic queuing networks) often learns unstable policies whose states drift arbitrarily far from the desired target, because optimality costs give poor credit assignment for destabilizing actions and neural networks extrapolate poorly.
Approach
Augment the optimality cost with a Lyapunov potential difference (l(s')-l(s), with l a power norm such as ||s||_p^p) to penalize destabilizing actions, and apply coordinate-wise compressive state transformations (symsqrt, symloge, symsigmoid) before feeding states to the networks, while computing costs on untransformed states.
Key results
- On the 2-queue setting, STOP's agent keeps visited states within L1 distance 20 with probability 0.95 after 100K steps, while vanilla PPO never enters that bounded region.
- Vanilla average-reward PPO takes destabilizing actions ~40% of the time, while STOP quickly drives this fraction down.
- STOP outperforms or is competitive with MaxWeight in 4 of 6 queuing settings, despite MaxWeight having transition-dynamics knowledge.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add linear Lyapunov cost shaping | Average-reward PPO · 2-queue example | normalized advantage for unstable actions: 0.09 ± 0.07 -> 0.25 ± 0.08 | Helped |
| Add quadratic Lyapunov cost shaping | Average-reward PPO · 2-queue example | normalized advantage for unstable actions: 0.09 ± 0.07 -> 0.25 ± 0.05 | Helped |
| Add quadratic Lyapunov cost shaping | Average-reward PPO · 2-queue example | fraction of destabilizing actions: ≈ 40% | Helped |
| Add quadratic Lyapunov cost shaping | Average-reward PPO · 2-queue example, after 100K interaction steps | probability of visiting states within L1 distance 20: 0.95 | Helped |
| Add symloge state transformation (ablation) | STOP with cubic Lyapunov shaping · 2-queue setup with faulty connections | true optimality cost | Helped |
| Add symsigmoid state transformation (ablation) | STOP with cubic Lyapunov shaping · 2-queue setup with faulty connections | true optimality cost | Helped |
| Add symsqrt state transformation (ablation) | STOP with cubic Lyapunov shaping · 2-queue setup with faulty connections | true optimality cost | Helped |
| Remove state transformation (use identity) (ablation) | STOP with cubic Lyapunov shaping · 2-queue setup with faulty connections | true optimality cost | Hurt |
| Remove Lyapunov stability cost, retaining state transformation (ablation) | STOP · 2-queue setup with faulty connections | stability | Hurt |
| Vary the Lyapunov power from moderate values to p=1 (ablation) | STOP with symloge state transformation · Queueing and N-model environments | average queue length or holding cost | Mixed |
| Vary the Lyapunov power from moderate values to p=5 (ablation) | STOP with symloge state transformation · Queueing and N-model environments | average queue length or holding cost | Mixed |
| Use moderate Lyapunov powers, such as p=3, instead of extreme powers (ablation) | STOP with symloge state transformation · High-load queueing and N-model environments | average queue length or holding cost | Helped |
Surprising findings
- Vanilla average-reward PPO is unstable in all high-load queuing environments tested, and in very high load settings all algorithms including MaxWeight-based STOP became unstable.
- State transformations alone (without the stability cost) do not stabilize the system, even though symsigmoid bounds the state space.
Limitations
- Lyapunov function is hand-chosen from queuing-theory intuition and power p must be tuned; learning it from data is future work
- Stability cost with linear Lyapunov function required replacing optimality cost with -1/(c+1) in highly stochastic queuing settings
- Only on-policy PPO was studied; the training-wheels experiment suggests off-policy methods are needed for stable-policy-assisted learning
Experimental setup
Datasets: simulated queuing networks (2-queue, 10-queue, N-model) SUMO traffic simulator big-intersection scenario
Benchmarks: 2-queue server allocation (medium, high, very high load) 10-queue server allocation N-model network (3 setups) SUMO traffic control
Metrics: true optimality cost (average queue length / holding cost / fraction of destabilizing actions state-visitation probability in bounded sub-grid
Baselines: average-reward PPO MaxWeight
Builds on: PPO average-reward RL MaxWeight potential-based reward shaping
Closest papers by meaning
- Taming "data-hungry" reinforcement learning? Stability in continuous state-action spaces (NeurIPS 2024 · similarity 0.88)
- Pausing Policy Learning in Non-stationary Reinforcement Learning (ICML 2024 · similarity 0.86)
- Relaxed Stationary Distribution Correction Estimation for Improved Offline Policy Optimization (AAAI 2024 · similarity 0.86)
- Stable Gradients for Stable Learning at Scale in Deep Reinforcement Learning (NeurIPS 2025 · similarity 0.86)
- SUF: Stabilized Unconstrained Fine-Tuning for Offline-to-Online Reinforcement Learning (AAAI 2024 · similarity 0.86)
- Not Only Where, But When: Temporal Scheduling for RLVR (NeurIPS 2026 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.