Tight Rates for Bandit Control Beyond Quadratics
Authors: Y. Jennifer Sun
Zhou Lu
Venue: NeurIPS 2024 poster (2024)
Keywords: Bandit Problem
Online Control
Primary area: online_learning

Abstract: Unlike classical control theory, such as Linear Quadratic Control (LQC), real-world control problems are highly complex. These problems often involve adversarial perturbations, bandit feedback models, and non-quadratic, adversarially chosen cost functions. A fundamental yet unresolved question is whether optimal regret can be achieved for these general control problems. The standard approach to addressing this problem involves a reduction to bandit convex optimization with memory. In the bandit setting, constructing a gradient estimator with low variance is challenging due to the memory structure and non-quadratic loss functions.

In this paper, we provide an affirmative answer to this question. Our main contribution is an algorithm that achieves an $\tilde{O}(\sqrt{T})$ optimal regret for bandit non-stochastic control with strongly-convex and smooth cost functions in the presence of adversarial perturbations, improving the previously known $\tilde{O}(T^{2/3})$ regret bound from \citep{cassel2020bandit}. Our algorithm overcomes the memory issue by reducing the problem to Bandit Convex Optimization (BCO) without memory and addresses general strongly-convex costs using recent advancements in BCO from \citep{suggala2024second}. Along the way, we develop an improved algorithm for BCO with memory, which may be of independent interest.

Tight Rates for Bandit Control Beyond Quadratics
Y. Jennifer Sun Princeton University ys7849@princeton edu
Zhou Lu Princeton University
choul@princeton edu
Abstract
Unlike classical control theory, such as Linear Quadratic Control (LQQ)), real-world control problems are highly complex. These problems often involve adversarial perturbations, bandit feedback models, and non-quadratic, adversarially chosen cost functions. A fundamental yet unresolved question is whether optimal regret can be achieved for these general control problems. The standard approach to addressing this problem involves reduction bandit convex optimization with memory. In the bandit setting, constructing gradient estimator with low variance is challenging due the memory structure and non-quadratic loss functions.
In this paper, we provide an affirmative answer to this question. Our main con- tribution an algorithm that achieves an Ö(VT) optimal regret for bandit non- stochastic control with strongly-convex and smooth cost functions in the presence of adversarial perturbations, improving the previously known (T7233) regret bound from (Cassel and Koren 2020). Our algorithm overcomes the memory issue by reducing the problem to Bandit Convex Optimization (BCO) without memory and addresses general strongly-conve
costs using recent advancements in BCO from (Suggala et al., 2024). Along the way, develop improved algorithm for BCO with memory, which may be of independent interest.
1 Introduction
Optimal control lies the heart of engineering and operations research, with applications ranging from launching spacecraft to stabilizing economies. The theory of optimal control is well-established field with rich history, dating back to 1868 when James Clerk Maxwell analyzed governors, and flourishing in the mid-20th century with the development of dynamic programming by (Bellman 1954) and the Kalman filter by (Kalman 1960).
Classic optimal control theory studies the problem where a controller interacts with an environment, according a (partially observable) linear time-invariant (LTI) dynamical system:
F++1 Ax; + Bu, + Wt: Yt = Cra + Ct,
where A, B, C' are the dynamics governing the system, Zt, Me, Vt, We, ea represent the system state, control input, observation, perturbation, and observation noise time l, respectively. At each time I, the controller observes y/ and chooses control ue, incurring cost Ci (Jtt, ux)) based on the current observation and control. The system then evolves according to Eq. to reach the next state Tt+1-
The theory of optimal control (c.g., LQC) typically relies on three key assumptions on the setting: the perturbation W; is stochastic, the cost function o is quadratic and known in advance, and the function e is observable to the controller. The linear-quadrate regulator (LQR) (Kalman et al. 1960) provides a closed-form optimal solution under these conditions, representing a pinnacle of classical control theory.
However, these assumptions are often idealistic for practical scenarios. In real-world control problems, the perturbations can be adversarial, the feedback model can be bandit, and the cost
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

