acceptodds
Under review as a conference paper at ICLR 2027

The Statistical Value of Lyapunov Stability in Reinforcement Learning

Abstract

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.

Primary area:
learning theory
Keywords:
Reinforcement Learning, Sample Complexity, Lyapunov Stability, Markov Decision Processes

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_zKYDOpenReview ↗
Rating
3(+1)
Confidence
1(−1)
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies generative-model learning in countable-state, average-reward MDPs. This work assumes a known Lyapunov function and stabilizing policy. They develop a model-based algorithm LyCore that learns inside a finite core and uses the stabilizing policy. Its analysis separates performance learning from stability certification, with respective accuracy exponents max⁡2,ν\max{2, \nu} and ν\nu, where nu describes core growth. Matching minimax lower bounds hold in the stated parameter regime. Experiments include synthetic diagnostics, birth-death processes, and voltage control.

Critical strengths
  1. The bounds quantify how drift strength and core growth affect learning complexity, separating reward optimization from stability certification. The transition at ν=2\nu = 2 and the dependence on stability slack are informative. The statistical characterization is the main contribution.

  2. The analysis addresses substantial technical issues. Independent drift samples retain the stable comparator while leaving the one-out arguments and shell-specific variance estimates to handle model-dependent bias functions without a next-state support factor. The lower bounds allow randomized output policies and adaptive sampling.

Critical weaknesses
  1. The second part of Lemma C.4 assumes drift only in the projected MDP (p. 17). This is insufficient since an exit from the core can appear contracting after projection, while the actual switching policy cycles between an in-core and an outside state.

  2. The rate diagnostics supply exact drift or rewards and pair independent trials. The complete implementations use uniform per-row sampling. Consequently, the experiments do not directly establish the full algorithm's shell-allocation advantage when both drift and dynamics are learned.

Questions for authors
  1. Can the Lemma C.4 be corrected with original-kernel drift and verify that every use satisfies this hypothesis without changing the rates?

  2. What explains the aggregate-versus-replay violation gap? Can the author report the replay result and clarify Proposition I.1's scope in the main text.

  3. Can the author compare full LyCore with uniform sampling at equal budgets and provide the allocation grids and sampling procedure for Figure 1?

Reviewer_dBCwOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper investigates the problem of stable reinforcement learning in Markov Decision Processes (MDPs) with countably infinite state spaces and proposes the LyCore algorithm. The core idea is to leverage Lyapunov drift constraints to concentrate long-term state visitation within a finite Lyapunov core. Within this core, the algorithm estimates Lyapunov drift using confidence bounds, learns rewards and transitions through shell-dependent sampling, and optimizes the average reward through constrained linear programming. The paper establishes global stability and near-optimality relative to a specified class of stable policies, while providing matching upper and lower bounds on sample complexity up to logarithmic factors. Experiments on synthetic MDPs support the predicted sample-complexity rates, while an IEEE 33-bus voltage-control task illustrates the method under model uncertainty.

Critical strengths
  1. Transformation of infinite-state learning into learning within a finite region. The paper not only proves that stable policies concentrate long-run state occupancy, but also establishes performance error bounds for using the original policy inside a finite core and a known stabilizing policy outside it. This provides a rigorous theoretical foundation for finite-sample learning in infinite-state MDPs, moving beyond simple heuristic state truncation.

  2. Shell-dependent sampling has a clear statistical motivation. The algorithm allocates model samples based on the influence of different Lyapunov shells on average reward and uses regenerative analysis to control model errors. Compared to uniform-precision sampling, this approach theoretically improves the dependence on precision and achieves matching upper and lower bounds up to logarithmic factors within the stated model class

Critical weaknesses
  1. The optimality benchmark is restricted by a fixed reference-state action. The paper requires all candidate policies to take a fixed action at the reference state s0s_0. This precludes the optimization of rewards at the reference state; even if other actions were to yield identical transition dynamics and stability, they could not be selected. Consequently, the near-optimality guarantee holds only for this restricted class of policies, potentially leaving a constant gap relative to the optimal return achievable by general stabilizing policies. This constraint limits the practical significance of the paper’s optimality conclusions.

  2. The matching lower bound relies on a specific transition mechanism at the reference state. Assumption 3.1 imposes an almost-sure bound on one-step potential growth only for non-reference states, while imposing only an expected-potential bound at the reference state. The construction of the lower bound exploits this exception, allowing the system to transition from the reference state to an arbitrarily distant state with a small probability. Although this construction satisfies Assumption 3.1, it does not reflect the bounded-movement physical systems used to motivate the assumption. It remains unclear whether the current matching lower bound and the associated phase transition results would still hold if the reference state were also subject to the same uniform single-step movement constraint.

Questions for authors
  1. Why is it necessary to fix the action taken at the reference state? If another action yields the same transition distribution but a higher reward, the current algorithm cannot select it. Could the authors clarify the potential loss in the optimal stable return resulting from this constraint?

  2. The difficult instance for Theorem 5.2 relies on transitioning directly from the reference state to a distant state. If we impose the same one-step movement bound on all states, including the reference state, do the matching lower bounds and the phase transition at ν=2\nu=2 still hold?

