利用预测改进在线凸优化中约束违规和损失的累积误差。
An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints
- 基于损失与约束的预测，设计乐观算法优化决策
- 预测准确时，误差率从√T降至√预测误差
- 适合有高质量预测的在线学习场景
我们研究带有对抗性约束的在线凸优化（OCO），算法需在序列决策中同时最小化凸损失函数并控制累积约束违规。考虑算法可获取损失与约束函数的预测信息，本文提出新方法，将现有最优的 $ O(ar{f}) $ 和 $ ilde{O}(ar{g^+}) $ 累积预测误差下，达到 $ O(ar{f}) $ 和 $ ilde{O}(ar{g^+}) $ 的遗憾与约束违规。最坏情况下，当 $ E_T(f) = O(T) $ 且 $ E_T(g^+) = O(T) $ 时，结果退化为 $ O(ar{f}) $，但预测越准，性能越优。进一步应用于具有序列风险约束的对抗性上下文老虎机问题，得到 $ O(ar{f} T^{1/3}) $ 遗憾与 $ O(ar{g^+} T^{1/3}) $ 违规，预测质量高时优于已有方法。
原文摘要 · Abstract (English)
We study Online Convex Optimization (OCO) with adversarial constraints, where an online algorithm must make sequential decisions to minimize both convex loss functions and cumulative constraint violations. We focus on a setting where the algorithm has access to predictions of the loss and constraint functions. Our results show that we can improve the current best bounds of $ O(\sqrt{T}) $ regret and $ \tilde{O}(\sqrt{T}) $ cumulative constraint violations to $ O(\sqrt{E_T(f)}) $ and $ \tilde{O}(\sqrt{E_T(g^+)}) $, respectively, where $ E_T(f) $ and $E_T(g^+)$ represent the cumulative prediction errors of the loss and constraint functions. In the worst case, where $E_T(f) = O(T) $ and $ E_T(g^+) = O(T) $ (assuming bounded gradients of the loss and constraint functions), our rates match the prior $ O(\sqrt{T}) $ results. However, when the loss and constraint predictions are accurate, our approach yields significantly smaller regret and cumulative constraint violations. Finally, we apply this to the setting of adversarial contextual bandits with sequential risk constraints, obtaining optimistic bounds $O (\sqrt{E_T(f)} T^{1/3})$ regret and $O(\sqrt{E_T(g^+)} T^{1/3})$ constraints violation, yielding better performance than existing results when prediction quality is sufficiently high.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。