function can be non non- -uaaduurr..ic. This is evident in applications such as autonomous vehicle navigation, advertisement placement, and traffic signal control. This discrepancy between theory and practice raises fundamental question for developing more general control theory:
Can we devise algorithms with provable guarantees for LTI control problems with adversarial perturbations, bandit feedback models, and hon-quadratic cost?
Recent research in online non-stochastic control (see (Hazan and Singh 2022) for a survey) aims to address this broader goal by relaxing two of the standard assumptions: (1) the cost et can be time-varying, non-quadratic convex functions unknown to the controller, (2) the perturbation w/ and the observation noise e, can be adversarially chosen.
The natural performance metric in this context is regret, defined as the excess cost incurred by the controller compared to the best control policy in a benchmark policy class II:
(egrett((ootroollll
cul u.) - -iin =C
c (v 27),
(2)
where (ye, u4) is the observation-contro) pair reached by executing the controller at time and (yā uF) is the observation-control pair under the policy x at time t. An optimal Ö ((T) regret was obtained by (Agarwal et al. 2019a) with the Gradient Perturbation Controller (GPC) algorithm.
Several works in online control have made further progress towards the general question. (Cassel and Koren 2020] Sun et al. 2024) obtained optimal regret under bandit feedback for strongly convex and smooth cost when the perturbation wy and observation noise e semi-adversarial (i.e. they contain an additive stochastic component that admits covariance matrices with least singular value bounded from below). (Cassel and Koren 2020) also showed a sub-optimal (T233) regret bound for fully adversarial perturbations. More recently, the advancement of (Suggala et al. 2024) showed for the first time that an optimal regret of Ö(vT) is achievable for strongly convex and smooth quadratic costs in the presence of adversarial perturbations and observation noises.
Still, no previous work has simultaneously addressed all three challenges with an optimal regret guarantee, which was left as an open problem by (Suggala et al. 2024). The main challenge lies in how to construct a low-variance gradient estimator under bandit feedback, with the memory structure and non-quadratic cost. Due to the 2/33/3 regret lower bound for general BCO with memory by (Suggala al. 2024). exploiting the special affine memory structure in control problems crucial to achieving optimal regret for general convex cost.
In this work, we provide the first affirmative answer to this general question by devising an algorithm that handles all three challenges with an optimal Ö(VT) regret bound. Our approach involves reducing the problem to no-memory BCO, which circumvents the high-dimensionall estimator issue for non-quadratic costs. We then leverage a special curvature structure of the loss function induced by general strongly convex and smooth costs to obtain the optimal regret guarantee. Our result serves as a preliminary step toward fully solving the general control problem.
1.1 Technical Overview
Several previous works have addressed the bandit non-stochastic control problem, but none achieved optimal regret across all three generalities due to the following technical challenges:
1.
The necessity of curvature: The first work tackling the bandit non-stochastic control problem was (Cassel and Koren 2020). which achieved an ÕTT2/3) regret bound for smooth convex cost. However, such sub-optimality is arguably inevitable due to the 2/33 regret lower bound for BCO-M with smooth convex[ccos (Suggala et al., 2024):: all existing results on bandit non-stochastic control relies on reduction to BCO-M! Indeed, the algorithm of (Cassel and Koren 2020) is based on online gradient descent (DGD) and ignores the geometry of cost. This is the reason why we introduce the assumption on strong convexity.
2. Strong convexity is not enough: Does strong convexity alone become an easy remedy to the control problem? Unfortunately, even if we assume the cost functions e, in the control
In fact, the lower bound proved in (Suggala et al. 2024 even holds for quadratic loss functions.

---

Regret
Perturbation
Feedback
Loss type
Agarwal et al.
2019a)
O(VT)
adversarial
full
strongly-convex
Agarwal et al.
2019b
O 2 T)
stochastic
full
convex
Cassel and Koren
2020
Ö(T2/3)
adversarial
bandit
convex smooth
Cassel and Koren
2020
Ö(VT)
stochastic
bandit
strongly-convex smooth
[Snn et al. 2024
Ö(VT)
semi-adv
bandit
str-conv smooth quadratic
(Suggala et al.
2024)
Ö(VT)
adversarial
bandit
str-conv smooth quadratic
This work
Õ(VT)
adversarial
bandit
strongly-convex smooth
Table I: Comparison of results. This work is the first to address all three generalities with Ö(v optimal regret: (Agarwal et al.] (009a)) addressed perturbation loss, (Cassel and Koren (2200 addressed feedback + loss, (Suggala et al. 2024) addressed perturbation feedback. (Cassel and
Koren 2020 also obtained a sub-optimal (T2//5 regret for perturbation + feedback + loss.
problem are strongly-convex, the induced loss functions in the BCO-M problem necessarily strongly-convex! was observed by (Suggala et al. 2024) that the induced loss functions satisfy property called s-convexity, allowing for low-variance estimation of Hessian matrices, which is a key ingredient in Newton- second-orde update to exploit the curvature.
3. Going beyond quadratic: However, finding a low-biased first-order estimation of gradients remains a challenge for BCO-M, because the nice property on the unit sphere domain Sa-1 {I E R ||||| 1} of the exploration term is not preserved under Cartesian product: S x S & Saxd-1- To handle this issue. (Suggala et al., 2024) relies on the quadratic cost assumption which admits unbiased estimator of the divergence of the induced loss function. It's unclear how to handle general x-convex smooth cost in BCO-M.
Similar to its full-information counterpart, reduce the bandit non-stochastic control problem bandit convex optimization with memory (BCO-M). To overcome these challenges, we further reduce the BCO-M problem to no-memory BCO problem following (Cassel and Koren 2020), to avoid the issue on the Cartesian product of S This allows for the use of a Newton- based BCO-M algorithm similar (Suggala et al., 2024). which can handle general к-convex smooth cost because the exploration domain is now Sz-1. Besides this new approach, our method also includes novel algorithmic components and analysis.
1.2 Related Work
Optimal control theory (Bellman 1954 concerns finding control for dynamical system such that some objective function is optimized. The basic form of optimal control is linear quadratic control (Kalman 1960). in which quadratic function is minimized in a linear first-order dynamical system with stochastic noise, whose solution is given by LQR.
Online non-stochastic control generalizes classic optimal control by considering adversarial pertur- bation and cost, with the metric of regret to compete with the best fixed policy in some benchmark class. The first work (Agarwal et al. 2019a) obtained an optimal regret bound for general convex cost by reduction to online convex optimization with memory (Anava et al. 2015), under stability assumptions the system. For the line of works the full information feedback setting, (Hazan and Singh 2022) for a survey.
Online non sto-hstcc control with bandit feedback were first considered by (Cassel and Koren 2020 Gradu et al. 2020). Under a smoothness assumption on cost functions, the two works showed an 2733)3 and (T33/4 regret bound respectively. When the cost functions are additionally strongly- convex quadratics, (Sun al. 2024) obtained an Ö(VT) regret, under aemi-adversarial perturbations. (Yan et al. 2024) showed sublineat regret for cost functions with heterogeneous curvatures under the
3

---

same semi semi-adversarial perturbations. This restriction on perturbation was later removed by (Suggala al. 2024) which achieved the same regret for adversarial perturbations.
Recent advancements on BCO (Lattimore and Cyörgy 2023 Suggala et al. 2021 Lattimore 2024)
considered Newton step updates to achieve improved regret bounds. In particular, (Suggala et al.
2024) also showed an (2(T2/33 lower bound for bandit quadratic optimization with memory (BQO-M)
without strong convexity. When making use of the affine memory structure, (Suggala et al. 2024) obtained an ((VT) regret bound for BQO-M.
Preliminary
2.1 Online non-stochastic control with bandit feedback
Consider the linear dynamical system in Eq. (T). At time E N, the learner receives observation y and outputs control Kg to which the learner receives scalar instantaneous cost (B u.) depending on both the current observation and the control, and no other information about or is available. The perturbation w, and observation noise e can be adversarially chosen. The learner's goal is to minimize regret over a fixed time horizon T E N defined in Eq.
Throughout this paper, all cost functions we consider are assumed to be twice continuously differen- tiable. Consistent with past literature (Sun al. 2024 (Suggala et al. 2024), we make the following assumptions on the cost functions.
Assumption 1 (Cost curvature and regularity). Let dy. du E N denote the dimensions of observation and control, respectively. The control cost function et Rd x IR. + R.+ satisfies that
1. (Curvature) C is at-stoongly convex and S.-shhoth over some compact set y x U c R4 x 8.
I for some Oe. 3e O, i.e., Vc, (x22) (x1 x22)
2 || 22113 2 c((21) ce(22) 2
(x1 (x2( [
x2) + 1| x21l2 for any x1, 22
U.
2. (Gradient bounds) There exists some Ge > 0 such that the gradients satisfy Ve, (3). u)lla 5 Gell for any y E V. u EU.
We also make stability assumption on the LDS in Eq. ( as well as norm bound on the perturbation and noise. These assumptions are standard in literature (e.g. (Hazan and Singh 2022) and necessary for deriving meaningful regret guarantees.
Assumption 2 (Strong stabilizability and bounded dynamics). (A, B, C) that governs the LDS in Eq. (I) satisfies that max ||p/ [|B| [[C']lop] S Kays for some positive constant Kays- There exists
K E Rdd, xdy s.t. A + BKC HL 1LL-1p1 H for some H > 0 and max[[] 12, || | [ S K, ||L||2 < 1 Y for some > 0, 0 < < 1. Such K is called a (K, -)-stabllizing linear controller for the LDS.
Assumption 3 (Bounded perturbation and noise). The perturbation and observation noise sequences sctisfy the norm bound max4e(T) [max{]] [[ []]]]12]] S Ruc,e for some Rug,e > O.
We assume the adversary chooses the cost functions and noise sequences in an oblivious way, i.e. they are chosen independently of the learner's 's decisions.
A Assumption 4 (Oblivious adversary). The sequence of cost functions {ct)E=1 and the noise sequences { [w Yz=1, (e are chosen by an oblivious adversary and does not depend on the control played by the learner.
For partially observable systems, the standard comparator class in literature (Simchowitz et al. 2020 is the class of Disturbance Response Controllers (DRC). Essentially, this class considers controllers that choose linear combinations of past signals and observations. The signals are simply the would-be observations had stabilizing controller K been used from the beginning of the time. Formally, the class of DRC is given by the following definition:
Definition 1 (DRC). (1) A disturbance response controller (DRC) is policy TM parametrized by m E N matrices M- = M10:m-1) in R. xdy such that the control at time t according to TM is
m
(TM Kyt+ +
Σ
Mi (K))
1=

---

where K is (k, 7) -stabiiiig linear controller, and y is the would-be be observation had the linear policy K been carried out from the beginning the time.
(2) A DRC policy class M(m, RM). parameterized by m E N. RM > 0. is the set of all DRC controller of length m and obeys the norm bound M op := m- |Mb llop S R.M-
DRC policy always produces controls that ensure the system remains state bounded, the DRC class expressive enough to approximate the class of linear policies of past observations (see Theorem in (Simchowitz et al. 2020)).
2.2 Bandit convex optimization with memory (BCO-M)
We start with the general protocol of bandit convex optimization with memory (BCO-M), In the (improper) BCO-M problem, at each time t, the learner is asked to output a decision 2 E Rd to which scalar loss fi (= depending
the learner's most recent m E N decisions is revealed. Given a convex compact set IC C IRd as the domain of comparators, the regret is measured on the best single point E K. over time horizon E N, formally given by
Regret
CC max E SEÑ
Σ fe(zi-mt1a) fe(z,..., 1=
In non-stochastic control, the learner's past decisions affect future states through affine structure, therefore we are interested in BCO-M problems with such structure. This leads to the following structural assumption on the induced loss function with memory. We will show in Lemma 9 that the bandit control problems with the standard regularity conditions satisfy Assumption
Assumption (Affine memory structure). time t N, the loss function with memory length m takes the form of fe (R")" R2 given by the following structure
Se(ze-mt1a)) =
B +
Σ i=0
Giily, 1z=
(3)
with parameters B₁ E R², Yi-s E Raxd and G = G(0:m-1) sequence of m matrices where Gli E Raxp for some n. E N. G G. E TRexd There exists some RH > O such that max |G., (1/,:,1//l2l11 | < Rn- In addition, we assume that G satisfies positive convolution invertibiliy-modull ie. k(G) = inf [|a,13 1=11 Enza Ex=o Gl Gl) = 1111.. We assume that the learner receives H, every step after they incurred the loss.
F We denote G. = En' Giiy, E Raxd, and H,
We make two standard curvature and regularity assumptions each of the instantaneous loss fi, that fe is strongly-convex and smooth, with its subgradient norm bounded by some constants, following the previous work of [Suggala et al. (2024).
Assumption (Curvature). Consider a loss function fe satisfying Assumption 5 and the set
m-1
2,
B
Σ
Glly 2 2t-m+1,.... Rt E K. Rd c CR",
where B., G.
are the parameters, and 4, R + R4 is the function associated with f. in Assumption 5 We assume that E, is o oo--toonglyy-one and By-smooth, i.e. a (e((2) 3 By over Z with < a <a 1 By here
mt 1:t G.
Assumption (Regularity). For d E N, denote B= := fa We assume that at time the with-memory loss function Jt (Rdym R2 with memory parameter m E N obeys the following gradient bounds over ICC + IB := for +
Rd ||^||| S 1) as the unit ball in TR...
K. E Ba):
[V 2m) GG; Vz Vzi,..., 2m K. Bd-
Additionally, we assume that has Euclidean diameter D 0.
2 Here we could write Gily,-, with single parameter, but current form matches that of control. Any strongly convex function is also min(1, a) strongly convex and similar for 8.
5

---

We consider an oblivious adversary model, given by Assumption 8
Assumption 8 (Oblivious adversary). For a BCO-M instance, we assume that the adversary is oblivious. In particular, let z, denote the algorithm's 's decision at time then the loss function fo chosen by the adversary does not depend on 21:b-
In the definition of regret in BCO-M, we compare the cumulative loss any algorithm with the best fixed comparator E K., evaluated on the induced unary form fe 2) of the loss ft. Formally, we have the following definition
Definition (Induced unary form). Vt E N, let ft Rd + R+ denote the induced unary form of the loss ft. given by fi(z) f((z...., 2). Then, for ft satisfying Assumption ft admits the structure f<(z) & B. + Di=D ,
We note that for ft satisfying Assumption 6 the induced unary form in Definition 2 satisfies a special curvature called iiconvexity introduced in (Suggala al. 2024). To avoid confusion with the notations with the bound on the dynamics (Assumption 2) we will call it Kg ko-convexity henceforth.
Definition 3 (No-convexity, (Suggala et al. 2024)). A function f Rdd + R is called Kg-convex a domain K. S TRd if and only if the following holds: f is convex and twice continuously differentiable. and moreover Ee, C > 0 and a PSD matrix 0 = H N 11 s.t. the Hessian of f at any E K. satisfies
cH = f())) CH,
S Kg-
The benefit that the loss function exhibits an affine memory dependence is that its induced unary form satisfies Ki convexity for some Ko 0, summarized the following observation.
Observation 4 (Ko (Ko-convyxity and gradient bound of the unary loss.). Consider (Idd + R. satisfying Assumption 5 Assumption 6 and Assumption 7
Then, the induced unary form ft Rd
R. in Definition satisfies the following two properties:
1. (Ro- coo-covvxitt) fo is Ru-convex with Ki By/ay, where H, G, G2 as in Assumption
H Hy: ojH, v Hy
Vz Rd
2. (Gradient bound)
[f((()) I Gyym, A2 Zz.
Proof of Observation 4 By our assumption on the affine structure of fr in Assumption 5 V2 E Rd
V2 (((()) = G. V B + G. co-convexity follows from the curvature assumption Assump-
tion 6 For any 21, 22 Rd we have that (ff())) (z2) S Gyll(a,,.. .21) (22,..",,2))
G m 21 22 2222.
2.3
Notations
For a positive semidefinite square matrix H 2 E _dxd define the norm - on Rd so that ||ul[ = He. We write a to denote the cost function of the control problem, and ft to denote the loss function for BCO with memory. For two sets A, B, A + B {a + b a E A, b E B). For set S, [S] denotes the cardinality of We use B,, S to denote the unit ball and unit sphere in Rd respectively. For n vectors Vi...., Un E Rdd we slightly abuse notation and shorthand Vin to denote the concatenated vector (ei,..., vn) E Rnd
3 Improved Bandit Convex Optimization with Memory
In this section, we introduce an improved algorithm for the bandit convex optimization with memory problem. Our algorithm incorporates the occasional update idea from (Cassel and Koren 2020) and the Newton-based update for Ko-convex functions from (Suggala et al. 2024), achieving an optimal Õ(VT) regret bound, improving the previously best known (T2333) result from (Cassel and Koren 2020 Besides the advancement on BCO-M, this result the key component of our main result in control. First, we define the BCO-M instance.

---

Definition 5 (BCO-M instance). Given E N, BCO-M instance is parametrized by O (K, m, (ff))tm,.en) where K с R is convex compact set; m is the memory length; fx Km + R2 measures the instantaneous loss at time f. Given any bandit online learning with memory algorithm A the regret of A on w.r.t. 2 E E is given by
Regret, 49, ((0)
Σ fe( fe(z),
where = = is the decision according to A at time t. We say BCO-M instance O is affine and (a,, 3, G. well-condiiioned if O satisfies Assumption Assumption with a a, By 8 Assumption with Gj = G. Dj D, and the adversary model satisfies Assumption
3.1 BCO-M algorithm
We describe Algorithm that runs bandit convex optimization for any BCO-M instance O [K,, m. { (tmmmee On a high level, our algorithm employs the occasional update idea from updated most once every steps, ensured by the b (line 8 Algorithm 1.. where by the Bernoulli random variable (partially) deciding whether the algorithm will make an update at the current time step. We write as the original ideal prediction, v as the random perturbation vector, and is the actual prediction the perturbed o) of the algorithm.
(Cassel and Koren 2020). The decisions
condition b, I_
Algorithm 1 Improved Bandit Convex Optimization with Affine Memory
Input: convex compact set C Rd step size y > 0, memory parameter m, curvature parameter a, time horizon T.
Om K. 90mm1 O,, Ån.m- 1, 1. 2: Sample ~ Sa-1 i..d. uniformly at random for t = ,,...,m.
1: Initialize: 01
3: Set 2, = 0, + A 1-1 2/ t m.
4: Draw b, Ber := I...,,
5: for = m...., T do
6: Play observe f( mia), receive H; = G. Gt.
7:
Draw by ~ Ber (1))
8:
if 6, 11 (1 b) then
9:
Let 8, = t.
10:
Update A, = A + 2 He,
11:
Create gradient estimate: gr- dft (2 (44-m+11444 E Rd.
Update Oc-1 = IIx A. Or n -
12:
Sample ut+1 S uniformly random, independent of previous steps.
14:
Set 21+1 0t+1 A, U1+1.
15:
T
+ t + 1
16:
else
17:
Set 0:+1 Oz, U2+1 = U2, Ze41 Zt, A. Ac-1, Gt = Āt-1-
18:
end if
19:
end for
Such occasional update essentially reduces the BCO-M problem a new no-memory BCO problem, whose equivalence will be shown later (see Appendix A.2). h. Consistent with the notation used in (Cassel and Koren 2020), we denote the following
S = {t E [T] 2++1 * x²}
(4)
to be the set of time steps where the algorithm updates its decision. We readily have |S|
<
T
Moreover, we have
fi f((z-m+1a)) fe(2(-m=1) f((ze), Vt S
(5)
7

---

since E S implies b updates with function value (z.).
6 = O. Thus, whenever Algorithm I Jupdates, it effectively
The occasional update alone only gives sub-optimal ((T2/3) regret as shown in (Cassel and Koren 2020). To achieve the optimal Ö(VTT) regret, we use nowton-based update exploit the yonvexiy of general strongly-convex smooth functions, recently introduced by (Suggala et al.
2024).
For this improvement we require the knowledge of a Hessian estimator H, as in Assumption Assumption 5 This doesn't hold in BCO in general, but we will show in the next section that the control problem indeed satisfies this assumption: thanks to ko-convexity, in the control problem Hy can be constructed from the knowledge of system, instead of knowledge of loss which would typically incur huge variance term.
The regret guarantee of Algorithm ils given by the following theorem.
Theorem 6 (BCO-M regret guarantee). Given an (a, B, G. Deee:) BCO-M instance
O {K, m, (ifemenmen) with poly (log T) and G. D O(1) (Definition 5 let (K,
((/vVT), m, az, T) be the impul Algorithm Algorithm
guarantees that
Algorithm 1 [(OO] s = (L
max E
ZER
where Ō()) hides all universal constants and logarithmic dependence in T.
Theorem is the first algorithm achieve the optimal Õ(vT) regret bound for the BCO-M problem with general smooth convex loss. Compared with the Ö(T2/3) bound from (Cassel and Koren 2020 our improvement exploits the new assumptions on the strong convexity of loss and the affine structure of memory. We notice that the Ó D(VT) regret bound of (Suggala et al. (024)) requires the additional quadratic loss assumption and uses the special structure of quadratic functions to construct low-biased gradient estimators for the unary form of losses. Algorithm [ and its guarantee in Theorem 6 thus improve upon both these previous results. The proof of Theorem 6 lengthy, therefore we leave to the appendix and include sketch here.
3.2 Proof Sketch
The theorem proven via reduction to a no-memory BCO algorithm with Newton-basee updates.
Step 1: regret of the base algorithm. We devise new BCO algorithm with two new ingredients different from standard algorithms. First, our algorithm adopts Newton-based updates which require estimating Hessians. In Assumption 5 we assume "free" access to Hessian estimator Hr, which holds in the control setting by utilizing the ro-convexity property.
Second, we incorporate new delay mechanism to decorrelate neighboring iterates such that o, is independent of recent perturbation vectors, which plays a crucial role in bounding the expectation of moving cost. Our base BCO algorithm is then shown to have an Õ(VT) regret bound (see Lemma
Step 2: reduction to the base algorithm. We show that the regret of Algorithm I can be controlled by the regret of the base algorithm plus moving cost term. By the design of Algorithm [ it updates a univariate loss function at most once every m steps. If all the 2, across these m steps are the same, (ggret(Algorithmm
[ will be exactly the same m Regret(base algorithm). When 2, different,
we suffer additional moving cost E Σ Etmm fe(zem+1aa) fe fe(zt- which can be bounded by the assumption on the gradient of ft if 2 changes slowly.
Step 3: bounding the moving cost. We partition the moving cost Le (e(zi-m+1z)) Sel Je( m++) into
three terms
F ft fe( fc fe + fe(or- - fl(o-m+1)++ Felor-m+1) - Fe F((2--m4z).
(a)
(0)
8

---

Here, (a). (c) can be seen perturbation loss suffered by the algorithm during exploration. (b) is the moving cost determined by the stability of the algorithm's neighboring iterates.
For the three terms in the above equation, (c) is bounded by Jensen's 's inequality using the convexity of the unary form of loss. We bound (a) using the curvature assumptions and the affine memory structure of ft. where we also make use of the delayed updates to decorrelate neighboring iterates for technical reasons. (b) bounded by the Lipschitzness of ft and the distance between neighboring iterates, Theorem 6 is reached by putting the three steps together.
4 Optimal Regret for Bandit Non-stochastic Control
In this section, we show how to achieve optimal regret for the bandit non-stochastic control problem with partially observable LTI dynamical system as described in Eq. (T) for strongly-convex smooth loss, by reduction the BCO-M algorithm (Algorithm [ we devise in the previous section. Previously, the best known regret bound for this problem was ( from (Cassel and Koren 2020), which is also rooted in a reduction to BCO-M. We use a similar reduction, obtaining a better bound thanks to the improved regret bound of BCO-M (Theorem (6). We first give the formal definition of the control problem.
Definition 7 (Bandit non-stochastic control). A bandit non-stochastic control problem of partially observable LDS is parametrized by a tuple L = (A, B, C, (WY))EN, (et) (Ce (C))e,, IT), where A, B, C and (W))XEN, (ct)teN are the dynamics and perturbations in the L.S (Eq. (1) with initial state 21 (we assume x z1=0 without loss of generality henceforth);
measures the instantaneous cost
time t; 1I is the comparator control policy class. Given any bandit non-stochastic control algorithm A, the regret of ANC on L over time horizon T' E NN is given by
Regretz (C,11) - Σ Colur
NN u
min TEll
cavi u
where (WAANG up urth ), (NT u,) are the observation, control pair at time L following the trajec- tory of ANC and π, respectively. We say that bandit non-stochastic control problem L is (a,, B, G, Nays: K. 7, Rw,e. M. weeleccccnnd if L and II satisfy Assumption with de
a, B. B, G. G' over some centered bounded convex domain y x U C Rd Assump- tion] 2 with Ksys K. 7/4 Assumption with Rw.e. and Assumption
The reduction from partially observable bandit non-stochastic control to BCO-M consists of two main steps. The first step construct the would-be signal (x(K) from the observation ye. where 31 (K) is used for updating but not directly observed by the controller. Ve (K) is computed by using the Markov operator of the LDS (Simchowitz al., 2020). The second step is standard black-box reduction from control to BCO-M, which uses the strong stability of the system. Reduction is formalized in the following definition.
Definition 8 (Approximationn. A bandit non-stochastic control instance (Definition L with some convex comparator class II over a time horizon T N is said to be e-approximated > 0) by BCO-M instance (Definition 5) O with domain IC = II, if the existence of a BCO-M algorithm AA implies the existence of bandit stochastc control algorithm NC satisfying
Regret NC K. (C,
< E Regrett " =(()] + ET..
The formal guarantee of the reduction is given below.
Lemma (Control reduction). Every instance of (ac, Be, Ge, Keg 16, Y, -.ul- conditioned bandit non-stochastic control problem L over the ball y x C. Rdy+do of radius
R with comparator class II M(m, RM) (Definition) [) is 2G DmT -approximated by
(o.,, By, G5. D) -eeloccl-ond BCO-M instance O with
4096 m09 R2 R2 3 R
B, = Bas D mmax dy RMM G₁
aj =a
provided that m (log log(1/(1-
*See Appendix B R Rw.e
(1 virum)
(VI+ RM 14 Vdu(I+x?)a), Vdo(Ltt37m0)) =0(1) -0(1))

---

Lemma 9 implies that every well-conditioned bandit non-stochastic control problem can be reduced well-conditioned BCO-M instance, whose parameters are polynomial in those of the control problem. As result, any regret bound for BCO-M will directly transfer to the control problem (at the expense of polynomial dependence on the system parameters). particular, combining Theorem and Lemma we obtain an optimal O(VT) regret bound for the bandit non-stochastic control with strongly-convex smooth cost.
Theorem 10 (Bandit non-stochastic control regret guarantee). Given an (o. B, G, Fayss Ki V, Bw.es V,2)) well---cocnnd bandit non-stochastic control instance L over the
ball RBd, C. Rdytd, for the same R as in Lemma
with G, Keys: R, s Rw dzs dy dy = 0(1
let (II, K. n7, m, P G, K, ) be the input to Algorithm 2
with
= poly(log T). Algorithm
guarantees that
Aigorithm 2 (O) S (2VVT)
max IE
=EK
where Ō()) hides all universal constants and logarithmic dependence in
Theorem 10 strictly improves Theorem 8 of (Cassel and Koren 2020) and Theorem 5 of (Suggala
ct al. 2024). the sense that our result achieves the optimal regret with fewer assumptions: all
three results achieve the same Ô _ VTT regret bound, however (Cassel and Koren 2020) requires
the additional assumption that perturbations are stochastic, while (Suggala et al. additional assumption that costs are quadratic.
2024) requires the
Algorithm 2 Improved Bandit stochascccttic Control
Input: Step size > O, memory parameter m. DRC policy class M(m, RM)., time horizon T, system dynamics, (x, ) stabilizing linear policy K, strong convexity parameter a >> 0.
1: Let A be an instance of Algorithm
! with inputs (AC = =M(m, R.M.. 77, m. a, T)..
2: Initialize: M =... Mhi 0a, xdy Vj [m].
-m-1 Omdady Ao
Ám-1 = ml xmdudd
3: Initialize AAt for 1,. m - (lines 1-4 in Algorithm
4: Sample
gmddddy11 i.i.d. uniformly at random for / m.
5: Play control it = Ky, incur cost et (yyy, u.) for E [m]]
6: for m...... do
7: Play control u. Mr Ky: + EY=
incur cost (3 u.).
8: Let ft (M(m, RM)) + be the induced with-memory loss function via reduction in Lemma H. be the associated Hessian estimator in Assumption
9: Update M + AB, (fo...m {H.))..).
end for
Conclusion
In this paper, we devise an algorithm with an Ö(VT) regret bound for the bandit non non-stochastic control problem with adversarial strongly-conver smooth cost functions. This is the first result with optimal regret that simultaneously breaks the three assumptions of LQC (1) stochastic perturbation (2) full-information feedback (3) quadratic cost. Our control algorithm is built upon an improved algorithm for BCO-M, which may be of independent interest.
As preliminary step to address the question a general control theory for LTI, our result comes with limitations and potential future research directions. Currently, the improvement over the Ö(T2/S regret by (Cassel and Koren 2020) is made under the additional assumption of strong convexity. It's unclear whether this assumption is necessary for ((VT) regret, leave determining the minimal assumption on the cost functions for optimal regret as an open question.
'The assumption that the system parameters are of order Õ(1) is consistent with prior works (Hazan and Singh 2022
10

---

References
Agarwal, N., Bullins, B., Hazan, E., Kakade, S., and Singh, K. (2019a). Online control with adversarial disturbances. In International Conference Machine Learning, pages 111-119. PMLR.
Agarwal, N., Hazan, E., and Singh, K. (2019b). Logarithmic regret for online control. Advances in Neural Information Processing Systems, 32.
Anava, O., Hazan, E., and Mannor, S. (2015). Online learning for adversaries with memory: price of past mistakes. Advances in Neural Information Processing Systems, 28.
Bellman, R. (1954). The theory of dynamic programming. Bulletin of the American Mathematical Society, 5035)553
Cassel, A. and Koren, T. (2020). Bandit linear control. Advances in Neural Information Processing Systems, 33:8872-8882.
Gradu, P., Hallman, J., and Hazan, E. (2020). Non-stochastic control with bandit feedhack. Advances in Neural Information Processing Systems, 33:10764-10774.
Hazan, E., Agarwal. A., and Kale, S. (2007). Logarithmic regret algorithms for online convex optimization. Machine Learning, 69(2):169-192.
Hazan, E. and Singh, K. (2022). Introduction to online non-stochastic control. arXiv preprint arXiv:2211.09619.
Kalman, R. E. (1960). A new approach to linear filtering and prediction problems.
Kalman, R. F. al. (1960). Contributions the theory of optimal control. Bol. soc. mat. mexicana, 5(2):102-119.
Lattimore, T. (2024). Bandit convex optimisation. arXiv preprint arXiv:2402.06535.
Lattimore, T. and György, A. (2023). A second-order method for stochastic bandit convex optimisa- tion. In The Thirty Sixth Annual Conference on Learning Theory, pages 2067-2094. PMLR.
Simchowitz, M. (2020). Making non-stochastic control (almost) as easy as stochastic, Advances in Neural Information Processing Systems, 33:1831 (1838818829)
Simchowitz, M., Singh, K., and Hazan, E. (2020). Improper learning for non-stochastic control, In Conference on Learning Theory, pages 3320-3436. PMLR.
Suggala, A., Sun, Y. J., Netrapalli, P., and Hazan, E. (2024). Second order methods for bandit optimization and control. arXiv preprint Stt::22002.08922
Suggala, S., Ravikumar, P., and Netrapalli, (2021). Efficient bandit convex optimization: Beyond linear losses. In Conference on Learning Theory, pages
PMLR.
Sun, Y. J.. Newman, S., and Hazan, E. (2024). Optimal rates for bandit non-stochastic control. Advances in Neural Information Processing Systems, 36.
Yan, Y.H.,, Wang, J., and Zhao, P. (2024). Handling heterogeneous curvatures bandit Iqr control. In Forty-first International Conference Machine Learning.

---

Contents
Introduction
1.1
Technical Overview
1.2
Related Work
Preliminary
Online non-stochastic control with bandit Teedback
2.2
Bandit convex optimization with memory (BCO-M)
2.3
Notations
3
Improved Bandit Convex Optimization with Memory
3.1
BCO-M algorithm
3.2
Proof Sketch
Optimal Regret for Bandit Non-stochastic Control
Conclusion
10
Proof of Theorem
13
Base No-Memory BCO Algorithm and Guarantees
13
Reduction
15
A.3
Bounding Moving Cost
16
A 4 Proof of Theorem
20
Proof of Lemma
12

---

A Proof of Theorem 6
The proof is reduction-based. It consists of three parts
1. We first consider an algorithm for the no- no-memory BCO problem, which uses Newton-based updates and novel delay mechanism. This algorithm will serve the base algorithm.
2. We then show that the regret our main a be bounded by the regret of the base algorithm plus moving cost, via an improved analysis on Ko-convexity.
3. Finally, we bound the moving cost and then put every pieces together.
A.1 Base No-Memory BCO Algorithm and Guarantees
In this section, we prove Lemma 11 which establishes the regret guarantee for the base algorithm used by Algorithm 1
The base no-memory algorithm is variant of the Newton-based (improper) BCO algorithm considered in Algorithm of (Suggala et al. 2024). The main differences are:
Algorithm in (Suggala et al.) 2024) constructs Hessian estimators from the bandit feedback. Algorithm
B doesn't tt require Hessian estimators, since the H, determining co-coeeexity is given by the system instead loss in bandit control problems, and thus it's computable by the learner given the system parameters.
2. Algorithm inttooduces an additional delay mechanism (specified by the delay parameter do E N) decorrelate neighboring iterates, necessary ingredient to later analysis.
Algorithm 3 Simple BCO-
Input: convex compact set K. C IRd, step size v) > 0, delay parameter do E N, curvature parameter 0, time horizon T N.
Initialize: 01 K, Åo Laxd. A. Oaxd. Vt 0. g: 0, Yt V
2: Sample 11 Sa-1 uniformly at random. Set 21 01 A en.
3: for f 1,...,Td do
4: Play 2,, observe fe(2z), receive H,,
5: Update A, Á + 22 H,. 2
6: Create gradient estimate: 9t = df((z) Rd. A 11
7: Update o++1 I
0: -
8: Sample ui+1 ~ Sa-1 uniformly at random, independent of previous steps.
9: Set 2t-1 = O1+1 + A, 1241.
10: end for
Lemma (Base BCO regret guarantee). Suppose that the sequence of loss functions (.Y and the convex compact set IC satisfy the conditions Assumption 7 Assumption and the properties in Observation 4 and max (1, [Hell2) } < Ru, Vt. With a = a in the first condition in Observation 4 with inputs (K., n, do. a. T) satisfies the following
(n, do) satisfymg do 2/(n RR), Algorithm Algorihmm
regret guarantee: Vo E K.
23d
Dd Ru
E Σ f((x) f(x))-((o)
s na
T+ 2d,GD +
+ +3ndgd D2
2n
In particular, by choosing r (LIVVT) and do (1), the above regret is of order Ô (LV
Proof of Lemma 77 First, note that by the condition on and dg we have that A, = 2Å,, Vi < dg. To see this, it is equivalent proving any PSD matrix H with Amax (H) I 1 satisfies that H - which follows from the fact that x (I H)x
| Xmaz ||0] > 0, Vz.
13

---

By the convexity and curvature assumption on ft described by the conditions in Observation we have
T Σ -
BVV + 2 Blu A, H A, 3, 0z).
8
s
t=1
where the first-order term equals 0 since v, is drawn independently of or: fe, A and Blvr] = We can further bound the second order term by
8 2
29 naay Σ
E
Σ - -
B
H. I
E[A, (Á, 1..-An Ac-1)l.
where the first step follows from Elu² Av AA] = A- Blev and the cyclic property of trace, and the last step follows from the definition of Å,, the stability condition that A, ~ 2 and a = af- Using standard inequalities on log determinant Newton step analysis (Hazan 2007). we have
Σ fl(z) F((o))
2/ yas
log del (AT)
23d nas
log
"aaBRTT + 1).
det(Ag)
Moreover, the curvature assumption on J. also implies
T
E
Σ f(lo)) fi(o) -
(o)
21
Bllo: -
1=1
[=1
T
Blg (o: -o]] as
Σ
Blllo
o112.
(6)
t=1
where the second step follows from E[ge
or (o:) by Stoke's theorem. By the projection step
in Line of Algorithm 3 we have
110
oll A
< |1o:-1 A -d-dooll
1
= -Ilo--1 -ol13 - + 2/1 =110-11 - -oll y He-d0 - 2n (0 - 00) 112100r-- -dll-dol122 11 2
$ |10--1 011
- أ
+ 110r-ds - -oll o112a,, Hi-do + 1100c-d - -0-1l 2ng do (0--do 0)
+ +2ngT do (Di-do - 01-1) + 17² 11 - -d 1
where the last inequality follows from that AH 2 O, |1 + ull s 2( - 1lvll2))
Rearranging, we have
JT (Or-do -)
0f 0
-0l
2
100 0112 A -
llo: 0 Ac-Ao
+ of 11-00- 11.11/21 tr-ds 01-1) 2/2 -l 127-:000
2n
Note that Vt,
ll0e 1, I (dGD) T
A , A S (dGD)?
|lo: 0111 & Ilo: - 0c- A I nllār-do al,, 1, I ndGD,
where the second inequality in the second bound follows from the update rule in Line of Algorithm 3
which gives l|o, 01-1113 1122--00 < |1 -t 112.... = 7 1l do 113 1 Thus, we can further bound
112,2
Of 1|0:-o -11-11221-00 5 RA do
|10:-doti - -0- Ga D²
2
T Ii-do (Or-do - -(-1) < 11ār- 1,1 11oc-do - -0- S 2nnddd D2
14

---

Combining both and using that A, = 2A,-1. Vi I do. we have that
de
Σ
9t
T
(ot (o:
0) 0f 0t ol
t=
T
Σ 2dg
I (0--oo -0) 2
a 0 - -ollite-ds
aydna G22 G2 G2 RH + Gd
d&G D2
102dg - 0
+NI
21)
A1g-1
2
D d2 + D'
2m
As result,
DddoRH + D2
E
Σ ( -(()) s 2doGD
2n
Combining, we have
2Rd na
Dd Ru
E
Σ t=1
f((z)) F((0)
$
2d,DD+
+ 3nd D2
G2
21
A.2 Reduction
In this section, we prove Lemmal 12 can be related to the regret guarantee of the base no-memory BCO algorithm (Algorithm
which states that the regret of BCO-M algorithm (Algorithm)
I
We follow the proof idea of (Cassel and Koren 2020). In the previous section we have proved an Ö(vT) regret bound for "no-memory" base BCO algorithm. Our main Algorithm however, has memory dependence. When 2; is changing slowly, Algorithm is approximately a "no-memory" algorithm, and we can do the following reduction: if all the across these steps are the same, Regret(Algorithm) [ will be exactly the same as m Regret algorithm).
In this part, we show that when z are different, we only suffer an additional moving cost
fe(z-m+1a)) - felz--mti)
E
which we will bound Appendix A.3
Lemma 12 (Lemma 11, (Cassel and Koren 2020)). Let (K., 17, m, T) be the imput for Algorithm
Suppose that the loss functions (fe) and the convex compact set K. satisfy Assumption 5 Assump- Then, the regret of Algorithm 7 with respect to any E K.
tion Assumption 7 and Assumption 8
upper bounded by
T
E
folzz fo(za-m1in) - F((o) 3m RAlgorithm
E
Σ f((a-m41a) - - fe(aa-maz)
m
where RAlgorithm dg = 2.
the regret upper bound obtained in Lemma
11
with time horizon and
m
Proof of Lemma 12 First, note that by assumption, the conditions in Lemma are satisfied for the
induced unary forms (feT The argument follows by reducing Algorithm to Algorithm 3
Denote Xt = b, -m
by-)) as the indicator of whether the algorithm gets updated during round
Recall the definition of (1 E [T] Xt 1} Eq. (4) The algorithm updates during round t S. For any S, we have that Xt-1
Xc-m+1 0. Therefore, we have 2tm--1
15

---

by design of Algorithm Thus, we have that fe f((2(-m1::) = f((z(m+11) fzz). Therefore, constrained to the time steps S. Algorithm
is essentially running Algorithm with delay parameter do 2 (since in Line 12 of Algorithm]] T we update with the gradient information at time 8r-1 during round 1). Note that since |S] S T (Algorithm updates most once every m steps), we have that Vo E K.
-
T
Bbern hEs
S EBEE [Algorithmm
[SD S
Rtgoorthhn
LIES
LES
It is left to relate the quantity on the left hand side of the above expression to the regret of Algorithm
Since X Xm (the two random variables equal in distribution), Vt, we have E[xa] E[xm] For any fixed K, have
D
E1(0) Ebrrntte LIES
Σ Fo(o) X Eixml
Σ f((o)
(7)
For E N. denote Fe to be the o-algebra generated by the randomness of Algorithm [ through
sampling ba Us up time i.e. Fi (fb,, v v./s1)) Since 2 2 whenever X bt are drawn independently of ++ and X is independent of Ft by definition of Xr. we have
Σ f((t)) LIES
T
Ebg MI:TT
= Ebur,ee
Σ
fe(z-m+1) Xx
Σ fc(e-m41)) Xt Fe-ms mt-
F(xm]
fe(z
(8)
Together, Eq. 7 and Eq. (8)
give that
T fe(2-m+11) - F((o)
T
Σ Fe(
E())
E(xml E
Σ
I E[xm] RAlgorithm S
LES
EES
{=m
Therefore, we have that
T
T
((e)-m-1s)) - F((0)
= E
Fe(o)
+ E
fe fe(2(-m1:c) - Fe(2e-mta)
T
EE (m))) Algorithm
+
E
fe(zimm11a) - fe(ze-m+1)
S 3m Balgorithm
T
+
E
fe(ze-mtaa) Se(
m
m
where the last inequality follows from
1
(11
1
E
[m]]
Ebmml
II
bi]
m
m
em
3m
1=1
A.3 Bounding Moving Cost
Lemma I1 and Lemma 12 almost give the regret guarantee in Theorem the moving cost term in Lemma
We are left with bounding
E
Σ
fe( - Fe fe(ze-
16

---

(Cassel and Koren 2020) bounded each of the summands by E[ + v/l. where 6; = ||0:+1 0. 2.
and 74 4. oz 2- 2- Making use of the No Ko-convexity induced by the affine memory structure of
non-stochastic control problems, we can establish tighter bound that is necessary to obtain optimal regret in Theorem [
Lemma 13 (Moving cost). Let (K, 17, m. m. be the input for Algorithm 1 Suppose that the loss
functions {ft)f-m and the convex compact set K. satisfy Assumption 5 Assumption Assumption
and Assumption 8
Suppose S 22/(naRn) Then, the iterates output by Algorithm 7 satisfy
12m BR max no log(na + 1)+
10m² R
E
fe( fe(2---11) Fe(zc-mt1)
mak(G)
k(G)
t=
m2 3dR VT ndGDD BT.
In particular, with 1j ((VT), m = poly(log T) and x(G) = 21(1) by Assumption the above bound is of order (VVT).
we have that
Proof of Lemmal 13 We can decompose the moving cost into three terms:
T
T
T
E
fe(zt 11) - felo felor-m1:t)
+
Σ
felor fe(or-+t:t)) Fe(or
+
Σ
fe(ormm+1) -fee-ffeeee fe(ze-mt1)
[=m
(6)
(c)
and we will bound each of the terms separately. particular, (a), (c) can be seen as perturbation loss suffered by the algorithm during exploration. (b) is the moving cost determined by the stability of the algorithm's 's neighboring iterates. We start with establishing bounds on (a), (c).
Perturbation loss. As before, we denote F; = of U2 V=)==)) to be the o-algebra generated by the randomness of Algorithm I throuugh sampling b,, Us up to time t. First, (c) S 0 by Jensen's inequality for conditional expectations. In particular, recall that Xt b, (1 b denotes whether the decision is updated at time f. For every E N, denote as T(t) == max < t X = 1} the last time that the algorithm updates its decision. naturally holds that O2 = 0T()+1. Ue UT())+1 by design Therefore, we have
of Algorithm]] 0
[[fe(or- m+)) - fe(zt-m+1)] B[ 1-a--/-1n [
(
f((oT(e-m+)) + A + (T(t-m+ m)++)))
By the sampling rule in Line 13 of Algorithm D if the algorithm updates its decision at time I (x+ 1), then ut+1 is independent drawn from previous steps. On the other hand, 0441 is measurable w.r.t. F, Therefore, we have by Jensen's inequality for conditional expectations that
2 (if((or(-m+1)-- f((ora-m A UT -eft-m++e m+1)+1>]l
(lf((or(-- -l + A uT ( m1444) (t
< Elfi(or(tm m1))1) - F.(B(or(-mtt)-1 + A ura +1) F Fr(-mm))))
B(f((or(-m41)) - Fe(or(-mti)) 0.
Summing up over t, get that (c) S 0. We move bound (a). We start with a (conditional) independence argument.
Independence argument. Fix f. Denote f =T(t) to be the most recent time when the algorithm makes an update. Additionally, denote to = T(T(t)) to be the second most recent time when the algorithm makes an update. We already have 0; 0t,+1. By the delayed update rule in Line I2 of Algorithm I. we have that 0t,+1 is updated with Oz, = Otg+1 and gradient information gt, and thus is Fr, measurable. On the other hand, consider the sequence of random vectors Ut-m+1,- Vt- We have that v, = UT())+1 1 for every t m + < s I t. Since the algorithm updates at most once every m steps, we have that T(s) 2 la for all m + 1 S S t. Therefore, ft-m=1..... independent of Fiz. This observation de-correlates o, with Vt-m+1.... v, conditioning Fiz-
17

---

For notation simplicity, for matrices A....., An Bdxd and vectors 01, ........ Un E R we slightly abuse notation and denote as Alm (A1 11.,...... u, E Rnd be the concatenated matrix- vector product of the two sequences.
We apply Taylor's theorem the function ft and obtain that
(a) - B Vfllo: A A m 2 2 i-mit-1 V file --m-
where 91- ml+ is some point that lies on the line segment connecting Ot-m+1:t and 24 m1: By the conditional independence argument, we have that the first order term vanishes: let (()()).
E Vfi(Or- A Pt-m+1d 1:t
E
E
Vf( (f((omm+1a))
" A 1 Fez
E
Vf (fr(omm+1aa))
A A [ (0 Fral
0.
The above sum thus reduces to the sum of second-order terms:
T
U/ U
A
f 1t- m
V
T
(A, m
Am v/)
T
fe (4)))
A m)mm))
U4
1=
Ar3
0
0
0
0
m-m
E
0
A 1-m m
0
fi(g--m+1it)
0
A m
0
2
1=
0
0
A
0
0
T
A fm
0
0
m
E
fe(
0
0
2
t-
0
0
A
m
m
E
A
V Vela--mtaall
where the first inequality follows from A, = A, for all < t; the second inequality follows from taking maximum over all concatenated unit vectors in Rd the third inequality follows from the inequality between trace and spectral norm.
From this point on, the bound follows almost identically the proof of Proposition 21 in (Suggala et al. 2024). We will reiterate the proof a concise manner for completeness.
Note that by the assumption of affine memory structure (Assumption 5) we can write the following expression for the Hessian matrix of fe evaluated at @t-m+1:t as the following:
WT-m= V W m-++1 W
Vflgg-m+1a)) m410))
W. (g)
W.VVL(
where 9 = B, + ΣT Gill and Wi-m+i = gim-ily, V1 S S m. By the curvature assumption & (Assumption 6), further bound the sum of diagonal blocks by m
m
(10m-m41:1l 3
W. mots Wr-m+i
Y Y- (Glm-sl (c cim-slyy
3 3RH
Y
18

---

Therefore, we can further bound
m
T
E
A A,
Σ
17
V fe (att-m+i:))l
m
m2 3R
T
E
A-1
Σ
Y.
2
2
m-m
T
1=1
s=f-m+
$ mm33pr
RR
A-1
Yo
s=t-m+1
Consider y LVT] and endpoints k, ~(j - 1) + m for j = 1.....JJ and J = --T="] Using
the fact that Trace (AC) Trace (BC) for any PSD matrices A, B, C with A 3 B, can further decompose and bound the sum in the above expression by
h+41-1
m? RR Σ Art
Σ
Y.V,,
m 3RH
An
Σ
Σ
Y,
+ m² Byd
m
m-1
==1
1= smt-m++
1511-1
m 3RH
A-1.
Σ
Y Yg
+ m² BydR;
j=1
tmmk mm+1
k
2m RmH
A -1
Rm +
Σ
He
m² BydR
GG
5=1
tk
11-1-1
2m 3RH
10m BRR
Ar!
Hi
m 3dR VT.
x(G)
x(G))
t
where the first inequality follows by applying the radius bounds on Y, for the last T J-y terms and using the fact that A, < A, for any s < t; the last inequality follows by applying Proposition 4.8 in (Simchowitz 2020 Therefore, suffices to bound the sum in the first term in expectation. First, recall that Vt, X b, b,) denotes whether Algorithm updates during round t, and = {m < < T: = }} denotes the set of all rounds where Algorithm updates. To bound the following, we make use of the facts that (1) H; is oblivious, and (2) Xt is independent of A for any
k: m. Then, we have that
Rit1 -1
E
Σ
Akmmm
H = E
A=1 Akym He Xt
j=1 telk telkkyketttnnn
t= k
k
E ky
H.]
E(xi]
1=
1441-1
Eix - E
Azj-m H
t=
k
> 3 - E
A Hi
t=
19

---

Using this and that As I 2A--m. we have that
K
E
Abj H₂
S
2m[xm]
'E
E
Σ
Arj He
k=
j-1
Asg -Jns
6m
IE
A
(AR - Ax
na
j=1
6m max naR
J
.
A Ayt1 (Augei-1- - Akg-
nj
6m max 2, na naR
Σ log (dot(Assts-1))
E
nj
det((Ar;-1)
6m max 2, naR det(())))))
nja
6dm max (2, no R
log(na Ry +1,,
where the first inequality follows from 11111-13 3 max 2, no R Ary. and rest follows from the
standard inequalities used in Newton-step analysis Hazan al. 2007).
Combining all the bounds, we have that
(a) 12m 12m43Rud max noRnH log(na Ru + +) 10m 10m mi BdR VT.
Gan(G)
x(G)
Movement cost. By design, the algorithm updates at most once in every m iterations. Therefore,
(ot 0r) (o.- 105-mmhe Ct S
where 8 is the Euclidean distance between neighboring iterates Algorithm
By analysis in
Lemma we have s < mdGDD By Lipschitz assumption on ft, we have
(b) S ndGD² BT.
Combining, have that the total moving cost is bounded by
fz m- 1:)) f6(2e-mt)
12m BRnd max naRn (ng(naRn + 1) nax(GG
10m 10m43R3 dVT
x(())
m² BdddRR +dGD2=
A.4 Proof of Theorem 6
Combining result from Lemma w.r.t. to any z E K. is bounded by
Lemma 12 and Lemma 1
we have the regret of Algorithm
2,3d log(n + 1) (dD( +
Dn
E B(eegret, (z)] < 3m
+ 3 R
na
2y
12m BR max(2, noR VT)
10m4 3R3 d/T
max(G)
x(G)
+ m2 BdR /T + ddG
and by choosing 17 = (1//7 we have the regret above is bounded by ò (@GDVT)
20

---

B Proof of Lemma 9
In this section, we prove Lemma 9 We begin by defining the Markov operator (Simchowitz et al.. 2020).
Definition 14 (Markov operator), Given a partially observable LDS instance parametrized by dynam-
ies A E R24 Xxx, B E IR xd. C E xd, satisfying Assumption with (re, 7) - stabilizing
K, define the Markov operator to be a sequence of matrices {Gl ]22 such that G [0; Ia..
and Vi 0, GL is given by
C G = KC
[Kc
(A+ (AC td,
The next observation (Observation 15) relates ye (e()), the signals used by the DRC policies (Defini- tion D}. to the observations and controls along the learner's trajectory. This justifies the accessibility of the signals.
Observation 15. Given partially observable LDS instance with (K, -sstronlyy stabilizing K, let G be the Markov operator in Definition 14 For t, i. N, let Mi...., Mi....,M-11 Rmxxd. be (L (4-11 1) playing MI...., M4-1 for time step I..... ....... ,t- 1. Let (K() be the control time by executing the linear policy K, i.e. (e(K) = K (K), and ye (K) be the would-be observation had K been executed from the beginning of the time. Then, (ye, uz) and (yr(K), u. (K))) can be related by the following equality:
DRC matrices (Definition 7}. Let (Wt, u³) be the observation-contee pair reached by
(c(K) (y((K)
= GlU
Σ MM.
(9)
In particular, Eq. (9) implies that yo (K) can be computed by the learner through access to the Markov operator G and the observations along the learner's 's own trajectory.
almost ready to reduce the control instance to the BCO-M problem. One delicate detail that the BCO-M problem is defined for vector-valuse decisions, and the the space M(n, RM) space of sequences of matrices. For clarity of presentation, we define the following embedding operators.
With Eq. (9),
Definition 16 (Embedding operators). For m, dy. du E N, denote d = mdydu. The embedding operator e (IR (dn, (m - Rdd is the natural embedding of a DRC controller M = M (0mm- (Definition in IRd. In particular, Vk [m - 1], e [du], E [dy].
(Ckd +(6 Ij e(M) = M!!!
Let cy (R4)m R.d.xe xd be given by Vyt fyt-m+1.-.. .... W/ TR Vi E [du], k [m].
(cy00t
Vt-
(k 1)dudy + (i 1)dy.
Proof of Lemma 9 Let B. (K) Kyr (K))
Eim Gli ( E Bdutdy, Vt. Let
Ye = e, (1 (k)((())) Then, by Eq. we have
m-
ce(v,, uz) = at
B
Σ
We can't directly define our fo this function because the Σi_ GolY term in B depends on historical steps, which will lead to an unbounded memory.
To this end, we define
((on(K) ((u)(K))Kui()) Kv((K) + Σ C
m-1
(10)
21

---

which is independent of Mi-m+1:. and Y is independent of Mi.r. Note that by the loss function with memory has an affine memory structure. Morcover. G and Y are computable by the learner given system parameters. By the choice of m (log T). the Lipschitzness of ct, and the norm-decaying property of G due the stability of the system, we can bound the distance
(ee(yr. u.) - fele(Mo-m+1))... eMM)) = (Tly(T))
In particular, we can choose m such that this term is O ) then any regret bound on Se in the BCO-M setting directly transfers the same regret bound on in the control setring, negligible o(1) cost which will be subsumed by the approximation error term.
We are left with two steps conclude this lemma. First, we need to show that fo indeed satisfies the conditions Definition 5 and specify the constants. Next, because ft is not equal to o while we only have access C, the gradient estimator for constructed from is biased. We need to bound this error and show that it has negligible impact on the regret bound.
Step 1: We denote the unary form to be Je as in Definition [MMm, m, (fihtmm,eee be the associated BCO-M instance (Definition
2
Let O =
By construction, ft satisfies Assumption 8 and Assumption 5 other than the assumption on positive
convolution inveriibiliy if the truncated vector (ve ( (K), ye (x)) + - mn _e always lives the RB, and the matrix parameters are bounded. For the positive convolution invertibility Lemma 3.1 in (Simchowitz, 2020) proves that the Glol t induced by the Markov operator in Definition 14 satisfies the positive convolution invertiillty-modulus. i.e. k(G) = 2(1). By assumption on ct. the curvature assumption in Assumption 6 is also satisfied. It is left to check the diameter bounds in Assumption S
and Assumption 7
First, we establish a diameter bound on our learning comparator set M(m, RM).
Diameter bound on KC M(m,, RM)) The diameter of the set M(m, RM) is given by
max [|o(Azz) c(222)ll2 S vm M. M.EMm,
max
max
|| M!'l ||
Mi MM.MM.M(m.RM
05iSm-1
m max d
max Mi MMMMM 0575m-1
max
||
11
1lop
m max d,) RM-
Algorithm 2 essentially calls the improper BCO-M algorithm in Algorithm With the diameter bound on M(m, RM), we know that the matrices governing the controls picked by Algorithm 2 during each round lives in the set (Mm, R + m). For simplicity, may assume that RM 2 m and thus the decisions made by Algorithm live in M(m, M)
Now, we are ready to prove the gradient bound on f. and the bounds on the observation-control pairs produced by Algorithm
Gradient bound of ft. First, we bound the sum of operator norms for the Markov operator. By Assumption and the fact that VM E Raxx, || S / S M|l, we have that
| llp 11
/IC(A+ BKC)+BBBB)BBB,, +ICCA++ B B
m |ILL'
< 1 + / x2) 2
<1 / /d x2) 3
71-7)²
=1+ / dd + k2 k2)
7
22

---

The signals yr (K) has the following norn bound:
r-1
max (E[T]
(B)()))l22
max tE[T]
C
(A + WKCC
2=0
Rage
1 v dgys
|HIL'1
1+ Vilations
S Rm.e
By the unfolding of (y,, Me) we) in Eq. norm bound: VL,
9 the observation and control pair (Mt, We) has the following
Ky.(K))la (v.. u2ll2 = (())))) +
Gl
Σ M
1
U1
==1
< Rw.e
1
vdgtings
V 1 + R2
+ +2RM
Σ
Gl
1=0
V Vigtings
(1
v do + 162 )))aayy )) R.
S Rw.e
1
VI+*2 2RM
The above bound holds similarly for the truncated (De, ūe)
== (Ve(K), KB((K))
Eioo Gfly ((M in Eq. (10). which shows that (De, ûe) E RlBay+d. This also completes
checking Assumption 5
By assumption, obeys the Lipschitz bounds
Ve,yy, u)ll2 Gell(y, u)ll2-
The gradient bound on fe is given by
[Vfi(e(Me c(M:))
=|(((G|m-)) (),,m+4) (ex Ve ūt) ...., (G(0l))) Verl un))
v do + (1
2 GoRa, (1+ vdgtion))
(VL+ +2M
1+ v do (1
x3?)
nigss
2
vm 1+
7 R2 de
?
4096 m
73
Clearly the gradient estimator obtained for f. is biased. We denote this error as a, which has norm bound ||a 2 O(+) with the same reasoning on bounding |c+ - Sz]. Now, only need to show that Algorithm 1 can tolerate such perturbation with no loss in regret.
Step 2:
It's known that the OGD algorithm bounded by O with no cost in regret. We will prove similar argument for Algorithm 3 Suppose in line 6, the unbiased gradient estimator 9, is replaced by biased estimator = Ôt + ae. then want to extend the regret bound for Algorithm 3 in Lemma IT in this setting with an additional term depending the sum of magnitude of az The analysis in the proof of Lemma 1T remains unchanged except when we bound the regret for the sequence {or VT in Eq. (6) the inequality becomes
tolerate per-round adaptive gradient perturbation with norm
T D Je(os) - F((o))
T
T Blllo - o122.
E
<
E(VS((o)) - -0]]
af Σ
2
1=1
T
T
Σ
Elg. (o. -o] Σ
Ela (o. -o]]
-aa
af Σ
Blllo: - ol1?,,1
2 1=1
23

---

The rest of proof after Eq. 6 is indentical, except that we replace each appearance of ğr by 9c-
Therefore, the regret incurred by using Dr instead of 9t the gradient estimator is bounded by the regret upper bound in Lemma 11 and the additional term E Ela," (or - o)] S aDT, where [T] ||ar|22. Since a O ) the additional regret bounded by O(1).
Concluding the lemma:
Denote
0 = Oc:: Bg Bc: D = v m max dy R.:
7/
We have that by Assumption 4 that
E Regretz NC
(C)
T
max
E
Σ
Cell (e(Mar11)) (M), (M()))
Rxx)
S GGDDm+ +E
Σ fele(Ms-mt)...... ((M))) F((e(M)))
c(w un()))
+ E
l=
cl, ((y)))(MM)) (wi((), +
Σ clyy, x
E
Ca
Br +
mm
1=0
1=0
f( ((Mo))) FAlccun) +G,Dm,
E
where we have
C2
B: +
Σ
G ((
(k)(K))))))))) + Σ cl c(
1=0
< G
Σ
gld y, c(M)
SG. Σ
|| Ul ||-
Recall that
M Σ
| < max(du, dg} Σ
|Mbiie m max dy RRy:
llee (K)ll S mmdyy Rew. (1+ v Vattiigs tE(T
||V:|12 = mdd
max
max
EE(T]
?/
(1 7) < dd x22) k (1 7
||G S dd R2?
Mays
We have for m 2 (IogT] ()))))))
(.dddyd,ddd1 + ( m
Ge
| lop V v
72
GandyyRdd mig R.
2T
24

---

Combining, we have
Gond, d RM
E Regreet NC (2) < E
Regrets [0)]
+ Dm
7/2
Regretz 1 (0) + 2G,Dm,
E
which concludes the claim that O 2G DGmDII approximmates L.
25

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: make sure all the claims are accurate.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: we discuss the limitations and future directions for improvement the Discus- sion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
26

---

Justification: we provide the full set of assumptions for all theoretical results. We provide complete (and correct) proof for all theoretical results, among which the simpler ones are left to the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
27

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification: paper does not include experiments requiring code.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ "pippscc/puulli//uuu /otee//guudddeeeedSuuubbmiibii ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
28

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification: the paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
we carefully follow the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: there is no societal impact of the work performed.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
29

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: the paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: the paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
30

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: the paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
31


Reviews:
[{"review_id": "Gn3dXhCKe5", "reviewer": "Reviewer_r1Ah", "summary": "This paper studies the Linear Quadratic Control (LQC) problem with adversarial perturbations, bandit feedback models, and non-quadratic cost. The authors propose an algorithm that achieves $\\mathcal{O}(\\sqrt{T})$ optimal regret for bandit non-stochastic control with strongly-convex and smooth cost functions in the presence of adversarial perturbations, which improves the known $\\mathcal{O}(T^{2/3})$ of the previous work of Cassel and Koren [2020].\n\nThe dynamic system (partially observable linear time-invariant (LTI)) is defined as in Eq.(1). This work is largely inspired by the previous work of Suggala et al. [2024] which achieves optimal regret guarantee in a more restricted setting.", "questions": "The questions are raised in the weakness section. I am willing to re-evaluate the scores if these questions are properly answered.", "limitations": "This paper is pure theoretical and does not have any limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Though I have skimmed the proof of several lemmas, the analysis part seems to be rigorous and mathematically correct. \n2. The delayed mechanism to de-correlate the recent m iterates looks interesting, which may be of use in the other delayed feedback setting.", "weaknesses": "1. The specific contribution of this work towards the previous work of Suggala et al. [2024]  is still a little bit unclear. According to Line 382 to 387, it seem that the most important algorithmic contribution is the delay mechanism.  \n2. Not certain what it means by \"preserves an estimation of Hessian $H_t$ for free\" in Line 236. It seems related to Assumption 5 which provides the $H_t$ to the learner directly at the end of each iteration. I wonder if this sort of assumptions is general, and whether it is reasonable in the LTI control problem. \n\nTypo:\n1. line 248, length to lengthy. \n2. Definition 3, $f_t$ should be $f$? \n\nOther than these two issues, I haven't observed any specific weaknesses in this work.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insights and valuable feedback. We will address your concerns here.\n\n**Contribution towards previous work (Suggala et. al. (2024))**: The algorithm and guarantees presented by Suggala et al. (2024) are limited to quadratic functions due to their reliance on a gradient estimator for with-memory loss functions, which maintains a low-bias guarantee only for quadratic functions. We overcome this restriction by reducing the problem to a no-memory optimization scenario, leveraging techniques from Cassel and Koren (2020). In applying Cassel and Koren's reduction technique, a delay mechanism is essential to de-correlate the iterates.\n\n**Clarification of Line 236**: This sentence means $H$ can be directly computed by the system parameters in our framework, avoiding the typical costly sampling for approximation of Hessians (inefficiency is the main obstacle in using second-order methods). This is proved in Lemma 9, where we showed that the control problem is a well-conditioned instance of BCO-M problem. Here, well-conditioned requires Assumption 5. \n\nIn the general setting of BCO-M, Assumption 5 is not common. However, we are interested in solving the bandit linear control problem in which this assumption is natural (BCO-M is merely a tool to solve this control problem). In fact, this condition should be understood as a natural feat of LTI control, and only becomes an \"assumption\" in BCO-M.\n\nEven when the system is unknown, we can run one of the existing system estimation algorithms to obtain system estimates and compute this matrix using the system estimates. The theoretical guarantees for unknown systems are out of scope in this paper, but such extensions have been seen previously in Simchowitz (2020) and Suggala et. al. (2024), and these works have all assumed similar assumptions as in Assumption 5. We will add more discussion about this point in the main text.\n\n[1] Simchowitz, Max. Making non-stochastic control (almost) as easy as stochastic. Advances in Neural Information Processing Systems 33 (2020): 18318-18329.\n\n[2] Suggala, Arun, et al. Second Order Methods for Bandit Optimization and Control. The Thirty Seventh Annual Conference on Learning Theory. PMLR, 2024.\n\nFor the typos, we will fix them accordingly. Thank you for the careful reading of our work! \n\nIf our response has addressed your concerns, please consider reevaluate our paper. If you have further questions, please let us know. Thank you again for your valuable time and insights!", "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": "", "extra_scores": {}}, {"review_id": "YfkzYqPMeu", "reviewer": "Reviewer_vynp", "summary": "This paper considers the problem of online non-stochastic control, focusing specifically on scenarios where the loss function is characterized by bandit feedback, strong convexity, and smoothness, and the noise is adversarial. Prior research has typically managed to achieve $O(\\sqrt{T})$ regret under assumptions such as quadratic loss functions, full information feedback, or stochastic noise. This paper breaks these assumptions, demonstrating that an $O(\\sqrt{T})$ regret bound can be achieved even in the presence of adversarial noise, bandit feedback, and strongly convex loss functions.", "questions": "No questions.", "limitations": "See weaknesses.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This paper presents a direct theoretical improvement, offering significant advancements in the field. It is well-written and theoretically solid, providing a robust analysis and clear insights into the online non-stochastic control problem with adversarial noise, bandit feedback, and strongly convex loss functions.", "weaknesses": "1. The citation for Optimal rates for bandit non-stochastic control is incorrect; it was mistakenly written as NeurIPS 2024.\n\n2.This paper could benefit from some additional discussion. While this work presents a significant improvement in a specific scenario of online bandit control, it is equally important to address the challenge of designing a single algorithm that can achieve theoretical guarantees across different scenarios simultaneously. For instance, you might consider the problem proposed by the recent work \"Handling Heterogeneous Curvatures in Bandit LQR Control\" from ICML 2024. I believe that discussing this issue in the related work and future work sections would add significant value to the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insights and valuable feedback. We will address your concerns here.\n\n**Incorrect citation of Sun et. al. (2023)**: Thank you for pointing this out! We will fix the typo accordingly.\n\n**Discussions of previous work**: Thank you for bringing the relevant paper into our attention! Designing adaptive/universal algorithms is a central research topic in online learning, and it's even more important for online control which can be seen as a practical application of online learning. We will add more comparisons with this work and other related works, and discuss potential future directions on making our algorithm universal.\n\nTo our understanding, you have no further concerns beyond the two points raised above. We kindly ask you to consider raising the score if the two weaknesses have been addressed. Thank you again for your valuable time!", "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": "", "extra_scores": {}}, {"review_id": "RdZIvMS1GW", "reviewer": "Reviewer_iRqM", "summary": "This paper studys online control with adversarial pertubations, bandit feedback and adversarial strongly-convex smooth cost functions. This setting is more general than previous works and the authors successfully achieve $O(\\sqrt{T})$ regret by leveraging occasional update and Newton-based update.", "questions": "What is the main techinical challenge when combining and adapting the proof in [1] and [2]?", "limitations": "Yes.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. This paper generalizes previous settings and get the optimal regret.\n\n2. This paper is well-written and the intuition behind algorithm is explained clearly.", "weaknesses": "The technical contribution seems not strong, the analysis of Algorithm 1 (reduce to no-memory BCO, bound regret for base algorithm and moving cost) follows the proof sketch of [1]. The main change is replacing the base algorithm with Newton-based updates in Algorithm 2 of [2], ensuring a tighter bound by utilizing the $\\kappa$-convexity and affine memory.\n\n\n[1] Cassel, A. and Koren, T. (2020). Bandit linear control. Advances in Neural Information Processing Systems, 33:8872–8882.\n\n[2] Suggala, A., Sun, Y. J., Netrapalli, P., and Hazan, E. (2024). Second order methods for bandit\noptimization and control. arXiv preprint arXiv:2402.08929.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your insights and valuable feedback! We will address your concerns here.\n\n**Technical contribution**: we consider the main contribution of this work as pushing the frontier of bandit online control, by achieving optimal regret without quadratic loss or stochastic noise assumptions. To achieve this goal, we introduce several new algorithmic/analysis components towards previous works, but they are not the main objective. One technical challenge we resolve is that the analysis in (Suggala et. al. 2024) depends on the delayed dependence of the iterates (the current iterate only depends on the algorithm's sampling randomness up to time $t-m$). The algorithm in (Suggala et. al. 2024) automatically guarantees such independence since each iterate is updated with information up to the $t-m$ step. The limitation of such algorithm is that the gradient estimator only satisfies low-bias guarantee for quadratic functions, and that motivates the adaptation of the reduction in (Cassel and Koren, 2020). However, we note that the update rules used in (Cassel and Koren, 2020) no longer guarantees the delayed independence. Here, we use a delaying mechanism to preserve this delayed independence.", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work provided the first T^{1/2} regret result for bandit non-stochastic control for strongly convex loses, where previous results achieving the same rate only applied in presence of stochastic (or smoothed adversarial) perturbations, or for strongly convex quadratics. This contribution was appreciated by the reviewers. Happy to recommend this for acceptance.
Decision: Accept (poster)