Safely Learning to Control the Constrained Linear Quadratic Regulator

Introduction

Data-driven design has considerable potential in contemporary control systems where precise modeling of the dynamics is intractable, whether due to complex large-scale interactions or nonlinearities resulting from contact forces. However, a large hurdle in the way of practical deployment is the question of maintaining safe operating conditions during the learning process, and furthermore guaranteeing safe execution using learned components.

Motivated by this issue, we study the data-driven design of a controller for the constrained Linear Quadratic Regulator (LQR) problem. In constrained LQR, we design a controller for a potentially unknown linear dynamical system that minimizes a given quadratic cost, subject to the additional requirement that both the state and input stay within a specified safe region. This is a problem that has received much attention within the model predictive control (MPC) community.

For the LQR problem with no constraints, a natural method of exploration for learning the dynamics is to excite the system by injecting white noise. When safety is not an issue, this method is effective and recently Dean et al. provide an end-to-end sample complexity on this “identify-then-control” scheme. However, this method of fails to consider safety, and the injected white noise may lead to constraint violation.

In this paper, we directly address the tension between exploration for learning and safety, which are fundamentally at odds. We do this by synthesizing a controller which simultaneously excites and regulates the system; we propose to learn by additively injecting bounded noise to the control inputs computed by a safe controller. By leveraging the recently developed system level synthesis (SLS) framework for control design , we give a computationally tractable algorithm which returns a controller that (a) guarantees the closed loop system remains within the specified constraint set and (b) ensures that enough noise can be injected into the system to obtain a statistical guarantee on learning. To the best of our knowledge, our algorithm is the first to simultaneously achieve both objectives. Furthermore, the controller synthesis is solved by a convex optimization problem whose feasibility is a certificate of safety, and no considerations of robust invariant sets are required.

Our second contribution is to provide a sub-optimality bound on control performance for constrained LQR. Using the same SLS framework, we quantify the excess cost incurred by playing a controller designed on the uncertain dynamics obtained from learning. The sub-optimality depends on both the size of the uncertainty sets and a type of constraint robustness cost gap of the optimal constrained controller for the true system. This allows us to provide the first end-to-end sample complexity guarantee for the control of constrained systems.

Estimation and control of the unconstrained LQR problem has been studied in the non-asymptotic setting . However, the identification schemes rely on pure excitation and system restarts, which is not suitable for the constrained setting. On the other hand, the online learning literature simultaneously considers learning and control, where strategies are based on optimism in the face of uncertainty or Thompson Sampling . These approaches guarantee system estimation only up to optimal closed-loop equivalence, and do not consider safety. Building on a statistical result by Simchowitz et al. which allows for non-asymptotic guarantees on parameter estimation from a single trajectory of a linear system, Dean et al. provide a robust online method that guarantees parameter estimation and stability throughout.

The design of controllers that guarantee robust constraint satisfaction has long been considered in the context of model predictive control , including methods that model uncertainty in the dynamics directly , or model it as a bounded state disturbance for computational efficiency . Strategies for incorporating estimation of the dynamics include experiment-design inspired costs , decoupling learning from constraint satisfaction , and set-membership methods rather than parameter estimation . Due to the receding horizon nature of model predictive controllers, this literature relies on set invariance theory for infinite horizon guarantees . Our framework considers the infinite horizon problem directly, and therefore we do not require computation of invariant sets.

Finally, the machine-learning community has begun to consider safety in reinforcement learning, where much work positions itself as being for general dynamical systems in lieu of providing statistical guarantees . Some works assume the existence of an initial safe controller for learning , and robust MPC methods have been proposed to modify potentially unsafe learning inputs . Our framework gives an alternative procedure for designing such a controller using coarse system estimates. Most similar to this work is that of Lu et al. , who propose a method to allow excitation on top of a safe controller, but consider only finite-time safety and require non-convex optimization to obtain formal guarantees. We fix an underlying linear dynamical system with full state observation,

In this work, we will focus on the errors for $p=2$ and $p=\infty$.

Furthermore, we assume some prior knowledge on the system dynamics, in the form of initial estimates $(\widehat{A}_{0},\widehat{B}_{0})$ and uncertainty measures $(\varepsilon_{A,p}^{0},\varepsilon_{B,p}^{0})$. Without such knowledge, guaranteeing safety in any form would be impossible. We note that the initial estimates may be coarse grained, and the goal of the learning procedure will be to refine this uncertainty prior to optimal control design.

The constrained LQR optimal control problem seeks to minimize the expected quadratic cost, subject to constraints on the state and input. Before further detailing this objective, we develop notation and background on system level synthesis.

