Tight Rates for Bandit Control Beyond Quadratics

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.

Strengths

1. This paper generalizes previous settings and get the optimal regret. 2. This paper is well-written and the intuition behind algorithm is explained clearly.

Weaknesses

The technical contribution seems not strong, the analysis of Algorithm 1 (reduce to no-memory BCO, bound regret for base algorithm and moving cost) follows the proof sketch of [1]. The main change is replacing the base algorithm with Newton-based updates in Algorithm 2 of [2], ensuring a tighter bound by utilizing the $\kappa$-convexity and affine memory. [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

What is the main techinical challenge when combining and adapting the proof in [1] and [2]?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes.

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.

Strengths

This paper presents a direct theoretical improvement, offering significant advancements in the field. It is well-written and theoretically solid, providing a robust analysis and clear insights into the online non-stochastic control problem with adversarial noise, bandit feedback, and strongly convex loss functions.

Weaknesses

1. The citation for Optimal rates for bandit non-stochastic control is incorrect; it was mistakenly written as NeurIPS 2024. 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

No questions.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

See weaknesses.

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.

Strengths

1. Though I have skimmed the proof of several lemmas, the analysis part seems to be rigorous and mathematically correct. 2. The delayed mechanism to de-correlate the recent m iterates looks interesting, which may be of use in the other delayed feedback setting.

Weaknesses

1. The specific contribution of this work towards the previous work of Suggala et al. [2024] is still a little bit unclear. According to Line 382 to 387, it seem that the most important algorithmic contribution is the delay mechanism. 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

The questions are raised in the weakness section. I am willing to re-evaluate the scores if these questions are properly answered.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

This paper is pure theoretical and does not have any limitations.