---
abstract: 'We develop a learning-based control algorithm for unknown dynamical systems under very severe data limitations. Specifically, the algorithm has access to streaming data only from a single and ongoing trial. Despite the scarcity of data, we show—through a series of examples—that the algorithm can provide performance comparable to reinforcement learning algorithms trained over millions of environment interactions. It accomplishes such performance by effectively leveraging various forms of side information on the dynamics to reduce the sample complexity. Such side information typically comes from elementary laws of physics and qualitative properties of the system. More precisely, the algorithm approximately solves an optimal control problem encoding the system's desired behavior. To this end, it constructs and refines a differential inclusion that contains the unknown vector field of the dynamics. The differential inclusion, used in an interval Taylor-based method, enables to over-approximate the set of states the system may reach. Theoretically, we establish a bound on the suboptimality of the approximate solution with respect to the case of known dynamics. We show that the longer the trial or the more side information is available, the tighter the bound. Empirically, experiments in a high-fidelity F-16 aircraft simulator and MuJoCo's environments such as the Reacher, Swimmer, and Cheetah illustrate the algorithm's effectiveness.'
author:
- |
    Franck Djeumou\
    Department of Electrical and Computer Engineering\
    University of Texas at Austin United States\
    `andrewsanford@example.net`\
    Ufuk Topcu\
    Department of Aerospace Engineering and Engineering Mechanics\
    University of Texas at Austin\
    `andrewsanford@example.net`\
bibliography:
- 'ref.bib'
title: |
     Learning to Reach, Swim, Walk and Fly in One Trial:\
    <span>Data-Driven Control with Scarce Data and Side Information</span>
---

Introduction
============

Learning how to achieve a complex task has found numerous applications ranging from robotics [@lillicrap2015continuous; @schulman2015trust; @deisenroth2013survey] to fluid dynamics [@kutz2017deep]. However, learning algorithms generally suffer from high sample complexity, often requiring millions of samples to achieve the desired performance [@nagabandi2018neural; @schulman2015trust]. Such data requirements limit the practicability of learning algorithms in real-world scenarios where an excessive number of trials cannot be performed on a physical system. A rather extreme example of such a scenario is an aircraft trying to retain a certain degree of control after abrupt changes in its dynamics, e.g., due to the loss of an engine. In such a scenario, there is a need to learn the dynamics after the abrupt changes using data from only the current trajectory.=-1

We develop a learning-based control algorithm that utilizes data from a single trial and leverages side information on the unknown dynamics to reduce the sample complexity. The data include finitely many samples of the states, the states' derivatives, and the control signals applied. Under such a severe limitation on the amount of available data, learning can be performed efficiently only by incorporating already known invariant properties of the dynamical system. We refer to such extra knowledge as *side information*. The side information, typically derived from elementary laws of physics, may be a priori knowledge of the underlying dynamics, monotonicity or bounds on the vector field, algebraic constraints on the states, or knowledge of parts of the vector field.

The developed algorithm, using the data and side information available to it, computes an over-approximation of the set of states the system may reach. Then, it incorporates such an over-approximation into a constrained short-horizon optimal control problem, which is solved on the fly.=-1