Many approaches to optimal control for systems with constraints involve receding horizon control, where an open loop finite-time trajectory is computed at each timestep; indeed, parameterizing optimal control problems by a state feedback controller generally leads to nonconvex optimization. As a motivating example, consider the static feedback law $u_{k}=Kx_{k}$ applied to the linear system (1.1). Then we can write

and a similar expression for $u_{k}$. Then it is clear that convex constraints on $x_{k}$ and $u_{k}$ will be non-convex in $K$. Instead, we can parametrize the problem in terms of convolution with the closed-loop system response,

where we defined $w_{-1}=x_{0}$ the fixed initial condition. We note that the expression above is valid for any linear dynamic controller, i.e. any controller which is a linear function of the state and its history. Since the relation in (1.2) is linear, convex constraints on state and input translate to convex constraints on the system response elements. The system level synthesis (SLS) framework shows that for any elements $\{\Phi_{x}(t),\Phi_{u}(t)\}$ constrained to obey, for all $k\geq 1$,

there exists a feedback controller that achieves the desired system responses (1.2). The state-feedback parameterization result in Theorem 1 of Wang et al. formalizes this principle, and therefore any optimal control problem over linear systems can be cast as a constrained optimization problem over system response elements. We remark that similar observations have been used for constrained state feedback control in the finite horizon setting .

In what follows, we use boldface letters to denote transfer functions and signals, e.g. $\mathbf{\Phi}_{x}(z)=\sum_{k=1}^{\infty}\Phi_{x}(k)z^{-k}$ and $\mathbf{x}(z)=\sum_{k=0}^{\infty}x_{k}z^{-k}$. Under this notation, the affine constraints can be rewritten as

and the corresponding control law $\mathbf{u}=\mathbf{K}\mathbf{x}$ is given by $\mathbf{K}=\mathbf{\Phi}_{u}\mathbf{\Phi}^{-1}_{x}$.

2 Notation

In this paper, we restrict our attention to the function space $\mathcal{RH}_{\infty}$, consisting of discrete-time stable matrix-valued transfer functions. We use $\frac{1}{z}\mathcal{RH}_{\infty}$ to denote the set of transfer functions $\mathbf{G}$ such that $z\mathbf{G}\in\mathcal{RH}_{\infty}$. We further define

for transfer functions that satisfy a certain decay rate in the spectral norm of their impulse response elements.

When working with transfer functions and signals, we will denote the coefficient of the term of degree $k$ as $\mathbf{G}[k]=G(k)$ and $\mathbf{x}[k]=x_{k}$. We will also denote $G[k:1]$ as the block row vector of system response elements of $\mathbf{G}$

Finally, for two numbers $a,b$, we let $a\lesssim b$ (resp. $a\gtrsim b$) denote that there exists an absolute constant $C>0$ such that $a\leq Cb$ (resp. $a\geq Cb$).

3 Optimal Control Problem

We now describe the constrained optimal control problem that we would want to solve given perfect knowledge of the system dynamics. First, we consider the expected infinite horizon quadratic cost for the system $(A_{\star},B_{\star})$ in feedback with $\mathbf{K}$:

Next, we consider polytopic constraint sets of the form

We will constrain the state and input trajectories to lie within these sets for any possible disturbance sequence $\{w_{k}\}$ satisfying $\lVert w_{k}\rVert_{\infty}\leq\sigma_{w}$ for all $k\geq 0$. Putting the cost and the constraints together, the optimal control problem that acts as our baseline is:

Above, we let the set $\mathcal{K}$ enumerate all inputs that result from linear dynamic stabilizing feedback controllers for $(A_{\star},B_{\star})$ of the form $\mathbf{u}=\mathbf{K}\mathbf{x}$. This is made possible by the system level synthesis framework described in the previous section.

As we show in the following section, the optimal control problem given in (1.3) is a convex, but infinite-dimensional problem. It is an idealized baseline to compare our actual solutions to; our sub-optimality guarantees will be with respect to the optimal cost achieved by this problem. It is a relevant baseline, since it optimizes for average case performance but ensures safety for the worst-case behavior, consistent with MPC literature . We remark that an alternative to (1.3) is to replace the worst case constraint behavior with probabilistic chance constraints . We do not work with chance constraints because they are generally difficult to directly enforce on an infinite horizon; arguments around recursive feasibility using robust invariant sets are common in the MPC literature to deal with this issue.

Constraint-Satisfying Control

We begin by formulating a method for robustly operating a system while maintaining safety. First we describe a system level synthesis approach to the constrained LQR problem, and then we propose a modification which makes it robust to uncertainties in system dynamics. Finally, we outline a reduction to tractable synthesis via a finite-dimensional optimization problem over a finite impulse response (FIR) approximation.

Using the SLS formulation, we define an optimization problem that solves the optimal control problem presented in the section above.

The following convex optimization problem solves the optimal control problem (1.3).

where the elements of the constraint functions are defined as

