Rate-Optimal Online Convex Optimization in Adaptive Linear Control
Authors: Asaf Cassel
Alon Cohen
Tomer Koren
Venue: NeurIPS 2022 Accept (2022)
Keywords: linear control
optimism
online convex optimization
adaptive control

Abstract: We consider the problem of controlling an unknown linear dynamical system under adversarially-changing convex costs and full feedback of both the state and cost function. We present the first computationally-efficient algorithm that attains an optimal $\sqrt{T}$-regret rate compared to the best stabilizing linear controller in hindsight, while avoiding stringent assumptions on the costs such as strong convexity. Our approach is based on a careful design of non-convex lower confidence bounds for the online costs, and uses a novel technique for computationally-efficient regret minimization of these bounds that leverages their particular non-convex structure.

Rate-Optimal Online Convex Optimization in Adaptive Linear Control
Asaf Cassel"
Alon Cohen
Tomer Koren
Abstract
We consider the problem of controlling unknown linear dynamical system under adversarially changing convex costs and full feedback of both the state and cost function. We present the first computationally--fin optimal Vr-regret rate compared to the best stabilizing linear controller in hindsight, while avoiding stringent assumptions approach is based on careful design of non-convex lower confidence bounds for the online costs, and minimization of these bounds that leverages their particular non-convex structure.
algorithm that attains
the costs such strong convexity. Our
novel technique for computationally-effeee regret
Introduction
We study a general setting online adaptive linear control, where learner attempts stabilize an initially unknown discrete-time linear dynamical system while minimizing its cumulative cost with respect an arbitrary sequence of convex loss functions. The system dynamics evolve according to
Xi+1 A,X, + B + W/-
where x, IRd, 14, Rdd are the (fully observable) system's 's state and learner's control at time step f, and [Rds is the system noise added at step which is a zero-mean i.i.d. Gaussian random variable. The matrices A, e gd, and B, 1d, are the system parameters, which are assumed to be unknown ahead of time and need to be learned adaptively. The goal is to minimize regret with respect sequence of convex loss functions ct...... ........ cr over T time steps, namely, the difference between the learner's cumulative control cost (,,, 1,) and the best cumulative cost achieved by a control policy from a given of benchmark policies.
This general framework encapsulates numerous variations of learning in linear control that have been studied extensively in the literature. When the system parameters known ahead of time and the costs are fixed and known (convex) quadratics, this amounts to the classical "planning" formulation of lincar-quadratic (LQ) stochastic control; see [12]. The special case where the costs are fixed and known quadratics but the system parameters are unknown has been addressed much more recently [1, 21, 31]. This was recently extended allow for fixed and known convex cost [33] and later for stochastic i.idd. costs [15]. On the other hand, the case where the system parameters are known but the quadratic costs are allowed vary arbitrarily between rounds was first addressed in [20]. and has been later extended in various ways to allow for arbitrarily-varying convex costs [5, 6, 36, 13]. In of these special cases, we now know of efficient algorithms with rate-optimal VT regret guarantees.
For the online adaptive linear control problem in its full generality, however, regret-optimal algorithms are presently known. The state-of the-art is due to [36] that achieved 2/33-regret using
"lavvttnik School of Computer Science, Tel Aviv University; acassel @mail. 0ww.l. tau.ac.il.
School Electrical Engineering, Aviv University, and Google Tel Aviv: alonco8tauez. tau.ac. $ Blavatnik School of Computer Science, Tel Aviv University, Google Tel Aviv; tkoren@tauex. tau. il.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

