Linear Quadratic Regulator (LQR) and Linear Quadratic Gaussian (LQG) control are foundational and extensively researched problems in optimal control. We investigate LQR and LQG problems with semi-adversarial perturbations and time-varying adversarial bandit loss functions. The best-known sublinear regret algorithm of \cite{gradu2020non} has a $T^{\frac{3}{4}}$ time horizon dependence, and its authors posed an open question about whether a tight rate of $\sqrt{T}$ could be achieved. We answer in the affirmative, giving an algorithm for bandit LQR and LQG which attains optimal regret (up to logarithmic factors) for both known and unknown systems. A central component of our method is a new scheme for bandit convex optimization with memory, which is of independent interest.
Paper
Similar papers
Peer review
Summary
The authors present an algorithm fro the LQG problem, in which a linear system has to be controlled in the presence of semi-adversarial perturbations in order to minimise an adversarially-chosen cost, with the controller only having access to a projection of the real dynamics onto a lower-dimensionality subspace. The authors show that their proposed method achieves optimal regret in time horizon of $O(\sqrt{T})$.
Strengths
The paper's introduction of the problem is quite readable to a non-specialist, though specialist knowledge is required to understand most of the details and the theorem proof.
Weaknesses
The paper is extremely theoretical and deals with a very specialised problem. This problem has connections with more mainstream AI problems (Optimal Control and Reinforcement Learning are closely related), and the paper does present it in a way that makes it understandable to a non-specialist reader. Still, the paper does not present any task-oriented AI-based framework involving the training of a Neural Net. While this might not be enough to disqualify the paper from publication at NeurIPS, it does severely restrict the number of potential readers.
Questions
My understanding of the paper is too limited to provide any meaningful suggestions for improvement.
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
1: Your assessment is an educated guess. The submission is not in your area or the submission was difficult to understand. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
The paper is extremely theoretical and can only be understood by a very specialised audience. The relevance of the author's solution for the presented problem (or even of the problem itself) to more mainstream AI research, if any, is not at all discussed. Edit: In their rebuttal, the authors challenged my assessment of their work's limitations by pointing out a connection between nonstochastic control and hyperparameter tuning in large-scale optimization, which was remarked in “A Nonstochastic Control Approach to Optimization” by Chen & Hazan (2023). While the connection is definitely present and fascinating, I still felt that it was not enough of an established research track for me to change my assessment. I therefore kept my initial score.
Summary
This paper studies LQG with semi-adversarial perturbations and time varying adversarial bandit loss functions. The best known bound for such problems has a T^{3/4} time horizon dependence. They provide an algorithm for LQR/LQG problems that attains $\tilde{\mathcal{O}}(\sqrt{T})$ regret. Their algorithm goes through even if the underlying system dynamics are unknown. Additionally, their method also provides a new scheme for bandit convex optimization with memory.
Strengths
This paper addresses an important problem in the field of control and online learning.
Weaknesses
I must express my concerns about its presentation and structure. The writing is not as clear as it needs to be, making it quite challenging to follow the paper. The argument seems to lack the rigorousness and the self-containment. A crucial element that seems to be missing is detailed explanations for the conclusions drawn. Without these, it becomes arduous to justify the results. Enhancing the clarity and providing in-depth explanations of the methodologies and results will significantly improve the comprehension and overall impact of the study. I list my comments, questions and suggestions below.
Questions
## Major comments: 1) Can you elaborate more on the DRC policy class? To me it seems like you are concentrating on the causal (non-anticipatory) policies that are linear. Is it possible to show that a linear policy will be optimal for your setting because you are concentrating on the quadratic cost function? I believe that would require to show that the estimation of the state given observations would be linear in observations as in the classical LQG setting. 2) I think nature's y seems like the purified the purified output control method in [R1]. Is that true? If yes can you please provide the relevant reference there? 3) I find it very confusing that $y$ suddenly becomes a decision variable in Section 3.1 while it represents the observations of the state in the previous chapter and also in the subsequent section. This is truly confusing if I did not miss something. Following that I do not understand why $u$ is the noise in Assumption 3.3. 4) What does $A_t$ represent in Algorithm 1? It seems completely irrelevant to the state transition matrix $A$ to me. Why do you choose the same letter? I find this very confusing. 5) Where is the proof of Theorem 3.7? 6) Line 529, I do not understand why $x_1, \ldots, x_{2\bar H +1} = argmin_{x \in \mathcal K} R(x)$ because it seems to me $x_1, \ldots x_{H } = argmin_{x \in \mathcal K} R(x)$ but $x_{H+1}, \ldots, x_{2 \bar H + 1} = argmin_{x \in \mathcal K} \sum_{s= H}^t \frac{\sigma}{2} \| x - x_{s- \bar H}\|^2) + \eta^{-1} R(x)$. What am I missing here? 7) Can you comment on if it is possible to remove the logarithmic term even from the regret or is it fundamentally not possible? (in Theorem 4.1 and Theorem 4.2) 8) Why this rate is optimal? $\sqrt{T}$ regret rate would be optimal as it is tight. By not $\tilde{\mathcal{O}}(\sqrt(T))$. Can you please elaborate on that. ## Minor comments: 1) Typo in Page 4, Line 136: Time step instead of timestep. 2) Please provide references for every claim that is mentioned in the paper without a proof. For example, in Page 4, Line 145, I suggest to provide examples of the papers that make us of the system's counterfactual signal. Same goes for Page 5, Line 159. Another example is in Page 5, Line 181. The sentence there reads "These conditions are relatively standard for bandit convex optimization algorithms, and are needed for the ..". Please provide references for the bandit convex optimization algorithms that make these standard assumptions. Please provide references for Line 215 (which previous works). 3) Typo in Page 5, Line 157, "that that" should be "that". 4) Line 444: "empirical" instead of "emprical" 5) $W_t$ is not introduced in Line 235. 6) Line 197, what is $\Theta(H)$? 7) It's mandatory to include the code for the experiment section in Neurlps submissions. Your code seems to be missing. Please rectify this immediately by sharing your code via an anonymous GitHub repository 8) I'm having trouble understanding the meaning of the paragraph found on Line 196. Could you please clarify? 9) In Line 510, which spiking? I do not understand the paragraph in Line 509. 10) Why there is a divergence problem in the third plot of Figure 1? 11) I must express difficulty in comprehending the conclusion about the initial phase of EBPC possessing lower stability. The relationship with Figure 1 is unclear and requires further explanation. I am also perplexed by the decision to choose an extraordinarily high starting multiplier on ε - a justification is needed for this choice. It's important to stress that the writing in the experiment section does not meet the expected standards for rigor. As it stands, the line of reasoning is opaque, and the process by which the conclusions were reached is indiscernible. Further compounding the issue, the code has not been made available for examination. This, as previously emphasised, hampers any possibility of a comprehensive understanding or verification of the results. I strongly recommend addressing these concerns in a revised submission. 12) Line 504- Why this is a barely-stable system? 13) Line 261, if the key point is to use ellipsoidal gradient estimator, where is its definition? 14) In algorithm 1, $S^{n-1}$ is not defined. 15) Line 810- There is a typo. References: [R1] A. Ben-Tal, S. Boyd, and A. Nemirovski, Control of Uncertainty-Affected Discrete Time Linear Systems via Convex Programming. Technical Report Minerva Optimization Center, Technion, Haifa, Israel, 2005 [Online]. Available: http://www.stanford.edu/~boyd/papers/pur_out_control.html
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
3 good
Presentation
2 fair
Contribution
3 good
Limitations
Yes.
Summary
This paper presents an algorithm to perform control in the semi-adversarial setting. After presenting the gap in the literature they want to fill, the authors present an algorithm that shows optimal regret ($O(\sqrt{T})$) for this setting, considerably improving the previous bound known from the literature ($O(T^{3/4})$, Gradu et al., 2020). The authors perform an experimental campaign to validate their solution in the appendix.
Strengths
- The gap in the literature that the authors fill is clearly stated. - The setting and the assumptions are clearly presented. - The work, in general, is clearly presented (except for the algorithms, see Weaknesses). - The authors face both the cases of known and unknown systems. - The bounds presented are tight, given the lower bounds known from the literature.
Weaknesses
- Algorithms 1, 2, and 3 should be explained instead of only presenting the pseudo-code. Some step may not be clear to all the readers only from the pseudo-code.
Questions
No questions.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
2: You are willing to defend your assessment, but it is quite likely that you did not understand the central parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
3 good
Presentation
3 good
Contribution
3 good
Limitations
No limitations.
Summary
This paper studies LQG with semi-adversarial disturbances and bandit feedback. The authors proposed a novel algorithm with $\sqrt T$ regret bound, which improves the $T^{3/4}$ regret bound in the literature. The algorithm utilizes the quadratic cost function structure and the ellipsoidal gradient estimator.
Strengths
The paper follows the classic disturbance-action policy and online nonstochastic control and OCO-M framework. The novel part is the Elllipsoida BCO with Memory algorithm and its regret analysis. The algorithm motivation and the key steps are explained clearly. The paper solves an interesting open question that whether $\sqrt T$ regret can be achieved for LQG under bandit feedback, under the assumption that the disturbances consist of both a large enough i.i.d. term and an adversarial term.
Weaknesses
1. Simulation. The paper lacks simulation results for verification of the improved technical bound. Though the supplementary material provides some figures, the simulation setups are not clearly explained. See more questions in the next box. 2. Novelty. I have mixed feelings about the novelty of this paper. On the one hand, the paper successfully improves the regret bound order to $\sqrt T$. On the other hand, the majority of the algorithm design is based on the classic disturbance-action policy and OCO-M formulation, so I am not sure if the algorithm design is novel enough for a neurips publication. 3. Presentation. The paper seems to be written in a rush. For example, the title of the paper is inconsistent with the title on the webpage. The major algorithm design trick is the ellipsoidal gradient estimator, but the paper didn't explain this estimator or provide intuition. The main theorems are merely stated without any explanation.
Questions
In the main paper, Q1: the title is inconsistent with that on the openreview webpage. Please make them consistent. Q2: Why do the authors consider semi-adversarial disturbances? What are the benefits and limitations of this setting? Why do the authors simulate i.i.d. disturbances instead of semi-adversarial disturbances? In the supplementary material, for the simulation results: Q3: Is the dynamical system known or unknown? If the system is unknown, how to obtain the optimal $K$ to the LQR problem? If the system is known, how does the algorithm perform under unknown dynamics? Q4: What's the y axis? Why is it 0.1, 0.01? The authors skipped most parts of the simulation setup and referred the reader to Gradu et al. 2020. But the figures look very different from those in Gradu et al. 2020. It is hard to interpret the simulation results without future explanation. Q5: The x axis scale goes as large as 100k, which is unreasonable for a control task. Is it possible to plot the figures in the same settings as in Gradu et al. 2020, where the horizon is usually within 1k?
Rating
5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
Confidence
3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.
Soundness
2 fair
Presentation
2 fair
Contribution
2 fair
Limitations
N/A
Summary
This paper studies the online control problem with a quadratic cost function, adversarially chosen dynamics, and semi-adversarially chosen losses (they are the sum of a zero-mean term and an obliviously chosen adversarial term). The algorithm proposed lowers the previous $T^{3/4}$ algorithm to a $\sqrt{T}$ algorithm against the class of disturbance response controllers, matching the lower bound. The crux of the analysis is handling the non-independence between plays and noise, which many OCO algorithms assume, and to carefully control the bias of the loss estimators. The authors solve the former with a novel method of using an online-learning with delay framework to bypass and the later by adapting an ellipsoidal gradient estimator.
Strengths
Good organization, really clear presentation and summary of the high-level ideas used in this and previous work. Excellent literature review as well. The overall structure of the paper is well organized, and the algorithm follows naturally from all the components used. The significance is high, as this paper really makes progress in closing off a field of online control by matching a lower bound. Much steady progress has been made on this problem over the years, so this paper is a great next step for this community. Tangentially, I think some of the ideas for algorithm 1 will be useful for the bandits-with-memory community.
Weaknesses
Assumption 3.3 seems unnatural. Can you provide a bit more context on its necessity? More generally, how are ideas from learning with delay present in your algorithms? I did not find this point very clear. Might be worth mentioning that there are empirical evaluations in the main body. Finally, I wish the authors provided more intuition for how the proofs of the theorems worked; for example, what are the implications of using $\hat G$ instead of $G$?
Questions
A few questions are asked above.
Rating
7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
Confidence
4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.
Soundness
4 excellent
Presentation
4 excellent
Contribution
3 good
Limitations
As a very theoretical work, I don't think any discussion about negative societal impact is necessary.
Thanks for the response. Reading the reviews of the other vewiers and the responses, I agree with the crowd that the writing and presentation can be cleaned up, which the authors seemed to have committed too. I think the technical results are still strong, so I will keep my score.
Thanks a lot for the response. About the 7th question in my major comments, can you explain why it is impossible for any OCO-M-based control algorithm? A reference would also work. I suggest including this in the paper for readers not working in this field. If the presentation of the paper is improved, it will have a better chance of being understood and used by other people. I certainly encourage the authors to do that in the revision.
Thank you for the follow up question! The original OCO-M paper [1] is the fundamental framework that a long line of nonstochastic control (cited in our paper) is based on. While [1] does not explicitly provide a lower bound, following similar analysis as in [1], the memory length would factor in the regret bound in polynomial order. In the nonstochastic control setting, the memory length is taken to be $\log T$ due to the decaying effect of the past states in stable systems. This is why in this line of work, $\log T$ appears in the final bound. We will clarify this in the paper. [1]: Anava, Oren, Elad Hazan, and Shie Mannor. "Online learning for adversaries with memory: price of past mistakes." Advances in Neural Information Processing Systems 28 (2015).
Thank the authors for their responses! Somehow I find the authors' responses are in a defensive manner instead of trying to clarify my confusion. I hope that we can carry out more discussions to help improve the quality of the paper and resolve the confusions that readers may have. I provide more comments below and am happy to discuss more! **1. On simulation** I also don't fully understand the authors' response here. There isn't a simulation section in the manuscript of the main paper I read, but I may be looking at the wrong manuscript, e.g., an older version due to technical errors in openreview. Please correct me if I am wrong. Regarding the simulations provided in the appendix, it is less organized than a formal simulation section in the main paper and there are many simulation settings missing. I do believe that the numerical verification for this method is important so I would suggest adding a more organized simulation section to the main paper. **2. On novelty** I agree with the authors that the improved rate is important, as I mentioned in my original review. But I am still not fully convinced by the "novel exploration scheme enabled by the gradient estimator in Suggala et al. (2021)". Could the authors provide more discussions on the novelty of the exploration scheme, e.g., why is it different from traditional methods, what's the challenge, how to resolve it? **3. Title** Thanks for the clarification! I empathize with that. **4. semi-adversarial disturbances** The authors provide a very interesting motivation for the semi-adversarial disturbances: the actual control may be corrupted by noises caused by mechanics or system errors. I totally agree with that. But then, with the authors' discussion on the difficulties of the fully adversarial noises, does it mean that mechanics errors actually help with the control? So instead of improving the mechanics device, one should opt for more unreliable ones since it provides some excitation to the system? I am puzzled and fascinated by this counter-intuitive logic here. **5. On unknown system** Thanks for the response. Sorry for not posing my confusion clearer. I was thinking when the system is not open-loop stable, then it needs to be stabilized by a K. With uncertainties, it means a robust stabilizing K, which calls for a small system uncertainty otherwise it does not exist. **6. On the simulation** The authors explained the horizon choices well. Regarding the y axis, I was asking why the range of the y axis looks very different from that in [Gradu et al. 2020], whose y axis order is around 10. The authors omitted most of the simulation setting and referred to [Gradu et al. 2020] but even the scales of the figures are different... Can the authors explain more what the new changes they made for the simulation setting?
Thank you for providing us with detailed follow-up questions! We are happy to clarify any areas where you found our responses insufficiently clear – please let us know. It's our goal to address your concerns to a satisfactory extent. 1. Indeed, the simulation section is contained in the appendix. As mentioned in our responses, we still plan to enhance the simulation section substantially and include more details about the simulation setting. To address your concern, we are happy to answer any questions you may have for our simulation sections here (and will add theses to the revised paper). We still plan to keep the detailed simulation section in the appendix (as we believe our main contribution is the theoretically tiger bound), but we will make sure to add a clear overview of the section to the main paper. 2. Online bandit algorithms rely on a stochastic unbiased/low-biased gradient estimator since the algorithm does not have direct access to the loss functions. The most traditional estimator used by [1] is a spherical estimator. That is, given an algorithm update $x_t$, sample $y_t$ from a sphere of appropriate size centered at $x_t$, and create the unbiased gradient estimator of $f_t(x_t)$ using $y_t$. This method does not take into account $f_t$’s structure. Later, [2] proposed an ellipsoid estimator that we make use of here: construct gradient estimator by sampling $y_t$ is instead sampled from an ellipsoid defined by $A_t$’s spectrum centered at $x_t$ (line 5 in algorithm 1). The key challenge here is that we want to extend the result of [2] to OCO with memory. In OCO with memory, the analysis follows from decomposing the regret into $(F_t(x_{t-H+1},\dots, x_t)-f_t(x_t))+(f_t(x_t)-f_t(x^*))$, where $f_t(x_t)=F_t(x_t,\dots,x_t)$. To bound the second term, it is essential that the gradient estimator $g_t$ is a low-bias estimator of $\nabla f_t(x_t)$. Our proposed gradient estimator achieves the low-bias guarantee. We show this by showing that $g_t$ is unbiased for the sum of partial gradients of $F_t(x_{t-H+1},\dots,x_t)$, which is motivated by the observation of unbiased gradient estimators for quadratic functions made by Suggala et al. (2021). [1]: Flaxman, Kalai, & McMahan. "Online convex optimization in the bandit setting: gradient descent without a gradient." [2]: Hazan & Levy. "Bandit convex optimization: Towards tight bounds." 4. This is subtle – it depends on what you mean by “help with the control.” The hard problem in nonstochastic control comes from the “nonstochastic” part. That is, the perturbations and loss functions to the system are selected by an adversary that acts more adversarially than stochastic systems. The intuition is that with the presence of some noise, the adversary’s ability is limited relative to the case in which the adversary also controlled that noise. If we consider a system that has only adversarial noise and add stochastic noise, the added noise does reduce regret, but only by increasing the “baseline” loss – that of the hindsight-best single-response controller. For instance, we add so much noise as to effectively drown out adversary perturbations, we may see our problem as being essentially stochastic, which makes it easier in a certain sense, but our absolute loss will of course be much higher. Your conclusion that “one should opt for more unreliable ones since it provides some excitation to the system” is therefore not quite right – when the problem parameters are still unset (for instance, if stochastic noise can be added or not), absolute error is not the same as regret, and we wish to minimize absolute error. We hope that this resolves your puzzlement. 5. Please let us know if we interpret the question wrong. If the question is what to do in the case of unknown stabilizable (but not stable) systems, our results may be generalized by the technique of learning a stabilizing controller. As mentioned in our discussion and conclusion section, Chen & Hazan showed stable controller recovery for unknown systems. We do not have this result for now, but [Chen & Hazan] makes this a future direction we can explore. 6. As everything is linear, the y-axis scale is simply a function of the noise magnitudes (which are different in our simulations, since we do not have access to the Gradu et al. simulation code). As a result, visual comparison of the charts is actually meaningful even without y-axis labels, since the results are invariant WRT this scale. Apart from that, the major nonspecified element is the exact nature of the sinusoidal noise (a sinusoidally varying scalar times a constant vector). We do not believe that there are any other meaningful unspecified changes to the setting (and our experimental results seem to conform to those of Gradu et al. in character) – please let us know if you spot any other missing details! We certainly intend to clarify the setting discussion in revision, including fleshing out the detail from the Gradu et al. setup.
Thanks for the detailed response! It resolved my concerns. But I still think more simulations are necessary even though I understand that the major contribution of this paper is to close a theoretical gap. I will raise my score.
What additional simulations do you believe would be helpful (and what other properties do you believe they should elucidate)? We based our experimental suite off of Gradu et al. (which was designed to showcase a variety of common practical uses of control), but we would of course be interested to hear any additional suggestions you might have for properties that we could demonstrate better (either through more focused explanation of the current experiments or adding specific new ones).
Thank you for your response. I will keep my score for now, waiting for the reviewers' discussion period.
Acknowledgement of rebuttal
I thank the authors for their rebuttal and their response to my only question about their paper. I think that the single reference that the authors point out as an argument for the relevance of their results is not quite enough to change my assessment; also, and perhaps more importantly, the authors did not add this reference and the underlying context to a revision of the paper itself, which would have been beneficial to the readers. I therefore shall keep my score unchanged.
Decision
Accept (poster)