A Lyapunov Drift-Plus-Penalty Method Tailored for Reinforcement Learning with Queue Stability

Wenhan Xu, Jiashuo Jiang, Lei Deng, Danny Hin-Kwok TsangarXiv 2025 · DOI · arXiv

Introduction

In the rapidly evolving landscape of the Internet of Things (IoT) and edge computing, network management systems face a dual challenge: optimizing operational performance (such as minimizing energy consumption or latency) while ensuring system stability. Stability, in this context, refers to preventing data queues from growing indefinitely, which would lead to catastrophic delays and packet loss.

The Stability-Performance Gap

Traditionally, researchers have relied on the Lyapunov Drift-Plus-Penalty (LDPP) method to manage these systems. LDPP is mathematically robust and guarantees queue stability, but it operates on a "greedy" principle, optimizing only for the immediate next time step. This short-sightedness often results in suboptimal long-term performance, especially when dealing with complex, non-convex cost functions.

Conversely, Reinforcement Learning (RL) excels at long-term planning and navigating complex state spaces. However, standard RL algorithms do not inherently guarantee queue stability. Previous attempts to merge these two approaches often involved simply inserting the Lyapunov formula into an RL reward function. The authors of this paper identify a fundamental mismatch in this "plug-and-play" approach: the short-term focus of LDPP conflicts with the long-term objective of RL, leading to potential instability or poor performance.

The LDPTRLQ Framework

To bridge this gap, the authors introduce LDPTRLQ, a framework that derives a novel reward function specifically designed to align Lyapunov optimization with RL's long-term maximization goal.

Instead of using a simple drift term, the derived reward function takes a quadratic form: $$R(t) = -\frac{1}{2} \sum (Q_n^2(t+1) + Q_n^2(t)) - V p(t)$$ where $Q$ represents queue lengths and $V p(t)$ is the penalty term (e.g., energy consumption). This formulation ensures that if an RL agent were to act greedily, it would behave exactly like the mathematically sound Lyapunov method. By using Proximal Policy Optimization (PPO), the agent learns to optimize this reward over long horizons, effectively balancing stability and efficiency.

Experimental Setup

The framework was evaluated using high-fidelity simulations of common networking scenarios. One primary environment is a Mobile Edge Computing (MEC) system, consisting of a base station and multiple mobile users offloading tasks.

Mobile Edge Computing (MEC) system model used for evaluation.

In this model, task arrivals follow a Poisson process, and the agent must decide how to offload tasks to minimize energy while keeping the local and base station queues stable. A second simulation involved network routing across a 20-node topology to test "backpressure" routing capabilities.

Key Results and Discussion

The LDPTRLQ algorithm demonstrated significant improvements over traditional and hybrid baselines.

Convergence of average energy and queue length over training iterations.

As shown in the convergence plots, LDPTRLQ (the blue line) achieves a superior balance between energy efficiency and queue stability compared to the "Original LDPRLQ" and "Simplified LDPRLQ" methods. Key findings include:

  • Superior Stability: LDPTRLQ maintained the most predictable queue lengths with the lowest standard deviation, ensuring the system is less prone to sudden backlogs.
  • Efficiency Gains: The agent converged faster to a lower energy state while maintaining shorter queues than its counterparts.
  • Handling Non-Convexity: The RL agent successfully navigated complex penalty functions where traditional greedy Lyapunov methods often stalled in local optima.
  • Algorithm Robustness: In the network routing task, the algorithm matched specialized "backpressure" algorithms while maintaining the flexibility to optimize for additional factors like energy.

Conclusion

LDPTRLQ provides a mathematically grounded way to integrate queue stability into reinforcement learning. By tailoring the reward function to the underlying Lyapunov theory, the authors enable RL agents to provide the stability guarantees required for critical infrastructure while maintaining the high performance of deep learning. Future work will focus on making the trade-off parameter $V$ adaptive to real-time network conditions and validating the framework in physical IoT testbeds.

Summary updated

BibTeX
@misc{xu2025lyapunov,
  author = {Wenhan Xu and Jiashuo Jiang and Lei Deng and Danny Hin-Kwok Tsang},
  title = {{A Lyapunov Drift-Plus-Penalty Method Tailored for Reinforcement Learning with Queue Stability}},
  year = {2025},
  eprint = {2506.04291},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2506.04291},
}
Figure