Tight Rates for Bandit Control Beyond Quadratics
<|reference_start|>Tight Rates for Bandit Control Beyond Quadratics: 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.<|reference_end|>
@article{sun2024tight,
    title={Tight Rates for Bandit Control Beyond Quadratics},
    author={Y. Jennifer Sun, Zhou Lu},
    journal={arXiv preprint arXiv:2410.00993},
    year={2024},
    archivePrefix={arXiv},
    eprint={2410.00993},
    primaryClass={cs.LG math.OC}
}