提出新算法实现带记忆的非凸控制最优后悔率
Tight Rates for Bandit Control Beyond Quadratics
- 将带记忆控制问题转化为无记忆凸优化，克服长期依赖难题
- 在对抗扰动下达成 √T 的最优后悔率，优于原有 T^{2/3}
- 适用于复杂现实控制场景，对强化学习研究者有参考价值
与经典线性二次控制不同，现实控制问题通常包含对抗扰动、仅能获取贝叶斯反馈以及非二次的对抗性代价函数。一个基础但未解决的问题是：能否在这些一般控制问题中实现最优后悔率？现有方法通常将问题归约为带记忆的贝叶斯凸优化（BCO）。然而，在贝叶斯设定下，由于记忆结构和非二次损失，构建低方差梯度估计器极具挑战。本文给出肯定回答：提出一种新算法，在存在对抗扰动的情况下，对强凸且光滑的代价函数，实现了 √T 的最优后悔率，优于先前的 Õ(T^{2/3})。该算法通过将问题转化为无记忆的 BCO 来克服记忆障碍，并利用近期 BCO 研究成果处理一般强凸代价。此外，我们还设计了改进的带记忆 BCO 算法，可能具有独立研究价值。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。