Tight Rates for Bandit Control Beyond Quadratics

Authors: y jennifer sun
zhou  lu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 21:35:46

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.

Main paper: 
 introduction: 
 Optimal control lies at the heart of engineering and operations research, with applications ranging from launching spacecraft to stabilizing economies. The theory of optimal control is a well-established field with a 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 to a (partially observable) linear time-invariant (LTI) dynamical system:EQUATIONwhere A, B, C are the dynamics governing the system, x t , u t , y t , w t , e t represent the system state, control input, observation, perturbation, and observation noise at time t, respectively. At each time t, the controller observes y t and chooses a control u t , incurring a cost c t (y t , u t ) based on the current observation and control. The system then evolves according to Eq. (1) to reach the next state x t+1 .The theory of optimal control (e.g., LQC) typically relies on three key assumptions on the setting: the perturbation w t is stochastic, the cost function c t is quadratic and known in advance, and the function c t is observable to the controller. The linear-quadratic 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 too idealistic for practical scenarios. In real-world control problems, the perturbations can be adversarial, the feedback model can be bandit, and the cost function can be non-quadratic. This is evident in applications such as autonomous vehicle navigation, advertisement placement, and traffic signal control. This discrepancy between theory and practice raises a fundamental question for developing a more general control theory:Can we devise algorithms with provable guarantees for LTI control problems with adversarial perturbations, bandit feedback models, and non-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 c t can be time-varying, non-quadratic convex functions unknown to the controller; (2) the perturbation w t and the observation noise e t 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 Π:EQUATIONwhere (y t , u t ) is the observation-control pair reached by executing the controller at time t, and (y π t , u π t ) is the observation-control pair under the policy π 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 w t and observation noise e t are 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 Õ(T 2/3 ) 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 Õ( √ T ) 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 Ω(T 2/3 ) regret lower bound for general BCO with memory by (Suggala et al., 2024) , exploiting the special affine memory structure in control problems is 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 Õ( √ T ) regret bound. Our approach involves reducing the problem to no-memory BCO, which circumvents the high-dimensional 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.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 Õ(T 2/3 ) regret bound for smooth convex cost. However, such sub-optimality is arguably inevitable due to the Ω(T 2/3 ) regret lower bound for BCO-M with smooth convex1 cost (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 (OGD) 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 c t in the controlPerturbation Feedback Loss type (Agarwal et al., 2019a) Õ( √ T ) adversarial full strongly-convex (Agarwal et al., 2019b) O(log 7 T ) stochastic full convex (Cassel and Koren, 2020 ) Õ(T 2/3 ) adversarial bandit convex smooth (Cassel and Koren, 2020) Õ( √ T ) stochastic bandit strongly-convex smooth (Sun et al., 2024) Õ( √ T ) semi-adv bandit str-conv smooth quadratic (Suggala et al., (Agarwal et al., 2019a) addressed perturbation + loss, (Cassel and Koren, 2020) addressed feedback + loss, (Suggala et al., 2024) addressed perturbation + feedback. (Cassel and Koren, 2020 ) also obtained a sub-optimal Õ(T 2/3 ) regret for perturbation + feedback + loss.problem are strongly-convex, the induced loss functions in the BCO-M problem are not necessarily strongly-convex! It was observed by (Suggala et al., 2024) that the induced loss functions satisfy a property called κ-convexity, allowing for low-variance estimation of Hessian matrices, which is a key ingredient in Newton-based second-order 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 domainS d-1 := {x ∈ R d | ∥x∥ 2 = 1} of the exploration term is not preserved under Cartesian product: S d-1 × S d-1 ̸ = S d×d-1 .To handle this issue, (Suggala et al., 2024) relies on the quadratic cost assumption which admits an unbiased estimator of the divergence of the induced loss function. It's unclear how to handle general κ-convex smooth cost in BCO-M.Similar to its full-information counterpart, we reduce the bandit non-stochastic control problem to bandit convex optimization with memory (BCO-M). To overcome these challenges, we further reduce the BCO-M problem to a no-memory BCO problem following (Cassel and Koren, 2020) , to avoid the issue on the Cartesian product of S d-1 . This allows for the use of a Newton-based BCO-M algorithm similar to (Suggala et al., 2024) , which can handle general κ-convex smooth cost because the exploration domain is now S d-1 . Besides this new approach, our method also includes novel algorithmic components and analysis.Optimal control theory (Bellman, 1954) concerns finding a control for a dynamical system such that some objective function is optimized. The basic form of optimal control is linear quadratic control (Kalman, 1960) , in which a 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 perturbation 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 on the system. For the line of works on the full information feedback setting, see (Hazan and Singh, 2022) for a survey.Online non-stochastic 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 Õ(T 2/3 ) and Õ(T 3/4 ) regret bound respectively. When the cost functions are additionally stronglyconvex quadratics, (Sun et al., 2024) obtained an Õ( √ T ) regret, under semi-adversarial perturbations. (Yan et al., 2024) showed sublinear regret for cost functions with heterogeneous curvatures under the same semi-adversarial perturbations. This restriction on perturbation was later removed by (Suggala et al., 2024) which achieved the same regret for adversarial perturbations.Recent advancements on BCO (Lattimore and Gyö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 Ω(T 2/3 ) 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 Õ( √ T ) regret bound for BQO-M. 
online non-stochastic control with bandit feedback: 
 Consider the linear dynamical system in Eq. ( 1). At time t ∈ N, the learner receives observation y t and outputs control u t , to which the learner receives a scalar instantaneous cost c t (y t , u t ) depending on both the current observation and the control, and no other information about c t is available.The perturbation w t and observation noise e t can be adversarially chosen. The learner's goal is to minimize regret over a fixed time horizon T ∈ N defined in Eq. ( 2).Throughout this paper, all cost functions we consider are assumed to be twice continuously differentiable. Consistent with past literature (Sun et al., 2024; Suggala et al., 2024) , we make the following assumptions on the cost functions. × R du → R + satisfies that 1. (Curvature) c t is α c -strongly convex and β c -smooth over some compact set Y × U ⊂ R dy × R du for some α c , β c > 0, i.e., ∇c t (x 2 ) ⊤ (x 1 -x 2 ) + βc 2 ∥x 1 -x 2 ∥ 2 2 ≥ c t (x 1 ) -c t (x 2 ) ≥ ∇c t (x 2 ) ⊤ (x 1 -x 2 ) + αc 2 ∥x 1 -x 2 ∥ 2 2 for any x 1 , x 2 ∈ Y × U.There exists some G c > 0 such that the gradients satisfy ∥∇c t (y, u)∥ 2 ≤ G c ∥(y, u)∥ 2 for any y ∈ Y, u ∈ U.We also make stability assumption on the LDS in Eq. (1) 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.(1) satisfies that max{∥A∥ op , ∥B∥ op , ∥C∥ op } ≤ κ sys for some positive constant κ sys . There existsK ∈ R du×dy s.t. A + BKC = HL -1 H for some H ≻ 0 and max{∥K∥ 2 , ∥H∥ 2 , ∥H -1 ∥ 2 } ≤ κ, ∥L∥ 2 ≤ 1 -γ for some κ > 0, 0 < γ ≤ 1. Such K is called a (κ, γ)-stabilizing linear controller for the LDS. Assumption 3 (Bounded perturbation and noise). The perturbation and observation noise sequences satisfy the norm bound max t∈[T ] {max{∥w t ∥ 2 , ∥e t ∥ 2 }} ≤ R w,e for some R w,e > 0.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 decisions. Assumption 4 (Oblivious adversary). The sequence of cost functions {c t } T t=1 and the noise sequences {w t } T t=1 , {e t } T t=1 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 a 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 a policy π M parametrized by m ∈ N matrices M = M [0:m-1] in R du×dy such that the control at time t according to π M isu t (π M ) = Ky t + m-1 j=0 M [j] y t-j (K),where K is a (κ, γ)-stabilizing linear controller, and y K t is the would-be observation had the linear policy K been carried out from the beginning of the time.(2) A DRC policy class M(m, R M ), parameterized by m ∈ N, R M > 0, is the set of all DRC controller of length m and obeys the norm bound ∥M ∥ ℓ1,op := m-1 j=0 ∥M [j] ∥ op ≤ R M .A DRC policy always produces controls that ensure the system remains state bounded, the DRC class is expressive enough to approximate the class of linear policies of past observations (see Theorem 1 in (Simchowitz et al., 2020) ).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 z t ∈ R d , to which a scalar loss f t (z t-m+1:t ), depending on the learner's most recent m ∈ N decisions is revealed. Given a convex compact set K ⊂ R d as the domain of comparators, the regret is measured on the best single point z ∈ K over a time horizon of T ∈ N, formally given byRegret K T = max z∈K E T t=m f t (z t-m+1:t ) -f t (z, • • • , z) .In non-stochastic control, the learner's past decisions affect future states through an 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 5. Assumption 5 (Affine memory structure). At time t ∈ N, the loss function with memory length m takes the form of f t : (R d ) m → R + given by the following structureEQUATIONwith parameters B t ∈ R n , Y t-i ∈ R p×d , and G = G [0:m-1] a sequence of m matrices whereG [i] ∈ R n×p for some n, p ∈ N. 2 We denote G t = m-1 i=0 G [i] Y t-i ∈ R n×d , and H t = G ⊤ t G t ∈ R d×d .There exists some R H > 0 such that max{1, ∥G t ∥ 2 , ∥Y t ∥ 2 , ∥H t ∥ 2 } ≤ R H . In addition, we assume that G satisfies positive convolution invertibility-modulus, i.e. κ(G) = infn≥0 ∥un∥ 2 2 =1 n≥0 ∥ n i=0 G [i] u n-i ∥ 2 2 = Ω(1). We assume that the learner receives H t every step after they incurred the loss.We make two standard curvature and regularity assumptions on each of the instantaneous loss f t , that f t is strongly-convex and smooth, with its subgradient norm bounded by some constants, following the previous work of Suggala et al. (2024) . Assumption 6 (Curvature). Consider a loss function f t satisfying Assumption 5 and the setZ t = B t + m-1 i=0 G [i] Y t-i z t-i : z t-m+1 , . . . , z t ∈ K + B d ⊂ R n ,where B t , G, Y t-m+1:t are the parameters, and ℓ t : R n → R + is the function associated with f t in Assumption 5. We assume that ℓ t is α f -strongly-convex and β f -smooth, i.e.α f I n ⪯ ∇ 2 ℓ t (z) ⪯ β f I n , over Z t , with 0 < α f ≤ 1 ≤ β f here 3 . Assumption 7 (Regularity). For d ∈ N, denote B d := {x ∈ R d | ∥x∥ 2 ≤ 1} as the unit ball in R d .We assume that at time t, the with-memory loss function f t : (R d ) m → R + with memory parameter m ∈ N obeys the following gradient bounds overK + B d := {x + y | x ∈ K, y ∈ B d }: ∥∇f t (z 1 , . . . , z m )∥ 2 ≤ G f , ∀z 1 , . . . , z m ∈ K + B d .Additionally, we assume that K has Euclidean diameter D > 0.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 t denote the algorithm's decision at time t, then the loss function f t chosen by the adversary does not depend on z 1:t .In the definition of regret in BCO-M, we compare the cumulative loss of any algorithm with the best fixed comparator z ∈ K, evaluated on the induced unary form f t (z, . . . , z) of the loss f t . Formally, we have the following definition Definition 2 (Induced unary form). ∀t ∈ N, let ft : R d → R + denote the induced unary form of the loss f t , given by ft (z) = f t (z, . . . , z). Then, for f t satisfying Assumption 5, ft admits the structureft (z) = ℓ t B t + m-1 i=0 G [i] Y t-i z .We note that for f t satisfying Assumption 6, the induced unary form in Definition 2 satisfies a special curvature called κ-convexity introduced in (Suggala et al., 2024) . To avoid confusion with the notations with the bound on the dynamics (Assumption 2), we will call it κ 0 -convexity henceforth. Definition 3 (κ 0 -convexity, (Suggala et al., 2024) ). A function f : R d → R is called κ 0 -convex over a domain K ⊆ R d if and only if the following holds: f is convex and twice continuously differentiable, and moreover ∃c, C > 0 and a PSD matrix 0 ⪯ H ⪯ I s.t. the Hessian of f at anyz ∈ K satisfies cH ⪯ ∇ 2 f (z) ⪯ CH, C c ≤ κ 0 .The benefit that the loss function exhibits an affine memory dependence is that its induced unary form satisfies κ 0 convexity for some κ 0 > 0, summarized the following observation.Observation 4 (κ 0 -convexity and gradient bound of the unary loss.). Consider f t : (R d ) m → R + satisfying Assumption 5, Assumption 6, and Assumption 7. Then, the induced unary form ft : R d → R + in Definition 2 satisfies the following two properties:1. (κ 0 -convexity) ft is κ 0 -convex with κ 0 = β f /α f , H = H t : α f H t ⪯ ∇ 2 ft (z) ⪯ β f H t ,whereH t = G ⊤ t G t as in Assumption 5, ∀z ∈ R d . 2. (Gradient bound) ∥∇ ft (z)∥ 2 ≤ G f √ m, ∀z ∈ Z t .Proof of Observation 4. By our assumption on the affine structure off t in Assumption 5, ∀z ∈ R d , ∇ 2 ft (z) = G ⊤ t ∇ 2 ℓ t (B t + G t z)G t .κ 0 -convexity follows from the curvature assumption in Assumption 6. For anyz 1 , z 2 ∈ R d , we have that | ft (z 1 ) -ft (z 2 )| ≤ G f ∥(z 1 , • • • , z 1 ) -(z 2 , • • • , z 2 )∥ 2 = G f √ m∥z 1 -z 2 ∥ 2 .For a positive semidefinite square matrixH ⪰ 0 ∈ R d×d , define the norm ∥ • ∥ H on R d so that ∥v∥ 2 H = v ⊤ Hv.We write c t to denote the cost function of the control problem, and f t to denote the loss function for BCO with memory. For two sets A, B, A + B = {a + b : a ∈ A, b ∈ B}. For a set S, |S| denotes the cardinality of S. We use B d , S d-1 to denote the unit ball and unit sphere in R d , respectively. For n vectors v 1 , . . . , v n ∈ R d , we slightly abuse notation and shorthand as v 1:n to denote the concatenated vector (v 1 , . . . , v n ) ∈ R nd .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 in the Discussion 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 in 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 on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 κ 0 -convex functions from (Suggala et al., 2024) , achieving an optimal Õ( √ T ) regret bound, improving the previously best known Õ(T 2/3 ) result from (Cassel and Koren, 2020) . Besides the advancement on BCO-M, this result is the key component of our main result in control. First, we define the BCO-M instance.Definition 5 (BCO-M instance). Given d ∈ N, a BCO-M instance is parametrized by O = {K, m, {f t } t≥m,t∈N }, where K ⊂ R d is a convex compact set; m is the memory length; f t : K m → R + measures the instantaneous loss at time t. Given any bandit online learning with memory algorithm A B , the regret ofA B on O w.r.t. z ∈ K is given by Regret A B ,z T (O) = T t=m f t (z t-m+1:t ) -ft (z), where z t = z A B tis the decision according to A B at time t. We say a BCO-M instance O is affine and (α, β, G, D)-well-conditioned if O satisfies Assumption 5, Assumption 6 with α f = α, β f = β, Assumption 7 with G f = G, D f = D, and the adversary model satisfies Assumption 8.We describe Algorithm 1 that runs bandit convex optimization for any BCO-M instance O = {K, m, {f t } t≥m,t∈N }. On a high level, our algorithm employs the occasional update idea from (Cassel and Koren, 2020) . The decisions are updated at most once every m steps, ensured by thecondition b t m-1 i=1 (1 -b t-i ) = 1 (line 8 in Algorithm 1), where b t is the Bernoulli random variable (partially) deciding whether the algorithm will make an update at the current time step. We write o as the original ideal prediction, v as the random perturbation vector, and z is the actual prediction (as the perturbed o) of the algorithm.Input: convex compact set K ⊂ R d , step size η > 0, memory parameter m, curvature parameter α, time horizon T . 1: Initialize: o 1 = • • • = o m ∈ K, g0:m-1 = 0 d , Â0:m-1 = I, τ = 1. 2: Sample v t ∼ S d-1 i.i.d. uniformly at random for t = 1, . . . , m. 3: Set z t = o t + Â-1 2 t-1 v t , t = 1, . . . , m. 4: Draw b t ∼ Ber 1 m , t = 1, . . . , m. 5: for t = m, . . . , T do 6: Play z t , observe f t (z t-m+1:t ), receive H t = G ⊤ t G t . 7: Draw b t ∼ Ber 1 m . 8: if b t m-1 i=1 (1 -b t-i ) = 1 then 9:Let s τ = t.10:Update Ât = Ât-1 + ηα 2 H t .11:Create gradient estimate:gt = df t (z t-m+1:t ) Â 1 2 t-1 v t ∈ R d .12:Updateo t+1 = Âs τ -1 K o t -η Â-1 sτ-1 gsτ-1 . 13:Sample v t+1 ∼ S d-1 uniformly at random, independent of previous steps.Setz t+1 = o t+1 + Â-1 2 t v t+1 .15:τ ← τ + 1.16:else 17: Set o t+1 = o t , v t+1 = v t , z t+1 = z t , Ât = Ât-1 , gt = gt-1 . 18:end if 19: end for Such occasional update essentially reduces the BCO-M problem to a new no-memory BCO problem, whose equivalence will be shown later (see Appendix A.2). Consistent with the notation used in (Cassel and Koren, 2020) , we denote the following setS := {t ∈ [T ] : z t+1 ̸ = z t } (4)to be the set of time steps where the algorithm updates its decision. We readily have |S| ≤ T m . Moreover, we haveEQUATION) since t ∈ S implies b t-m+1 = • • • = b t-1 = 0.Thus, whenever Algorithm 1 updates, it effectively updates with function value ft (z t ).The occasional update alone only gives a sub-optimal Õ(T 2/3 ) regret as shown in (Cassel and Koren, 2020) . To achieve the optimal Õ( √ T ) regret, we use a Newton-based update to exploit the κ 0 -convexity 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 t 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 κ 0 -convexity, in the control problem H t can be constructed from the knowledge of system, instead of knowledge of loss which would typically incur a huge variance term.The regret guarantee of Algorithm 1 is given by the following theorem. Theorem 6 (BCO-M regret guarantee). Given an(α, β, G, D)-well-conditioned BCO-M instance O = {K, m, {f t } t≥m,t∈N } with m = poly(log T ) and G, D = Õ(1) (Definition 5), let (K, η = Θ(1/ √ T ), m, α, T ) be the input to Algorithm 1. Algorithm 1 guarantees that max z∈K E Regret Algorithm 1,z T (O) ≤ Õ β α GD √ T ,where Õ(•) hides all universal constants and logarithmic dependence in T .Theorem 6 is the first algorithm to achieve the optimal Õ( √ T ) regret bound for the BCO-M problem with general smooth convex loss. Compared with the Õ(T 2/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 Õ( √ T ) regret bound of (Suggala et al., 2024) 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 1 and its guarantee in Theorem 6 thus improve upon both of these previous results. The proof of Theorem 6 is lengthy, therefore we leave it to the appendix and include a sketch here.The theorem is proven via reduction to a no-memory BCO algorithm with Newton-based updates.Step 1: regret of the base algorithm. We devise a 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 a Hessian estimator H t , which holds in the control setting by utilizing the κ 0 -convexity property.Second, we incorporate a new delay mechanism to decorrelate neighboring iterates such that o t 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 Õ(√ T ) regret bound (see Lemma 11).Step 2: reduction to the base algorithm. We show that the regret of Algorithm 1 can be controlled by the regret of the base algorithm plus a moving cost term. By the design of Algorithm 1, it updates a univariate loss function at most once every m steps. If all the z t across these m steps are the same, Regret(Algorithm 1) will be exactly the same as m × Regret(base algorithm). When z t are different, we suffer an additional moving cost E T t=m f t (z t-m+1:t ) -ft (z t-m+1 ) , which can be bounded by the assumption on the gradient of f t if z t changes slowly.Step 3: bounding the moving cost. We partition the moving cost f t (z t-m+1:t ) -ft (z t-m+1 ) into three termsf t (z t-m+1:t ) -f t (o t-m+1:t ) (a) + f t (o t-m+1:t ) -ft (o t-m+1 ) (b) + ft (o t-m+1 ) -ft (z t-m+1 ) (c) .Here, (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 neighboring iterates.For the three terms in the above equation, (c) is bounded by Jensen's inequality using the convexity of the unary form of loss. We bound (a) using the curvature assumptions and the affine memory structure of f t , where we also make use of the delayed updates to decorrelate neighboring iterates for technical reasons. (b) is bounded by the Lipschitzness of f t and the distance between neighboring iterates. Theorem 6 is reached by putting the three steps together.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or 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 a 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 error 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. 
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 a partially observable LTI dynamical system as described in Eq. ( 1) for strongly-convex smooth loss, by a reduction to the BCO-M algorithm (Algorithm 1) we devise in the previous section. Previously, the best known regret bound for this problem was Õ(T 2/3 ) 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 a partially observable LDS is parametrized by a tuple L = (A, B, C, x 1 , (w t ) t∈N , (e t ) t∈N , (c t ) t∈N , Π), where A, B, C and (w t ) t∈N , (e t ) t∈N are the dynamics and perturbations in the LDS (Eq. ( 1)) with initial state x 1 (we assume x 1 =0 without loss of generality henceforth); c t measures the instantaneous cost at time t; Π is the comparator control policy class. Given any bandit non-stochastic control algorithm A, the regret of A NC on L over a time horizon T ∈ N is given byRegret A NC T (L, Π) = T t=1 c t (y A NC t , u A NC t ) -min π∈Π T t=1 c t (y π t , u π t ),where (yA NC t , u A NC t), (y π t , u π t ) are the observation, control pair at time t following the trajectory of A NC and π, respectively. We say that a bandit non-stochastic control problem L is (α, β, G, κ sys , κ, γ, R w,e , Y, U)-well-conditioned if L and Π satisfy Assumption 1 with α c = α, β c = β, G c = G over some centered bounded convex domain Y × U ⊂ R dy+du , Assumption 2 with κ sys , κ, γ, Assumption 3 with R w,e , and Assumption 4.The reduction from partially observable bandit non-stochastic control to BCO-M consists of two main steps. The first step is to construct the would-be signal y t (K) from the observation y t , where y t (K) is used for updating but not directly observed by the controller. y t (K) is computed by using the Markov operator of the LDS (Simchowitz et al., 2020) . The second step is a 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 (Approximation). A bandit non-stochastic control instance (Definition 7) L with some convex comparator class Π over a time horizon T ∈ N is said to be ε-approximated(ε > 0) by a BCO-M instance (Definition 5) O with domain K = Π, if the existence of a BCO-M algorithm A B implies the existence of a bandit non-stochastic control algorithm A NC satisfying E Regret A NC ,K T (L, Π) ≤ E Regret A B ,K T (O) + εT.The formal guarantee of the reduction is given below. Lemma 9 (Control reduction). Every instance of (αc , β c , G c , κ sys , κ, γ, R w,e , Y, U)-well- conditioned bandit non-stochastic control problem L over the ball Y × U ⊂ R dy+du of radius R 4 with comparator class Π = M(m, R M ) (Definition 1) is 2G f DmT -1 -approximated by a (α f , β f , G f , D)-well-conditioned BCO-M instance O with α f = α c , β f = β c , D = m max{d u , d y }R M , G f = 4096 √ mG c R 2 w,e R 2 M d 2.5 x κ 3 κ 8 sys γ 5 , provided that m = Θ(log T / log(1/(1 -γ))). 4 See Appendix B, R = Rw,e 1 + √ dxκsys γ √ 1 + κ 2 + RM 1 + √ dx(1+κ 2 )κ 2 sys γ = O(1).Lemma 9 implies that every well-conditioned bandit non-stochastic control problem can be reduced to a well-conditioned BCO-M instance, whose parameters are polynomial in those of the control problem. As a result, any regret bound for BCO-M will directly transfer to the control problem (at the expense of polynomial dependence on the system parameters). In particular, combining Theorem 6 and Lemma 9, we obtain an optimal Õ( √ T ) regret bound for the bandit non-stochastic control with strongly-convex smooth cost. Theorem 10 (Bandit non-stochastic control regret guarantee). Given an (α, β, G, κ sys , κ, γ, R w,e , Y, U)-well-conditioned bandit non-stochastic control instance L over the ball RB dy+du ⊂ R dy+du for the same R as in Lemma 9, with G, κ sys , κ, γ, R w,e , d x , d y , d u = Õ(1)5 , let (Π, K, η, m, T, G, K, α) be the input to Algorithm 2 with m = poly(log T ). Algorithm 2 guarantees thatmax z∈K E Regret Algorithm 2,z T (O) ≤ Õ β α √ T ,where Õ(•) hides all universal constants and logarithmic dependence in T .Theorem 10 strictly improves Theorem 8 of (Cassel and Koren, 2020) and Theorem 5 of (Suggala et al., 2024) , in the sense that our result achieves the optimal regret with fewer assumptions: all three results achieve the same Õ β α √ T regret bound, however (Cassel and Koren, 2020) requires the additional assumption that perturbations are stochastic, while (Suggala et al., 2024) requires the additional assumption that costs are quadratic.Algorithm 2 Improved Bandit Non-stochastic Control Input:Step size η > 0, memory parameter m, DRC policy class M(m, R M ), time horizon T , system dynamics, (κ, γ)-strongly stabilizing linear policy K, strong convexity parameter α > 0. 1: Let A B be an instance of Algorithm 1 with inputs (K = M(m, R M ), η, m, α, T ). 2: Initialize: M [j] 1 = • • • = M [j] m = 0 du×dy , ∀j ∈ [m]. g0 = • • • = gm-1 = 0 mdudy , Â0 = Âm-1 = mI mdudy×mdudy . 3: Initialize A B for t = 1, • • • , m -1 (lines 1-4 inPlay control u Mt t = Ky t + m-1 j=0 M [j]t y t-j (K), incur cost c t (y t , u t ).Let f t : (M(m, R M )) m → R be the induced with-memory loss function via reduction in Lemma 9 and H t be the associated Hessian estimator in Assumption 5.Update M t+1 ← A B (M t , {f s } t s=m , {H s } t s=m ). 10: end for 
conclusion: 
 In this paper, we devise an algorithm with an Õ( √ T ) regret bound for the bandit non-stochastic control problem with adversarial strongly-convex 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 a preliminary step to address the question of a general control theory for LTI, our result comes with limitations and potential future research directions. Currently, the improvement over the Õ(T 2/3 regret by (Cassel and Koren, 2020) is made under the additional assumption of strong convexity. It's unclear whether this assumption is necessary for an Õ( √ T ) regret, we leave determining the minimal assumption on the cost functions for optimal regret as an open question.  
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?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 as well as 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 it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines?Answer: [Yes] Justification: we carefully follow the NeurIPS 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 a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
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 is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or 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.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: the paper poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 not use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: A Proof of Theorem 6The proof is reduction-based. It consists of three parts 1. We first consider an algorithm for the no-memory BCO problem, which uses Newton-based updates and a novel delay mechanism. This algorithm will serve as the base algorithm.2. We then show that the regret of our main algorithm 1 can be bounded by the regret of the base algorithm plus a moving cost, via an improved analysis on κ 0 -convexity.3. Finally, we bound the moving cost and then put every pieces together.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 a variant of the Newton-based (improper) BCO algorithm considered in Algorithm 1 of (Suggala et al., 2024) . The main differences are:1. Algorithm 1 in (Suggala et al., 2024) constructs Hessian estimators from the bandit feedback. Algorithm 3 doesn't require Hessian estimators, since the H t determining κ 0 -convexity is given by the system instead of loss in bandit control problems, and thus it's computable by the learner given the system parameters.2. Algorithm 3 introduces an additional delay mechanism (specified by the delay parameter d 0 ∈ N) to decorrelate neighboring iterates, a necessary ingredient to later analysis.Algorithm 3 Simple BCO-with-delayInput: convex compact set K ⊂ R d , step size η > 0, delay parameter d 0 ∈ N, curvature parameter α > 0, time horizon T ∈ N.1: Initialize: o 1 ∈ K, Â0 = I d×d . Ât = 0 d×d , ∀t < 0. gt = 0, ∀t ≤ 0.2: Sample v 1 ∼ S d-1 uniformly at random. Set z 1 = o 1 + Â-1 2 0 v 1 . 3: for t = 1, . . . , T do 4:Play z t , observe ft (z t ), receive H t .Update Ât = Ât-1 + ηα 2 H t .6:Create gradient estimate:gt = d ft (z t ) Â 1 2 t-1 v t ∈ R d . 7: Update o t+1 = Ât-d 0 +1 K o t -η Â-1 t-d0+1 gt-d0+1 . 8:Sample v t+1 ∼ S d-1 uniformly at random, independent of previous steps.Set z t+1 = o t+1 + Â-1 2 t v t+1 . 10: end for Lemma 11 (Base BCO regret guarantee). Suppose that the sequence of loss functions { ft } T t=1 and the convex compact set K satisfy the conditions in Assumption 7, Assumption 8, and the properties in Observation 4, and max{1,∥H t ∥ 2 } ≤ R H , ∀t. With α = α f in the first condition in Observation 4, (η, d 0 ) satisfying d 0 ≤ 2/(ηαR H ), Algorithm 3 run with inputs (K, η, d 0 , α, T ) satisfies the following regret guarantee: ∀o ∈ K, E T t=1 ft (z t ) -ft (o) ≤ 2βd ηα log(ηR H T + 1) + 2d 0 GD + D 2 d 0 R H 2η + 3ηd 0 d 2 G 2 D 2 R H T.In particular, by choosing η = Θ(1/ √ T ) and d 0 = Θ(1), the above regret is of orderÕ β α √ T .Proof of Lemma 11. First, note that by the condition on η and d 0 , we have that Ât ⪯ 2 Ât-i , ∀i ≤ d 0 .To see this, it is equivalent to proving any PSD matrix H with λ max (H) ≤ 1 satisfies that H ⪯ I, which follows from the fact that x ⊤ (I -H)x ≥ ∥x∥ 2 2 -λ max ∥x∥ 2 2 ≥ 0, ∀x.By the convexity and curvature assumption on ft described by the conditions in Observation 4, we haveE T t=1 ft (z t ) -ft (o t ) ≤ T t=1 E[∇ ft (o t ) ⊤ Â-1 2 t-1 v t ] + β 2 T t=1 E[v ⊤ t Â-1 2 t-1 H t Â-1 2 t-1 v t ],where the first-order term equals 0 since v t is drawn independently of o t , ft , Ât-1 , and E[v t ] = 0.We can further bound the second order term byE T t=1 ft (z t ) -ft (o t ) ≤ β 2 T t=1 E[ Â-1 t-1 • H t ] ≤ 2β ηα f T t=1 E[ Â-1 t • ( Ât -Ât-1 )],where the first step follows fromE[v ⊤ Av|A] = A • E[vv ⊤] and the cyclic property of trace, and the last step follows from the definition of Ât , the stability condition that Ât ⪯ 2 Ât-1 , and α = α f . Using standard inequalities on log determinant in Newton step analysis (Hazan et al., 2007) , we haveE T t=1 ft (z t ) -ft (o t ) ≤ 2β ηα f log det( ÂT ) det( Â0 ) ≤ 2βd ηα f log ηα f R H T 2 + 1 .Moreover, the curvature assumption on ft also impliesEQUATIONwhere the second step follows from E[g t | o t ] = ∇ ft (o t ) by Stoke's theorem. By the projection step in Line 7 of Algorithm 3, we have∥o t -o∥ 2 Ât-d 0 ≤ ∥o t-1 -o -η Â-1 t-d0 gt-d0 ∥ 2 Ât-d 0 = ∥o t-1 -o∥ 2 Ât-d 0 -1 + 1 2 ∥o t-1 -o∥ 2 ηα f H t-d 0 -2ηg ⊤ t-d0 (o t-1 -o) + η 2 ∥g t-d0 ∥ 2 Â-1 t-d 0 ≤ ∥o t-1 -o∥ 2 Ât-d 0 -1 + ∥o t-d0 -o∥ 2 ηα f H t-d 0 + ∥o t-d0 -o t-1 ∥ 2 ηα f H t-d 0 -2ηg ⊤ t-d0 (o t-d0 -o) + 2ηg ⊤ t-d0 (o t-d0 -o t-1 ) + η 2 ∥g t-d0 ∥ 2 Â-1 t-d 0 ,where the last inequality follows from that ∀H ⪰ 0, ∥x + y∥ 2 H ≤ 2(∥x∥ 2 H + ∥y∥ 2 H ). Rearranging, we haveg⊤ t-d0 (o t-d0 -o) - α f 2 ∥o t-d0 -o∥ 2 H t-d 0 ≤ ∥o t-1 -o∥ 2 Ât-d 0 -1 -∥o t -o∥ 2 Ât-d 0 2η + α f 2 ∥o t-d0 -o t-1 ∥ 2 H t-d 0 + g⊤ t-d0 (o t-d0 -o t-1 ) + η 2 ∥g t-d0 ∥ 2 Â-1 t-d 0 . Note that ∀t, ∥g t ∥ 2 Â-1 t ≤ (dGD) 2 v ⊤ t Â 1 2 t-1 Â-1 t Â 1 2 t-1 v t ≤ (dGD) 2 , ∥o t -o t-1 ∥ 2 ≤ ∥o t -o t-1 ∥ Ât-d 0 ≤ η∥g t-d0 ∥ Â-1 t-d 0 ≤ ηdGD,where the second inequality in the second bound follows from the update rule in Line 7 of Algorithm 3, which gives ∥ot -o t-1 ∥ 2 Ât-d 0 ≤ ∥η Â-1 t-d0 gt-d0 ∥ 2 Ât-d 0 = η 2 ∥g t-d0 ∥ 2 Â-1 t-d 0. Thus, we can further boundα f 2 ∥o t-d0 -o t-1 ∥ 2 H t-d 0 ≤ α f R H d 0 2 d0 i=0 ∥o t-d0+i -o t-d0+i+1 ∥ 2 2 ≤ η 2 α f d 0 d 2 G 2 D 2 R H 2 , g⊤ t-d0 (o t-d0 -o t-1 ) ≤ ∥g t-d0 ∥ Â-1 t-d 0 ∥o t-d0 -o t-1 ∥ Ât-d 0 ≤ 2ηd 0 d 2 G 2 D 2 .Combining both and using that Ât ⪯ 2 Ât-i , ∀i ≤ d 0 , we have thatT -d0 t=d0 g⊤ t (o t -o) - α f 2 ∥o t -o∥ 2 Ht = T t=2d0 g⊤ t-d0 (o t-d0 -o) - α f 2 ∥o t-d0 -o∥ 2 H t-d 0 ≤ 1 2η ∥o 2d0-1 -o∥ 2 Âd 0 -1 + ηT α f d 0 d 2 G 2 D 2 R H 2 + 2d 0 d 2 G 2 D 2 + d 2 G 2 D 2 2 ≤ D 2 d 0 R H 2η + 3ηd 0 d 2 G 2 D 2 R H T.As a result,E T t=1 ft (o t ) -ft (o) ≤ 2d 0 GD + D 2 d 0 R H 2η + 3ηd 0 d 2 G 2 D 2 R H T.Combining, we haveE T t=1 ft (z t ) -ft (o) ≤ 2βd ηα log(ηR H T + 1) + 2d 0 GD + D 2 d 0 R H 2η + 3ηd 0 d 2 G 2 D 2 R H T.In this section, we prove Lemma 12, which states that the regret of BCO-M algorithm (Algorithm 1) can be related to the regret guarantee of the base no-memory BCO algorithm (Algorithm 3).We follow the proof idea of (Cassel and Koren, 2020) . In the previous section we have proved an Õ( √ T ) regret bound for a "no-memory" base BCO algorithm. Our main Algorithm 1, however, has memory dependence. When z t is changing slowly, Algorithm 1 is approximately a "no-memory" algorithm, and we can do the following reduction: if all the z t across these steps are the same, Regret(Algorithm 1) will be exactly the same as m × Regret(base algorithm).In this part, we show that when z t are different, we only suffer an additional moving cost E T t=m f t (z t-m+1:t ) -ft (z t-m+1 ) , which we will bound in Appendix A.3. Lemma 12 (Lemma 11, (Cassel and Koren, 2020) ). Let (K, η, m, T ) be the input for Algorithm 1. Suppose that the loss functions {f t } T t=m and the convex compact set K satisfy Assumption 5, Assumption 6, Assumption 7, and Assumption 8. Then, the regret of Algorithm 1 with respect to any o ∈ K is upper bounded byE T t=m f t (z t-m+1:t ) -ft (o) ≤ 3m • R Algorithm 3 T m + E T t=m f t (z t-m+1:t ) -ft (z t-m+1 ) ,where R Algorithm 3 4). The algorithm updates during round t if t ∈ S. For any t ∈ S, we have that χ t-1 = • • • = χ t-m+1 = 0. Therefore, we have z t-m+1 = • • • = z t by design of Algorithm 1. Thus, we have that f t (z t-m+1:t ) = ft (z t-m+1 ) = ft (z t ). Therefore, constrained to the time steps t ∈ S, Algorithm 1 is essentially running Algorithm 3 with a delay parameter d 0 = 2 (since in Line 12 of Algorithm 1, we update with the gradient information at time s τ -1 during round t). Note that since |S| ≤ T m (Algorithm 1 updates at most once every m steps), we have that ∀o ∈ K,E b 1:T ,{vt} t∈S t∈S ft (z t ) - t∈S ft (o) ≤ E b 1:T [R Algorithm 3 (|S|)] ≤ R Algorithm 3 T m .It is left to relate the quantity on the left hand side of the above expression to the regret of Algorithm 1. Since χ t D = χ m (the two random variables equal in distribution), ∀t, we haveEQUATION)For t ∈ N, denote F t to be the σ-algebra generated by the randomness of Algorithm 1 through sampling b s , v s up to time t, i.e. F t = σ({b s , v s } t s=1 ). Since z t = z t-m+1 whenever χ t = 1, b t-m+1:t are drawn independently of z t-m+1 and χ t is independent of F t-m by definition of χ t , we haveEQUATIONTogether, Eq. ( 7) and Eq. ( 8) give thatE b 1:T ,{vt} t∈S t∈S ft (z t ) - t∈S ft (o) = E[χ m ] • E T t=m ft (z t-m+1 ) -ft (o) ≤ E[χ m ] • R Algorithm 3 T m .Therefore, we have thatE T t=m f t (z t-m+1:t ) -ft (o) = E T t=m ft (z t-m+1 ) -ft (o) + E T t=m f t (z t-m+1:t ) -ft (z t-m+1 ) ≤ (E[χ m ]) -1 R Algorithm 3 T m + E T t=m f t (z t-m+1:t ) -ft (z t-m+1 ) ≤ 3m • R Algorithm 3 T m + E T t=m f t (z t-m+1:t ) -ft (z t-m+1 ) ,where the last inequality follows fromE[χ m ] = E[b m ] m-1 i=1 E[1 -b i ] = 1 m 1 - 1 m m-1 ≥ 1 em > 1 3m .Lemma 11 and Lemma 12 almost give the regret guarantee in Theorem 6. We are left with bounding the moving cost term in Lemma 12E T t=m f t (z t-m+1:t ) -ft (z t-m+1 ) .(Cassel and Koren, 2020) bounded each of the summands by E[δ t + ν t ], where δ t = ∥o t+1 -o t ∥ 2 , and ν t = ∥z t -o t ∥ 2 . Making use of the κ 0 -convexity induced by the affine memory structure of non-stochastic control problems, we can establish a tighter bound that is necessary to obtain optimal regret in Theorem 6. Lemma 13 (Moving cost). Let (K, η, m, T ) be the input for Algorithm 1. Suppose that the loss functions {f t } T t=m and the convex compact set K satisfy Assumption 5, Assumption 6, Assumption 7, and Assumption 8. Suppose m ≤ 2/(ηαR H ). Then, the iterates output by Algorithm 1 satisfyE T t=m f t (z t-m+1:t ) -ft (z t-m+1 ) ≤ 12m 4 βR H d • max{2, ηαR H √ T } ηακ(G) log(ηαR H + 1) + 10m 4 βR 3 H d √ T κ(G) + m 2 βdR 3 H √ T + ηdGD 2 βT.In particular, with η = Θ( √ T ), m = poly(log T ) and κ(G) = Ω(1) by Assumption 5, we have that the above bound is of order Õ( √ T ).Proof of Lemma 13. We can decompose the moving cost into three terms:E T t=m f t (z t-m+1:t ) -f t (o t-m+1:t ) (a) + E T t=m f t (o t-m+1:t ) -ft (o t-m+1 ) (b) + E T t=m ft (o t-m+1 ) -ft (z t-m+1 ) (c), and we will bound each of the terms separately. In 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 neighboring iterates. We start with establishing bounds on (a), (c).Perturbation loss. As before, we denoteF t = σ({b s , v s } t s=1) to be the σ-algebra generated by the randomness of Algorithm 1 through sampling b s , v s up to time t. First, (c) ≤ 0 by Jensen's inequality for conditional expectations. In particular, recall that χ t = b t Π m-1 i=1 (1 -b t-i ) denotes whether the decision is updated at time t. For every t ∈ N, denote as T (t) := max{s < t | χ s = 1} the last time that the algorithm updates its decision. It naturally holds that o t = o T (t)+1 , v t = v T (t)+1 by design of Algorithm 1. Therefore, we haveE[ ft (o t-m+1 ) -ft (z t-m+1 )] = E[ ft (o T (t-m+1)+1 ) -ft (z T (t-m+1)+1 )] = E[ ft (o T (t-m+1)+1 ) -ft (o T (t-m+1) + Â-1 2 t-m v T (t-m+1)+1 )]. By the sampling rule in Line 13 of Algorithm 1, if the algorithm updates its decision at time t (χ t = 1), then v t+1 is independent drawn from previous steps. On the other hand, o t+1 is measurable w.r.t. F t . Therefore, we have by Jensen's inequality for conditional expectations thatE[ ft (o T (t-m+1)+1 ) -ft (o T (t-m+1)+1 + Â-1 2 t-m v T (t-m+1)+1 )] = E[ ft (o T (t-m+1)+1 ) -E[ ft (o T (t-m+1)+1 + Â-1 2 t-m v T (t-m+1)+1 ) | F T (t-m+1) ]] ≤ E[ ft (o T (t-m+1)+1 ) -ft (E[o T (t-m+1)+1 + Â-1 2 t-m v T (t-m+1)+1 | F T (t-m+1) ])] = E[ ft (o T (t-m+1) ) -ft (o T (t-m+1) )] = 0.Summing up over t, we get that (c) ≤ 0. We move on to bound (a). We start with a (conditional) independence argument.Independence argument. Fix t. Denote t 1 = T (t) to be the most recent time when the algorithm makes an update. Additionally, denote t 2 = T (T (t)) to be the second most recent time when the algorithm makes an update. We already have o t = o t1+1 . By the delayed update rule in Line 12 of Algorithm 1, we have that o t1+1 is updated with o t1 = o t2+1 and gradient information gt2 and thus is F t2 -measurable. On the other hand, consider the sequence of random vectors v t-m+1 , . . . , v t . We have that v s = v T (s)+1 for every t -m + 1 ≤ s ≤ t. Since the algorithm updates at most once every m steps, we have that T (s) ≥ t 2 for all t -m + 1 ≤ s ≤ t. Therefore, v t-m+1 , . . . , v t is independent of F t2 . This observation de-correlates o t with v t-m+1 , . . . , v t conditioning on F t2 .For notation simplicity, for matrices A 1 , . . . , A n ∈ R d×d and vectors v 1 , . . . , v n ∈ R d , we slightly abuse notation and denote as A 1:n v 1:n = (A 1 v 1 , . . . , A n v n ) ∈ R nd to be the concatenated matrixvector product of the two sequences.We apply Taylor's theorem to the function f t and obtain that(a) = T t=m E ∇f t (o t-m+1:t ) ⊤ Â-1 2 t-m:t-1 v t-m+1:t + 1 2 v ⊤ t-m+1:t Â-1 2 t-m:t-1 ∇ 2 f t (q t-m+1:t ) Â-1 2 t-m:t-1 v t-m+1:t ,where q t-m+1:t is some point that lies on the line segment connecting o t-m+1:t and z t-m+1:t . By the conditional independence argument, we have that the first order term vanishes: let t 2 = T (T (t)),E ∇f t (o t-m+1:t ) ⊤ Â-1 2 t-m:t-1 v t-m+1:t = E E ∇f t (o t-m+1:t ) ⊤ Â-1 2 t-m:t-1 v t-m+1:t | F t2 = E ∇f t (o t-m+1:t ) ⊤ Â-1 2 t-m:t-1 E [v t-m+1:t | F t2 ]= 0. The above sum thus reduces to the sum of second-order terms:1 2 T t=m E v ⊤ t-m+1:t Â-1 2 t-m:t-1 ∇ 2 f t (q t-m+1:t ) Â-1 2 t-m:t-1 v t-m+1:t ≤ 1 2 T t=m E ( Â-1 2 t-m v t-m+1 , . . . , Â-1 2 t-m v t ) ⊤ ∇ 2 f t (q t-m+1:t )( Â-1 2 t-m v t-m+1 , . . . , Â-1 2 t-m v t ) , ≤ 1 2 T t=m E    max u∈R dm :∥u∥ 2 2 =m u ⊤    Â-1 2 t-m 0 . . . 0 0 Â-1 2 t-m . . . 0 0 0 . . . Â-1 2 t-m    ∇ 2 f t (q t-m+1:t )    Â-1 2 t-m 0 . . . 0 Â-1 2 t-m . . . 0 0 . . . Â- t-m    u    , ≤ m 2 2 T t=m E   ∇ 2 f t (q t-m+1:t ) •   Â-1 t-m 0 . . . 0 0 Â-1 t-m . . . 0 0 0 . . . Â-1 t-m     , = m 2 2 T t=m E Â-1 t-m • m i=1 [∇ 2 f t (q t-m+1:t )] ii ,where the first inequality follows from Âs ⪯ Ât for all s < t; the second inequality follows from taking maximum over all concatenated unit vectors in R d ; the third inequality follows from the inequality between trace and spectral norm.From this point on, the bound follows almost identically to the proof of Proposition 21 in (Suggala et al., 2024) . We will reiterate the proof in 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 f t evaluated at q t-m+1:t as the following:∇ 2 f t (q t-m+1:t ) =   W ⊤ t-m+1 ∇ 2 ℓ t (q)W t-m+1 . . . W ⊤ t-m+1 ∇ 2 ℓ t (q)W t . . . . . . . . . W ⊤ t ∇ 2 ℓ t (q)W t-m+1 . . . W ⊤ t ∇ 2 ℓ t (q)W t   , where q = B t + m-1 i=0 G [i] Y t-i q t-i , and W t-m+i = G [m-i] Y t-m+i , ∀1 ≤ i ≤ m.By the curvature assumption on ℓ t (Assumption 6), we can further bound the sum of diagonal blocks bym i=1 [∇ 2 f t (q t-m+1:t )] ii ⪯ β m i=1 W ⊤ t-m+i W t-m+i = β m i=1 Y ⊤ t-m+i (G [m-i] ) ⊤ G [m-i] Y t-m+i ⪯ βR H m i=1 Y ⊤ t-m+i Y t-m+i .Therefore, we can further boundm 2 2 T t=m E Â-1 t-m • m i=1 [∇ 2 f t (q t-m+1:t )] ii ≤ m 2 βR H 2 T t=m E Â-1 t-m • t s=t-m+1 Y ⊤ s Y s ≤ m 2 βR H T t=m E Â-1 t • t s=t-m+1 Y ⊤ s Y s .Consider γ = ⌊ √ T ⌋ and endpoints k j = γ(j -1) + m for j = 1, . . . , J, and J = ⌊ T -m γ ⌋. Using the fact that Trace(AC) ≤ Trace(BC) for any PSD matrices A, B, C with A ⪯ B, we can further decompose and bound the sum in the above expression bym 2 βR H T t=m Â-1 t • t s=t-m+1 Y ⊤ s Y s ≤ m 2 βR H J j=1 Â-1 kj •   kj+1-1 t=kj t s=t-m+1 Y ⊤ s Y s   + m 2 βγdR 3 H ≤ m 3 βR H J j=1 Â-1 kj •   kj+1-1 t=kj -m+1 Y ⊤ t Y t   + m 2 βγdR 3 H ≤ 2m 3 βR H κ(G) J j=1 Â-1 kj •   5mR 2 H I + kj+1-1 t=kj H t   + m 2 βγdR 3 H = 2m 3 βR H κ(G) J j=1 Â-1 kj •   kj+1-1 t=kj H t   + 10m 4 βR 3 H d √ T κ(G) + m 2 βdR 3 H √ T .where the first inequality follows by applying the radius bounds on Y t for the last T -Jγ terms and using the fact that Âs ⪯ Ât for any s < t; the last inequality follows by applying Proposition 4.8 in (Simchowitz, 2020) . Therefore, it suffices to bound the sum in the first term in expectation. First, recall that ∀t, χ t = b t Π m-1 i=1 (1 -b i ) denotes whether Algorithm 1 updates during round t, and S = {m ≤ t ≤ T : χ t = 1} denotes the set of all rounds where Algorithm 1 updates. To bound the following, we make use of the facts that (1) H t is oblivious, and (2) χ t is independent of Â-1 k for any k ≤ t -m. Then, we have thatE   J j=1 t∈[kj ,kj+1-1]∩S Â-1 kj -m • H t   = E   J j=1 kj+1-1 t=kj Â-1 kj -m • H t • χ t   = J j=1 kj+1-1 t=kj E[ Â-1 kj -m • H t ] • E[χ t ] = E[χ m ] • E   J j=1 kj+1-1 t=kj Â-1 kj -m • H t   ≥ E[χ m ] • E   J j=1 kj+1-1 t=kj Â-1 kj • H t   .Using this and that Ât ⪯ 2 Ât-m , we have thatE   J j=1 kj+1-1 t=kj Â-1 kj • H t   ≤ 2E[χ m ] -1 E   J j=1 t∈[kj ,kj+1-1]∩S Â-1 kj • H t   = 6m ηα • E   J j=1 Â-1 kj • ( Âkj+1-1 -Âkj-1 )   ≤ 6m • max{2, ηαR H γ} ηα • E   J j=1 Â-1 kj+1-1 • ( Âkj+1-1 -Âkj-1 )   ≤ 6m • max{2, ηαR H γ} ηα • E   J j=1 log det( Âkj+1-1 ) det( Âkj-1 )   ≤ 6m • max{2, ηαR H γ} ηα • E[log det( ÂT )] ≤ 6dm • max{2, ηαR H γ} ηα log(ηαR H + 1),where the first inequality follows from Âkj+1-1 ⪯ max{2, ηαR H γ} Âkj , and rest follows from the standard inequalities used in Newton-step analysis (Hazan et al., 2007) .Combining all the bounds, we have that(a) ≤ 12m 4 βR H d • max{2, ηαR H √ T } ηακ(G) log(ηαR H + 1) + 10m 4 βR 3 H d √ T κ(G) + m 2 βdR 3 H √ T .Movement cost. By design, the algorithm updates at most once in every m iterations. Therefore,∥(o t-m+1 , . . . , o t ) -(o t-m+1 , . . . , o t-m+1 )∥ 2 ≤ s,where s is the Euclidean distance between neighboring iterates in Algorithm 3. By analysis in Lemma 11, we have s ≤ ηdGD. By Lipschitz assumption on f t , we have(b) ≤ ηdGD 2 βT.Combining, we have that the total moving cost is bounded byE T t=m f t (z t-m+1:t ) -ft (z t-m+1 ) ≤ 12m 4 βR H d • max{2, ηαR H √ T } ηακ(G) log(ηαR H + 1) + 10m 4 βR 3 H d √ T κ(G) + m 2 βdR 3 H √ T + ηdGD 2 βT.Combining result from Lemma 11, Lemma 12, and Lemma 13, we have the regret of Algorithm 1 w.r.t. to any z ∈ K is bounded byE[Regret T (z)] ≤ 3m 2βd ηα log(ηR H T + 1) + 2d 0 (GD) + D 2 d 0 R H 2η + 3ηd 0 d 2 (GD) 2 R H T + 12m 4 βR H d • max{2, ηαR H √ T } ηακ(G) log(ηR H T + 1) + 10m 4 βR 3 H d √ T κ(G) + m 2 βdR 3 H √ T + ηdGβD 2 T,and by choosing η = Θ 1 α √ T , we have the regret above is bounded by Õ β α GD √ T .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 dynamics A ∈ R dx×dx , B ∈ R dx×du , C ∈ R dy×dx satisfying Assumption 2 with (κ, γ)-strongly stabilizing K, define the Markov operator to be a sequence of matrices G = {G [i] } i≥0 such that G 0 = [0; I du ] and ∀i > 0, G [i] is given byG [i] = C KC (A + BKC) i-1 B ∈ R (dy+du)×du .The next observation (Observation 15) relates y t (K), the signals used by the DRC policies (Definition 1), to the observations and controls along the learner's trajectory. This justifies the accessibility of the signals.Observation 15. Given a partially observable LDS instance with (κ, γ)-strongly stabilizing K, let G be the Markov operator in Definition 14. For t, m ∈ N, let M 1 , . . . , M t-1 ∈ R m×du×dy be (t -1) DRC matrices (Definition 1). Let (y t , u t ) be the observation-control pair reached by playing M 1 , . . . , M t-1 for time step t = 1, . . . , t -1. Let u t (K) be the control at time t by executing the linear policy K, i.e. y t (K) = Ku t (K), and y t (K) be the would-be observation had K been executed from the beginning of the time. Then, (y t , u t ) and (y t (K), u t (K)) can be related by the following equality:EQUATIONIn particular, Eq. ( 9) implies that y t (K) can be computed by the learner through access to the Markov operator G and the observations along the learner's own trajectory.With Eq. ( 9), we are almost ready to reduce the control instance to the BCO-M problem. One delicate detail is that the BCO-M problem is defined for vector-valued decisions, and the the space M(m, R M ) is a space of sequences of matrices. For clarity of presentation, we define the following embedding operators. Definition 16 (Embedding operators). For m, d y , d u ∈ N, denote d = md y d u . The embedding operator e : (R (du×dy) ) m → R d is the natural embedding of a DRC controller M = M [0:m-1] (Definition 1) in R d . In particular, ∀k ∈ [m -1], i ∈ [d u ], j ∈ [d y ], ⟨e kdudy+(i-1)dy+j , e(M )⟩ = M [k] ij .Let e y : (R dy ) m → R du×d be given by ∀y t-m+1 , . . . ,y t ∈ R dy , ∀i ∈ [d u ], k ∈ [m], [e y (y t-m+1:t )] i,j+1:j+dy = y t-k+1 , if j = (k -1)d u d y + (i -1)d y . Proof of Lemma 9. Let B t = (y t (K), Ky t (K)) + t i=m G [i] Y t-i e(M t-i ) ∈ R du+dy , ∀t. Let Y t = e y (y t-m+1:t (K)).Then, by Eq. ( 9), we havec t (y t , u t ) = c t B t + m-1 i=0 G [i] Y t-i e(M t-i ) .We can't directly define our f t as this function because the t i=m G [i] Y t-i e(M t-i ) term in B t depends on historical steps, which will lead to an unbounded memory.To this end, we defineEQUATIONwhich is independent of M t-m+1:t , and Y t is independent of M 1:T . Note that by the loss function with memory has an affine memory structure. Moreover, G [i] and Y t-i are computable by the learner given system parameters. By the choice of m = Θ(log T ), the Lipschitzness of c t , and the norm-decaying property of G [i] due to the stability of the system, we can bound the distance|c t (y t , u t ) -f t (e(M t-m+1 ), . . . , e(M t ))| = O 1 poly(T ).In particular, we can choose m such that this term is O 1 T 2 , then any regret bound on f t in the BCO-M setting directly transfers to the same regret bound on c t in the control setting, at a negligible o(1) cost which will be subsumed by the approximation error term.We are left with two steps to conclude this lemma. First, we need to show that f t indeed satisfies the conditions in Definition 5 and specify the constants. Next, because f t is not equal to c t while we only have access to c t , the gradient estimator for f t constructed from c t 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 ft as in Definition 2 .Let O = {M(m, R M ), m, {f t } t≥m,t∈N } be the associated BCO-M instance (Definition 5).By construction, f t satisfies Assumption 8 and Assumption 5 other than the assumption on positive convolution invertibility-modulus if the truncated vector (y t (K),Ky t (K))+ m-1 i=0 G [i] Y t-i e(M t-i )always lives in the RB dy+du and the matrix parameters are bounded. For the positive convolution invertibility-modulus, Lemma 3.1 in (Simchowitz, 2020) proves that the G [0] , . . . , G [m-1] induced by the Markov operator in Definition 14 satisfies the positive convolution invertibility-modulus, i.e. κ(G) = Ω(1). By assumption on c t , the curvature assumption in Assumption 6 is also satisfied. It is left to check the diameter bounds in Assumption 5 and Assumption 7.First, we establish a diameter bound on our learning comparator set K = M(m, R M ).K = M(m, R M ). The diameter of the set M(m, R M ) is given by max M1,M2∈M(m,R M ) ∥e(M 1 ) -e(M 2 )∥ 2 ≤ √ m max M1,M2∈M(m,R M ) max 0≤j≤m-1 ∥M [j] 1 -M [j] 2 ∥ F ≤ m max{d u , d y } max M1,M2∈M(m,R M ) max 0≤j≤m-1 ∥M [j] 1 -M [j] 2 ∥ op ≤ m max{d u , d y }R M .Algorithm 2 essentially calls the improper BCO-M algorithm in Algorithm 1. With the diameter bound on M(m, R M ), we know that the matrices governing the controls picked by Algorithm 2 during each round lives in the set M(m, R M + m). For simplicity, we may assume that R M ≥ m and thus the decisions made by Algorithm 2 live in M(m, 2R M ).Now, we are ready to prove the gradient bound on f t and the bounds on the observation-control pairs produced by Algorithm 2.Gradient bound of f t . First, we bound the sum of operator norms for the Markov operator. By Assumption 2 and the fact that∀M ∈ R n×n , ∥M ∥ op ≤ √ n∥M ∥ max ≤ √ n∥M ∥ 2 , we have that ∞ i=0 ∥G [i] ∥ op ≤ 1 + ∞ i=1 ∥C(A + BKC) i-1 B∥ 2 op + ∥KC(A + BKC) i-1 B∥ 2 op ≤ 1 + d x (1 + κ 2 )κ 2 sys ∞ i=1 ∥HL i-1 H -1 ∥ 2 ≤ 1 + d x (1 + κ 2 )κ 2 sys ∞ i=0 (1 -γ) i = 1 + d x (1 + κ 2 )κ 2 sys γ .The signals y t (K) has the following norm bound:max t∈[T ] ∥y t (K)∥ 2 = max t∈[T ] C t-1 i=0 (A + BKC) i w t-i + e t 2 ≤ R w,e 1 + d x κ sys ∞ i=1 ∥HL i-1 H -1 ∥ 2 ≤ R w,e 1 + √ d x κ sys γ .By the unfolding of (y t , u t ) in Eq. ( 9), the observation and control pair (y t , u t ) has the following norm bound: ∀t,∥(y t , u t )∥ 2 ≤ ∥(y t (K), Ky t (K))∥ 2 + t i=1 G [i]   m-1 j=0 M [j] t-i y t-i-j (K)   2 ≤ R w,e 1 + √ d x κ sys γ   1 + κ 2 + 2R M ∞ i=0 G [i] op   ≤ R w,e 1 + √ d x κ sys γ 1 + κ 2 + 2R M 1 + d x (1 + κ 2 )κ 2 sys γ =: R.The above bound holds similarly for the truncated (ŷ t , ût ) := (y t (K), 10), which shows that (ŷ t , ût ) ∈ RB dy+du . This also completes checking Assumption 5.Ky t (K)) + m-1 i=0 G [i] Y t-i e(M t-i ) in Eq. (By assumption, c t obeys the Lipschitz bounds∥∇c t (y, u)∥ 2 ≤ G c ∥(y, u)∥ 2 .The gradient bound on f t is given by ∥∇f t (e(M t-m+1 ), . . . , e(M t ))∥ 2= ((G [m-1] Y t-m+1 ) ⊤ ∇c t (ŷ t , ût ), . . . , (G [0] Y t ) ⊤ ∇c t (ŷ t , ût ) 2 ≤ √ m 1 + d x (1 + κ 2 )κ 2 sys γ G c R 2 w,e 1 + √ d x κ sys γ 2 1 + κ 2 + 2R M 1 + d x (1 + κ 2 )κ 2 sys γ 2 ≤ 4096 √ mG c R 2 w,e R 2 M d 2.5 x κ 3 κ 8 sys γ 5 .Step 2: Clearly the gradient estimator obtained for f t is biased. We denote this error as a t which has a norm bound ∥a t ∥ 2 = O( 1 T ) with the same reasoning on bounding |c t -f t |. Now, we only need to show that Algorithm 1 can tolerate such perturbation with no loss in regret.It's known that the OGD algorithm can tolerate per-round adaptive gradient perturbation with norm bounded by O( 1T ), with no cost in regret. We will prove a similar argument for Algorithm 3. Suppose in line 6, the unbiased gradient estimator gt is replaced by a biased estimator ĝt = gt + a t , then we want to extend the regret bound for Algorithm 3 in Lemma 11 in this setting with an additional term depending on the sum of magnitude of a t . The analysis in the proof of Lemma 11 remains unchanged except when we bound the regret for the sequence {o t } T t=1 in Eq. ( 6), the inequality becomesE T t=1 ft (o t ) -ft (o) ≤ T t=1 E[∇ ft (o t ) ⊤ (o t -o)] - α f 2 T t=1 E[∥o t -o∥ 2 Ht ] = T t=1 E[ĝ ⊤ t (o t -o)] - T t=1 E[a ⊤ t (o t -o)] - α f 2 T t=1 E[∥o t -o∥ 2 Ht ].The rest of proof after Eq. ( 6) is indentical, except that we replace each appearance of gt by ĝt .Therefore, the regret incurred by using ĝt instead of gt as the gradient estimator is bounded by the regret upper bound in Lemma 11 and the additional termT t=1 E[a ⊤ t (o t -o)] ≤ aDT , where a = max t∈[T ] ∥a t ∥ 2 . Since a = O( 1 T ), the additional regret is bounded by O(1).Concluding the lemma: Denoteα f = α c , β f = β c , D = m max{d u , d y }R M , G f = 4096 √ mG c R 2 w,e R 2 M d 2.5 x κ 3 κ 8 sys γ 5 .We have that by Assumption 4 that where we haveE Regret A NC T (L) = max M ∈M(m,R M ) E T t=1 c t (y t (M 1:t-1 ), u t (M 1:t-1 )) -c t (y t (M ), u t (M )) ≤ G f Dm + E T t=m f t (e(M t-m+1 ), . . . , e(M t )) -ft (e(M )) + E T t=m ft (e(M )) -c t (y t (M ), u t (M )) = E T t=m c t B t + m-1 i=0 G [i] Y t-i e(M )) -c t (y t (K), Ky t (K)) + t i=0 G [i] Y t-i e(M )c t B t + m-1 i=0 G [i] Y t-i e(M )) -c t (y t (K), Ky t (K)) + t i=0 G [i] Y t-i e(M ) ≤ G c t i=m G [i] Y t-i e(M ) 2 ≤ G c t i=m ∥G [i] ∥ op ∥Y t-i ∥ F ∥M ∥ F .Recall that∥M ∥ 2 F = m-1 j=0 ∥M [j] ∥ 2 F ≤ max{d u , d y } m-1 j=0 ∥M [j] ∥ 2 op ≤ m max{d u , d y }R 2 M , max t∈[T ] ∥Y t ∥ 2 = md y d 2 u • max t∈[T ] ∥y t (K)∥ 2 ≤ md y d 2 u • R w,e 1 + √ d x κ sys γ , ∞ i=m ∥G [i] ∥ op ≤ d x (1 + κ 2 )κ 2 sys ∞ i=m (1 -γ) i ≤ d x (1 + κ 2 )κ 2 sys (1 -γ) m γ .We have for m = Θ (logT / log(1/(1 -γ))), G c t i=m ∥G [i] ∥ op ∥Y t-i ∥ F ∥M ∥ F ≤ 4G c md y d 2 u d x (1 + κ 2 )κ 4 sys R M (1 -γ) m γ 2 ≤ G c md y d 2 u d x κ 2 κ 4 sys R M γ 2 T .Combining, we haveE Regret A NC T (L) ≤ E Regret A B T (O) + G c md y d 2 u d x κ 2 κ 4 sys R M γ 2 + G f Dm ≤ E Regret A B T (O) + 2G f Dm, which concludes the claim that O 2G f DmT -1 -approximates L.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: we 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 as long as it is clear that these goals are not attained by the paper.In fact, the lower bound proved in(Suggala et al.,2024) even holds for quadratic loss functions.Here we could write G[i] Yt-i with a single parameter, but the current form matches that of control.Any α strongly convex function is also min(1, α) strongly convex and similar for β.The assumption that the system parameters are of order Õ(1) is consistent with prior works(Hazan and Singh, 2022). 


Decision: 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.

Reviews: review: paper_summary: paper_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].

The 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.
strength_weakness: strength_weakness: 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.  
2. 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. 

Typo:
1. line 248, length to lengthy. 
2. Definition 3, $f_t$ should be $f$? 

Other than these two issues, I haven't observed any specific weaknesses in this work.
questions: questions: The questions are raised in the weakness section. I am willing to re-evaluate the scores if these questions are properly answered.
limitations: limitations: This paper is pure theoretical and does not have any limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: 1. The citation for Optimal rates for bandit non-stochastic control is incorrect; it was mistakenly written as NeurIPS 2024.

2.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.
questions: questions: No questions.
limitations: limitations: See weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.


[1] Cassel, A. and Koren, T. (2020). Bandit linear control. Advances in Neural Information Processing Systems, 33:8872–8882.

[2] Suggala, A., Sun, Y. J., Netrapalli, P., and Hazan, E. (2024). Second order methods for bandit
optimization and control. arXiv preprint arXiv:2402.08929.
questions: questions: What is the main techinical challenge when combining and adapting the proof in [1] and [2]?
limitations: limitations: Yes.

Comments: comment: Thank the authors for their response. My questions are well-addressed ,and I would like to increase my score.
I thank the authors for the response. I do not have further questions now and will keep my score.