Optimal Exploration for Model-Based RL in Nonlinear Systems
Authors: Andrew Wagenmaker
Guanya Shi
Kevin Jamieson
Venue: NeurIPS 2023 spotlight (2023)
Keywords: reinforcement learning
control theory
system identification
experiment design
active learning
TL;DR: We develop an approach which optimally explores unknown nonlinear dynamical systems with the goal of learning a good controller.

Abstract: Learning to control unknown nonlinear dynamical systems is a fundamental problem in reinforcement learning and control theory. A commonly applied approach is to first explore the environment (exploration), learn an accurate model of it (system identification), and then compute an optimal controller with the minimum cost on this estimated system (policy optimization). While existing work has shown that it is possible to learn a uniformly good model of the system (Mania et al., 2020), in practice, if we aim to learn a good controller with a low cost on the actual system, certain system parameters may be significantly more critical than others, and we therefore ought to focus our exploration on learning such parameters.

In this work, we consider the setting of nonlinear dynamical systems and seek to formally quantify, in such settings, (a) which parameters are most relevant to learning a good controller, and (b) how we can best explore so as to minimize uncertainty in such parameters. Inspired by recent work in linear systems (Wagenmaker et al., 2021), we show that minimizing the controller loss in nonlinear systems translates to estimating the system parameters in a particular, task-dependent metric. Motivated by this, we develop an algorithm able to efficiently explore the system to reduce uncertainty in this metric, and prove a lower bound showing that our approach learns a controller at a near-instance-optimal rate. Our algorithm relies on a general reduction from policy optimization to optimal experiment design in arbitrary systems, and may be of independent interest. We conclude with experiments demonstrating the effectiveness of our method in realistic nonlinear robotic systems.

Optimal Exploration for Model-Based RL in Nonlinear Systems
Andrew Wagenmaker"
Guanya Shit Robotics Institute
Paul G. Allen School of Computer Science & Engineering University of Washington Seattle, WA 98195
Carnegie Mellon University Pittsburgh, PA 15213
Kevin Jamieson
Paul G. Allen School of Computer Science & Engincering University of Washington
Seattle, WA 98195
Abstract
Learning to control unknown nonlinear dynamical systems is a fundamental prob- lem in reinforcement learning and control theory. A commonly applied approach is to first explore the environment (exploration), learn an accurate model of it (system identification), and then compute an optimal controller with the minimum cost on this estimated system (policy optimization). While existing work has shown that it is possible to learn uniformly good model of the system [1], in practice, if we aim to learn good controller with a low cost on the actual system, certain system parameters may be significantly more critical than others, and we therefore ought to focus our exploration on learning such parameters.
In this work, consider the setting of nonlinear dynamical systems and seek to formally quantify, in such settings, (a) which parameters are most relevant to learning good controller, and (b) how uncertainty in such parameters. Inspired by recent work in linear systems [2], we show that minimizing the controller loss in nonlinear systems translates to estimat- ing the system parameters in particular, task-dependent metric. Motivated by this, we develop an algorithm able efficiently explore the system reduce uncertainty in this metric, and prove a lower bound showing that our approach learns a con- troller at pear-instance-optimall rate. Our algorithm relies on a general reduction from policy optimization to optimal experiment design in arbitrary systems, and may be of independent interest. We conclude with experiments demonstrating the effectiveness of our method in realistic nonlinear robotic systems'.
best explore
minimize
1 Introduction
Controlling nonlinear dynamical systems core problem in robotics, and beyond, and significant body of work in both the control theory and reinforcement learning communities has sought to address this challenge [3-5]. In many real-world scenarios [6-9], the dynamics of the system of interest is unknown, only coarse model of them is available, which
systems,
"ajvagenOcs washington. edu guanyas@andrew. cmu, edu "jamiesonecs washington edu 'Code: https://githu/: http://////.aaaaaa///aaaaaaraaaa oortrarrrrrridddfoooottooolll
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

significantly increases the challenge of control not only must we control such systems, we must learn to control them. While a variety of methods exist to address this challenge, commonly applied approach is to first perform system identification, learning an accurate model of the system's s dynamies, and then use this model to obtain a controller. Despite its promising potential, there are still several fundamental questions that must be answered to make this approach practically effective.
Which parameters are most relevant learning a good controller? Beyond some special cases, little work has been done characterizing how the estimation error from system identification translates to end-to-end suboptimality in the resulting controller of our nonlinear systems. In particular, certain parameters of the system or regions of the state space may be irrelevant to learning a good controller, and coarse estimates of these parameters would suffice, while other parameters may be critical to learning good controller, and we must therefore estimate these parameters very accurately in order to effectively control the system. In the context of this work, where nonlinearities are considered, the heterogeneity of the parameters is further accentuated. For instance, around point of equilibrium, some system parameters might be completely inactive, having no impact on the dynamics (see the example in Section 1.1 for an illustration of this).
How can we best explore as minimize uncertainty in relevant parameters? Even if we are able to determine which parameters are most important for obtaining a good controller on the true system, it is not obvious how to use this information. How can we direct our system identification phase in order to focus on learning these parameters as quickly as possible, without spending time estimating the parameters of the system less critical for control? This is fundamentally a question of exploration. While it is known in linear systems that random excitation will efficiently explore [10], exploration in nonlinear systems is significantly more challenging since, in order to excite all parameters of interest, non-trivial planning may be required to ensure all relevant states are reached (as is the case in the example considered in Section I.1).
We address both these questions in a particular class of nonlinear systems parameterized as:
1h+1 A, (Ph, Up.) + w?.
(1.1)
Here 2t E IR dz denotes the state of the system, uAa. E C Rdd the input, wP ~ (O, o². .T) random noise, +):-)) E Rd a (possibly nonlinear, known) feature map, and A, E 1dd the (unknown) system parameter. Systems of this form are able to model variety of real-world settings [11-15] and have been the subject of recent attention in the reinforcement learning community [1, 17, 14], yet the aforementioned questions have remained unanswered. Towards addressing this, in this work we make the following contributions:
1. For systems of the form (I.1), given some cost of interest which we wish to find a controller to minimize, we (a) formally characterize how estimation error translates into suboptimality in the learned controller, under the certainty equivalent control rule and (b) provide a lower bound on the loss of any (sufficiently regular) control rule learned from T rounds of interaction with (1.1).
2. Motivated by this characterization, we present an algorithm which achieves the instance-optimal rate, with controller loss matching our lower bound. To the best of our knowledge, this is the first statistically optimal algorithm in the setting of nonlinear dynamical systems. Our algorithm relies on generic reduction from policy optimization to optimal exploration in arbitrary dynamical systems (not necessarily of the form (I.1)), which may be of independent interest.
3. We present numerical experiments on several realistic nonlinear systems which illustrate that our approach-efficientlly exploring to reduce uncertainty in parameters most relevant to learning a controller-yields significant gains in practice.
To further motivate our approach, we consider the following example.
1.1 Motivating Example
To motivate the need for effective exploration, we consider a simple I-D system with nonlinear dynamics given by:
Fh++ (1 + ug + 10
IIn real-world settings, & is typically (1) from physics (i.e., the system structure is known but some parameters such as drag coefficient unknown [3]) (2) learned using representation learning or meta-learning [12, 15]. and/or (3) from random features (e.g., any sufficiently regular, smooth nonlincar system f(r, u)) can be modeled by (1.1) using N random features up to 1/vN error [16]).

---