with $j$ indexing the rows of $F_{x}$ and $F_{u}$ and entries of $G_{x}$ and $G_{u}$.

Examining the form of the optimization problem above, we see that the expected quadratic cost transforms into a system $\mathcal{H}_{2}$ norm, while the worst-case polytopic constraints on state and input become closed-form polytopic constraints on the system response. For a controller $\mathbf{K}=\mathbf{\Phi}_{u}(\mathbf{\Phi}_{x})^{-1}$, note that the LQR cost is equivalent to

Lastly, we remark here that the feasibility of the convex synthesis problem in (2.1) for an initial condition $x_{0}$ implies that $x_{0}$ is a member of a robust control invariant set.

By the state-feedback parameterization result in Theorem 1 of , the SLS parametrization encompasses all internally stabilizing state-feedback controllers acting on the true system $(A_{\star},B_{\star})$. Thus, it is necessary only to show that the optimization problem in (2.1) is consistent with that of (1.3) under the system level parametrization. The equivalence between the LQR cost and the $\mathcal{H}_{2}$ system norm is standard and we refer to the Appendix of , which presents this reformulation in terms of system responses for Gaussian process noise. The argument applies unchanged to any distribution satisfying our assumptions.

Therefore, it remains to consider the inequality constraints. Because the constraints must be satisfied robustly, it is equivalent to consider

Then considering elements in the second term with each $j$ indexing the rows of $F_{x}$,

Thus the inequality constraint on the function $G_{x}(\Phi_{x};k)$ is an equivalent condition. A similar computation holds for the input constraint. ∎

2 Robust Control

We are further motivated to reformulate the optimal control problem in terms of system responses so that we can transparently consider uncertainties in the dynamics. We are interested in controller synthesis under model errors, where only nominal estimates of the system are known. Suppose that the system responses $\widehat{\mathbf{\Phi}}_{x}$, $\widehat{\mathbf{\Phi}}_{u}$ are designed on the estimated system. Then

The model mismatch impacts the closed-loop behavior of the true system in feedback with the controller $\widehat{\mathbf{K}}=\widehat{\mathbf{\Phi}}_{u}(\widehat{\mathbf{\Phi}}_{x})^{-1}$ in a transparent way. Supposing that $\|\widehat{\mathbf{\Delta}}\|_{\mathcal{H}_{\infty}}<1$, it achieves the system response and bounded cost:

This follows from the robust stability result in Theorem 2 of Matni et al. and the sub-multiplicativity of the $\mathcal{H}_{2}$ and $\mathcal{H}_{\infty}$ norms. Note that $\|\widehat{\mathbf{\Delta}}\|<1$ is a sufficient condition for the existence of the inverse $(I+\widehat{\mathbf{\Delta}})^{-1}$ for any induced norm $\|.\|$ by the small gain theorem.

This expression provides an upper bound on the cost achieved for a controller designed system estimates which depends only on the system estimates and the size of the error system $\widehat{\mathbf{\Delta}}$. Motivated by this bound, consider the following robust optimization problem:

where $0\leq\gamma,\tau\leq 1$ are fixed parameters and for each $j$ and $k$,

and similarly for $G_{u}^{\tau}(\mathbf{\Phi}_{u};k)_{j}$.

Any controller designed from a feasible solution to the robust control problem (2.3) for any $0\leq\gamma,\tau<1$ will stabilize the true system. Furthermore, the state and input constraints will be satisfied.

First, note that by the system norm constraints,

Then by (2.2), the true system trajectory will be given by the stable system responses

Therefore, the state constraints are satisfied as long as

Consequently, a sufficient condition for satisfying state constraints is to have for $j$ indexing rows of $F_{x}$ and elements of $b_{x}$,

Therefore, the constraints on $\mathbf{\Phi}_{x}$ imply that the state constraints are satisfied. Similar logic shows that the constraints on $\mathbf{\Phi}_{u}$ imply that the input constraints are satisfied. ∎

3 Finite Dimensional Reduction

To make controller synthesis tractable, we can solve a finite approximation to optimization problem (2.3) wherein we only optimize over the first $L$ impulse response elements of $\mathbf{\Phi}_{x}$ and $\mathbf{\Phi}_{u}$, treating them as finite impulse response (FIR) filters. We show that in this setting, the optimization variables and constraints admit finite-dimensional representations. We first reformulate the constraints. Starting with the affine constraint, we have for $k=1,...,L-1$

where we will also optimize over $V$, a term which captures the tail of the system responses that we ignore in the synthesis.

where the tail variable $V$ enters transparently. For $k=1,\dots,L-1$, the inequality constraints on $G^{\tau}_{x}(\Phi_{x};k)$ and $G^{\tau}_{u}(\Phi_{u};k)$ remain. For any $k\geq L$, the expression reduces to, for each $j$,