![The developed learning-based algorithm can achieve near-optimal control of simulated robots and an F-16 aircraft using streaming data obtained from the systems' ongoing trajectory and some side information derived from elementary laws of physics. From left to right, we have screenshots of the Reacher, Swimmer, Cheetah, and F-16 aircraft simulator environments^\[vid\]^.](figs/environments.png){width="\textwidth" height="0.75in"}

\[fig:environments\]

Specifically, the developed algorithm leverages a data-driven differential inclusion to compute over-approximations of the reachable sets of the system. It first constructs a differential inclusion that contains the unknown vector field. Next, it builds on contractor programming @CHABERT20091079 to refine the differential inclusion as more data become available. Then, it computes over-approximations of the reachable sets of all dynamics described by the differential inclusion through an interval Taylor-based method @berz1998verified [@nedialkov1999validated] that can enforce constraints from the side information.

The obtained over-approximations enable to formulate the data-driven optimal control problem as a nonconvex, uncertain optimization problem. Specifically, we encode the control task as a sequential optimization of a cost function over a short time horizon. Even if the cost is convex, the optimal control problem is typically nonconvex. Furthermore, the predictions of the states' values at future times cannot be computed due to the unknown dynamics. The developed algorithm leverages the obtained over-approximations to optimize the nonconvex problem under the uncertain states' predictions.

The algorithm computes approximate solutions to the nonconvex optimization problem through convex relaxations. We develop a sequential convex optimization scheme @mao2019successive that uses the obtained over-approximation and iteratively linearizes its nonconvex constraint around the previous iteration solution. Thus, each iteration solves a *linear* optimization problem, and we leverage trust regions to account for the potential errors due to the linearization.

Theoretically, we establish a bound on the suboptimality of the approximate solution with respect to the optimal solution in the case where the dynamics were known. The bound is proportional to the width of the obtained over-approximations. We show that the longer the trial or the more the side information available, the tighter the over-approximations. Thus, the algorithm achieves near-optimal control as more data streams or more side information is available.

Empirically, through a series of simulation examples and *unfair* comparisons to the developed algorithm, we show that the algorithm can provide performance comparable to reinforcement learning (RL) algorithms trained over millions of environment interactions. *We emphasize that if we had made fair comparisons, i.e., the baselines RL algorithms were also trained using streaming data from only the ongoing and single episode, the developed algorithm would have achieved significantly higher performance than any of these baselines since they cannot learn with such constraints on the amount of data*. Specifically, in several control tasks from MuJoCo @todorov2012mujoco [@tassa2018deepmind], we provide promising and comparative results to state-of-the-art RL algorithms <span>`D4PG`</span> @barthmaron2018distributed and <span>`SAC`</span> [@haarnoja2018soft]. Further, in a ground collision avoidance scenario of an F-16 aircraft [@heidlauf2018verification], we show that the algorithm outperforms the highly-tuned linear-quadratic regulator controller of the simulator. We provide more details about each experiment in the supplementary material.=-1

**Related work.** In @franckACC, the authors describe a data-driven algorithm similar to our algorithm. However, the algorithm in @franckACC works only for control-affine dynamics. Further, most of the considered side information is not tailored for robotic systems, and the authors investigate only one-step optimal control problems. In contrast, the algorithm in this paper is applicable for a more general class of dynamics with polynomial dependency in control. We also consider side information tailored for robotic systems such as algebraic constraints on unknown terms of the dynamics, e.g, Coulomb law of friction. Besides, we investigate short-horizon, rather than one-step optimal control problems.

Model-free @mnih2015human [@oh2016control; @lillicrap2015continuous; @mnih2016asynchronous; @schulman2015high] and model-based @nagabandi2018neural [@deisenroth2011pilco; @gu2016continuous; @boedecker2014approximate; @levine2014learning; @ko2009gp] RL algorithms have been widely used for data-driven control of unknown systems. Model-free algorithms can achieve high performance at the expense of high sample complexity @schulman2015high. These approaches do not exploit side information from laws of physics to reduce their sample complexities. Besides, it has been shown that neural networks often struggle to learn @greydanus2019hamiltonian invariant properties of physical systems and other qualitative properties. Model-based algorithms are generally regarded as more data-efficient @deisenroth2013survey than model-free ones at the expense of conservativeness, low-dimensional task limitations, and significant bias due to modeling errors @nagabandi2018neural. In contrast, the algorithm developed in this paper can work with data from only the system's current trajectory, and increases the data efficiency through side information. Several approaches for data-driven control combine model predictive control with system identification @korda2018linear [@kaiser2018sparse; @proctor2016dynamic] or data-driven reachable set estimation @devonport2020data [@haesaert2017data; @chakrabarty2018data]. These approaches achieve system identification through sparse regression over a library of nonlinear functions @kaiser2018sparse, spectral properties of the collected data @proctor2016dynamic, Koopman theory @korda2018linear, or Gaussian processes @krause2011contextual. The approaches in @devonport2020data [@haesaert2017data; @chakrabarty2018data] achieve data-driven estimation of the reachable sets of partially unknown dynamics using either supervised learning @chakrabarty2018data or Gaussian process-based algorithms @haesaert2017data [@devonport2020data]. They provide only probabilistic guarantees of the correctness of the computed reachable sets while our algorithm computes correct over-approximations. Furthermore, in their current forms, none of the above approaches can incorporate side information. The authors in @franckACC empirically demonstrate that a learning algorithm with side information outperforms these approaches in terms of computation time and suboptimality of the control. Thus, our approach is guaranteed to inherit such properties.

Background {#sec:prelem}
==========

#### Notation.

We denote an interval by $[a , b] = \{ x \in \mathbb{R} |  a \leq x \leq b \}$ for some $a, b\in \mathbb{R}$ such that $a \leq b$, the set $\{i,\hdots,j\}$ by $\mathbb{N}_{[i,j]}$ for $i,j \in \mathbb{N}$ with $i\leq j$, the $k^\mathrm{th}$ component of a vector $x$ and the $(k,j)$ component of a matrix $X$ by ${x}_k$ and ${X}_{k,j}$, respectively, the weighted norm of a vector $x \in \mathbb{R}^n$ by $||x||_w = \sqrt{\sum_{i=1}^n (w_i x_i)^2}$ for some $w \in \mathbb{R}^n_+$, and the Lipschitz constant of $f : \mathcal{X} \to \mathbb{R}$ by $L^w_f = \sup \{ L \in \mathbb{R} \: \vert \: |f(x) - f(y)| \leq L \|x-y\|_w, x,y \in \mathcal{X}, x \neq y\}$ for $\mathcal{X} \subseteq \mathbb{R}^n$. **Interval Analysis.** We denote the set of intervals on $\mathbb{R}$ by $\mathbb{IR} = \{ \mathcal{A} = [\underline{\mathcal{A}},\overline{\mathcal{A}}]  \: | \: \underline{\mathcal{A}},\overline{\mathcal{A}} \in \mathbb{R}, \underline{\mathcal{A}} \leq \overline{\mathcal{A}}\}$, the set of $n$-dimensional interval vectors by $\mathbb{IR}^n$, and the set of $n\times m$-dimensional interval matrices by $\mathbb{IR}^{n \times m}$. We carry forward the definitions @moore1966interval of arithmetic operations, set inclusion, and intersections of intervals to interval vectors and matrices by applying them componentwise. We use the term interval to specify an interval vector or interval matrix when it is clear from the context. Given $f : \mathcal{X} \mapsto \mathcal{Y}$ with $\mathcal{X} \subseteq \mathbb{R}^n$ and $\mathcal{Y} \subseteq \mathbb{R}^{m}$, we define an *interval extension of $f$* as $\boldsymbol{f} : \mathbb{IR}^n \mapsto \mathbb{IR}^m$ satisfying $\boldsymbol{f}(\mathcal{A}) \supseteq \mathscr{R}(f, \mathcal{A}) = \{ f(x) \: | \: x \in \mathcal{A} \}, \: \forall \mathcal{A} \subseteq \mathcal{X}$. Thus, given an interval $ \mathcal{A}$, $\boldsymbol{f}(\mathcal{A})$ is an interval that *over-approximates* the range of values taken by $f$ over $\mathcal{A}$.

**Interval-Based Contractor Programming.** Interval-based contractor programming is a mathematical framework to solve constraints involving interval variables, e.g., nonlinear equations or inequalities. Specifically, given an initial over-estimation of the constraint's solutions, a contractor filters such variable domains, i.e., reduces the interval of each variable, without loss of solutions of the constraints. Consider the constraint $h(\cdot) \leq 0$. Assume that $\mathcal{A}=[\mathcal{A}_1,\hdots,\mathcal{A}_n] \in \mathbb{IR}^n$ is a set containing all the solutions of the constraint. Then, the contractor operator computes $C^h_{\mathcal{A}} = [C^h_{\mathcal{A}_1},\hdots, C^h_{\mathcal{A}_n}] \in \mathbb{IR}^n$ such that $C^h_{\mathcal{A}_i} \subseteq \mathcal{A}_i, \forall i \in \mathbb{N}_{[1,n]}$ and $h(x) > 0$ for all $ x \in \mathcal{A} \setminus C^h_{\mathcal{A}}$.

Several polynomial-time algorithms have been developed to compute contractors associated with a given constraint. `HC4-Revise` @benhamou-contractor1999 is a linear-time algorithm that provides optimal contractors when each variable appears only once in the constraint. When a variable has multiple occurrences in the constraint, `BoxNarrow` @van1997numerica provides sharper bounds at the expense of higher computation cost. In the following, we use $C^h_{\mathcal{A}}$ to refer to the contracted interval resulting from these algorithms.

Problem Formulation
===================

This paper considers nonlinear dynamics with polynomial dependency in the control inputs as

$$\begin{aligned}
    \dot{x} = f(x) + \sum\nolimits_{p=1}^d  g_p(x) {\textit{u}}[\alpha^p], \label{eq:polynomial-control}\end{aligned}$$

where $d \in \mathbb{N}$, $\alpha^p \in \mathbb{N}^m$ is known, the state $x: \mathbb{R}_+ \mapsto \mathcal{X}$ is a continuous-time signal evolving in $\mathcal{X} \in \mathbb{IR}^n$, ${\textit{u}}[\alpha^p] = u_1^{\alpha_1^p} \cdots u_m^{\alpha_m^p}$ is a monomial with variables from the control signal $u : \mathbb{R}^+ \mapsto \mathcal{U}$ where $\mathcal{U} \in \mathbb{IR}^m$. The vector-valued functions $f = [f_k] : \mathbb{R}^n \mapsto \mathbb{R}^n$ and $g_p = [g_{p,k}] : \mathbb{R}^n \mapsto \mathbb{R}^{n}$ are considered to be *nonlinear and unknown*. Note that even if the dynamics are not in the class above, Taylor expansion provides a tight approximation of the dynamics that lies in such a class. Henceforth, we can directly apply the results of this paper on the Taylor expansion.

\[<span style="font-variant:small-caps;">Lipschitz systems</span>\] \[ass:lipshitz-bounds\] Given a set $\mathcal{A} \subseteq \mathbb{R}^n$, $f_k$ and $g_{p,k}$ admit local Lipschitz constants $L^w_{f_k},  L^{w}_{g_{p,k}}> 0$ on $\mathcal{A}$, for some $w \in \mathbb{R}^n_+$ and for all $k \in {\mathbb{N}_{[1,n]}}, p \in {\mathbb{N}_{[1,d]}}$.

Assumption \[ass:lipshitz-bounds\] is common in the framework of optimal control. We emphasize that even though we use the weighted norm to define the Lipschitz constants, the results of this paper can be straightforwardly extended to general modulus of continuity assumption on $f$ and $g_p$. The weighted norm has the advantage of providing information on the relative importance of each variable in the function.

Recall that the domain $\mathcal{X} \in \mathbb{IR}^n$ is bounded. Thus, by Assumption \[ass:lipshitz-bounds\], $f_k$ and $g_{p,k}$ admit Lipschitz constants on $\mathcal{X}$. We exploit such a knowledge by considering Side information \[side:Lip\] that provides upper bounds on the Lipschitz constants of $f$ and $g_p$. However, it is worth noting that we can estimate with certain confidence such bounds on the fly using the data from the system's current trajectory.

\[<span style="font-variant:small-caps;">Lipschitz constants bounds</span>\]\[side:Lip\] Let ${\overline{f}}_k \in \mathbb{R}_+$ and ${\overline{g}}_{p,k} \in \mathbb{R}_+$ be known upper bounds on the Lipschitz constants $L^w_{f_k}$ and $L^{w}_{g_{p,k}}$, respectively, for $k \in {\mathbb{N}_{[1,n]}}$ and $p \in {\mathbb{N}_{[1,d]}}$.

In a discrete-time setting, we denote the initial time by $t_1 \geq 0$ and the current time by $t_j > t_1$ for some $j > 1$. Let ${\mathscr{T}}_j = \{(x^i,\dot{x}^i, u^i)\}_{i=1}^{j-1}$ be the finite-length set of observations obtained between $t_1$ and $t_j$. The dataset ${\mathscr{T}}_j$ contains $j-1$ samples of the state $x^i=x(t_i)$, the derivative $\dot{x}_i=\dot{x}(t_i)$ of the state, and the applied input $u^i = u(t_i)$. We seek to control the unknown dynamical system  by finding $u^j,\hdots, u^{j+N} \in \mathcal{U}$ that are solutions of the *$N$-step optimal control problem*

$$\begin{aligned}
    \underset{u^j,\hdots,u^{j+N}\in \mathcal{U}}{\mathrm{minimize}}& \quad \sum\nolimits_{q=j}^{j+N} c(x^q, u^q, x^{q+1} = x(t_{q+1}; x_q, u_q)),\label{eq:n-step-optimal-control}\end{aligned}$$

where $N$ is the planning horizon, $x^j = x(t_j)$ is the known current state of the system, $t_q = t_j + (q-j) \Delta t $, $\Delta t$ is a constant time step, and $x^{q+1} = x(t_{q+1}; x^q, u^q)$ is the state at $t_{q+1}$, i.e., a solution of the differential equation   at $t_{q+1}$ when $x^q$ is the initial state and $u^q$ is the constant control applied between $[t_q,t_{q+1}]$. We encode the desired behavior of the system as the *known cost function* $c:\mathcal{X} \times \mathcal{U} \times \mathcal{X} \mapsto \mathbb{R}$ that assigns preferences over the tuple of the current state, the current control input, and the corresponding state at the next time step. Even if the one-step cost function $c$ is convex, the optimization problem  is generally nonconvex since the state at $t_{q+1}$ is nonconvex due to the nonlinear dynamics. Besides, $x^{q+1}$ cannot be computed due to the unknown dynamics. As a consequence, we can only hope to approximate solutions of such an optimization problem.

\[prob:control\] Given the dataset ${\mathscr{T}}_{j}$, the current state $x^j$, compute an approximate solution to the $N$-step optimal control problem  and characterize the suboptimality of such approximation.

Reachable Set Over-Approximation via Data-Based Differential Inclusions {#sec:overapprox-reach}
=======================================================================

In this section, we first construct a differential inclusion $\dot{x} \in \boldsymbol{f}(x) + \sum_{p=1}^d \boldsymbol{g}_p(x) {\textit{u}}[\alpha^p]$ that contains the unknown vector field. Then, we adapt an interval Taylor-based method to over-approximate the reachable set of dynamics described by the constructed differential inclusion. Finally, we show how additional side information constrains the Taylor expansion to provide tighter over-approximations.

\[<span style="font-variant:small-caps;">Over-approximation of $f$ and $g_p$</span>\]\[lem:overapprox-fg\] Let the set $\mathscr{E}_j = \{ (x^i,C_{\mathcal{F}^i}, C_{\mathcal{G}^i}) \}_{i=0}^{j-1}$ be such that $C_{\mathcal{F}^i} = [C_{\mathcal{F}_k^i}] \in \mathbb{IR}^n$ and $C_{\mathcal{G}^i} = [C_{\mathcal{G}_{p,k}^i}] \in \mathbb{IR}^{d \times n}$ satisfy $f_k(x^i) \in C_{\mathcal{F}_k^i}$ and $g_{p,k}(x^i) \in C_{\mathcal{G}_{p,k}^i}$ for all $p \in {\mathbb{N}_{[1,d]}}$ and $k \in {\mathbb{N}_{[1,n]}}$. Then, the interval-valued functions $\boldsymbol{f} = [\boldsymbol{f}_k] : \mathbb{IR}^n \to \mathbb{IR}^{n}$ and $\boldsymbol{g}_{p} = [\boldsymbol{g}_{p,k}] : \mathbb{IR}^n \to \mathbb{IR}^{n}$, defined by $\boldsymbol{f}_k(\mathcal{A}) =  \bigcap_{(x^i, C_{\mathcal{F}^i}, \cdot) \in \mathscr{E}_j} C_{\mathcal{F}_k^i} + [-1,1] {\overline{f}}_k \boldsymbol{\eta}^w(\mathcal{A} - x^i)$ and $\boldsymbol{g}_{p,k}(\mathcal{A}) = \bigcap_{(x^i, \cdot, C_{\mathcal{G}^i}) \in \mathscr{E}_j} C_{\mathcal{G}_{p,k}^i} + [-1,1] {\overline{g}}_{p,k} \boldsymbol{\eta}^w(\mathcal{A} - x^i)$, are such that $\mathscr{R}(f_k,\mathcal{A}) \subseteq \boldsymbol{f}_k(\mathcal{A})$ and $\mathscr{R}(g_{p,k}, \mathcal{A}) \subseteq \boldsymbol{g}_{p,k}(\mathcal{A})$ for all $\mathcal{A} \subseteq \mathcal{X}$. Furthermore, the function $\boldsymbol{\eta}^w : \mathbb{IR}^n \mapsto \mathbb{IR}$ can be any straightforward interval extension of the weighted norm $||\cdot||_w$.

We provide a proof of the lemma and an expression for $\boldsymbol{\eta}^w$ in the supplementary material. Lemma \[lem:overapprox-fg\] states that if a set $\mathscr{E}_j = \{ (x^i,C_{\mathcal{F}^i}, C_{\mathcal{G}^i}) \}_{i=0}^{j-1}$ is known, it is possible to obtain an analytic formula to over-approximate the unknown $f$ and $g_p$. Lemma \[lem:contraction\] enables to compute the set $\mathscr{E}_j$ based on $\mathscr{T}_j$.

\[<span style="font-variant:small-caps;">Refinement via contractor</span>\] \[lem:contraction\] Given a data point $(x^i,\dot{x}^i, u^i) \in {\mathscr{T}}_j$, an interval $\mathcal{F}^i = [\mathcal{F}^i_k] \in \mathbb{IR}^n$ such that $f(x^i) \in \mathcal{F}^i$, and an interval $\mathcal{G}^i = [\mathcal{G}^i_{p,k}] \in \mathbb{IR}^{d \times n}$ such that $g_{p,k}(x^i) \in \mathcal{G}_{p,k}^i$ for all $p \in {\mathbb{N}_{[1,d]}},k \in {\mathbb{N}_{[1,n]}}$. Let the intervals $C_{\mathcal{F}^i} \in \mathbb{IR}^n$ and $C_{\mathcal{G}^i} \in \mathbb{IR}^{d\times n}$ defined by $$\begin{aligned}
        C_{\mathcal{F}^i_k} &= \mathcal{F}^i_k \: \cap \: \left\{\dot{x}^i_k - \sum_{p=1}^d \mathcal{G}^i_{p,k} {\textit{u}}^i[\alpha^p] \right\}, C_{\mathcal{G}^i_{p,k}} = \begin{cases} \Big( \left\{ \mathcal{S}_{p-1,k} - \sum_{l = p+1}^d \mathcal{G}^i_{l,k} {\textit{u}}^i[\alpha^l] \right\} \cap   \mathcal{G}^i_{p,k} {\textit{u}}^i[\alpha^p] \Big) \frac{1}{{\textit{u}}^i[\alpha^p]}, \\ 
        \quad \mathrm{if} \ {\textit{u}}^i[\alpha^p] \neq 0, \\
        \mathcal{G}^i_{p,k}, \quad \mathrm{otherwise},
        \end{cases}\\
        \mathcal{S}_{0,k} &= \left\{ \dot{x}^i_k - C_{\mathcal{F}^i_k} \right\} \cap \left\{ \sum_{p=1}^d \mathcal{G}^i_{p,k} {\textit{u}}^i[\alpha^p] \right\},
        \mathcal{S}_{p,k} = \left\{ \mathcal{S}_{p-1,k} - C_{\mathcal{G}^i_{p,k}} {\textit{u}}^i[\alpha^p] \right\} \cap \left\{ \sum_{l = p+1}^d \mathcal{G}^i_{l,k} {\textit{u}}^i[\alpha^l] \right\},
    \end{aligned}$$ for successive values of $k \in {\mathbb{N}_{[1,n]}}$ and for all $p \in {\mathbb{N}_{[1,d]}}$. Then, $C_{\mathcal{F}^i}$ and $C_{\mathcal{G}^i}$ are the smallest intervals enclosing $f(x^i)$ and $g_p(x^i)$, given only the data $(x^i,\dot{x}^i,u^i)$, $\mathcal{F}^i$, and $\mathcal{G}^i$.

\[t\]<span>0.49</span> \[DOWHILE\]<span>Do</span><span>doWhile</span>\[1\]<span> \#1</span>

\[H\]

\[1\] $\mathcal{A} \gets \mathcal{X}$, $\mathcal{R}^{f_\mathcal{A}} \gets [-M,M]^n$, $\mathcal{R}^{G_\mathcal{A}} \gets [-M,M]^{d \times n}$ Define $x_0 \in \mathcal{A}$, $C_{\mathcal{F}^0} \gets \mathcal{R}^{f_\mathcal{A}}$, $C_{\mathcal{G}^0} \gets \mathcal{R}^{G_\mathcal{A}}$ \[eq:sideinfo-boundvectorfield\] $\mathscr{E}_i \gets \texttt{Refine}((x^i, \dot{x}^i, u^i),\mathscr{E}_{i-1}, {\mathscr{T}}_i)$ $\mathscr{E}_j$

\[t\]<span>0.49</span> \[DOWHILE\]<span>Do</span><span>doWhile</span>\[1\]<span> \#1</span>

\[H\]

\[1\] Compute $\mathcal{F}^j = \boldsymbol{f}(x^j), \mathcal{G}^j = [\boldsymbol{g}_{p,k}(x^j)]$ via Lemma \[lem:overapprox-fg\] and $\mathscr{E}_{j}$ \[alg:update-ei\] Compute $C_{\mathcal{F}^{j}}, C_{\mathcal{G}^j}$ via Lemma \[lem:contraction\] \[alg:contraction-f-G\] \[alg:while-begin\] \[alg:begin-init-e\] Execute \[alg:update-ei\]–\[alg:contraction-f-G\] with $j=i$, $\mathscr{E}_{j}= \mathscr{E}_{j+1}$ \[alg:end-init-e\] \[alg:while-end\] $\mathscr{E}_{j+1}$

The proof of the lemma is established in the supplementary material. Lemma \[lem:contraction\] simply provides tighter intervals $C_{\mathcal{F}^i} \subseteq \mathcal{F}^i$ and $C_{\mathcal{G}^i} \subseteq \mathcal{G}^i$ that prune out from $\mathcal{F}^i$ and $\mathcal{G}^i$ some values $f(x^i)$ and $g_p(x^i)$ that do not satisfy the dynamics constraint $\dot{x}^i = f(x^i) + \sum_{p=1}^d g_p(x^i) {\textit{u}}^i[\alpha^p]$.

\[<span style="font-variant:small-caps;">Data-driven differential inclusion</span>\] \[thm:diffinclusion\] Given a dataset ${\mathscr{T}}_j$, the bounds ${\overline{f}}_k$ and ${\overline{g}}_{p,k}$ from Side information \[side:Lip\], it holds that the unknown vector field of the dynamics  satisfies

$$\begin{aligned}
        \dot{x} \in \boldsymbol{h}(x,u) \triangleq \boldsymbol{f}(x) + \sum\nolimits_{p=1}^d \boldsymbol{g}_p(x) {\textit{u}}[\alpha^p], \label{eq:diffinclusion}
    \end{aligned}$$

where $\boldsymbol{f}$ and $\boldsymbol{g}_p$ are obtained from Lemma \[lem:overapprox-fg\] with $\mathscr{E}_j$ taken as the output of Algorithm \[algo:construction\].

The quality of the differential inclusion  depends on how much information on $f$ and $g_p$ can be obtained from the dataset $\mathscr{T}_j$. This is the classical observability problem, sometimes referred to as persistent excitation. Thus, to improve the quality of the differential inclusion and improve future control decisions, the learning algorithm should sometimes take suboptimal actions through persistent excitations of the system.

Finally, we compute an over-approximation of the reachable set of all dynamics described by the differential inclusion . Theorem \[thm:one-step-overapprox\] provides a closed-form expression for such a set.

\[<span style="font-variant:small-caps;">Data-driven reachable set over-approximation</span>\]\[thm:one-step-overapprox\] Given the dataset ${\mathscr{T}}_j$, a constant control signal $u : t \mapsto u^q$ on the interval $[t_q,t_{q+1}]$ with $u^q \in \mathcal{U}$, Side information \[side:Lip\], and the uncertain set $\mathcal{R}^q \in \mathbb{IR}^n$ of states $x^q$ at time $t_q$. Then, a closed-form expression for $\mathcal{R}^{q+1} \supseteq \{x(t_{q+1}; u^q, x^q) \in \mathcal{X} | x^q \in \mathcal{R}^q\}$, which over-approximates the set of states the unknown system may reach at $t_{q+1}$ for all possible $x^q \in \mathcal{R}^q$, is given by

$$\begin{aligned}
        \mathcal{R}^{q+1} = \mathcal{R}^q +  \boldsymbol{h}(\mathcal{R}^q,u^q) \Delta t
        + \big( \mathcal{J}^f + \sum\nolimits_{p=1}^d \mathcal{J}^{g_p} {\textit{u}}^q[\alpha^p] \big) \boldsymbol{h}(\mathcal{P}^q, u^q) \Delta t^2/2, \label{eq:nextstate}
    \end{aligned}$$

where the matrices $\mathcal{J}^f = [\mathcal{J}_{k,l}^f] \in \mathbb{IR}^{n \times n}$ and $\mathcal{J}^{g_p} = [\mathcal{J}_{k,l}^{g_p}] \in \mathbb{IR}^{n \times n}$, over-approximations of the Jacobian of $f$ and $g_p$ , are such that $\mathcal{J}_{k,l}^f = [-1,1] w_k {\overline{f}}_k $ and $\mathcal{J}_{k,l}^{g_p} = [-1,1] w_k {\overline{g}}_{p,k} $ for all $p\in {\mathbb{N}_{[1,d]}}$ and $k,l \in {\mathbb{N}_{[1,n]}}$. Further, the set $\mathcal{P}^q$, a rough enclosure of $\{x(t_{q+1}; u^q, x^q) \in \mathcal{X} | x^q \in \mathcal{R}^q\}$, is a solution of the fixpoint equation $\mathcal{R}^{q} \ + \  [0, \Delta t]\ \boldsymbol{h}(\mathcal{P}^q, u^q) \ \subseteq \ \mathcal{P}^{q}$.

We provide a proof of Theorem \[thm:one-step-overapprox\] in the supplementary material, where we merge the differential inclusion with an interval Taylor-based expansion of order $2$ to obtain the result.

Theorem \[thm:one-step-overapprox\] does not consider uncertain control inputs or *noises* as in the literature of reachable sets' computation. However, such an extension is straightforward from the proof of the theorem. We show in the supplementary material how to incorporate *noises* in this framework.

Theorem \[thm:one-step-overapprox\], as it is, does not incorporate side information other than Side information \[side:Lip\]. We describe in the following how to incorporate more side information to tighten $\mathcal{R}^{q+1}$ given by .

\[<span style="font-variant:small-caps;">Partial dynamics knowledge</span>\]\[side:partknowledge\] The vector field of  contains both known and unknown terms. That is, $\dot{x} = \sum_{s=1}^S \mathrm{f}^s(x) \cdot f^s(x) + \sum_{p=1}^d \sum_{s=1}^S \mathrm{g}^s_p(x) \cdot g_p^s(x) {\textit{u}}[\alpha^p]$, where $\cdot$ denotes the elementwise product between vectors or matrices, $\mathrm{f}^s$ and $\mathrm{g}^s_p(x)$ are known functions, and $f^s, g_p^s$ are unknown functions satisfying Assumption \[ass:lipshitz-bounds\].

Given $\mathscr{E}^s_j$ containing past over-approximations of $f^s, g^s_p$ and a new data point $(x^j,\dot{x}^j, u^j)$, the refinement (Algorithm \[algo:refine\]) is adapted to compute in line \[alg:update-ei\] over-approximations $\boldsymbol{f}^s(x^j)$ and $\boldsymbol{g}^s_p(x^j)$ via Lemma \[lem:overapprox-fg\] and $\mathscr{E}^s_j$. Then, line \[alg:contraction-f-G\] is modified such that each $\boldsymbol{f}^s(x^j)$ and $\boldsymbol{g}^s_p(x^j)$ are contracted according to the new dynamics' constraint $\dot{x}^j = \sum_{s=1}^S \mathrm{f}^s(x^j) \cdot f^s(x^j) + \sum_{p=1}^d \sum_{s=1}^S \mathrm{g}^s_p(x^j) \cdot g_p^s(x^j) \textit{u}^j[\alpha^p]$. The contracted sets can be obtained straightforwardly by slight changes in the scheme described by Lemma \[lem:contraction\] or by calling an algorithm such as `HC4-Revise`. Thus, the new differential inclusion  is given by $\boldsymbol{h}(x,u) = \sum_{s=1}^S \boldsymbol{\mathrm{f}}^s(x) \cdot \boldsymbol{f}^s(x) + \sum_{p=1}^d \sum_{s=1}^S \boldsymbol{\mathrm{g}}^s_p(x) \cdot \boldsymbol{g}_p^s(x) {\textit{u}}[\alpha^p]$, where $\boldsymbol{\mathrm{f}}^s$ and $\boldsymbol{\mathrm{g}}^s$ are interval extensions of known $\mathrm{f}^s$ and $\mathrm{g}^s_p$. Furthermore, we compute the new Jacobian terms $\mathcal{J}^f$ and $\mathcal{J}^{g_p}$ used in $\mathcal{R}^{q+1}$ as follows: $\mathcal{J}^f = \sum_{s=1}^S \big( \frac{\partial \boldsymbol{\mathrm{f}}^s}{\boldsymbol{\partial x}}(\mathcal{P}^q) \cdot \boldsymbol{f}^s(\mathcal{P}^q) + \mathcal{J}^{f^s} \cdot \boldsymbol{\mathrm{f}}^s(\mathcal{P}^q) \big)$ and $\mathcal{J}^{g^p} = \sum_{s=1}^S \big( \frac{\partial \boldsymbol{\mathrm{g}}_p^s}{\boldsymbol{\partial x}}(\mathcal{P}^q) \cdot \boldsymbol{g}_p^s(\mathcal{P}^q) + \mathcal{J}^{g_p^s} \cdot \boldsymbol{\mathrm{g}}_p^s(\mathcal{P}^q) \big)$.

\[<span style="font-variant:small-caps;">Algebraic constraints</span>\]\[sideinfo:algebraic\] We are given a constraint $r(\dot{x}(\cdot), x(\cdot)) \geq 0$ where $r$ is a differential map. Such a constraint typically derives from conservation laws of physics.

Without loss of generality, we consider that $r : \mathbb{R}^n \times \mathbb{R}^n \mapsto \mathbb{R}$. This side information provides tighter over-approximations on $\boldsymbol{f}$, $\boldsymbol{g}_p$, $\mathcal{J}^f$, and $\mathcal{J}^{g_p}$ *locally*. Specifically, this constraint can be formulated as the new constraint $w(f(x), [g_{p,k}(x)], u, x) \geq 0$. Even if $\dot{x}(\cdot)$ does not appear in the expression of $r$, by derivating the function $t \mapsto r(x(t))$, we obtain the constraint given by $w$. If we compute the partial derivatives of $w$ with respect to all the states $x_i$, then we obtain a new constraint $z(f(x), [g_{p,k}(x)], \frac{\partial f}{\partial x}(x), [\frac{\partial g_{p,k}}{\partial x}(x)], u, x) \geq 0$. The new constraints $w$ and $z$ can be incorporated in the computation of $\mathcal{R}^{q+1}$ through contractors. More specifically, the refinement algorithm and the interval extensions of the Jacobian can be improved by additionally contracting with respect to the constraints $w$ and $z$. Thus, such side information enables to obtain a tighter $\mathcal{R}^{q+1}$.

In general, any mathematical constraints on the states, the states derivatives, or unknown terms of the dynamics can be enforced in the Taylor expansion using the contractor framework. Due to the page limitations, we provide in the supplementary material how to handle more side information.

Approximate Optimal Control
===========================

\[sec:optcontrol\] In this section, we develop an algorithm that computes approximate solutions to the optimal control problem  using over-approximations of the reachable sets. Further, we characterize the suboptimality of the approximate solutions with respect to the case of the known dynamics.

The nonconvexity in the optimal control problem  is due to the possibly nonconvex cost function $c$ and the nonconvex expression $x^{q+1} = x(t_{q+1}; x^q, u^q)$. We replace such an expression by $x^{q+1} = \hat{h}^{\theta}(x^q, u^q) \in \mathcal{R}^{q+1}$, where the function $\hat{h}^\theta$, parameterized with $\theta \in \mathbb{R}^n$, is a trajectory picked inside $\mathcal{R}^{q+1}$. For example, a straightforward choice can be $\hat{h}^\theta(x^q,u^q) = \theta \overline{\mathcal{R}^{q+1}} + (1-\theta) \underline{\mathcal{R}^{q+1}}$, for $\theta \in [0,1]^n$. Then, we solve the nonconvex problem by sequentially linearizing $x^{q+1}$ and the cost function $c$ around the solution of the $s^{\mathrm{th}}$ iteration. This results into a *linear subproblem* that is solved to full optimality. The obtained solutions are then used at the $(s+1)^{\mathrm{th}}$ iteration.

**Linearization.** Let $\mathrm{x} = [x^{j+1};\hdots;x^{j+N+1}] \in \mathbb{R}^{nN}$ and $\mathrm{u} = [u^{j};\hdots;u^{j+N}] \in \mathbb{R}^{mN}$. We denote the solutions of the $s^{\mathrm{th}}$ iteration by $\mathrm{x}^s = [x^{j+1,s};\hdots;x^{j+N+1,s}]$ and $\mathrm{u}^s = [u^{j,s};\hdots;x^{j+N,s}]$. Then, we can approximate the gradient of $h^\theta$ (or $x(t_{q+1}; x^q, u^q)$) around $\mathrm{x}^s, \mathrm{u}^s$ as follows:

$$\begin{aligned}
    A^{q,s}  &= \frac{\partial h^\theta(x^q,u^q)}{\partial x^q} \Big\vert_{x^{q,s}, u^{q,s}}
        \in \mathbb{I} +  \big( \mathcal{J}^f(x^{q,s}) + \sum\nolimits_{p=1}^d \mathcal{J}^{g_p}(x^{q,s}) \textit{u}^{q,s}[\alpha^p]\big) \Delta t  = \mathcal{A}^{q,s},\\
    B^{q,s} &=  \frac{\partial h^\theta(x^q,u^q)}{\partial u^q} \Big\vert_{x^{q,s}, u^{q,s}}
        \in \sum\nolimits_{p=1}^d \Big[ \Delta t \boldsymbol{g}_{p,k}(x^{q,s})  \frac{\partial {\textit{u}}[\alpha^p]}{\partial u_l}\Big\vert_{u^{q,s}} \Big]_{k,l} = \mathcal{B}^{q,s},\end{aligned}$$

where $\mathbb{I}$ is the identity matrix of appropriate dimensions. The jacobian $\mathcal{J}^f(x^{q,s}), \mathcal{J}^{g_p}(x^{q,s})$ are exactly $\mathcal{J}^f$ and $\mathcal{J}^{g_p}$ when no extra side information are given. With side information, the matrices are computed as described in Section \[sec:overapprox-reach\] with $\mathcal{P}^q$ replaced by $x^{q,s}$. Note that since we neglect the term in $\Delta t^2$, $\mathcal{A}^{q,s}$ and $\mathcal{B}^{q,s}$ are approximations of the actual range of the gradients of $h^\theta$.

Next, we define the new variables $\Delta \mathrm{x} = \mathrm{x} - \mathrm{x}^s$, $\Delta \mathrm{x}^{q} = x^q - x^{q,s}$, $\Delta \mathrm{u} = \mathrm{u} - \mathrm{u}^s$, and $\Delta \mathrm{u}^{q} = u^q - u^{q,s}$ in term of the unknown solutions of the current iteration $\mathrm{x}$ and $\mathrm{u}$. Thus, at the $(s+1)^\mathrm{th}$ iteration, the first-order approximation of $x^{q+1} = \hat{h}^{\theta}(x^q, u^q)$ around the previous solution $(x^{q,s}, u^{q,s})$ is $$x^{q+1,s} + \Delta \mathrm{x}^{q+1} = \quad h^\theta (x^{q,s}, u^{q,s})  + A^{q,s} \Delta \mathrm{x}^q +B^{q,s} \Delta \mathrm{u}^q +  v^{q},\label{eq:linearization}$$ where $\mathrm{v} = [v^{j};\hdots; v^{j+N}]$ are penalty variables that enable the linearization to be always feasible. Further, to ensure that the variable $v^q$ is used only when necessary, we augment the cost function with the sufficiently large penalization weight $\lambda > 0$. Thus, the solution for the $(s+1)^\mathrm{th}$ iteration, optimizes the penalized and linearized cost given by $$\begin{aligned}
         L^s(\Delta \mathrm{x}, \Delta \mathrm{u}) = \sum\nolimits_{q=j}^{j+N} ( c(x^{q,s}, u^{q,s}, x^{q+1,s}) + \nabla c(x^{q,s}, u^{q,s}, x^{q+1,s}) [\Delta \mathrm{x}; \Delta \mathrm{u}]) + \lambda \sum\nolimits_{q=j}^{j+N} \|v^q\|,\vspace{-0.20cm} \nonumber
 \end{aligned}$$ where we also linearize the possibly nonconvex function $c$ given that $\nabla c$ is its gradient, and $\|\cdot\|$ can be either the infinity norm or $1$-norm. In order to verify the linearization accuracy, we also define the nonlinear *realized* cost $J(\mathrm{x},\mathrm{u}) = \sum\nolimits_{q=j}^{j+N} c(x^{q}, u^{q}, x^{q+1}) + \lambda \sum\nolimits_{q=j}^{j+N} \|x^{q+1} - h^\theta(x^q, u^q) \|$. **Trust Region Constraints and Linearized Problem.** We impose the trust region constraint $\|\Delta \mathrm{u}\| \leq r^s$ to ensure that $\mathrm{u}$ does not deviate significantly from the control input $\mathrm{u}^s$ obtained in the previous iteration, where $r^s$ will be updated at each iteration so that the $\mathrm{x}$ remains close to $\mathrm{x}^s$. This update rule enables to keep the solutions within the region where the linearization is accurate. As a consequence, each iteration of our algorithm solves the following linear optimization problem: $$\begin{aligned}
     \underset{\Delta \mathrm{u}, \Delta \mathrm{x}}{\mathrm{minimize}}  &\quad L^s(\Delta \mathrm{x}, \Delta \mathrm{u}) \label{eq:convexsub}\\
     \mathrm{subject \ to} &\quad \eqref{eq:linearization}, \|\Delta \mathrm{u}\| \leq r^s, \mathrm{u}^s + \Delta \mathrm{u} \in \mathcal{U}^N, \mathrm{x}^s + \Delta \mathrm{x} \in \mathcal{X}^N.  \nonumber
 \end{aligned}$$ The optimal solution of the linearized problem is either accepted and used in the next iteration or rejected until convergence. When the linearization is considered accurate, i.e. the realized cost $J$ and linearized cost $L^s$ are similar, the solution is accepted and the trust region is expanded. Otherwise, the solution is rejected and the trust region is contracted. We provide in the supplementary material our algorithm with further details on the expansion and contraction of the trust region.

\[<span style="font-variant:small-caps;">Suboptimality bound</span>\]\[thm:suboptimality-gap\] Assume that $L_c$ with the $2$-norm is the Lipschitz constant of the cost $c$ on $\mathcal{X} \times \mathcal{U} \times \mathcal{X}$. Let $C_j^{\star}$ and $\hat{C}_j$ be the optimal costs of the $N$-step control problem  when the dynamics are known, e.g. $x^{q+1} = x(\cdot, x^q, u^q)$ is known, and the dynamics are unknown, e.g. $x^{q+1} = h^\theta(x^q,u^q) \in \mathcal{R}^{q+1}$. Then, the following inequality holds $$\begin{aligned}
        |  C_j^* - C_j| \leq L_c \Big( \|\mathrm{wd}(\mathcal{R}_\mathcal{U}^{j+N+1})\|_2  +\sum\nolimits_{q=j+1}^{j+N} 2\|\mathrm{wd}(\mathcal{R}_\mathcal{U}^{q})\|_2\Big),\nonumber
    \end{aligned}$$ where $\mathrm{wd}(\mathcal{A}) = \overline{\mathcal{A}} - \underline{\mathcal{A}}$ is the width of the interval $\mathcal{A}$. The interval $\mathcal{R}_\mathcal{U}^{q+1}$ is the over-approximation of the reachable set at time index $t_{q+1}$ from the initial uncertain set $\mathcal{R}_\mathcal{U}^q$ (with $\mathcal{R}_\mathcal{U}^j = x^j$) and all possible values $u^q \in \mathcal{U}$. Such sets can be computed from  by replacing $u^q$ with $\mathcal{U}$.

Theorem \[thm:suboptimality-gap\] provides that the suboptimality bound is proportional to the width of the over-approximation of the reachable set. Thus, our algorithm achieves near-optimal control with more data along the trajectory and more side information, as the over-approximations become tighter.

Numerical Experiments
=====================

\[sec:numsection\] In this section, we illustrate the effectiveness of our control algorithm through a series of examples in MuJoCo @todorov2012mujoco and a high-physics F-16 aircraft simulator @heidlauf2018verification. We empirically demonstrate that the algorithm, using data from only the current trial, can achieve performance comparable to the highly-tuned implementations of <span>`D4PG`</span> @hoffman2020acme and <span>`SAC`</span> @pytorch_sac trained over *ten million* of interactions with the environments. We emphasize that the comparison is unfair to our algorithm since, at each evaluating episode, it learns from only the *thousand* data obtained during the episode, while <span>`D4PG`</span> and <span>`SAC`</span> were pre-trained using *ten million* data before the evaluation. Further, we show in an F-16 aircraft simulator, a $13$-states and $4$-control inputs nonlinear dynamics with polynomial control, that the algorithm can meet real-time requirements. A video showing the examples can be found at the link[^1].=-1 **Experiments in MuJoCo Environments.** The equations of motion for multi-joint dynamical systems in the MuJoCo environment are as follows: $M(q) \ddot{q} + b(\dot{q}, q) = h(u) + J_c^{\mathrm{T}}(q) F_c(\dot{q}, q, u)$, where $q$ is the system's state, $M(q)$ is the inertial matrix, $b(\dot{q}, q)$ contains coriolis, centrifugal, gravitational and passive forces, $J_c^{\mathrm{T}}(q)$ is the contact Jacobian matrix, and $F_c(\dot{q}, q, u)$ is the contact force.

We seek to achieve high performance in control tasks such as driving to a target a two-link planar reacher (Reacher) and a $3$-link planar swimmer (Swimmer) based on highly-accurate Reynolds fluid drag model. Besides, we seek to maximize the speed of a running planar biped (Cheetah).

\[t\]

<span>0.3</span>

<span>0.3</span>

<span>0.3</span>

. \[fig:exp-mujoco\]

For each environment, the cost function is provided by MuJoCo and we perform numeric differentiation in order to find its gradient. The Lipschitz bounds are under-estimated using only $1000$ data points obtained prior to the on-the-fly control. The Reacher environment does not consider any side information other than the Lipschitz bounds, while Swimmer and Cheetah consider that $M(q)$ is known (Side information \[side:partknowledge\]). $M(q)$ is typically obtained for a robot through Euler-Lagrange formulation that uses the kinetic and potential energy. Further, we reduce the over-approximation of the contact force $F_c$ by considering the Couloumb law's of friction. That is, we impose the constraints $F^1_c \geq 0$ and $F^1_c \geq \sqrt{ (F^2_c)^2 \mu_1 +  (F^3_c)^2 \mu_2}$ at each contact point, where $F^1_c$ is the normal force value, $F^2_c$ and $F^3_c$ are the tangential forces, and $\mu_1, \mu_2$ are the friction coefficients. Figure \[fig:exp-mujoco\] demonstrates that it is possible to learn to control with only data from a single episode by leveraging side information. In Cheetah, more side information can improve our algorithm's performance. We reduced the time-step value of Reacher to accommodate our algorithm and observed that <span>`D4PG`</span> was unable to learn the task solely due to such a change, while <span>`SAC`</span> was not affected.

**Data-driven Control of an F-16 Aircraft.** We consider a scenario involving an F-16 aircraft diving towards the ground and show how our algorithm can prevent a ground collision using only the measurements obtained during the dive and elementary laws of physics as side information.

<span>r</span><span>0.55</span>

\[f16datacontrol\]

We compare our algorithm with the tuned linear-quadratic regulator (LQR) algorithm of the simulator. The F-16's flight control system @heidlauf2018verification is described by a hierarchical feedback control loop consisting of an autopilot and a low-level controller. Inside the simulator, the underlying dynamics of the F-16 capture the ($6$-DOF) movement of an aircraft through the standard aerodynamic equations @stevens2015aircraft. The dynamics describe the evolution of the system's states, namely velocity $v_t$, angle of attack $\alpha$, sideslip $\beta$, altitude $h$, attitude angles: roll $\phi$, pitch $\theta$, yaw $\psi$, and their corresponding rates $p$, $q$, $r$, engine $power$ and two more states for translation along north and east. The plant model uses several *linearly interpolated lookup tables* to incorporate wind tunnel data describing the engine model, the various coefficients including force and moment coefficients, and the moments due to the control surfaces.=-1 Our algorithm takes as side information the knowledge of the rigid-body dynamics of a $6$-DOF @stevens2015aircraft, while assuming that the aerodynamics forces and moments interpolated via lookup tables are *unknown*. Thus, the response of the system to control inputs is unknown and needs to be learned on the fly. The Lipschitz bounds were estimated using $1000$ data collected before the scenario.

Conclusion {#sec:conclusion}
==========

This paper develops a learning-based, data-efficient control algorithm for unknown systems using streaming data from an ongoing trial and available side information. The experiments demonstrate that it is indeed possible, with data from a single episode and side information, to perform comparably to learning algorithms trained over millions of environment's interactions. Further, we empirically show that the algorithm is fast and can be used in scenario with real-time constraints.

[^1]: \[vid\]The videos of the simulations are available at https://tinyurl.com/hdem8x76.

{'source': 'arXiv_out/2106'}