Koopman Spectrum Nonlinear Regulators and Efficient Online Learning
Authors: Motoya Ohnishi
Isao Ishikawa
Kendall Lowrey
Masahiro Ikeda
Sham M. Kakade
Yoshinobu Kawahara
Venue: Accepted by TMLR ()

Abstract: Most modern reinforcement learning algorithms optimize a cumulative single-step cost along a trajectory.  The optimized motions are often ‘unnatural’, representing, for example, behaviors with sudden accelerations that waste energy and lack predictability.  In this work, we present a novel paradigm of controlling nonlinear systems via the minimization of the Koopman spectrum cost: a cost over the Koopman operator of the controlled dynamics.  This induces a broader class of dynamical behaviors that evolve over stable manifolds such as nonlinear oscillators, closed loops, and smooth movements.   We demonstrate that some dynamics characterizations that are not possible with a cumulative cost are feasible in this paradigm, which generalizes the classical eigenstructure and pole assignments to nonlinear decision making.   Moreover, we present a sample efficient online learning algorithm for our problem that enjoys a sub-linear regret bound under some structural assumptions.

Published in Transactions on Machine Learning Research (6/2024)
Koopman Spectrum Nonlinear Regulators and Efficient On- line Learning
Motoya Ohnishi
mobnishhi@ecs.usshiggtoon.ccc
Paul G. Allen School of Computer Science & Engineering University of Washington
Isao Ishikawa
Ehine University
RIKEN Center for Advanced Intelligence Project
Kendall Lowrey
kendall..owrrey@@mmaii
Et Cetera Robotics
Masahiro Ikeda
masahiro. @riken..jp
RIKEN Center for Advanced Intelligence Project
Keio University
Sham Kakade Harvard University
sham@ssea..havvrdddcc edu
Yoshinobu Kawahara
kauuharr@istosakaauu
Graduate School of Information Science and Technology, Osaka University
RIKEN Center for Advanced Intelligence Project
Reviewed on OpenReview: https: // openreview. net/ forun? id= thfoUZuguS
Abstract
Most modern reinforcement learning algorithms optimize a cumulative single-step cost along trajectory. The optimized motions are often 'unnatural', representing, for example, be- haviors with sudden accelerations that waste energy and lack predictability. In this work, we present novel paradigm of controlling nonlinear systems via the minimization of the Koopman spectrum cost: cost over the Koopman operator of the controlled dynamics. This induces a broader class of dynamical behaviors that evolve over stable manifolds such as nonlinear oscillators, closed loops, and smooth movements, We demonstrate that some dynamics characterizations that are not possible with a cumulative cost are fcasible in this paradigm, which generalizes the classical eigenstructure and pole assignments to nonlinear decision making. Moreover, present sample efficient online learning algorithm for our problem that enjoys sub-linear regret bound under some structural assumptions.
1 Introduction
Reinforcement learning (RL) has been successfully applied to diverse domains, such robot control (Kober al. (2013); Todorov et al. (2012); Ibarz et al. (2021)) and playing video games (Mnih et al. (2013; 2015)). Most modern RL problems modeled Markov decision processes consider an immodiate (singlo-step) cost (reward) that accumulates over a cerlain time horizon to encode tasks of interest. Although such a cost can encode any single realizable dynamics, which is central to inverse RL problems (Ng Russell (2000)), the generated motions often exhibit undesirable propertics such as high jerk, sudden accelerations that waste energy, and unpredictability. Intuitively, the motion specified by the task-oriented cumulative cost formulation may ignore "how to" achieve the task unless careful design of cumulative cost is in place,

---

Published in Transactions on Machine Learning Research (6/2024)
necessitating a systematic approach that effectively regularizes constrains the dynamics to guarantee predictable global property such as stability.
Meanwhile, many dynamic phenomena found in nature are known to be represented as simple trajectories, such as nonlinear oscillators, on low-dimensional manifolds embedded in high-dimensionall spaces that we observe (Strogatz, 2018). Tts mathematical concept is known as phase reduction (Winfree, 2001; Nakao, 2017), and recently its connection to the Koopman operator has been attracted much attention in response to the growing abundance of measurement data and the lack of known governing equations for many systems of interest (Koopman, 1931; Mezić, 2005; Kutz et al., 2016).
In this work, we present a novel paradigın of controlling nonlinear systems based on the spectrum of the Koopman operator. To this end, we exploit the recent theoretical and practical developments of the Koopman operators (Koopman, 1931; Mezić, 2005), and propose the Koopman spectrum cost as the cost over the Koopman operator of controlled dynamics, defining a preference of the dynamical system the reducod phase space. The Koopman operator, also known the composition operator, is linear operator over an observable space of a (potentially nonlinear) dynamical system, and is used to extract global properties of the dynamics such as its dominating modes and eigenspectrum through spectral decomposition. Controlling nonlinear systems via the minimization of the Koopman spectrum cost induces a broader class of dynamical behaviors such as nonlinear oscillators, closed loops, and smooth movements.
Although working in the spectrum (or frequency) domain has been standard in the control community (e.g. Andry et al. (1983); Hemati & Yao (2017)), the use of the Koopman spectrum cost together with function approximation and learning techniques enables us to generate rich class of dynamics evolving over stable manifolds (cf. Strogatz (2018)).
Our contributions. The contributions of this work are three folds: First, we propose the Koopman spec- trum cost that complements the (cumulative) single-step cost for nonlinear control. Our problem, which we refer to as Koopman Spectrum Nonlinear Regulator (KSNR), is to find an optimal parameter (e.g. policy parameter) that leads to a dynamical system associated to the Koopman operator that minimizes the sum of both the Koopman spectrum cost and the cumulative cost. Note that "Regulator" in KSNR means not only controller in control problems but a more broad sense of regularization of dynamical systems for attaining specific characteristics. Second, we show that KSNR paradigm effectively incoes//imtaate some desirable agent dynamics such limit cycles, stable loops, and smooth movements. Note that, when the underlying agent dynamics is known, KSNR may be approximately solved by exlending any nonlinear planning heuris- tics, including population based methods. Lastly, we present a (theoretical) learning algorithm for online KSNR, which attains the sub-lincar regret bound (under cortain condition, of order Ô(VT)). Our algo- rithm Sroopman-Spectrum LC (KS-LC*)) is a modification of Lower Confidence--assed Continuous Control (I.C)) (Kakade et al., 2020) to KSNR problems with several technical contributions. We need structural assumptions on the model to simultaneously deal with the Koopman spectrum cost and cumulative cost. Additionally, present a certain Hölder condition of the Koopman spectrum cost that makes regret analysis tractable for some cost such as the spectral radius.
Key Takeaways
KSNR considers the spectrum cost that is not subsumed by a classical single-step cost or an episodic cost, and is beyond the MDP framework, which could be viewed as a generalization of eigenst eigenstructure ructure / pole
assignments to nonlinear decision making problems. The framework systematically deals with the shaping of behavior (c.g., ensuring stability, smoothness, and adherence to target mode of behavior). Because we employ this new cost criterion, we strongly emphasize that this work is not intended to compete against the MDP counterports, but rather to illustrate the effectiveness of the generalization we make for systematic behavior shaping. For online learning settings under unknown dynamics, the spectrum cost mobservable because of inaccessible system models; thus differs from other costs such as a policy cost. As such, we need specific structural assumptions that are irrelevant to the Kernelized Nonlincar Regulator (Kakade al., 2020) to devise sample efficient (if not computationally efficient) algorithm. Proof techniques include some operator theoretic arguments that are novel in this context.
2

---

Published in Transactions on Machine Learning Research (6/2024)
Notation. Throughout this paper, I, Rzo. N, Z,0, and C denote the set of the real numbers, the non- negative real numbers, the natural numbers respectively. Also, 1l is a set of dynamics parameters, and [H] := {0, 1,... H - 1} for H E Z2o. The set of bounded lincar operators from A to B is denoted by L(A; B), and the adjoint of the operator of is denoted by df'. We let (et(.) be the functional determinant. Finally, we let || ||=|| || and || I|a be the Euclidean norm of E R2, the 1-norm (sum of absolute values), the operator norm of of E C(A B), and the Hilbert Schmidt norm of a Hilbert-Schmidt operator of respectively.
the positive integers, and the complex numbers,
2 Related work
Koopman operator was first introduced in Koopman (1931); and, during the last two decades, it has gained traction, leading to the developments of theory and algorithm (e.g. Crnjarí6-Zic et al. (2019); Kawahara (2016); Mauroy & Mezić (2016); Ishikawa et al. (2018); Iwata & Kawahara (2020); Burov et al. (2021)) partially due to the surge of interests in data-driven approaches. The analysis of nonlinear dynamical system with Koopman operator has been applied to control (e.g. Korda & Mezić (2018); Mauroy et al. (2020); Kaiser et al. (2021); Li et al. (2019); Korda & Mezié (2020)), using model predictive control (MPC) framework and linear quadratic regulator (LQR) although nonlinear controlled systems in general cannot be transformed to LQR. problem even by lifting to a feature space. For unknown systems, active learning of Koopman operator has been proposed (Abraham & Murphey (2019)). Note our framework applied to stability regularization considers the solcly different problem than that of (Mamakoukas et al., 2023). In the context of stability regularization, our framework is not for learning the slable Koopman operalor or to construct a control Lyopunov function from the learned operator but to solve the regulator problem to balance the (possibly task-based) cumulative cost and the spectrum cost that enforees stability. We will revisit this perspective in Section 3.3.
The line of work that is most closely related to ours is the eigenstructure/ pole assignments problem (e.g. Andry et al. (1983); Hemati & Yao (2017)) classically considered in the control community particularly for linear systems. In fact, in the literature on control, working in frequency domain has been standard (e.g. Pintelon & Schoukens (2012); Sabanovic & Ohnishi (2011))- These problems aim at computing a feedback policy that generates the dynamics whose eigenstructure matches the desired one; we note such problems can be naturally encoded by using the Koopman spectrum cost in our framework as well. In connection with the relation of the Koopman operator to stability, these are in principle closely related to the recent surge of interest in neural networks to learn dynamics with stability (Manek & Kolter, 2019; Takeishi & Kawahara, 2021).
In the RL community, there have been several attempts of using metrics such as mutual information for acquisitions of the skills under RL settings, which are often referred to as unsupervised RL (c.g. Eysenbach et al. (2018)). These work provide an approach of effectively generating desirable behaviors through com- positions of skills rather than directly optimizing for tasks, but are still within cumulative (single-step) cost. framework. Historically, the motor primitives investigated in, for example, (Peters & Schaal, 2008; ljspeert et al., 2002; Stulp & Sigaud, 2013) have considered parametric nonlinear dynamics having some desirable properties such as stability, convergence to certain attractor etc., and it is related to the Koopman spectrum regularization in the sense both aim at regulating the global dynamical properties. Those primitives may be discovered by clustering (cf. Stulp et al. (2014)), learned by imitation learning (cf. Kober & Peters (2010)), and coupled with parameer learning (e.g. Kober et al. (2012)).
Finally, as relatod to the sample efficient algorithm we propose, provably correct methods (o.g. Jiang et al. (2017); Sun et al. (2019)) have recently been developed for continuous control problems (Kakade et al., 2020; Mania et al., 2020; Simchowitz & Foster, 2020; Curi et al., 2020).
Below, we present our control framework, KSNR, in Section 3 with several illustrative mumerical examples based on population based policy search (e.g. genetic algorithm), followed by an introduction of its example online learning algorithm (Section 4) with its theoretical insights on sample complexity and on reduction of the model to that of eigenstructure assignments problem as a special case. For more details about population based search that repeatedly evaluates the sampled actions to update the sampling distribution of action sequence that the agent can achieve lower cost, see for example (Beheshti & Shamsuddin, 2013).
3

---