Therefore, the synthesis problem becomes, for any fixed $0\leq\gamma,\tau<1$,

This is a finite dimensional SDP. The controller given by $\mathbf{K}=\mathbf{\Phi}_{u}\mathbf{\Phi}_{x}^{-1}$ can be written in an equivalent state-space realization $(A_{K},B_{K},C_{K},D_{K})$ via Theorem 2 of Anderson et al. .

Suboptimality Guarantees

How much is control performance degraded by uncertainties about the dynamics? In this section, we derive a sub-optimality bound which answers this question for the constrained LQR problem. First, consider the addition of an outer minimization over $\gamma$ and $\tau$: The objective (2.3) is unimodal in $\gamma,\tau$ individually, and therefore this outer minimization can be achieved by searching over the box $[0,1)\times[0,1)$. For less computational complexity, the minimization need only be over a single outer variable: $\max(\gamma,\tau)$. In this case, the sub-optimality bound will retain the same flavor, but the norm distinctions between cost and constraints will be less clear.

Denote the solution to the true optimal control problem as $(\mathbf{\Phi}_{x}^{\star},\mathbf{\Phi}_{u}^{\star})$, then define $\mathbf{K}_{\star}=\mathbf{\Phi}^{\star}_{u}{\mathbf{\Phi}^{\star}_{x}}^{-1}$ and $J_{\star}=J(A_{\star},B_{\star},\mathbf{K}_{\star})$. Additionally, define constants related to the optimal system norm and the dynamics uncertainties:

Before stating the suboptimality result, we define a robust version of the optimal constrained controller. Define the doubly robust constraint sets

and similarly for $\bar{G}_{u}^{\zeta}(\mathbf{\Phi}_{u};k)_{j}$. Note that these constraint sets resemble the robust constraint sets with $\tau=2\zeta_{\infty}$ and an enlarged noise process with $\sigma_{w}\leftarrow\frac{\sigma_{w}}{1-\zeta_{\infty}}$. Then the optimal robustly constrained controller is defined as

with $\mathbf{K}_{c}=\mathbf{\Phi}_{u}(\mathbf{\Phi}_{x}^{c})^{-1}$. Note that this optimization problem designs a controller which has similar closed-loop behavior to the true optimal controller (i.e. system norms of similar size), but satisfies more stringent state and input constraints. The relative robustness cost gap is defined as

Now we are ready to state a data independent bound on the sub-optimality of robust controllers synthesized on estimated dynamics.

Suppose that the robust optimal constrained controller problem is feasible. As long as $\zeta_{2}\leq\frac{1}{4\sqrt{2}}$ and $\zeta_{\infty}\leq\frac{1}{2}$, we have that the cost achieved by $\widehat{\mathbf{K}}=\widehat{\mathbf{\Phi}}_{u}\widehat{\mathbf{\Phi}}_{x}^{-1}$ synthesized from the minimizers of (3.1) satisfies

This result is stated in terms of quantities related to the unknown true system, with the goal of highlighting properties of systems that make them harder or easier to robustly control. We see that the bound grows with the $\mathcal{H}_{\infty}$ norm of the optimal controller and closed-loop response. It also grows with the robustness cost gap $M_{\zeta}$.

Remark that $M_{\zeta}$ is be difficult to characterize analytically; in general, it requires checking the boundaries of the robust polytopic constraints. Once errors $\varepsilon_{A}$ and $\varepsilon_{B}$ are small enough that the optimal system response $(\mathbf{\Phi}_{x}^{\star},\mathbf{\Phi}_{u}^{\star})$ satisfies the doubly robust constraints, we will have $M_{\zeta}=0$. If the optimal controller saturates its constraints, then $M_{\zeta}$ will be nonzero for any nonzero estimation errors. In Section 5 (Figure 2), we numerically characterize this optimality gap for a double integrator example.

Using (2.2) along with the norm bounds (2.4) and the constraints in optimization problem (3.1),

Next, we will connect the optimal system response to the estimated system by constructing a feasible solution to the robust optimization problem. We will use the following lemma

Under the conditions of Theorem 3.1, we have that the following is a feasible solution to (3.1)

where we define ${\mathbf{\Delta}}:=-\begin{bmatrix}\Delta_{A}&\Delta_{B}\end{bmatrix}\begin{bmatrix}\mathbf{\Phi}_{x}^{c}\\ \mathbf{\Phi}_{u}^{c}\end{bmatrix}$.

The proof of Lemma 3.2 follows by checking that the proposed solution satisfies all the constraints and is presented in Appendix A. Applying Lemma 3.2,