where (x)x) max - 100(x - c,)2, for some C₁. We choose = 0.8, a2 = 1, and
ag ...... 012 -3. We assume 01:12 are unknown, (0:) 10 known, and set
cost(2,, u) (x -2) o,)² 100 1..1..... u²a
With this choice of cost, the optimal controller will attempt to direct the state z to the equilibrium point C1 and maintain this position. Note that, with our choice of Φ,, Φi o only when æ is very close to c.. This renders the parameters a4:12 irrelevant to learning the optimal controller, since 22.-.., 110 will be inactive if we are playing optimally, but learning 01:3 is critical to performing optimally. In particular, the coefficient of the first nonlinearity, d3, must be learned, as its value significantly changes the dynamics at the goal state.
We illustrate the result of running this system in Fig- ure I. comparing our proposed approach (Task-Driven Exploration, Algorithm 1) to the approach which chooses Un ~ (0,0, (Random Exploration), and
Contelter LoGs
the approach proposed in [1] (Uniform Exploration) which seeks to explore so as to estimate 41:12 uniformly well. As can be seen, neither of these latter two approaches are able to learn a good controller, while our approach eas- ily finds near-optimal controller. The failure modes of each of these approaches is somewhat different. Here Random Exploration on fails since the chance of reaching the point æn ~ Ci is extremely small if the input is random noise-reaching 61 requires playing a particular sequence of actions which are very unlikely to be played if un is chosen randomly. The Uniform Exploration on approach does, in contrast, plan and, given enough time, is guaranteed to estimate all parameters accurately. However, as it aims to estimate all parame- ters uniformly well, it will attempt to estimate 04:12 accurately despite their irrelevance to control, which will slow down the rate at which it is able to estimate Only our approach, which both plans and takes into account the cost while exploring, is able reach ag enough times efficiently estimate it, and learn a good controller.
lasi--nn van Exploration (Ours) Random Exploration
Uniform Exploration
Moon
Number Eggsades
Figure Example
Performance on Motivating
This example illustrates that is critical both explore efficiently, and also let the objective- learning a good controller-guide this exploration. We emphasize that the behavior in this example is only exhibited in nonlinear systems- thoushhhhhhhhhh taking into account the task while exploring in linear systems is known to yield provable improvements [2], even playing random noise allows every direction be learned in such systems. In nonlinear systems, however, this not the case-one may fail to learn completely unless careful planning is performed.
2 Related Work
Learning for control. Recently, there has been increased interest in studying control problems from a learning-thooretic perspective, largely for linear system settings such as online LQR or LQG with unknown dynamics [18, 10, 19-26]. In the nonlinear setting, [27-29] provide formal guarantees on system identification in several different classes of nonlinear systems, yet they only consider noiseless systems, or systems that are significantly easier to excite than (I.1). [17] study systems of the form (1.1), but consider only the regret minimization problem. While their bounds would yield polyno- mial complexity via online-to bothhtchhhhhhtteoeeeeate conversion, the resulting guarantec would scale a ( (T) rate, significantly slower than our O(1/T) rate. Several additional works in reinforcement with gen- eral function approximation encompass nonlinear systems of the form (1.1) [30-32], 32]. yet these results also achieve slow O(1/VT) rate. The most relevant work [1] proposes an active learning approach to identify unknown parameters in (I.1). with the goal of minimizing the Euclidean distance in the parameter space. However, they do not provide end-to-end guarantees shown in Section 1.1, this approach could be significantly worse than learning a model with the goal task in mind. Also very related to our work is [2], which seeks answer a similar of questions: per- forming system identification in order to learn a good controller. This work is restricted to the setting of linear dynamics, however, and does not address the additional complexities of nonlinear systems. System identification, dual control, and iterative learning control. There is a large body of classical work in system identification [7], and our work can be seen an instance of active system
learning controllers and, as
3

---

identification. While variety of approaches have been proposed for active system identification [33-40], these tend to only consider linear systems, or lack rigorous theoretical guarantees. Recently deep learning approaches have also been applied in system identification [6, 8, 9, 41, 42]. In these works, the system identification phase is separate from the downstream controller design. Instead, in the control community, estimating parameters while simultaneously optimizing for performance has been formulated as a dual or iterative learning control problem [43-45], yet these settings focus on stability or asymptotic convergence whereas our work quantifies the end-to-end suboptimality gap. Model-based reinforcement learning. This paper falls into the broad category of model-based reinforcement learning (MBRL), where an agent explores the environment to learn a model and then computes an optimal policy using the learned model. On the empirical side, deep MBRL has made exciting progress in many domains [46-48], and several task-aware methods have been designed to improve MBRL's performance [47-49], yet these works lack formal guarantees. On the theoretical side, a variety of different model-based approaches exist [50-55, 14]; however, the majority of these consider restricted settings such as tabular or linear MDPs. Of particular interest is the work of [14] which presents a result in systems of the form (1.1). While they show that polynomial sample complexity is possible, their guarantee scales at a (1/TT)/6) (1/TT) rate.
rate compared to our much faster
Adaptive nonlinear control. Adaptive nonlinear control also seeks to control an unknown nonlinear system with parametric uncertainties [3, 4J. In particular, the key idea of model-reference adaptive control (MRAC) bears affinity this paper, in that the adaptation law in MRAC adapts unknown parameters in task-aware manner. There are two main differences between MRAC and our work. First, adaptive control does not explicitly optimize cost function- the objective typically tracking error convergence and Lyapunov stability, whereas our framework allows general cost functions and the focus is typically on asymptotic convergence, while we give non-asymptotic optimality guarantees. Second, adaptive control has by and large been limited to specific system classes (e.g.. fully-actuated systems [4, 15)) and policy classes (e.g.. policy to directly cancel out the matched uncertainty [12, 13]), whereas our framework allows more general systems and policy classes.
3 Preliminaries
Notation. ||lloop denotes the operator norm (matrix 2-norm), || ||F the Frobenius norm, and ||- 1lar the Mahalanobis norm, defined as ||>|| M == vx Mx for M 2 0. vec(A) denotes the vectorization of matrix A. (A; == (A'= A A'Ilp S r)- [H] (1, H). We let EA[-] denote the expectation over trajectories induced on system with parameter A, and EA,=[-] the expectation
induced when policy æ is played. poly(-) denotes some term that is polynomial in its arguments, with exponents absolute constants. We use S informally to highlight key parameters in an inequality.
Setting, In this work, we are interested in systems of the form (1.1). We consider the episodic setting, where episodes are of length H, and assume that each episodes starts from a given state 21. We also as- sume |l < BA for some known B O. We note that the setting considered here encompasses many world systems of interest in robotics and control (e.g., [12, 14, 11, 15] and Section 6).
The goal of the learner is to find policy (controller) π (TT ) which achieves minimal cost on (1.1), for the cost defined by some (known) function (cost, (- >) with cost,, IR x 4 + R.. For given policy x, we define the expected cost on system A
J(;; A) = EA.= It cost, (mn, un)
We consider the following interaction protocol:
1. Learner interacts with (I.I) for T episodes, at each episode playing a policy Texp E llexp-
2. After T episodes, the learner proposes policy ीि E II*.
3. The learner suffers cost J (fr; A.).
The goal of the learner is therefore first to explore and, after T episodes of exploration, to propose its best guess at the optimal controller for (I.1), कт. Here we take Hoxp to be a (known) set of admissible exploration policies (for example, policies with bounded input power), and II* (known) set of admissible control policies. We assume that policies in II* are deterministic, but allow for randomized policies in Hexp- Policies may be either open- closed-loop.

---

System Notation. We let T denote the space of all possible state trajectories, T C ( and, for any T, let TiAh denote the first h states and inputs in t. For any policy и, we denote
A, RAA E H( un
( ( u
the expected covariance induced by playing on system A, A, := AA.. and Á := la & A the Kronecker product of ld and A. Finally, we let denote the convex hull of covariance matrices induced by exxp. Ω = (EET [Am] w Ar for ATeep the set of distributions over eexp-
3.1 Regularity Assumptions
In order to make learning in (1.1) tractable, we need several regularity assumptions. Assumption (Bounded Features). For all Rd= and U, we have (1 u)ll2 S B Assumption 2 (Bounded Cost). There exists some (A.) > O such that, for all A E BF (Ax; Toost (A.)) and all E II,, have EA,=[(En== cost, (2n,, [n) S Lenst.
Assumption 3 (Uniform Feature Excitation). There exists E Alwop such that Amin oo (A=a))) 2 Sor some Xuin > 0.
We remark that these assumptions have appeared before work on systems of the form (1.1) [1, 17]. In particular, Assumption 3 implies that every direction of A. can, in principle, be excited, allowing it to be learned. order to precisely quantify the optimal rates of learning, we require that our system satisfy certain smoothness assumptions. First, we require that Φ(.,-) is differentiable in its second argument.
Assumption (Smooth Nonlinearity). For all E RRd and u E U, Φ(x u) is four-times differen- tiable in u. Furthermore, ||V (xx, u) Lap Vi E (1,2,3,4 4), a E Rd,, and E L.
We also require that the class of admissible control policies, IT*, has a parametric form, IT = (TT O E de }, and that the parameterization is smooth in the following sense.
Assumption 5 (Smooth Controller Class). (TI.) and h E [H]. Furthermore, || ( (TI:A) I Le for Vi E (1,2,3,43 4}. 0 E Rdo, and т E T.
) is four-times differentiable in O for all & E T
Assumption is satisfied for commonly considered classes of controllers, such as linear controllers, but also satisfied by more complex classes such as neural network controllers. While the learner may propose any म E II*, are particularly interested in the certainty equivalence decision rule (i.e., the learner decides रт as if the estimated system is the actual one), defined as:
n. (A) == (A)) for (A()) arg mingeR [n: (A.
(3.1)
To ensure that x. (A) is well-defined and sufficiently regular, we make the following assumption. Assumption 6 (Unique Optimal Controller). We assume that the global minimum of I [(m A.), (A.),, is unique, and that (m: A.)le=a.(A.) > 0.
In general, the policy optimization problem in (3.1) may not be computationally tractable. As we show in Appendix D. the globally optimal decision rule of (3.1) ) can be replaced with a locally optimal decision rule (i.e. म. (A) local minimum of (=; A)). Furthermore, Assumption 6 can be replaced by assuming the differentiabilityy of (A) with respect to A for A near A.. For case of exposition, in the main text we assume that Assumption holds and that n, (A) is defined as in 13. With these definitions and under Assumptions 2, and 5, we can show that (==;; ; A.) is differentiable in and, combined with Assumption 6, that 0. (A) is differentiable in A, for E (p(A.:ra ro (A.)) and some re (A.) O. We let Lx, denote an upper bound on the norm of the derivatives of 0, (A).
Optimal Exploration in Nonlinear Systems
In this work, we are interested in characterizing the instance-optimal rates of learning a controller π E IT* which minimizes the loss J(T; A.). The following result, generalization of Proposition 8.2 of [2] to nonlinear systems, is the starting point of our analysis.
5

---

Proposition 1 (Informal). Under Assumptions 1, 2 and 4 to 6 and on the system (1.1), we have
= lIvec(A. A)) +0 (1.. AAli)) (r) - (TT
for
H(A.) := (4) (A))
and where (-) hides factors polynomial in the regularity parameters of Assumptions to 6.
The quantity H(A.) == (² (A): A.) referred as the model-task Hessian in [2]. corresponds to the curvalure of the loss of the precisely quantifies how estimation error each coordinate of A, translates into suboptimality of the controller- providing an answer to our question of which parameters are most relevant to learning a good controller- and reduces the problem minimizing the controller loss to estimating A, in particular norm. The following result gives a bound on this estimation error, ||vec(A, A)
controller (A) around A <- A..
Proposition 2 (Informal). Consider interacting with (1.1) for T episodes, and let Ar Eh 1=1 s(ahh u (at), ) denote the observed covariates and
À arg min E E hh 11 Abb w
the least-squares estimate of A.. Recalling that ÂT Ide @ Ar, we have, with high probability:
||voo(A, - -))lBAA 5o tr(H((A))A)).
4.1 Algorithm and Upper Bound
Proposition motivates our algorithmic approach: explore to collect covariates Ar minimizing (r(H(AA)) There are two primary challenges to achieving this: we do not know H(A,), as it de- pends on the (unknown) parameter A, and, even if we did know H(A.), is not clear how to explore collect data minimizing tr(H(AA.AA.) We address both of these challenges in Algorithm 1.
Algorithm Optimal Exploration in Nonlincar Systems (informal)
1: inputs: episodes T, (cost A=11 confidence 8, control policies I1", exploration policies Ieexp
2: A < 0, l - [log, T 7/87, T₁
3: for
eT do
4: Compute estimate of model-task Hessian: He + H(A')
5: Run DYNAMICOED on (A) +- tr(He 111 to learn exploration policies IIg C TTxp
6: Rerun each policy in II N₂ [Te/[ times, denote collected data Dz
7: Estimate A,: 7 arg min Σ (TAAT. || Acp(an, ux)
8: return कo. c T. (1) e II*
Algorithm proceeds epochs of exponentially increasing length. At each epoch first approximates H(A.)) ) by computing the model-task Hessian of the estimated system, A². Using this approximatiom of (A.)), it seeks to explore to minimize tr (r(H((A))) )A'))" This exploration routine is encapsulated in the DYNAMICOED (dynamic optimal experiment design) function, an adaptive experiment-desige routine inspired by recent work in reinforcement learning [56] and described in more detail in Sec- tion 5. DYNAMICÕED returns of exploration policies, II,, which we run collect data De. As we will show, the collected covariates, A = ElI (mM..A))) Φ(I,, un un) (xx,, un) satisfy
Ln (H(AA)
ST. minAen In (H(((AAA-)
which implies that DYNAMICOED collects data minimizing tr (r())(A')) 11 at near-optimal rate. Given the data De, we form the least-squares estimate of A,, 7++1 and the process repeats. After running for T episodes, the eertaint--eqiivllnn controller on the last estimate obtained, fy = n. T. (Afr+1), is returnd.. The following result bounds the suboptimality of ीि as compared to n, (A.).

---

Theorem 1. Under Assumptions I to 6, if 2 Opoly max(1, (e,oa(AA)) (roo(A))). then with probability at least 1 5, Algorithm I explores with policies in Πoxp at every episode, runs for at most T episodes, and returns är E II satisfying:
d min tr (H(A,)A-1) C' Clog 6dgds
Opoly T3/2
- -T)
+
T
AER
where we recall 52 is the set of possible expected covariates (1.1), C' is universal constant, and
Opoly = poly(da dx. H, BA, B$. Los Lo, Loost, La, Dws o log F)
man
Theorem shows that Algorithm 1 is able to explore so as to optimally minimize the exploration loss tr(?((A.)AT)) up to a lower-order term scaling as 3 and polynomially in system parameters. While Propositions and 2 show that collecting data which minimizes tr(H(A.) )A77) ') is in some sense fundamental, it clear is necessary. We next show that is indeed necessary.
4.2 Lower Bounds Learning Controllers
Our goal is to show that, up to constants and lower-order terms, the bound given Theorem is not improvable, regardless of which controller estimate use. To obtain such lower bounds, need several additional assumptions. In particular, we require that the loss [ A) grows quadratically in the distance 0 is from 0. (A), and strengthen Assumption 3 to ensure (1.1) is sufficiently easy to excite. Formal statements of these conditions are given in Appendix F. Our lower bound as follows.
Theorem (Informal). Under Assumptions
and the additional regularity assumptions men- tioned above, as long as T 2 Cib. for any Wexp E Aillsyg we have
a 3T
Cbb T5/4
min max EDr~A 1J (G((D)) J(H. (A); a AEST
min (r(H(A..)A))) ACΩ
for Br == (
EDrmAweespl E ET waxe [EDT~A, |-]l the expectation over trajectories generated by running policies π ~ Wexp on system A for T episodes, ग any mapping from observations to policies in I1", and Cib some value scaling polynomially in problem parameters.
Note that this lower bound holds for any A, and mapping Φ, as long our assumptions are met. Up constants and lower-order terms, the scaling of Theorem 2 matches that of Theorem 1-both scale with min e br(H(A.) -t) implies that Algorithm 1 is indeed optimal (under certain additional regularity conditions). To the best of our knowledge, this is the first result characterizing the optimal statistical rates for learning in nonlinear dynamical systems. We emphasize that Theorem holds for any decision rule --it does not require that we use the certainty equivalence decision rule. As Algorithm does rely on certainty equivalence, this result also implies that the certainty equivalence decision rule is optimal for (certain classes of) nonlinear dynamical systems.
The proof of Theorem 2 builds the work [2], which shows similar result for linear dynamical systems. It critically relies on our quadratic decomposition of the controller loss in Proposition 1, which reduces the problem of obtaining lower bound controller loss to lower bound estimating A, in the H(A.) norm. Given this, the result can be obtained by applying lower bounds on regression in general norms.
5 Optimal Experiment Design in Arbitrary Dynamical Systems
We turn now to the DYNAMICOED routine, which is the key algorithmic tool we use to prove Theorem 1. DYNAMICOED is general reduction from policy optimization to optimal experiment design in arbitrary dynamical systems, and is an extension of a recently proposed approach for experiment design in linear MDPs [56]. This section may be of independent interest.
To illustrate the generality of this reduction, in this section we consider the following system:
Bh++ [xh,, uhs wa), h = 1, .... H,
(5.1)
where wy E X C &R denotes the state, un E l C Rdd the input, and wn E Rh the noise. We take the dynamics (fr H to be unknown and arbitrary. We assume there is some known featurization of

---

our system that is of interest, Φ(x, u) + R and an experiment design object on this featurization, addexds + R. Our goal is to collect some set of trajectories {T:) which minimizes 4;
+ TH Ei u/ (i)o(a) - T)
As an example, (A)) log (A), this reduces to D-optimal design, and (() -r(H-A-)))) the setting considered in Section 4, this reduces to weighted A-optimal design. As before, we assume we have access to some set of exploration policies eexp and define A, and Ω as in Section 3, but with respect to this new feature map & and system (5.1). We also define Q to be the space of all possible covariance matrices:
Ω = {> !! 6l2n, un ((xn, un)" Tn E X, un E E vA E {
To facilitate efficient experiment design in this setting, will make the following assumption +. Assumption (Regularity of Φ). 4 is regular in the following sense:
1. is convex, differentiable, and 3-smooth in the norm || (with dual-norm || 1|=):
VAA - V A 3- |A A
AY, E Ω
2. There exists some M satisfying sup SlIPpeX 10( u) V ((A) u) s M.
The key algorithmic assumption we make is access to a regret minimization oracle on (5.1).
Assumption 8 (Regret Minimization Oracle). Let cost, (ar, u) = Φ(x, T Qn u. for some Qn E Rdd such that Σn costi, (Ik, uz)l S 1 for all Di E X, un U. We assume we have access to some learner luR which is able to achieve low regret on costs {costa (-.-)) with respect to policy class leepp. That is, with probability at least 1 - ô:
Et F.S.5. E
uf))] )] - mmingenlar J.
ux)) S Cr log J To
for some OR > 0, PR > 0, and a E (0, 1), and where ne the policy ARR plays at episode t.
Note that the regret minimization algorithm satisfying Assumption 8 may be arbitrary. For example, for linear systems, we could apply provably efficient algorithms for the Linear Quadratic Regulator [25, 20]; for nonlinear systems of the form (1.1) we could apply the LC algorithm of [17]; for more general settings of reinforcement learning with function approximation. algorithms such as BILIN-UCB [30] or E2D [31] could be applied. In practice, though they may not formally satisfy the guarantee of Assumption 8, deep RI approaches could be used. We have the following result.
Theorem Fix T and denote == E. ||- A'|]. Under Assumption 7, and assuming we have access to a learner A.R satisfying Assumption with 1/2, DYNAMICOED runs for T episodes on (5.1), and with probability at least 8 collects data { ut,) (h)eeeeeee satisfying
T H
3R log HM(CR log 2T 3 3log" 1/2 5
①
min ((A) Ae
<
T
T1/3
1=1
4=1
where 0 = <00/ w.)). and we recall Ω is the set of possible expected covariates on (5.1).
Theorem 3 shows that, given access only to a regret minimization oracle, it is possible to solve experiment design problems on arbitrary dynamical systems. The requirement that 1/2 is for expositional purposes only-we generalize this result to arbitrary a (and more general feature maps) in Appendix C. Under certain conditions, it can be shown that, if the exploration policies DYNAMICOED runs to collect @ are rerun, the newly collected data satisfies a similar guarantee as Theorem 3. This lets DYNAMICOED to learn an approximate solution of min ((A), and then rerun the learned policies as many times as desired to collect additional data approximately minimizing &
5.1 Overview of DYNAMICOED Algorithm
DYNAMICOED is inspired by recent work on experiment design in reinforcement learning [57, 58, 56, 59]. and can be seen an extension of the FWREGRET algorithm of [56] to arbitrary systems. We

---

refer the reader to [56] for more in-depth discussion of the FWREGRET algorithm, and briefly sketch its extension arbitrary systems here (see Appendix and Algorithm 4 for precise definitions).
Algorithm 2 Dynamic Optimal Experiment Design (DYNAMICOED, Informal)
1: input: objective 4, episodes T, confidence 6, regret algorithm ArR exploration policies eоx
2: Set K + O(T2/3), + O(T1/5), 7n f n+1
If %% (( kin u4 ") for (æx) 224 ") the state-input at step h of episode & of iteration
3: Play any Tex E eexp for K episodes, set Ao f K
Σ Σ k.0 (%) (.")
4: for = 1, ................................ .N do
5: Compute derivative of & (AAn En f V (A) A=A--1
6: Run AR on cost cost (x, u) + M (1 u) (En ((, for K episodes
7: An (1 Vn An) + t E -A=I
E t (Φ (hh))
8: return 1
T En k= h Oh
k.n (ox
Conceptually, DYNAMICOED runs variant of conditional gradient descent on the objective (A). At each iteration, n, it computes the gradient of the loss at the current iterate, E, <- V
To run a standard gradient descent algorithm on this objective, we would simply update - by taking a step the direction E,,. However, our objective is to minimize & over the constraint set, S2. Thus, rather than taking step in the direction En. we wish to take step in the direction of steepest descent within the constraint set.
The challenge is that the constraint set in our setting, S2 is unknown, as it depends on the expectation over trajectories induced on the unknown dynamics (ff))== and therefore we cannot directly compute this steepest descent direction. The key observation is that the computation of this steepest descent direction is equivalent solving:
arg min
Texp min
F.g.T.A E un) ((n)))(()) (,)) un)]
This is simply a policy optimization problem. however, and can be solved approximately by Ax under Assumption 8. Thus, in the call to AR on Line 6. we approximate the steepest descent direction, and on Line 7 update A in this direction. Convergence of this procedure to the optimal value, min & (A), can then be shown by the standard analysis of conditional gradient descent. We remark that, under Assumption and Assumption this argument is completely generic and does not require that our system, (5.1), exhibit any additional properties.
5.2 From Theorem 3 to Theorem
In Algorithm our goal to collect covariates, Á= on (1.1) such that tr(H(A')) is as small as possible. To achieve this, we apply DYNAMICOED to the dynamics (1.1) and objective (A) (r( ) -1), with Assumption 8 instantiated by the LC algorithm of [17]. By the guarantee given in Theorem 3, after running for a number of episodes N which seales polynomially in problem parameters, DYNAMICOED will collect covariates AN such that De y AN) I 2 minxen (A),, which implies tr(H((A') A < 2 min (T(H(AAAA-)) -1). By rerunning the policies DYNAMICOED used collect this AN for Te/N additional times, we can ensure ( S +,- min (H*)(((())))))))))(>))))))) -1) as desired.
We remark that the LC algorithm requires access to a computation oracle. As the focus of this work primarily statistical, we leave addressing this computational challenge for future work. Furthermore, as we show in the following section, computationally efficient, sampling-basee implementations of our approach are very effective in practice. We remark well that the objective ultimately care about minimizing is tr tr(H(A,)AA)) As show, by including small amount of uniform exploration, we can ensure that the suboptimality incurred optimizing tr(H(ā')A -1) instead of tr( tr(H(A.)A only contributes the lower-order terms of the final guarantee in Theorem 1.
6 Experimental Results
Finally, we demonstrate the effectiveness of our proposed approach (Algorithm 1, the Task-Driven Exploration method in Figures 1 to 3) on several systems motivated by robotic applications. We

---

70
DrivDriven Exploration (Ours)
6000
Task Driven Explaration (Ours)
Nean Excess Controller Loss
80
Random Exploration
Mean Excers Controller Loss
Exploration fniform Exploration
Uniffomm Exploration
5000
50
40
4000
30
20
2000
10
1000
100
200
300
400
500
600
Episodes
Number of Episodes
Figure 2: Performance on Drone
Figure 3: Performance on Car
compare Algorithm I with an approach that plays Un NV00 ou I) (Gaussian Exploration), and an approach inspired by [1] (Uniform Exploration), which seeks to estimate A, uniformly well, playing inputs that reduce | A.llop
To benchmark the performance of these approaches, we consider an affine system with dynamics corresponding that of simplified 3-D drone (i.c., 3-D double integrator with a gravity term), and a nonlinear system with dynamics corresponding to that of a 2-D car. For both systems, we choose H 50, and plot the value of J (R₁; A.) J(x, (A.); A.) for 7. the certainty-equivalnnee controller computed on the estimate of the system obtained at time t. For the drone, we let II" be the class of linear-affine feedback controllers, and for the car, II* a set of nonlinear controllers with dimension 4. While the optimal controller for the drone can be computed in closed-form, for the car we rely on a sampling- -baed routine to find an approximately optimal controller. The model-task hessian )(A) is computed via automatic differentiation. For the exploration policies of Task-Driven Exploration and Uniform Exploration, eexp we rely MPC-style sampling
based methods. For all approaches, we require that EA, E un ||]] S 72 for some 7² >> 0 and all Tex Ilexp- On all examples, we implement DYNAMICÕED with AR posterior sampling- inspired version of the LC of [17]. Figures and 3 shows performance averaged over 100 trials, and Figure over 200 trials. Additional experimental details can found Appendix G.
As illustrated in Figures to 3, our approach yields a non-trivial gain over existing approaches on all systems. particular, in Figures 2 and 3 it improves on the sample complexity of existing approaches by roughly factor of 2 for example, in the drone system, reaching excess controller cost of 10 after less than 20 episodes, as compared to over 40 episodes for existing approaches.
Our implementation is very modular, and any piece (for example, the parameterization of Texp and II" the policy optimizer, or the exploration routine) can be easily replaced with other procedures. Our results highlight that, even when using, for example, a possibly suboptimal policy optimizer, exploring so to minimize uncertainty in the model-task hessian yields non-trivial gain. We expect that this would hold true regardless of the policy optimizer used-the model-task hessian will adapt to the structure of the policy optimizer. Integration of our approach with deep model-base RL approaches is an interesting direction for future work, but we believe the approach will scale to these settings as well.
7 Conclusion
In this work, we have characterized the instance-optimal rate of learning controllers in nonlinear dynamical systems. To the best of our knowledge, this is the first work to obtain an optimal sample complexity for learning in nonlinear dynamical systems. Furthermore, our experimental results demonstrate the effectiveness of our proposed algorithm in realistic nonlinear systems. This work opens the door for several interesting directions for future work. First, it is not clear that the assumption uniform feature excitation, Assumption 3, is necessary. Can this be removed with more refined analysis (or shown to be necessary)? Second, while in many settings & is known or can be effectively represented by random features, in some settings it is helpful to learn it [12]. Can obtain end-to-end guarantees on learning both & and A,? ? Finally, it is of much interest to extend our experimental results to larger-scale systems for real-world deployment.
10

---

Acknowledgements
AW would like to thank Kevin Tully for helpful discussions. The work of AW is supported by NSF HDR 62-0221. The work of KJ is supported in part by NSF TRIPODS 2023166 and CIF 2007036.
References
[1] Horia Mania, Michael Jordan, and Benjamin Recht. Active learning for nonlinear system identification with guarantees. J. Mach. Learn. Res., 23:32-1, 2022.
[2] Andrew Wagenmaker, Max Simchowitz, and Kevin Jamieson. Task-opumal exploration in linear dynamical systems. In International Conference on Machine Learning, pages 10641 10652. PMLR, 2021.
[3] Jean-Jacques E Slotine, Weiping Li, et al. Applied nonlinear control, volume 199. Prentice hall Englewood Cliffs, NJ, 1991.
[4] Karl Äström and Bjöm Wittenmark. Adaptive control. Courier Corporation, 2013.
[5] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[6] Guanya Shi, Xichen Shi, Michael O'Connell, Rose Yu, Kamyar Azizzadenesheli, Animashree Anandkumar, Yisong Yue, and Soon-Jo Chung. Neural lander: Stable drone landing control using learned dynamics. 2019 International Conference on Robotics and Automation (ICRA), pages 9784-9799 9790. IEEE, 2019.
[7] Lennart Ljung. System identification. Springer, 1998.
[8] Duy Nguyen-Tuone and Jan Peters. Model learning for robot control: a survey. Cognitive processing, 12:319-340 340, 2011.
[9] Lukas Brunke, Melissa Greeff, Adam W Hall, Zhaocong Yuan, Siqi Zhou, Jacopo Panerati, and Angela P Schoellig. Safe learning robotics: From learning- based control to safe reinforcement learning. Annual Review of Control, Robotics, and Autonomous Systems, 5:411-444, 2022.
[10] Max Simehowitz, Horia Mania, Stephen Tu, Michael I Jordan, and Benjamin Recht. Learning without mixing: Towards sharp analysis of linear system identification. arXiv preprint 1rXiv:1802.08334 2018.
[11] Guanya Shi, Kamyar Azizzadenesheli, Michael O'Connell, Soon-Jo Chung, and Yisong Yue. Meta-adaptive nonlinear control: Theory and algorithms. Advances in Neural Information Processing Systems, 34:10013-10025, 2021.
[12] Michael O' O'Connlll, Guanya Shi, Xichen Shi, Kamyar Azizzadenesheli, Anima Anandkumar, Yisong Yue, and Soon-Jo Chung. Neural-fly enables rapid learning for agile flight in strong winds. Science Robotics, 7666))eab66597, 2022.
[13] Nicholas M Boffi, Stephen Tu, and Jean-Jacques E Slotine. Regret bounds for adaptive nonlinear control. In Learning for Dynamics and Control, pages 471-483. PMLR, 2021.
[14] Yuda Song and Wen Sun. Pc-mlp: Model-based reinforcement learning with policy cover guided exploration. In International Conference on Machine Learning. pages 9801-9811. PMLR. 2021.
[15] Spencer M Richards, Navid Azizan, Jean-Jacques Slotine, and Marco Pavone. Adaptive-control- oriented meta-learning for nonlinear systems. arXiv preprint Sit::21033044900 2021.
[16] Ali Rahimi and Benjamin Recht. Uniform approximation of functions with random bases. In 2008 46th annual allerton conference on communication, control, and computing, pages 555-561. IEEE, 2008
[17] Sham Kakade, Akshay Krishnamurthy, Kendall Lowrey, Motoya Ohnishi, and Wen Sun. Infor- mation theoretic regret bounds for online nonlinear control. Advances in Neural Information Processing Systems, 33:15312-1553 2020.

---

