acceptodds
Under review as a conference paper at ICLR 2027

Sharp Sample Complexity for Lyapunov-Based Control of Unknown Systems

Abstract

Learning control from offline demonstrations requires transferring certificate guarantees to a replacement controller's trajectories. We study control-affine systems using one fixed batch of independent expert episodes, including recorded controls. The method jointly learns a certificate and a drift predictor, then synthesizes constrained feedback through a soft control-Lyapunov quadratic program, without further plant interaction. A bounded, one-sided warning loss measures expert-margin deficits and harmful directional model errors. Under explicit encounter coverage, its population value bounds the probability of any certificate-decrease violation over a prescribed deployment horizon. Soundness requires no expert stability premise; useful guarantees additionally require an in-class decrease witness and directional approximation. We give same-batch bounds for parametric and smooth reproducing-kernel classes. For a fixed library of certificates and an affine predictor with coefficients, a convex scenario formulation yields a report of order O\(\frac{p+\log(K/\delta)}{\nu_{enc} N}) at zero optimal warning slack. We quantify the probability of passing a requested risk tolerance. Separately, spatial logging coverage gives practical stability outside a ball whose radius shrinks with the loss bound. A realizable control family establishes matching sample, dimension, and coverage dependence within prescribed classes and synthesis architecture, despite nonvanishing minimax uniform drift-estimation error. Experiments illustrate directional learning and the distinct roles of source confidence and deployment coverage.

Primary area:
learning on time series and dynamical systems
Keywords:
learning stability certificates, control Lyapunov functions, learning from demonstrations, offline learning, learning-based control, unknown dynamics, robust CLF-QP, scenario optimization, sample complexity, certified deployment

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_gP8dOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper learns a Lyapunov certificate V and a drift predictor F from passive expert demonstrations of an unknown control-affine system, then deploys a CLF-QP built from them. A one-sided warning score (expert margin deficit plus the positive part of the drift error along grad V) provably exceeds a tight threshold whenever the deployed QP violates certificate decrease (Lemma 3). Under an encounter-coverage assumption (Assumption 4), deployment risk is at most the logged warning loss divided by nu_enc (Theorem 1). The paper gives parametric, scenario-based, and RKHS bounds on that loss, and a minimax lower bound of order d/(nu N) on a constructed family (Theorem 4). Experiments on a pendulum and a cart-pole with linear saturated experts compare against behavior cloning, MSE identification plus QP, and neural baselines. Since nu_enc is never established, the reported deployment bound is Q = 1 throughout.

Critical strengths
  1. The directional warning and detection lemma are a clean, useful idea: only model errors that can hide a certificate increase are penalized, and the threshold is tight in the scalar case. The statistical side is careful (simultaneous bounds allowing same-batch selection, correct scenario dimension p+1, certified numerical optimizer transfer). I reproduced the scenario bounds in Table 6 exactly.

  2. The paper is transparent. It reports Q = 1 instead of an optimistic number, gives counterexamples to favorable coverage (Table 7), proves the coverage dependence is unavoidable for this architecture, and uses a frozen protocol with interval verification of the final pendulum controllers.

Critical weaknesses
  1. The deployment guarantee depends entirely on Assumption 4, which can't be verified from passive data and is never instantiated. Given Lemma 3, Theorem 1 follows in a few lines. The authors' own estimates (Appendix G.6) put the coverage ratio around 0.07-0.08. Even if that value were certified, the best source bound at N = 256 (0.1635) would still give Q = 1, and by my calculation Q <= 0.1 would need roughly 6,000 episodes on the pendulum. The "sharp" result (Theorem 4) holds on a constructed family with uninformative expert trajectories, one terminal record per episode, and a fixed QP architecture, where the authors note u = -3x stabilizes every member. The title overstates this.

  2. The experiments don't show when the method is needed. The experts are linear and behavior cloning recovers them almost exactly. BC-ridge and NLC-on-model have zero violations in every cell. At N = 128 the scenario learner has 13/384 (pendulum) and 144/384 (cart-pole) violations, worse on cart-pole than R39-ERM (21/384) and MSE-ID+QP (115/384). On cart-pole, BC also has lower effort and faster settling (Table 11).

Questions for authors
  1. Proposition 1 gives νenc=1\nu_{\mathrm{enc}} = 1 if a warning sublevel set Kb={x:sh(x)≤b}K_b = \{x : s_h(x) \le b\} is forward invariant. Since you already run interval verification (Appendix G.10), can you certify this for the selected pendulum pair and report a non-vacuous QQ?
  2. Is "OURS-ERM" in Table 1 the same as "R39-ERM"? What does R39 refer to?
  3. The matching upper bound d/(4ν0(N+1))d/(4\nu_0(N+1)) in Theorem 4 comes from a bit-guessing selector. Does Algorithm 1 achieve the same rate on that family? Since the VV class there is a continuum, Theorem 3 does not apply directly.
  4. Why does the scenario learner do much worse than R39-ERM on cart-pole at N=128N = 128 (144144 vs. 2121 violations out of 384384)?
  5. Nonlinear experts or higher-dimensional systems, where cloning is not trivially exact, would show where the approach pays off.
  6. Direct testing needs only 5959 failure-free rollouts for a 5%5\% bound (Appendix G.7). When is the passive route preferable to a small amount of on-policy testing?
3 comments
AuthorsOpenReview ↗

General comment (1/2)