simple sxploe--hhen-exleee strategy: in the exploration phase, their algorithm estimates the dynamics parameters by exciting the system with noise; then, in the exploitation phase it runs an online procedure for known dynamies using the estimated transitions. This simple strategy has also been shown to achieve the optimal VT-regret when the online costs are additionally strongly convex, demonstrating that the stringent strong convexity assumption allows one to circumvent the challenge of balancing exploration and exploitation in online adaptive linear control.
In this paper, we resolve this gap and give the first rate-optimal algorithm for the general online adaptive linear control problem, accommodating arbitrarily changing general convex (and Lipschitz) costs and unknown system parameters. Our algorithm is computationally efficient and attains VT regret guarantee with polynomial dependence on the natural parameters of the problem.
Techniques. Our approach builds upon a combination of recent techniques in online linear control. First, we rely the Disturbance Action Policies (DAPs) of Agarwal et al. [5]: our algorithm generates DAPs that choose the control at each time step as a linear transformation of past noise terms; the DAPs themselves are maintained by online convex optimization algorithms that generate slowly-changing decisions for guaranteeing the stability of the system throughout the learning process. Moreover, since the dynamics are unknown, our algorithm estimates the noise terms on-the-fly, and uses these estimates in place of the true noise vectors (this is akin to technique in [33]..
Second, following the recent developments of Cassel al. [15] for the case of stochastic costs, perform regret minimization with respect to optimistic lower confidence bounds of the online costs. However, these confidence bounds turn out to be inherently nonconvex. To maintain computational efficiency, we adapt a trick of Dani et al. [22] (in the context of stochastic linear bandits) for relaxing the nonconvex objectives so assume the form of a minimum of a small number of convex objectives; then, we hedge over multiple copies of online gradient descent as "experts" in a meta-algorithm, where each copy minimizes regret with respect one of these convex objectives.
Even so, the decisions of the hedging meta-algorithm are random and can thus change abruptly, interfering with the slowly-moving nature of the DAPs that is crucial for the stability of the system. We address this issue by using a lazy version of Follow the Perturbed Leader in place of the meta- algorithm (due to [7]) that employs only a small number of switches between experts. Overall, this results in a computationally efficient scheme that maintains the VT regret rate of the individual gradient-based experts.
Related work. The problem of adaptive tinear-quadrane control has a long history [e.g.. 12]. Recent years have seen renewed interest in this problem through the modern view of regret minimization- building on classic asymptotic results to obtain finite-time guarantees [1. 3, 9, 23, 24, 27, 32]. More recently [21. 31] provided polynomial-time algorithms obtaining an optimal vT regret rate. The optimality of the VT rate was proved concurrently by [14, 35].
More recently. [33] gave an efficient algorithm with vT regret for learning the dynamics under fixed known convex cost. [33] also observed that the problem of learning both dynamics and stochastic convex costs under bandit feedback is reducible to an instance of stochastic bandit convex optimization for which complex, yet polynomial-time
generic algorithms exist [4]. Cassel et al. [15] later study the problem of learning the dynamics and stochastic convex costs under full-information feedback. Unlike the approach of [33], their algorithm is based on an "optimism in the face of uncertainty" principle and is thus conceptually simpler and more efficient to implement.
Our approach relies on the standard assumption that the controller is provided with some initial stabilizing policy. First proposed in [23], such an assumption yields regret that is polynomial in the problem dimensions, and was later shown to be necessary by [18].
Past work has also considered adaptive LQG control, namely linea-quudrrate control under partial observability of the state [for example, 36). However, it turned out that in the stochastic setting, learning the optimal partial-observation linear controller is in a sense easier than learning the full- observation controller. It is in fact possible obtain poly(log 7") regret for adaptive LQG [29]. This result is facilitated by simplifying assumptions on both the noise distribution as well as the benchmark policy, assumptions which we do not make in this work.
Most works on regret minimization in adaptive control are basel-based;; meaning, the algorithm attempts to estimate the model parameters. Previous literature also considered the alternative approach
2

---

of model-free control [e.g., 2, 17, 25, 30, 37]. These works, however, rely heavily on the assumption of quadratic strongly-convex costs and do not apply to general convex costs.
Lastly, [13, 26, 33] consider control under bandit feedback. These results are unfortunately impeded by the state-of-the-art in Bandit Convex Optimization, that is either not efficient in practice (namely, high-degree polynomial runtime) or requires further assumptions on the curvature of the cost functions. For this reason we focus here on fulliinformation feedback, with the hope that our techniques can be adapted to bandit feedback in subsequent work, contingent on future advancements in BCO.
Preliminaries
2.1 Linear control background
A discrete-time linear control system is one whose dynamics are governed by the following rule:
Xx+1 = A,X, + B, + Wi+
where A, E Rdixds, B. Rddxddu, and where W, E Rdx is zero-mean i.i.d. In the planning version of the problem the controller knows A.. B, and, at each time f, can choose as a function of ,y, After choosing u,, the controller incurs a known cost c(x,, Classic results pertain to quadratic costs, and state that the control rule that minimizes the steady state cost ((r) limy Ex & Σ/=1 c(x,, U;)]. chooses n, = Kx, for some matrix K E Rd,xdx Moreover, the optimal rule x stabilizes the system, implying that / (T.) is finite and well-defined for any quadratic cost function.
We require the following notion of strong stability [20), which is standard in the literature and whose purpose is to quantify the classic notion of (asymptotic) stability.
Definition 1 (Strong stability). A controller K for the system (A+, B.) is (x >-rr>)sssttoyyyy stable (x 2 1, < y < 1) if there exist matrices Q, L such that A, B.K QLQ ||/|| y, and ||K]I, S k.
2.2 Problem setup
We address the problem of controlling an unknown linear dynamical system subject to general adversarial convex costs with full state and cost observation. In particular, the system parameters A.,
B, are initially unknown and the learner repeatedly interacts with the system as follows:
(1) The player observes state xy;
(2) The player chooses control Ny;
The player observes the cost function C, Rdd x Rdd R, and incurs cost e, (Xy, u4).
Note that (wr) are unobserved, and the cost c, is revealed only after selecting 4t- Our goal is to minimize regret with respect any policy in benchmark policy class II. To that end, denote by x," u, the state and action sequence resulting when following a policy æ.; then the regret compared to is defined
T (egret((r) = Σ cx (x) (x, ,
1=1
and we seek to bound this quantity with high probability for fixed π II. We focus on the benchmark policy class of strongly stable linear policies that choose u, Kx, ie..
Mia {K IRduxdd
K is (k, -tstronglyy stable).
We make the following assumptions on our learning problem:
Non-stochastic convex and Lipschitz costs. The costs c, are arbitrarily determined by an oblivious adversary* such that each (x, u) is convex in the pair (x, u) and for any (x, u), (x', u²) we have |c, (x' u')l [x x', l:
4 An oblivious adversary does use past random choices of the learner to select its loss functions.
'In the full version of the paper [16] we also explain how to accommodate quadratic losses via an appropriate choice of normalizing constant.
3

---

ii.d. Gaussian noise. (wr))=1 is sequence of ii.d. random variables such that N(O, o20,
Stabilizable system. A is (x. -ttt-stroglly stable, and BB s Rg.
Note that the assumption that A, is strongly stable is without loss of generality. Otherwise, given access to stabilizing controller Ko. we show in the full version of the paper [16] generic black- box reduction that takes any learning algorithm that assumes strongly-stable A., augments its observations and adds Kox, its predicted actions. This essentially replaces A, with A. + Ko. which is (k, y)sttryy stable as desired, and only incurs a 2k multiplicatiie factor the regret.
The assumption that the noise distribution is known is standard one that appears in several past works [23. 31, 21, 33]. However some works, e-g.. [6. 13, 35], only assume light-tailed (sub- Gaussian or bounded) noise with lower bounded covariance. In the context of this work, the known distribution assumption used generate one "fresh" noise sample per time step (see Algorithm and Section 3.3 for further details). We conjecture that recycling past noise estimates could replace the noise generation thus dismissing the known distribution assumption, but leave this as an open problem for future research.
2.3 Disturbance Action Policies
We the, now standard, class of Disturbance Action Policies (DAPs) first proposed by [5]. This class is parameterized by sequence of matrices (M Rd.xdd ) h=1- For brevity of notation, these concatenated into a single matrix M RduxHd, defined as M (M MM DAP AM chooses actions
H U,
Σ
M [b]
wz-h.
where recall that the w, system disturbances. Consider the benchmark policy class
ПDPP
{ΛM
||M[|
RM)-
There are two main reasons for considering the DAP parameterization. First, the loss functions are convex in M, a fact which is generally untrue for K in a linear policy = Kx,, This paves the way for tools from the online convex optimization literature. Second, shown in [5, Lemma 5.2], if E 22y log 7) and Rm E 2(x2 then ПDP good approximation for Tin the sense that a regret guarantee with respect to UDAP gives the same guarantee with respect to Him up to constant additive factor. In light of the above, our regret guarantee will be given with respect to IDPP-
Bounded memory representation. As observed in recent literature, the linear dynamics have an infinitely long memory, i.e., all past actions have some effect the current state, and such on the losses. However, due to the stability of A., the effective memory of the system, H, is essentially constant. To see this, unroll the transition model get that
H
H X N1 =
Σ 1=1
| Ball a(- A X1-H P + W7-1s
(1)
where V. HA B...... Aa.....AAB... B,, AH A+] E Rdd.xde and P. = [u] HH-HH... J..
w HH...... IT E Rd where dy := Hdd (11 1)dx. Now, since A, is strongly stable, the term A# quickly becomes negligible. Following the notation set by [15]] this observation is combined with the DAP policy parameterization to define the following bounded memory representations. Let
MIH]
M[H-1]
MII]
M [H]
MIH-1]
M
P(M)
M |
M
M
M
1
We note that more common definition uses Σ [h]]] to measure the size of the class. We chose the Frobenius norm for simplicity of the analysis, but replacing it would not change the results significantly.

---

and for an arbitrary sequence of disturbances w {Wi)r21 define
My (M::w) = E M w
( w) -(4+1-H (M:)) ..... .... (M;w), WiH--...... wi-1) P(M))wH12RH--1
(M; P, w) = -PPp-I (M;:)) + W,-1.
(3)
Notice that uz Pr, do not depend the entire sequence w, but only W/-H:-11 W and W1-2Hu-1 respectively. Importantly, this means that we can compute these functions with knowledge of only the last (at most) 2H disturbances. While this notation does reveal this fact explicitly, helps with both brevity and clarity.
Algorithm 1 OCO in Adaptive Linear Control
1: input: confidence parameter 6, memory length H, optimism parameter a, regularization parame- ters Ay, Aws learning rate !,, noise bound W.
2: set j = 1, V1 Ay M₁ = and w; = 0, W,, u, = 0 for < 1.
3: define loss scaling function:
(M) == [ 2a R RMx)
4: for 1,2...., do
5: play u, = >/1 M,
6: set V1+1 = V P.p for Pr = (4-HH- uJ, WT 1+1-H ".1 a TL)
7: observe Xy+1 and cost function
8:
calculate
(A, B,) = arg min (A B) B)ERde rideddd)
Σ x=1
(A B)z, - xs+1 112 + Aw (IA B) Bl
where 2,
x5
11s]
9:
estimate noise v, = =[] A,x, B,u,). sample w,- N(0, l2)))). if det(( > <ee((V,,) then start new epoch: i= +,+++++11
10:
11:
12:
estimate system parameters
V
arg min 4 Wegddexayy
Σ IVp, - x 2 1
14:
initialize A = new instance of BFPL* 5/6 and set M,, =... M
15:
else /f 2 + 2// then
define expert loss functions: Vk [dy] [(2H 1)dxl.x (=1}
( w) (M; aox (v=!!2((M))
define loss vector &, 22222211)ddd.c s.t. (k)x, = (MM((k..))kkxx))/MMM
17:
18:
update experts: Vk [dv] x ((2 1)dx,,1 (=1)
(k+ 11 - (M,
update prediction (ke+1) A(t)) and set M,+1 M
Algorithm and Main Result
In this section we present our algorithm for regret minimization linear systems with unknown dynamics and adversarial convex costs; see Algorithm 1. We denote by II the projection onto M.
5

---

The algorithm mediates between least squares estimation of the system dynamics (Lines 8 and 13), and optimizing the policy w.r.t. inversarially-changee cost functions. For OCO, the algorithm uses combination of Online Gradient Descent [38] (Line 18) and BFPI, [7] (Line 14)-an an experts algorithm that also guarantees an overall small number of switches with probability least 6. Our algorithm uses DAP parameterization (Line 5; see Section 2.3 and notations therein), and feeds the aforementioned online optimization algorithms with lower confidence bounds of the online costs. See below for further details on the algorithm's 's operation.
We have the following guarantee for Algorithm 1. The proof is deferred to the full version of the paper [16].
Theorem 2 (Simplified version of Theorem 7 in the full version of the paper [16]). Ler ö (0, 1) and suppose that we run Algorithm with parameters M, RB 2 1 and for proper choices of W, W.H,Aw; Ay, NG. If 2 8 then for any ПDAP, with probability least 6,
(rg I p .o,, RB. RM, dx du (0)
Our algorithm is comprised of multiple components working in tandem. We now give a brief overview of each of the components and how they play together. We note that some components previously appeared in [15], and provide a detailed comparison at the end of the section.
3.1 Prerequisites: system estimation and DAP parameterization
Parameter estimation: The algorithm proceeds in epochs. At the beginning of each epoch, it estimates the unrolled model via least squares using all past observations (Line 13), and the estimate Vr, is then kept fixed throughout the epoch. The epoch ends when the determinant of V, is doubled (Line 11); intuitively, when the confidence of the unrolled model increases substantially." 7 Throughout the epoch, the algorithm maintains estimates of the transition noise (vb, ), (Lines and 9). We observe that these noise estimates are essentially produced for "free" and no explicit exploration is needed.
DAP implementation: While the benefits of ПaP are clear, notice that it cannot be implemented as is since we do not have access to the system disturbances w; nor can we accurately recover them (due to the uncertainty in the transition model). Similarly previous works, our algorithm thus uses estimated disturbances vi, to compute its actions. At each time step I, the algorithm chooses u, as a linear function of the past H noise estimates, and parameterized by M, (Line 5). M, itself is updated using OCO on surrogate cost functions that are formed as a composition between cy (x, u) and the bounded memory representations U, M: ) xy (M; Y r, 10). implicitly assuming that M, was kept fixed for the last H time steps. It is therefore crucial that these representations closely reflect the state and action that are actually observed, hence the OCO procedure has to make sure that the sequence (M changes slowly (more on this below).
Construction of lower confidence bounds: The algorithm uses the estimated unrolled model to minimize regret with respect to lower confidence bounds of the form:
C,
W) u, (M) - a'. -I (M:
(4)
This lower confidence bound follows immediately by combining the Lipschitzness of c, and standard self-normalizing concentration bounds [1]. In our analysis, we show that it indeed lower bounds e, (X,, u,). Such lower confidence bounds are used extensively in multi-armer bandit and reinforce- ment learning literature to efficiently combine exploration and exploitation [10, 11]. Intuitively, their minimization steers the resulting policy towards state-action pairs that either yield low cost, or are insufficiently explored.
3.2
Key idea: making the algorithm efficient
The functions in Eq. (4) are, unfortunately, nonconvex (being a difference of two convex functions), and thus cannot be used in OCO algorithms in their current form. However, we overcome this by relaxing the functions in Eq. (4); we do so in two steps. First, we move to an expected, amortized notion of optimism. We can do this since since w, which are i.i.d, and thus standard concentration arguments imply that the realized bonus term is close to its conditional expectation, which takes the form:
E V Pi-1 (M: pr-
= or||= 1/ P(M))
"Concretely, the volume of the confidence ellipsoid around the unrolled model decreases by constant factor.

---

where P(M) is define in Eq. (2). Second, building on a trick from [22] in the context of linear bandit optimization, further bound || P(M))l d P(M)l (where Il is the entry-wise matrix infinity norm). Due to an adaptivity issue (more on this below), we also replace the estimated noises w in the cost term with random simulated noises w V(0,o²2) After this relaxation, the resulting optimistic cost can be written as minimum of convex functions of the form
(5) where & [dy] [(2H - 1) is matrix coordinate, X {+1} is sign variable. and dya'. Crucial to this trick is the fact that, unlike Eq. (4), the linearized non-conves term is independent of the time index This observation yields computationally-effie
fMM: x)
(xy (M; Vr., W), u,
u, (M; w)) -oox P(M))
regret minimization via two-tier approach described as follows. We run a different copy of Online Gradient Descent [38] for each value of k. X. maintaining different set of DAP parameters M, (k, (,, x), and fed with f.;: x) (Line 18). On top of the OGD algorithmss, we run an experts meta-algorithm to minimize (k; over x.X (Line 19), treating the output of each OGD algorithm as expert.
Observe that having initially taken expectation over the noises yields an exploration bonus term that, for fixed M, is fixed throughout each epoch. This makes sure that OCO algorithms, that are restarted at every epoch, can compare against M, (the best in hindsight) with & and X being fixed at the start of the epoch.
3.3 Additional challenges
Stabilizing the meta- -eta-algori Our hedging approach nevertheless comes at a price. The choices of the meta-algorithm are inherently random, thus M, might change abruptly between consecutive rounds (recall that DAP require slovly-changing M,). We therefore use a version of Follow the Lazy I Leader (BFPL* (7]) that guarantees, with high probability, both no-regret and small number of switches. The small number of switches in conjunction with the fact that each of the expert algorithms generate slowly-changing decisions, guarantee that M, itself is slowly-changing overall.
Mitigating adaptivity costs: Even so, the guarantees BFPL* hold only against oblivious adver- saries (and this limitation is inherent, as [7] discuss extensively), yet the loss sequence constituting of the functions in Eq. (5) unfortunately nor oblivious. This is because the noise estimate v were generated using policies derived from previous choices of BFPL* We overcome this hindrance relying on the fact that the noise vectors are drawn from known (Gaussian) distribution. This allows to sample i.i.d. copies of the noise vectors w (Line 10) that we use in w instead of w, arriving at the losses.
functions defined in Line 16, and ensuring that BFPI.* receives abliviously-generaae
Comparison with [15]. Algorithm I here shares some components with Algorithm I of [15]. In particular, the parameter estimation and DAP implementation are identical. However, there are some crucial differences. Most notably, the optimistic cost minimization must handle the non-stationary adversarial costs rather than the stationary stochastic ones. As such Algorithm I employs a regret minimization scheme with respect to the non-convex optimistic costs (Section 3.2) as opposed to a simpler empirical risk minimization (ERM) in [15]. The stability and adaptivity challenges above are also unique to our adversarial setting. In [15] these are avoided by changing the decision only a small (logarithmic) number of times, which can only be done for stochastic costs.
4 Analysis
In this section we give (nearly) complete proof of Theorem 2 in simplified setup, inspired by [33], where A, = The analysis in the general case is significantly more technical and thus deferred from this extended abstract (see the full version of the paper [16] for full details).
Suppose that A, and thus Xy+1 = Buu, + wr, assume that (x,x, u) = (x),, i.e., the costs do not depend on u, and aim to minimize the pseudo regret,
Σ (B [=1
max SR
where J,(x) C, + w), is the expected instantaneous cost, which can be computed from e, (x) for known noise distribution. The resulting problem is an instance of the following variant of online convex optimization, which we now define with clean notation as to avoid confusion with our general setting.
7

---

4.1 Simplified setting: OCO with Hidden Linear Transform
Consider the following setting of online convex optimization. Let S C IRd be a convex decision set. (We denote by IIs the projection S.) At round the learner:
(i) predicts a, E S;
(ii) observes cost function 4 Rdd - and state ye+1 = Q+ay cxi
(iii) incurs cost aQ.4).
We have that 6, dR are i.i.d. noise terms, 2. Rdyxda is unknown linear transform, and E Rdy are noisy observations. The cost functions are chosen by an oblivious adversary, and we consider minimizing the regret, defined as
Σ - (( ES
regrety = max
Assumptions. We make the following assumptions:
(-) are convex and I L-Lipschitz;
There exist known W, R2 2 0 such that ||&|l s W, and ||@x|l s Ro-
For all E S we have ||a|| s R,/2.
Algorithm 2 OCO with a hidden linear transform
1: input: optimism parameter a, regularizer learning rates NG.
2: set: V/ 11, 0, T, = 1, and a,(k, S. (k, = 112dd Vk e [dal.x {+1}.
3: =0r/=1,2,.... do
4: draw (i),
and play a, = =a, (k,,
5: observe y1+1 Q.a, w, and cost function l, and set Vi+1 V, + a,aF
6: if det(Vr+1) > de)((V,)) then
start new episode i =+ and set Pr+t (k, x) 1/2d a++1 (k. (k,
8:
estimate parameters: 2+, arg min me ReRdyxda Σ {1laa, yss + All 211:..
9:
else
10:
define expert loss functions: (,; k,
-xx ax x (( (V=
11:
update experts: ax+1 (k,
nc (k update prediction: Prai x) p, (a
+ OGD
12:
MW
Algorithm. Our algorithm for this simplified setup is detailed in Algorithm 2. Unlike the full control setting, the adversarial costs here have no memory, thus enable the following simplifications compared to Algorithm 1. First, can forgo the DAP parameterization and directly optimize the prediction a,- This both removes the need to estimate the disturbances, and simplifies the construction of the lower confidence bound. Moreover, the lack of memory obviates the need make our predictions change slowly over time, and we replace the BFPI.* sub-routine with Multiplicative Weights (MW) [see 8).
4.2 Analysis
The main result of this section bounds the regret of Algorithm 2 with high probability.
Theorem 3. Let ō E (0. 1) and suppose that we run Algorithu 2 with parameters
TG (2aRa² RONNT 7M = 2(2a + RaRo) VT -= = R2 a = vda Wdy 8 8log 2 +VZRoRo)
Ra
Iog(2da)
I 2 8 then with probability least 6-
21 + RaRQ Tlog2 4d,T² 3/2 Wdy log o
regret, S 77d
8

---

The proof of Theorem 3 is composed of two main lemmas. Similarly to the control setting, we first define an optimistic loss
(a)) = ( Fea V alloc.
where i(z) max(i: 7 f). The following lemma shows that the optimistic loss lower bounds the true loss, and bounds the error between the two.
Lemma 4 (optimism). Suppose that Vdalle QxIlv=mn a. Then for any E Rd,,
(a)) - 4(O+a) s (a) 2a a VTV=
Proof. The proof follows standard arguments (see e.g. Lemma [15]). assumption to get
We first use the Lipschitz
((((aa)) (012,a))-((rm... a)l & 11(2 - (ranraa )all
$ 11 @rao Vlve,o
IV all
|V all
Vda
<r||V=ii alloe.
where the second and third transitions also used the estimation error and that ||a|| s Vaallallo.. We thus have on one hand,
4(L+a) 2 l (( a) - allv 1/2 1eos allo = & (a),
and on the other hand we also have
((@+a)= s & ( (m a) + a allVV Fun a 11.00 (a) 2ar Va
1 Fun) alloo s (((a) + 2a Vild
where the last step also used ||a]| s ||a||-
Next, the following result bounds the regret with respect to the optimistic cost functions.
Lemma 5. Define G; = =I ll a/2-1/2 and G 20r1-11 RØ. With probability least 1 for all epochs 2 simultaneously:
Σ 1=T1
(4(a,)) -(aa))(((a))) s 3Ra ( +
T Tlog 2d
Proof. First, fix epoch and notice that a, (k, x) are the result of running Online Gradient Descent (OGD) on the functions (; k, x), which are G; Lipschitz. A classic regret bound for OGD (see Lemma 25 in the full version of the paper [16]) then gives us that for all S and T; S s = T
Σ ((a,(k)))k (,aakk RG G.G-1NTT
Next, note that MW invariant to a constant shift in the loss vectors. Letting do S be arbi- trary, have that Pr is updated according to the MW rule with the loss of each expert being (K, x):k, k. x) - ( ag). Using the Lipschitz property of &, these are bounded as
(a, (k, k):k)) 4, (0), 1lē Illa, (klaa, (k. abll a. aza (k, x)ll s G.R..
standard regret guarantee of MW (Lemma 26 in the full version of the paper [16]) thus gives us that with probability least 5-
Σ (k),, (, & R. ( F
2daT 6T log
8
for all & [dal.x e (-1,1), and ST.T.

---

Now, let k;)a), (a) be such that (()) = (a) (a)) for all T; S T/-1 Importantly, notice that kū (a), (a) are independent of the time index r. This is because the minimum in & is taken over the optimism term, which is independent of inside given epoch. For case of notation, the following will omit the dependence of x on which will be kept as a fixed (arbitrary) comparator. Combining the above, with probability
we have that for all e S:
T ((a,)- ((a) &
Mark x1) - (aakk')
(G() ((:k,x))
=
Σ
x'))
xx)
s 3Ra ( G / Flog 2d
Repeating the above with 6/7 and taking union bound over the epochs (of which there are at most 7) concludes the proof.
We ready to prove Theorem 3. We focus here on the main ideas, deferring some details to the full version of the paper [16].
Proof of Theorem 3. We decompose the regret as
regret, (a) s Σ
- Σ
-
- c(Caa),
T=1
R₂
and conclude the proof by bounding each term on the following good event. Suppose Lemma holds for all epochs with 8/27, and that vdulle, - Q+1ly, I a for all / S T, which follows from standard least squares estimation bound (see Lemma 22). Taking union bound, this event holds with probability at least 1 6. We conclude that Lemma 4 holds and thus R3 0. Moreover, we get that
Ri
20 LevaTVVla s 2a
2aTV 2x Σ t=1
2T Σ av s 2aV log f-1
[=1
where the second inequality uses Lemma 27 of [21], which states that for V1 2 V/2 0 we have Vi 3 V2(det(Vi)/dett V2)), the third due to Jensen's inequality, and the fourth a standard algebraic argument (see Lemma 23).
Now, an immediate corollary (see Eq. (10)) of the least square error bound is that || || s at at 1/2+ We thus have that G, s G for all i s N. Next, notice that the number of epochs satisfies s 2d T (Lemma 24). We conclude that
T Σ
4d
R₂
(a(a,)) [((a))
3Ra G G Σ t=1
T Tlog
(Lemma 5)
8
4d.T²
12da RaRe)
Tlog²
Acknowledgments and Disclosure of Funding
This work was partially supported by the Israeli Science Foundation (ISF) grant 2549/19, by the Len Blavatnik and the Blavatnik Family foundation, by the Yandex Initiative in Machine Learning, and by the Israeli VATAT data science scholarship. AC is supported by the Israeli Science Foundation (ISF) grant no. 2250/22.
10

---

References
[1] Y. Abbaasi-YYadaee and C. Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference on Learning Theory, pages 1-26, 2011.
[2] Y. Abbasi-Yadkori. N. Lazic, and Szepesvári. Model-free linear quadratic control via reduction to expert prediction. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 3108-3117. PMLR, 2019.
[3] M. Abeille and A. Lazaric. Improved regret bounds for thompson sampling in linear quadratic control problems. In International Conference Machine Learning, pages 1-9. PMLR, 2018.
[4] A. Agarwal, D. P. Foster, D. J. Hsu, S. M. Kakade, and A. Rakhlin. Stochastic convex optimization with bandit feedback. Advances in Neural Information Processing Systems, 24, 2011.
[5] N. Agarwal, B. Bullins, E. Hazan, S. Kakade, and K. Singh. Online control with adversarial disturbances. In International Conference on Machine Learning, pages 111-119. PMLR, 2019.
[6] N. Agarwal, E. Hazan, and K. Singh. Logarithmic regret for online control. In Advances in Neural Information Processing Systems, pages 10175-10184, 2019.
[7] J. Altschuler and K. Talwar. Online learning over finite action set with limited switching, In Conference On Learning Theory, pages 1569-1573. PMLR, 2018.
[8] Arora, F. Hazan, and S. Kale. The multiplicative weights update method: a mlgo-ilgo and applications. Theory of computing, 8(1):221-664, 2012.
[9] S. Arora, E. Hazan, H. Lee, K. Singh, C. Zhang, and Y. Zhang. Towards provable control for unknown linear dynamical systems. 2018.
[10] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2):235-256, 2002.
[11] Auer, Jaksch, and R. Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
[12] D. P. Bertsekas. Dynamic programming and optimal control, volume 1. Athena scientific Belmont, MA, 1995.
[13] A. Cassel and T. Koren. Bandit linear control. Advances in Neural Information Processing Systems, 33, 2020.
[14] A. Cassel, A. Cohen, and T. Koren. Logarithmic regret for learning linear quadratic regulators efficiently. In International Conference on Machine Learning, pages 1328-1337. PMLR, 2020.
[15] A. Cassel, A. Cohen, and T. Koren. Efficient online linear control with stochastic convex costs and unknown dynamics. arXiv preprint arXiv:2203.01170, 2022.
[16] A. Cassel, A. Cohen, and T. Koren. Rate-optimal online convex optimization in adaptive linear control. arXiv preprint arXiv:2206.01426, 2022.
[17] A. B. Cassel and T. Koren. Online policy gradient for model free learning of linear quadratic regulators with VT regret. International Conference on Machine Learning, pages 1304-1313. PMLR, 2021.
[18] X. Chen and E. Hazan. Black-box control for linear dynamical systems. In Conference Learning Theory, pages 1114-1143. PMLR, 2021.
[19] A. Chernov and F. Zhdanov. Prediction with expert advice under discounted loss. In Interna- tional Conference on Algorithmic Learning Theory, pages 255-269. Springer, 2010.
[20] A. Cohen, A. Hasidim, Koren, N. Lazic, Y. Mansour, K. Talwar. Online linear quadratic control. In International Conference on Machine Learning, pages 1029-1038, 2018.

---

[21] A. Cohen, T. Koren, and Y. Mansour. Learning Linear-quadraie regulators efficiently with only
VT regret. In International Conference on Machine Learning, pages 1300-1309, 2019.
[22] V. Dani, T. P. Hayes, and M. Kakade. Stochastic linear optimization under bandit feedback. 2008.
[23] S. Dean, H. Mania, N. Matni, B. Recht, and S. Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. Advances in Neural Information Processing Systems, 31, 2018.
[24] M. K. S. Faradonbeh, A. Tewari, and G. Michailidis. Finite time analysis of optimal adaptive policies for linear-quadratic systems. arXiv preprint arXiv: 2017.
[25] M. Fazel, R. Ge, S. Kakade, and M. Mesbahi. Global convergence of policy gradient methods for the linear quadratic regulator. In Proceedings of the 35th International Conference on Machine Learning, volume 80, 2018.
[26] Gradu, J. Hallman, and E. Hazan. Non-stochastic control with bandit feedback. Advances in Neural Information Processing Systems, 13:10764-10774 2020.
[27] M. Ibrahimi, A. Javanmard, and B. Roy. Efficient reinforcement learning for high dimensional linear quadratic systems. Advances in Neural Information Processing Systems, 25, 2012.
[28] A. Kalai and S. Vempala. Efficient algorithms for online decision problems. Journal of Computer and System Sciences, 7 71(3):291-307, 2005.
[29] S. Lale, K. Azizzadenesheli, B. Hassibi, and A. Anandkumar. Logarithmic regret bound in partially observable linear dynamical systems. Advances in Neural Information Processing Systems, 33:20876 21-00876-2088,, 2020.
[30] D. Malik, A. Pananjady, K. Bhatia, K. Khamaru, L. Bartlett, and M. Wainwright. Derivative- free methods for policy optimization: Guarantees for linear quadratic systems. Journal of Machine Learning Research, (1(21):1-51, 2020.
[31] H. Mania, S. Tu, and B. Recht. Certainty equivalence is efficient for linear quadratic control. In Advances in Neural Information Processing Systems, volume 32, pages 10154-10164, 2019.
[32] Y. Ouyang, M. Gagrani, and R. Jain. Control of unknown linear systems with thompson sam- pling. In 2017 55th Annual Allerton Conference on Communication, Control, and Computing (Allerion), pages 1198-120s IEEF, 2017.
[33] O. Plevrakis and E. Hazan. Geometric exploration for online control. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 7637-7647. Curran Associates, Inc., 2020.
[34] A. Rosenberg, A. Cohen, Y. Mansour, and H. Kaplan. Near-optimal regret bounds for stochastic shortest path. In International Conference on Machine Learning, pages 8210-8219. PMLR, 2020.
[35] M. Simchowitz and D. Foster. Naive exploration optimal for online lqr. In International Conference Machine Learning, pages 8937-8948. PMLR, 2020.
[36] M. Simchowitz, K. Singh, and E. Hazan. Improper learning for non-stochastic control. In Conference on Learning Theory, pages 3320-3436. PMLR, 2020.
[37] S. Tu and B. Recht. The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint. In Conference on Learning Theory, pages 3036-3083 PMLR, 2019.
[38] M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-936. 2003.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] in the supplementary material
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(C) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "vcxT36D_vVN", "reviewer": "Reviewer_F712", "summary": "The paper looks at the problem of controlling a linear dynamical system when there are adversarial convex cost functions. They study this problem in the setting when there is full feedback on the cost and the current state of the system. They provide an algorithm that obtains optimal regret even when the cost functions are not strongly convex. They also provide a non-convex lower bound for the cost.", "questions": "What are the challenges of moving away from a full feedback model to a limited feedback model? What if you were to observe the state and/or the cost function, with some form of error? How would this affect the tractability of the problem?", "limitations": "The paper points out that the meta-algorithms they use as experts have inherent randomness that could result in instability. They point out that the use of a follow the lazy leader algorithm helps stabilize the effects. They state that there are inherent challenges of using the follow the lazy leader algorithm as it does not work well against non-oblivious adversaries. They do get over this barrier by using gaussian distribution assumptions on noise.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- Originality: The problem of controlling linear dynamical systems has been studied in the literature. The paper attempts to further this study by considering the model of adversarial and general convex cost functions. They provide a computationally efficient algorithm that gives near-optimal regret.\n\n- Quality and Clarity: The paper is well written and clear.\n\n- Significance:  The paper claims to provide the first computationally efficient algorithm that achieves near-optimal regret for the linear dynamical system when the cost functions change over time.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "iANWJ8_6AE", "reviewer": "Reviewer_2qLS", "summary": "This paper considers the task of controlling an unknown (stochastic) linear dynamical system subject to changing convex costs revealed online. The main result is a computationally efficient achieving T^0.5 regret against the class of stable linear policies. ", "questions": "I understand the need to play slow-moving iterates. But neither once-randomized FTPL nor shrinking dartboard is necessary here, to the best of my comprehension, because the underlying decision space is continuous, obviating the need for explicit sampling. Here is a simpler alternative.\n\nGiven M_1, … M_K expert recommendations, and (normalized) weights from a MW instance p_1, .. p_K, play the policy M’=sum_i p_i M_i. By convexity of the true cost, cost(M’) < sum_i p_i cost(M_i). Furthermore, p_i’s change slowly as usual. I point out MW for simplicity, but any low-regret algorithm with slow moving iterates is equally suitable (e.g. OGD or the expected iterate for FTPL).\n\nIn fact, this approach has potentially greater technical merit in that it also works for adaptive adversaries.\n\nCan the authors comment on this consideration?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "— The previously best known regret bound was T^2/3, improvable to T^0.5 for strongly convex costs or in the stochastic setting. This is an unambiguous improvement.\n\n— The primary innovation here is choosing the compatible efficient implementation of OFU to combine with OGD/regret-minimizing algorithm. The typically non-convex optimistic cost can be convexified with the correct guess of the active norm constraint; this was used in the recent result (CCK’22) on stochastic costs. \n\n— Here the natural choice would be to use a regret minimizer to guess this active constraint, except such a procedure would only be sound if the cost associated the norm penalty was stationary, i.e. when the best in hindsight decision coincides with the point-wise best. This stationarity is what the paper notes (Line 211). Notably, this characterization was also true, but not necessary for the result, in the stochastic case (CCK’22). I think this observation is neat.\n\n— The paper is well written, and, to a great extent, linearly readable.\n\nSetting apart the FTPL/switching issue (see below), I do not have any reservations on the claims made.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "R1phW3dyZ0y", "reviewer": "Reviewer_jGE4", "summary": "The paper provides a high-probability $\\tilde{O}(\\sqrt{T})$ regret bound for online linear control with convex, Lipshitz costs and stochastic noise with known covariance provided a stabilizing controller.  This is in contrast to existing work with $O(T^{2/3})$ regret for convex costs or $\\tilde{O}(\\sqrt{T})$ with restrictions on costs like strong convexity.", "questions": "Could notation be described earlier before the algorithm?", "limitations": "The authors could do a better job of relating the assumptions of this work to other related works.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Online linear control is a classically important problem and policy regret approaches to the problem have been popular in the last few years.  Improved rates are a worthwhile problem.\n- The approach is technically challenging, combining lower confidence bound techniques, online control policies, along with slowly changing experts.  These cannot be naively combined as dealing with the nonconvexity of the lower confidence bounds requires cleverness.\n- The exposition of the algorithm/proof are relatively easy to understand and follow\n\nWeaknesses:\n- Much of the recent work in online control focused on regret-minimization allows for adversarial bounded costs.  Stochastic noise with known covariance is much weaker.\n- Stabilizing controller is required for this method while some other methods are fully black box.\n- Some parts of the writing can be a bit hard to follow notation wise.  For example, understanding that $k$ was a tuple as defined in the equation 3 required reference to the algorithm. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "IK7Mgu8y2W", "reviewer": "Reviewer_U5w9", "summary": "The authors study the problem of online control of an unknown linear dynamical system w.r.t. a sequence of (oblivious) adversarial cost functions. They give a computationally efficient algorithm that achieves $O(\\sqrt{T})$ regret, compared to the best static stabilizing controller in hindsight. Their approach does not require strong convexity of the cost functions as in prior work.", "questions": "- As pointed out by the authors, one drawback of the DAP policy class is that it requires the noise disturbance sequence $\\{w_t\\}$ to compute the action $u_t$. An alternative parameterization is the system level synthesis framework (see Section 2 of Anderson et al. https://www.sciencedirect.com/science/article/abs/pii/S1367578819300215), which is essentially the DAP parameterization with an extra subspace constraint involving the dynamics. By adding the subspace constraint (which can be encoded using the current $(A_t, B_t)$), one can then turn the DAP policy into a proper state feedback policy. I wonder if this parameterization would simplify various aspects of both the algorithm (no need to estimate the noise sequences in Line 8), and the proof.  ", "limitations": "- As mentioned previously, no experiments. In my opinion, condensing Section 4 and adding an experimental evaluation would further strengthen this paper from accept to strong accept.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- Paper is well written.\n- Authors advance the state of the art in online LQR control.\n- Proof techniques may be of independent interest. \n\n**Weaknesses:**\n- The algorithm is not the most straightforward, and involves a lot of different components (each of the components are, however, standard in the OCO literature). \n- No experiments showing that the algorithm is actually practical.\n- I would have liked to see a much more detailed comparison to Cassel et al. [16]. The setting of [16] is stochastic (instead of adversarial costs), but Algorithm 1 from [16] seems similar. The main difference is that the OFU step in [16] is replaced with the BFPL step in Lines 15-18 of Algorithm 1. Is this for computational reasons only, or is this actually necessary? (Apologies if this is an obvious question, I am not an expert in online convex optimization). This is also where an experiment would have been nice, to see the practical difference between these two algorithms.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept