Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: In this paper the author proposed an MPC algorithm in which both the dynamics function and the Lyapunov function are parameterized with neural networks.. Specifically leveraging the results of Lyapunov networks (2018 CORL paper: https://arxiv.org/abs/1808.00924) for learning Lyapunov functions, the authors derived an MPC algorithm for quadratic cost/reward problems and also proved the stability, robustness, and sub-optimality performance. To demonstrate the effectiveness of the algorithms, the authors also evaluated this approach on the simple inverted pendulum and car kinematics tasks. 

In general I find this paper presents a comprehensive results of a model-based control method that is very popular in the control theory community. To justify their algorithms they also proved several standard properties (stability, sub-optimality performance) in control, which I appreciate their efforts. However, I do have severals questions/concerns regarding the details of their approach:

1) The presentation of the loss function of Lyapunov network is not easy to parse, especially there are couple terms that contain specific mathematical operators (sign, ReLU). Can the authors explain each term in the loss and why such choices of loss terms are necessary. Is this loss function identical to the Lyapunov network 2018 CORL paper?

2) From the main paper it is unclear how the NN-dynamics model \hat f is learned. Does it just train based on prediction loss? More importantly, while the MPC algorithm uses the learned model how does the dynamics model error affect the stability/robustness/performance bounds of the control algorithm? I cannot immediately find this information in lemma 1 and lemma 2, which makes me worried about the correctness of these results. (Unfortunately I haven't had a chance to check the appendix for proofs)

3) Having sub-optimality performance for MPC algorithms is a nice result, as not many MPC algorithms have performance guarantees. However these kind of results are also not new (for example, see https://ieeexplore.ieee.org/document/4639448).  How does the MPC performance result here compared with the ones by Grune and Rantzer? 

4) Among various safe MPC papers, how does the proposed one in this paper compared with this safe MPC algorithm: https://arxiv.org/pdf/1803.08287.pdf, which is also proposed by Andreas Krause's group (that proposed the Lyapunov network)? At least experimentally how does the proposed algorithm compare with other safe MPC baselines (such as the one above) on the standard benchmark tasks (for example the above work also tested the algorithms on the pendulum task).

On the overall, I find this paper's algorithm interesting. However, there are several technical question listed above, and one high-level concern is its novelty. Without further discussions, it appears to me that the work combines several existing results on Lyapunov network and MPC, for which the contribution is rather incremental.
review_title: Paper presents solid control theoretical foundation, though unsure how novel the ideas are

final_score: rating: 3: Clear rejection
review_content: This paper proposes an MPC algorithm based on a learned (neural network) Lyapunov function. In particular, they learn both the Lyapunov function and the forward model of the dynamics, and then control the system using an MPC with respect to these models.

Cons
- Poorly written
- Unclear connections to related work
- Weak experiments

It is unclear exactly what problem the authors are attempting to solve. In general, the authors introduce a large amount of notation and theory, but very little of it appears to be directly related to their algorithm. For example, they refer to the stability guarantees afforded by Lyapunov functions, but as far as I can tell, they never prove that their algorithm actually learns a Lyapunov function (indeed, Lemma 1 starts with “Assume that V(x) satisfies (5) [the Lyapunov condition] ...”).

Similarly, they allude to “robustness margins to model errors”, but nothing in the algorithm actually takes into account model errors. Is the point of these margins just to show that they exist? If so, it’s not clear the results (either theoretical or empirical) are very meaningful, given that they depend on the unknown model error (which they assume to be bounded).

In addition, the different loss functions they use (e.g., (10)) are poorly justified. Why is this loss the right one to use to learn a Lyapunov function?

Furthermore, the authors’ approach is closely related to learning the value function and planning over some horizon using the value function as the terminal cost (indeed, the value function is a valid Lyapunov function, but not necessarily vice versa). For instance;

Buckman et al., Sample-Efficient Reinforcement Learning with Stochastic Ensemble Value Expansion. In NeurIPS, 2018.