The second inequality follows from an application of (2.2) with the roles of the nominal and true systems switched. The final follows from bounding $\|\mathbf{\Delta}\|_{2}$ by $\sqrt{2}\zeta$ and noticing that $\frac{x}{1-x}\leq 2x$ for $0\leq x\leq\frac{1}{2}$, where we set $x=2\sqrt{2}\zeta_{2}$. Finally, we note that

Here, we briefly remark that a similar sub-optimality bound can be derived for the finite problem in (2.8). In short, controllers synthesized by minimizing over $\gamma$ and $\tau$ will satisfy a sub-optimality bound of the form in Theorem 3.1 with an additional factor due to the FIR truncation. The formal statement and proof of this result are deferred to Appendix A, but we highlight here that the cost penalty incurred due to FIR approximation decays exponentially in the horizon $L$ over which the approximation is taken.

Learning with Control

Finally, we connect the previous results on robust control with system estimation. We adopt control actions that both keep the system safe and provide excitation,

In what follows, we will prove a statistical rate on the least-squares estimate $(\widehat{A},\widehat{B})$ in terms of the system response and the trajectory length.

Fix a failure probability $\delta\in(0,1)$. Suppose the stochastic disturbance $\{w_{k}\}$ and the input disturbance $\{\eta_{k}\}$ satisfy the assumptions above. Assume for simplicity that $\sigma_{\eta}\leq\sigma_{w}$, and that the stabilizing controller $\mathbf{K}$ achieves a SLS response $\mathbf{\Phi}_{x}\in\frac{1}{z}\mathcal{RH}_{\infty}(C_{x},\rho),\mathbf{\Phi}_{u}\in\frac{1}{z}\mathcal{RH}_{\infty}(C_{u},\rho)$. Let $C_{K}^{2}:=nC_{x}^{2}+dC_{u}^{2}$. Then as long as the trajectory length $T$ satisfies the condition:

we have the following bound on the least-squares estimation errors that holds with probability at least $1-\delta$,

The proof of this result is presented in Appendix C. We remark on the interpretation of statistical learning bounds. A priori guarantees, like the one presented here, depend on quantities related to the underlying true system. As such, they are not directly useful when the system is unknown, Statistical bounds in terms of data-dependent quantities can also be worked out; however, modern methods like bootstrapping generally provide tighter statistical guarantees . but rather they indicate qualities of systems that make them easier or harder to estimate. For example, we see that this bound on estimation errors decreases with the size of the excitation, and increases with the size of the process noise. The bound also increases with $C_{u}$, a constant which bounds the gain from disturbance to control inputs.

Finally, we connect the sub-optimality result to the statistical learning bound for an end-to-end sample complexity bound on the constrained LQR problem. Define $M_{T}$ to be the value of $M_{\zeta}$ when the definition determined by (3.2) has values set as

Assume initial feasibility of the learning problem. Then for a trajectory of length

the cost achieved by $\widehat{\mathbf{K}}=\widehat{\mathbf{\Phi}}_{u}(\widehat{\mathbf{\Phi}}_{x})^{-1}$ synthesized from (2.3) on the least-squares estimates $\widehat{A},\widehat{B}$ satisfies with probability at least $1-\delta$,

(Sketch) This result follows by combining the statistical guarantee in Theorem 4.1 with the sub-optimality bound in Theorem 3.1. Note that we use the naïve bound $\varepsilon_{A,\infty}\leq\sqrt{n}\varepsilon_{A,2}$ and similarly $\varepsilon_{B,\infty}\leq\sqrt{d}\varepsilon_{B,2}$; this results in an extra factor of $(n+d)$ appearing in (4.4) and in the definition of $M_{T}$. ∎

Our final result depends both on the true system and the initial system estimates by way of the learning controller, which affects $T_{0}$ and constants $C_{x}$, $C_{u}$, and $\rho$. The system constraints enter through their effect on $M_{T}$.

Numerical Experiments

We demonstrate the utility of this framework on a double integrator example. In this case, the true dynamics are given by

with the constraints as states bounded between $-8$ and $8$, and inputs bounded in between $-4$ and $4$. We have $\sigma_{w}=0.1$. Our initial estimate comes from a randomly generated initial perturbation of the true system with $\varepsilon_{A,\infty}=\varepsilon_{B,\infty}=0.1$. Safe controllers are generated with finite truncation length $L=15$, and for larger initial conditions, the system is warm-started with a finite-time robust controller with horizon $20$ to reduce the initial condition.

Figure 1 displays safe trajectories and input sequences for several example initial conditions. In 1a, the plotted trajectories are used for learning: the controller both regulates and excites the system ($\sigma_{\eta}=0.5$), and is robust to initial uncertainties. Figure 1b demonstrates an ability to operate closer to the constraints when there is less uncertainty: in this case, there is no added excitation ($\sigma_{\eta}=0$) and the system estimates are better specified ($\varepsilon_{\infty}=0.001$), so larger initial conditions are feasible.