The uploaded full paper includes a linked guide for each reviewer in the supplement material pdf immediately after the references. The links under each question and concern jump to the passages highlighted for that item. Footer links take you back to the guide.

The reviewers ask what a batch of expert demonstrations can establish about a controller that will take different actions. The risk we bound is the probability that a fresh start leads to any violation of the prescribed Lyapunov decrease over a fixed horizon. On a trajectory that meets this requirement, the certificate decays at least exponentially through the stated horizon. We give a worked offline certificate, a model-assisted proof for the fitted pendulum controllers, and matched tests of decrease and terminal settling.

A worked certificate before the first replacement rollout. The terminal-record coverage example uses an oscillator with unknown drift coefficients. The learner knows their ranges and the reset rule. The expert and replacement follow different trajectories, but radial ordering makes the expert’s terminal record cover the warning along the replacement path. With 32 episodes, this gives a 95% deployment bound of 13.985%. All 32 test starts lie outside the inner disk. The oscillator figure shows why the entire 4% of nominal risk lies inside it. The structural information matters because two plants can generate identical complete expert paths while every candidate controller in the class fails on at least one plant (Proposition 17, Sections 3 and 5, Appendix G.9).

Where the statistical rate is sharp. For a fixed certificate library and affine predictor class, the sufficient episode budget depends on the requested risk, confidence and coverage. On the constructed realizable family, Algorithm 1 attains the minimax order of expected deployment risk in the episode count, predictor dimension and coverage, even though uniform drift-estimation error remains bounded away from zero (Theorem 4 and Proposition 14).

What the benchmarks establish. With a training margin and designed logging at 1,024 episodes, Algorithm 1 had zero detected decrease violations in 196,608 pendulum and cart-pole deployments across four instances. Full-vector identification followed by the same QP had detections on 46% to 100% of starts. A second study on new batches had zero detections for every share of designed resets from 10% to 100% (Appendix H.15). With the slow nonlinear pendulum expert under uniform logging, both cloners settled from every start. Ridge and neural cloning nevertheless missed the prescribed decrease on 100% and 8.4% of starts, respectively (Section 5). Under zero-mean derivative noise, detections of Algorithm 1 began only at median noise-to-signal ratios of 37.8% and 55.5%, and new Proposition 19 covers sign-symmetric noise of any size (Appendix H.15). On a new six-state quadrotor with a linear expert, both cloners had no detection and Algorithm 1 had at best 3 in 49,152 starts, at 4,096 episodes (follow-up comment).

The passive deployment report is one on both benchmarks. For three frozen pendulum fits, the optimizer checks and a model-based invariant-set proof give a 95% deployment bound below 2.874% per fit under independent draws from the benchmark’s finite-precision reset law. A separate interval proof establishes all-time decrease on the full reset disk. For three cart-pole fits on independently reconstructed batches, treating their records as exact gives a bound below 0.04550 on mean logged warning loss. The exact 0.011 margin proved for the enlarged cart-pole reset law concerns the expert. For the 12 zero-onset cart-pole fits under that law, an interval proof on the model now gives all-time decrease from every reset (Appendices G.8 and H.14).

We retained the submitted title for review. If accepted, we will use Sharp Sample Complexity for Certifying Lyapunov Decrease in Offline Control of Unknown Systems for the camera-ready version.

AuthorsOpenReview ↗

General Comment (2/2)

Three additions to the revised manuscript concern the designed expert resets (rKsi Q5, ZbmT Q1 and W1, gP8d Q1) and a system above four states (gP8d Q5, rKsi W5). All were specified before their data.

How much designed logging is needed (Appendix H.15, Figure 14). The designed laws of the paper draw each expert reset from a probe law with probability one half: near the origin for the pendulums, and on an enlarged set for cart-pole. We varied this probability γ\gamma over 0, 0.025, 0.1, 0.25, 0.5, 0.75 and 1 on the four benchmarks, with 12 new batches per cell and deployment starts from the original law. At N=1024N=1024, Algorithm 1 at zero onset had 467 and 112 detections in 49,152 cart-pole starts at γ=0\gamma=0 and 0.025. It had none in 196,608 starts across the four benchmarks at every share from 0.1 to 1. At N=128N=128, detections vanished from γ=0.25\gamma=0.25 with the slow nonlinear expert and from 0.025 with the fast one. On cart-pole at N=128N=128 they were fewest at 0.25 and 0.5 (72 and 65 of 12,288) and rose to 6,398 at γ=1\gamma=1, where no reset comes from the deployment law. MSE-ID+QP had detections on 27.4% to 100% of starts in every cell. With zero-mean derivative noise added, the noise level at which most starts have detections was the same at all seven shares.

What the design certifies. These counts are measurements. The reset coefficient of Appendix C.3 is at most 5⋅10−12γ5\cdot10^{-12}\gamma on the pendulums and 2.1⋅10−27γ2.1\cdot10^{-27}\gamma on cart-pole, so the passive report on the physical benchmarks remains one, as stated. Measured with simulator labels, the probe law gave a positive logged loss for each of the 878 fitted pairs with detections on at least 1% of starts. The ratio of that loss to the mean path score was below the oscillator's 0.916 for 607 of 965 pairs. The design thus exposes each such controller in the logs, without a uniform coefficient.