The most closely related work I’m aware of is the following:

Deits et al., Lvis: Learning from value function intervals for contact-aware robot controllers. In ICRA, 2019.

The authors should clarify their contributions with respect to these papers. More importantly, the authors should discuss their motivation for indirectly learning a Lyapunov function instead of simply learning the value function (which appears to be more natural and potentially more effective).

Next, the authors’ experiments are very weak. They only consider two environments, the inverted pendulum and car, both of which are very simple. The inverted pendulum starts near the unstable equilibrium, which further trivializes the problem. In addition, they do not even appear to give the dynamics model of the car they are using (or the state space).

Finally, this paper is poorly written and hard to follow. They provide a lot of definitions and equations without sufficient explanation or justification, and introduce a lot of terminology without giving sufficient background.

------------------------------------------------------------------------------------------------------------------------------------------------

Post rebuttal: While I appreciate the authors' comments, they do not fundamentally address my concerns that the paper is too unclear in terms of the meaning of its technical results to merit acceptance. As a concrete example, in their clarification, the authors indicate that they obtain "probabilistic safety guarantees" by checking the Lyapunov condition (5) using sampling. However, at best, sampling can ensure that the function is "approximately" Lypaunov (e.g., using PAC guarantees) -- i.e., satisfies (5) on all but 1-\epsilon of the state space.

Unfortunately, an "approximately" Lyapunov function (i.e., satisfies the Lyapunov condition (5) on 1-\epsilon of the state space) provides *zero* safety guarantees (not even probabilistic safety at any confidence level). Intuitively, at each step, the system has a 1-\epsilon chance of exiting a given level set of the Lyapunov function. These errors compound as time progresses; after time horizon T, only 1 - T * \epsilon of the state space is guaranteed to remain in the level set, so eventually the safety guarantee is entirely void.

One way to remedy this is if the Lyapunov function is Lipschitz continuous. However, then, the number of samples required would still be exponential in the dimension of the state space. At this point, existing formal methods tools for verifying Lyapunov functions would perform just as well if not better, e.g., see:

Soonho Kong, Sicun Gao, Wei Chen, and Edmund Clarke. dReach: δ-Reachability Analysis for Hybrid Systems. 2015.

This approach was recently applied to synthesizing NN Lyapunov functions (Chang et al. 2019). My point isn't that the authors' approach is invalid, but that given the current writing it is impossible for me to understand the theoretical properties of their approach.

Overall, I think the paper may have some interesting ideas, but I cannot support publishing it in its current state
review_title: Poorly motivated and unclear contributions

final_score: rating: 7: Good paper, accept
review_content: This paper addresses the question of how to stabilize a system in a vicinity of an equilibrium. While the majority of reinforcement learning algorithms rely on trial and error, which may damage the system, the authors introduce an algorithm for safe exploration and control. A traditional approach in model-based RL is to use MPC with a surrogate forward model to minimize a planning objective comprising a sum of stage costs along with a terminal cost, often chosen as an approximated value function -i.e. the optimal expected cost-to-go- which can be learned by a Bellman equation. Instead, this work is placed in the framework of Robust MPC, where this value function is replaced by a Luyapunov function $V$, which is related to the notion of stability and is only constrained to decrease along trajectories. Such a Luyapunov function, when available, provides both a safe region, defined as a level-set of V, and a MPC policy for which stability analyses have been developed: the authors extend a result from Limon et al. (2003; 2009) to show that this MPC policy enjoys asymptotic stability in general, and input-to-state stability in the presence of small enough model errors. Accordingly, the authors propose a scheme allowing to learn a Lyapunov function $V$ from demonstration data only, through a loss function that penalizes increments of $V$ along one-step transitions. A regularization parameter $\alpha$ of this MPC, which balances stability with constraints satisfaction and stage costs, is also learned jointly by an alternative training procedure. This approach is evaluated empirically on two standard constrained non-linear continuous control tasks.