[18] Yasin Abbasi- Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances neural information processing systems, 24:2312-2320, 2011.
[19] Max Simchowitz, Ross Boczar, and Benjamin Recht. Learning linear dynamical systems with semi-parametric least squares. arXiv preprint 1902.00790 2019.
[20] Horia Mania, Stephen Tu, and Benjamin Recht. Certainty equivalence is efficient for linear quadratic control. Advances in Neural Information Processing Systems, 32, 2019.
[21] Alon Cohen, Tomer Koren, and Yishay Mansour. Learning linear-quadratic regulators efficiently with only VT regret. arXiv preprint (00.00690200223,, 2019.
[22] Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. On the sample complexity of the linear quadratic regulator. Foundations of Computational Mathematics, 20(4):
633-679, 2020.
[23] Chenkai Yu, Guanya Shi, Soon-Jo Chung, Yisong Yue, and Adam Wierman. The power of predictions in online control. Advances in Neural Information Processing Systems, 33: 2020.
[24] Andrew Wagenmaker and Kevin Jamieson. Active learning for identification of linear dynamical systems. In Conference on Learning Theory, pages 3487-3582. PMLR, 2020.
[25] Max Simchowitz and Dylan Foster. Naive exploration is optimal for online lqr. In International Conference on Machine Learning, pages 8937-8948. PMLR, 2020.
[26] Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non- non-stochastic control. In Conference on Learning Theory, pages 3320-3436. PMLR, 2020.
[27] Dylan Foster, Tuhin Sarkar, and Alexander Rakhlin. Learning nonlinear dynamical systems from a single trajectory. In Learning for Dynamics and Control, pages 851-861. PMLR, 2020.
[28] Samet Oymak. Stochastic gradient descent learns state equations with nonlinear activations. In conference on Learning Theory, pages 2551-2579, PMLR, 2019.
[29] Yahya Sattar and Samet Oymak. Non-asymptotic and accurate learning of nonlinear dynamical systems. The Journal of Machine Learning Research, 23(1 (6(1))6248666) 66296, 2022.
[30] Simon Du, Sham Kakade, Jason Lee, Shachar Lovett, Gaurav Mahajan, Wen Sun, and Ruosong Wang. Bilinear classes: A structural framework for provable generalization in rl. In International Conference on Machine Learning, pages 2826-2836. PMLR, 2021.
[31] Dylan J Foster, Sham M Kakade, Jian Qian, and Alexander Rakhlin. The statistical complexity of interactive decision making. arXiv preprint arXiv:2112.1343 2021.
[32] Zixiang Chen, Chris Junchi Li, Angela Yuan, Quanquan Gu, and Michael I Jordan. A general framework for samplc-efficient function approximation in reinforcement learning, arXiv preprint urXiv:2209.16634 2022.
[33] Raman Mehra. Optimal input signals for parameter estimation in dynamic ristems-survee and new results. IEEE Transactions on Automatic Control, 19(6):753-768, 1974.
[34] László Gerencsér and Häkan Hjalmarsson. Adaptive input design in system identification. In Proceedings of the 44th IEEE Conference on Decision and Control, pages 4988 4993. IEEE, 2005.
[35] Dimitrios Katselis, Cristian R Rojas, Häkan Hjalmarsson, and Mats Bengtsson. Application- oriented finite sample experiment design: A semidefinite relaxation approach. IFAC Proceedings Volumes, 45(16): 1635-16666 2012.
[36] Ian R Manchester. Input design for system identification via convex relaxation. In 49th IEEE Conference on Decision and Control (CDC), pages 2041-2046. IEEE, 2010.
[37] Cristian R Rojas, James S Welsh, Graham @Goodwin, and Arie Feuer. Robust optimal experiment design for system identification. Automatica, 43(6):993-1008, 2007.
12

---

[38] Graham Clifford Goodwin and Robert L Payne. Dynamic system identification: experiment design and data analysis. Academic press, 1977.
[39] Kristian Lindqvist and Häkan Hjalmarsson. Identification for control: Adaptive input design using convex optimization. In Proceedings of the 40th IEEE Conference on Decision and Control (Cat. No. 01CH37228), volume 5, pages 4326-4331 IEFE, 2001.
[40] László Gerencsér, Jonas Mårtensson, and Håkan Hjalmarsson. Adaptive input design for arx systems. In 2007 European Control Conference (ECC), pages 5707-5714, IEFF, 2007.
[41] Grady Williams, Nolan Wagener, Brian Goldfain, Paul Drews, James M Rehg, Byron Boots, and Evangelos A Theodorou. Information theoretic mpe for model-based reinforcement learning. In 2017 IEEE International Conference on Robotics and Automation (ICRA), pages 1714-1721. IEEE, 2017.
[42] Guanya Shi, Wolfgang Hönig, Xichen Shi. Yisong Yue, and Soon-Jo Chung. Neural-swarm2: Planning and control of heterogeneous multirotor swarms using learned interactions. IEEE Transactions on Robotics, 38(2);003311073 2021.
[43] Alcksandr Aronovich Feldbaum. Dual control theory. i. Avtomatika Telemekhanika, 21(9): 1240-1249, 1960.
[44] Ali Mesbah. Stochastic model predictive control with active uncertainty learning: A survey dual control. Annual Reviews in Control, 45:107-117, 2018.
[45] Douglas A Bristow, Marina Tharayil, and Andrew G Alleyne. A survey of iterative learning control. IEEE control systems magazine, 26(3):96-114 114, 2006.
[46] Lukasz Kaiser, Mohammad Babaeizadeh, Piotr Milos, Blazej Osinski, Roy H Campbell, Konrad Czechowski, Dumitru Erhan, Chelsea Finn, Piotr Kozakowski, Sergey Levine, et al. Model- based reinforcement learning for atari. arXiv preprint 19XXvv:/003.0000 2019.
[47] Tianhe Yu, Garrett Thomas, Lantao Yu, Stefano Ermon, James Zou, Sergey Levine, Chelsea Finn, and Tengyu Ma. Mopo: Model-based offline policy optimization. Advances in Neural Information Processing Systems, 33: 11914122-1414,, 2020.
[48] Kurtland Chua, Roberto Calandra, Rowan McAllister, and Sergey Levine. Deep reinforcement learning in a handful of trials using probabilistic dynamics models. Advances in neural information processing systems, 31, 2018.
[49] Yashwanth Kumar Nakka, Anqi Liu, Guanya Shi, Anima Anandkumar, Yisong Yue, and Soon- Jo Chung. Chance-constrained trajectory optimization for safe exploration and learning of nonlinear systems. IEEE Robotics and Automation Letters, 6(2):389-396 2020.
[50] Ian Osband and Benjamin Van Roy. Model-based reinforcement learning and the eluder dimension. Advances in Neural Information Processing Systems, 27, 2014.
[51] Wen Sun, Nan Jiang, Akshay Krishnamurthy, Alekh Agarwal, and John Langford. Model-based rl in contextual decision processes: Pac bounds and exponential improvements over model-free approaches. In Conference on learning theory, pages 2898-2933. PMLR, 2019.
[52] Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with generative model is minimax optimal. In Conference on Learning Theory, pages 67-83. PMLR, 2020.
[53] Dongruo Zhou, Quanquan Gu, and Csaba Szepesvari. Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532-4576. PMLR, 2021.
[54] Andrea Zanette and Emma Brunskill. Tighter problem-dependdnt regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304-7312. PMLR, 2019.
13

---

[55] Mohammad Gheshlaghi Azar, lan Osband, and Rémi Munos. Minimax regret bounds for reinforcement learning. In International Conference Machine Learning, pages 263-272. PMLR, 2017.
[56] Andrew Wagenmaker and Kevin Jamieson. Instance-dependent near-optimal policy identifica- tion linear mdps via online experiment design. arXiv preprint arXiv:2207.02555, 2022.
[57] Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International Conference Machine Learning, pages 2681-2699 PMLR, 2019.
[58] Tom Zahavy, Brendan O'Donoghue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex mdps. Advances in Neural Information Processing Systems, 34:25746-25759, 2021.
[59] Andrew Wagenmaker and Aldo Pacchiano. Leveraging offline data in online reinforcement learning. arXiv preprint urXiv:2211.04972 2022.
[60] Jean Dieudonné. Foundations of modern analysis. Read Books Ltd, 2011.
[61] John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In International conference on machine learning, pages 1889-1897.
PMLR, 2015.
[62] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov, Proximal policy optimization algorithms. arXiv preprint 1YXiv:1707.06377 2017.
14

---

A Technical Tools
Additional Notation. We let Sd-1 refer to the unit ball in dimensions and S (resp. $44+ the of positive semi-definite matrices (resp. positive definite matrices) in Rdxd, Throughout, O(-) denotes standard big-O notation, O(-) hides additional logarithmic factors. poly(-) denotes some term that is polynomial in its arguments, with exponents absolute constants. Ax denotes the set of distributions over set X.
Lemma A.1. Let w, NNO,, la=) for all i 21,2.....7 Then,
]
E
Σ
|emil2
S n² poly(dz).
for e an absolute constant.
Proof. We first bound
Σ [1wel12) <n max 10: S n Σ w0:l1e
The result then follows since we can bound the B[[lw;]b s poly(d) for wn N( 7) and an absolute constant.
Lemma A.2 (Lemma 1.4 of [2]). Assume A, B E Sq Il BBBop I and c < Amiu (B). Then
|| B-1 llop S Amin (Aminn - e))
A.1 Martingale Regression in General Norms
For the following two results, we consider the martingale regression setting of [2] (referred to as the MDM setting). In particular, we consider observations of the form
3t (14" ze) W.,
(A.1)
for E R, unknown parameter μ¹ E Rd for filtration (Fi).21- This setting therefore encompasses general stochastic processes where the observations are linear-thl evolution of 2, could be arbitrary.
F VV and 2, F --masurrable
We consider the setting where we interact with (A.1) for steps, collecting observations ((Ee, Do) and then form the least-squares estimate of μ²:
Zelt..
We also denote Σr DT 2, The following results characterize the estimation error of çü in the M-norm and 2-norm.
Proposition (Theorem 7.2 of [2]). Fix any matrices 54H M s with M + O. Given parameter 8 E (0, 1/4), define the event
:
[] Illop S BAmin (T)}.
Then, if & holds, the the following holds with probability at least 1 - 6:
6d
| 1 1l < 5(1 +) on log
tr( tr(Mr-1
8
where Ç 26 Amax (T))
Proposition 4 (Lemma E. of [2]). On the event
Eop == {Amin Ex) 2 AT, Ex Tī+),
then we have that with probability at least 8:
log 1/6 + du + log det (TT/ / 1)
j 4=ll22 S C. ow
AT
15

---

A.1.1 Connection Between (1.1) and (A.1)
We will apply the results Proposition 3 and Proposition 4 in the setting of (1.1) in order to obtain estimation bounds on A.. As the setting (1.1) has vector observations, we briefly describe here how it can be mapped into the setting described above.
Recall that (1.1) evolves
Th+1 = A.o(Zn. un) + wh: h h H,
for æn E Rd=, o( u) E Rde, and A. E Rdaxda We assume that is some fixed starting state, Assume that we have run for T episodes, and collected observations {(o) ui, 22....., oy u/ 1))=- Now let μ* vec(A.). Furthermore, for any t, h, and i [dæ]. let t (t, h, i) and &, [O (l uh), Odo(da-s) E RRddd where Og denotes the zero vector of length d. Then we see that
[+)+ (n", z4) + J.
Setting y/: - -2> [1] and wi = [wfle it is clear that this follows the observation model (A.1) with dy dæd, and T d, T.. It is also straightforward to see that the measurability assumptions of the setting (A.1) are satisfied by this.
B Proof of Main Result
Algorithm 3 Optimal Exploration in Nonlinear Systems (Full Version of Algorithm 1)
1: inputs: number of episodes to run T, cost function (cost;) confidence 6, control policies II", exploration policies elexp
2: A + anything, fτ + [log2 T/8)
3: for L = 1, 3, ... lT do
4: + 2-, + 6
5: Compute estimate of cost matrix: Hy + H(A)
11. f- LEARNEXPI[(HH, Te, de, AR. leepp) (Algorithm 7). with AR the LC3 algorithm [17]
7: Rerun each policy in II, N₂- = [ times, denote collected data Dr
8:
Estimate system parameters
9:
A++1 arg min Σ
Σ
| AΦ( un)l
h=1 (2% (,
10: return का < T. (A
Theorem 4 (Full Version of Theorem 1). Assume Assumptions 1 to 5 and 13 hold. Then if
-1 T2 poly (do, dæ, H, BA, Br, Lo, La, Loost, La,, Twn T w x log F) .max {I, Food ro(A,)
(B.1)
with probability at least 8, Algorithm 3 plays exploration policies Tesp E Iexp at every episode, runs for at most T episodes, and the controller कo returned Algorithm 3 satisfies, with probability at least 1 8:
2 min tr (P((A))A1)) C AER
6d 8
Ouo T3/2
[ A.) J(T.
+
T
for C' universal constant and
Opoly == poly (do. de. H, BA, Bo, Ls. Lo, Loost Lu. Tw Tm 1 log T
Anan 8
Proof. Let & denote that the good event of Lemma holds at round which, by Lemma B.3, occurs with probability at least 6dg. By our setting of dg 8/ 8/12 we have that the total failure
16

---

probability of & for all e is bounded as
6 S 8. 12
8=1
Henceforth we assume that & = NgEe holds. Let À == A and Ā = Āt..
Before proceeding to the main proof, we note that the conclusion that Algorithm only explores with policies in ex follows from the definition of LEARNEXPII and LC Note that LEARNEXPII only interacts with (1.1) through calls to DYNAMICOED, which itself only interacts with (1.1) through calls to AR. instantiated in Algorithm 3 by LC Inspection of the LC algorithm in [17] reveals that LC only interacts with (1.1) by playing policies in Ieepp. from which the conclusion follows.
Bounding the Number of Episodes. Denote Toad [[Tg]- Note that by construction we always have NyIgra 2 Tg. By Lemma B.2, as long as (B.1) is met, we can bound the total number of episodes collected up and including round by 47, for l E (er, by - 1}- We therefore, in the following, will make use the fact that
e e- S N S .T
for E {er,eT - }} and absolute constants c, c' Furthermore, also follows from this that the total number of episodes run by Algorithm 3 is bounded by
T =
47 4. 2 flog T/8 <8
so Algorithm 3 runs for at most 7 episodes.
Approximating the Controller Loss. Let (A.) := min (1, reont (o.)),o(AA))) for Teost (A..)(A.)
as in Assumption and re (A.)) as Assumption 13. By Lemma D.2, under Assumptions 1, 2, 4, and 13, as long as E (AxA:i Test (oeest(AA)))))) (A+)), we have
I (ār: A.)
J ( (A.); A.) S [ A.)1
+ poly Lx., || Los Lo Loost, ow H, dz) || - -.p
Furthermore, we can bound
||voo(A A.)IBa((,) = ||vec(A (Ā ((Ā)) + veo(A - A.) (.)T((((A))) H(Ā ))voc(A (((A-))voc(A AA.)
< (Â- A.) H(A ) A.) + ||Ā A, IH(A.) H((A"))
Bounding the Hessian Estimation Error. On E, by Lemma B.3 and long (B.1) is met, have (note that the final epoch, the plug-in estimator H(ĀĀ) is given input DYNAMICOED):
|vve (Ā -A.) (- S
60
min tr (H((A-)A)) σ w AES
log
dd
Ne, Toed
poly da 1
1
Ter 8
BA, BΦ. log
H. [| lapp llllapploggg log
Ninia
N2,
C
min
(H(A (H((Ā-)A))
o log
6d
T
Agn
1
1
1
-poly
dø. day
BA. B log
H. [I log
Xiii
ow
7
where the last line uses that Ne, Tood is within a constant of T, and that Tood can be bounded by
-,BA Bs, log 1 -,, log T g ow
poly do dur Xmin
by Lemma B.3. By Lemma B.4 we can bound
((-) s min 2tr (H(AA)A-1) + dd |17((A.) -((-)))lo) Ilop
min Ae
AER
A
17

---

and by Lemma D.3, under Assumptions 2, 4, and 13, and as long as A E (est we can bound
(H(())) HH(A (A I polyyLLo, loop Lep, Lo, Leost Tw- (d, 11Ā Aallop.
Let
T
Clot po TIT.:
BA, BΦg Lup Lo, Least dæy dø.
ww. H, H1IiH((A)))opp log
X
denote some lower-order constant, whose precise polynomial dependence may change from line to line. On &, by Lemma B.3 we can bound
1
|| A. Aolo IĀ - -Allop S Ciot
(B.2)
VT
and assuming the burn-in (B.1) is met, bound || Aollop S (A.). This then implies that
A. llop S (A.) and ||
[P((A.) -((A-))lop S Clot
V
so in particular bound
1 -
7 8
poly
dos da;
BA, B H, log
[|7((A (llpppAp log
Xinin
Ow
s poly (dp dæs
BA. BB, H, log -1,1((,))) llop. log
1
T
Amin
Fw
We have therefore shown that
C T Aen
dd
J(Fr: A.) J(TT A.)
min (H(AA)AA1) oz log
8
Cio
||Ā--A11ă (IĀĀ- A.1 + +11
A+ 1
+ T +
1|
A_ Alpp
T
C
min (H(A.)A 2 log 6d
Clot
T
UEn
T3/2
The final result follows from using Lemma D.4 to bound
H(A.))l S poly((IA, Bg. L Lo, Lecor Len, o -1 H, dz).
Proof of Theorem 1. The proof of Theorem is identical that of Theorem the only difference being that we replace Assumption 13 with Assumption 6. However, by Proposition 6, the conditions of Assumption 13 are when Assumption holds.
B.1 Supporting Lemmas
Lemma B.l. Under Assumptions I and 3, the system (1.1) satisfies Assumptions 11 and 12 with
(b(T)= < Tap c
Φ(a u ( uF) D = HBH
1=1
de + dædæ, and where x (resp. UH)) denotes the state (resp. input) at step h of trajectory Furthermore, it satisfies Assumption 10 with AUR instantiated with the LC algorithm of [17] and
CR= CR CCH dx + BA) log(1 + BoH/ow), PR = 3/2, 1/2
for universal constant C.
18

---

Proof. That Assumption 12 is satisfied is immediate under Assumption 3. It is clear that (b(T) E
Sdedz, To obtain bound on D, we only need to bound the trace of (TT):
tr()((T))= Σ
tr tr( tr(((()), (.)) ux))
h=1
d
< dg H H
where the inequality holds under Assumption 1.
To show that Assumption 10 is satisfied in this setting, we have by Theorem 6 that with probability at least 1 5, LC has regret bounded as (using that Cmax I in the setting of Assumption 10):
1 () T log + B
Rr S C. H do (dæ + dr BA + log
for C' a universal constant. We can therefore take - 1/2, PR 3/2, and
CR= H do + de + Ba) -lg((1 + (Q/H/ww)
Lemma B.2. Let T3 denote the total number of episodes collected by Algorithm at round For
1 BA, BBg log
1 _
Ti 8
Te 2 poly (Lp. dm:
H, log
(B.3)
X
Tw
on the success event of Lemma B.3, we have 2T, 2 Tq and
21' Tp.
Proof. Recall that T, = 2 and N₂ TTo/To for Tood = [Tg. By Lemma B.3, T can be bounded as
T S NeTped + (16 + 2 log Toedyroed
and 7ped can be bounded
1 X
1
Te
Toed < poly
dop dn:
BA, BΦs log Tw
H, log
(B.4)
Note that we can bound
T, < N,Toed
+ (16 + log Tioed yroedy
< T. + (17 2og T,oed T,oed
< + poly
(op. dzy X
Ba, BB. log _ H, log
T
Oa
From this is immediately obvious that 27, 2 Tr as long as (B.3) is satisfied.
To show the second conclusion note that, by our choice of T; 24, we have that T₃ 2 E--1 T,, so therefore remains to show that
T, H, log
T M poly (ds. da Xim
BA. B log
ow
19

---

However, we can bound
1
1
Ti 8
1
1
Te
poly poly (o.
BA, Ba log
-
H, log
s poly dss. dx
BAi Bs, log
H. log
llog Tt.
Ain
Xmii
sufficient condition
Ti log Te
Te 2 poly
dep day Xmin BA, BΦb log
H. log
ow
which we see is met when (B.3) holds.
Lemma B.3. Consider running Algorithm 7 with weight matrix H. parameter N, and confidence and rerunning each policy in Hout N < N times. Then, under Assumptions 1 and 3, with probability at least 60:
60
6d
(voc(A-A.)113 I
min tr (HA-1)
o log
NTout
AER
8
1
BA BΦ log _
1
N
1
+ poly ds. dz:
H. 117lllop log
Xmiu
Tw
N22
where À denotes the least-squares estimate of A, obtained on the data generated by rerunning Tout- In addition, we have
dg. 1 _, BAr B ww H, log
N
AA-
A.IFF S poly
Xmin
Furthermore, we have
N
Tout S poly
dø, day
BA,
BΦ, log
log H.
X
Tw
5
and the total number of episodes collected by this procedure is bounded by NT + (16+2 (Tg((out))
Touts for Tout
[oont]
Proof. By Lemma B.I, the assumptions of Lemma C.6 and Lemma C.7 are met, so we can therefore apply these results in setting. By Lemma C.6. the event Exxp occurs with probability least 1 - 8. Throughout the remainder of the proof we union bound over the success event of Lemma C.7 and Eexp. which together occur with probability at least 45.
Let
NTou Σ
NTww
(TT))
Lde
Σ
bla), w/2f T
denote the features returned by rerunning every policy in Hou N times. By Lemma C.7, we then have that:
VT / /ddd log(1 + 8 oTuut) + 8 log 1/5
N Exeelon
d
Amin (N E Exeeoon An).
op
VN. 6272d log 68N
:9
Applying Proposition with E the event that the above conclusion holds and :==NN N. Ag. we obtain that, with probability at least 8 (using the mapping to the martingale regression setting described in Appendix 1.1.1):
6dgds
||vec A A.) < 5(1 + {) oh log
tT(HT-
8
20

---

for = 26/3²x Amax trr (T and 3 as defined above. Since || (( u) S B& under Assumption 1, we have || I B so we can upper bound Amax S NT Bdg By Lemma C.7, we can also bound (using that D d B by Lemma B.1):
Ir (r(T))) S N 6272d, log 68.
à
Combining these and using that
Tour S poly
dø, dzy
BA, BΦr log
H, log 8
(B.5)
X
as shown in Lemma C.8 (and using our bounds on CR and pR in Lemma B.1), we can therefore bound
log Ñ 1
Ç $ poly dp. dzy Xmii
BA, BΦ, log
H,
Tw
N
Using that tr(HI-1) < HPlpp tr(T-)), and the bound on tr(r-1) given above, it follows that
dd
BA, BA B log 1 H, |17| log
|[veo A A- -A < 50 w log
tr( + poly
dg. dea Xmin
8 N2
Finally, by Lemma C.7, we can bound
12
tr(HI
min tr(HA
NTou
AE
By Lemma C.8, we can bound the total number of episodes collected by Algorithm 7 by (16 2 log((To))) Toutt
Bound on Frobenius Norm Error. By Lemma C.7, we can lower bound
68N
Amni A) 2 N. 6272d H3 log
Furthermore, since [| 12]l2 < Bg, we always have | lop & NTout B², which implies Ä < NT B I. By Proposition 4, we then have that with probability least 1 - 8 (again using the mapping to the martingale regression setting described in Appendix A.1.1):
log 1/6 + dg ds + log det(
T
1 1+1 I)
6272d dg log 6aN
A AxIlF S C.aww
62722dd log
68A
N BA. B Rw, H, log
I poly do day Xii
8
VN
Lemma B.4. Under Assumption for any H. H'' we can bound
2d
min tr(AA -1) min 2tr Ä -1) Ags
176 H'llop-
Aes
A
Proof. We have
min tr(-A- = min tr (r(H'r Á -1 + tr - H''A-1) Ae
Aen
< min tr(H'A Á -1) + | H'llop tr -1) Agn
21

---

Under Assumption 3, we know that there exists some A E 52 such that Amin (A) 2 Min then bound
We can
min tr(H'A Aeo
+ || - H'llop tr(A
$ min tr À + 2 A + 11 Hlllop tr(( _ A + 12A+2A1
1 (\)=
min 2tr - + 2 Hollop dods Acf
Xmii
which proves the result.
C Experiment Design in Arbitrary Dynamical Systems
In this section we generalize somewhat the setting of Section 5. In particular, our goal will be to collect some set of trajectories D = {TT) which minimize
+b
(T.))
T
for some general feature mapping &b T + Rd + R R. and T (X U) x X the space of
possible state-input trajectories, т (oo, uo, 3t, 1H 11 E T. We will assume that tp can be decomposed additively
(TT) Σ (an,, un))
In Section 5 we considered the special case where (2, u) = Φ(x u)Φ(a, u) in this section tb> could instead be any arbitrary mapping.
As before, we will interested in defining optimal exploration with respect some of exploration policies, Texp- Let
2 == (ErrwW [ : w An}
denote the space of expected value of (bT) for mixtures of policies in Πexp- To distinguish elements E Ω from elements in Szp we will let r = [En
refer to elements of Sz, and in particular define Tx == E, (+]( (where it is assumed that the expectation is collected trajectories on (5.1)). will usually denote unnormalized sums features, e.g. Σ (TT)) with Σ. We also define 2z to be the space of all possible combinations of <b(T):
Kup == (+bT)( w E AT].
We generalize Assumption 7 and Assumption 8 as follows. Assumption (Regularity of 4). We make the following assumptions:
1. & is convex, differentiable, and 3-smooth in the norm || ||:
|V Vr. I B. - VT. e Q
for - the dual norm of ||
2. There exists some M < oo satisfying
sup sup | (Vr+(T), +(T)) M.
ref EET
Assumption 10 (Regret Minimization Oracle). Let costa (T) (Q 1/n. (T)) for some Qs. E Rdd, and cost(T) = =E (TS the total cost of trajectory T. We assume we have access to some learner P.R which, in the setting when (cost(T) < for all & E T, is able achieve low regret on {costa (-, H with respect to policy class eexp. That is, with probability at least 1 8:
T 8
Σ E f. [cost(T:)] T inf [cos(cs(( S CR log
#Ellosp
for some OR 0. pR 0. and (0, 1), and where ne is the policy AoR plays at episode t.
22

---

Algorithm 4 Dynamic Optimal Experiment Design (DYNAMICOED)
1: input: objective C number of episodes T (OR number of iterates N, episodes per iterate K), confidence 8, regret minimization algorithm AR. exploration policies exx
2: Play any policy Texp E eexp for K episodes, collect trajectories Do = {T) set To t
K K-1> k=1 (b(T))
.N do 3: for = 1, 2,..... ,,2,...,
4:
Set 7n a+I
5: Run AR on cost
1/ Enn (2 un)) for E. + vr
(T)
M
for K episodes, collect trajectories Dn = [T) denote policies run as II,
6: In < (1 In "n K
Σx K
k= (TTT))
7: return (N + 1)RTN. w. U Tn U 2
We define DYNAMICOED as in Algorithm 4. We then have the following generalization of T'eeoeem 3. Theorem (Full Version of Theorem 3). Let Assumption 7 hold, and assume that have access
1o a learner ARR satisfying Assumption 8. Fix N, K > O. Then, with probability at least 1 DYNAMICOED runs for most (N 1)K episodes, and collects dataset satisfying D
K (1 kJ Jmmi Ji satisfying
④
1
Σ
(T
min 4(T) I refl
BR N +1)
M
(CR logeR
2NK
K
K(N +1)
2(N + 1)
k=0k=1
8 Bogg4NN/0 (4N/6)
K
where R= su=.upr.ree - --
In this work we are particularly interested the case where (T) E Sh.. We encapsulate this the
following assumption.
Assumption 11 (Matrix Experiment Design). We assume that <b(T) S4 and that, for all I T.
tr({(TT)) D for some D > O.
The following corollary instantiates Theorem 3 under Assumption 11 with objective Φ(T) =
(H(T + =1)- the objective considered in Algorithm
Corollary 1. Consider the objective
TT = tr (H- (T
and assume that H > O and Assumption 10 holds with 1/2 and Assumption 11 holds. Fix N, K, let := (N + 1)K, and consider running Algorithm on this objective and with these choices of N and K. Then Algorithm 4 will run for at most T episodes, and, with probability at least 8, will return data satisfying
Σ (TTT) +TT.) )T) 1=1
17 [lp T 1l T(N +1)
tr 7
min tr (H(T + To) rele
+ +
T
SD
To 11a
(log 1/2 4r
+ CR log 27
8
TVK
C.1 Proof of Theorem 3 and Theorem 5
Lemma C.1 (Lemma C.1 of [56]). Consider rumning Algorithm with some convex function that is 3-smooth with respect some norm || assume that yn y for some y and all and let
23

---

Algorithm 5 Approximate Frank-Woie Wolfe
1: input: function to optimize number of iterations run N, starting iterate æ1
2: for -........ . do
3: Se n+1
4: Choose yn to be any point such that
(z((zn)
"
yn
min (z() yEZ
En
5: Rn+1 f- (1 zn Mn
6: return 2N+1
R = 2up2, y.zuyy ||= Ul1. Then for N 2 2, we huve
3R (log N +11
f(#N+1) min f(z) ZE2
N Σ En
2(N +1)
Lemma C.2 (Lemma C.2 of [56]). When running Algorithm 5, we have
N++
Σ
yn + z1
N+1
Proof of Theeormm 3. By our assumption on Ag, Assumption 8, we have that, at round n, with probability least 1 - 5/2N,
Ex [cost" S CR logeR 2NK
Exg [cost [cx)s"(TT)) K inf
K
a Elllop
8
where we have used that, under Assumption 9 and by the definition of cost % (T), /cost" (T) S for all E TT This implies that
1 K
2NK
I (b(+)) < M inf TETTex
Ex [cost((T)) + MCR log Ka-1
K
Furthermore, by Kauma-Hoeffding and under Assumption 9, we have that, with probability least 1 - 8/2N,
K
K
8M2 log(4N//6)
Σ E (Tx))
B I( (b(Tx))) S
K
K
K
1=1
k=1
This implies that
k
3log(4N/8)
Ba (T+)))
s M. inf E, [cost" (Coost((T]++ M. (C g
ka-1 +
K
"Ellow
K
(C.1)
Note that
= (V
and that for any I Rzp, we have
(T)(())r=r... D) Enow
for w. This implies that
inf renl
( = inf weAn
E (())))))))
inf Ex((En relloxp

---

M inf En (oost" (T)]. TElleap
By (C.1) above, we have that
1 K K
Σ (T{))
an approximate minimizer of M- sup eelles E [cost" (T)), with approximation tolerance
(CC log" R 2NK
Ka-1 + Blog((N/6)
We can therefore apply Lemma C.1 with
8
K
cn = M. CR log K -ka-k Ka-l+
8 log 4N/0)
to get that
3R N +1)
2NK
8 8log(4N/0)
min ((T)= - FEf
+ M.
CR logoR
Ka-1
10-1__ +
2(N +1
5
K
The result then follows since NN+1 K(N+I) En Ex= (T(T) by Lemma C.2.
Proof of Corollary 1. By Theorem 5, for any setting of N and K, we have that with probability at
least 1 8:
N
+ To )")
tr H K(N + 1)
3 (
min tr (H + 1t)
ren
n= 1=1
3R2 log N N+
MCR log
2NK
log AN
+
8
M
Kl-a
K
which implics
N ΣΣ
minres tr (H(T To) Io)-
H.
4b (T{ + T
T
312 log N T(N + 1)
MCr log 2NK
+ M 1
8 log 1N
TVK
T
K
This gives
K ΣΣ
minren Ur (H(T + -o)-1)
tr
H
( + TTo
T
===
3R2 log T
M(3log
1/2 3/ Cx logeR 2F
27
T(N +1)
TVK
It then remains to bound R, 3, and M. By Lemma D.6 of [56], we have that
Vr -tr (H(TT + -'(() To)-1) ro)-1)
We can then compute the second derivative as, using Lemma D.6 of [56]:
V( [ (H(T + r, - To + (T) {T)
=r (H(T + ro) - + ro)-
25

---

+ (H(T +o) -o) To) T(T + To) 1
Recall that M is any bound on
sup sup (T), reñ TET
By the above computation of the gradient, we can bound this as sup sup (Vr ((T))
< sup sup tr (H(T To)-~
ro)-
re tET
re TET
H op To ll
sup tr((b(T)
(C.2)
TET
s H| o 1
To bound 3, by the Mean Value Theorem suffices to bound the operator norm of VT. Using the expression above, bound this
sup (TT(D) ((T))) - 2// I 1op
sup tr(TT)
r.ee
llap.
Finally, it's straightforward to bound R < 2D. Putting all of this together gives the result.
C.2 Collecting Full-Rank Data
Algorithm 6 Minimum Eigenvalue Maximization (MINEIG)
1: input: scale N, confidence ò, regret minimization algorithm AR, exploration policies 1eexp
2: for 1, 3, do
T, ,8, 6 4: II + DYNAMICOED(&, N,. K, 85. AR. Ieep)) for 4(T) tr((T + Xラ 1) 1)
N, [2//37 K2 /22//3 + (N₃ 1) +
5: if "mmin (E,) 2 12544Ddz log (2+2332T,)
8 then
6: break
7:
return II,
In this section, consider the setting where (T) $ and our goal is collect {T,)²= such that ( Σ (b;)) > 0. For this to be achievable, we need the following assumption, generalization of Assumption
Assumption 12 (Full-Rank Data), Consider (b(T) such that <b(T) E sT.. Then we have supren, Amin (T) Niin some Xmna >
Throughout this section we also assume that Assumption 10 satisfied with a = 1/2 (though all results generalize in straightforward way for * 1/2). We have the following result.
Lemma C.3. Under Assumptions 10 to 12, running Algorithm 6 we have that with probability at least 1 8, it will terminate after collecting at most
N
poly
dap. X
D, Cr, log
8
episodes, and return policy set II such that
68.V
Amin (ETENTT) 2 6272ndd log
Furthermore, if we rerun each policy in once, the resulting features Σ will satisfy, with probability at least 1 - 8/N:
68.N
Amin EΣ) 2 6272Dd log
26

---

Proof. By Lemma C.4 and our choice of N, and K3 in Algorithm 6, we have that if X, S
Aiii and ddg.
TJ'S 2 σ (7"2ã((2)) ((D((A((D2)5' + OR log )/
Xmin
(C.3)
dep
then Amin (Ee)
Amin 4
Tÿ with probability at least 8y. It follows that, with probability least
- 6g. the if statement on Line will be true once X3 S 22."
Amin (C.3) holds, and
min 4d
22 + 327,)
T₁ 2 12544Ddb log
(C.4)
By our choice of X = = T
a sufficient condition to ensure X
Amin Idw
(C.3), and (C.4)
{
dep min
D*AAiin dx
)
6 (DCR log
X
9/2
Dd
NT,
T, 2 Ω max
log
6y
dx
min
8
Since 7;= = [24/3] [221/3] [2), 4. 2/). ,, it follows that the if statement on Line 5 will be met after running for at most
max ( de Amin
DD*Miin) dx
min )
"(CC log
Xmii
9/2
Dd
N N 8 (C.5)
))
log
8, dx
Min
episodes.
By Lemma C.5, if Amin (E3) 12544Dd log 2N(2+32T,) and
all policies in Ιī then
will collect data Σ such that Amiu [ 2 Amin (E)) ). with probability at least 1 - 8/2N. As the statement on Line 5 will only be true once this met, follows that, with probability at least 1 - 8/2N, rerunning all policies in Il, once, we will collect data E which satisfies
Amin (x)) 2 Dd72 log 2N (2 + 32T,)
68N
Amnnn
N 6272Dd log 5
5
The lower bound on Amiu Exen Tx) follows analogously from Lemma C.5.
The result then follows noting that the failure probability of running DYNAMICOED at most
8
Σ
S 6/2.
4j Ø=1
C.2.1 Supporting Lemmas
Lemma C.4. Under Assumptions 10 to 12, consider running DYNAMICOED on the objective
+ TTD tr((T +
with N [21/3] - and T224/3 for some and Let (N +1K. Then if X
<
X
1dg
and
1/3 2 ā. "(DA->1D>>'' + Cr logeR po 1))
Xmin
(C.6)
dgz
with probability at least 1 1 8,
T
Amin
Σ (Ti))
X
4d
1=1
27

---

Proof. Applying Corollary 1 with H. = I and To = A I, we have that, with probability at least 1- 6:
)
-D1A-3
8DX 2 1/2 T
+ CR log 7) ))
Σ (TT)) +TX
S T
min refl
T(N +1)
TVK
1 min tr((T + +
24
240x 1/2 T 3 + C log ))
$ T
rEfl
T
T4/3
where the second inequality follows since
T= (2 [221/3] S ..2²
which implies N + [21/3] then we can bound
T / and K [226/3|] 72/3 T2/33/4//3 If satisfies (C.6),
2-
24DX (log 2/2 _ + CR logeR 4)
1 dpb
74/3
T4/3
T X
Furthermore, under Assumption there exists some r Sup such that r 2 Xmin I, so we can upper bound
de Mmn
min tr((T + A ( < TEn+
and we can lower bound
3 (T., (E +TX-1
tr
Amin (E (b(T)) + +TX
Thus.
2cle
I
T TXinn TX.
v T
Amin
Σ (b((T))
2
Amin Et (T())) + TA
X
2d
It follows that if X <
Aman Id
then we have
Amin Σ (TT))
TT.
A 4d
which proves the result.
Lemma C.5. Consider running some policies (NT) for Fear-measurable, and collecting "i= (b(T). Then under Assumption 11, as long
covariance Ex =E
Amin (Er) 2 12544Dd log 2 32T
5
with probability at least 1 5, if we rerun each ( TT will collect features Ey such that
1
Amiu (Ex)
2
Furthermore,
Amiu Σ
r
Amiu (Er)-
nr
Proof. This follows from applying Lemma D.7 of [56] to the matrix 1 Er. Note that while [56] considers the setting of linear MDPs, the proof of Lemma D.7 of [56] does not make use of the linear MDP assumption, and the proof therefore extends immediately though it is not explicitly stated, the lower bound on Xmin ( Tr.) also proved in Lemma D.7 of [56].
our setting. Furthermore.
D
28

---

Algorithm 7 Learn Minimizing Exploration Policies (LEARNEXPII)
1: input: H. iterates bound N, confidence 6, regrer minimization algorithm AR. exploration policies Ilexp
2: for i = 1, .... do
3: N; f [2 K; f- /22 + (N, + 1)K,, + 8/41²
4: MIMIEIG f- MINEIG (NT, 5,, AR. Ieep))
5: Run policies in MINENI [T:/[LMEEEE times, set T to collected features
6:
((T) + tr(H + T;
7:
Ti H <- DYNAMICOED((,, N,, K2, 6, AR. lex))
8:
if
max j=1...
MINEROl ST
(C.7)
16D4 17 (I; - 1lop
16D (T, (r)0=1101100
(log 1/2 47's CR log 27'
(log'
S tr
H
(T fw + +1a)
+(NN+11)
T TiVK;
(C.8)
lr(H)- DT/ Sdw log(1 8//TT)) llg 1/6
S H (Ti + rr) -
Amia (Ti + r%)
(C.9)
1
Dv DV2T.V 8dw log 2T,) 8 log 1/8 S Amin (Iiw + IT)
(C.10)
9: then
Tout f I Fw + To Hout +- MINNEIG U (u TT/ Hassenlll (1wp))
10:
return out, Hout
C.3
Rerunning Policies
In this section, we build on the analysis of the DYNAMICŌED algorithm to show that, not only do the features collected by DYNAMICOED approximately minimize h; but that, under certain conditions, if we rerun the policies that DYNAMICOED ran to collect this data, we will collect a new set of features which also approximately minimizes Q.
In particular, we specialize this argument to objectives of the form 4(T) tr(HT-1). LEARNEXPII (Algorithm proceeds by first calling MINEIG collect full-rank data, using this data regularizer of (TT), and the rumning DYM on this objective. After meeting certain termination criteria, it terminates, and returns the policies has run over its operation.
Lemma C.6. Let Exxp denote the event that, for all 1,2, 3....... the success event of MINEIG and DYNAMICOED occur, and
68N
Amin (T)) 2 [T:/| [T 11 . 62222Dd log
Then if Assumptions 10 12 hold. P[Eexp] 2 8.
Lemma C.7. Consider rerunning each policy in Tout < Ñ times, and let I denote the obtained features. Then, if Assumptions 10 12 hold, with probability least 1 36, the event Exxp:
VTout Vod log(1 + 8/NT out log 1/5
F - N Σ FE Ix op
Amin (N ExeT Px)
VN. 6272d log 68N
(C.11)
68N
N 6272Ddd log
< min (Amin (N. Exelloo PT) Amin A
(C.12)
5
and
tr H (x)
1
<
12
min tr (HT-1)
(C.13)
Tout
ren
29

---

for Tout = [out
Lemma C.8. On the event Exxp, under Assumptions 10 to 12, we can bound
1
N
Tout poly de. D, CR. log
Xmin
Furthermore, the total number of episodes collected by Algorithm 7 bounded by (16+ Tout-
C.3.1 Supporting Lemmas and Proofs
Lemma C.9. Under Assumption for any r = Brow (T) and H. 2 0 we can bound
tr(HT D-1 tr(H))
Proof. By Von Neumann's Trace Inequality we can lower bound
tr(H(-1) 2 A tr(H)) || - tr(H).
By our assumption that tr( (T())(T)) S D, we can bound ||]|lop S D. which proves the result.
Lemma C.10. Assume tr (T(((T)) S for Let I denote the timennommllied features obtained by playing policies { 1= where Ta is 77--1-measurabl Then, with probability at least 1 5,
1R
8dg log(1 8VK) + 8 log 1/6
Σ
TK
s DV
K
K
Proof. This follows from an argument identical to the proof of Lemma C.4 of [56]. While [56] considers the setting of linear MDPs, we note that the proof of Lemma C.4 of [56] nowhere relies on the linear MDP assumption. The result stated here then follows identically as Lemma C.4 of [56], after normalizing <b( by D.
Proof of Lemma C.6. By Lemma C.3, the failure probability of running MINEIG round is 5, = 55/822 and by Corollary the failure probability of DYNAMICOED at round i also bounded by 6/862. It follows that the total failure probability of running MINEIG and DYNAMICOED is bounded by
5
S
812
2
Furthermore, by Lemma C.3, have that rerunning all policies in IT MINEIG will obtain features satisfying, with probability least 5 NT,
68N
Amin (T) 2 6272Dd log
6
Repeating this
times and union bounding, we have that
68N
Amin (T)) Z TT -6272Ddd log
8,
with probability at least 5/NT.. [T:/ MINEIG 11 2 5/Ñ.
Proof of Lemma C.7. Let IMIEEE:; To. Ir Fiw Fo denote the policies and features obtained on round at which Algorithm 7 terminates. Let Tiw Is denote the number of episodes of DYNAMI- cOED on the terminating round, and New: Kiw the corresponding values of N; and Kü- Throughout the proof we make use of the fact that at termination of Algorithm 7, all of (C.7)-(C.10) are met.
30

---

Proof of (C.11) and (C.12), By Lemma C.10 we have that, with probability at least 1 - 8:
N. N-N-ExeT F
DDVNTou V 8dg log + 8V NToww) + 8 log 1/6.
On Eexp, by Lemma C.3, we can bound
1 _ CR, log dep
NT
M S poly
Xmii
8
and, furthermore, we can lower bound
68.N
Amin (ErEThaNaa ra) 2 6272Ddw log
Since MINEIG C Tout. it follows that
68.V
Amin (N Ex N 6272Dd log
Combining these, we therefore have that, with probability at least 1 - 6:
VNTou
Sdup log(1 + 8v NT ouut) + 8 log 1/6
Î - N. Ex I Ix
Amin (N Evellome Ix)
N- 6272d log 08.
In addition, also by Lemma C.3, we have that with probability at least 1 8/ NT N2 2 1 1 6, that
68.V
Amin (T) 2 N 6272 log
Proof of (C.13). By Corollary on Exxp we have that:
((Tiw) = ir HH (Ttw + +ro) -ro)- minrea tr (H(T
Ti TT'' rT)=1)
Tiw
8D* |7|1lpp1 (Trw To) -11
8DI1 (T fw
To) 1 (log'
1/2 1h T / Km
8 + Cx log
27w
8
+
Tew (New + +)
Since Tiw satisfies (C.8), we can bound
8D* Fw ( -113 Tiw (Ntw + 1) + sD]iH (T) -1 (log' 1/2 1h b Tiw Ktw
Cn log
2im
S + (Tt)).
2
follows that
(T tw) minrea tr (H(T + To)
(T
The
2
(T )w) 2 minren tr (H(T + T ro)-1)
(C.14)
Tew
By Lemma C.10, we have that, with probability at least
6:
Eremoo Tx (Tiw 1l)plopp < Tou 8chp log(1 8 Tous) + 8 llog 1/0.
Since (C. satisfied and [ Ti, we have
DV/Tout v 8dv log(1 8 + 8 log 1/8 < Amin (Itw + To).
By Lemma A.2 it follows that
(EmEll.n) rElloa [z)
(
Fv + Po) -1
S DV out 8dyp log(1 + 8 Tout) + 8 log 1/8-
2 Amin (Trv fw To)²
31

---

This implies that
tr H (E Fx)
s tr H (T + +To)
2 Amin (Tir fw + To)
+ +tr(H)) D Do V 8dw log(1 + 8 + 8log 1/6.
Now if
ir(H). DV Tout DyTout V Sdup log(1 / + 8 log 1/6
2 Amin (Ttw + ro)
S lr H (I + -))=
(C.15)
can bound this all by
I 2tr (T + To) ro)-
minn tr (PL(T + Tww TT ren
Tww
where the last inequality follows from (C.14). However, note that (C.15) since (C.9) holds. Finally, note that
Tout Tiw + [Tt// MINEII MIIe S 2T [[ S 3Tw
where the last inequality follows since (C.7) holds. We can therefore upper bound Putting this together proves the result.
4 Tew
S
Tous
12
Proof of Lemma C.8. To bound Tout, it suffices to show that (C.7)-(C.10) are satisfied for sufficiently large T,.
On Eexp. by Lemma C.3, we can bound
NT:
MINeral S poly
dy. X
D, log
so ensure (C.7) is met suffices that
N deb. 1..D D. CR logo
1,D,
T; 2 poly
Xmin
On Eexp, we have
68NV
Amin (T) tvr + 1b) 2 Amin (Tt) 2 MTNtall
6272Ddd log
Which also implies
[1T, (T6) llop Auiin (T))
T
T
MINERG
(T: IT M
6272Dd log 68N
Dd72 log 5
68
Furthermore, by Lemma C.9 we can lower bound
Ir H (Tiw + 1o) -1)
tr(H)
tr(H)
D(T, + IT
3DT,
Combining these and using that N; - 13 and K; -((, it easy see that (C.8)-C..10) will be met once
N
T. > poly
dep X
D. CR, 1og
8
The bound on Tout then follows since 7, = / |22/3 E [2 29), so can at most constant larger than the sufficient condition before terminating.
32

---

Let i* denote the round that Algorithm terminates on. Note that at round i, MINEIG runs for most MInicIl. DYNAMICOED runs for most T, episodes, and we run for an additional [T E MINEIG episodes on Line 5, In total, then, the number of episodes Algorithm runs for is bounded by
Σ (T. MINEGol
[T/ [ I I MINtsal 1) I "22er (T; +
II MINEra
I 16T,- +
I
MISEia
==1
where the last inequality follows since T; E [2 4. 2¹). Now note that, since Algorithm 7 only terminates once (C.7) is met, will have max MInnaal I T... This implies that
2 3Σ MINtio S T. < 2log(T;-) Tù.. Bounding Tę I Tout gives the result.
D Smooth Nonlinear Systems
In this section we restrict to the nonlinear regulator system of (1.1). Our goal will be to show that, under assumptions, the nonlinear regulator system exhibits certain smooth behavior. As we have assumed
II" (x O IR.)
will be convenient to define J(0; :) = ; and (A) = -.. For the remainder of this section, we will typically use 0 in place n In addition, when considering radius terms such as re() and Tcost (..,) (A.), simplify results this does not change the validity of the result since, for example, a result holds with E By (A.;r) for some
assume that ro (A.) < 1 and reost (co (A.) < 1. Note that
(A.), it also holds for A (A,A,rra) (A.)). Throughout this section, we let V=](<> A] refer to the directional gradient of ((x) in direction A.
We first have the following result, which shows that under our assumptions, the controller loss is differentiable.
Lemma D.1. Under Assumptions 1, and 5. for any A satisfying A Be controller loss I J(;; A) is four-times differentiable in O and A. Furthermore, we can bound
the
V
A)llop S poly([IAllog) (llAll Bo, LG, Lo, Leost, ow H, dz))
for i,j E {0, 1,, 3,4]
4} satisfyyng iit 3.
In this section, we generalize Assumption 6 to the following.
Assumption 13. We assume there exists some re(A.) > such that, for all A E (p(A, O. (A) satisfies:
VeJ (0; (O;A)lo=z..a) =,
. 0. (A) is three-times differentiuble in A, and we can bound 1 (.()llop S Ln, for some Lx. > and i E 21.
The first condition requires that 0, (A) corresponds stationary point of the loss. This will be met, for example, by choosing (A) to be a minima (local or global) of J(0; A). is not obvious, however, that the first and second condition can be simultaneously satisfied. In the following that, assuming T(O: ; A. A-)le=e.(A, (A.) is full-rank (which will be the case, for example, when (A.) is a strict local minimum of [ AA)). there always exists some 0, (A) satisfying both conditions of Assumption 13, with L,, scaling polynomially
show
problem parameters, and ra (A.) scaling inverse polynomially in problem parameters. Note that this definition of π (A) is general enough to capture settings where the global minimum of J (T;; A) cannot be efficiently computed it suffices to take (A) local minimum of the loss.
33

---

Proposition 5. Assume that Assumptions 1, 2, 4 and 5 hold and that Amin ( 0. Let re(r)) > 0 be some value satisfying
Bg. Tup, T.g, Looorr Fw H, dze ]]
re().) min (roas PA.;
Amin A. o. 1|A.
Then there exists some funcciin (A(A) such that, for all A E Br (o
(eJ 0,
(A) is three-times differentiable A,
and it suffices that we take
Lr. poly Amin (VzJ (.) ||A, Ilop. B$, Lo Lo, Leests ow' H.H,d, dz
While Proposition shows that there exists some (A) satisfying Assumption 13, it does not directly give recipe for constructing such a map. The following result shows that under a mild additional assumption, the minimizer of the loss satisfies Assumption 13.
Proposition 6. Let
(A(A) == arg min [(0; A).
GERdo
Then under Assumptions 1, and 4 to 6, there exists some ro( > and Ls, < 00 such that O, (A) satisfies Assumption 13.
The scaling of L,, in Proposition can be shown match that of Proposition 5, but in general (A() could be smaller than the value of rA(A,) given in Proposition 5. In particular, in the setting Proposition 6, we can only show that re ro(A, (A.) scales with minggg: (A.):r) [O; A,) (O.()A)) A..): for some r 0 which scales inverse polynomially in problem parameters. While we can show that J(:; A.) ((.,(A.) A.) scales inverse polynomially in problem parameters, including in Amain (V)J A.)lo=0,(A)) for 0 approximately distance of r from 0. (A.)). is possible J(0; A.) has some local minimizer O' arbitrarily far away from 0. (A.),, such that J [('; A.) and (A.); A.) are arbitrarily close, in which case A", and therefore re re(A.), could be arbitrarily small. The failure mode here that, while (A.) may the global minimum of [O; A.), for A arbitrarily close to A., the global minimum of J [(0: A) could instead be near 0', which would render the map (A) discontinuous.
By making further assumptions on J(0: A.) which exclude this case, we can obtain a value of rA(A,) scaling similarly to in Proposition 5. For example, in the following, show that under the assumption that J (0; A) is convex, this holds.
Proposition 7. Assume that there exists some Tconv (A.) >>
O such that, for all A
Bp (A.; Toonv (A.)), [(; A) is convex in 0, and set
(A(A) = arg min J (0; A).
OERdo
Then we have that 0, satisfies Assumption 13 with
ro(A)) min Toonv (A.), (A.),
poly
A|Allopp BΦ, Les Lo, Leastt H, di
Amiu (aiia(V [i:T(: (0: o.(A)))
and it suffices that we take
Lr, = poly
Xmin (2: (0 ).()))) |A BΦ: Los Lo, Leasts o _0 H, du
Note that, if J(0; A) s-strongly convex in O for all near A., we can lower bound Amin (2J A. (lee)_ n.
34

---

Approximating the Controller Loss. In order to efficiently direct our exploration, it is convenient derive a quadratic approximation to the controller loss. The following result shows that, under our assumptions, this is indeed possible.
Lemma D.2 (Formal Version of Proposition 1). Under Assumptions 1, 2, and 13r A Bp (A,; min cost
we have
(A) A.) (A.): A.) s veo(A A.) H(A.)voc(A A.) MIA A,, A., A.).
for some tensor M such that
[|M[A - A., A- A., A A.lllop S poly(Lx. ||Aallop: BΦg Lop Lg, Leost, Tw H, dz) 1|Ā Al
In practice we do not know ((A)) and must estimate The following result shows that the distance between H(A.) and H(A) can be bounded.
Lemma D.3. Under Assumptions 1, 2, 4, 5 and 13, and if Ā Br (A,; min fress (A.), we can bound
[{{)))) - H(A))lop S (o,y(Lz,,) Alppp B Laz La, Lenst, ow H, dz) I - Axllop.
D.1 Proof of Smoothness of Nonlinear System
We let fw denote the density of the noise (which, by assumption, is simply an isotropic Gaussian density). We let (-) denote the density over trajectories induced by playing controller 0 on system A. We will overload notation somewhat and let (2 Tı:A) denote the density over Ih+I induced by playing controller 0 given trajectory Tish- Note that f..0 (2.0(
Ti:h)
fw (#n+1 ( R (T)))) and
H fA II (a.0 TTa). h=1
Throughout this section we let ax (resp. ( denote the state (resp. input) at step h of trajectory t. Under our regularity assumptions (Assumptions 2, and 5) and since the noise is Gaussian, we can swap derivatives and integrals, which we make use of throughout the following proofs.
Proof of Lemma D.I. Let cost(T) denote the cost of trajectory T. Then we have
J(0:A) cost(()ff..(T)dtt
/ and 0, = 0 5 53 + s3 for some A and A which we assume satisfy || loop: | llop S 1. Rather than differentiating J(0; A) with respect to A, we will differentiate J(0x; Ar) with respect to some T1, 33, 2i E (11, 12, l3, 81, 82, 83). Note that, for example,
Let Ae : A+t +t4 + t3
J(0,; A)) = VAJ(O, dt
ie. the directional gradient of J(, A) with respect to A in direction A and that this similarly holds for gradients with respect to other t,, $j, higher-order derivatives. Thus, if we show that J(e:: At) is differentiable with respect to any 21. F2, 2z, 24 E {t1, 12, t3. $1, $2, 83), and this holds for any choice of A Af. then we have that J@, A) four-times differentiable with respect to and A. Furthermore, we can bound the operator norm of JJJ(O, (O, by bounding the value of d
de, [(2;; At) t= for A satisfying | 1lop (and we can similarly bound the operator norm of the higher order derivatives of ((0, A)).
J(0; A) is Differentiable.
vs Let I1, 22, 24 E {tz, t2, t3, 81, $2, s3). We have
d dx J(0:: At) = dr, / cost(T)fA,.
35

---

/ (T) d
[A,O, dri doi S (T)cost(T)t
/ dr
log fs (T) (ott
Differentiating this gives
d
/ dri
d
[(0s: Ar)
log
S (T) cost(T)fA,,
dæg da
dr2
= / ((ar)
cdd log (Ac (t)
(1d, doz
log (nc
cost (,
dz
d d log Ssco, cost(t)/A,,,(())tt
+
dx dxi
and
d d
(L log (T)
(1d2_ log (A ( dwz
log (t) cost((T)A,, (T)dT
[(.:: At) =
dag dr2 dr
dri
drz
+
/ drg dæi
d d
log (
d do2
log (1)
-cos((T) (T)dk
+ / (drn log O (T)
d
d
d
log (T)
co
drg dus
+ / dag daz dri log fA (T)
+ /Ld d
log (A. (T)
(
dzs
d
log (A.
cost(T)/A (T)dT.
dx1 The fourth derivative of [0; A) can be similarly calculated by differentiating day dæs das J (0,; Ad); we omit for brevity. We have
d d d
H fA. (x TIn)
log f. (T) = log
II
h=1
H
log fw (x)++ A (T(a)))
h=1
Н
Σ
|
A n (TTSA))
20
h=1
w
some C which does not depend on or 8. Given that (xx, u) is four-times differentiable in w and 00 n (Tı:) ) is four-times diffcrentiable in æ (which hold by Assumption and Assumption 5), is clear that log fA. o, (T) is four-time tour-times differentiable f or s,, regardless of the choice of A or A This proves the first result.
Norm Bounds on Gradient.
Note that
H Σ
log fA. e, (T)lt=a=0
- A (T(T)))) (
dl,
h=1
H
d log ls (T) ds;
Σ
- AV AV (f V A.
h=1
Furthermore, differentiating these expressions further with respect to Lj or 8j will simply yield higher-order derivates of Φix u) and . (T):)). Using the norm bounds on the gradient of Φ(x, u) and of (TI:A) given in Assumption 4 and Assumption 5, and the norm bound of Φ(x, u) given in Assumption 1, we can then bound
| ( log) S Poly([ B&, Ls Lo. r
(1 > | Appx) = (T(:s))))
36

---

for i,j E 10,1,2,3,4 satisfying S Σ (where we have used the fact noted above that, to bound the operator of V V log (T), it suffices to bound the directional gradient in every direction). follows that we can bound
( J(0; A)llop
$ poly poly(1|Allop. BΦ, Lib Lo, ow:) /
H E( + |0/+1 Ap(x7 of (TT))))))
cost(()ff.o())dr
poly plly(I|Allop. Bs, Lb Lo, ow²) // cost cost(()(fA.oT))))
V
"
Σ (1+ |,, A.p(2 o ( (TTTA))])
fA,o(T)dT
(
S (pol([I-Alopp.. Bø, Ls Lo. Leost, -1 H,d
where (a) follows from Sauchy-Schward and (b) follows from Lemma A.1 and Assumption 2, since we have assumed A E Bp (A;; Teost (A.)).
Proof of Proposition 5. Existence and Differentiability of 0.. By Lemma D.1 have that [(; 1) is four-times differentiable its arguments. By the Implicit Function Theorem, since Amin (V). (0; A.) 4.))0==.(4.)) > 0 by assumption, we have that there exists some (A.) > 0 and unique function 0- (A) defined Br(A,,;r (A.)) such that VoJ(0: (A) 0, and (A) three- ttree-times differentiable (note that, while the Implicit Function Theorem is typically stated to give that the resulting function is only one-time differentiable, can be extended k-times differentiable. assuming the implicit equation is k-times differentiable [60]).
By Lemma D.I and the continuity of eigenvalues, it follows that for A close enough to A., we We can therefore apply the Implicit Function Theorem above any A satisfying this, to get that there exists some unique (A') defined for all A' near A such that VoJ A')lo
have Amin ( V (0: A))o=o.(A)) 2 _ Amin ( (V)J (A)ooo (A.)) > )
(A7) 0 and (A') differentiable.
By the uniqueness of 0, (A) on Bp r', be identical to (A) on Bp (A.;r's (A.)) (assuming the regions which they are defined overlaps). We can therefore define (A) simply the extension of 0. (A) to all such (A)). defined for all and will have
follows that any 0. (.A') defined in this way must
A near A. such that Amiu (V). ( A)))-a 2 Aminn ( [V)J((: (0;AA)) 1.))lee..AA that 0, (A) is three-times differentiable and satisfies VoJ (0; A)le=o.(A) = for all such A.
We then choose (A.) to be defined such that, for all A E (r(AA:ro(A.). we have Xminn (V2 (V)J(( A)) 2 (V.. A.))o__,)))) By Lemma D.I, we know that (0; A) is continuous and furthermore we know that eigenvalues are continuous. Using the gradient bounds given in Lemma D.1 to bound the Lipschitz constant of V2J (0; A), it follows that we can take
1
(A,) poly
(V (V) ||A, BΦ. L Lo. Least: σe H, dz
Bounding Norm of Gradients. Fix A (p(A,, We know that 0. (A) satisfies
VoJ A)e = 0.
We wish to differentiate (A) with respect to A, and bound the magnitude of up to the third derivative. Similar to the proof of Lemma D.I, we let A, := A + t + tz + ts for some A A satisfying llop E 1. As noted in the proof of Lemma D.I, we have
d 0. (Ao) AAO,(A)AAA) dl
37

---

(and similarly for higher-order derivatives). Thus, to show the result, it suffices to show that 0. (A4) differentiable in E &2, t3 for all 4 and bound the magnitude of this derivative for all A with || llop 1. We have
d dt
VoJ(O; Aa) -00
V VATo/0--)00ora...e::: - =0 (D.1)
VA0.(A)AAN
-0((1,14)
which implies
Gi
which is well-defined since we have assumed that V (0: (0:A))o0) (4) is full-rank, and J is differen- tiable in both its arguments by Lemma D.I. To compute the second derivative of 0., differentiate through (D.1) which gives
( VAO.(A))AA)) Ie-o
dt²
d
(Gi A VOJ(0; Ac)lo=0.(A) (xO,(A)(A(]) 10-0
dl2
=GG(AAAAA))
+ (0: (A)AA A =0
Note that G2 (2,A,44 A A involves most a third-order derivative of I [(:: A) and first-order deriva- tive of 0, (A), both of which we know exist by Lemma D.I and what we showed above. This then further implies
0.)(AA) A -V (00:00:))eela ()) (12),,
which well-defined since we have assumed that ()) (a) is full-rank. Finally, we compute
dt3 (G2(A,, ( (2 A31) I
d dlg
(G2(Ar, 41 A V (A)(A) A1I) 1
(0: A)la A)) (,(A) (A)A(A AS =
Note that G3 A, A4 A involves at most a fourth-order derivative of [0; and second- order derivative of 0, (A), both of which we know exist by Lemma D.1 and what we showed above. We therefore have
V ( A - A)loo..aa)) G2(A, A A4 Ag
which is well-defined since have assumed that VīJ A)le=a.(A) is full-rank. As each of these expressions is defined for choice of A,, the differentiabillty of (A)) follows.
Note that the above expressions for VA0.(A)AT1) V 0, (A)A Ad), and 3 (A) A$. Ag all depend on at most fourth derivative of J(0: A), as well as (V (0; ())) The norm bounds are then a direct consequence of Lemma D.I.
Proof of Proposition 6. By Lemma D.1 we have that J J(0: A) four-times differentiable in its arguments. Since we have assumed ViJ A.) a. (A,) ) > 0, by the Implicit Function Theorem o.
[60], follows that there exists some r'p > and mapping ((A) such that, for all A E (F(A,: V ToJ(0: A) ((A)))) = 0, and ((A) is three-times differentiable.
38

---

Our goal is now to show that ((4) (A) for A close enough to A.. By the continuity of eigenval- ues, [o; A), and (A),, have that there exists some and r such that, for all 0 (0.()))) and (A.,)))), we have (0 > and, furthermore, ((A) E (A. (A.):r/2) for all A E (p This implies that 0 (AA) is strict local minimum of J [0; A) and, in particular, that
J(0:A) > A()(A):A), A0 E (2(0.(A.)::) 0 ((4).
Let A == (0. J (0: J(O. (A.); A.) and note that, since we have assumed the global minimum of [(;;A, is unique, we have A > 0.
Fix some A E (A.,rr)) and assume that ((A) is not the global minimum of A():A). This implies that (A). the global minimum of J (0; A), is outside of (2(0. (A.);r). Furthermore, by the continuity of [(; A), we have, for some L, L' > 0,
J(0. (A); A.) (A): + LIIA - A.IIF
4 - A.IIF
$ +)2 A.lE
41))(()))))))+ A. ||F + L|0((A) (A(A.ll2
$ (J((((A): A.IIF
This implies that
1/ 2 T | A.I1r
However, for r small enough, this is contradiction. Thus, it follows that ((A) is the global minimum of J(0; A), so (.A) = (A).
The result then follows since we already have that (AA) is three-times differentiable and satisfies VoJ(O; A) A) 0, and by taking re(A.) be the minimum of r' and r" The boundedness of T.,, follows as in the proof of Proposition 5.
Proof of Proposition 7. Note that, by convexity and the KKT conditions, the solutions to arg mingeet J(0: A) are described by
VoJ A) ()) =0
Thus, an equivalent definition for O,(A) is that it satisfies VoJ A)le=0 0. Assumption 13 then be shown hold by argument analogous Proposition 5.
Proof of Lemma D.2. Let A(t) tă (1-t)A, and g(t) = (A()() By Lemma D.1 and under Assumption 5, we have that both J(0; A) and (A) are three-times differentiable for all A = t + (1 t). [0, 1], so it follows that g(f) is three- times differentiable in t. We can therefore apply Taylor's Theorem to expand g(1) about the point = to get:
(1) (() VoJ
(A) [ A.) VAOA(A)IT=A, (2J V
[ AA, A.]
VoJ (O.. A. A.)l -- A.]
(A)( A., A..A-AA) A.]
where A' = A(t') for some e' E [o, 1]. Under Assumption 13, we have that [oJ(0:AA))o-o.(4.) 0. which implies that, plugging in the definition of g()) and ((),
I(O,(A); A.) (O, V.O. VĀJ A.) (-.. (AO (AO((A))A-A) Ao, -.AA-A. A.) (A)
A., A. A-..AAA. A.A.).
39

---

We can bound
(A)) (A (AAA,A,. A., A,,-A
A. (V) llop - -|Á-- 1.1-A.10 A.llop
The expression for (A A.) contains up to the third derivative of both [(:: A,) and (A).. By Lemma D.I and under Assumption 13, since A' E (A, minfrroo (A, ro (A,)) by construction, we can then bound
(O., A.) poly(L.. || lopps Bø. Lo Lo. Loost 0 H. dz).. The result follows by the definition of H(AA).
Proof of Lemma D.3. Recall that H((A (O)) To prove this, we will use that this is differentiable by Lemma D.I, and will apply Taylor's Theorem.
First, note that by Taylor's Theorem we have
(O. A) A=A JO. (A); V.A.A.+VVJJO (O): A= -AJ]
for A' = + +1 t)A, for some E [0, 1]. The third derivative (A)) A) will involve up to the third derivative of both J(0; A) and 0. so using Lemma D.1 and Assumption 13, since bound
A' (A, min (A.),, ro())) by assumption,
T (A); A
a I4 A.lloop poly ||A, lop. BØg L Lg. Leost; 0 1 H, dz) I| A, llopp-
Next, we wish to relate (O.( A) to (0, A-) =((A)). Again apply- ing Taylor's Theorem, we have
(O,,((A) A) A- = (A): + V (4), (A))
A.]
for A" = t. + (1 t) for some E [0, 1]. By Lemma D.I and Assumption 13, we can bound
V A ((1
A.lloap
S poly 11 Alppp Lsp, Lo, Lucost owl H, d=) 1| A.llop-
The result follows.
Lemma D.4. Under Assumptions 1, and 13, for all A Bp(A,; min (A.), we can bound
[H(A))lop S polly(1A..lop. BB, T.p: L.g Tecst; Tix,, ow H, dz)
Proof. Recall that H(Ā) = (A) The bound then follows from Lemma D.1 and Assumption 13.
E High-Probability Regret Bounds in Nonlinear Systems
In this section, we modify the proof the main result of [17] slightly to show a high probability regret bound for LC For the sake of brevity, we omit details that are identical to the proof given in [17]. We will need the following assumption.
Assumption 14 (Bounded Cost). We assume that, for all trajectories
have cost(T) S Cmaax-
We adopt the notation used in this work, modifying somewhat the notation from [17]. particular, we let (nT; A) denote the expected cost of playing policy under system A, and we set
H
Σ M
(lx), (/) TT + Al
h=1
denote the covariates obtained by the first episodes of LC3 (plus a regularizer). We let x denote the policy played at episode i of 3C3, For policy set II, we define regret as
T
R = Σ
J(T;; A.) min I J(;; A.). xell
1=1
40

---

We will also denote π. := arg min, rent I (T; A.). In addition to these notational changes, we modity LC slightly to use the parameter
0 VABA Sd log log(( det( det (ee((2o)-1/0
in the construction of the confidence set, BALL".
Besides the aforementioned changes, in the following proofs adopt the same notation as [17]. We have the following result.
Theorem Under Assumptions and 14 and with any policy class 11, with probability at least
LC has regret bounded as
(II I C. Crax v ds (d4 + de + Ba + log 1 () T log (1 + B&HT
for a universal constant
Proof of Theorem 6. By Lemma E.2, we have that the event & holds with probability at least 1 8. We therefore assume ε holds for the remainder of the proof.
By the definition of the confidence set LC3, on & we have that A, the confidence set for all t < T. It follows that E1.
RT -
I (17:AA) - J(TT;AA))
H
I(A, - -A)) Φ( un un)1l, 1
Cmax EA..
Σ
min
(E.1)
Ow
where (a) follows from the optimistic property of LC3 when A, E BALL', and (b) follows from
Lemma E. On E,, have
[I(A. - A' ( un 122 I |I(A, - A 1/2 E 1/2 (0 un)lle
- (I(AA, - A') /2 + (1 A')=\/²112) |E, 1/2
1/,,122 (xx,, unlll
- 10 un x
where the last inequality follows from the definition of BALL since A' E BALL by construction. and by the definition of E, This gives
(E.1) S Gmax EA,, mr
Σ min
2 ow
[ un 1n
By Lemma E.3, with probability we can bound this as
20max 3
T
Σ min (1obat) u/))l l i, 11] + +40max H. V log 1/5.
Tar
t=1
h=1
(a)
By we can bound (a) as
(a) <
20max
3T
VT
min {106a1 u
Tw
41

---

We have
H
T
H
min | u w
H <
Σ min
p u 1
< 2H log(det( Er) det Eo)
where the last inequality uses Lemma B.6 of [17]. Putting all of this together, we have shown that with probability at least 26, we have
2Cmax B"
Rx <
VT- /2H log(del (Eo) + 4cmax H V log 1/6.
Ow
It remains to bound 8 and log(det(Eg) det (ee((E)))) We have Eg AI, (Eo) Ado Furthermore, if | u)ll2 < Bg. then we can bound (ET) I (A + H) de Putting this logether we have
dett) - de log(1 + T//H/
Recalling that
B VABA + ow V 8d log 5+ + log(( det [T) det (2o)-1/))
we can similarly bound
/ow S VABA/ow + / /dd log + 8ds log(1 B3TH/X) log (Tg(
I VABA/ow + o + do log(1 + B&TH/A) - log 1/5.
Choosing À A= o completes the proof.
E.1
Supporting Lemmas
Lemma E.1. Under Assumption 14, we can bound
A) un un)ll2 }}
- Cmax BA.s
Σ
min
Il
-
Fw
Proof. Following the proof of Lemma B.3 of [17], and adopting the same notation, we have
[IKK A) un un)lla }}
A A) S
Σ BA,.
VA,
min
ow
h=1
Under Assumption 14 have A₂ S cmax. Plugging this in gives the result.
Lemma E.2. Let B == VAB+tou v 8dz log 5 + 8 logg(T det(E,) det (o)) Eo)-1/8) and let E denote the event
E : vt ST
A.) Σ 1/2
S 8d
Then running LC we have PA, [&] 2 1 1 8.
Proof. The proof of Lemma B.5 of [17) shows that with probability at least - 6,
(A) A.) |!/²| < <'lllAullop + ow v Sdg log + 8 log(det(E,) det
The result then follows from this, since ||A, llopp S BA. and union bound.
42

---

Lemma E.3. With probability 1 - 6, we have
H
2
28 T
BA..
min
1 un
WAll
min
{lo u uhlll,
Fm
Oa
+ 4H V log 1/6.
Proof.
This
is
an
immediate
consequence
Azuma-Hoefiding
since
Ekmn min on ( un un)lx,,1, 1 x H almost surely, and from upper bounding
28
20 min-
| u/)ll ..1]
2,T*
min {10(1)) u wHll,,,
Fu
Lower Bounds on Learning in Nonlinear Systems
In this section, we assume that 0, and T. correspond the global minimizer:
(A)) == arg min J(; Tr (A) == arg min [(;; A).
(F.1)
BER
Here we formally state the additional assumptions needed in Section 4.2, and provide formal version of Theorem
Assumption 15. There exists some Ty (A.) 0 such that, for all A E (p(A.. n. (A) is
unique and, furthermore, there exists some p > O such that
2 A) + 0 0 (A)I12
Assumption 15 will be satisfied cases where " A) is strongly convex in 0, but may hold even when this is not the case. Intuitively, it requires that our controller class is not overparameterized moving 0 away from optimal value will cause the loss to increase. We will additionally make the following regularity assumptions policies in Heep and their induced covariates set, Ω.
Assumption 16. There exists some À 0 such that, for each A Ω have Amin (A) A
Assumption 16 requires that every exploration policy we consider excites all directions in Φ space (in contrast, Assumption only assumes there exists some distribution over policies in Πexp which excite all directions). We remark that this assumption is relatively mild if Assumption 3 holds. As we show in Appendix C.2, under Assumption 3, mixture can be learned using only a number of samples scaling polynomially in problem parameters. Given w, policy class Hexp satisfying Assumption can be obtained by simply mixing with every other exploration policy. We are now ready to state our main lower bound.
policies, w, satisfying Amii [A,
Theorem 7 (Formal Version of Theorem 2). Under Assumptions 1, 2, 4. 5, 13, 15 and 16 and if m. is defined as (F.1), long as T Cib. for any wexp E Allep we have
o2
Clb T5/4
min max EDT A, ( J (A); (A:: AEBT
min tr tr(H(A,)AA-) Aen
3T
for Br : (A |A- A. < 5d (2d,TH) Egy~A [.] Exwassp ED A. [:11 denotes the expectation trajectories generated by running policies drawn according to Wexp on system for T episodes, any mapping from observations to policies in II", and
Ob. = :-y (do) du. H, ||A, lops B&g Los Lo. Least LT, o
X ( Pooa(A) (a(A.) vo(A))
Proof of Theorem 7. This proof follows immediately from Lemma F.I, by lower bounding the right- hand side of (F.2) by the min over all policies in II.
D
43

---

Lemma F.1. Under Assumptions 2. 5, 13, 15 and 16 and i is defined as in (F.1), as long as T poly(llA, Les, Lo, Lmw, Leces: Ow, ow Bs. H, dæ dø A ,1 11 Foost ro(A) (x(A))))
for any Wexp An, we have
- min max EDynAwap -(00)))))0000000000)000)000)0000
o trrHH(A.)
grwweep (d11
Cıb
0 AEB
37
T
(F.2)
for BT = (A : s SSdadd/(TTH)rpg where E A.iupp Exxwis D [:]l denotes the expectation over trajectories generated by running policies drawn according wexp on system forrr T episodes, and
Cbb = --ppoollAA.llee. Lo. Le. Lu, Leost, ow: Tw BB. H, dæ do A 1 Feost Feost((A)) (A.)),re(AA))" (A((s)))
Proof. This result is a direct consequence of Theorem 6.1 of [2]-to to obtain the result we must only verify that the assumptions of this result are met. We verify each assumption below.
Verifying Assumption 3 of [2]. Part I of Assumption 3 of [2] is met by Assumption 15 within diameter r. (A.). Furthermore, under Assumptions additional parts of Assumption of [2] are also met with diameter min(T (A.), (A,)) and smoothness constant poly (4 A+lpp T.p, L.o, Ti Teesst ow H, dz))
2, 4, and 13 and by Lemma D.I, the
Verifying Assumption 4 and Assumption 5 of [2]. Assumption 4 of [2] is immediately met by Assumption 16. Furthermore, Assumption is met by Lemma F.2 with Coov = 1, Loov (0., 7²) H²
poly(da), and Ccov = 22
Given that these assumptions are met, the result follows noting that, we run for 7 episodes, then the
effective horizon is d (using the mapping from the setting of (1.1) to the martingale regression setting described in Appendix A.1.1). Note that the final bound scales with T instead и.TH as we
able bring the d factor into the A term, since Ageup is not normalized by dz O
Lemma F22. Under Assumption for any policy distribution w E A.oosp and A, A', we have
H²B
Eyow AA,z I Enow =
pollydd) ||A - AA'lpe Il I. o
Proof. We will prove that the desired bound follows for particular E Texps which immediately implies that it holds for w Anoop By definition we have
dww u (oo ()) mZ)T)
A
Σ h=1
. (T)(T
and
SA,
II
2h (T) a.))) fa(
h=1
Fix some v E -d and note that, given the expression above, we have
H
AAAU =
/
Σ
vv TTz
fax (T)dT.
h=1
It follows that
/ Σ
V V AA,
T xz Vafan(T)dr
1=1
44

---

Σ v
T
Φ( uz))² fAA((T) log fA, (T)dT.
As in the proof of Lemma D.I, we have, for any A,
Va log lo
Σ
(1)
Acp(a)) u A0(a7 u.),
h=1
so we can bound
BΦ H
V A log SA, (T)
Σ
1 A0pa0 22.
h=1
Furthermore, we can also bound (v Φ(2%, u2
B We therefore have
H
A ulop I HB
Σ
|
A0(2)) u2 fA,((T)
H B
(oly(dx)
du
where the last inequality follows from Lemma A.I. follows from the Mean Value Theorem that
H
AA - v A $
poly(dz)) ||A -A'lle ll
As this holds for all Sd-1, it follows that
H²
| Alooo S
pollydd)) ||- A'Ilr.
G Additional Experimental Details
In this section, we provide additional details on our experimental results presented in Section 6. All experiments were run on a machine with 56 Intel(R) Xeon(R) CPU ES-2690 v4 @ 2.60GHz CPUs, and 64GB RAM. All code was implemented in PyTorch.
G.1 Details Problem Settings and Controller Parameterizations
We first expand on the precise definitions of the systems considered. As noted in Section 6, for the drone and car examples we set // 50, and for the system of Section 1.1 for all examples the noise is distributed as wA ~ (00 0.1 1). In all cases we set 72 10/1 (where 7 is bound on Staep E h= u ux)). and therefore let Ieepp denote the set of all policies satisfying Egrepp |EA Uj un < 2
10. addition,
G.1.1 System of Section 1.1 (Figure 1)
The dynamics for this system are given by
10
3h+1 = 0.8 + un Σ (x)( W
1=1
for (x) = max 100(x c,)², and cost (t, u) = (x - c1)² + 10010 w². We set
10, 02 = 14, 11, 8, -5, Co 2,, e7 1, 4, 7.
This then corresponds to system in the form (1.1) with
A. [0.8, 1, - ...... 3]. o u)
|x, u, Φ1) (x).)
45

---

For this system, we parameterize our controller class II" as, for any x E II with parameter 0,
x 0
θ 0++10:(2)) 112-
Note that the form of this controller lets simply "match" the parameters of the system, and cancel undesirable parameters. Given this, for this system we let π. (A) be the controller which sets 1:111 1 to cancel the dynamics of the system A, and set 12 C 10.
See Appendix G.1.3 for details on the computation of H(A) on this system.
G.1.2 Drone System (Figure 2)
The dynamics of this system are given by
0
0
0.1
0
0
0
1
0
0
0.1
0
0
0
0
0
0
1
0
0.1
0
1h+1
0
0
0
1
0
0
0.1
0
0
0
+ Wh-
(G.1)
0
0
0
0
0
0
0
0
0
0.1
0.98
Here interpret [as the x; y/ and positions, respectively, and [ar] 4:6 as the x, y. velocities. This system is therefore equivalent to three double integrator systems, with an affine term (which we interpret "gravity") affecting only the coordinate. We the cost to
de
0.1
cast(ar, u) =
[u]] + [24] + [u]]
5
This then corresponds to system in the form (1.1) with
1
0
0
0.1
0
0
0
0
0
1
0
0
0.1
0
0
0
0
0
1
0
0
0.1
0
0
0
0
4,
Φ(x, 4) = [[x; us 1].
0
0
0
1
0.1
0
0
0
0
0
1
0
0.1
0
0
0
0
0
0.1
-0.98
For this system, we parameterize our controller class II* as, for any T0 E II* with parameter O,
T 0% + Offfset
where 0 E 3 is the state-feedback portion of the controller, and @offset E R33 is an offset term. It can be shown that the optimal controller for system of the form (G.1) can be parameterized in this way [23]. Furthermore, the optimal parameters can be computed in closed-form. As such, for this system
n. (A) be with the optimal parameters, computed using this closed-form solution.
In addition to computing the optimal controller closed-form, we can also compute the cost of controller, J (m; A), in closed-form. To compute H () in this example, we then simply apply the torch. aucograu functional. hessian in function to T (T, (A);
G.1.3 Car System (Figure 3)
The dynamies of this system are given by
1
0.1
0
0
0
0.1
0
0
0
0
0
0.1 cos( [x))s)
24+1
0
0
0
1
0
0
0.1 sin (x)
0
27h
(G.2)
0.1
0
0
1
0
0.1
46

---

where (zals denotes the 5th element of 2/, Here we interpret [2x]] as the æ position, [2a]2 as the y/ position. [21]3 as the x velocity, [x,]4 as the y velocity, [x, the angle of orientation (that is, the direction the car is facing), and (ara]s as the angular velocity. The first control dimension, then, corresponds to the "gas", the power given to the car to move forward backward, and the second control dimension corresponds to altering the direction of the steering wheel. Similar to the drone system, we set the cost to
0.1 1 2 + U22
cost(ar, , u)
Q
with Q
|0.1 101./- + 01 + 02 llop
for some 1 222- To write this in the form of (1.1), in order make the problem more challenging choose an overparameterized ((æ,, u):
Φ( (r, u) = æ,, u, cas( cos(())))) sin([[)]] [u4] cos([ ([ [u0] ssin([)]ss, [ul2 cos([z]ss) [u]p sin([x]ss]
and set
1
0
0.1
0
0
0
0
0
07
0
0
0.1
0
0
0
0
0
1
0
0
0
0.1
0
0
A. =
0
0
0
1
0
0
0.1
0
0
0
0
0
1
0.1
0
0
0
0
0
0
0
0.1
For the car system, the controller class II" is a hierarchical controller parameterized by some R This controller first uses PD) control to compute a "goal input", the direction we would like to modify the state in, as:
Maga((2) 01 [x]] 1:2 02 [a0]3.4.
Given the underactuated structure of the system in (G.2), we cannot directly push the state in the direction of u (goa((rr) Instead, we set uz to the following:
cos(( [x) sin s))
Ugoal (x²) 03([2]]s 8gosl (2))
for (goal(()) = tan ((
[216
Given the complex form of this controller and the dynamics, there does not exist closed-form way to set O optimally. Instead, for this system, we rely on simple random search procedure to compute (A)). To find an optimal controller for system A, randomly sample parameters 0, compute the cost they incur on system A, and then set (AA) to the randomly generated controller with lowest cost. Note that this procedure is not differentiable, but we require (A) is differentiable. To remedy this, A) is needed (in particular, in the computation of ((A)), rather than returning a single controller, we return the softmin distribution over controllers sampled, weighting each controller by its estimated cost. As the softmin distribution can be differentiated, this parameterization of T. (A) differentiable.
in situations where differentiable π, (A)
For this system, there does not cxist closed-form expression for J [[T; A) and, as such, to compute J J(T;A) A). we simply perform many roll-outs of policy æ on system A and aver- age the cost. Given this and the search-based implementation of (A) outlined above, we found that computing the hessian H(A) using the torch. autograd functionan hessian as in Appendix G.1.2 was very memory-intensive. Instead, we computed the Jacobian G(A) ==
V (T, (A'); A) and then, in place of H(A)), we use G(A)G(A)) To compute G(A), we use the torch. autograd. ffn.cfff.nnnnnaniecc ceattionaljaacco.. jacobiar an function. While using (A) in place of H(A) is not justified by our theoretical analysis, if are in settings where π. (A) is not precisely the minimum of J J(T: A) (which will likely be the case here since we are relying on a sampling- based implementation of T., (A), which will ineur some small error), then argue that this is reasonable metric use. In particular, in this setting, the approximation of (= A.) given in Proposition should have an additional first-order term of the form G(A) T veo(AA. - A). As we can upper bound
G(A) ([A)Tvecl vec(A, -A) < /|veecAA. -A)112 2)1
47

---

optimizing for the metric GA)) instead of H((A) can be seen as minimizing the first-order haylor-approximation of the excess loss. Intuitively, this metric quantifies the sensitivity the loss to particular parameters in A., and in practice we found that optimizing this metric produced significant improvements over existing methods. The implementation of the example from Section 1.1 relied on this same approximation.
G.2
Implementation Details
For all methods considered, our implementation follows the basic structure of Algorithm 1: every epoch, we explore so as to minimize some exploration objective, form an estimate of A, on the collected data, and then compute rT (Az) our estimate. Our main experimental results (Figures I to 3) show the loss of v. (At) the time horizon increases. For each method, collect an initial set of data, we begin each trial by exploring randomly for some fixed number of episodes (10 for the drone example, 100 for the car example). The first point in each plot then corresponds to the performance after this initial random exploration. Each aspect of our implementation is modular, and any given component can be easily replaced. Below we highlight our implementation of the exploration routine, and choice of exploration objective, for the various approaches we consider.
G.2.1 Implementation of DYNAMICOED
Implementing exploration procedure, DYNAMICOED, requires access to a regret minimization oracle. While in principle the LC algorithm of [17] could be applied to this problem to give such an oracle, the LC algorithm requires access to a computation oracle which not clear how to implement in practice. To remedy this, we implement Thompson Sampling-inspires modification to the LC3 algorithm of [17].
The primary computational challenge of implementing the LC algorithm is the computation of the optimistic policy:
arg min min
ToxP
TElloxp AEBALI
where [T: A) denotes the exploration cost that is minimized in LC3 (i.c. the expected cost the cost function costj (z. u) + M Φ(xx, (((,,,))(EE))))))))) (En))(zz, u) set in DYNAMICOED), and BALL' the confidence set for A, at iteration
To avoid solving this optimization, we adopt Thompson Sampling-inspired variation of this pro- cedure. In particular, at iteration t, we sample A, ~ (A, A, A, Standard Thompson Sampling would then compute arg min JexP (TT; At), but even this can be challenging, so instead rely on sampling MPC-insping approach. Given that U U1..... -4-1, we aim to approximately solve the following optimization:
state æ,, and have played inputs
H
min Ma. Mh uer Ea
cost (IW, (4))
h
(G.3)
S.t. Th+1 A. wh. un) Σ u un S 532
To solve this approximately, sample many possible randomly, compute the value of the objective of (G.3) on the trajectories induced by these u. and finally choose the input that minimizes this objective. Rather than playing the entire sequence of chosen inputs, however, first input in the sequence, observe the new state on the actual system, and re-solve (G.3) on this new state. Note that the implementation of LC3 used for the experiments given [17] relies on a similar Thompson Sampling-basse approximation to the LC3 algorithm.
simply play the
G.2.2 Implementation of Uniform Exploration
The goal of the procedure we have referred as Uniform Exploration is collect data which will result in the estimation error, || A, Āllop- being minimized, the goal the method given [1]. It can be shown that this is equivalent maximizing (ain(A)). so this method reduces to choosing
48

---

inputs that maximize Amin(Ar) To implement this procedure, we rely on the same sampling -aased based MPC approach as we outlined above, with the primary difference being that instead of minimizing the objective of (G.3), we choose the inputs that maximize
Amin
A
Σ Φ( un ( un) ux) A=1
where A, denote the covariates we have obtained so far at iteration t. While very similar in spirit to the algorithm of [1]. the implementation details are somewhat different than the algorithm proposed in that work. We found that in practice implementation performed better than directly imple- menting (a sampling-base variant of) the algorithm from [1], and all reported results for Uniform Exploration are therefore this version.
G.2.3 Exploring via Cost Minimization
natural point of comparison to our methods would be to forsake the system identification phase entirely, and simply run standard policy optimization algorithms such as TRPO PPO [61, 62], to obtain a controller कr. The primary difficulty with these approaches in the settings we consider that these algorithms are on-policy, meaning that they primarily roll out trajectories using their current estimate of the optimal policy, 7., and using the collected data to do policy improvement on setting is eff-policy, the sense that the learner must explore by playing policies
Th. In contrast, in Hexp. but return some policy in II". Since in the settings we consider пexp * II", on-policy approaches are simply exploring very differently, and therefore cannot be compared with directly.
This is particularly an issue in our setting where stability may come into play. Indeed, may be the case that controller in II" will destabilize the system, and cause the norm of the state to increase exponentially in h. Inducing such trajectories significantly improves one's ability to perform system identification the signal-to to-aaltt-ooiee ratio also then increases exponentially. However, to induce this trajectory with a state-feedback controller, the power of the input played by this controller will also increase exponentially in h. Since choose Πoxp to include only policies with bounded power, this is not a fair comparison (and, furthermore, is likely not an algorithm one would want to run in practice).
While direct comparison with such approaches is therefore not possible, it is possible to compare against algorithms that, instead of collecting data that minimizes maximizes objectives such as tr(HA-1) Amin(A) instead simply aims to play policies minimizing I (T; A). In principle, such algorithms are similar to approaches such as TRPO how they perform their exploration-bov collect data by aiming to minimize the actual cost we are attempting to find a controller to minimize.
To implement this approach, we rely on a sampling-baat based MPC algorithm similar that described in Appendix G.2.1, but where the goal is now to solve
J (T; cC
min
Note that the key difference between this approach and approaches such as TRPO is that we still only play π E Mexp. Using this objective to induce exploration, we then simply estimate A, on this collected data, and return k. (A). The results of this approach on the drone system are given in Figure 4 (with this cost minimization approach denoted as Cost Minimization Exploration). As this illustrates, this approach is significantly worse than Algorithm 1, and also outperformed by Uniform Exploration or Random Exploration when the number of episodes is large enough.
G.3 Additional Results
Finally, in this section we present versions of Figures to 3 with error bars in Figures 5 to 7, In all figures, errors bars denote one standard error.
49

---

70
Task-Driven Exploration (Cuns)
Random Exploration
Exploration
Mean bacees Controter
50
Misimzation Exploration
40
20
10
15
20
35
Figure Performance on drone with LC Exploration
Mean Eicees Controter LO0
lask Driven Exploration (Cuns)
Random Exploration
Unifo Exploration
22
50
60
Number Episades
Figure 5: Mean excess controller loss on instance of Section 1.1 with error bars
"eel-Driven Esploration (Ours) Randam Exploration Uniferm Exploration
Mean Eaces Contrlle LONk
60
30
40
20
20
Epsades
Figure Mean excess controller loss on drone with error bars
Tisk-Dria Oriven Exploration (Ours) Random Exploration Unfform Exaloration
Mean Ex08s1 Controter Loaa
6000
5000
2000
3000
Figure Mean excess controller loss on car with error bars
50


Reviews:
[{"review_id": "ZPNuyz4nPg", "reviewer": "Reviewer_srf1", "summary": "\nIn this paper, the authors propose a method for learning an optimal controller that is able to focus the exploration so as to minimize the estimation error of relevant parameters. They show that the proposed method is indeed optimal with tight upper and lower bounds on the gap. Experiments show that the proposed algorithm performs better compared to the baseline reaching lower loss at any given number of learning episodes.\n\n**After authors' rebuttal:** Thanks for the added clarification. I agree that the paper's contributions are largely theoretical and there's enough here to merit a publication. The authors mention their intention for addition of proof sketches and intuitive discussion which will improve the readability of the paper further. Given these, I am keeping my rating at 7!", "questions": "NA", "limitations": "NA", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is clearly-written, well-motivated and systematically-structured. The assumptions are explicit and the theorems are described to develop intuition. While the idea of certain parameters dictating the system dynamics might make abstract sense, having the motivating example in section 1.1 made the follow-up analysis more grounded for me. Using the second order moment to quantify parameter relevance is neat but that appears to be adopted from previous work. In general, the theory part of the paper is crisp and laid out to facilitate understanding. \n", "weaknesses": "On the other hand, the experiment section is quite thin. However, as a largely theoretical contribution, this is acceptable. I didn’t look through the appendix so I missed out on the proofs, and the paper could have benefitted from some proof sketches without hashing out all the details. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their comments and will work to incorporate the feedback into the final version. We address specific comments below.\n\n> *\"On the other hand, the experiment section is quite thin. However, as a largely theoretical contribution, this is acceptable.\"*\n\nWe refer the reviewer to points 1. and 3. of our response to all reviewers. As stated there (and as the reviewer and other reviewers also state) our contribution is primarily theoretical, but we believe our experimental results do provide empirical evidence that task-driven exploration yields non-trivial gains on realistic systems, and motivates future experimental work in this direction.\n\n> *\"the paper could have benefitted from some proof sketches without hashing out all the details\"*\n\nWe agree that proof sketches would be helpful and will plan to include in the final version with the extra page of space. In particular, we will include intuition on how the lower bound was proved, and additional intuition on the exploration procedure (DynamicOED).\n"}, {"review_id": "SDgmOZA5Wt", "reviewer": "Reviewer_KGe1", "summary": "The paper seeks to quantify formally in the settings of nonlinear dynamical systems (a) which parameters are most relevant to learning a good controller and (b) the best exploration strategy to minimize uncertainty in such parameters. This paper draws theoretical insights where minimizing the controller loss in nonlinear systems translates to estimating the system parameters in a particular task-dependent metric. In light of this characterization, the paper presents an algorithm that achieves the instance-optimal rate for efficient exploration, with controller loss matching a proven lower bound. Several numerical experiments are conducted on nonlinear systems to validate the analysis and the approach.\n\n\n", "questions": "- The authors mentioned in line 378 that they believe the approach will also scale to deep model-based RL settings. Could the authors explain how their approach can be scaled with deep RL? \n", "limitations": "- The authors target a particular class of nonlinear systems characterized in (1.1). This characterization would determine what kind of systems the theoretical insights and the approach can be directly related to.\n- The authors provide experimental analysis on simulated domains. It would be interesting to see the results in real-world environments.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- **S1** The paper is very well written. The problem definitions and contributions are clear.\n- **S2** For a particular class of nonlinear systems of the form (Eqn. 1.1), the paper characterizes how minimizing the controller loss in nonlinear systems translates to estimating the system parameters in a task-dependent metric, and provides a lower bound on the loss of any control rule.\n- **S3** The paper proposes an algorithm that achieves the instance-optimal rate, with controller loss matching the proven lower bound. \n- **S4** The proposed approah demonstrates improvements compared to the baselines in several numerical experiments.", "weaknesses": "- **W1** The paper could benefit from having stronger experimental results. The authors could include more simulated environments that fit into the particular class of nonlinear systems, both in simulation and the real world, such as [1]. The authors could also consider comparing with more baseline methods, such as [2] and [3], from the deep model-based RL community.\n- **W2** Could the authors elaborate on how theoretical insights from the paper relate to problems in practical applications of the particular class of nonlinear systems (1.1)? I believe this would improve the paper's impact on the broader robotics, control, and RL communities. For instance, could applications in safety-critical scenarios be benefited from these insights (e.g., flight maneuvers in [1])?\n\n[1] O’Connell et al., \"Neural-fly enables rapid learning for agile flight in strong winds.\" Science Robotics, 7(66):eabm6597, 2022.\n\n[2] Kaiser et al., \"Model-based reinforcement learning for atari.\"  arXiv preprint arXiv:1903.00374, 2019.\n\n[3] Hafner et al., \"Dream to Control: Learning Behaviors by Latent Imagination.\" arXiv preprint arXiv:1912.01603, 2020.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their comments and will work to incorporate the feedback into the final version. We address specific comments below.\n\n> *Response to W1*\n\nWe refer the reviewer to points 1. and 3. of our response to all reviewers. As stated there our contribution is primarily theoretical, but we believe our experimental results do provide empirical evidence that task-driven exploration yields non-trivial gains on realistic systems, and motivates future experimental work in this direction.\n\n> *Response to W2*\n\nThe primary practical insights from our theory are in what and how to explore. Our theoretical analysis provides a precise quantification of which parameters of the system are most relevant to learn if our goal is to find a good policy, and therefore provide an exploration objective: explore so as to minimize the estimation error in these parameters. Furthermore, our analysis provides insight into how to achieve this: running the DynamicOED procedure will ensure that the estimation error in relevant parameters is minimized as much as possible.\n\nThe particulars of a given application can be easily encoded in our cost. For example, one could add a penalty to the cost to incentivize safe behavior, or could choose the cost to track a particular trajectory. In such settings, our approach will adapt to direct exploration to whatever parameters are most relevant to the particular cost. In addition, as our exploration policy set is generic, it could be restricted to only include “safe” exploration policies (for example, policies guaranteed to maintain stability of the drone during exploration)---our theoretical results still provide an end-to-end guarantee in such settings. Moreover, the learned features in [1] exactly matches our setting in (1.1), so our theory applies directly to guide practice in such applications.\n\n> *\"The authors mentioned in line 378 that they believe the approach will also scale to deep model-based RL settings. Could the authors explain how their approach can be scaled with deep RL?\"*\n\nOur approach is very modular—for example, the policy parameterization and optimizer used, as well as the regret minimization oracle for DynamicOED could be replaced without changing our end-to-end guarantee. One could therefore instantiate these with a variety of methods, including deep RL approaches (e.g. PPO with neural network function approximation could be run on the estimated system to obtain a good policy). While these approaches may lack the theoretical guarantees necessary for our formal results to hold, we expect that, if they are used effectively, they could still yield strong empirical results. \n"}, {"review_id": "4K23Yfh9Ey", "reviewer": "Reviewer_oMB3", "summary": "This paper tackles the challenge of controlling unknown nonlinear dynamical systems in reinforcement learning and control theory. The authors propose a novel algorithm, inspired by recent work in linear systems, focusing on the most critical parameters for learning a low-cost controller on the actual system. This method efficiently explores the system to reduce uncertainty in a specific, task-dependent metric. They demonstrate the algorithm's effectiveness on nonlinear robotic systems and provide a theoretical lower bound showing that their approach learns a controller at a near instance optimal rate. This work could have significant implications for reinforcement learning and control theory.", "questions": "The formulation of the nonlinear system in (1.1) seems restricted, can you explain more about the formulation?", "limitations": "The simulations are conducted on low dimension systems and the experiment setting should be stated more clearly. Besides, this work faces a high computational burden.", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The author presents an algorithm which achieves the instance-optimal rate, with controller loss matching the lower bound on the loss of any sufficiently regular control rule.", "weaknesses": "The regularity assumptions in 3.1 should be addressed clearly and the author could give a toy example to illustrate when these assumptions are satisfied.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their comments and will work to incorporate the feedback into the final version. We address specific comments below.\n\n> *\"The regularity assumptions in 3.1 should be addressed clearly and the author could give a toy example to illustrate when these assumptions are satisfied.\"*\n\nWe would like to emphasize that, as noted, the majority of the assumptions in Section 3.1 are standard in the theoretical literature [1,2]. These will all be met for classes of problems such as LQR. We also want to emphasize that, intuitively, such assumptions are needed to learn efficiently. For example, if our smoothness assumptions (Assumptions 4 and 5) are not met, small changes in the system parameters could lead to arbitrarily large changes in the cost of the learned controller. To ensure that a (reasonably) good controller can be learned on an estimate of the system parameters, we must assume that the cost of a controller varies smoothly as the parameters of the system change.\n\n[1] Mania, Horia, Michael I. Jordan, and Benjamin Recht. \"Active learning for nonlinear system identification with guarantees.\" arXiv preprint arXiv:2006.10277 (2020).\n\n[2] Kakade, Sham, et al. \"Information theoretic regret bounds for online nonlinear control.\" Advances in Neural Information Processing Systems 33 (2020): 15312-15325.\n\n> *\"The formulation of the nonlinear system in (1.1) seems restricted, can you explain more about the formulation?\"*\n\nWe refer the reviewer to point 2. of our response to all reviewers. As stated there, system (1.1) is actually very general and can encompass essentially any continuous dynamical system.\n\n> *\"The simulations are conducted on low dimension systems and the experiment setting should be stated more clearly. Besides, this work faces a high computational burden.\"*\n\nWe refer the reader to point 1., 3., and 4. of our response to all reviewers, and to Appendix G for additional experimental details. As noted, we believe our contribution is primarily theoretical (with a focus on statistical optimality rather than computational complexity), but we believe our experimental results do provide empirical evidence that task-driven exploration yields non-trivial gains on realistic systems, and motivates future experimental work in this direction. Furthermore, efficient approximations of our algorithm exist, which we believe could be scaled to higher-dimensional systems without issue.\n"}, {"review_id": "WzVkrcBHdf", "reviewer": "Reviewer_o9V7", "summary": "The paper proposes an active exploration algorithm for systems of the form $x_{k+1} = A \\phi(x_k, u_k) + w_k$ with known features $\\phi$ and unknown matrix $A$, where $w_k \\sim \\mathcal{N}(0,1)$. The problem is reduced to minimising $\\mathrm{tr}(\\mathcal{H}(A_\\star)\\check{\\Lambda}_T^{-1})$ where $\\mathcal{H}(A_\\star)$ is the Hessian at the optimal $A_\\star$ (which is iteratively estimated) and $\\check{\\Lambda}_T^{-1}$ is roughly the expected covariance $\\phi\\phi^T$ over $T$ episodes of length $H$. Thorough analysis is presented. The algorithm achieves instance-optimal rate. Examples on simulated systems are provided.", "questions": "Could one further improve the algorithm for control-affine systems? I.e., $x' = A\\phi(x) + Bu$ with unknown $A$ and $B$?", "limitations": "No. The authors are encouraged to add at least one paragraph of Conclusion, which also discusses the limitations.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Very strong theoretical paper, solving optimal exploration for a class of linear-in-features systems. Originality, quality, clarity, are excellent. Significance is strong, but since the features are assumed known, it limits the applicability of the algorithm.\n", "weaknesses": "- The class of systems is quite restricted. If one needs to learn the non-linear features $\\phi(x, u)$ first, then one could just as well use the collected data to estimate $A$ afterwards. It would be interesting to see an extension where features are learned as well.\n- The computational complexity is unclear. Does the algorithm run real-time? Is the numerical implementation stable?\n- There is no Discussion/Conclusion/Limitations section.\n- Empirical comparisons are only done with respect to very naive baselines (random and uniform exploration). At least some variance or entropy minimising active exploration could be considered, as e.g., in [1]. But for this paper it is fine, the theoretical contributions are already sufficient, no further experiments are necessary.\n\n[1] Schultheis, M., Belousov, B., Abdulsamad, H., & Peters, J. (2020). Receding horizon curiosity. In Conference on robot learning (pp. 1278-1288). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their comments and will work to incorporate the feedback into the final version. We address specific comments below.\n\n> *“The class of systems is quite restricted. If one needs to learn the non-linear features  first, then one could just as well use the collected data to estimate  afterwards. It would be interesting to see an extension where features are learned as well.”*\n\nWe refer the reviewer to point 2. in our response to all reviewers. We agree that there are interesting cases where one may want to learn the features of the system, but leave fully addressing this for future work. We remark, however, that in many settings (e.g. inverted pendulum) the features (i.e., structure from physics) are known, and all that must be learned is the coefficient. Furthermore, in many settings it may be possible to learn an expressive set of features from one task and transfer them to another; therefore, we do not believe the assumption that the features are known is particularly restrictive (though is nonetheless an interesting direction for future work). \n\n> *“The computational complexity is unclear. Does the algorithm run real-time? Is the numerical implementation stable?”*\n\nWe refer the reviewer to point 4. in our response to all reviewers for discussion on computational complexity. The current implementation is essentially real-time—the primary computational burden is in the policy optimization step and computation of the hessian. While these cannot be done in real-time currently, they only need to be performed a limited number of times (on order $\\log T$) and can be performed offline between episodes. Furthermore, as noted, our approach is very modular and these more computationally expensive components could be replaced with more computationally efficient procedures if desired—we did not optimize for this. The implementation is numerically stable and we plan to release code for it.\n\n> *“There is no Discussion/Conclusion/Limitations section.”*\n\nWe have omitted this due to space constraints but will add for the final version. In particular, we will make sure to highlight some of the limitations mentioned by reviewers here.\n\n> *“Empirical comparisons are only done with respect to very naive baselines (random and uniform exploration). At least some variance or entropy minimising active exploration could be considered, as e.g., in [1]. But for this paper it is fine, the theoretical contributions are already sufficient, no further experiments are necessary.”*\n\nWe refer the reviewer to points 1. and 3. of our response to all reviewers. As stated there (and noted by the reviewer) our contribution is primarily theoretical, but we believe our experimental results do provide empirical evidence that task-driven exploration yields non-trivial gains on realistic systems, and motivates future experimental work in this direction. Furthermore, we believe the “Uniform” baseline we compare against is very strong (see point 3. for more explanation). \n\n> *“Could one further improve the algorithm for control-affine systems? I.e., $x' = A \\phi(x) + Bu$ with unknown $A$ and $B$?”*\n\nAs our result is optimal for any choice of $\\phi$, in the control-affine case, where $\\phi(x,u) = [\\phi(x),u]$, our statistical complexity cannot be improved (since it is already optimal). However, there might exist more computationally efficient implementations in such control-affine settings.\n"}, {"review_id": "jykSIyFaCz", "reviewer": "Reviewer_DNZf", "summary": "This paper considers the problem of task-relevant system identification. It starts with the motivation that not all parameters in the dynamics model are relevant to the given task; thus, the exploration should be placed to prioritize the identification of the relevant dynamics parameters, and thus eventually leading to improved efficiency of the model-based policy learning.\n\nThe authors begin with translating the task loss to the dynamics prediction loss, which is weighted by the cost hessian at ground truth dynamics model. The main result of this paper is to show that this dynamics loss can be approximated tightly by DynamicOED method. The proposed method is validated using some toy problems.\n\nOverall, the paper is well-motivated and presented. This paper did a great job in explaining the theorems. Although the interest of parametric dynamics model is restricted to weighted features, the main results of this paper may be of interest to the reinforcement learning community.\n", "questions": "See my comments in Weaknesses.", "limitations": "See my comments in Weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "See my comments in Summary", "weaknesses": "- In the motivating example, the explanation of task-irrelevant or relevant parameters are confusing. Shouldn't $a_{3:12}$ be irrelevant to learning the optimal controller, while $a_{1:2}$ critical?\n- Please further explain \"In practice, though they may not formally satisfy 290 the guarantee of Assumption 8, deep RL approaches could be used.\"\n- I think Section 5 a bit deviates from the main problem formulation, especially starting with a new system Equ. (5), although I understand the authors are trying to introduce DynamicOED generally for a broad interest of the readers. \n- The authors could give some perspectives on the promise of the results applied to more general dynamics.\n- I strongly suggest adding more or complex tasks to demonstrate the efficiency of the proposed methods over non-optimal exploration model-based policy learning.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their comments and will work to incorporate the feedback into the final version. We address specific comments below.\n\n> *“In the motivating example, the explanation of task-irrelevant or relevant parameters are confusing. Shouldn't $a_{3:12}$ be irrelevant to learning the optimal controller, while $a_{1:2}$ critical?”*\n\n$a_1$, $a_2$, and $a_3$ are all critical to learning the optimal controller—$a_1$ and $a_2$ since they are active everywhere, and $a_3$ since it is active at the point the optimal controller seeks to reach (and so therefore significantly influences the dynamics at the optimal point). $a_1$ and $a_2$ would be learned efficiently be essentially any approach, however—our approach is able to outperform existing approaches by targeting its exploration $a_3$ (while simultaneously learning $a_1$ and $a_2$). We will add additional explanation to the final version to make this clear. \n\n> *“Please further explain \"In practice, though they may not formally satisfy 290 the guarantee of Assumption 8, deep RL approaches could be used.\"”*\n\nOur approach is very modular—for example, the policy parameterization and optimizer used, as well as the regret minimization oracle for DynamicOED could be replaced without changing our end-to-end guarantee. One could therefore instantiate these with a variety of methods, including deep RL approaches (e.g. PPO with neural network function approximation could be run on the estimated system to obtain a good policy). While these approaches may lack the theoretical guarantees necessary for our formal results to hold, we expect that, if they are used effectively, they could still yield strong empirical results.\n\n> *“I think Section 5 a bit deviates from the main problem formulation, especially starting with a new system Equ. (5), although I understand the authors are trying to introduce DynamicOED generally for a broad interest of the readers.”*\n\nAs we hoped to make the results of Section 5 as applicable as possible to a wide range of systems (and make clear that the results in this section do not require that our system be of the form (1.1)), we chose to make this section as general as possible. We will make clear in the final version, however, its connections to systems of the form (1.1).\n\n> *“The authors could give some perspectives on the promise of the results applied to more general dynamics.”*\n\nWe refer the reviewer to point 2. of our response to all reviewers—the dynamics considered are quite general and can encompass nearly any continuous dynamical system. We believe extending our results to even more general settings is an interesting future direction, but is beyond the scope of this work. In particular, extending to more general systems would require new estimation procedures, as the least-squares estimator is not necessarily optimal in such settings, which could significantly affect how the observations translate to estimation error and therefore to controller loss, introducing non-trivial analysis challenges.\n\n> *“I strongly suggest adding more or complex tasks to demonstrate the efficiency of the proposed methods over non-optimal exploration model-based policy learning.”*\n\nWe refer the reviewer to points 1. and 3. of our response to all reviewers. As stated there our contribution is primarily theoretical, but we believe our experimental results do provide empirical evidence that task-driven exploration yields non-trivial gains on realistic systems, and motivates future experimental work in this direction.\n"}, {"review_id": "oaydHTU6pf", "reviewer": "Reviewer_vdw9", "summary": "This paper addresses the problem of exploration when learning to control non linear systems. In particular, they derive a task-driven exploration method which focuses on learning the system parameters that are relevant for the specific task that a controller is trying to achieve. \n\nTo derive the algorithm, they rely on a quantity which estimates how much the task loss vary, under a certainty-equivalence controller and the current model estimate. This quantity is the key to estimating what parameters in the model are relevant for the task at hand. It can be used by existing exploration algorithms (DynamicOED) as a minimization target.\n\nThe exploration routine is presented as a second contribution which extends an algorithm originally designed for linear MDPs to non-linear systems.\n", "questions": "- Is there any physical system that would be like the motivating example?\n\n- What is D-optimal design? What to the optimization targets presented as example represent at line 270 in section 5?\n\n- Why is dynamicOED returning several exploration policies and not just one per step in algorithm 1?\n\n- How is the optimal controller $\\pi_*$ obtained to compute the excess controller loss?\n\n", "limitations": "They assume a specific form of non-linear system which could limit the applicability of the solution (at least the theoretical results), however a few references are mentioned indicating that many systems fit into this category.\n\nThe bounds scale polynomially in the number of system parameters, it is not commented whether it is desirable or not. Couldn’t systems have a large number of parameters? \n", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The premises of the article that all parameters of the system might not be useful to know for the task of the controller makes a lot of sense, and the problem of task driven exploration is interesting and relevant. \n\nOverall, there is novelty as they extend a lot of existing concepts to a much broader class of systems (non-linear) and the contribution seems significant. However, it would be quite hard to implement the proposed algorithm from reading just the paper itself. \n\nThe introduction of the motivating example and associated discussion is quite useful to understand the problem space. \n\nThe related work section helps to position the scope of the paper and is mixing both RL and more traditional control.\n\nThe experiment section show that the proposed algorithm outperforms non task-driven exploration methods. The set of baselines is quite limited but as the concept is quite specific to this article, I believe they are a sound choice. \n", "weaknesses": "Although the paper is well structured and written, the main weakness is the presentation. Since the paper introduces a lot of mathematical concepts and assumptions, it is useful to help the reader by describing intuitively what they mean. \n\nThe assumptions presented are justified by citing previous work but some description would be useful to make the paper more self contained. Specifically assumption 3, it would be useful if the authors provide an intuitive justification.\n\nAssumption 8 lacks some general explanation. How does the choice of the underlying algorithm affect the performance? and why is the cost different than the goal $\\Phi$?\n\nA lot of the concepts are derived from reference [2] which essentially solves the problem in the case of linear systems. It makes the contribution more incremental, however the jump from linear to non-linear is still significant. \n\nTheorem 1 and 2 introduce bounds on the exploration loss which are claimed to be novel, it would still be useful to compare with the bounds for algorithms that are not task dependent. Is there a trade-off? \nSince section 5 is presented as a potentially independent contribution, it would have been useful to add more background about the experiment design problem and clearly highlight the difference with previous work.\n\nThe notation in dynamicOED is hard to follow, the explanation helps only a little. It would be quite hard to implement the algorithm just from reading the paper. It refers a lot to the LC3 algorithm which is not explained (this is certainly not my main expertise).\n\nThe systems use in the experiments have fairly small scales (6 dimensions for the state). One could wonder whether the approach scale in the number of dimensions. It is mention a linear dependency with the system parameter for the convergence. What about the computational cost of the algorithm?\n\nIn the experimental section, it is mentioned that MPC sampling based methods are used for exploration. How do we know that they verify assumption 8 which is key for convergence? \n\nMaybe the author could have tried linearizing the systems and applied the linear version of the algorithm that is cited.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their comments and will work to incorporate the feedback into the final version. We address specific comments below.\n\n> *“However, it would be quite hard to implement the proposed algorithm...” “The notation in dynamicOED is hard to follow, the explanation helps only a little...”*\n\nWhile the algorithm description in the main body is somewhat brief due to space constraints, we provided many more experimental details in Appendix G, which we believe will be helpful in implementing our algorithm. Furthermore, we plan to release code for our approach, and will work to clarify notation in the final version.\n\n> *“Although the paper is well structured and written, the main weakness is the presentation...”*\n\nWe were somewhat limited by space constraints in the original submission, but will plan to add more explanation as space permits in the final version. We would be happy to provide explanations to any particular points the reviewer has. \n\n> *“The assumptions presented are justified by citing previous work but some description would be useful...”*\n\nIntuitively, Assumption 3 states that every feature direction can be reached, and is relevant to learning a good controller. If this assumption is not satisfied, then $\\phi$ is overspecified, and could be projected down to a lower-dimensional space without changing the behavior. If our smoothness assumptions (Assumptions 4 and 5) are not met, small changes in the system parameters could lead to arbitrarily large changes in the cost of the learned controller. To ensure that a (reasonably) good controller can be learned on an estimate of the system parameters, we must assume that the cost of a controller varies smoothly as the parameters of the system change. We will add these intuitions in the extra page.\n\n> *“Assumption 8 lacks some general explanation...”*\n\nAs shown in Theorem 3, the parameters the algorithm employed by Assumption 8 has ($C_{\\mathcal{R}},p_{\\mathcal{R}}$) affect the convergence rate of our experiment design procedure—besides this, the choice of algorithm does not affect the performance. The cost in Assumption 8 is different from the goal cost as we do not apply the algorithm of Assumption 8 to optimize the goal cost directly—instead, we apply it to a cost which incentives exploration (and the data collected during exploration is then used to solve the actual goal). This is illustrated and described in in Section 5.1.\n\n> *“A lot of the concepts are derived from reference [2]...”* \n\nWe emphasize that moving from linear to nonlinear systems is usually very non-trivial, which is the case here, and to achieve our guarantee in the nonlinear setting requires non-trivial analysis. For example, in linear systems, random excitation is sufficient, while in nonlinear systems random excitation is not guaranteed to excite each direction, and estimates of system parameters could be arbitrarily bad. To address this required developing exploration techniques that navigate within the system to ensure all directions are excited.\n\n> *“Theorem 1 and 2 introduce bounds on the exploration loss which are claimed to be novel...”*\n\nOnly several works that we are aware of can be directly compared with our results in Theorem 1 and 2. In particular, [1,2] both provide guarantees in this setting, but their rates translate to suboptimality guarantees that scale as $O(1/\\sqrt{T})$, significantly slower than our $O(1/T)$ rate. The work of [3] does not give an end-to-end guarantee on controller loss (and furthermore they consider the non-episodic setting). However, applying their estimation guarantee in Proposition 1, we obtain a bound scaling as roughly \n$O( || \\mathcal{H}(A_\\star) ||\\_{op} \\cdot \\min [ d_x, d\\_{\\phi}] \\cdot \\frac{H (d_x + d_\\phi)}{\\lambda_{\\min}^\\star T})$, which could be significantly worse than our bound, as we  demonstrate to be the case experimentally in Section 1.1 (we emphasize again that these are not directly comparable though—to obtain a direct comparison the results of [3] would need to be reworked in the episodic setting we consider). We will add further discussion on this in the final version.\n\n[1] Kakade, Sham, et al. \"Information theoretic regret bounds for online nonlinear control.\" Advances in Neural Information Processing Systems 33 (2020): 15312-15325.\n\n[2] Song, Yuda, and Wen Sun. \"Pc-mlp: Model-based reinforcement learning with policy cover guided exploration.\" International Conference on Machine Learning. PMLR, 2021.\n\n[3] Mania, Horia, Michael I. Jordan, and Benjamin Recht. \"Active learning for nonlinear system identification with guarantees.\" arXiv preprint arXiv:2006.10277 (2020).\n\n> *“The systems use in the experiments have fairly small scales (6 dimensions for the state)...”*\n\nWe refer the reviewer to point 1., 3., and 4. of our response to all reviewers, and to Appendix G for additional experimental details. As noted, we believe our contribution is primarily theoretical, but we believe our experimental results do provide empirical evidence that task-driven exploration yields non-trivial gains on realistic systems, and motivates future experimental work in this direction. Furthermore, efficient approximations of our algorithm exist, which we believe could be scaled to higher-dimensional systems without issue.\n\n> *“In the experimental section, it is mentioned that MPC sampling based methods are used for exploration. How do we know that they verify assumption 8 which is key for convergence?”*\n\nIn practice our MPC procedure may not have a guarantee satisfying Assumption 8 directly. However, we see this as an advantage: our experimental results demonstrate that our approach can be effectively applied even when our assumptions are not necessarily met. "}]

Author rebuttal:
We would like to thank the reviewers for their feedback and will do our best to incorporate as much of it as possible into the final version. We address several key points of clarification below:

1. **Primary Contributions:** We want to emphasize that the primary contribution of this paper is theoretical. To our knowledge, ours is the first work to provide instance-optimal guarantees for nonlinear control. We also want to emphasize that the extension from linear to nonlinear systems introduces significant technical difficulties (e.g. in linear systems, random excitation allows for efficient learning, which is not the case here), which our work overcomes. Furthermore, the study of instance-optimality in decision making is of much interest to the theory community and is a very active area of research (see e.g. [1,2,3] below and references therein)—we believe our results are an important contribution in this direction.

2. **System Model:** Several reviewers remarked that the class of systems we consider is too restrictive. We have several comments on this. First, as is stated in bullet point 1, our setting can model any continuous dynamics model given expressive enough $\phi$ (which can be accomplished without prior knowledge of the system by, for example, using random fourier features [7]), and is therefore quite general. In particular, our setting encompasses many standard control settings: linear systems, control affine systems, etc. Second, this setting is standard in the theory community, and has seen much recent work [4,5]. Finally, similar settings have been considered in a variety of empirical studies, demonstrating its applicability to a wide range of real-world problems in robotics and model-based RL [6,7,8].

3. **Experiments:** Several reviewers suggested that we provide additional experimental results, or compare against more baselines. We first want to reiterate that our primary contribution is theoretical. Our experiments, then, serve as a proof-of-concept of the theory. They are also, however, the first experimental results, to our knowledge, to demonstrate that task-driven exploration can yield non-trivial improvements over more naive exploration in realistic systems. We believe this motivates future empirical research extending this to higher-dimensional systems, but this is beyond the scope of the current work. We also want to reiterate that our method is agnostic to the choice of policy parameterization and optimizer, and could be combined with many different approaches—our method provides a statistically optimal exploration routine for any given policy parameterization and optimization method. Given this, for the sake of clarity in our experiments we chose to use relatively straightforward control methods, but the extension to more general methods is straightforward. On our choice of baselines, we want to emphasize that the method referred to as “Uniform” (the approach of [4]) is a very strong baseline as it explores in a targeted manner to optimally reduce uncertainty in the estimated model. It is essentially performing a variant of maximum entropy exploration specialized to the class of systems we consider—we would not expect any existing approaches for MBRL (which either rely on random exploration or entropy-driven exploration) to improve on this baseline. 

4. **Computational Efficiency:** Several reviewers brought up the computational efficiency of our approach. While our approach is not computationally efficient in general, we want to emphasize it is statistically optimal. In addition, existing work on learning in systems of the form (1.1) are also computationally inefficient as efficient planning in systems of the form (1.1) is in general not tractable. For special cases—such as linear systems—however, where efficient planning is possible, our algorithm is computationally efficient. Furthermore, as we demonstrate experimentally, there exist computationally efficient approximations (e.g., using a Jacobian approximation to the Hessian computation) to our algorithm which allow us to run it on a range of systems. 

[1] Wagenmaker, Andrew J., and Dylan J. Foster. "Instance-optimality in interactive decision making: Toward a non-asymptotic theory." The Thirty Sixth Annual Conference on Learning Theory. PMLR, 2023.

[2] Kirschner, Johannes, et al. "Asymptotically optimal information-directed sampling." Conference on Learning Theory. PMLR, 2021.

[3] Xu, Haike, Tengyu Ma, and Simon Du. "Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step bootstrap." Conference on Learning Theory. PMLR, 2021.

[4] Mania, Horia, Michael I. Jordan, and Benjamin Recht. "Active learning for nonlinear system identification with guarantees." arXiv preprint arXiv:2006.10277 (2020).

[5] Kakade, Sham, et al. "Information theoretic regret bounds for online nonlinear control." Advances in Neural Information Processing Systems 33 (2020): 15312-15325.

[6] Richards, Spencer M., et al. "Adaptive-control-oriented meta-learning for nonlinear systems." arXiv preprint arXiv:2103.04490 (2021).

[7] Boffi, Nicholas M., Stephen Tu, and Jean-Jacques E. Slotine. "Regret bounds for adaptive nonlinear control." Learning for Dynamics and Control. PMLR, 2021.

[8] O’Connell, Michael, et al. "Neural-fly enables rapid learning for agile flight in strong winds." Science Robotics 7.66 (2022): eabm6597.

Meta-review: This paper considers the setting of nonlinear dynamical systems and seeks to formally quantify which parameters are most relevant to learning a good controller, and how one can best explore so as to minimize uncertainty in such parameters. The proposed algorithm is supported by theoretical guarantees and shows significant improvement over simple exploration mechanisms in a number of simulated environments. The reviewers agree that the paper is well-written, clear, technically strong, and the algorithm is novel.
Decision: Accept (spotlight)