A six-state benchmark (Appendix H.15, Figure 15). We repeated the logging and expert comparison on a planar quadrotor with six states, two inputs and an LQR expert (p=42p=42, K=73K=73, 12 batches per cell). Under the uniform reset law, Algorithm 1 at zero onset had detections from 1,749 of 12,288 starts at N=128N=128, 115 of 49,152 at N=1024N=1024 and 3 of 49,152 at N=4096N=4096. MSE-ID+QP had detections from 84% to 97% of starts, and ridge and neural cloning of the linear expert had none in any cell. Every trajectory of every method settled, so the detections concern the prescribed rate. The probe laws did not lower the counts at N=1024N=1024 or 4096. At share one half and N=4096N=4096, the near-origin law gave 22 detections and the enlarged law 30,785, with slack above bb in every fit, so the report was one. This is one system above four states. It does not measure scaling with dimension.

From a sampled check to a proof on cart-pole (Appendix G.8). The manuscript reported a sampled check of one zero-onset cart-pole fit under enlarged logging. An interval branch-and-bound now covers the whole certificate sublevel set containing the reset set, for all 12 such fits at N=1024N=1024. Each fit is verified: the normalized decrease residual is at most −10−4-10^{-4} on the set, with 15.9 to 49.7 million accepted boxes per fit and 17.2 CPU-hours in total. Hence VV decreases at the prescribed rate along every model trajectory from the reset set, for all time, for each of the 12 controllers. The same program verifies the three pendulum fits of Appendix G.8 and returns a counterexample for a cart-pole fit with measured violations. As for the pendulum, this is a verification with the plant model after fitting, and the passive report is unchanged.

These runs used a second machine. Its check against 48 rows of Table 1 reproduces every Algorithm 1 count and differs in one MSE-ID+QP count, so the share study is reported from its own rows.

AuthorsOpenReview ↗

Response to —— gP8d —— on Certification and Sample Complexity (1/1)

Thank you for reproducing the scenario bounds. Your guide is in the supplement of the uploaded full paper, just after the references. Links under each question and concern jump to the highlighted passages.

Q1. Can the pendulum sublevel be certified? Yes. For each of the three frozen N=1024N=1024 fits, intervals enclose every potentially active face derivative under the clipped QP control. This proves invariance of the warning sublevel at b=3/128b=3/128 within an invariant ellipsoid containing all resets. Since every episode logs its reset, Proposition 1 gives coverage one for that fit. We checked the analytic expert actions and derivatives at all resets used to train these fits. Lemma 7 then gives a 95% deployment bound below 2.874% per fit under independent draws from the benchmark’s finite-precision reset law. Proposition 10 separately proves all-time decay throughout the continuous reset disk. For the 12 zero-onset cart-pole fits under enlarged logging, a new interval proof gives all-time decrease. These checks use the model after fitting. The passive deployment report is one (Appendix G.8).

For the separate study with p=22p=22, K=224K=224 and zero effective slack, certifying coverage at 0.08 or 0.07 would first bring the exact 95% scenario report to 10% or less at 5,452 or 6,232 episodes, respectively. The observed ratios alone cannot certify those coverage values (Appendix G.5).

Q2. Method names. Yes. OURS-ERM and R39-ERM denote the same estimator. R39 was an internal identifier. The estimator averages, over episodes, the largest squared one-sided warning in each episode.

Q3. Does Algorithm 1 attain the minimax order? Yes. Proposition 14 uses the single certificate V(x)=∣x∣2/2V(x)=\\|x\\|^2/2 from the continuum, so Theorem 3 applies with K=1K=1 and p=dp=d. A probe revealing a nonzero bit forces its fitted coefficient up. Only unseen active bits can contribute to risk, yielding expected risk at most d/[ν0(N+1)]d/[\nu_0(N+1)]. Theorem 4 gives the matching lower order for the declared class and QP. The construction uses one terminal record per episode. The unrestricted policy u=−3xu=-3x stabilizes this family. Proposition 17 separately establishes non-identifiability even with complete expert paths.

Q4. Why 144 versus 21 detections? The positive training onset allows warnings up to aa even at zero slack. At zero objective, the average-loss fit forces every logged warning to zero. On fresh cart-pole expert episodes at N=128N=128, warnings exceeded aa on 7.1% to 9.5% of episodes at positive onset and 0.35% to 1.87% at zero onset. Lowering the onset changed deployment detections from 896 to 345 in the logging and expert comparison, and from 498 to 670 in its independent replication, out of 12,288 in each study. The onset determines which warnings the fit penalizes. Its empirical effect depends on the batch (Appendices H.3 and H.11).

Q5. Nonlinear experts and baselines. With the slow nonlinear expert, ridge and neural cloning both settled from every start. Under uniform logging at N=1024N=1024, their diagnostic certificates missed the rate on 100% and 8.4% of starts, respectively. Zero-onset Algorithm 1 had zero detections. With the fast expert, both cloners passed the rate test. In the four-state cart-pole comparison, NLC-on-model had 0/384 detections at N=1024N=1024, and ridge cloning used less effort and settled faster. On a new six-state quadrotor with an LQR expert, both cloners had no detection and zero-onset Algorithm 1 had at best 3 in 49,152 starts, at 4,096 episodes (Section 5, Appendices G.7 and H.15).

Q6. When use the passive route? With a justified coverage bound, the report is available before the replacement’s first plant trial. When representative independent trials of a frozen controller are feasible, 59 event-free trials give a one-sided 95% upper limit of 4.95% if each trial measures the target event. With only expert data and no coverage evidence, Proposition 11 still bounds violations at logged states.

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