Published in Transactions on Machine Learning Research (6/2024)
3 Koopman Spectrum Nonlinear Regulator
In this section, we present the dynamical system model and our main framework.
3.1 Dynamical system model
Let X' C Rdx be the state space, and IT set of parameters each of which corresponds to one random dynamical system (RDS) as described below. Given a parameter θ E II, let (Ne, be probability space, where le is a measurable space and Pe is a probability measure. Let pe == (He(r))reN be semi-group of measure preserving measurable maps on Ge (i.e., pe(r) Ωe + Ωe). This work studies the following nonlinear regulator (control) problem: for each parameter θ E II, the corresponding nonlinear random dynamical system is given by
J :Nx x X
that satisfics
(0,
( (r, F (s,,,,)) e WE wese, X.
(3.1)
The above definition of random dynamical system is standard in the community studying dynamical systems (refer to (Arnold, 1998), for example). Roughly speaking, an RDS consists of the following two models:
A model of the noise;
A function representing the physical dynamics of the system.
RDSs subsume many practical systems including solutions to stochastic differential equations and additive- noise systems, i.e.,
Th+1 = f(r) The Tn Rdd, h [H]
where f Rdx Rdx represents the dynamics, and ma Rd is the zero-mean ii.d. additive noise vector. Let No be probability space of the noise, and one could consider Ω = a (and f is the shift) to express the system as an RDS. Also, Markov chains can be described as an RDS by regarding them as composition of i..dd random transition and by following similar arguments to the above (sec Arnold (1998, Theorem 2.1.6)).
As an example, consider the discrete states 82] and the transition matrix
0.8 0.2 = 0.7
[[]]]])) 1
0
0
1 0
[ 0
TRANSITION MATRIX = 0.1 0.9
+ 0.2
+
+
where the right hand side shows decomposition of the transition matrix to deterministic transitions. For this example, one can naturely treat this Markov chain as an RDS that generates each deterministie transition with corresponding probability at every step.
More intuitively, dynamical systems with an invariant noise-generatingg mechanism could be described as an RDS by an appropriate translation (see Figure (Left) for an illustration of an RDS).
Koopman operator For the random dynamical systems being defined above, define the operator- valued map H below, using the dynamical system model.
Definition 3.1 (Koopman operator). Let H be a function space on X' over C and let { fee) be a dynamical system model. We define an operator-valued map X by H + L(H, H) such that for any θ and g E H,
[0)gg))()) = Ess [g Fo (L, rE X.
We will choose a suitable to define the map X, and ((O) the Koopman operator for F Essontially, the Koopman operator represents a nonlinear dynamics as a linear (infnite-dimensioonal) operator that describes the evolution of obseroables in lifted space (see Figure 1 Right).
4

---

Published in Transactions on Machine Learning Research (6/2024)
{ue(s)o} x x
(w} N
{pe(r + +m)t x
X
Lift
H
g
[ (e))) = x(())
( + 8,00 1 (nlpe (a.,))))
31
pe(s)
((0))
Sample space
pelr + 8)6
(realizations of paths)
Random dynamical system consists of model of the noise and function representing the physical phase space (the illustration is inspired by Arnold (1998); Ghil et al. (2008)). The RDS flows over sample space and phase space for each realization w and for initial state Right: By lifting the state space to a space of observables, a nonlinear dynamical system over the state space is represented by the linear operator in a lifted space.
Figure 1: Left:
Remark 3.1 (Choice of H and existence of X). In extreme (bul. useless) case, one could choose H to be dimensional space spanned by constant function, and X be defined. In general, the properties of the Koopman operator depend the choice of the space which the operator is defined. As more practical cases, if one employs a Gaussian RKHS for example, the only dynamics inducing bounded Koopman operators are those of affine (e.g. Tshikawa (2023); Tkeda et al. (2022)). However, some practical algorithms have recently been proposed for an RKHS to approximate the eigenvalues of so-called "extended" Koopman operator through some appropriate computations under certain conditions on the dynamics and on the RKHS (ef. Ishikawa al. (2024)).
With these settings place, we propose our framework.
3.2 Koopman Spectrum Nonlinear Regulator
Fix a set X, == (=0,0 Ho), (Fo.1, Hy)..... (Fo.N-1,HNII)) Fo X'Z20 for N e Z>o, and define c : X Rgo be cost function. The Koopman Spectrum Nonlinear Regulator (KSNR), which propose in this paper, is the following optimization problem:
Find O* E arg min J
(3.2)
BEll
where A H(H:H) + R2o is mapping that takes Koopman operator input and returns its cost: and
N-1
H -1 c(znn) 0, zon
1 (Xo:c) =
Ena
Σ 1=0
R=0
where (h,n(w) (w) = F w. (o..). control problem setting, the problem (3.2) can be read as finding a control policy O", which minimizes the cost; note, each control policy generates a dynamical system that gives the costs AiX (9)] and J c) in this case. However, we mention that the parameter θ can be the physics parameters used to design the robot body for automated fabrication any parameter that uniquely determines the dynamics.
Example 3.1 (Examples of A). Some of the examples of A are:
1. A [a/] max (I)) where p(el/ is the spectral radius of ot prefers stable dynamics.
5

---

Published in Transactions on Machine Learning Research (6/2024)
d(H-1))
single-step cost (observed)
dxo)
((1))
HH-1
Cepisode [(rr)
episodic cost
20
(observed or computable)
11
l policy (0) policy cost (computable)
Dynamics represented by H (0)
A[X (0)] spectrum cost (not observed)
Comparisons of several costs for decision making problems. The Koopman spectrum cost is the cost over the global properties of the dynamical system itself which is typically unknown for learning problems, and is unobservable.
Figure 2:
A|a] for. (of) can be used for imitation learning, where las (ef) : ((H; - 12zo a loss function measuring the gap between of and the given of E C(H: H).
3. - A (of) prefers agent behaviors described by fewer dominating modes. Here, {Ae the set of eigenvalues of the operator sf (assuming that the operator has discrete spectrum).
Assuming that the Koopman operator is defined over dimite-dimensional space, an eigenvalue of the operator corresponding to each eigenfunction can be given by that of the matrix realization of the operator. In practice, one employs a fimite-dimensional space even if it is not invariant under the Koopman operator; in such cases, there are several analyses that have recently been made for providing estimates of the spectra of the Koopman operator through computations over such a limen-iimeniional space. Interested readers may be referred to (Ishikawa et al., 2024; Colbrook Townsend, 2024; Colbrook et al., 2023) for example. In particular, avoiding spectral pollution, which refers to the phenomena where discretizations of an infnite-dimeeniinnal operator to finite matrix create spurious eigenvalues, and approximating the continuous spectra. have been actively studied with some theoretical convergence guarantees for the approximated spectra. In order to obtain an estimate of the spectral radius through computations on matrix of finite rank, the Koopman operator may need to be compact (see the very recent. work A Akindji et al. (2024) for example).
Remark 3.2 (Remarks on how the choice of affects the Koopman spectrum cost). As we have discussed in Remark 3.1, the mathematical properties of the Koopman operator depend on the function space H, and information of the background dynamics implied by this operator depends on the choice of H; however their spectral properties typically capture global characterstics of the dynamics through its lincarity.
We mention that the Koopman operator over H may fully represents the dynamics in the sense that it can reproduce the dynamical system over the state space (i.e., the original space) under certain conditions (see Ishikawa et al. (2024) for example on detailed discussions); however, depending on the choice of H, is often the case that the Koopman operator does not uniquely reproduce the dynamics. The extreme case of such an example the function space of single dimension spanned by a constant function, for which the Koopman operator does not carry any information about the dynamics. Even for the cases where the Koopman operator over the chosen space H only captures partial information on the dynamics, the spectrum cost is still expected to act as regularizer of such partial spectral properties of the dynamics.
As also mentioned in Remark 3.2, the Koopman spectrum cost regularizes certain global properties of the generated dynamical system; as such, it advantageous to employ this cost A over sums of single-step costs c(x) that are the objective in MDPs especially when encoding stability of the system for example. To illustrate this perspective more, we consider generating a desirable dynamical system (or trajectory) as a solution to some optimization problem.

---

Published in Transactions on Machine Learning Research (6/2024)
Regularization of global characteristic of dynamies
Cumulative cost formulation
Koopman spectrum cost formulation
Trajectory generated by dynamics of o
desirable transition
Dynamies corresponding to Top mode m
Th
c( Th41) =
Th+1
undesirable transition
<( = 1, Vr X' (ma11)
A(a)) if the top mode is m else
Trajectory could be specified by assigning "local" costs to undesirable transition
Global characteristics of dynamics could be specified by the spectrum costs
Figure 3: While single-step costs (taking the current and next states as input) could be used to specify every transition, acting as a "local" cost, the Koopman spectrum cost regularizes "global" characteristics of the dynamics through specifying its spectral properties (e-g., by forcing the dynamics to have some given mode m² as its top mode). The regularization incurred by the Koopman spectrum cost may not be implemented by the cumulative cost formulation in straightforward manner. We mention it has some relations to the skill learning with motor primitives (see Section 2) in the sense that both aim at regulating the global dynamical properties.
Let X' R, e (0, 1], and let c: X Ryo be nonconstant cost function. We consider the following loss function for a random dynamical system F N:NNXxA X:
(F,x)) = En Σ c (F((F(,,,,0)))
Now considor the dynamical system F(), = Ve E. Vo E Ω for example. Then, it holds that, for any choice of u and e, there exists another random dynamical system satisfying that for x E X,
19)xx) < ((F,)).
This fact indicates that there exists a dynamical system that cannot be described by a solution to the above optimization. Note, however, that given any doterministic map f : X' + X, one employs a (different form of) cost c: e: X' x X' - R20, where c(x, y) evaluates to only y = (*)) and otherwise evaluates to 1, is straightforward to see that the dynamics f* is the one that simultaneously optimizes c(2, v) for any X. In other words, this form of single-step cost uniquely identifies the (deterministic) dynamics by defining its evaluation at each state (see Figure 3 (Left)).
In contrast, when one wishes to constrain or regularize the dynamics globally in the (spatio-temporal) spectrum domain, to obtain the set of stable dynamics for example, single-step costs become powerless. Intuitively, while cumulative cost can effectively determine or regularize one-step transitions towards certain state, the Koopman spectrum cost can characterize the dynamics globally (sce Figure (Right)). Refer Appendix C for more formal arguments.
Although aforementioned facts simple, they give some insights the limitation of the use of (cumu- lative) single-step cost for characterizing dynamical systems, and imply that enforcing certain constraints on the dynamics requires the Koopman spectrum perspective. This is similar to the problems treated in the Fourier analysis; where the global (spectral) characteristies of the sequential data are better captured in the frequency domain.
Lastly, we depicted how the spectrum cost differs from other types costs used in decision making problems in Figure 2. The figure illustrates that the spectrum cost is not incurred single-step one trajectory

---

Published in Transactions on Machine Learning Research (6/ (6/2024)
X-Y trajectory
Cart velocity trajectories
1.5
6.0
1.0
velocity
0.5
0.0
2.0
-05
0.0
-1.0
-1
0
1
2
20
40
60
80
100
IF
timesteps
no spectrum cost
with spectrum cost
Figure 4: Left: We minimize solely for Koopman spectrum cost (( = ||m m' || to imitate the top mode of reference spectrum to recover desired limit cycle behavior for the single-integrator system. Right: By regularizing the spectral radius of Cartpole with cumulative cost that favors high velocity, the cartpole performs stable oscillation rather than moving off to infinity.
Joint trajectories (no spectrum cost)
Joint trajectories with spectrum cost
1.0
1.0
0.0
0.0
values
values
-1.0
-1.0
-2.0
-2.0
-3.0
200
300
100
200
300
timesteps
timesteps
Figure 5: The joint angle trajectories generated by a combination linear and RFF policies. Left: when only cumulative reward maximized. Right: when both the cumulative cost and the spectrum cost A(of) = E [Ar(e/) are used, where the factor 5 is multiplied to balance between the spectrum cost and the cumulative cost.
(episode), but is over (part of) the global properties of the dynamical system model (see also Remark 3.2). The dynamics typically corresponds to policy, but policy regularization cost used in, for example (Haarnoja et al., 2018), is computable when given the current policy while the spectrum cost is unobservable if the dynamics is unknown (and hence is not directly computable).
3.3 Simulated experiments
We illustrate how one can the costs in Example 3.1. See Appendix H for detailed descriptions and results of the experiments. Throughout, used Julia language (Bezanson al., 2017) based robotics Cross- control package, Lyceum (Summers et al., 2020), for simulations and visualizations. Also, Entropy Method (CEM) based policy scarch (Kobilarov (2012); one of the population based policy scarch techniques) to optimize the policy parameter O to minimize the cost in (3.2). Specifically, al each iteration of CEM, we generate many parameters (Os) to compute the loss (i.e., the sum of the Koopman spectrum cost and negative cumulative reward). This achieved by fitting the transition data the chosen feature space estimate its (fiite-dimensionall realization of) Koopman operator (see Appendix H.1); here the data generated by the simulator which assume to have access to.

---

Published in Transactions on Machine Learning Research (6/2024)
Imitating target behaviors through the Koopman operators
We consider the limit cycle dynamics
i r= ( 0-1,
described by the polar coordinates, and find the Koopman operator for this dynamics by sampling transitions, assumiing H is the span of Random Fourier Features (RFEs) (Rahimi & Recht, 2007). We illustrate how KSNR is used to imitate the dynamics; particular, by imitating the Koopman modes, we expect that some physically meaningful dynamical behaviors of the target system can be effectively reconstructed.
To define Koopman modes, suppose that the Koopman operator of induced by the target dynamics has eigenvalues X C and eigenfunctions & : X C for i E (1, d i.e,
d d
If the set of observables o,s satisfies
dg Φ Σ (
for m E Cds,, where oR == (x))x,, 02(),, La (x) E Rd,, then m s are called the Koopman modes. The Koopman modes are closely related to the concept isostable; interested readers are referred to (Mauroy et al., 2013) for example.
In this simulated example, the target system is being imitated by forcing the generated dynamics to have (approximalely) the same top mode (i.e., the Koopman modes corresponding to the largest absolute eigen- value) that dominates the behavior. To this end, with IT a space of RFF policies that define 7 and 0 as a single-integrator model, we solve KSNR for the spectrum cost A(or) = |mm m=Il,, where m E Cde and m are the top modes of the Koopman operator induced by the generated dynamics and of the target Koopman operator found previously, respectively.
Figure (Left) plots the trajectories (of the Cartesian coordinates) generated by RFF policies that minimize this cost; it is observed that the agent successfully converged to the desired limit cycle of radius one by imitating the dominant mode of the target spectrum.
Generating stable loops (Cartpole) We consider Cartpole environment (where the rail length is ex- tended from the original model). The single-step reward (negative cost.) is 10-3/o| where e is the velocity of the cart, plus the penalty -1 when the pole falls down (i.e., directing downward). This single-step reward encourages the cartpole to maximize its velocity while preferring not to let the pole fall down. The additional spectrum cost considered in this experiment is A(of)= = 10 max(1, p(sf)) which highly penalizes spectral radius larger than one; it therefore regularizes the dynamics to be stable, preventing the velocity from ever increasing its magnitude.
Figure 4 (Right) plots the cart velocity trajectories generated by RFF policies that (approximately) solve KSNR with/ without the spectrum cost. It is observed that spectral regularization lod to a back-and-forth motion while the non-regularized policy preferred accelerating to one direction to solely maximize velocity. When the spectrum cost was used, the cumulative rewards were 0.072 and the spectral radius was 0.990, while they were 0.212 and 1.003 when the spectrum cost was not used; limiting the spectral radius prevents the ever increasing change in position.
We mention that this experiment is not intended to force the dynamics to have this oscillation, but rather to let the dynamics be stable in the sense that the Koopman operator over a chosen space has spectral radius that is less than or equal to one (see Figure to review the difference of concepts and roles of cumulative cost and Koopman spectrum cost). See more experimental results in Appendix
Remark 3.3 (Remarks on the stability regularization). As mentioned in Section 2, this stability regular- ization not meant to learn the stable Koopman operator but to find an RDS that balances the cumulative cost and the spectrum cost that enforces stability; in other words, the task is to find dynamical system that minimizes the cumulative cost under the hard stability constraint encoded by the spectrum cost. Here,
9

---

Published in Transactions on Machine Learning Research (6/20) (6/2024)
10
-0
-5 -0
10
Figure 6: Examples of attractor dynamics that are stable; from the left, they are a fixed-point attractor, limit cycle attractor, and strange attractor. Those should be included the set of stable dynamics.
we emphasize that the set of stable dynamics should include a variety dynamics ranging from a fixed-point attractor to strange attractor as portrayed in Figure 6. On the other hand, constraining dynamics by a single control Lyapunov function (cf. Freeman & Primbs (1996)) will form strictly smaller set of stable dynamics (see the discussions in Section 3.2 well). Also, in this simulation example, the stability does not necessarily mean the behaviors converging to the zero state as long as the velocity does not increase indefinilely, and the preference of keeping the pole straight up is encoded by the cumulative cost lerm instead.
Generating smooth movements (Walker) We use the Walker2d environment and compare movements with/withond the spectrum cost. The single-step reward (negative cost) is given by 0-0000 [/00///a| where is the velocity and is the action vector of dimension 6. The spectrum cost is given by A(oo) = 5 Ein [l((o/)) where the factor 5 is multiplied to balance between the spectrum and cumulative cost. The single-step reward encourages the walker to move to the right as fast as possible with a small penalty incurred on the action input, and the spectrum cost regularizes the dynamics have fewer dominating modes, which intuitively leads smoother motions.
Figure 5 plots typical joint angles along trajectory generated by combination of linear and RFF policies that (approximately) solves KSNR with/withou the spectrum cost. Tt. is observed that the spectrum cost led to simpler (i.e., some joint positions converge) and smoother dynamics while doing the task sufficiently well. With the spectrum cost, the cumulative rewards and the spectrum costs averaged across four random seeds (plus-ming minus standard deviation) were 584 112 and 196 = 8.13. Without the spectrum cost, they were 698 = 231 and 310 38.6. We observe that, as expected, the spectrum cost. lower for KSNR while the classical cumulative reward is higher for the behavior generated by the optimization without spectrum cost. Again, we emphasize that reward, but rather showing effect of additional spectrum cost. Please also refer to Appendix H and for detailed results.
not competing against the MDP counterparts in terms of the cumulative
4 Theoretical algorithm of online KSNR and its insights on the complexity
In this section, present (thcoretical) lcarning algorithm for online KSNR. Although the KSNR itself is general regulator framework, need some structural assumptions to the problem in order to devise sample efficient (if not computation efficient) algorithm. Nevertheless, despite the unobservability of the spectrum cost, KSNR admits a sample efficient model-based algorithm through operator theoretic arguments under those assumptions. Here, "model-based" simply means we are not directly learning the spectrum cost itself but the Koopman operator model. We believe the algorithm and its theoretical analysis clarify the intrinsic difficulty of considering the spectrum cost, and pave the way towards future rescarch.
The learning goal is to find a parameter Ott that satisfies (3.2) al each episode / E [7]. We employ episodic learning, and let O be parameter employed at the t-th episode. Adversary chooses X := {(=6,n- Hy), (rá, ...,..., (10 H beginning of each episode. Let oh == et (1ha)) Zai chosen according to Pec.
H H) C X' x Zyo. where N Zyo. and the cost function c' at the
10

---

Published in Transactions on Machine Learning Research (6/2024)
Algorithm evaluation.
In this work, we employ the following performance metric, namely, the cumulative
regret:
T-1 Σ
N1 R
T-1
REGRETT == ([)))
Σ n=0
min Bell
+
Note the minimum on the second lerm the right hand side taken at every episode. Below, we present model assumptions and algorithm with regret bound.
4.1 Models and algorithms
We make the following modeling assumptions.
Assumption 1. Let (0) be the Koopman operator corresponding to parameter O Then, ossume that there erists a finite-dimensional subspace Ho X' over R and its basis 01s..., Pd such that the random dynamical system (3.1) satisfies the following:
AO E II, Vo E :
+e(W),
where the additive noise <((w) ~ N(0,0²) is assumed to be independent across timesteps, porameters O and indices i.
Remark 4.1 (On Assumption 1). Although the added noise term is expected to deal with stochasticity and misspecification to some extent in practice, Assumption 1 is strong to ask for; in fact, claiming existence of the Koopman operator over a useful RKHS (e.g., with Gaussian kernel) not trivial for most of the practical problems. Studying misspecified case with small error margin is an important future direction of research; however, as our regulator problem is novel, we believe this work guides the future attempts of further algorithmic research.
Assumption 2 (Function-valuee RKHS (see Appendix A for details)). A (-)Ø for & H is assumed to live in known function valued RKHS with the pmerator-valuch reproducing kernel K(,,)) II II L(H; H), equivalently, there exists known map V : II L(H:H)) for specific Hilbert space H' satisfying for any & E H. there exists vb E H' such that
{()o = (.)
(4.1)
Remark 4.2 (On Assumption 2). The assumption intuitively states that the structure on how the closeness of parameters θs relates to that the resulting Koopman operators known. One can always consider an expressive function-valued RKHS practice, but may lead increased (effective) dimensions that will require more samples learn.
When Assumption 2 holds, we obtain the following claim which is critical for our learning framework. Lemma 4.3. Suppose Assumption 2 holds. Then, there exists a linear operator M* H + H' such that
* x()) = ( M
In the reminder of this paper, we work on the invariant subspace Ho in Assumption and thus we regard H = Ho ž Tede, L(H; z Rdaxds, and, by abuse of notations, we view X X(O) the realization of the operator over Rdo, i.e.
F x(0) + +e(w)
(v)) M + +e(w),
where Φ = (x),,,,, 02(x) ... Sa (x))T Rdo, and ((w) (2(ww, ed (w)]T Rd.
Finally, we assume the following.
Assumption 3 (Realizability of costs). For allt, the single-step cost d known and satisfies c' cxxx) w(().) for some known map w' RR R2o-
11

---

Published in Transactions on Machine Learning Research (6/2024)
Algorithm Koopman-Spectrum LC3 (KS-LC")
Require:
Parameter set II; regularizer À
1: Initialize BALL to be a set containing M*.
2: for = O...T do
Adversary chooses Xj-
Or, M, arg minlen, MEBant', A(V(O)) M] + (X;:
5: Under the dynamics Fd sample transition data r² [ where 7 (1 1
Update BAL
end for
Remark 4.4 (On Assumption 3). As mentioned in Remark 3.2, the space No over which the Koopman operator is acting should be properly chosen so that the Koopman operator exists and that its spectrum cost has desirable regularization effect over the dynamics. At the same time, Assumption 3 requires that Ho is sufficiently expressive in the sense that can capture the immediate cost c².
For later use, we define, for all t E [T], n E [N*,, and h E [Ha]: Ahi E (C(H; and x E L(H by
(M, (0 M| (Doh...
(M) (OO) M.
Remark 4.5 (Hilbert-Schmidt operators). Both oh and 5 are Hilbert-Schmidt operators because the ranges H and L(H; () are of finite dimension. Note, in case H' is finite, we obtain
()ew). (()) M' +((w) = ( @ veo)))ve (M') + +e(w),
(4.2)
where vee is the vectorization of matrix.
With these preparations in mind, proposed information theoretic algorithm, which is an extension of LC3 to KSNR problem (estimating the true operator M*) is sunmarized in Algorithm 1. This algorithm assumee the following oracle.
Definition 4.1 (Optimal parameter oracle). Define the oracle, OptDynamics, that computes the minimiza- tion problem (3.2) for any X, Xo: A and satisfying Assumption 3.
4.2 Information theoretic regret bounds
Here, we present the regret bound analysis. To this end, we make the following assumptions. Assumption 4. The operator A satisfies the following (modified) Hölder condition:
3L E R20, 3a E (0, 1], Vol E EH, H), EI
|A (+)] & L max { (1 x 1| - [())1²
Further, we assume there erists constant Amax 2 0 such that, for any O E 11 and for any M e BALLY
(()( o Ml S Amax-
Remark 4.6 (On Assumption 4). This assumption does not preclude practical examples such matrix norms (because of the triangle inequality) and the spectral radius described below. However, we note that the spectrum cost in Section 3.3 used for top mode imitation, namely, A(o/) = || -milla does not satisfy this (modified) Hölder condition in general; therefore this cost might not be used for K
For example, for spectral radius P, the following proposition holds using the result from (Song, 2002, Corollary 2.3).
See Appendix B for the definitions the values in this algorithm.
12

---

Published in Transactions on Machine Learning Research (6/2024)
Proposition 4.7. Assume there crists constont Amax 0 such that, for any E II and for any M E BALL M. (() o M) S Amax. Let the Jordan condition namber of X (()) be the following:
: sup inf (1100)))1Q((0)*11 (1000))))) (()),
een 2())
where ( is Jordan canonical form of X (@) transformed by nonsingular matris (()). Also, let be the order of the largest Jordan block. Then, if < 0o, the cost A(al) p(off satisfies the Assumption 4 for
L L:= (1+)) Vo
m
Note when X x()) is diagonalizable for all θ a
Assumption 5. For every t, adversary chooses No trajectories such that ( satisfies that the smallest eigencalue of En=o Dxb... zo, is bounded below by some constant C > 0. Also, there erists a constant H E Zyo such that for every t, Enno H H.
Remark 4.8 (On Assumption 5). In practice, user may wait to end an episode until a sufficient number of trajectories collected in order for the assumption hold. Intuitively, this condition ensures that fitting the transition data over the feature space is not ill-posed. Note, this assumption does not preclude the necessity of exploration: If the sole purpose is just to fit the data for single paramcter O may not need well-designed exploration strategy in this case; however, because the smallest eigenvalue of Σn=v - - of 1 'o h.n is in general not bounded below by a positive constant, we still need careful design of exploration. We mention that this assumption plays a role in our regret analysis to simultaneously manage the cumulative cost and the spectrum cost through the use common confidence balls; note the former cares about each single-step transition while the latter deals with the global dynamical properties represented as the Koopman operator realized over given space.
The direct use of this assumption is highlighted by Lemma F.2 in Appendix F (derived from our positive operator norm bounding lemma; see Lemma F.1) which is used to basically bound the norm of difference between the true Koopman operator and the estimated one al each episode by the multiple of radius of the confidence ball.
We hope that this assumption can be relaxed by assuming the bounds on the norms of Φ and X (e) and by using matrix Bernstein inequality under additive Gaussian noise assumption.
Lastly, the following assumption is the modified version of the one made in (Kakade et al., 2020).
Assumption [Modified version of Assumption in (Kakade et al., 2020)} Assume there erists a constani Vmax such that, for every 1,
N
H1-1 -1 d (shan)
2
sup llll
Σ n=
Eas
Σ h=0
0, 0,
Vnax-
Remark 4.9 (On Assumption 6). This is slight modification of Assumption 2 in (Kakade et al., 2020) to adjust to our problem settings; this assumption does not state that the cost function is bounded over the state space but the second moment of realized cumulative cost is bounded, and the complexity depends on this bound.
Theorem 4.10. Suppose Assumption 1 to hold. Sel X
2 T Then, there exists an absolute constant
C1 such that, for all T, KS-LC (Algorithm 1) using Op tDymamiccs enjoys the following regret bound:
E 1S- [REGRETT] I Cidra dr2)
13

---

Published in Transactions on Machine Learning Research (6/2024)
where
11 = (1 mT, [1 + C- + (T. + Amax L) + C-1)),rr + +Agux + 1.2]
d;22 = o7 H V max of + ds + log(T)) = H)
B1.T o² (d log + Tr,d/),
B2T = o ((d + log(T) + nT, (2,T,a))
Here, YT 72, and TT. are the expected mazimum information gains that scale with T under practical settings (see Appendir B for details).
Remark 4.11 (On the order). We note that, when 1, we obtain the order of Ö(VT).
Remark 4.12 (On the adversary). In our setting, the adversary only chooses the initial states, their time horizons, and the immediate cost function. The trajectories themselves are generated by the learner's s parameter O. Although the regret bound given above is valid if the assumptions hold regardless of the adversary, a caveat here is the bound H and max appearing in the regret bound can potentially depend on the choice of the adversary.
The proof techniques include our positive operator norm bounding lemma (see Lemma F.1 in Appendix F); which is another crucial operator theoretic lemma in this work in addition to Lemma 4.3.
4.3 Relations to the kernelized nonlinear regulator and to eigenstructure assignments
First, we mention that our theoretical results apply some of the techniques developed in the work of KNR; and in fact, additional theoretical arguments that necessitated for KSNR framework highlight the essential difference of our framework from the MDP counterpart.
As mentioned in Remark 4.1, for given dynamics described by the system model studied in the KNR (i.e., the transition map from the current state and control to the next state is in a known RKHS), the existence of a (fiitteddimensionaa) space Hy in Assumption that can represent the given cumulative cost is in general not guaranteed. As such, the system model considered this section no more general than that of the KNR (although our spectrum cost formulation is indeed generalization of that of the KNR). Now, we consider the finite dimensional description (sec (4.2)) for simplicity. The equation (4.2) can be rewritten by
)FF(1 = (T s vTc(M+)T) vec [ <(w),
and is a special case of the system model of the KNR.
We see that the model associated with our spectrum cost formulation reduces the eigenstructure assign- ment problem for the lincar systems described by
Ad + Bug + AE Rd B BRdxxxx ~~ e
Th+1
where u E du is a control input. In particular, considering the feedback policy in the form of uy = Kry where E Rduxdx (or θ = K in this casc), the system becomes Th+1 = (A + BK)aa + c. By letting Ho be Rdx where the canonical basis is taken and by properly designing (O) (see Appendix G), our system model reduces to the linear case. The spectrum cost may be designed not only constrain the eigenstructure but also balance with the cumulative single-step cost in our framework as well.
4.4 Simulated experiments
Linear case: as eigenstructure assignment problem First, to demonstrate the correctness of our the- oretical algorithm, we consider a linear system case. In partieular, the following simple system considered:
Th+l Ihh + At uh.
14

---

Published in Transactions on Machine Learning Research (6/ (6/2024)
spectrum cost curve
estimated spectrum cost curve
2.0
spectrum cost
spectrum cost
10
1.00
6.00
4.00
0.0
2.00
-1.0
0.00
0.00
-0.50
2
5
9
13
5
9
13
episodes
episodes
Ground truth
Learned trajectory
Figure 7: Linear system imitation (as eigenstructure assignment) by KS-LC3 using the spectrum cost A(al) [I(T + 0.05K*) (A BK) BK)l (where A and B are extracted from sf). Left: ground-truth linear system position trajectory and a trajectory generated by the learned model with KS-LO3, We see both overlap exactly, indicating that the algorithm learned the feedback matrix properly. Middle: The spectrum cost curve evaluated approximately using the current trajectory data. Right: The estimated spectrum cost curve obtained by using the current estimate M.
where At = 0.05. The target linear system is given by
Th+1 (I + 0.05K*) sh:
where
2
4 2
K =
enforces that the parameter θ (which feedback matrix K in this case) generates the dynamical system that follows this target linear dynamics; where A and B are matrices that are part of the Koopman operator to learn (see Section 4.3). Figure plots the result showing that the trajectories generated by the ground-truth target linear system and by the learned model match almost exactly, and that the spectrum cost decreases along episodes. The spectrum cost curve evaluated approximately using the current trajectory data is given in Figure 7 (Middle). Note the curve is averaged across four random seeds and across episode window of size four. Additionally, the estimated spectrum cost curve obtained by using the current estimate M plotted in Figure (Right).
The spectrum cost given by |[4==00510'-
Cartpole problem with reduced policy space We again consider a Cartpole environment for KS-LC3 To reduce the policy search space, we compose three pre-trained policies to balance the pole while 1) moving the cart position p to -0.3 and then to 0.3, 2) moving the cart with velocity velocity u == 1.5. We also extract the Koopman operalor of for the first. policy. Then, we let II to be the space of linear combinations of the three policies, reducing the dimension of θ We let the first four features di (x: to (x) be 2i I4, where [x ..l.....,,,,, x4] the state, and the rest be RFFs.
1.5,, 3) moving cart with
The single-step cost given by 10-1(1u] 1.5)² plus the large penalty when the pole falls down (i.e., directing downward), and the spectrum cost is A(of) = ||,[[1 4, - .f 4, :l: + 0.01 D (A(())) where [f 4, ]] E dx is the first four rows of sf; this imitates the first policy while also regularizing the spectrum.
When CEM used to (approximately) solve KSNR, the resulting carl position trajectories are given by Figure 8 (Left). With the spectrum cost, the cumulative costs and the spectrum costs averaged across four random seeds were 0.706 + 0.006 and 2.706 + 0.035. Without the spectrum cost, they were 0.428 + 0.045 and 3.383 + 0.604.
We then use the Thompson sampling version of KS-LC3; the resulting cart position trajectories are given by Figure (Left) well, and the spectrum cost curves are also shown. It is observed that the addition of the spectrum cost favored the behavior corresponding to the target Koopman operator to oscillate while balancing the pole, and achieved similar performance to the ground-truth model optimized with CEM.
15

---

Published in Transactions on Machine Learning Research (6/20) (6/2024)
Cart position trajectories
spectrum cost
estimated spectrum cost
5,00
cart position
6.0
spectrum cost
4.00
spectrum cost
4.0
3.50
4.00
3.00
3.00
2.0
2.50
0.0
2.00
2.00
100
200
300
400
500
13
17
13
17
timesteps
episodes
episodes
nn spectrum cost (CEM)
with spectrum cost (CEM)
with spectrum cost (learn)
Figure Cartpole imitation by KS-LC3 using the spectrum cost A(a)) = || [4:])=/1p 44
0.01 Den |ax(a)) Left: Cart position trajectories with/ with// the spectrum cost with CEM on a known model versus the learned model with KS-LCS. Middle: The spectrum cost curve evaluated approximately using the current trajectory data. Right: The estimated spectrum cost curve obtained by using the current estimate M.
5 Discussion and conclusion
This work proposed a novel paradigm of regulating (controlling) dynamical systems, which we refer to Koopman Spectrum Nonlinear Regulator, and presented an information theoretic algorithm that achieves a sublinear regret bound under model assumptions. We showed that behaviors such as limit cycles interest, stable motion, and smooth movements are effectively realized within our framework, which an effective generalization of classical eigenstructure (pole) assignments. In terms of learning algorithms, we stress that there is significant potential of future work for inventing sophisticated and scalable methods that elicit desired and interesting behaviors from dynamical systems. Our motivation of this work stems from the fact that some preferences over dynamical systems cannot be encoded by cumulative single-step cost based control/learning algorithms; we believe that this work enables a broader representation of dynamical properties that can enable more intelligent and robust agent behaviors.
6 Limitations
First, when the dynamical systems of interests do not meet certain conditions, Koopman operators might not be well defined over functional spaces that can be practically managed (e-g- RKHSs). Studying such conditions is an on-going research topic, and we will need additional studies of misspecified cases where only approximately invariant Koopman space is employed with errors.
Second, to solve KSNR, one needs heuristic approximations when the (policy) space IT or the state space X' is continuous. Even when the dynamical system model is known, getting better approximation results would require certain amount of computations, and additional studies on the relation between the amount of computations (or samples) and approximation errors would be required. Also, studying a better heuristic algorithm that is well suitod our problem to robustly scale the methodology more complicated domains is indeed an interesting direction of research.
Third, KS-LO3 requires several assumptions for tractable regret analysis. It is again somewhat strong to assume that one can find Koopman invariant space H. Further, additive Gaussian noise assumption may not be satisfied exactly in some practical applications, and robustness against the violations of the assumptions is an important future work. However, we stress that we believe the analysis of provably correct methods doepens our understandings of the problem. Eventually, we hope our framework will match the maturity of the MDP counterpart, for example by studying gradient- pradient-based algorithms that scale better the more complicated domains and their theoretical analysis with sample complexity guarantee.
16

---

Published in Transactions on Machine Learning Research (6/2024)
Lastly, note that empirical experiment results only conducted simulators; apply to real robotics problems, need additional studies, such as computtaiion-accuraey trade-off, safety /robustness issues, and canulation-to-rall if necessary. Also, balancing between cumulaatve cost and the Koopman spectrum cost is necessary to avoid unexpected negative outcomes.
7 Broader impact statement
The work, along with other robotics/control literature, encourages the further automation of robols; which would lead to loss of jobs that are currently existent, or may lead to developments of harmful military robots. Further, when our proposed framework requires additional (computational or other) resources, it would benefit entities with larger amount of such resources. Also, there is always a risk of robots misbchaving under partially unknown environments under adversarial attacks.
However, overall, believe our work alone does not immediately carry significant risk of harm. Moreover, we stress that the use of the Koopman spectrum cost has no implications on "good" and "bad" about any particular human behaviors.
Acknowledgments
We thank the constructive comments by anonymous reviewers for improving this work. Motoya Ohnishi thanks Colin Summers for instructions on Lyceum. Kendall Lowrey and Moloya Ohnishi thank Emanuel Todorov for valuable discussions and Roboti LLC for computational supports. This work of Motoya Ohnishi, Isao Ishikawa, Masahiro Tkoda, and Yoshinobu Kawahara was supported by JST CREST Grant Number JPMJCR1913, including AIP challenge program, Japan. Also, Motoya Ohnishi is supported in part by Funai Overseas Fellowship. Sham Kakade acknowledges funding from the ONR award N00014-18-1-2247.
References
Abraham and T. D. Murphey, Active learning of dynamics for data-driven control using Koopman oper- ators. IEEE Trans. Robotics, 35(5):1071-1083, 2019.
E. Akindji, J. Slipantschuk, O. Bandtlow, and W. Just. Convergence properties of dynamic mode decom- position for analytic interval maps. arXiv preprint xrXi::444400851,, 2024.
A. N. Andry, E. Y. Shapiro, and J. C. Chung. Eigenstructure assignment for linear systems. IEEE Trans. Aerospace and Electronic Systems, (5):711-729, 1983.
L. Arnold. Random dynamical systems. Springer, 1998.
Z. Beheshti and S. M. Н. Shamsuddin. A review of population-based meta-heuristi algorithms. Int. j. adv. soft comput. appl, 5(1):1-35, 2013.
J. Bezanson, A. Edelman, S. Karpinski, and V. B. Shah. Julia: A fresh approach to mumerical computing. STAM review, 59(1):65-9)))) 98, 2017.
Brault, M. Heinonen, and Buc. Random Fourier features for operator-valued kernels. In Proc. ACML, pp. 110- 125, 2016.
G. Brockman, V. Cheung, L. Pettersson, J. Schneider, J. Schulman, J. Tang, and W. Zaremba. OpenAi Gym. arXiu preprint ww..i:160660111 2016.
D. Burov, D. Giannakis, K. Manohar, and A. Stuart. Kernel analog forecasting: Multiscale test problems. Multiscale Modeling & Simulation, 19(2):1011 1040, 2021.
M. J. Colbrook and A. Townsend. Rigorous data-driven computation of spectral propertics of Koopman operators for dynamical systems. Communications on Pure and Applied Mathematics, 77(1):221-25) -233, 2024.
17

---

Published in Transactions on Machine Learning Research (6/2024)
M. J. Colbrook, L. J. Ayton, and M. Szöke. Residual dynamic mode decomposition: robust and verified Koopmanism. Journal of Fluid Mechanics, 955:A21, 2023.
N. Crnjarié-Zic, S. Maćesić, and I. Mezić. Koopman operator spectrum for random dynamical systems. Journal of Nonlinear Science, pp. 1-50, 2019.
S. Curi, F. Berkenkamp, and A. Krause. Efficient model-based reinforcement learning through optimistic policy search and planning. arXiv preprint vrXi:2006608668) 2020.
B. Eysenbach, A. Gupta, J. Ibarz, and S. Levine. Diversity all you need: Learning skills without a reward function. arXiv preprint orX1w:1802.06171 2018.
A. Freeman and J. Primbs. Control Lyapunov functions: New ideas from an old source. In IEEE Proc. CDC, volume 4, pp. 223-1, 1996.
M. Ghil, M. D. Chekroun, and E. Simonnet. Climate dynamics and fluid mechanics: Natural variability and related uncertainties. Physica D: Nonlinear Phenomena, 237(14-17):111 22222, 2008
L. Grafakos. Classical Fourier analysis, volume 2. Springer, 2008.
T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In Proc. ICML, pp. 1861-1870, 2018.
M. Hemati and H. Yao. Dynamic mode shaping for fluid flow control: New strategies for transient growth suppression. Tn 8th ATAA Theoretical Fluid Mechanics Conference, pp. 3160, 2017.
J. Ibarz, J. Tan, C. Finn, M. Kalakrishnan, P. Pastor, and S. Levine How to train your robot with deep reinforcement learning: lessons we have learned. International Journal of Roboties Research, 40(4-5): 698-721, 2021.
A. Tjspeert, J. Nakanishi, and S. Schaal. Learning attractor landscapes for learning motor primitives. Proc. NewrIPS, 15, 2002.
M. Ikeda, Ishikawa, and C. Schlosser. Koopman and Perron Frobenius operators on reproducing kernel Banach spaces. Chaos: An Interdisciplinary Journal of Nonlinear Science, 32(12), 2022.
Tshikawa. Bounded composition operators on functional quasi-Banach spaces and stability of dynamical systems. Advances in Mathematics, 424:109048, 2023.
Ishikawa, K. Fujii, M. lkeda, Y. Hashimoto, and Y. Kawahara. Metric on nonlinear dynamical systems with
operators. In Proc. NeurIPS, pp. 2856-2866. 2018.
Ishikawa, Y. Hashimoto, M. Ikoda, and Y. Kawahara. Koopman operators with intrinsic observables in rigged reproducing kernel Hilbert spaces. arXiv preprial ar urXiv:2403.0253 025224 2024.
T. Iwata and Y. Kawahara. Neural dynamic mode decomposition for end-to-end modeling of nonlinear dynamics. 27Xiv:2012.0619. 2020.
N. Jiang, A. Krishnamurthy, A. Agarwal, J. Langford, and R. E. Schapire. Contextual decision processes with low Bellman rank are PAC-learnable. In Proc. ICML, pp. 1704 1713, 2017.
H. Kadri, E. Duflos, P. Preux, S. Canu, A. Rakotomamonjy, and J. Audiffren. Operator-valued kernels for learning from functional response data. Journal of Machine Learning Research, 17(2))11-54, 2016.
E. Kaiser, J. N. Kutz, and S. Brunton. Data-driven discovery of Koopman eigenfunctions for control. Machine Learning: Science and Technology, 2021.
S. Kakade, A. Krishnamurthy, K. Lowrey, M. Ohnishi, and W. Sun. Information theoretic regret. bounds for online nonlinear control. Proc. NeurIPS, 2020.
Y. Kawahara. Dynamic mode decomposition with reproducing kernels for Koopman spectral analysis.
Proc. NewrIPS, 29:911-918 2016.
18

---

Published in Transactions on Machine Learning Research (6/2024)
J. Kober and J. Peters. Imitation and reinforcement learning. IEEE Robotics 8 Automation Magazine, 17 (2):55 62, 2010.
J. Kober, A. Wilhelm, E. Oztop, and J. Peters. Reinforcement learning to adjust parametrized motor primitives new situations. Autonomous Robots, 33:361-379, 2012.
J. Kober, J. A. Bagnell, and J. Peters. Reinforcement learning in robotics: A survey, International Journal of Robotics Research, 32(11):1238-1274, 2013.
M. Kobilarov. Cross-entropy motion planning. International Journal of Robotics Research, 31(7):855 871, 2012.
B. O. Koopman. Hamiltonian systems and transformation in Hilbert space. Proc. National Academy of Sciences of the United States of America, 17(5):315, 1931.
M. Korda and Mezić. Linear predictors for nonlinear dynamical systems: Koopman operator meets model prodictive control. Automatica, 93:1 13:149-160, 2018.
M. Korda and 1. Mezić. Optimal construction of Koopman eigenfunctions for prediction and control. 1EEE Trans. Automatic Control, 65112):5114-5129, 2020.
J. N. Kutz, S. L. Brunton, B. W. Brunton, and J. L. Proctor. Dynamic mode decomposition: Data-driven modeling of complex systems. STAM, 2016.
Y. Li, H. He, J. Wu, D. Katabi, and A. Torralba. Learning compositional Koopman operators for model-based control. arXiv preprint 11:0:99000000 2019.
Mamakoukas, Abraham, and T. D. Murphey. Learning stable models for prediction and control. 1EEE Trans. Robotics, 2023.
G. Manek and J Zico Kolter. Learning stable deep dynamics models. Proc. NewrIPS, 2019.
H. Mania, M. I. Jordan, and B. Recht. Active learning for nonlinear system identification with guarantcos. arXiv preprint reXic:2006.1027 2020.
A. Mauroy and I. Mezić. Global stability analysis using the eigenfunctions of the Koopman operator. IEEE Trans. Automatic Control, 61(11):3356 3369, 2016.
Mauroy, T. Mezić, and J. Moehlis. Isostables, isochrons, and Koopman spectrum for the action action-angle representation stable fixed point dynamics. Physica Nonlinear Phenomena, 261:19 30, 2013.
A. Mauroy, Y. Susuki, and Mezić. The Koopman operator in systems and control. Springer, 2020.
1. Mezić. Spectral properties of dynamical systems, model reduction and decompositions. Nonlinear Dy- namics, 41:309 325, 2005.
V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, Antonoglou, D. Wierstra, and M. Riedmiller. Playing Atari with deep reinforcement learning. arXiv preprint 1312::1312.5602, 2013.
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529 533, 2015.
H. Nakao. Phase reduction approach to synchronization of nonlincar oscillators. Contemporary Physics, 57 (2):188-20) 214, 2017.
A. Y. Ng and S. J. Russell. Algorithms for inverse reinforcement learning. In Proc. ICML, volume 1, 2000.
J. Peters and S. Schaal. Reinforcement learning motor skills with policy gradients. Neural networks, 21 (4):682 697, 2008.
19

---

Published in Transactions on Machine Learning Research (6/2024)
R. Pintelon and J. Schoukens. System identification: frequency domain approach. John Wiley & Sons, 2012.
A. Rahimi and B. Recht. Random features for large-scale kernel machines. Proc. NewrIPS, 2007.
A. Rajeswaran, K. Lowrey, E. Todorov, and S. Kakade. Towards generalization and simplicity in continuous control. Proc. NewrIPS, 2017.
A. Sabanovic and K. Ohnishi. Motion control systems. John Wiley & Sons, 2011.
M. Simchowitz and Foster. Naive exploration is optimal for online LQR. In Proc. ICML, pp. 8937 8948, 2020.
Y. Song. A note on the variation of the spectrum of an arbitrary matrix. Linear algebra and its applications, 342(1-3):41144, 2002.
S. H. Strogatz. Nonlinear dynamics and chaos with student solutions manual: With applications to physics, biology, chemistry, and engineering. CRC press, 2018.
F. Stulp and O. Sigaud. Robot skill learning: From reinforcement learning to evolution strategies. Paladyn, Journal of Behavioral Robotics, 4(1):99 61, 2013.
F. Stulp, L. Herlant, A. Hoarau, and G. Raiola. Simultaneous on-line discovery and improvement of robotic skill options. In IEEE/RSJ IROS, pp. 1408-1413, 2014.
C. Summers, K. Lowrey, A. Rajeswaran, S. Srinivasa, and E. Todorov. Lyceum: An efficient and scalable ecosystem for robot learning. In Learning for Dynomics and Control, pp. 793-803. PMLR, 2020.
W. Sun, N. Jiang, A. Krishnamurthy, A. Agarwal, and J. Langford. Model-basod RL in contextual decision processes: PAC bounds and exponential improvements over model-free approaches. In Proc. COLT, pp. 2898 2933, 2019.
N. Takeishi and Y. Kawahara. Learning dynamics models with stable invariant sets. Proc. AAAT, 2021.
Y. Tassa, Y. Doron, A. Muldal, T. Frez, Y. Li, D. L. Casas, D. Budden, A. Abdolmaleki, J. Merel, A. Lefrancq, et al. DeepMind Control Suite, arXiv preprint (.Xiv:1801000600 2018.
E. Todorov, T. Erez, and Y. Tassa. MuJoCo: A physics engine for model-based control. In TEFE/RS) RSSJ IROS, pp. 5026-5033, 2012.
Williams, A. Aldrich, and E. Theodorou. Model predictive path integral control: From theory to parallel computation. Journal of Guidance, Control, and Dynamics, 40(2):344-357 357, 2017.
A. T. Winfree. The Geometry of Biological Time. Springer, 2001.
20

---

Published in Transactions on Machine Learning Research (6/2024)
A Function-valued RKHS
Funetion-valued reproducing kernel Hilbert spaces (RKHSs) are defined below.
Definition A.1 (Kadri et al. (2016)). A Hilbert space (HK, (5 Hx) of functions from II a Hilbert space (H, (x) is called reproducing kernel Hilbert space if there is a nonnegative L(H: H.)valued kernel K on II x II such that:
1. θ K(O', O) belongs to Hx for all O' E Il and ø E H,
2. for every z HK, θ II and ø E H, (9, ((), )0) (9))), 0)
For function-valued RKHSs, the following proposition holds.
Proposition A.1 (Feature map (Brault et al., 2016)). Let H' be Hilbert space and V II L(H; H.). Then the operator W H' + H defined by [@)) := (O)),,, Vi E H' and vO E 11, is partial isometry from H' onto the reproducing kernel Hilbert space Hx with reproducing kernel ( θ1) = ((2)) (())) y9,, O2 E II.
Remark A.2 (Decomposable kernel). In practice, when the kernel K is given by k O2) = k(O,, A for some scalar-valued kernel k(O,, and for positive ceminiefinit operator A L(H, H), the kernel K is called decomposable kernel. For an RKHS of a decomposable kernel K, (4.1) becomes
decomposable kernel (Brault et al., 2016);
X (0)6 (S())) & B)b,
where ç: II + 7² is known (H" is some Hilbert space), and A = BBt, Further, to use RFFs, one considers shifl-invarianl kernel k(O,, O2).
B
Some definitions of the values
The value (XH; My in Algorithm defined by
N
H
Mc) = Σ En
d' O,
2=0
where the expectation taken over the trajectory following oman confidence ball at is given by
(V(e)t Md + c(w)).
Also the
1IN--1H-1
BALLYy = [
(M] (M -M) 10= 88x
BALL Ey = AI Σ
Σ
h=0
and D WI, where Byg = 2002 (ds + log
dec(E "ee((
and
1- 1-N H
M == arg min M
Σ
(MD) R
+ A M
n=0
h=0
Similar to the work (Kakade et al., 2020), we define the expected maximum information gains as:
log det (>
FI ( = 2 max EA
A
det (Σ))
21

---

Published in Transactions on Machine Learning Research (6/2024)
Here, det is properly defined functional determinant of bounded linear operator. Further,
[(nog
det (E'r) 27
(A) = 2 max AEA A det (2/)/
Also, we define
det (2:3e)
E MI, (A) = max BA Σ AI T 0r
log
A
det (2
Lemma B.1. Assume that (O)) E xde and that 1 S B T S Ba for all E [T],
E [N'], and h E [Hh]] and some By 2 0 and B 2 O. Them, Tht (A) = Oldadv log(1 + TT (BBB//)) and
( = O(dady log(1+ TBB /A)).
Proof. For "r (A), from the definition of Hilbert-Schmidt norm, we have
T-1N Hr
Σ
o $ shin
THB
and the result follows from too.
(Kakade et al., 2020, Lemma C.5). The similar argument holds for yr (A)
C Formal argument on the limitation of cumulative costs
In this section, we present a formal argument on the limitation of cumulative costs, mentioned in Section 3.2. To this end, we give the following proposition.
Proposition C.1. Let X R. Consider the set S of dynamics converging to some point in X. Then, for any choice of u E (0, set-valued map I + 2 10, and cost e of the form
0
(y E (x)),
c(z, v)
(otherwise),
we have (F) + Sj. Here, {F} are given by
arg Eq
Σ A=0
d 2o). 1,,,,,,000 +1,,,
Finds.
RoEX
Proof. Assume there exist v, set-valued map y and such that the set (F0] = Sy. Then, because Sy is strictly smaller than the set of arbitrary dynamics, it must be the case that Ero E X, Eyo E X, yo & J (xo). However, the dynamics f*, where f = yo and (x) = x, Vo E X' } is an element of Sy. Therefore, the proposition is proved.
Remark C.2 (Interpretation of Proposition C.I). Proposition C.1 intuitively says that the set of "stable dynamics" cannot be determined by specifying every single transition. This is because, the dynamics that does not follow any pre-specified transition can always be "stable".
Proof of Lemma 4.3
It easy to see that one can define a map Mo so that satisfies Mo(e) = ab such that Assumption 2 holds. Define
M = PMo.
22

---

Published in Transactions on Machine Learning Research (6/2024)
where P is the orthogonal projection operator onto the sum space of the orthogonal complement of the mill space of v()) for all O ET, namely,
Σ ker (
een
Also, define Pe by the orthogonal projection onto
kcr (1)())
Then, for any II, we obtain
Pe v(O))* X()),
where ot is the pseudoinverse of the operator d, and Po is linear. Let a, E IR and Φ1, th E H, and define o by
3- = PMolaa0 + b(2)) aPMoll01) bP
Because PMP Ma, follows that Per = for all e II, which implies
n
kerPe
n
ker (e))).
9Ell
eEnl
On the other hand, we have
+ E ker (O))))
Bell
Therefore, it follows that y 0, which proves that M is linear.
E Proof of Proposition 4.7
Fix θ IT and suppose that the eigenvalues A; (i == (1,))....do)) of (9) are descending order according their absolute values, i.e., |^ı] 2 |>a 2 ... 2 | Given of L(H: H), suppose also that the eigenvalues μr (i E I) of of are in descending order according to their absolute values. Let
ke = inf {I(((0)]] 2(0) (()) 2
(0)).
where 1(0) is Jordan canonical form of (()) transformed by nonsingular matrix ((0). Also, let
Re ==
max
me(l....de
Then, by (Song, 2002, Corollary 2.3), we have
||as| Aaill < 1m4 Aal <
Σ mi X Σ (Mm(() - A'l
S dg do + dd p) max nev delleer - H (+)l,, (Ne / ds) 1 - (1)
for any I and for some permutation n, where p E 21,2, ... dø} is the number of the Jordan block of ( and m (1.2...., dd} is the order of the largest Jordan block. Because v ddg- for any p (1, 2,....... .... d and because
1 VVTp maxt dd (Vdo) max { Kō
}} s dorier
max mE(
it follows that
- -00))==1100 = Paill
- k (1 + vdg - max {
x x -(()|
Since Ke 1 + K, simple computations complete the proof.
23

---

Published in Transactions on Machine Learning Research (6/2024)
F Regret analysis
Throughout this section, suppose Assumptions 1 to 6 hold. Note that Assumption 3 is required for OptDynamics. We first give the positive operator norm bounding lemma followed by another lemma based on it.
Lemma F.1 (Positive operator norm bounding lemma). Let H. be Hilbert space and A,, B, E ((H; (i e (1,2....,nh). Assume, for all E (1.2.....m)) n), that A, is positive definite. Also, assume B1 is positive definile, and for all i E
n), B, positive semiidefinite. Then,
Σ B A.B.
Σ B:
Σ
B A.B.
S max |A,
If A, = B,A, for all i E f1,2. .2,...,,,,.. n). then
-
[ AAB A.B
[ B:
(IABB))
Σ ArB.)
S max ||,, 111
Proof. Let c:= max; ||4 ||| Then, we have, for all i,
1 13,,,,1 || A 3 cAi,
from which it follows that
B, 13BBAAAB
Therefore, we obtain
Σ B 3 c >
B3 A.B.
(E, BB A.
From the assumptions,
exists and
[ΣB] B, )
Σ B B
(EB}
[ B A
3d.
from which obtain
-
Σ B A.B
[ Bi
Σ B A,B
A
Sc.
The second claim follows immediately.
7
Lemma F.2. Suppose Assumplions 1, 2, and 5 hold. Then, it follows that, for all L [T],
| / (M- M²) || +11+c)) (M-M") 12
Proof. Under Assumptions and 2, define 8 (CC(,,
7(): L(H; 7(1) by
N-118 11
8'(M) Mo
Σ
Σ
M=0
24

---

Published in Transactions on Machine Learning Research (6/2024)
-1 Also, define 2¹ = En=o In= Ahn thin and grt == B' Φ.. We have E = Vi = 2¹ (and thus
2x -V'2' and
Eg = AI + Σ L", E/ = XI +
y
==
7=0
From Assumption 5, we obtain, for all E [T], (gt)-1
exists and
NN-1 m
N
|((6))
Σ
S
Σ
o
o 0,00
Φ
S cc
h,
hm0
Therefore, using Lemma F.1 by substituting 7 and C to A, AI and y to B, it follows that
[ (> max {1,
m 111 $1+0
rEld]
and
| } (M M²) )²(l (2') (3 +
M M² )²²
s (E / (M M² (1(
= (2y))
- (M mT)
s <1 | ) (M- :
Here, the second equality used ||,r||2- = 1l .ett||
Now, let Et be the event M E BALL'M Assume nT=o gt. Then, using Assumption 4,
((x]++ (AL* + 1 (Xbi
(A[x x|x + (xbi jou (X)i
(0') - Al M²) + (Jor (X):c)) - Jo (Xo: (o::N))))) (0))
(|1x1(8) (9") - A|38' o s1'1l) +
oo (xt:))))))))
min L. max ||80 (M* - 1 1|² :||500 (MV* - 1/r))"
axtt- )10) 2Amax + (JØr (X):c)- - Jo (xi:
Nit;; )²)
term
termi
(F.1)
Here, the first inequality follows because we assumed Et and because the algorithm selects M and O such that
A o Mr + Jot (x6: M.;e)
S A Al o M + J (X:: M:,')
for any M E BALL'S and for any θ II. The third incquality follows from Assumption 4. Using Lemma F.2, we have
r (M* -
5 (E'z)² 2 (M- - -x7') (>*))) #|
< 31+
( (M - -xt")) 28 (-
< 1(1+
(1(2 (Σbr)} ) (Mr' T77") || + + 1 ( ar )1) |=
22 22
10 - (:-8).
25

---

Published in Transactions on Machine Learning Research (6/2024)
Therefore, if Eτ, it follows that
term min { r. (4 ( 1- + 13 max {|
(2/)))
||
8 (E -
|
2M
(F.2)
Then, we use the following lemma which is an extension of (Kakade et al., 2020, Lemman B.6) to our Hölder condition.
Lemma F.3. For any sequence of H and for any (0, 1|, have
min x (Σ'))) -
=1/ 2a
1 < 27
det (2/
1 + log
det (27)
Proof. Using x S 2 log(1 + x) for x E [0, 1],
min
(2x))
<
min
8
(5 )
1 1 1
(:: ||ll/|||
S
[l
t=0
min
20
Σ
2 log
1+ 20
(E
HS
Σ 2log
1 tr(((()))
(E
}}
T-1
< 2
log det
(T + 1 (F
1=0
< 20
log det
I + (1)
1
8 (Ebe)
a
det
[Σ
< 2 aa
(log det (I log det (Σ's))
<
27
log
det (Xgge
det. (E))
< 1o
1 log
det (2))
Here, the fifth incquality follows from (Grafakos, 2008, Exercise 1.1.4). Corollary F.4. For any sequence of z and for any E (0, 1], we have
Σ min max (1')) -311
det (Σ:
0 (xx)
< 27 -a
I + log
det [Σ0
26

---

Published in Transactions on Machine Learning Research (6/2024)
From (F.2) and Corollary F.4, obtain
T-1
E
term
t=0
E
min [4(1+ +1} max
{
(2
$
$11
(>
}
22 2A
1=0
E
+ + +1} 2Amax min
max
(x'
||
(
$ $10} (1)
+ (11
+ + 2A max [2]
min
max
(
||
+ + +1 + 2Amax 11]
Σ min max
||
( -
2cx
S VT value / TI a (2 (A)).
(F.3)
Here, the first inequality is due to (F.2); the third inequality uses B[ab] V [[b2) the forth inequality uses the Cauchy-Schwarla incquality; the last is from Corollary F.4. Also,
value = 1616 =66""(++-+))
(8L² + s 0² (2- (I² + Amax L1 [ + A max + I2²}.
C C +-) 4A + L2 + 4A max
for some constant C".
Next, we turn bound the latter term terma of (F.1); our analysis is based on that of (Kakade el al., 2020). Simple calculations show that
-1-
M - MM'M' A(2 (2% -
Hh Eh,n
h=0
where T, is the sampled noise at 7-th episode, h-th timestep, and n-th trajectory. Now, by introducing a Hilbert space containing an operator of L(C(H; H'); R), which a Hilbert-Schmidt operator, because of Assumption 1, we can apply Lemma C.4 in (Kakade et al., 2020) to our problem too. Therefore, with probability at least - de, it holds that.
(E* (M-M") M²) s A|IM (8dg log(5) 8 log(det (E's) 1
and properly choosing & leads to 8i defined in Section B, and obtain the result
1 2
Pr
U 1=0
g
In our algorithm, transition data are chosen from any initial states and the horizon lengths vary; however, slight modification of the analysis of LC will give the following lemma.
Lemma F.5 (Modified version of Theorem 3.2 in (Kakade et al., 2020)). Suppose Assumptions 1, 2, 3, 5, and 6 hold. Then, the term terma is bounded by
T
T T-1
termg 1=0
g
HV max V (dT + log(T) + ( + H) (T) H)MT(()))
27

---

Published in Transactions on Machine Learning Research (6/2024)
Combining all of the above results, we prove Theorem 4.10:
Proof of Theorem 4.10. Using (F.3) (which requires Assumptions 1, 4, and 5), Lemma F.5 (which requires Assumptions 1, 2, 3, 5, and 6), and Pr(Ui. gr S
1 it follows that
Es LC3 [REGRETT]
+ (I2 + Amax + C-11)[(3M) + A -[}}} V ( + log(T) tm, H) H)
v HVmax V B4T(ds log(T)
+ (Amax Vmax)
& CTT-- (dr,1 + dr.2),
for some absolute constant Ct. Therefore, the theorem is proved.
G Reduction to eigenstructure assignment problem for linear systems
To see how our system model studied in (4.2) reduces to linear system case, take Rdx as Ho with the canonical basis (i.c., Φ, = z) and let
(()) [Tax & Kj Iax @ kg.... ..... Lax 2 kixx Tax]"
where the feedback matrix is given by K = [ki, k2, ..... kaxl, and let
M [ a1] [bax Odx
where the entries of the row vector b, all zero except for the entries from the index (i 1)dxdur to the index du given by vec (BT), and A [a ag .... T.
28

---

Published in Transactions on Machine Learning Research (6/2024)
H Setups and results of simulations in the main body
Throughout the main body of this paper, used the following version of Julia; for cach experiment, the running time was less than around 10 minutes.
Julia Version 1.5.3
Platform Info:
OS: Linux (x86 6e-------inx--ggu
CPU: AMD Ryzen Threadripper 3990X 64-Core Processor
WORD_SIZE: 64
LIBM: libopenlibm
LLVM: 1ibLLVM-9.00 (ORCJIT, znver2)
Environment: MULRAADUMTHRREADS
JULIA_NUM THREADS = 12
The licenses of Julia, OpenAl Gym, DeepMind Control Suile, Lyceum, and MuJoCo, are [The MIT Li- cense; Copyright (c) 2009-2021: Jeff Bezanson, Stefan Karpinski, Viral B. Shah, and other contribu- (itiorutiiiilii/mootuuuttttsss [The MIT License; Copyright (c) 2016 OpenAI tors: https:/ htpps://githae [Apache License Version 2.0, January 2004 http://www.apache..o hrabbeese////cessss///// [The
MIT License; Copyright (c) 2019 Colin Summers, The Contributors of Lyceum], and [MuJoCo Pro Lab license], respectively.
In this section, we provide simulation setups, including the details of environments (see also Figure 9) and parameter settings.
Figure 9: Illustration of some dynamical systems have used in this work. Left: Simple limit cycle represented effectively by the Koopman modes. Middle: DeepMind Control Suite (Tassa et al., 2018) Cartpole showing stable cycle with spectral radius regularization. Right: OpenAT Gym (Brockman et al., 2016) walker2d showing simpler movement cycle when the Koopman cigenvalues are rogularized.
H.1 Cross-entropy method
Throughout, we used CEM for dynamics parameter (policy) selection to approximately solve KSNR. Here, we present the setting of CEM.
First, prepare some fixed feature (e.g. RFFs) for 6. Then, each iteration of CEM, generate many parameters to compute the loss (i.c., the sum of the Koopman spectrum cost and negative cumulative reward) by fitting the transition data generated by each parameter to the feature to estimate its Koopman operator d. In particular, we used the following regularized fitting:
s YX (XXT +1)-1
29

---

Published in Transactions on Machine Learning Research (6/2024)
Table 1: Hyperparameters used for limit cycle generation.
CEM hyperparameter
Value
Training target Koopman operator
Value
samples
200
training iteration
500
clite size
20
RFF bandwidth for Φ
3.0
iteration
50
RFF dimension dg
80
planning horizon
80
horizon for each iteration
80
policy RFF dimension
50
policy RFF bandwidth
2.0
where Y := ( #hg+1.2"
and X == [ Pangii"
P
If the feature spans a Koopman invariant space and the deterministic dynamical systems are considered, and if no regularization (i.e., the identity matrix I) is used, any sufficiently rich trajectory data may be used to exactly compute X (@) for O. However, practice, the estimate depends on transition data although the regularization mitigates this effect. In our simulations, at cach iteration, we randomly reset the initial state according to some distribution, and computed loss for each parameter generating trajectory starting from that state.
H.2 Setups: imitating target behaviors through Koopman operators
The discrete-time dynamics
Th+1 = Th + Ut, On+1 = 0, + ug
is considered and the policy returns Ur and vo, given rh and On. In our simulation, used At = 0.05. Note the ground-truth dynamics
i=r(1-r3 0 11
is discretized to
Th41 = rx (1-1))) At, Bxt1 = 0% + At.
Figure 10 plots the ground-truth trajectories of observations and x-y positions.
We trained the target Koopman operator using the ground-truth dynamics with random initializations; the hyperparameters used for training are sumnarized in Table 1.
Then, we used CEM to select policy so that the spectrum cost is minimized; the hyperparameters are also summarized in Table
We tested two forms of the spectrum cost; A1 (1 = |mmmmmm' m²I and = trajectories are plotted in Figure and 12, respectively. It interesting to observe that the top mode imi- tation successfully converged to the desirable limit cycle while Frobenius norm imitation did not. Intuitively, the top mode imitation focuses more on reconstruct ing the practically and physically meaningful behavior while minimizing the error on the Frobenius norm has no immediately clear physical meaning.
-f
The resulting
H.3 Setups: Generating stable loops (Cartpole)
We used DeepMind Control Suite Cartpole environment with modifications; specifically, we extended the cart rail to [-100, 100] from the original length [-5,5] 5] to deal with divergent behaviors. Also, we used a combination of lincar and RFF fcatures; the first elements of the feature are simply the observation (state) vector, and the rest are Gaussian RFFs. That way, we found divergent behaviors were well-captured in terms of spectral radius. The hyperparemeters used for CEM summarized in Table 2.
30

---

Published in Transactions on Machine Learning Research (6/2024)
Observation trajectories
X-Y trajectory
observations
2.0
1.0
0.5
1.0
0.0
0.0
-0.5
-1.0
-1.0
0
50
100
150
200
-1
0
1
2
timesteps
Σ
-r (ddstannce
- -cos( ()
sin (
Figure 10: The ground-truth trajectory of the limit cycle + r(1 -,²), 0 = 1. Left: Observations cos( and sin(f). Right: z-y positions.
Observation trajectories
X-Y trajectory
observations
2.0
1.5
1.0
1.0
0.5
0.0
0.0
-0.5
-1.0
-1.0
50
100
150
200
-1
0
timesteps
-r (distance)
-co ()
sin ())
Figure 11: The trajectory generated by RFF policies that minimize A(oo) = m mm /1. Left: Observations
r, (0), and sin( Right: x-y positions.
H.4 Setups: Generating smooth movements (Walker)
Because of the complexity of the dynamics, used four random seeds in this simulation, namely, 100, 200, 300, and 400. We used a combination of linear and RFF features for both & and the policy. Note, according to the work (Rajeswaran et al., 2017), 7), linear policy is actually sufficient for some tasks for particular environments. The hyperparemeters used for CEM are summarized in Table 3.
The resulting trajectorics of Walker are illustrated in Figure The results are rather surprising: because we did not specify the height in reward, the dynamics with only cumulative cost. showed rolling behavior (Up figure) to go right faster most of the time. On the other hand, when the spectrum cost used, the hopping behavior (Down figure) emerged. Indeed this hopping behavior moves only one or two joints most of the time while fixing other joints, which leads to lower (absolute values of) eigenvalues.
The eigenspectrums the resulting dynamics with/withon the spectrum cost are plotted in Figure 14. fact, it observed that the dynamics when the spectrum cost was used showed consistently lower (absolute values of) eigenvalues; for the hopping behavior, most of the joint angles converged some values and stayed there.
31

---

Published in Transactions on Machine Learning Research (6/2024)
Observation trajectories
X-Y trajectory
observations
2.0
1.0
0.5
1.0
0.0
-0.5
0.0
-1.0
-1.5
-1.0
0
50
100
150
200
1
1
2
timesteps
2:
-r (ddistance)
- -cos( 0)
-sin(0) 0)
Figure 12: The trajectory generated by RFF policies that minimize A(d) pod-ool'll Left: Observations T, cOs( and sin(f). Right: r-y positions.
Table Hyperparameters used for stable loop generation.
Hyperparameters
Value
Hyperparameters
Value
samples
200
elite size
20
iteration
100
planning horizon
100
dimension dø
50
RFF bandwidth for ø
2.0
policy RFF dimension
100
policy RFF bandwidth
2.0
Algorithm 2 Practical Algorithm for KS-LC
Require: Parameter set πI; prior parameter A; covariance scale I2z--
1: Prior distribution over M' is given by (E)r) -1 where E == Al
2: for t = O - - do
Adversary chooses Xj.
Sample A from N' MM' (2ix)
Solve O' arg men (()) jo
(x(]+x (x :ot) (e.g., using CEM)
Under the dynamics Jd sample transition data == (T W--1 where 7, = 1 H
7:
Update E
8: end for
H.5 Setups: Koopman-Spectrum LC3
Decomposable kernels case. Assume that employ decomposable kernel with B I for simplicity. Also, suppose V(O) de xda is of finite dimension. For such a case, the dimension du = de do where de is the dimension of H": however, we do not need to store a covariance matrix of size d&ds x dade but only require to update a matrix of size dødę x dødę which significantly reduces the memory size. Specifically, we consider the model & draei = Mi( & (())); then using M" == reshape(M', dor dø), we obtain X(O) = [M"[ :, 1)c(()...... I. (e)) Here, is the realization of (()) over some basis. Now, we note that the dimension of Øay (()) is de dg- Our practical (Thompson sampling version) algorithm is thus given by Algorithm 2. In the algorithm, used (() [ i,. li.())...., ".",., do,)))(())) where 2a" : reshape N/ dg do).
We explain how to reduce the memory size in special decomposable kernel
32

---

Published in Transactions on Machine Learning Research (6/2024)
Table 3: Hyperparameters used for Walker.
Hyperparameters
Value
Hyperparameters
Value
samples
300
elite size
20
itcration
50
planning horizon
300
dimension of dø
200
RFF bandwidth for &
5.0
policy RFF dimension
300
policy RFF bandwidth
30.0
HMM
Figure 13: Walker trajectories visualized via Lyceum. Up: When only (singlo-step) reward 0.001 ||a||
is used, showing rolling behavior. Down: When the spectrum cost A(or) E (ax())) is used together with the reward, showing simple hopping behavior.
Simple linear system experiment experiment are summarized in Table
The hyperparameters used for KS-LC in the simple lincar system
Cartpole pretraining policies For training three policies, used Model Predictive Path Integral Con- trol (MPPI) (Williams et al., 2017) with the rewards (p+ 0.3) (p 0.3) (v + 1.5)², and (v 1.5)², where is the cart position and is the cart velocity. Also, for all of the cases, the penalty -100 is added when cos( < 0, where 0 is the pole angle, which aims at preventing the pole from falling down.
Because we need to have one more state dimension to specify which reward to generale, we used the analytical model of cartpole specified in OpenAl Gym.
Starting from random initial state, we first use MPPI move p= -033, then from there move to p p= 0.3; and learn RFF policy for this movement along with the Koopman operator. Then, randomly
33

---

Published in Transactions on Machine Learning Research (6/2024)
Eigenspectrum
1.0
absolute values
0.8
0.5
0.3
0.0
50
100
150
200
index
no spectrum cost
wwith spectrum cost
Figure 14: Eigenspectrums showing absolute values of eigenvalues for the dynamics with/w the spec-
trum cost.
Table 4: Hyperparameters used for KS-LC3 the simple linear case.
Hyperparameters
Value
Hyperparameters
Value
prior parameter À
0.05
covariance scale
0.0001
planning horizon
50
initialized the state to accelerate to -1.5, followed by random initialization again to accelerate to 1.5; then learned two policies for those two movements. We used the planning horizons of 100 for every movement except for the movement going to 0.3 where we used 120 because it is following the previous movement. We repeated this for 20 iterations.
The parameter space II is a space lincar combinations of those three policios. We summarized the hyperparemeters used for MPPI/pretraining Table 5.
Cartpole learning For learning, we used four random seeds, namely, 100, 200, 300, and 400. The esti- mated spectrum cost curve represents the cost AO))((0")) The hyperparameters used for CEM and KS-LC summarized in Table 6. We note that for KS-LC3 added additional cost. the policy parameter exceeding its foo norm above 2.0.
Table Hyperparameters of MPPI and pretraining.
MPPI hyperparameters
Value
Pretraining hyperparameters
Value
variance of controls
0.4²
iteration
20
temperature parameter
0.1
policy RFF dimension
2000
planning horizon
100/120
policy RFF bandwidth
1.5
number of planning samples
524
dimension de
60
RFF bandwidth for
1.5
34

---

Published in Transactions on Machine Learning Research (6/2024)
Table 6: Hyperparameters used for CEM/KS-LC*.
Hyperparameters for CEM
Value
Hyperparameters for KS-LIC
Value
samples elite size
200
dimension of dç
50
20
RFF bandwidth for C
5.0
plamning horizon
500
prior parameter
1.0
iteration
50
covariance scalc i
0.0001
Further experimental analysis
In this section, provide additional experiments. Throughout this section, used the following version of Julia as our computational resource has changed when conducting the experiments presented in this section.
Julia Version 1.5.3
Platform Info:
OS: Linux (x86 -64-pc-1inux-gnu)
CPU: Intel (R) (Ro CPU E5-2620 v3 @ 2.40GHz
SIZE: 64
LIBM: libopenlibm
LLVM: 1ibLLVM-9.00 0.11 (ORCJIT, haswell)
Environment:
SAITA_NUM_THREADE = 12
MuJoCo version 2.0 is used (license: MuJoCo Pro Individual license).
1.1 Variations on stable Cartpole motions
In our simulation of generating stable Cartpole motion, we have seen that it shows oscillating behavior when stability is enforced through the spectrum cost in addition to the reward that encourages the cartpole to have larger velocity. To see this phenomenon more in details, we have conducted the same experiments for different time horizons, namely, 50, 100 and 200. Here, we use A(ar) = 10 p(x/1, (10 times more weight than that in the simulation experiment in the main body). The resulting velocity trajectories with/without the spectrum cost are plotted in Figure 15. Also, the angle trajectories are plotted in Figure 16, where the zero lines the threshold for adding penalty costs. Note for the case of time horizon 200, we used more intensive CEM search whose parameters summarized in Table 7, but could not find policy parameter that can keep the pole straight up. Studying more sophisticated heuristic search algorithm will be an important direction of future research. From Figure 15, is observed that the longer horizon may not indicate more oscillation "cycles", In fact, our spectrum cost only regularizes the dynamics to be stable, which may include a motion where the velocity converges to some fixed value. The spectrum radius for the given by 1.003, 1.00006 and 1.002, while
cases of time horizon 50, 100 and 200 without the spectrum that with the spectrum cost is 0.992, 0.999 and 0.997. While all of them show stable Koopman spectrum when the spectrun cost is used, the case for the time horizon 100 shows particularly interesting behavior. Please recall that the failure of keeping the pole straight up is not necessarily regarded as unstable dynamics over the specified state space where the angle representation is bounded but costs the learner within the cumulative cost term.
Variations on smooth Walker motions
To investigate smooth motion generations studied in the main body of this paper more, we conducted additional experiments.
35

---

Published in Transactions on Machine Learning Research (6/2024)
Horizon 50
Horizon 100
6.0
1.0
velocity
4.0
0.0
2.0
-1.
30
20
60
100
timesteps
timesteps
Horizon 200
15.0
10.0
velocky
5.0
0.0
-5.0
50
100
150
200
timesteps
spectrum cost
with spectrum cost
Figure 15: Velocity trajectories of Cartpole for different time horizons (50, 100 and 200) with/withone the
spectrum cost.
Table 7: Hyperparameters used for stabilized Cartpole for time horizon 200.
Hyperparameters
Value
Hyperparameters
Value
samples iteration
200
elite size
20
1000
planning horizon
200
dimension do
50
RFF bandwidth for ø
2.0
policy RFF dimension
300
policy RFF bandwidth
2.0
1.2.1 Smoothness comparison with increased action cost
Especially, also compare our KSNR for smoothness euhancements the of action costs the Walker environment. In this experiment, used the hyperparameters summarized in Table 8. We again used combination of linear and RFF features for both & and the policy. Recall the default immediate reward is v 0-0.001||a]33 where v is the velocity and a is the action vector of dimension 6. Here, in addition to KSNR, we tested increased action cost. scenarios where the immediate rewards are w 0.01 ||] and vー 0.1. /|1 respectively. Across the six seed runs (of seed mumbers of 100, 200, 300, 400, 500, and 600), we obtained the mcan of the cumulative reward and the cumulative action cost (which computed for the trajectorics using 0.001 0.001|/a|| || for all of the cases), and the mean and standard deviation of the spectrum cost, all of which summarized in Table 9. As observed, increased action cost in scenarios shows lower spectrum cost: while KSNR shows better cumulative reward with better spectrum cost. However, the motion generated by the increased action cost shows lower action penalty cost; which implics that the spectrum cost and the action cost have some correlation while they qualitatively prefer different motions. We also measured the smoothness by another metric than the spectrum cost itself, which is defined by
F7
Smoothness(())
|| Zz ||,,
dx H
h=0
36

---

Published in Transactions on Machine Learning Research (6/2024)
Horizon 50
Horizon 100
10
1.0
pole angle
08
0.8
0.
0.5
03
0.0
0.0
20
40
50
20
40
60
80
100
timesteps
timesteps
Horizon 200
1.0
pole angle
0.5
0.0
-05
-1.0
0
50
100 timesteps
150
200
"no spectrum cost
-with spectrum cost
-aggle threshold
Figure 16: Angle trajectories of Cartpole for different time horizons (50, 100 and 200) with/withoo the
spectrum cost.
Table 8: Hyperparamoters used for additional Walker smoothness experiments.
Hyperparamoters
Value
Hyperparameters
Value
samples
300
clite size
20
iteration
120
planning horizon
300
dimension of dø
200
RFF bandwidth for ø
5.0
policy RFF dimension
300
policy RFF bandwidth
30.0
where J == {xa) D is trajectory. The mean smoothness values across the for the motions generated by the CEM algorithms with default action cost, 10 times more action cost, 100 times more action cost, and with the spectrum cost are 0.082, 0.033, 0.007, and 0.028 respectively, and they appear to be consistent to the spectrum cost in this case. The motions are visualized in Figure 17; their joint trajectories are plotted Figure 18 and the eigenspectrums are given in Figure 19. Note those motions are of those showing median values of the spectrum cost within the seed runs.
1.2.2 Different feature space Ho
Next, we examine what happens when different feature space Ho employed practice. In particular, we used polynomial feature (spanned by x, x 2² x2, .25) for á while the policy is again a combination of linear and RFF features. The hyperparameters
the same except for the dimension of de which is now 5dx.
Now, the spectrum costs of the generated motions of the CEM algorithms with default action cost, 10 times more action cost, 100 times more action cost. are given by 232.9 + 13.6, 194.5 + 19.5, 152.1 + 42.8, and 217.9 + 24.7; and the mean cumulative reward and action cost (penalty) of the one with spectrum cost defined over the polynomial feature space 900.1 and 143.3. is observed that times more action cost led lower spectrum cost in this case than KSNR while the cumulative reward of KSNR is much higher. The smoothness measure for KSNR is now 0.064, which is higher than the with RFF features.
37

---

Published in Transactions on Machine Learning Research (6/2024)
Table 9: Cumulative reward, cumulative action cost (penalty), and spectrum cost comparisons.
Method (Env. setting)
Reward
Penalty
Spectrum cost (mean)
Spectrum cost (std)
CEM (default action cost)
1011.5
177.3
317.0
+33.2
CEM (x10 action cost)
596.4
10.9
213.2
+50.0
CFM 100 action cost)
63.4
0.5
88.8
+446.6
CEM (with spectrum cost)
737.8
78.1
186.6
188844
In fact, when visualizing the motion and joint trajectory Figure 20, observe that the walker also shows similar rolling behavior but with slightly better periodicity than that one without spectrum cost. Eigenspec- trums are shown in Figure 21; where we see less difference among the ones with/without spectrum cost and with x 10 action cost.
These results imply that the feature space selection influences the qualitative behavior difference in practice; please also see Remark 3.2.
38

---

Published in Transactions on Machine Learning Research (6/2024)
without spectrum cost
x 10 action cost
X 100 action cost
with spectrum cost
Figure 17: Visualizations of Walker motions generated by the CEM algorithm with default action cost, 10 times more action cost, 100 times more action cost, and with the spectrum cost. The motions of those showing median values of the spectrum cost within the seed runs. It is observed that the motion generated by the one with 10 times more action cost is smooth but uses two feet to hop, which would reduce the magnitudes of actions applied to the joints. The motion generated by the one with the spectrum cost again lifts one foot and hops; this specific visualized motion then shows a bit of rotation at the last moment.
39

---

Published in Transactions on Machine Learning Research (6/2024)
Joint trajectories (no spectrum cost)
With spectrum cost
10
0.0
0.0
values
values
-1.0
-1.0
-20
-2.0
-3.0
0
100
200
300
0
100
200
300
timesteps
timesteps
x 10 action cost
100 action cost
0.0
10
-0.5
0.0
values
values
-1.0
-155
-20
-20
0
100
200
300
0
100
200
300
timesteps
timesteps
Figure 18: Joint trajectories of Walker motions generated by the CEM algorithm with default action cost, 10 times more action cost, 100 times more action cost, and with the spectrum cost. They are of those showing median values of the spectrum cost within the scod runs.
Eigenspectrum
1.0
absolute values
0.8
0.5
0.3
0.0
50
100
150
200
index
"'o spectrum cost
-with spectrum cost -X 10 action cost
-X 100 action cost
Figure 19: Averaged eigenspectrums showing absolute values of eigenvalues for the dynamics with/wiid without the spectrum cost and with 10 times more action cost and 100 times more action cost.
40

---

Published in Transactions on Machine Learning Research (6/2024)
with spectrum cost (over polynomial basis)
with spectrum cost (over polynomial basis)
1.0
0.0
values
-1.0
-2.0
-3.0
100
200
300
timesteps
Visualization of Walker motions generated by the CEM algorithm with the spectrum cost where the feature space spanned by ær x? .x3 x²1 25. The motion of that showing median value of the spectrum cost within the seed runs. Down: Its joint trajectory.
Figure 20: Up:
41

---

Published in Transactions on Machine Learning Research (6/2024)
Eigenspectrum
1.0
absolute values
0.8
0.5
0.3
0.0
20
40
60
80
index
no spectrum cost
-with spectrum cost "'X 10 action cost
"XX 100 action cost
Figure 21: Averaged eigenspectrums over the polynomial feature space showing absolute values of eigenvalues for the dynamics with without the spectrum cost and with 10 times more act ion cost and 100 times more action cost.
42


Reviews:
[{"review_id": "ucfsjrX3qO", "reviewer": "Reviewer_qbzi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "While this reviewer is not an expert on Koopman theory for dynamical systems, they get the impression that this manuscript makes a solid and relevant contribution to the theory of dynamical systems / controller learning in the context of Koopman operator theory.\n\n\n\n### Strengths\n\n1) Manuscript makes a conceptual and potentially fundamental contribution, which could open up new research directions (as also mentioned in the manuscript)\n2) Well written manuscript\n3) Clear and transparent communication of contributions (p. 2)\n4) Assumptions clearly stated\n5) Aiming to give illustrative examples and explanations \n\n\n\n### Weaknesses\n\n1) While the authors make an effort providing intuition for the theoretical concepts, especially linking the exposition to the (more commonly known) MDP-type RL framework, which is commendable, the exposition could be still be clearer or more elaborate in parts. This includes, in particular, the following parts:\n   * P. 4, \"is a mapping that takes a Koopman operator as an input and returns its cost\" -> Can we interpret this to basically mean that the mapping takes a dynamical system (described by a Koopman operator) as input and returns its cost?  Such statement could be added and also compared to standard MDP formulation for illustration.\n   * What is the goal of the design in (3.2)? In practice, would this be used to find a controller? The controller is not explicitly introduced, but presumable it is considered part of the dynamical system (thus its parameters would be part of \\Theta). I suggest to clarify this. In this context, what components in the formulation have the role of the controller/policy?  \n   * Sec. 3.3: How is CEM based policy search related to the design problem (3.2)?  Is CEM the optimizer that is used to solve the problem (3.2)?  Or is this a separate problem building on top of it?  In general, it would be very helpful if the authors could better explain how policy search relates to their design problem (3.2).\n2) If possible, it would be helpful to provide intuition about Assumptions 2-4 + 6 (e.g., examples for which the assumptions hold; are the assumptions restrictive; etc)\n3) Some further aspects still require more explanation (see minor comments and suggestions below)\n\n\n\n### Minor comments and suggestions\n\n* Introduction/Abstract: What do the authors mean with \"unpredictability\" of the motions generated by standard RL? Please explain.\n* p. 2, key takeaways: I don't understand the sentence \"such, we need some specific structural assumptions that are irrelevant to the Kernelized Nonlinear Regulator (KNR)\". Why is KNR mentioned here? It seems to be out of context, or at least the context is not clear to the reviewer.\n* Related work: \"Skill learning\", e.g. with RL, is an important topic in robotics.  I suggest the authors to review main works there and mention the relation to their approach herein.  Some of the main authors include Jan Peters, Jens Kober, Stefan Schaal, Freek Stulp, for example.\n* Section 2: At the end of this section, \"population based policy search\" is mentioned, but not explained.  It was unclear to this reviewer what the authors mean. Furthermore, why are these numerical examples \"based on population based policy search\" relevant for this work?  Please explain.\n* Bottom of p. 3: even though it is standard, \"i.i.d.\" should be introduced.\n* General question:  Does \"Regulator\" refer to \"regularization\" or \"Regulator\" (controller) as in LQR?  Might be useful to clarify early on. (I only realized later, what was actually meant.)\n* Section 4, first paragraph: What is meant by \"model-based algorithm\"?  What model?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This manuscript proposes a new paradigm for learning control of nonlinear random dynamical systems, which is based on Koopman operator theory. Specifically, the authors propose an optimization formulation over the cost of the Koopman operator of the dynamical system. They term this the Koopman spectrum cost.  Contributions of the manuscript include the conceptual formulation and proposal, a (theoretical) learning algorithms, as well as several numerical examples illustrating the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See weaknesses above.  \n\nMinor comments can be considered optional suggestions.", "broader_impact_concerns": "No concerns.  The manuscript contains a description of (technical) limitations, which is commendable.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "sKv9EUM1HT", "reviewer": "Reviewer_KaJJ", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper addresses an important problem of learning/optimizing control policies that lead to smooth, natural motion in contrast to what might be learned by an RL algorithm\n- The results are well-grounded in theory to motivate the design decisions.\n- Simulations seem to suggest this achieves the desired results.\n- The theory for the online learning algorithm is also promising.\n\nWeaknesses:\n- a number of approximations have to be made to get the online algorithm to work on cartpole, which is a relatively simple problem (including restricting the policy space). This suggests it may be difficult to scale these methods and insights to harder control problems.\n- I have questions about some of the experiments below that are potential weaknesses.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of controlling a nonlinear system by minimizing both stepwise costs and also a koopman spectrum cost. The main intuition is tha this serves as a regularizing effect that leads to smoother motions that are more natural and adapted to the dynamics of the system itself. Both simulation experiments and some theory for an online learning algorithm are demonstrated.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I only have requests for clarifications based on these questions:\n\n-  “Note, this assumption does not preclude the necessity of exploration…” Can you elaborate on this point? Is the exploration that is done in the algorithm done through maintaining the BALL confidence set and minimizing over this optimistically? Then, what purpose does this eigenvalue lower bound serve in Assumption 5?\n- In the initial simulation experiments of section 3.3,  it’s a little unclear what is being learned vs. just optimized. The appendix seems to suggest that the K is being learned through transitions. How were these generated? Was this done iteratively? If so, I’m confused about the difference between these and the results 4.4. Why can one not use the method of 3.3 to solve 4.4 as well?\n- Is it possible to achieve the desired smoothness effects by simply regularizing e.g. punishing high accelerations? Qualitatively, how would this differ from the proposed method? It would perhaps be nice to see comparisons with this in the experiments.\n- I don’t really understand the design decisions made in the first cart pole experiments. The reward is set high for the cart for large velocity, so it makes sense that it increases the velocity. If one wanted it to oscillate, why not just shape the reward function to get it to oscillate? It’s unclear why this might require more machinery when the spectrum cost is also set by hand.\n- The regret bound seems potentially dependent on the adversary’s choice of sequences, as opposed to doing regret that is just the suboptimality with respect to the lowest cost achievable by any control policy. Can you elaborate on how the sequences are chosen? Are they not chosen by the learner’s policy itself?", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ipH1RrJVTH", "reviewer": "Reviewer_62Mx", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper presents a novel form of using the Koopman operator which is a timely and useful tool for modeling nonlinear systems as linear systems in a lifted spectral domain. Control in that domain is often very challenging to acquire, even though the system is modeled as a lifted linear system. The work does a good job of describing the Koopman operator and how one can obtain controllers that leverage the spectrum of the nonlinear system. The theoretical results are very strong and seem to be a significant advancement in Koopman operator theory.\n\nHowever, the empirical results of the proposed work are not convincing, especially with the baseline comparisons. For example, the provided video experiments do not seem like the proposed method provided much more improvement. The results provided in the paper provide a better picture of the results but are still limited in the example cases and could be explicitly compared with the addition of a table outlining the extent to which performance has improved.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper presents a method for control of nonlinear systems using Koopman operator theory with a spectral-based cost. The approach is claimed to be effective at online learning.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The paper should consider more baseline experiments that holistically demonstrate and analyze the proposed method. For instance, adding in ablation studies regarding the basis function and choices of cost parameters would strengthen the contribution of the paper. \n\nWith regards to the results, the paper claims to have cyclical behavior for the cart pendulum and the walker, however, the results only show one \"cycle\". How repeatable are the trajectories only some of the results show clear repeatability. It would be good to see if the approach can be extended to non-cyclical systems. If not, what are the conditions for which a system can use the proposed method?\n\nAdditional results for the online learning for different systems and different basis functions would be valuable for the paper as well.", "broader_impact_concerns": "The paper did not provide a broader impact statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: I would like to thank the authors for their patience, as this paper has been under review for longer than usual.

The final decisions of the reviewers have been one Accept, one Leaning Accept, and one Leaning Reject.

All reviewers believe that the paper makes interesting contributions. So, from the novelty perspective, this paper is strong. Most of them also believe that the claims are reasonably well supported. The reviewer on the negative side, however, criticizes the paper because the advantages of the proposed method is not very evident.


I read the paper myself, without verifying the proofs. At a high-level, the paper has 
- some conceptual novelty (the addition of a Koopman spectrum cost to the per-step cost);
- theoretical guarantees in the form of regret bounds (which are under strong assumptions, such as Assumption 1);
- some empirical illustrations, mostly on toy problems.

Given that the formulation is new and optimization of the corresponding objective is not trivial, perhaps it is reasonable not to expect extensive and competitive empirical results for this work.


One aspect of the paper that can and should be improved is its clarity. At several points in the paper, its quality of writing and clarity decline. I believe it is partly because the authors revised the paper to answer specific questions of the reviewers, but those revisions disrupted the flow of the paper (for example, Figure 3 and Analogy to Fourier analysis). In some other places, more explanation can be added. I provide some specific examples, in addition to some of my own questions. 

**Overall, this is a good paper overall, and can be accepted if the authors improve the paper's clarity.**


===

Some places were clarity can be improved and some additional questions:

- More discussion of the RDS model in Section 3.1. For example, it is stated that "RDS subsume many practical systems including Markov chains". Some examples of this would be helpful.
- More explanation of the Koopman operator. The mathematical definition is in Definition 3.1, but some intuition would be helpful. For example, it is not clear whether such an operator K always exists or not.
- Example 3.1 can be expanded. How easy is it to compute the spectral radius of the Koopman operator (given that it is infinite dimensional)? What are the practical ways to compute it?
- Remark 3.1 is unclear to me. This is apparently an answer to one of the reviewers, but it may not be very clear for someone who hasn't read the discussion between the authors and the reviewers.
- m and m* are used in Section 3.3 before being introduced much later in Appendix H.2. In general, I believe the discussion of Simulated experiments in Section 3.3 can be improved by adding more details.
- Would you confirm that the minimum in the definition of regret is after the summation over t and not before that?
Decision: Accept (poster)