Optimistic Safety for Linearly-Constrained Online Convex Optimization
Spencer Hutchinson Tianyi Chen Mahnoosh Alizadeh
The setting of online convex optimization (OCO) under unknown constraints has
garnered significant attention in recent years. In this work, we consider a
version of this problem with static linear constraints that the player receives
noisy feedback of and must always satisfy. By leveraging our novel design
paradigm of optimistic safety, we give an algorithm for this problem that
enjoys $\tilde{\mathcal{O}}(\sqrt{T})$ regret. This improves on the previous
best regret bound of $\tilde{\mathcal{O}}(T^{2/3})$ while using only slightly
stronger assumptions of independent noise and an oblivious adversary. Then, by
recasting this problem as OCO under time-varying stochastic linear constraints,
we show that our algorithm enjoys the same regret guarantees in such a setting
and never violates the constraints in expectation. This contributes to the
literature on OCO under time-varying stochastic constraints, where the
state-of-the-art algorithms enjoy $\tilde{\mathcal{O}}(\sqrt{T})$ regret and
$\tilde{\mathcal{O}}(\sqrt{T})$ violation when the constraints are convex and
the player receives full feedback. Additionally, we provide a version of our
algorithm that is more computationally efficient and give numerical experiments
comparing it with benchmark algorithms.