This paper studies how to learn a stabilizing controller for an unknown physical system from a fixed offline batch of expert demonstrations. A standard model-based approach tries to learn the system's unknown physics accurately in every direction before using the model for control. The authors observe that if the goal is simply to keep a "Lyapunov energy function" decreasing toward the target state, most model errors do not actually matter: errors sideways to the energy bowl's slope, or errors that make the system look less stable than it really is, do not cause stability failures. Only errors that underestimate how strongly the system's natural physics pushes the state "uphill" are dangerous. Building on this idea, the paper jointly learns an energy function and a physics predictor using a one-sided directional loss, provides finite-sample theoretical guarantees for when training performance transfers to the deployed controller, and demonstrates the method on simulated pendulum and cart-pole tasks.

Critical strengths
  • While projecting model uncertainty onto ∇V\nabla V has been used before for a fixed certificate, the paper extends this to jointly evaluating (V,F)(V,F) from offline data via a one-sided warning loss (Lemma 3) that combines the expert's decrease deficit with only the harmful (uphill) sign of the drift error.

  • The theoretical analysis shows that you can obtain finite-sample stability guarantees on the true unknown plant without ever needing full-vector dynamics accuracy. This is further supported by a minimax construction (Theorem 4) where closed-loop stability risk vanishes with NN even though uniform drift estimation error stays bounded away from zero.

  • The experiments illustrate this separation well. Standard system ID (MSE-ID+QP) gets low (under 3.5%) physics error on pendulum and cart-pole yet fails on 30%–48% of rollouts, while the proposed directional methods have huge overall model error (41.9% and 89.6%) yet get 0/384 stability violations at N=1024N=1024.

Critical weaknesses
  • The end-to-end offline deployment bound (QN=min⁡{1,U/νenc}Q_N = \min\{1, U/\nu_{\text{enc}}\}) depends on the encounter coverage parameter νenc\nu_{\text{enc}} (Assumption 4). Since there does not seem to be a way to know or verify νenc\nu_{\text{enc}} from passive data without knowing the true dynamics, the offline risk bound in the experiments defaults to QN=1Q_N = 1 (vacuous). The non-vacuous certificate in Section 5 comes instead from post-hoc interval verification using the true simulator equations.

  • Jointly optimizing VV and FF is inherently non-convex because the directional error ∇V(x)⊤F(x)\nabla V(x)^\top F(x) is bilinear in (V,F)(V,F). To get a convex problem, the main algorithm discretizes V\mathcal{V} into a pre-specified finite library of KK candidate certificates and solves a two-stage lexicographic program for each one. Building a library that contains a valid certificate relies on prior nominal-model grids (which may not scale well to higher dimensions). While the statistical guarantees generally scale with log⁡K\log K, the computational complexity is linear in KK, limiting practical application.

  • As the authors acknowledge in the discussion, the method and its guarantees assume exact, noise-free state derivative measurements (x˙\dot{x}) and an exact known control matrix g(x)g(x). Given that OURS-scenario takes a hard maximum over the batch and already shows noticeable sensitivity on clean data at smaller sample sizes (N=128N=128 on cart-pole, getting 144/384 violations vs. 21/384 for the average-loss OURS-ERM), it is a concern how brittle the approach might be under realistic observation noise.

  • In the main-text experiments (Table 1), simple behavioral cloning (BC-ridge) gets 0/384 violations everywhere without needing x˙\dot{x}, g(x)g(x), or a QP at runtime, likely because the benchmark experts are linear and stable. What is missing from the experiments is a clear regime where behavioral cloning fails to stabilize the system while the proposed approach succeeds. Also, as a minor point, Table 1 calls the method OURS-ERM while the text calls it R39-ERM.

Questions for authors
  • Without knowing the true plant dynamics to run post-hoc verification, is there a realistic regime or method where νenc\nu_{\text{enc}} (or the spatial conditions in Proposition 5) can be certified from offline data alone so that the deployment guarantee is non-vacuous?

  • Can you show a setting in the main paper (for example, with a nonlinear expert) where simple behavioral cloning fails to stabilize the system while your approach succeeds?

  • Can you add a discussion on how system/observation noise would affect your results?

5 comments
AuthorsOpenReview ↗

General comment (1/2)

The uploaded full paper includes a linked guide for each reviewer in the supplement material pdf immediately after the references. The links under each question and concern jump to the passages highlighted for that item. Footer links take you back to the guide.

The reviewers ask what a batch of expert demonstrations can establish about a controller that will take different actions. The risk we bound is the probability that a fresh start leads to any violation of the prescribed Lyapunov decrease over a fixed horizon. On a trajectory that meets this requirement, the certificate decays at least exponentially through the stated horizon. We give a worked offline certificate, a model-assisted proof for the fitted pendulum controllers, and matched tests of decrease and terminal settling.

A worked certificate before the first replacement rollout. The terminal-record coverage example uses an oscillator with unknown drift coefficients. The learner knows their ranges and the reset rule. The expert and replacement follow different trajectories, but radial ordering makes the expert’s terminal record cover the warning along the replacement path. With 32 episodes, this gives a 95% deployment bound of 13.985%. All 32 test starts lie outside the inner disk. The oscillator figure shows why the entire 4% of nominal risk lies inside it. The structural information matters because two plants can generate identical complete expert paths while every candidate controller in the class fails on at least one plant (Proposition 17, Sections 3 and 5, Appendix G.9).

Where the statistical rate is sharp. For a fixed certificate library and affine predictor class, the sufficient episode budget depends on the requested risk, confidence and coverage. On the constructed realizable family, Algorithm 1 attains the minimax order of expected deployment risk in the episode count, predictor dimension and coverage, even though uniform drift-estimation error remains bounded away from zero (Theorem 4 and Proposition 14).

What the benchmarks establish. With a training margin and designed logging at 1,024 episodes, Algorithm 1 had zero detected decrease violations in 196,608 pendulum and cart-pole deployments across four instances. Full-vector identification followed by the same QP had detections on 46% to 100% of starts. A second study on new batches had zero detections for every share of designed resets from 10% to 100% (Appendix H.15). With the slow nonlinear pendulum expert under uniform logging, both cloners settled from every start. Ridge and neural cloning nevertheless missed the prescribed decrease on 100% and 8.4% of starts, respectively (Section 5). Under zero-mean derivative noise, detections of Algorithm 1 began only at median noise-to-signal ratios of 37.8% and 55.5%, and new Proposition 19 covers sign-symmetric noise of any size (Appendix H.15). On a new six-state quadrotor with a linear expert, both cloners had no detection and Algorithm 1 had at best 3 in 49,152 starts, at 4,096 episodes (follow-up comment).

The passive deployment report is one on both benchmarks. For three frozen pendulum fits, the optimizer checks and a model-based invariant-set proof give a 95% deployment bound below 2.874% per fit under independent draws from the benchmark’s finite-precision reset law. A separate interval proof establishes all-time decrease on the full reset disk. For three cart-pole fits on independently reconstructed batches, treating their records as exact gives a bound below 0.04550 on mean logged warning loss. The exact 0.011 margin proved for the enlarged cart-pole reset law concerns the expert. For the 12 zero-onset cart-pole fits under that law, an interval proof on the model now gives all-time decrease from every reset (Appendices G.8 and H.14).

We retained the submitted title for review. If accepted, we will use Sharp Sample Complexity for Certifying Lyapunov Decrease in Offline Control of Unknown Systems for the camera-ready version.

AuthorsOpenReview ↗

General comment (2/2)

Three additions to the revised manuscript concern the designed expert resets (rKsi Q5, ZbmT Q1 and W1, gP8d Q1) and a system above four states (gP8d Q5, rKsi W5). All were specified before their data.

How much designed logging is needed (Appendix H.15, Figure 14). The designed laws of the paper draw each expert reset from a probe law with probability one half: near the origin for the pendulums, and on an enlarged set for cart-pole. We varied this probability γ\gamma over 0, 0.025, 0.1, 0.25, 0.5, 0.75 and 1 on the four benchmarks, with 12 new batches per cell and deployment starts from the original law. At N=1024N=1024, Algorithm 1 at zero onset had 467 and 112 detections in 49,152 cart-pole starts at γ=0\gamma=0 and 0.025. It had none in 196,608 starts across the four benchmarks at every share from 0.1 to 1. At N=128N=128, detections vanished from γ=0.25\gamma=0.25 with the slow nonlinear expert and from 0.025 with the fast one. On cart-pole at N=128N=128 they were fewest at 0.25 and 0.5 (72 and 65 of 12,288) and rose to 6,398 at γ=1\gamma=1, where no reset comes from the deployment law. MSE-ID+QP had detections on 27.4% to 100% of starts in every cell. With zero-mean derivative noise added, the noise level at which most starts have detections was the same at all seven shares.

What the design certifies. These counts are measurements. The reset coefficient of Appendix C.3 is at most 5⋅10−12γ5\cdot10^{-12}\gamma on the pendulums and 2.1⋅10−27γ2.1\cdot10^{-27}\gamma on cart-pole, so the passive report on the physical benchmarks remains one, as stated. Measured with simulator labels, the probe law gave a positive logged loss for each of the 878 fitted pairs with detections on at least 1% of starts. The ratio of that loss to the mean path score was below the oscillator's 0.916 for 607 of 965 pairs. The design thus exposes each such controller in the logs, without a uniform coefficient.

A six-state benchmark (Appendix H.15, Figure 15). We repeated the logging and expert comparison on a planar quadrotor with six states, two inputs and an LQR expert (p=42p=42, K=73K=73, 12 batches per cell). Under the uniform reset law, Algorithm 1 at zero onset had detections from 1,749 of 12,288 starts at N=128N=128, 115 of 49,152 at N=1024N=1024 and 3 of 49,152 at N=4096N=4096. MSE-ID+QP had detections from 84% to 97% of starts, and ridge and neural cloning of the linear expert had none in any cell. Every trajectory of every method settled, so the detections concern the prescribed rate. The probe laws did not lower the counts at N=1024N=1024 or 4096. At share one half and N=4096N=4096, the near-origin law gave 22 detections and the enlarged law 30,785, with slack above bb in every fit, so the report was one. This is one system above four states. It does not measure scaling with dimension.

From a sampled check to a proof on cart-pole (Appendix G.8). The manuscript reported a sampled check of one zero-onset cart-pole fit under enlarged logging. An interval branch-and-bound now covers the whole certificate sublevel set containing the reset set, for all 12 such fits at N=1024N=1024. Each fit is verified: the normalized decrease residual is at most −10−4-10^{-4} on the set, with 15.9 to 49.7 million accepted boxes per fit and 17.2 CPU-hours in total. Hence VV decreases at the prescribed rate along every model trajectory from the reset set, for all time, for each of the 12 controllers. The same program verifies the three pendulum fits of Appendix G.8 and returns a counterexample for a cart-pole fit with measured violations. As for the pendulum, this is a verification with the plant model after fitting, and the passive report is unchanged.

These runs used a second machine. Its check against 48 rows of Table 1 reproduces every Algorithm 1 count and differs in one MSE-ID+QP count, so the share study is reported from its own rows.

AuthorsOpenReview ↗

Response to —— ZbmT —— on Coverage, Baselines, and Measurement Noise (1/2)

Your guide is in the supplement of the uploaded full paper, just after the references. Links under each question and concern jump to the highlighted passages. If accepted, we will use Sharp Sample Complexity for Certifying Lyapunov Decrease in Offline Control of Unknown Systems for the camera-ready version.

Q1. Can coverage be established before deployment? Yes, if the logging rule and known plant structure relate expert records to replacement paths. In the terminal-record coverage example (Appendix G.9), the oscillator’s drift coefficients are unknown but their ranges are given. The expert contracts radially faster than every selectable replacement, and the warning increases toward smaller radii. The terminal expert record then bounds every replacement warning from the same start. If a known fraction η\eta of expert starts comes from the deployment law, η\eta is a coverage lower bound before fitting. At η=1\eta=1 and N=32N=32, the 95% deployment bound is 13.985%. The nominal risk is 4%. All 32 test starts lie outside the violating disk. The reset-frequency study estimates informative-reset probability on the same batch with a separate confidence allocation (Appendix G.10).

Proposition 17 constructs two plants with identical complete expert paths. Each candidate in the class violates decrease on at least one plant. The passive deployment report is one on the two physical benchmarks. For three frozen pendulum pairs, model verification gives coverage one and a 95% bound below 2.874% per fit under independent draws from the benchmark’s finite-precision reset law (Appendix G.8). The spatial alternative in Proposition 5 requires a lower bound on logged-state density, residual regularity and sublevel containment.

Q2. Does a cloner fail to stabilize? Both cloners settled on all tested starts for the slow and fast nonlinear pendulum experts. The prescribed decrease distinguishes them. With the slow expert and N=1024N=1024, ridge cloning missed the rate on 100% of starts. Neural cloning missed it on 8.4% under uniform logging and 10.5% under near-origin logging. Each cloner used a diagnostic certificate selected from the common library on its training batch. Algorithm 1 at zero onset passed both tests for every start under both laws. With the fast expert, both cloners passed the decrease test. With the slow expert, full-vector identification plus the QP missed terminal settling on 43.4% and 13.6% under the two laws (Section 5 and Appendix H.15).

Q3. What changes with measurement noise? With exact states and actions, a bounded derivative error consumes training margin (Proposition 15), and a sign-symmetric error of any size at most doubles the tail term (new Proposition 19). Proposition 16 treats a bounded error in the input map. The derivative-noise study now continues until detections occur. With zero-mean noise, Algorithm 1 at zero onset had zero detections up to median noise-to-signal ratios of 12.6% on pendulum and 16.6% on cart-pole. Detections began at 37.8% and 55.5%, after the fitted slack had already set the report to one. With errors reflected to hide warnings, the slack stayed zero and detections began one to two decades earlier. State error affects warning evaluation and feedback. Process noise also changes which states deployment reaches (Appendices H.7 and H.15, Figure 11). Our follow-up comment gives the details.

Library cost and method names. Nominal model ranges and LQR weights generate the cart-pole library. It can require KK convex fits, although its statistical penalty grows as log⁡K\log K. Appendix D.5 screens candidates by slack. Appendix H.8 gives a single convex fit in a distinct quadratic-certificate class, with a dimension counting both certificate and drift coefficients. OURS-ERM and R39-ERM denote the same average-loss estimator. R39 was an internal identifier. At zero objective it agrees with zero-onset Algorithm 1 under the common tie rule (Appendix H.3).

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

This paper develops a statistically principled method for learning a Lyapunov certificate and a control-relevant drift predictor from a fixed batch of expert demonstrations, then synthesizing a replacement controller through a soft control-Lyapunov-function quadratic program (CLF-QP). The paper’s main idea is a warning signal that detects two possible problems: the proposed Lyapunov function does not decrease enough under the expert, or the learned dynamics are wrong in a way that threatens stability.

Critical strengths
  • The motivating problem is interesting.
  • The technical derivation appears to be non-trivial.
Critical weaknesses
  • The readability of the paper is very low. I'm actually not sure how much of this is due to the use of AI or the fact that the paper is simply not very coherent in its main message.
  • The practical relevance of the results is unclear. I see Theorem 1 as the main theorem. I read it multiple times, yet I still cannot understand what it is trying to say.
  • The title of the paper appears very broad, but I'm not sure what it actually delivers. "Sample complexity" for achieving what? In what sense is it sharp?
  • The assumptions substantially limit the applicability of the results (if any). Assumption 4 appears to be the worst. What did \nu_enc come from?
  • For this type of certificate, there has to be a curse of dimensionality somewhere. This is unclear because the paper doesn't explain it.
Questions for authors
  • Are the assumptions satisfied by the numerical examples in the paper? Are all the constants involved computable? What did the experiments actually demonstrate?
  • Can you explain where there might be a curse of dimensionality?
  • What does sharp sample complexity mean?
  • Can you elaborate in plain language on the significance of the results?
  • Can the authors provide one worked example in which a positive \nu_{enc} is certified without using post-fit access to the true plant? What information does the procedure require, what value results, and what final Q_N does it produce?
4 comments