Figure 2a displays the decreasing estimation errors over time, demonstrating learning. Shaded areas represent quartiles over $400$ trials. Figure 2b displays the trade-off between safety and exploration by showing the largest value of $\sigma_{\eta}$ for which the robust synthesis is feasible, given a size for the state constraint set $r_{x}$. Here, we leave $x_{0}=0$, and examine a variety of errors in the dynamics estimates. As the uncertainties in the dynamics decrease, higher levels of both safety and exploration are achievable. Finally, Figure 2c shows the value of the relative robust sub-optimality gap $M_{\zeta}$ for the given example. We see a sharp transition from infeasibility for $\varepsilon\geq 0.05$ to near-optimality for $\varepsilon\leq 0.03$. This indicates that the gap may be most significant as a feasibility condition for our sub-optimality guarantees to hold.

Discussion

In this paper, we propose a method for learning unknown linear systems while ensuring that they satisfy state and input constraints. By synthesizing a controller that both excites and regulates the system, we address the trade-off between safety and exploration directly. We further derive an end-to-end finite sample bound on the performance of constrained LQR controllers synthesized from collected data.

There are several directions for possible extensions of this work. To mitigate the conservativeness of the robust controller, tighter bounds on the uncertainty in the system response $\widehat{\mathbf{\Delta}}$ could be derived for structured settings, where more than just the norm of the error is known. To connect this work to experiment design literature, the objective in the synthesis problem (2.3) could be replaced with an exploration inspired cost function for the learning stage.

Alternatively, the constrained LQR problem could be cast in the setting of online learning, where one seeks to minimize cost at all times, including during learning. This would require an analysis of recursive feasibility, to understand the transition that occurs when controllers are updated based on refined system estimates. It would also likely require a finer analysis on the performance loss characterized by $M_{\zeta}$. Finally, we remark that the exploration vs. safety trade-off is most compelling for nonlinear systems, and a linear-time-varying extension to this work may be applicable to those problems.

ACKNOWLEDGMENT

We thank Francesco Borrelli and the members of the MPC Lab at UC Berkeley for their helpful comments and feedback. SD is supported by an NSF Graduate Research Fellowship under Grant No. DGE 1752814. ST is supported by a Google PhD fellowship. BR is generously supported in part by ONR awards N00014-17-1-2191, N00014-17-1-2401, and N00014-18-1-2833, the DARPA Assured Autonomy (FA8750-18-C-0101) and Lagrange (W911NF-16-1-0552) programs, and an Amazon AWS AI Research Award.

References

Appendix A Extended Sub-optimality Results and Proofs

This section contains proofs necessary for the sub-optimality results. It further develops a sub-optimality bound for the case of FIR truncation. We begin by considering the frequency response elements of composed transfer functions. First, define, for $\mathbf{D}=\sum_{k=1}^{\infty}D(k)z^{-k}$,

where we use the notation $D(1:k)$ for the vertical concatenation of $D(1)$ through $D(k)$. Further, we have

For the first statement, notice that we can write

due to the sub-multiplicative property of the $\mathcal{H}_{\infty}$ norm and the norm constraint in the definition of $(\mathbf{\Phi}^{c}_{x},\mathbf{\Phi}^{c}_{u})$. By similar logic $\|\mathbf{\Delta}\|_{\mathcal{L}_{1}}\leq\zeta_{\infty}$.

Considering the $\mathcal{H}_{\infty}$ norm constraint,

where the inequality follows due to the fact that $\sqrt{2}\|\mathbf{\Delta}\|_{\mathcal{H}_{\infty}}\leq 1$. Then consider the $\mathcal{L}_{1}$ norm constraint,

where the decomposition of the inverse is valid by assumption on the size of $\zeta_{\infty}$.

Then it remains to show that the robust state and input constraints are satisfied. For compactness we will write $c_{0}=\max(1,\frac{1}{\sigma_{w}}\|x_{0}\|_{\infty})$. Recall that they are given by

Assume that $\zeta_{\infty}<1$ and let $D$ represent the frequency response of $\mathbf{\Delta}(1-\mathbf{\Delta})^{-1}$. Then for any vector $v$,

Now we are ready to consider the state constraint indexed by $j$ and $k$,

Then defining $E_{1}$ to contain an identity in the first block and zeros elsewhere,

The first inequality is Hölder’s inequality and the second by Lemma A.2. Next, the second term:

where the inequality holds by Lemma A.2. Finally, the last term,

Then considering constants around the final term,

A.2 Finite Dimensional Sub-optimality

We can recover sub-optimality guarantees in the case that we optimize over only a finite set of system response variables. Define the truncated responses $\mathbf{\Phi}_{x}^{L}=\sum_{k=1}^{L}\Phi_{x}(t)z^{-k}$ and similarly for $\mathbf{\Phi}_{u}^{L}$, and notice that

