Optimal Rates for Bandit Nonstochastic Control
Authors: Y. Jennifer Sun
Stephen Newman
Elad Hazan
Venue: NeurIPS 2023 poster (2023)
Keywords: Bandit control
online learning

Abstract: Linear Quadratic Regulator (LQR) and Linear Quadratic Gaussian (LQG) control are foundational and extensively researched problems in optimal control. We investigate LQR and LQG problems with semi-adversarial perturbations and time-varying adversarial bandit loss functions. The best-known sublinear regret algorithm~\cite{gradu2020non} has a $T^{\frac{3}{4}}$ time horizon dependence, and its authors posed an open question about whether a tight rate of $\sqrt{T}$ could be achieved. We answer in the affirmative, giving an algorithm for bandit LQR and LQG which attains optimal regret, up to logarithmic factors. A central component of our method is a new scheme for bandit convex optimization with memory, which is of independent interest.

Optimal Rates for Bandit Nonstochastic Control
Y. Jennifer Sun Princeton University Google DeepMind ys ys7849@princeton..
Stephen Newman Princeton University an
Elad Hazan
Princeton University & Google DeepMind
ehazangorinceton.dd
Abstract
Linear Quadratic Regulator (I.QR) and Linear Quadratic Gaussian (LQG) control are foundational and extensively researched problems in optimal control. We investigate LQR and LQG problems with semi-adversarial perturbations and time- varying adversarial bandit loss functions. The best-known sublinear regret algo- rithm of Gradu et al. [2020] has T time horizon dependence, and the authors posed an open question about whether tight rate of VT could be achieved. We answer the affirmative, giving an algorithm for bandit LQR and LQG which attains optimal regret (up to logarithmic factors) for both known and unknown systems. A central component of our method is new scheme for bandit convex optimization with memory, which of independent interest.
Introduction
Linear-Quus Qreea--uuadaatc Regulator (LQR) and the more general Linear-Gaussian (LQG) control problems have been extensively studied in the field of control theory due to their wide range of applications and admittance of analytical solutions by the seminal works of Bellman [1954] and Kalman [1960]. LQR and LQG control problems study the design of a feedback control policy for linear dynamical system with the goal of minimizing cumulative, possibly lime-varying quadratic costs. The discrete version of the problem studies the control of the following linear dynamical system governed by dynamics (A, B, !:
X Ax; Bu, + W: Yr Cx, + e:
where at time f, x; represents the system's 's state, u, represents the control exerted on the system, and (wr]7_ represents sequence of i.i.d. centered Gaussian perturbations injected to the system. For a simple example of the model, consider the problem controlling an elevator to reach the desired floors while minimizing the discomfort (due to acceleration deceleration) and the energy consumption. In this case, the state X, would be vector consisting of the elevator's position and velocity at time f. The control input u, is the force applied by the elevator motor time t. w, represents process noise at time t, caused possibly by unexpected mechanical disturbances. In the generality of LQG, the system's states are not accessible. In the elevator example, one may have the access to the measurement of the elevator's velocity or the precise position of the elevator. Instead, the algorithm has access to an observation yı, which is linear transformation state perturbed by sequence {er]T= of i.i.d. centered Gaussian noises, i.e. the elevator's observed position. The cost is
'The LQR/LQG dynamics be generalized to time-varying linear dynamical systems. Here restrict ourselves linear time-invariant systems for simplicity.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

a quadratic function of both the observation and the control exerted. The goal in LQR/LQG problems find control policy æ in some policy class II that minimizes the cumulative cost over finite time horizon T. With ył iy denoting the observation and control at time / resulted from executing policy n, the objective is formally given by
T Ea(y7.u7 4 = Σ yi T Quy7 + R.
T
minimize *eIl
(T((T) del
where Qc, Rs are some possibly time-varying stigh-wei and weightin matrices, re- spectively. In the elevator example, if our goal is to control the elevator to reach the desired floors while minimizing the discomfort and the energy consumption, the cost function at every time step t may take the form et (y,, uz) ei cally+ Egonl 1 + 02 selluell2 where Egoal is the target position of the
elevator, C1 C2 0.
Variations of the LQR/LQG problem have garnered considerable interest in the machine learning com- munity. In the recent literature of online nonstochastic control, several setting-based generalizations to the aforementioned linear-control framework have been explored, including:
A Adversarial cost functions (Cohen et al. [2018], Agarwal et al. [2019a]). In this setting, the cost functions are adversarially chosen in an unpredictable way to the learner. This generalized formulation allows for applications such as building climate control in the presence of time-varying energy costs, as the energy costs may depend on unexpected demand fluctuation (Cohen et al. [2018]). More recently, the model of adversarially chosen cost functions, along with adversarial perturbations in the subsequent paragraph, give rise to building connection between control theory and meta optimization (Chen and Hazan [2023]), where the nonconvex problem of hyperparameter tuning (e.g. learning rate tuning) can be reduced to online nonstochastic control, which often admits convex formulation.
Adversarial perturbations (Agarwal et al. [2019a], etc.): In this setting, differing from i.i.d. the usual Gaussian assumption on the perturbation distribution (w, ~ N NO, Σ)), non- stochastic control often considers arbitrary disturbances w, in the dynamics. The relaxed assumption on the perturbations allows for the control of nonlinear systems under model inaccuracies by approximating them as linear systems (Ghai al. [2022].
Together with the aforementioned two generalizations, control under bandit feedback further generalizes the control problem and suits many real-world applica- tions. In the bandit setting, the cost functions is unknown to the learner. The learner has access only to the cost incurred by their chosen control. In addition, the learner has access the system's is state (x; in the fully observed LQR setting) or noisy, possibly and usually low-dimensional observation (y: in the partially observed LQG setting). The bandit LQG problem can be illustrated with a motivating example. In the problem of controlling medical device such as ventilator, the state usually represents number of health status indicators of the patient, such as heart rate, blood pressure, and other related metrics. However, this state may not be fully observable. After the treatment is provided, the learner can observe the patient's 's response, e.g. changes in some vital indicators, with some observation noise and a cost function, e.g. deviation from the targeted breathing pattern. In this limited information setting, can a learner hope to learn meaning controls under minimal assumptions? Previ- ously, the work of Gradu et al. [2020] and Cassel and Koren [2020] both studied the bandit nonstochastic control problem of fully observed systems and provided provable guarantees.
Bandit feedback:
Taken together, these settings give rise to a general setting in differentiable reinforcement learning that strictly contains variety of classical problems in optimal and robust control. Naturally, when adversarial costs and perturbations are considered, an optimal solution is not defined a priori. Instead, the primary performance metric is regret: the difference between the total cost of control algorithm and that of the best controller from a specific policy class in hindsight.
As mentioned above, this general setting of bandit nonstochastic control was considered in the recent work of Gradu et al. [2020], whose proposed Bandit Perturbation Controller (BPC) algorithm has a provable regret guarantee of Ö when compared to a rich policy class called disturbance action controllers (DAC) for fully observed systems. Similar setting has also been studied by Cassel and Koren [2020], who established an optimal regret up logarithmic factor of Ó(vT) for fully
2

---

observable systems under stochastic perturbations and adversarially chosen cost functions. Recently Ghai al. [2023] improves the dimension dependence of regret bounds using exploration in action- space rather than parameter-space. However, bandit control for partially observable systems (e.g. IQQ)) less understood. Thus, these developments in the search for efficient, low-regret bandit online control algorithms leave a central open question (also stated by by Gradu et al. [2020]):
Can we achieve optimal regret (vT) with bandit LQG and nonstochastic noise?
Our work answers this question up to logarithmic factors. Our novel Ellipsoidal Bandit Perturbation Controller (EBPC) achieves Ö(VT) regret guarantee in the presence of semi-adversarial perturba- tions in bandit LQG problems with strongly convex cost functions, with the additional generality of possibly unknown system dynamics. By Shamir [2013], this is asymptotically optimal up to logarithmic factors, as bandit optimization over quadratics reduces to bandit control with quadratic losses under A 0, B I. Our work therefore resolves the upper- upper-bounds woaedd/wwwe-bbbutt gap for this generalization of LQR/LQG. The following table gives a comprehensive comparison between the regret guarantee of EBPC and existing results in literature.
Table 1: Comparison of previous results contributions.
Algorithm
Noise
Observation
Feedback System
Regret
Agarwal et al. [2019a]
Adversarial
full
full
known
O(VT)
Agarwal al. [2019b]
Stochastic
full
full
known
O(1)
Foster and Simchowitz [2020]
Adversarial
full
full
known
0(1)
Simehowitz al. [2020]
Semi-Adv.
partial full
known
O(1)
Simchowitz et al. [2020]
Semi-Adv.
partial full
unknown
Ö(VT)
Gradu et al. [2020]
Adversarial
full bandit
unknown
O
Cassel and Koren [2020]
Stochastic
full
bandit
known
O(VT)
Cassel and Koren [2020]
Adversarial
full bandit known
Ö(Tड)
Theorem 4.1
Semi-Adv.
partial bandit known
O(VT)
Theorem 4.2
Semi-Ady.
partial bandit
unknown
O(VT)
1.1 Related work
Online Nonstochastic Control and Online LQR. In the last decade, much research has been devoted to the intersection of learning and control. Abbasi-Yadkori and Szepesvári [2011] and Ibrahimi et al. [2012] considered the problem of learning a controller in LQR for known quadratic cost functions and stochastic/martingale difference perturbation sequence when the dynamics of the system unknown, and achieved Ö(VT)) -regret in this case. Dean et al. [2018] provided the first provable low-regret, efficient algorithm to solve LQR problems with known cost functions and stochastic perturbations. Cohen et al. [2018] extended this result to changing quadratic costs with
stochastic perturbations and provided regret guarantee of O(VT). Lale et al. [2021] consider the LQG problem with stochastic noise and unknown systems.
More recently, interest has turned nonstochastic control, in which the cost functions and the perturbations can be adversarially chosen Agarwal et al. [2019a]. A broad spectrum of control problems were reconsidered from the nonstochastic perspective, and several different generalizations were derived. See Hazan and Singh [2022] for a comprehensive text detailing these results.
Online Bandit Convex Optimization with Memory. A classical approach nonstochastic control of stable/stabilizable linear dynamical systems is to reduce control problems to online convex optimization with bounded memory. This reduction stems from the observation that the effects of past controls decay exponentially in stable/stabilizzble systems. In the bandit online convex optimization with bounded memory setting, the learner iteratively plays decision æ; in a convex set C Rd and suffers an adversarially chosen loss Fr(x,, 111,), where x;- 11 is the sequence of points Jt- #+1, ..., Tt. particular, the loss depends on the last H points played by the algorithm, and the only information revealed to the learner is the scalar loss that they incurred. The goal is to minimize
3

---

regrer, the difference between the loss actually suffered and the loss suffered under the best single play in hindsight:
Regrety
def
F(( 1=H
min æEK
Σ Fz.
Since the loss function is unknown to the learner in the bandit setting, online bandit convex opti- mization algorithms make use of low-bias estimators of the true gradient or Hessian. Therefore, is standard to measure the algorithm's performance by regret over the expectation of losses, where the expectation is taken over the randomness injected when creating such estimators.
Online convex optimization with memory in the full information setting, where the loss function known to the learner, was proposed by Anava et al. [2015]. The work of Agarwal et al. [2019a], was the first to connect this to control, and to give regret bound for online control with adversarial perturbations.
The Ö(T*) regret bound of Gradu et al. [2020] leveraged the bandit convex optimization method of Flaxman et al. [2005]. We focus on the bandit LQR//LQG setting with strongly convex and smooth loss functions. It thus natural use the techniques of Hazan and Levy [2014], 4], who obtained a Ö(VT) regret guarantee for bandit convex optimization without memory.
Online Learning with Delay. One technical difficulty in extending OCO with memory to the bandit setting arises from the requirement of independence between every play and the noises injected from the recent H steps. We resolve this issue by adapting online learning with delay to the subroutine algorithm used in our BCO algorithm. Online learning with delay was introduced by Quanrud and Khashabi [2015]. In particular, Flaspohler et al. [2021 relates online learning with delay to online learning with optimism and established a sublinear regret guarantee for mirror descent algorithms. A similar delay scheme was seen in [Gradu et al., 2020].
1.2 Notations and organization
Notation. For convenience and succinctness, we denote H del H- 1. We use lowercase bold letters (e.g. x,y, e) to denote the states, observations, controls, and noises of the dynamical system 2, and dx. du, dy to denote their corresponding dimensions. We use 5 to denote the unit sphere in I as 5n-1 m=- R++ + denote all non-negative, positive real numbers, respectively. For a differentiable function F (R*) - IR, we denote the gradient of F with respect to its ith argument vector by v-)(. p(-) acting on a square matrix measures the spectral radius of the we use [| to denote the sum of the operator norm: def Eier |lop (A4 denotes the o-algebra generated by a random variable A. We use O() to hide all universal constants, (-) to hide poly(log) 2") terms, and (-)) to hide all natural parameters.
1.
matrix. For a sequence M =
||M op
Organization. Our method has two main components: a novel algorithm for BCO with memory (EBCO-M), and its application building a novel bandit perturbation controller (EBPC). Section describes our problem setting. Section 3 gives EBCO-M and its near-optimal regret guarantec. Section introduces EBPC and its regret guarantees both known and unknown systems.
2 The Bandit LQG Problem
In this section we provide necessary background and describe and formalize the main problem of interest. We consider control of linear time-invariant dynamical systems the form
Ax; + Bu, + Wt. Yt Cx; + e:
(2.1)
with dynamics matrices A E xd B dd xdu, C E xd2,
xdx, Here, consistent with previous notations, X E dd is the state of the system at time f, u, E IRd is the control applied at time t, and
It shall be noted that unbolded the linear dynamical system.
are used in the EBCO-M algorithm (Algorithm 1) and is unrelated to

---

Wt RR*. e2 E R' are the system and measurement perturbations. At each timestep, the learner may observe yt R which usually represents a possibly noisy projection of the state x, onto some (possibly and usually) low-dimensional space.
In the online bandit setting, the learner is asked perform control at time f. After the control is performed, the adversary chooses a quadratic cost function ee (y,, ut). The learner observes the scalar er (Yr; Ur) + and the signal ys, but no additional information about c)(:-), Xt, W., e, given. The goal of the learner is to minimize expected regret, where regret against the controller class II is defined as
Regrety def
Caly,, min well
ca cy7
(2.2)
where . is the control exerted at time by policy n, and yJ is the time-t observation that would have occurred against the same costs/noises if the control policy π were carried out from the beginning.
In controlling linear dynamical systems with partial observations, we often make use of the system's counterfactual signal had no controls been performed since the beginming of the instance:
Definition 2.1 (Nature's 's y). Nature's 's at time t, denoted by y is the signal that the system would have generated at time under U1:t = O. We may compute this as
nat = AAxpat We. y! = Cxxpat
or, equivalently, y! e, + E1= CAA-i-l w.
Critically, this may be calculated via the Markov operator:
Definition 2.2 (Markov operator). The Markov operator G |G corresponding to linear system parametrized by B.) as in 12. is sequence of matrices in IRdy xda such that GM def CA G del Od, xdu
follows immediately that y may be computed from observations as y = yr - -i Gl u
2.1 Assumptions
We impose four core assumptions on the problem:
Assumption 2.3 (Stable system). We assume the system is stable: the spectral radius p(A) < 1
This assumption has the following important consequence:
Remark 2.4 (Decay of stable systems). That the system is stable implies that 3P Od Xdg.
P Sym(dz) such that rP > A PA for some 0 r < 1, and therefore 3x depending on [B]o [[Cllop, mmiu(P) such that [lop I kT Then with (log T), we can assume that ||G]] Ei || S RG and (H) def Σ ||GL loop S Re.
Together, Assumption 2.3 and its consequence Remark 2.4 allows modeling the nonstochastic control problem as an online convex optimization problem against adversary with bounded memory, as the effect of past controls decays exponentially. Assumption 2.5-2.7 introduce the assumptions on the adversarial cost functions and perturbations.
Assumption 2.5 (Noise model). The perturbations {W:, e are assumed to be semi-adversarial:
Wt. e₁ decompose as sums of adversarial and stochastic components we = w = + egdv e The stochastic components of the perturbations are assumed to come come distributions stoch oe > O. (We, e are bounded such that |lymat Reate Vl. for some parameter Reat-
wiicch and e; =
satisfying E[[[toch]] Ejectoch] 0. w watcch w wttcch
L E stocc e ]] > IZI,
"Although out of scope of this work, we refer the readers to Appendix G of Simchowitz et al. [2020] for a possible and expected extension of out results to the relaxed assumption of stability: the learner is given access stabilizing controller of the system.
5

---

The bound on y is implied by bounded noise, which is standard assumption in literature, and the stability of the system. The remi-adversarias assumption is also seen in prior work [Simchowitz et al., 2020], and is a necessary condition for our analysis: we depend on the regret guarantee of bandit online convex optimization with memory algorithm which requires the strong convexity of the expected loss functions conditioned on all but the (poly T)) most recent steps of history. This assumption is essentially equivalent to the adversarial assumption in applications: in almost all systems, noise is either endemic may be injected. We also emphasize that this assumption is much weaker than that of previous optimal-rate work: even in the known-state, known-dynamic case, the previous optimal guarantee in the bandit setting depended 1).
adversarial perturbation (see Table
Assumption 2.6 (Cost model). The cost functions c) are assumed be quadratic, ae-strongly convex, Se-smooth, iee. cely, u) yT_QQQ Q.y + u R&u with Bel = Q2 ,eI, 'zz Rí x a.l Vl. They are also assumed obey the following Lipschitz condition: v(y, u), (y', u') Rdy
|ce u) cyy', u')l S Loll, u)ll2 V II(y', ,')ll))) - y', , 1')l2
(2.3)
These conditions are relatively standard for bandit convex optimization algorithms,, and are needed for the novel 1-0--wih-mmmrr algorithm which underpins our control algorithm.
Assumption 2.7 (Adversary). {<r(s )), wady eeddv ji=1 is chosen by the adversary ahead of time.
2.2 Disturbance Response Controllers
Regret compares the excess cost from executing our proposed control algorithm with respect the cost of the best algorithm in hindsight from given policy class. In particular, low regret against rich policy class is very strong near-optimality guarantee. We take the comparator policy class II to be the set of disturbance response controllers (DRC), formally given by the following definition.
Definition 2.8 (Disturbance Response Controllers). The disturbance response controller (DRC) and the DRC policy class defined as:
A disturbance response controller (DRC) is a policy TMs parametrized by M (Mbi) o- where H E Z44+, a sequence of H matrices in Rduxdy s.t. the control at time given by TM u MM =
fi =ド M Mlatt t-jj We shorthand u def u
The DRC policy class parametrized by H E Z R E R4 is the set of all disturbance response controller with bounded length H and norm R: M(H It) = [M = (M
[M = ΣØ || S R).
Previous works have demonstrated the richness of the DRC policy class. In particular, Theorem 1 from Simehowitz et al. [2020] has established that the DRC policy class generalizes the state-of-art benchmark class of stabilizing linear dynamic controllers (LDC) with error e -(I)).
2.3 Approach and Technical Challenges
The classical approach in online nonstochastic control of stable/stabilizable systems is to reduce to problem of online convex optimization with memory. This insight relies on the exponentially decaying effect of past states and controls on the present, which allows approximating the cost functions as functions of the most recent controls.
core technical challenge lies in the bandit convex optimization problem obtained from the bandit control problem. In the bandit setting, no gradient information is given to the learner, and thus the learner needs to construct low-bias gradient estimator. Previous work uses the classical spherical gradient estimator proposed by Flaxman et al. [2004], but the regret guarantee is suboptimal. We would like to leverage the ellipsoidal gradient estimator proposed by Hazan and Levy [2014]. However, when extending to loss functions with memory, there is no clear mechanism for obtaining a low-bias bound for general convex functions. We exploit the quadratic structure of the LQR/LQG cost functions to build EBCO-M (Algorithm 1), which uses ellipsoidal gradient estimators. We note that even outside of the control applications, FRCO-M may be of independent interests in bandit online learning theory.

---

3 BCO with Memory: Quadratic and Strongly Convex Functions
As with previous works, our control algorithm will depend erucially on generic algorithm for bandit convex optimization with memory (BCO-M). We present new online bandit convex optimization with memory algorithm that explores the structure of quadratic costs to achieve near-optimal regret.
3.1 Setting and working assumptions
In the BCO-M setting with memory length H. consider an algorithm playing against an adversary. At time f, the algorithm is asked to play its choice yt in the convex constraint set K. The adversary chooses loss function F; K R2 which takes input the algorithm's 's current play as well as its previous H plays. The algorithm then observes a cost (y H..... Mr) (and no other information about Fi(-)) before it chooses and plays the next action yt-11 The goal is to minimize regret with respect to the expected loss, which the excessive loss incurred by the algorithm compared to the best fixed decision in K::
T B[Fi(ycH..... H. ve) min SEK. 1=
T
Regrety def
E[Fi(T
x)}.
For notation convenience, will at times shorthand U--A ..... Ve) E K
def
3.1.1 BCO-M assumptions
We make the following assumptions the loss functions {Fi)T н and the constraint set K. Assumption 3.1 (Constraint set). K. is convex, closed, and bounded with non-empty interior. diam(K) sup || 22112 - D.
E,='EK
Assumption 3.2 (Loss functions). The loss function chosen by the adversary obeys the following regularity and curvature assumptions:
F. KH R4 is quadratic and B-smooth:
Quadratic: 3W, E RRHxxHH be E RRH Ce E R such that F((w) = w W.w + 6J
Ct Vw E K.H.
Smooth: W, N 3.nHHxHH
F2 KCH + RR is a-strongly convex in its induced unary form: ft KC -+ RR., with Se(z)
Fe(z,....,3' 2) is --strongly convex, iee. fe(z) 2 fe(z') + Vf((2)) (z z²) + 211 2| 2 1
V2, 2' E E.
Ft satisfies the following diameter and gradient bound on K.: 3B, T. such that
B sup (F((w) F((w)), L sup w.we EK
[F)(w)l2
WEKH
In the online control problems, when formulating the cost function as a function Fe of the most recent H controls played, the function Fr itself may depend the entire history of the algorithm through step - H. Therefore, it is essential to analyze the regret guarantee of our BCO-M algorithm when playing against adversary that can be (1 -dddppiive, giving rise the following assumption.
Assumption 3.3 (Adversarial adaptivity). The adversary chooses F; independently of the noise Bt which is drawn by the algorithm in the H most recent steps, but possibly not independently of earlier noises.
Note that Assumption 3.3 is minimal for BCO: if this fails, then in the subcase of delayed loss, the adversary may fully control the agent's 's observations, resulting in no possibility of learning.
Self-concordant barrier. The algorithm makes use of self-concordant barrier R(-) of IC as the regularization function in the updates.
7

---

Definition 3,4 Self-connorrant barrier). A three-time continuously differentiable function R(-) over a closed convex set K. C IR with non-empty interior is v-self-concordant barrier of K. if satisfies the following two properties:
(Boundary property) For any sequence (InJaEN C in)(()) such that tim Un = OK.
limn-sos R(xn) = DC.
2. (Self-concordant) Vor E int( h E R",
(a) [V) h, A|] s 2 [(=)[,, h|/3/2
(b) (VR(<)) S (> h/]l/2
3.2 Algorithm specification and regret guarantee
We present EBCO-M (Algorithm for online bandit convex optimization with memory. The key novelty is the use of an ellipsoidal gradient estimator. It is difficult to establish a low-bias guarantee for ellipsoidal gradient estimator for general convex loss functions. However, thanks to the quadratic structure of the loss functions in L.QR/LQGG problems, we can show provable low bias for the ellipsoidal gradient estimator, and therefore achieve optimal regret.
Algorithm 1 Ellipsoidal BCO with memory (EBCO-M)
1: Input: Convex, closed set K. C IR" with non-empty interior, time horizon T, memory length H, step size 1) p-self-concordann barrier R(-) over K, convexity strength parameter a.
2: Initialize Tt arg min R(x), Vt I,...,
3: Compute A, = (V R(x;) + no(l) -1/2 VI ...... H.
4: Sample u...... Uf 5n i.i.d. uniformly at random.
5: Set y = 34 + Ar Vt = 1, 1..... H. H.
6: Set 9: 0, Vt =
7: Play y1,...,
8: for t == H,...,TT do
9: Play yr, suffer loss (1 A:t). H
Store 9: nFi(y (FF(() Σi=0 A-1 u
11: Set F++1 = arg min E.=H -0-0 x 211x= x, x- a1²)
1 R(x).
12: Compute A++1 (V2 R((()))) + no(t 1)1)
Sample ut+1 Sn-1 uniformly at random.
14:
Set Vt+1 = I++1 A.414
end for
Before analyzing the regret, we first make note of two properties of Algorithm
Remark 3.5 (Delayed dependence). In Algorithm xı is independent of u Bitr VI, and therefore A, is independent of U as A, is determined by dt-
Remark 3.6 (Correctness). Yt. played by Algorithm I lies in K:: ||y: [lye- Aeeeell S
[|, 2 1, and by Proposition C.I, the Dikin ellipsoid centered al T4 is contained in K.
We give the following two theorems regret guarantees of the EBCO- M algorithm. In particu- lar, Theorem 3.6.B slight generalization of Theorem 3.6.A in its relaxation on the curvature assumption the sequence of loss functions FH-T-
Theorem 3.6.A (EBCO-B M regret with strong convexity). For any sequence of cost functions (F satisfying Assumption 3.2, constraint set satisfying Assumption 3.1. adversary satisfying Assump- tion 3.3, and H = poly (log T), Algorithu I satisfies the regret bound
min [[(((s)) (0 SEK
(EBCO-M
Σ (( t=H
1=H
where the expectation is taken over the randomness of the exploration noises uI.T with Ô hiding all natural parameters (B, D, L) and logarithmic dependence T.
8

---

Theorem 3.6.B (EBCO-M regret with conditional strong convexity). Suppose Algorithm 1 is run on K satisfying Assumption 3.1 against an adversary satisfying Assumption 3.3 with sequence of random cost functions (Fr )t satisfying that
1. Ft is quadratic, convex, 3-smooth, has diameter bound B and gradient bound L on K
2. 3 filtration 91-r such that uir is independent of Gr. Fi o(uaa-H) U Gu and Fi is conditionally o-strongly convex in its induced unary form: f((z) E(f((=) W1--H Gc-Hl is o-strongly convex.
Then, Algorithm 1 satisfies the same regret bound attained Theorem 3.6.A, i.e.
T E[F
T Σ B[f((t)) BEK
( (3m O (TVVT
(EgCer,(E
min
where the expectation is taken over the randomness of the exploration noises u1.T and the random functions FH with hiding all natural parameters (B, D) and logarithmic dependence on T.
4 Bandit Controller: Known and Unknown Systems
We will now use our BCO-with- 1-00-with-mmooe memooyy algorithm to find an optimal controller (as in Gradu et al. [2020]), arguing that regret in choice of controller transfers into the setting discussed in the previous section. We first consider the case where the system is known, and then reduce the unknown system case to the known system case.
4.1 Known systems
Applying Algorithm to predict controllers' with losses given by control losses, we obtain Algorithm
Algorithm 2 Ellipsoidal Bandit Perturbation Controller (EBPC)
1: Input: Time horizon T, memory length H. Markov operator G. BCO-M parameters o, 1)- Self-concordant barrier R(-) over M(H, R) C. Hx H
2: Initialize M1 = MH arg min R(M).
MEM(H.R)
3: Compute A; (V R(M) not -1/2 Vi 1, ..... H.
4: Sample f,,..., EH Hd x
i.i.d uniformly random.
5: Set M, M, Eq. Vi l..... H. Set 9i 0. vi
I.... H.
6: Play control u, = 0, incur cost c, (y:, u.) Vi 1, H.
7: for H...., ....... T do
8: Play control u, = (M, = E M y incur cost co uy).
9: Observe 1 and compute signal y = Y-+i Ein Glul u
10:
Store 9: dudy (yr u,) Σ Ex= A-
11:
Update M = arg min Σ (1g. : M) I - MM-#1l?) + R(M) MEM(H.R)
12: Compute A411 = (V R(M + na (t + 1)12-1/2. 1/2
13:
Sample E1+1 S1 xdy xdy uniformly at random. Set M = Met1 + A4t15
end for
Theorem 4.1 (Known system control regret). Consider linear dynamical system governed by known dynamics (A, B)C) and the interaction model with adversarially chosen cost functions
typically a tensor, should thought of output vector of Algorithm 1. As such, the relevant vector and matrix operations in that algorithm will correspond to tensor operations here, and the notation reflects that correspondence. In particular, the inner product on line 11 is an all dimension tensor dot product and A is square "matrix" which acts on tensors of shape (H, du, dy).
NNotatio: while our controller

---

and perturbations satisfying Assumption 2.3, 2.5, 2.6, 2.7. Then running Algorithm 2 with H (ppoly(log T)), o - 0c O² + ow Cmin(C) and 1j = LudyLeHiVT
guarantees
(eRegrety(EBPQO S (Baluely vT
( Oc
where regret is defined in Eq.(.. the expectation is taken the exploration noises E1: the algorithm as well as the stochastic components (watoch, eqtoch Ji=1 of the perturbations {We, e j== and (-) hides all universal constants, natural parameters, and logarithmic dependence on T.
4.2 Unknown systems: control after estimation
Note that EBPC (Algorithm 2) relies the access to the system's 's Markov operator G, which is available and only if the system dynamics (A, B,C) C) are known. When the system dynamics is unknown,
identify the system using system estimation algorithm, obtain estimated Markov operator G, and run EBPC with G G. Algorithm 3 outlines the estimation method of system dynamics via least squares.
Algorithm 3 System estimation via least squares (SysEst-In
1: Input: estimation sample size N, system length H.
2: Initialize: (14) = O, VL. 2 H.
N. 4: Set G(O:N) arg min E lly: El 0
3: Sample and play u, N(0, Idy Xdux 11
5: Return G.
Theorem 4.2 (Unknown system control regret). Consider a linear dynamical system governed by unknown dynamics (A, B, C) and the interaction model with adversarially chosen cost functions and perturbations satisfying Assumption 2.3, 2.5, 2.6, 2.7. Suppose we obtain an estimated Markov operator G from Algorithm with N [VT] and H (pooly log T). Then Algorithmm 2 with guarantees
G+ G. H. 3H, a o and 1)
dutly HolyH
ElRegret, (EBPC)) < Ô (Sednddy
0oc VT
where regret is defined as in (2.2), the expectation is taken over the exploration noises E1.T in Algorithm the sampled Gaussian controls U1:N in Algorithm 3, and the stochastic components (witach, et astoch/7 1t=1 of the perturbations {w,, YT and Õ() hides all universal constants, natural parameters, and logarithmic dependence on T.
5 Discussion and conclusion
We solve the open problem put forth by Gradu et al. [2020] on the optimal rate for online bandit control for the case of LQR/LQG control, improving to regret Õ(VT) from Ö(T3) in the semi- adversarial noise model and for strongly convex LQR/LQG cost functions. Our method builds upon recent advancements bandit convex optimization for quadratic functions, providing the first near-optimal regret algorithm for bandit convex optimization with memory in nonstochastic setting.
would be interesting to investigate (1) whether the results can extended to fully adversarial noise, (2) whether similar stable controller recovery as seen in [Chen and Hazan, 2021] for fully observable systems can be established for partially observable systems, and whether that can incorporated to extend our result to stabilizable systems even without access to a stabilizing controller.
Acknowledgement
Flad Hazan acknowledges funding from the Office Naval Research grant 4000142312156, the NSF award 2134040, and Open Philanthropy.
10

---

References
Yasin Sabasi-Yadkond and Csaba Szepesvári. Regret bounds for the adaptive control of linear quadratic systems. In Proceedings of the 24th Annual Conference Learning Theory, pages 1-26. JMLR Workshop and Conference Proceedings, 2011.
Jacob Abernethy, Elad Hazan, and Alexander Rakhlin. Competing in the dark: An efficient algorithm for bandit linear optimization. In 21st Annual Conference on Learning Theory, COLT 2008, 2008.
Naman Agarwal, Brian Bullins, Elad Hazan, Sham Kakade, and Karan Singh. Online control with adversarial disturbances. In International Conference on Machine Learning, pages 111-119. PMLR, 2019a.
Naman Agarwal, Elad Hazan, and Karan Singh. Logarithmic regret for online control. Advances in Neural Information Processing Systems, 32, 2019b.
Oren Anava, Elad Hazan, and Shie Mannor. Online learning for adversaries with memory: price of past mistakes. Advances in Neural Information Processing Systems, 28, 2015.
Richard Bellman. The theory of dynamic programming. Bulletin of the American Mathematical Society, 60(6):503-515 -155003-511111 1954.
Asaf Cassel and Tomer Koren. Bandit linear control. Advances in Neural Information Processing Systems, 33:8872-888: 2020.
Xinyi Chen and Elad Hazan. Black-box control for linear dynamical systems. In Conference Learning Theory, pages 113. PMLR, 2021.
Xinyi Chen and Elad Hazan. A nonstochastic control approach to optimization. arXiv preprint arXiv:2301.07902, 2023.
Alon Cohen, Avinatan Hasidim, Tomer Koren, Nevena Lazic, Yishay Mansour, and Kunal Talwar. Online linear quadratic control. In International Conference on Machine Learning, pages 1029- 1038. PMLR, 2018
Sarah Dean, Horia Mania, Nikolai Matni, Benjamin Recht, and Stephen Tu. Regret bounds for robust adaptive control of the linear quadratic regulator. Advances in Neural Information Processing Systems, 31, 2018.
Genevieve E Flaspohler, Francesco Orabona, Judah Cohen, Soukayna Mouatadid, Miruna Oprescu, Paulo Orenstein, and Lester Mackey, Online learning with optimism and delay, In International Conference on Machine Learning, pages 3363-3373, PMLR, 2021.
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. arXiv preprint cs/0408007, 2004.
Abraham D Flaxman, Adam Tauman Kalai, and H Brendan McMahan. Online convex optimization in the bandit setting: gradient descent without gradient. In Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, pages 385-394, 2005.
Dylan Foster and Max Simchowitz. Logarithmic regret for adversarial online control. In International Conference on Machine Learning, pages
PMLR, 2020.
Udaya Ghai, Xinyi Chen, Elad Hazan, and Alexandre Megretski. Robust online control with model misspecification. In Learning for Dynamics and Control Conference, pages 1163-1175. PMLR, 2022.
Udaya Ghai, Arushi Gupta, Wenhan Xia, Karan Singh, and Elad Hazan. Online nonstochastic model-free reinforcement learning. arXiv preprint arXiv:2305. 17552, 2023.
Paula Gradu, John Hallman, and Elad Hazan. Non-stochastic control with bandit feedback. Advances in Neural Information Processing Systems, 33:10764-10777 2020.
Paula Gradu, John Hallman, Daniel Suo, Alex Yu, Naman Agarwal, Udaya Ghai, Karan Singh, Cyril Zhang, Anirudha Majumdar, and Elad Hazan. Deluca-a differentiable control library: 2021.
Environments, methods, and benchmarking. arXiv preprint
11

---

Elad Hazan. Introduction to online convex optimization. Foundations and Trends in Optimization, 235-4)::57-325, 2016.
Elad Hazan and Kfir Levy. Bandit convex optimization: Towards tight bounds. Advances Neural Information Processing Systems, 27, 2014.
Elad Hazan and Karan Singh. Introduction to online nonstochastic control. arXiv preprint arXiv:2211.06619, 2022.
Elad Hazan, Amit Agarwal, and Satyen Kale. Logarithmic regret algorithms for online convex optimization. Machine Learning. 69(2):169-192, 2007.
Morteza Ibrahimi, Adel Javanmard, and Benjamin Roy. Efficient reinforcement learning for high dimensional linear quadratic systems. Advances in Neural Information Processing Systems, 25, 2012.
Rudolph Emil Kalman. A new approach to linear filtering and prediction problems. 1960.
Sahin Lale, Kamyar Azizzadenesheli, Babak Hassibi, and Anima Anandkumar. Adaptive control and regret minimization in linear quadratic gaussian (lgg) setting. In 2021 American Control Conference (ACC), pages 2517-2522 IEEE, 2021.
Kent Quanrud and Daniel Khashabi. Online learning with adversarial delays. Advances in neural information processing systems, 28, 2015.
Ohad Shamir. On the complexity bandit and derivative-fiee free stochastic convex optimization. In Conference on Learning Theory, pages 3-24. PMLR, 2013.
Max Simchowitz, Karan Singh, and Elad Hazan. Improper learning for non-stochastic control. In Conference on Learning Theory, pages 3320-3436. PMLR, 2020.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference Machine Learning (ICML-03), pages 928 936, 2003.
12


Reviews:
[{"review_id": "MrZDSQt1kd", "reviewer": "Reviewer_6aiM", "summary": "This paper studies the online control problem with a quadratic cost function, adversarially chosen dynamics, and semi-adversarially chosen losses (they are the sum of a zero-mean term and an obliviously chosen adversarial term). The algorithm proposed lowers the previous $T^{3/4}$ algorithm to a $\\sqrt{T}$ algorithm against the class of disturbance response controllers, matching the lower bound. The crux of the analysis is handling the non-independence between plays and noise, which many OCO algorithms assume, and to carefully control the bias of the loss estimators. The authors solve the former with a novel method of using an online-learning with delay framework to bypass and the later by adapting an ellipsoidal gradient estimator. ", "questions": "A few questions are asked above.", "limitations": "As a very theoretical work, I don't think any discussion about negative societal impact is necessary. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "Good organization, really clear presentation and summary of the high-level ideas used in this and previous work. Excellent literature review as well. The overall structure of the paper is well organized, and the algorithm follows naturally from all the components used.\n\nThe significance is high, as this paper really makes progress in closing off a field of online control by matching a lower bound. Much steady progress has been made on this problem over the years, so this paper is a great next step for this community. Tangentially, I think some of the ideas for algorithm 1 will be useful for the bandits-with-memory community. ", "weaknesses": "Assumption 3.3 seems unnatural. Can you provide a bit more context on its necessity? More generally, how are ideas from learning with delay present in your algorithms? I did not find this point very clear.\n\nMight be worth mentioning that there are empirical evaluations in the main body. \n\nFinally, I wish the authors provided more intuition for how the proofs of the theorems worked; for example, what are the implications of using $\\hat G$ instead of $G$?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough review. We respond to your points here:\n\n1. **6aiM**: Assumption 3.3 seems unnatural. Can you provide a bit more context on its necessity? More generally, how are ideas from learning with delay present in your algorithms? I did not find this point very clear. **Response**: Assumption 3.3 is common (Gradu et al. 2020, for example) and turns out to be nearly minimal for bandit low-regret learning with memory. The noise in the semi-adversarial model is used by the gradient estimator, and if the adversary can observe and respond to that noise before the agent can, they can effectively remove it. In a case where agent state observation is delayed by one turn (via an off-diagonal transition matrix) and the adversary can condition response on the noise of previous steps, they can cause systematic misestimation of the gradient by effectively changing the noise distribution – or even remove its historical components entirely. Assumption 3.3 is analogous to the usual assumption that the adversary is not adaptive to the most recent algorithm decision (see, for instance, Flaxman et. al. (2008): “Online convex optimization in the bandit setting: gradient descent without a gradient”).\nBroadly, learning with memory is present as we attempt to learn a controller, but our choice of controller on a given step can affect our loss in subsequent steps. We will clarify this pursuant to point 3.\n\n2. **6aiM**: Might be worth mentioning that there are empirical evaluations in the main body. **Response**: Thank you for pointing this out. We agree, and will add it in the introduction section. \n\n3. **6aiM**: Finally, I wish the authors provided more intuition for how the proofs of the theorems worked; for example, what are the implications of using $\\hat{G}$ instead of $G$? **Response**: First, let us address your specific question: $G$ is the Markov operator introduced in Definition 2.2 (line 151, page 4, main text) associated with the system. When the system is known, we can compute $G$ and therefore directly use $G$ in the algorithm. When the system is unknown, we use Algorithm 3 to estimate the Markov operator and obtain $\\hat{G}$. The challenge in the unknown system case is that since $\\hat{G}$ is an estimation of the true Markov operator $G$, the estimation error would affect the controls played by the algorithm. We showed that this estimation error would propagate through the algorithm in a way such that the $\\tilde{O}(\\sqrt{T})$-regret is still preserved for the unknown system (Theorem 4.2, main text). On the general point, we thank you (and other reviewers) for pointing this out, and intend to add substantially more intuition for both the critical parts of the theorems and the structure of the algorithms.\n\nThank you again for your various comments, criticisms, and suggestions for improvement. We hope that our proposed changes address them to your satisfaction – please let us know if you have further questions or concerns.\n"}, {"review_id": "jKhq0YDB6U", "reviewer": "Reviewer_7wFb", "summary": "This paper studies LQG with semi-adversarial disturbances and bandit feedback. The authors proposed a novel algorithm with $\\sqrt T$ regret bound, which improves the $T^{3/4}$ regret bound in the literature. The algorithm utilizes the quadratic cost function structure and the ellipsoidal gradient estimator.", "questions": "In the main paper,\nQ1: the title is inconsistent with that on the openreview webpage. Please make them consistent.\n\nQ2: Why do the authors consider semi-adversarial disturbances? What are the benefits and limitations of this setting? Why do the authors simulate i.i.d. disturbances instead of semi-adversarial disturbances? \n\nIn the supplementary material, for the simulation results:\n\nQ3: Is the dynamical system known or unknown? If the system is unknown, how to obtain the optimal $K$ to the LQR problem? If the system is known, how does the algorithm perform under unknown dynamics?\n\nQ4: What's the y axis? Why is it 0.1, 0.01? The authors skipped most parts of the simulation setup and referred the reader to Gradu et al. 2020. But the figures look very different from those in Gradu et al. 2020. It is hard to interpret the simulation results without future explanation.\n\nQ5: The x axis scale goes as large as 100k, which is unreasonable for a control task. Is it possible to plot the figures in the same settings as in Gradu et al. 2020, where the horizon is usually within 1k?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The paper follows the classic disturbance-action policy and online nonstochastic control and OCO-M framework. The novel part is the Elllipsoida BCO with Memory algorithm and its regret analysis. The algorithm motivation and the key steps are explained clearly. \n\nThe paper solves an interesting open question that whether $\\sqrt T$ regret can be achieved for LQG under bandit feedback, under the assumption that the disturbances consist of both a large enough i.i.d. term and an adversarial term.", "weaknesses": "1. Simulation. The paper lacks simulation results for verification of the improved technical bound. Though the supplementary material provides some figures, the simulation setups are not clearly explained. See more questions in the next box.\n\n2. Novelty. I have mixed feelings about the novelty of this paper. On the one hand, the paper successfully improves the regret bound order to $\\sqrt T$. On the other hand, the majority of the algorithm design is based on the classic disturbance-action policy and OCO-M formulation, so I am not sure if the algorithm design is novel enough for a neurips publication.\n\n3. Presentation. The paper seems to be written in a rush. For example, the title of the paper is inconsistent with the title on the webpage. The major algorithm design trick is the ellipsoidal gradient estimator, but the paper didn't explain this estimator or provide intuition. The main theorems are merely stated without any explanation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to read and review our work. We believe that your concerns are valuable for us to improve our presentation. We hope that the following responses can explain our novelty and contribution better and boost your confidence in our work. \n\nWeakness comments: \n\n**7wFb**: Simulation. The paper lacks simulation results for verification of the improved technical bound. Though the supplementary material provides some figures, the simulation setups are not clearly explained. See more questions in the next box.\n**Response**: We are unsure about the intended meaning of the first comment – the simulation section shows that our algorithm improves on previous methods in practice, validating the theoretical findings. We are happy to substantially clarify the simulation setup (and the reasons behind it) in response to your concerns, and shift a summary to the main paper – thank you for pointing this out.\n\n**7wFb**: Novelty. I have mixed feelings about the novelty of this paper. On the one hand, the paper successfully improves the regret bound order to $\\sqrt{T}$. On the other hand, the majority of the algorithm design is based on the classic disturbance-action policy and OCO-M formulation, so I am not sure if the algorithm design is novel enough for a neurips publication.\n**Response**: It is true that all recent nonstochastic control results are based on the paradigm of OCO-M, and DAC policies, so from a high level they look similar. The technical novelty of our paper is in a novel exploration scheme enabled by a new gradient estimator (from Suggala et al. (2021)). We show that this allows the optimal regret bound of $\\sqrt{T}$, even in the generality of unknown systems with partially observed states. This improves the best known rate for this fundamental problem, and in fact is tight up to logarithmic factors. \n\n**7wFb**: Presentation. The paper seems to be written in a rush. For example, the title of the paper is inconsistent with the title on the webpage. The major algorithm design trick is the ellipsoidal gradient estimator, but the paper didn't explain this estimator or provide intuition. The main theorems are merely stated without any explanation.\n**Response**: For the title, see Q1 below. For the other points, we thank the valuable feedback and will amend the paper with intuition and nontechnical explanation for the algorithm components and the proof techniques/implications.\n\nResponses to questions:\n\n**Q1**: Thank you for pointing this out. We found the title “Optimal Rates for Bandit Nonstochastic Control” more descriptive than our original proposed title after the abstract submission deadline, and felt unsure whether we can change the title then. The title in the paper is our final decision. We will make sure the title is consistent moving forward. \n\n**Q2**: Semi-adversarial disturbances were chosen as they reflect a variety of real-world settings, in which adversarial agents exercise control only up to system noise (thermal/electrical/kinematic/etc.). Notably, said noise may be of small magnitude, and may in many cases be added manually via control, so it poses no meaningful barrier to application in the vast majority of practical settings. It is, however, a slightly weaker setting than the fully adversarial one – our algorithm’s performance does depend on noise magnitude, and is not shown to succeed in cases with absolutely zero non-adversarial noise. We simulate with various types of non-adversarial noise to comply with the established setting of Gradu et al. Testing with respect to adversarial noise is highly problem-specific, as determining worst-case noise inputs is an extremely challenging problem in general.\n\n**Q3**: Our contribution is for both known and unknown dynamical systems. This is discussed in detail in Section 4: Theorem 4.1 establishes the regret guarantee for LQR with known systems, and Theorem 4.2 establishes the regret guarantee with unknown systems. For the unknown system case, we run Algorithm 3 to estimate the system first and then run our controller algorithm. We showed that the system estimation error propagates through the controller algorithm in a way that the optimal rate is still preserved. \n\n**Q4**: The y-axis represents average error at the given timestep. Could you please clarify what you are referring to in “Why is it 0.1, 0.01”?  Are you asking about logarithmic vs. linear scale? The loss functions are quadratic, and convergence is of polynomial order, so there is no reason to choose a logarithmic scale. Broadly speaking, we intend to provide more methodological exposition for the experiments – see other comments.\n\n**Q5**: It is indeed possible to plot the figures with a smaller horizon; however, we chose not to do so for several reasons. First, part of the goal of the plots is to demonstrate the asymptotic difference between the convergence rate/convergence minimum of Gradu et al.’s work and our own, which is substantially more visible at higher timescales. Second, the low-time experimental setup of Gradu et al. required a large multiplier on learning rate in order to achieve practically-oriented results in settings without large-scale adversarial noise at low timescales (since the loss functions are prone to converge quickly here, artificially inflating the learning rate is advantageous). The advantage that this multiplier gives decreases at large timescales, reducing the gap between the theoretical and altered-practical performance and providing a more accurate representation.\n\n\nThank you again for your various comments, criticisms, and suggestions for improvement. We hope that our proposed changes address them to your satisfaction – please consider raising your review score if so, and let us know if you have further questions or concerns.\n"}, {"review_id": "fn6r41AxxR", "reviewer": "Reviewer_2R7J", "summary": "This paper presents an algorithm to perform control in the semi-adversarial setting. After presenting the gap in the literature they want to fill, the authors present an algorithm that shows optimal regret ($O(\\sqrt{T})$) for this setting, considerably improving the previous bound known from the literature ($O(T^{3/4})$, Gradu et al., 2020). The authors perform an experimental campaign to validate their solution in the appendix.", "questions": "No questions.", "limitations": "No limitations.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The gap in the literature that the authors fill is clearly stated.\n\n- The setting and the assumptions are clearly presented.\n\n- The work, in general, is clearly presented (except for the algorithms, see Weaknesses).\n\n- The authors face both the cases of known and unknown systems.\n\n- The bounds presented are tight, given the lower bounds known from the literature.\n\n", "weaknesses": "- Algorithms 1, 2, and 3 should be explained instead of only presenting the pseudo-code. Some step may not be clear to all the readers only from the pseudo-code.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and feedback. Here is the response to your concern, with which we hope to further boost your confidence in our work:\n\n**2R7J**: Algorithms 1, 2, and 3 should be explained instead of only presenting the pseudo-code. Some steps may not be clear to all the readers only from the pseudo-code.\n**Response**: Thank you for pointing out this issue. We agree that the current presentation of the algorithms lacks an intuitive explanation and therefore limits the presentation clarity to a broader audience. We will add more explanations before introducing the pseudocode for every algorithm. \n"}, {"review_id": "Y9OFaiAvq9", "reviewer": "Reviewer_iuZo", "summary": "This paper studies LQG with semi-adversarial perturbations and time varying adversarial bandit loss functions.\nThe best known bound for such problems has a T^{3/4} time horizon dependence.\nThey provide an algorithm for LQR/LQG problems that attains $\\tilde{\\mathcal{O}}(\\sqrt{T})$ regret. \nTheir algorithm goes through even if the underlying system dynamics are unknown. \nAdditionally, their method also provides a new scheme for bandit convex optimization with memory.\n", "questions": "\n## Major comments:\n\n1) Can you elaborate more on the DRC policy class? To me it seems like you are concentrating on the causal (non-anticipatory) policies that are linear. Is it possible to show that a linear policy will be optimal for your setting because you are concentrating on the quadratic cost function? I believe that would require to show that the estimation of the state given observations would be linear in observations as in the classical LQG setting. \n\n2) I think nature's y seems like the purified the purified output control method in [R1]. Is that true? If yes can you please provide the relevant reference there? \n\n3) I find it very confusing that $y$ suddenly becomes a decision variable in Section 3.1 while it represents the observations of the state in the previous chapter and also in the subsequent section. This is truly confusing if I did not miss something. Following that I do not understand why $u$ is the noise in Assumption 3.3. \n\n\n4) What does $A_t$ represent in Algorithm 1? It seems completely irrelevant to the state transition matrix $A$ to me. Why do you choose the same letter? I find this very confusing. \n\n\n5) Where is the proof of Theorem 3.7? \n\n6) Line 529, I do not understand why $x_1, \\ldots, x_{2\\bar H +1} = argmin_{x \\in \\mathcal K} R(x)$ because it seems to me $x_1, \\ldots x_{H } = argmin_{x \\in \\mathcal K} R(x)$ but $x_{H+1}, \\ldots, x_{2 \\bar H + 1}  = argmin_{x \\in \\mathcal K} \\sum_{s= H}^t \\frac{\\sigma}{2} \\| x - x_{s- \\bar H}\\|^2) + \\eta^{-1} R(x)$. What am I missing here?\n\n7) Can you comment on if it is possible to remove the logarithmic term even from the regret or is it fundamentally not possible? (in Theorem 4.1 and Theorem 4.2)\n\n8) Why this rate is optimal? $\\sqrt{T}$ regret rate would be optimal as it is tight. By not $\\tilde{\\mathcal{O}}(\\sqrt(T))$. Can you please elaborate on that. \n\n## Minor comments:\n\n1) Typo in Page 4, Line 136: Time step instead of timestep.\n\n2) Please provide references for every claim that is mentioned in the paper without a proof. For example, in Page 4, Line 145, I suggest to provide examples of the papers that make us of the system's counterfactual signal. Same goes for Page 5, Line 159. \nAnother example is in Page 5, Line 181. The sentence there reads \"These conditions are relatively standard for bandit convex optimization algorithms, and are needed for the ..\". Please provide references for the bandit convex optimization algorithms that make these standard assumptions.\nPlease provide references for Line 215 (which previous works). \n\n3) Typo in Page 5, Line 157, \"that that\" should be \"that\".\n\n4) Line 444: \"empirical\" instead of \"emprical\"\n5) $W_t$ is not introduced in Line 235. \n6) Line 197, what is $\\Theta(H)$?\n7) It's mandatory to include the code for the experiment section in Neurlps submissions. Your code seems to be missing. Please rectify this immediately by sharing your code via an anonymous GitHub repository\n8) I'm having trouble understanding the meaning of the paragraph found on Line 196. Could you please clarify? \n9) In Line 510, which spiking? I do not understand the paragraph in Line 509. \n10) Why there is a divergence problem in the third plot of Figure 1? \n11) I must express difficulty in comprehending the conclusion about the initial phase of EBPC possessing lower stability. The relationship with Figure 1 is unclear and requires further explanation. I am also perplexed by the decision to choose an extraordinarily high starting multiplier on ε - a justification is needed for this choice.\nIt's important to stress that the writing in the experiment section does not meet the expected standards for rigor. As it stands, the line of reasoning is opaque, and the process by which the conclusions were reached is indiscernible.\nFurther compounding the issue, the code has not been made available for examination. This, as previously emphasised, hampers any possibility of a comprehensive understanding or verification of the results. I strongly recommend addressing these concerns in a revised submission.\n12) Line 504- Why this is a barely-stable system?\n13) Line 261, if the key point is to use ellipsoidal gradient estimator, where is its definition?\n14) In algorithm 1, $S^{n-1}$ is not defined. \n15) Line 810- There is a typo. \n\n\nReferences: \n\n[R1] A. Ben-Tal, S. Boyd, and A. Nemirovski, Control of Uncertainty-Affected Discrete Time Linear Systems via Convex Programming. Technical Report Minerva Optimization Center, Technion, Haifa,\nIsrael, 2005 [Online]. Available: http://www.stanford.edu/~boyd/papers/pur_out_control.html\n", "limitations": "Yes. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "This paper addresses an important problem in the field of control and online learning. ", "weaknesses": "\nI must express my concerns about its presentation and structure. The writing is not as clear as it needs to be, making it quite challenging to follow the paper. \nThe argument seems to lack the rigorousness and the self-containment.\n\nA crucial element that seems to be missing is detailed explanations for the conclusions drawn. Without these, it becomes arduous to justify the results. Enhancing the clarity and providing in-depth explanations of the methodologies and results will significantly improve the comprehension and overall impact of the study. I list my comments, questions and suggestions below. \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your review and valuable feedback. Here are our responses to the points you raised:\n\nWeaknesses:\n\n**iuZo**: I must express my concerns about its presentation and structure. The writing is not as clear as it needs to be, making it quite challenging to follow the paper. The argument seems to lack the rigorousness and the self-containment.\nA crucial element that seems to be missing is detailed explanations for the conclusions drawn. Without these, it becomes arduous to justify the results. Enhancing the clarity and providing in-depth explanations of the methodologies and results will significantly improve the comprehension and overall impact of the study. I list my comments, questions and suggestions below.\n\n**Response**: Thank you for raising your concerns. In general, we agree that the presentation of our paper can be improved. We will add in more explanations on the intuitions and main ideas of our algorithms and theorems. \n\nQuestions:\n\nMajor comments:\n\n1. The linear dynamic controller (LDC) policy class is optimal for this problem (proved by Kalman in the 1960s). The DRC policy class contains (or approximates up to arbitrary accuracy) the class of LDC (see Theorem 1 of “Improper Learning for Non-Stochastic Control” by Simchowitz et al. (2020)). We plan to clarify this context in the paper – thank you for pointing out the deficit.\n\n\n2. We were not aware of this – thank you for providing the link to the paper! To the best of our knowledge, our nature’s y is the same as the purified output defined by 1.2 in [R1]. We will add this reference (which is also called the “Youla reparametrization” from the 1970`s literature in control, see references in Simchowitz et al.). \n\n3. We wholeheartedly agree. This came about because we attempt to maintain consistency with the standard notations in both online bandit optimization and nonstochastic control, which causes overlapping use of letters. We differentiate the notations with bolded letters in the control setting and standard letters in the bandit settings, but we will change notations to make the presentation more clear, and avoid overloading. \n\n4. Thank you for pointing this out. $A_t$ is not related to the state transition matrix (we are in the time-invariant setting, therefore $A$ is the state transition matrix) and is constructed in line 12 of Algorithm 1. We will change this for clarity.\n\n5. The proof of Theorem 3.7 is in Appendix C.\n\n6. You are right about $x_{H+1},\\dots,x_{2\\bar{H}+1}=argmin_{x\\in\\mathcal{K}}\\sum_{s=H}^t \\frac{\\sigma}{2}|x-x_{s-\\bar{H}}|^2+\\eta^{-1}R(x)$. However, the equality $x_1,\\dots,x_{2\\bar{H}+1}=argmin_{x\\in\\mathcal{K}}R(x)$ still holds because the first $H$ $x$’s are the same. In particular, let us denote $x^*=argmin_{x\\in\\mathcal{K}}R(x)$, then we have for each $s=H+1,\\dots,2\\bar{H}+1$, $x_s=argmin_{x\\in\\mathcal{K}}\\sum_{s=H}^t \\frac{\\sigma}{2}|x-x^*|^2+\\eta^{-1}R(x)=x^*$. \n\n7. No, it is not possible for any OCO-M based control algorithm. \n\n8. You are correct; by “tight” we mean up to logarithmic terms in T, as with most ONC literature. We will make sure to clarify. \n\nResponse to minor comments: \n\nFor comments 1, 2, 3, 4, 15, thank you for pointing these issues out, and we will change according to your suggestions. \n\n5: $W_t$ is the same as the $W_t$ in line 233.\n\n6: $\\Theta(\\cdot)$ denotes asymptotic equivalence, as defined in line 482. \n\n7: Thank you for asking. The link to the anonymous GitHub will be sent to the AC as instructed by the guidelines. Updated code for the modified experiments will follow with the modifications.\n\n8: Previous work by Simchowitz et al. (2020) showed that the DRC policy class is a very rich policy class. See discussion to reviewer iuZo’s comment 1.\n\n9: The spiking is not reflected visibly in the graphs (due to averaging across many runs). We will attempt to clarify this paragraph in the revision: it deals with a) the empirically motivated learning rate modification by Gradu et al. (see point 11) and b) adverse behavior observed in their code when the modification is made.\n\n10: There is not a divergence problem: as we use DRC, the error in a generic system will reflect noise magnitude, which is increasing under random-walk noise. Note the essentially identical behavior in figure (1f) of Gradu et al.\n\n11: The lower stability is reflected by a substantially slower decline to the minimum than the Gradu et al. algorithm under the empirically optimized multiplier – we will attempt to clarify this in the plots. The addition of the starting multiplier is not a novel addition for empirical tests, but was present in the tests of Gradu et al. (and is visible in their source) – we apologize if this was unclear. We intend to clarify the discussion of this choice (which was made by Gradu et al. to demonstrate empirically meaningful convergence results over a reasonable time threshold in the non-adversarial noise cases tested in that paper and here), as well as clarifying the presentation of the evidence for the conclusions drawn. For code, see point 7. \n\n12: The system is barely stable because its eigenvalues have absolute values near 1. A system is stable in the strong sense if and only if its eigenvalues all have absolute values <1.\n\n13: It is the $g_t$ defined in Algorithm 1. We will make sure we clarify that when introducing Algorithm 1. \n\n14: Thank you for pointing this out. $S^{n-1}$ denotes the unit sphere in $\\mathbb{R}^{n}$. We will add this into our notation section starting in line 119. \n\nThank you again for your various comments, criticisms, and suggestions for improvement. We hope that our proposed changes address them to your satisfaction – please let us know if you have further questions or concerns."}, {"review_id": "I9sJ2ikUs8", "reviewer": "Reviewer_FiLK", "summary": "The authors present an algorithm fro the LQG problem, in which a linear system has to be controlled in the presence of semi-adversarial perturbations in order to minimise an adversarially-chosen cost, with the controller only having access to a projection of the real dynamics onto a lower-dimensionality subspace. The authors show that their proposed method achieves optimal regret in time horizon of $O(\\sqrt{T})$.", "questions": "My understanding of the paper is too limited to provide any meaningful suggestions for improvement.", "limitations": "The paper is extremely theoretical and can only be understood by a very specialised audience. The relevance of the author's solution for the presented problem (or even of the problem itself) to more mainstream AI research, if any, is not at all discussed.\n\nEdit: In their rebuttal, the authors challenged my assessment of their work's limitations by pointing out a connection between nonstochastic control and hyperparameter tuning in large-scale optimization, which was remarked in “A Nonstochastic Control Approach to Optimization” by Chen & Hazan (2023). While the connection is definitely present and fascinating, I still felt that it was not enough of an established research track for me to change my assessment. I therefore kept my initial score.", "rating": 5, "confidence": 1, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper's introduction of the problem is quite readable to a non-specialist, though specialist knowledge is required to understand most of the details and the theorem proof.", "weaknesses": "The paper is extremely theoretical and deals with a very specialised problem. This problem has connections with more mainstream AI problems (Optimal Control and Reinforcement Learning are closely related), and the paper does present it in a way that makes it understandable to a non-specialist reader. Still, the paper does not present any task-oriented AI-based framework involving the training of a Neural Net. While this might not be enough to disqualify the paper from publication at NeurIPS, it does severely restrict the number of potential readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to read and review our paper. We tried to address your concerns in the following paragraph:\n\nWeakness:\n\n**FiLK**: The paper is extremely theoretical and deals with a very specialised problem. This problem has connections with more mainstream AI problems (Optimal Control and Reinforcement Learning are closely related), and the paper does present it in a way that makes it understandable to a non-specialist reader. Still, the paper does not present any task-oriented AI-based framework involving the training of a Neural Net. While this might not be enough to disqualify the paper from publication at NeurIPS, it does severely restrict the number of potential readers.\n\n**Response**: Thank you for your feedback. We agree that this is indeed a theoretical work, but the recent emerging line of work, as cited in our paper, in online nonstochastic control makes NeurIPS an appropriate venue to submit our theoretical work. Therefore, we respectfully disagree with the reviewer’s comment about the lack of relevance of our work to “more mainstream AI research”. \n\nThere is a direct connection between online control and training deep neural networks, as per the recent work “A Nonstochastic Control Approach to Optimization” by Chen & Hazan (2023), which establishes a connection between nonstochastic control and hyperparameter tuning in large-scale optimization.This establishes a connection between control, RL and optimization for deep learning, which renders the study of online control relevant to mainstream AI research. We will mention this in our paper, but feel that direct implementation of this recent advancement is out of scope (as it is the topic of another (almost) concurrent paper).\n\nIn general, we want to emphasize that (1) this is a work, although theoretical, on the topic that has become increasingly popular in the online learning community in the recent years, and (2) our work has the potential to be applied to DNN related research, but since it is out of the scope of our current paper, we believe that our current experiments are sufficient for supporting the theory. If this changes your perception of our work, please consider raising your score. Thank you!\n"}]

Author rebuttal:

Meta-review: The paper received a uniformly positive evaluation from the reviewers. They generally appreciate the paper's theoretical contribution and agree that the paper addresses a significant problem in the field of control and online learning, by achieving an optimal regret bound in the considered setting. There were also some concerns and suggestions, which should be addressed by the authors in the final version of the manuscript.
Decision: Accept (poster)