The Statistical Value of Lyapunov Stability in Reinforcement Learning

Reinforcement learning for long-running tasks, such as robotic and queueing control, must achieve high reward while maintaining stability. In many such tasks, state variables such as motion tracking errors and queue lengths may be unbounded, making it challenging to learn a globally stable and near-optimal policy from finite data. Counterintuitively, we show that Lyapunov stability makes learning in countably infinite MDPs effectively finite: negative Lyapunov drift concentrates long-run occupancy within a finite region, which we call a Lyapunov core. We develop a model-based algorithm LYCORE, which learns from samples collected only within an accuracy-dependent Lyapunov core and uses a known stabilizing policy elsewhere, with guarantees of global stability and near-optimality among Lyapunov-stable policies. We further establish matching upper and lower bounds on the sample complexity up to logarithmic factors, separating the fundamental costs of stability and performance learning. Our algorithm attains these bounds by combining uniform drift sampling with shell-dependent model sampling, which allocates fewer model samples to outer, rarely visited regions. The bounds reveal an interesting phase transition: performance learning dominates at high accuracy in low effective dimensions, whereas stability learning can dominate in higher effective dimensions. Experiments on a multi-shell synthetic MDP support the predicted rates, while a nonlinear IEEE 33-bus voltage-control task illustrates the method under realistic model uncertainty.