An Optimistic Algorithm for Online Convex Optimization with Adversarial Constraints
This work addresses optimization under uncertainty for online decision-making systems, offering incremental improvements when predictions are accurate.
The paper tackles the problem of Online Convex Optimization with adversarial constraints by using predictions of loss and constraint functions to improve regret and constraint violation bounds from O(√T) to O(√E_T(f)) and Õ(√E_T(g^+)), respectively, where E_T(f) and E_T(g^+) are cumulative prediction errors, and applies this to adversarial contextual bandits with sequential risk constraints for optimistic bounds.
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.