Abstract
In the field of online non-stochastic control, bridging the gap between idealized classical assumptions and adversarial real-world environments remains a fundamental challenge. This paper presents a significant theoretical advancement by establishing the first algorithm to achieve the optimal $O(\sqrt{T})$ regret bound for bandit control problems involving adversarial noise and non-quadratic, strongly convex costs. By reducing the control problem to a simpler optimization task with occasional updates and employing second-order methods, the authors improve upon the previous state-of-the-art $O(T^{2/3})$ rate.
Introduction
Classical control theory, exemplified by Linear Quadratic Control (LQC), typically relies on three simplifying assumptions: stochastic noise following known distributions, full information feedback (access to cost functions and gradients), and quadratic cost structures. However, real-world applications—such as autonomous vehicle navigation or complex robotics—frequently violate these assumptions. In these settings, noise may be adversarial, cost functions are often non-quadratic, and feedback is restricted to "bandit" observations (a single scalar value representing the total cost).
The central question addressed in this work is whether optimal performance, measured by $O(\sqrt{T})$ regret, is attainable when all three classical pillars are removed. While previous research achieved this rate for quadratic costs, general smooth costs remained limited to a sub-optimal $O(T^{2/3})$ rate.
Methodology: Reduction and Curvature
The authors' approach centers on a sophisticated reduction strategy that transforms the control problem into a manageable optimization framework.
Reduction to Bandit Convex Optimization with Memory (BCO-M)
The control problem is first mapped to BCO-M, where the current cost is a function of both the current action and a window of preceding actions. This captures the inherent state-dependency of control systems.
The "Occasional Update" Mechanism
To mitigate the complexities of memory in bandit feedback, the algorithm employs an "occasional update" strategy. Using a Bernoulli random variable, the controller decides whether to update its strategy at each time step, typically updating once every $m$ steps. This effectively "clears" the system's memory, allowing the algorithm to treat the problem as a sequence of independent optimization tasks.
Newton-Based Updates and $\kappa_0$-Convexity
Unlike prior methods relying on first-order Gradient Descent, this work utilizes second-order Newton-based updates. This allows the algorithm to exploit the strong convexity (curvature) of the cost function. To facilitate this in a bandit setting, the authors leverage $\kappa_0$-convexity, a property that enables the construction of low-variance estimators for the Hessian (second derivatives) using only scalar feedback.
Key Insights
The paper identifies several critical factors that enable the jump to $O(\sqrt{T})$ regret:
- The Role of Curvature: Strong convexity is identified as the essential requirement for achieving optimal rates under bandit feedback. Without curvature, the scalar feedback provides insufficient information for rapid optimization.
- Exploiting Affine Structure: By leveraging the underlying linear structure of control systems ($x_{t+1} = Ax_t + Bu_t$), the authors bypass the lower bounds that typically restrict general bandit problems with memory.
- Decorrelation via Delay: A novel delay mechanism is introduced to decorrelate neighboring iterates, which is vital for bounding the "moving cost"—the penalty incurred by the algorithm for shifting strategies too rapidly.
Results and Impact
The primary contribution is the rigorous proof that the proposed algorithm achieves $O(\sqrt{T})$ regret for bandit non-stochastic control with strongly convex and smooth cost functions. This result closes the theoretical gap left by previous works, such as Cassel and Koren (2020), and generalizes the findings of Suggala et al. (2024) beyond quadratic costs. Furthermore, the improvements made to BCO-M algorithms have potential implications for other domains, including resource allocation and recommendation systems.
Limitations and Future Directions
While the $O(\sqrt{T})$ rate is a significant milestone, it relies on the assumption of strong convexity. Whether this rate can be maintained for general convex functions remains an open theoretical question. Additionally, the computational overhead of Newton-based updates—specifically matrix inversions—may pose challenges for high-dimensional systems. Future empirical research is needed to evaluate these controllers in real-world simulators and assess the practical impact of the constants involved in the theoretical bounds.
Summary updated