This reformulation allows for the optimization over the FIR filters $\mathbf{\Phi}_{x}^{L}$ and $\mathbf{\Phi}_{u}^{L}$, plus an additional variable that represents the tail of the true response. Applying this observation to the robust synthesis problem (2.3) yields the following finite dimensional problem:

We now show that so long as the horizon $L$ is suitably large, all of the properties that hold for the solution of infinite horizon problem (2.3) carry over to the solution of the finite dimensional approximation (A.2).

Any controller designed from a feasible solution to the finite robust control problem (A.2) for any $0\leq\gamma,\tau<1$ stabilizes the true system and ensures that state and input constraints will be satisfied.

Consider the affine constraint on $\mathbf{\Phi}_{x}^{L}$ and $\mathbf{\Phi}_{u}^{L}$. We can equivalently write, using the observation in (A.1),

where we define $\widehat{\mathbf{\Delta}}=\Delta_{A}\mathbf{\Phi}_{x}^{L}+\Delta_{B}\mathbf{\Phi}_{u}^{L}$. The noting that

by (2.2), the system is stabilized and the true system trajectory is given by

The rest of the proof follows exactly as in the proof of Theorem 2.2 ∎

To bound the sub-optimality of this robust synthesis, we need to connect the optimal controller to the robust problem. For this feasibility result, it is necessary to understand the system response induced by putting the optimal robustly constrained controller $\mathbf{K}_{c}=\mathbf{\Phi}_{u}^{c}(\mathbf{\Phi}_{x}^{c})^{-1}$, as defined in (3.2), in feedback with the estimated dynamics $(\widehat{A},\widehat{B})$. We denote this system responses as $\mathbf{\Phi}_{x}^{c}(I-\mathbf{\Delta})^{-1}$. As before, ${\mathbf{\Delta}}=-\Delta_{A}\mathbf{\Phi}_{x}^{c}-\Delta_{B}\mathbf{\Phi}_{u}^{c}$.

We thus define constants related to the decay rate of the system responses. Let $C_{\star}$ and $\rho_{\star}$ be any constants such that $\|\Phi_{x}^{c}(k)\|_{p}\leq C_{\star}\rho_{\star}^{k}$ for $p\in\{2,\infty\}$. Note that these constants must exist since the optimal closed loop will be exponentially stable. Let $C_{\Delta}$ and $\rho_{\Delta}$ similarly be any constants that bound the norm of the frequency response elements of $(I-\mathbf{\Delta})^{-1}$. We note that these constants can be bounded by multiples of $C_{\star}$ and $\rho_{\star}$, as worked out in Appendix G of Dean et al. .

Suppose that for $p\in\{2,\infty\}$, $\|\Phi_{x}^{c}(k)\|_{p}\leq C_{\star}\rho_{\star}^{k}$ and $\|(I-\mathbf{\Delta})^{-1}[k]\|_{p}\leq C_{\Delta}\rho_{\Delta}^{k}$. Define $C=\frac{C_{\star}C_{\Delta}}{\log(\frac{\max(\rho_{\star},\rho_{\Delta})+1}{2\max(\rho_{\star},\rho_{\Delta})})}$ and $\rho=\frac{\max(\rho_{\star},\rho_{\Delta})+1}{2}$. Then for $p\in\{2,\infty\}$ and all $t\geq 0$,

We defer the proof of this lemma to the end of the section. Next, we redefine the optimal robustly constrained responses $(\mathbf{\Phi}^{c}_{x},\mathbf{\Phi}^{c}_{u})$ in (3.2) to satisfy the modified doubly robust constraint sets

Here, we have changed a factor of $2$ to a factor of $3$ in the last term to account for the finite approximation. We will define $M_{\zeta}$ as in (3.3) using the new $(\mathbf{\Phi}^{c}_{x},\mathbf{\Phi}^{c}_{u})$. We are now ready to state the sub-optimality result.

Suppose that the truncation length is such that

As long as $\zeta_{\infty}<\frac{1}{3}$ and $\zeta_{2}<\frac{1}{3\sqrt{2}}$, we have that the cost achieved by $\widehat{\mathbf{K}}(L)=\widehat{\mathbf{\Phi}}_{u}\widehat{\mathbf{\Phi}}_{x}^{-1}$ synthesized from the minimizers of $\min_{\gamma,\tau}~\widehat{J}_{L}(\gamma,\tau)$ satisfies

To prove this result, we first construct a feasible solution to the truncated synthesis problem (A.2).

Under the conditions of Theorem A.5, the following is a feasible solution to (A.2):

First, we consider the affine constraint,

Next, we consider the $\mathcal{H}_{\infty}$ norm constraint