Reviewer_XNXnOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies RL for systems that are non-episodic (i.e., run forever), the state can grow unbounded (e.g., queue lengths or tracking errors), and the policy should learn/stay stable. Stability is defined through a Lyaponuv energy function: under a stable policy, the energy shrinks on average at every step. The key point is that a stable system spends most of its time at low energy, so learning only needs to happen in a finite low-energy region, and a known safe policy takes over outside it to bring us back to the "core"/safe Lyaponuv area. From this, they propose a simulator-based method (assuming state-reset capability, which is concerning). The method learns the model and the stability constraint inside that region, then solves a (somewhat constrained) planning problem. They give matching upper/lower bounds on the number of samples needed, split into a cost for learning good performance and a cost for learning stability, which is quite insightful and intuitive. Experiments include a synthetic MDP and a power-grid voltage-control task.

Critical strengths
  1. A clear and well-motivated question:
    1. Can finite data enough to learn a stable, near-optimal policy when the state space is unbounded? That is a natural question for control and queue applications.
  2. An intuitive central idea:
    1. Stability keeps the system in a finite region most of the time, so learn there and fall back to a safe policy elsewhere. This is easy to make peace with and is explained well in the paper.
  3. An interpretable split of the cost:
    1. Separating the sample cost into performmance learning and stability learning is a nice way to think about the problem.
  4. Matching lower bounds:
    1. The authors provide lower bounds that match their upper bound up to log factors, which makes for a strong theory. I did not check the proofs in detail.
Critical weaknesses

My over-simplified understanding of the flow is as follows; please correct me if I am woefully wrong in the rebuttals:

  • Stability means the energy shrinks on average, so the system rarily sits at high energy.
  • So it is enough to learn a good policy inside a finite low-energy region, and use the known safe policy outside it (I'm referring to pi_stab).
  • Inside that region, the method samples every state to check the stability constraint, samples the model less in the rarely visited outer states, and solves a constrained planning problem.
  • Counting the samples gives two terms: one for learning performance and one for learning stability.

Given that,

  1. Regarding how realistic the assumptions are:
    1. the paper requires the energy to shrink at every state except a single "home" state. In many real systems, I would expect this to hold only far away from the operating point, since noise keeps pushing the energy around near it.
    2. A single step can only multiply the energy by a bounded factor, and this has to hold with probability one (almost surely). Wouldn't this rule out the common Gaussian noise models?! Even a small Gaussian disturbance has some chance of a large jump.
    3. The size of the low-energy region is assumed to grow polynomially with the energy level, and this growth rate is treated as an "effective dimension".
      1. what does that mean in real life?
      2. what kind of a system satisfies this, and which doesn't?
      3. would the examples in the paper actually be covered by it?
    4. The algorithm also needs a known stabilizing policy, the energy function, and several structural constants as inputs. A short discussion of how someone would obtain/tune these would help. I assume that requires a hyper-parameter tunning loop outside, which can be quite expensive.
  2. Regarding the simulator assumption:
    1. the method needs a simulator that can be set to any state (even far-away, high-energy states) and stepped once from there.
    2. This is a significant requirement. Typical RL methods do not ask for that kind of liberty; they interact with the environment by rolling out trajectories. Even in software-simulated environments, setting the simulator to an arbitrary state is difficult to implement, especially when real-world effects (physics, delays, hardware or weather dynamics) are simulated and the internal state is not fully exposed or consistent.
    3. On top of that, the high-energy states the algorithm must query are exactly the unsafe states that stability is supposed to avoid. How do the authors see this working for the robotics and data-center motivations in the introduction?
  3. Regarding the "phase transition" framing:
    1. The bounds drops constants and log factors, which is standard. However, the paper then uses these constant-free bounds to compare the too costs and decide which one "dominates".
    2. Above the transition point, if I understand correctly, both costs grow at the same rate, and stability is only larger by a constant-like factor. Since the bounds already hide unknown constants, I'm not sure that comparison is meaningful. Even the paper's own experiment seems to show the performance cost being larger at the boundary case.
    3. I'd suggest either making this comparison more rigorous, or toning down the "phase transition" language.
  4. Regarding the experiments:
    1. These is not standard RL tasks. The power-grid feeder is more common in the power-systems and control communities, and the other experiments are small custom MDPs.
    2. For this venue, I'd encourage the authors to include benchmarks the RL community already uses, ideally ones that match the paper's own motivation, such as classic control tasks.
    3. That would make it much easier for readers to judge how the method compares with existing approaches.
  5. Regarding notation:
    1. It would be great if the authors could add a table of notations to the appendix. There are many symbols and constants, and having them in one place would make the paper much easier to follow.
Questions for authors

See the critical weaknesses. In addition:

  1. Can you give one concreate, realistic system where all the assumptions (e.g., energy shrinkings, single-step movements, core region constraints, etc) hold together?
  2. Is the method intended as a practical algorithm, or mainly as a theoretical result? If practical, how would one run it without a simulator that can be set to arbitrary states? Wouldn't that limit the applicability of the system to general RL applications you reference in the paper repeatedly?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.