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 (Cassel and Koren, 2020. Our algorithm overcomes the memory issue by reducing the problem to Bandit Convex Optimization (BCO) without memory and addresses general strongly-convex costs using recent advancements in BCO from (Suggala et al., 2024). Along the way, we develop an improved algorithm for BCO with memory, which may be of independent interest.

本研究解决了在面对对抗性扰动情况下，如何为复杂控制问题实现最佳后悔值的未解问题。论文提出了一种新算法，实现了在这种情况下的$\tilde{O}(\sqrt{T})$最优后悔值，相较于之前的$\tilde{O}(T^{2/3})$的界限有了显著提升。此算法有效克服了内存结构带来的挑战，并引入了对强凸成本的处理方法，具有广泛的应用潜力。

超越二次函数的强盗控制紧速率