Strong points:
1. This paper is clearly written, well motivated, honest about its place in the literature, and all derivations seem technically correct.
2. By bringing together existing results and techniques (MPC stability analyses, value-based RL analyses, LuyapunovNet), the authors manage to relax several assumptions of prior works (no need for access to the perfect dynamics or a stabilizing policy, but only to a demonstration dataset) which makes the approach more practical.
3. Empirically, the learned Luyapunov functions seem to effectively capture useful stability information, since the proposed approach outperforms a standard MPC with a longer planning horizon. Even better, this observation is theoretically justified by Lemma 2: errors of the surrogate model compound when used in an MPC, which is detrimental for long-term planning. Conversely, if $V$ contains long-term information, it can directly be used for short-sighted planning, similarly to being greedy with respect to a value function.


Weak points:
1. The part which was the least clear to me is the *Performance with surrogate models* paragraph, with Lemma 2. The authors draw a parallel between Luyapunov functions in control theory and value functions in RL, but the latter are not really defined clearly in the text. The authors state in their introduction that they treat "the learned Lyapunov NN as an estimate of the value function" and later they mention a "correct" value function $V^*$ for optimal "expected infinite-horizon performance", but this quantity is nowhere defined. I suppose $V^*$ is an expected infinite sum of discounted stage costs, but which costs? The same as in equation (3)? If so, I find it hard to believe that the assumption of Lemma 2 should be satisfied ($V^*$ close to $\alpha V$), given that the stage cost $l$ of (3) used to define $V^*$ does not appear in the loss (10) used to learn the Lyapunov function $V$.
2. I find it difficult to assess the novelty of the theoretical results. The authors are honest in stating that they are extending/adapting known results, but it is not precisely stated what their added value is. Moreover, the abstract mentions that "we also present theorems" but in the article these results are presented as lemmas, which to me usually suggests that they are either instrumental to another result (which they are not), or of minor importance.
3. One of the main claim of the paper is the ability of the method to expand a demonstrated safe region. However, this is not really observed consistently across tasks and iterations. For instance, it is not the case in Figure 3. Likewise, the Table 1 states that "With iterations, the number of points verified by the controller increases", but only a two iterations is provided (i.e. a single opportunity to increase/decrease). This seems a bit suspicious and suggests that the ratio of verified points may actually decrease on subsequent iterations, as it does on iteration 3 of Table 3.


To conclude, I lean toward recommending acceptance, but I am ready to increase my score provided that the authors improve the clarity on both the analogy between Lyapunov and value functions, and state more clearly the novelty of their theoretical contributions.


Minor remarks and typos:
* I do not really see the relevance of the safety performance metric in the Inverted Pendulum experiment (Fig. 3): the state constraints are loose enough that every successful trajectory is also considered safe, so this safety plot (right) does not really bring any new information to the table.
* p2, Equation (5): X_s\ **X_T**
* p3, Learning and Safety Ver**i**fication
* p6, to minimize the loss defined in **(11)**
review_title: Promising work, but unclear theoretical novelty and empirical achievements

Meta-review: The authors propose an MPC based approach for learning to control systems with continuous state and actions - the dynamics, control policy and a Lyapunov function are parameterized as neural networks and the authors claim to derive stability certificates based on the Lyapunov function.

The reviewers raised several serious technical issues with the paper as well as the lack of clarity in the presentation of the main technique in the initial version of the paper. While the clarity concerns were partially addressed during the rebuttal, the technical concerns (in particular those raised by reviewer 1) remain unaddressed - the stability certificate derived is questionable due to the fact that sampling based approaches to certifying that a function is a valid Lyapunov function are insufficient to derive any stability guarantee. Further, the experimental results are only demonstrated on relatively simple dynamical systems. Hence I recommend rejection. 

However, all reviewers agree that the ideas presented in the paper are potentially interesting - I would suggest that the authors consider revising the paper to address the feedback on technical issues and submit to a future venue.


Decision: Reject