Just following up, as I am hoping to get a response from the authors regarding my questions.

AuthorsOpenReview ↗

Response to —— rKsi —— on Deployment Risk and Coverage (1/1)

Thank you for following up. Overlapping deadlines delayed our reply. Open the highlighted full paper in Supplementary Material. Your guide follows the references and links each question and concern to highlighted passages.

Q4. What can Theorem 1 tell a practitioner? Before the replacement runs, the expert’s recorded state, action and derivative reveal shortfalls in its decrease and drift errors that hide a violation. Lemma 3 shows that every decrease violation triggers a warning. Coverage measures how well the logs expose warnings along replacement paths. If the 95% upper bound on mean logged loss is 0.02 and coverage is at least 0.5, the deployment risk is at most 4% at that confidence. For at least 96% of starts, V(x(t))V(x(t)) stays at or below e−λtV(x(0))e^{-\lambda t}V(x(0)) through time TT. Because VV is bounded above and below by multiples of the squared state norm, this gives an exponential bound on the distance to equilibrium through TT.

Boffi et al. learn certificates for new trajectories of a fixed dynamical system. Changing feedback can change the closed-loop dynamics even when the plant is known. Taylor et al. use successive rollouts of a simulated Segway to learn uncertainty in a CLF derivative. Here one expert batch must suffice for the replacement feedback. The AI use statement describes the assistance used. Boffi et al. · Taylor et al.

Q3. What does the title mean? We retained the submitted title for review. If accepted, we will use Sharp Sample Complexity for Certifying Lyapunov Decrease in Offline Control of Unknown Systems for the camera-ready version. “Sample complexity” counts the expert episodes sufficient to bound the probability of any Lyapunov decrease violation under the learned feedback through time TT, and “sharp” means the algorithm attains the matching minimax expected-risk order in episode count, predictor dimension and coverage on a realizable CLF-QP family. At zero effective slack, 2[p+log⁡(K/δ)]/(ϵνenc)2[p+\log(K/\delta)]/(\epsilon\nu_{\rm enc}) episodes suffice for pp coefficients, KK certificates, target risk ϵ\epsilon and confidence 1−δ1-\delta. The matching lower bound concerns expected risk (Theorems 3–4, Proposition 14).

Q5. Where does positive coverage come from? In the terminal-record coverage example (Appendix G.9), the oscillator’s radial drift is (κ−γr2)x(\kappa-\gamma r^2)x, with κ\kappa in [0.4, 0.5] and γ\gamma in [0.1, 0.2]. The learner knows these ranges, the expert uE=−xu_E=-x, the declared certificate and predictor class, and the reset rule. The expert contracts faster, so its terminal warning dominates all replacement warnings from the same start. If a known fraction η\eta of expert starts comes from the deployment law, coverage is at least η\eta before fitting. With η=1\eta=1 and 32 episodes, the 95% report is 0.13985 and nominal risk is 4%. No post-fit plant access enters the report.

Q1. Which assumptions and constants can be checked? The input map, QP and libraries are design inputs. The simulator equations supply regularity and containment and verify expert witnesses for all three pendulum experts and both cart-pole reset laws. On the enlarged cart-pole law, exact rational bounds give a margin of 0.011. The assumption and parameter tables in H.5 and H.12 identify which inputs require the model. With passive expert records alone, the benchmark report is one. The logging and expert comparison tests decrease on a numerical grid (Section 5 and Appendix H.14).

Q2. Where does dimension enter? A uniform reset in a radius-RR ball hits an interior radius-rr ball with probability (r/R)n(r/R)^n. A fixed local requirement can thus cost exponentially many episodes in state dimension. Predictor and library sizes may grow as well. In the separate spatial result, halving the exceptional radius costs about 2n2^n times as many episodes at the 1/N1/N rate with other constants fixed (Proposition 18).

AuthorsOpenReview ↗

General comment (1/2)

The uploaded full paper includes a linked guide for each reviewer in the supplement material pdf immediately after the references. The links under each question and concern jump to the passages highlighted for that item. Footer links take you back to the guide.

The reviewers ask what a batch of expert demonstrations can establish about a controller that will take different actions. The risk we bound is the probability that a fresh start leads to any violation of the prescribed Lyapunov decrease over a fixed horizon. On a trajectory that meets this requirement, the certificate decays at least exponentially through the stated horizon. We give a worked offline certificate, a model-assisted proof for the fitted pendulum controllers, and matched tests of decrease and terminal settling.

A worked certificate before the first replacement rollout. The terminal-record coverage example uses an oscillator with unknown drift coefficients. The learner knows their ranges and the reset rule. The expert and replacement follow different trajectories, but radial ordering makes the expert’s terminal record cover the warning along the replacement path. With 32 episodes, this gives a 95% deployment bound of 13.985%. All 32 test starts lie outside the inner disk. The oscillator figure shows why the entire 4% of nominal risk lies inside it. The structural information matters because two plants can generate identical complete expert paths while every candidate controller in the class fails on at least one plant (Proposition 17, Sections 3 and 5, Appendix G.9).

Where the statistical rate is sharp. For a fixed certificate library and affine predictor class, the sufficient episode budget depends on the requested risk, confidence and coverage. On the constructed realizable family, Algorithm 1 attains the minimax order of expected deployment risk in the episode count, predictor dimension and coverage, even though uniform drift-estimation error remains bounded away from zero (Theorem 4 and Proposition 14).