This affects the constant factors around the final term of the sum

We are now ready to prove the main sub-optimality result.

Recall that we denote the minimizers of $\min_{\gamma,\tau}~\eqref{eq:sls_lqr_robust_FIR}$ as $(\widehat{\mathbf{\Phi}}_{x},\widehat{\mathbf{\Phi}}_{u},\widehat{V},\widehat{\gamma},\widehat{\tau})$. Let

By the constraints of the optimization problem in (A.2).

We now apply observation A.1 and (2.2) with $\widehat{\mathbf{\Delta}}_{L}$ to characterize the response achieved by the FIR approximate controller $\widehat{\mathbf{K}}(L)$ on the true system $(A_{\star},B_{\star})$, giving the following:

The inequality follows because $\|\widehat{\mathbf{\Delta}}\|_{\mathcal{H}_{\infty}}\leq\widehat{\gamma}<1$.

which follows for $\zeta_{2}<\frac{1}{6\sqrt{2}}$. Then finally,

Using Lemma A.1 with $D(t)$ representing the frequency response elements of $(I-\mathbf{\Delta})^{-1}$, we have that

Then noting that for any $x\in(0,1)$, $\alpha>0$, and $k\geq 1$,

which is true because $\log\left(\frac{k}{\alpha}\right)\leq\frac{k}{\alpha}$, we have for $p=2,\infty$

The final inequality follows from choosing $\alpha=\log\left(\frac{\max(\rho_{\star},\rho_{\Delta})+1}{2\max(\rho_{\star},\rho_{\Delta})}\right)^{-1}$. ∎

Appendix B Additive Disturbance Alternative

In this section we discuss an alternative to the proposed robust control problem in (2.3) in which the constraints are tightened using a traditional additive disturbance approximation. We will contrast this additive reduction with the system-response reduction presented in Section 2.2. Define the additive robust synthesis problem as

where $0\leq\gamma<1$ is a fixed parameter and

Any controller designed from a feasible solution to the robust control problem (B.1) for any $0\leq\gamma<1$ will stabilize the true system. Furthermore, the state and input constraints will be satisfied.

First, note that by the system norm constraint,

Now note that if $x_{k}\in\mathcal{X}$, we have

The next result establishes conditions under which this additive disturbance robust control is better than the system-response robust control.

Let $\widehat{\tau}$ be an optimizer of (3.1). The additive disturbance reduction is less conservative than the system-response based reduction if and only if

From this statement, we can see that the system-response reduction suffers for large initial conditions, while the additive reduction suffers with the size of the constraint sets. For this reason, that additive disturbance reduction would not properly characterize the tradeoff between safety and exploration as plotted in Figure 2b. However, we note that the condition in Proposition B.2 could be used as a switch in a control synthesis problem to decide which reduction to use.

Recall that $\mathbf{w}=x_{0}z+\sum_{k=0}^{\infty}w_{k}z^{-k}$. The system-response reduction writes

This expression can be viewed as expanding the disturbance by the uncertainty as

In the robust constraints (2.3), this additional uncertainty is bounded as

Then in the robust constraints (B.1), this additional uncertainty is bounded as

Then the additive bound is worse than the system-response bound as stated. ∎

Finally, we note that the sub-optimality result could be extended to controllers synthesized from minimizing (B.1) over $\gamma$, and that the main difference would arise from the definition of the robust cost sub-optimality gap $M_{\zeta}$.

Appendix C Learning Results

First, we prove a simple small-ball result for random variables with finite fourth moments.

Now define the function $f(a)$ for $a\geq 0$ as

Clearly $f(0)=\mu^{2}/(3\beta)$ and $f(\infty)=1$. Since by Jensen’s inequality we know that $\mu^{2}\leq\beta$, this means $f(0)<f(\infty)$. On the other hand,

Assume that $\mu\neq 0$ (otherwise the claim is trivially true). The only critical points of the function $f$ on non-negative reals is at $a=0$ and $a=\sqrt{\frac{4\mu^{2}-3\beta}{3\mu}}$ if $4\mu^{2}\geq 3\beta$. If $4\mu^{2}<3\beta$, then $a=0$ is the only critical point of $f$, so $f(a)\geq f(0)=\mu^{2}/(3\beta)\geq 1/(3C)$. On the other hand, if $4\mu^{2}\geq 3\beta$ holds, Some algebra yields that

The inequality above holds since $3\beta\in[3\mu^{2},4\mu^{2}]$. Hence,

This gives us the main new technical ingredient needed to prove Theorem 4.1.

With Proposition C.2 in place, the proof of Theorem 4.1 is identical to that of Proposition C.1 in Dean et al. , except in the final step of establishing the block martingale condition: instead of using the small-ball calculation for Gaussian distributions we replace it with the estimate provided by Proposition C.2.