What the benchmarks establish. With a training margin and designed logging at 1,024 episodes, Algorithm 1 had zero detected decrease violations in 196,608 pendulum and cart-pole deployments across four instances. Full-vector identification followed by the same QP had detections on 46% to 100% of starts. A second study on new batches had zero detections for every share of designed resets from 10% to 100% (Appendix H.15). With the slow nonlinear pendulum expert under uniform logging, both cloners settled from every start. Ridge and neural cloning nevertheless missed the prescribed decrease on 100% and 8.4% of starts, respectively (Section 5). Under zero-mean derivative noise, detections of Algorithm 1 began only at median noise-to-signal ratios of 37.8% and 55.5%, and new Proposition 19 covers sign-symmetric noise of any size (Appendix H.15). On a new six-state quadrotor with a linear expert, both cloners had no detection and Algorithm 1 had at best 3 in 49,152 starts, at 4,096 episodes (follow-up comment).

The passive deployment report is one on both benchmarks. For three frozen pendulum fits, the optimizer checks and a model-based invariant-set proof give a 95% deployment bound below 2.874% per fit under independent draws from the benchmark’s finite-precision reset law. A separate interval proof establishes all-time decrease on the full reset disk. For three cart-pole fits on independently reconstructed batches, treating their records as exact gives a bound below 0.04550 on mean logged warning loss. The exact 0.011 margin proved for the enlarged cart-pole reset law concerns the expert. For the 12 zero-onset cart-pole fits under that law, an interval proof on the model now gives all-time decrease from every reset (Appendices G.8 and H.14).

We retained the submitted title for review. If accepted, we will use Sharp Sample Complexity for Certifying Lyapunov Decrease in Offline Control of Unknown Systems for the camera-ready version.

AuthorsOpenReview ↗

General comment (2/2)

Three additions to the revised manuscript concern the designed expert resets (rKsi Q5, ZbmT Q1 and W1, gP8d Q1) and a system above four states (gP8d Q5, rKsi W5). All were specified before their data.

How much designed logging is needed (Appendix H.15, Figure 14). The designed laws of the paper draw each expert reset from a probe law with probability one half: near the origin for the pendulums, and on an enlarged set for cart-pole. We varied this probability γ\gamma over 0, 0.025, 0.1, 0.25, 0.5, 0.75 and 1 on the four benchmarks, with 12 new batches per cell and deployment starts from the original law. At N=1024N=1024, Algorithm 1 at zero onset had 467 and 112 detections in 49,152 cart-pole starts at γ=0\gamma=0 and 0.025. It had none in 196,608 starts across the four benchmarks at every share from 0.1 to 1. At N=128N=128, detections vanished from γ=0.25\gamma=0.25 with the slow nonlinear expert and from 0.025 with the fast one. On cart-pole at N=128N=128 they were fewest at 0.25 and 0.5 (72 and 65 of 12,288) and rose to 6,398 at γ=1\gamma=1, where no reset comes from the deployment law. MSE-ID+QP had detections on 27.4% to 100% of starts in every cell. With zero-mean derivative noise added, the noise level at which most starts have detections was the same at all seven shares.

What the design certifies. These counts are measurements. The reset coefficient of Appendix C.3 is at most 5⋅10−12γ5\cdot10^{-12}\gamma on the pendulums and 2.1⋅10−27γ2.1\cdot10^{-27}\gamma on cart-pole, so the passive report on the physical benchmarks remains one, as stated. Measured with simulator labels, the probe law gave a positive logged loss for each of the 878 fitted pairs with detections on at least 1% of starts. The ratio of that loss to the mean path score was below the oscillator's 0.916 for 607 of 965 pairs. The design thus exposes each such controller in the logs, without a uniform coefficient.

A six-state benchmark (Appendix H.15, Figure 15). We repeated the logging and expert comparison on a planar quadrotor with six states, two inputs and an LQR expert (p=42p=42, K=73K=73, 12 batches per cell). Under the uniform reset law, Algorithm 1 at zero onset had detections from 1,749 of 12,288 starts at N=128N=128, 115 of 49,152 at N=1024N=1024 and 3 of 49,152 at N=4096N=4096. MSE-ID+QP had detections from 84% to 97% of starts, and ridge and neural cloning of the linear expert had none in any cell. Every trajectory of every method settled, so the detections concern the prescribed rate. The probe laws did not lower the counts at N=1024N=1024 or 4096. At share one half and N=4096N=4096, the near-origin law gave 22 detections and the enlarged law 30,785, with slack above bb in every fit, so the report was one. This is one system above four states. It does not measure scaling with dimension.

From a sampled check to a proof on cart-pole (Appendix G.8). The manuscript reported a sampled check of one zero-onset cart-pole fit under enlarged logging. An interval branch-and-bound now covers the whole certificate sublevel set containing the reset set, for all 12 such fits at N=1024N=1024. Each fit is verified: the normalized decrease residual is at most −10−4-10^{-4} on the set, with 15.9 to 49.7 million accepted boxes per fit and 17.2 CPU-hours in total. Hence VV decreases at the prescribed rate along every model trajectory from the reset set, for all time, for each of the 12 controllers. The same program verifies the three pendulum fits of Appendix G.8 and returns a counterexample for a cart-pole fit with measured violations. As for the pendulum, this is a verification with the plant model after fitting, and the passive report is unchanged.

These runs used a second machine. Its check against 48 rows of Table 1 reproduces every Algorithm 1 count and differs in one MSE-ID+QP count, so the share study is reported from its own rows.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.