2021/11/14 by Sapana Chaudhary, Chaudhary, Sapana, Dileep Kalathil +1 · 1 citation
Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning and Algorithms #Optimization and Control (math.OC) #Optimization and Search Problems #cs.LG #math.OC
paper · pdf · doi:10.48550/arxiv.2111.07430
18 pages
arxiv created 2021/11/14 · openalex publication_date 2021/11/14 · arxiv updated 2021/11/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problem of safe online convex optimization, where the action at each time step must satisfy a set of linear safety constraints. The goal is to select a sequence of actions to minimize the regret without violating the safety constraints at any time step (with high probability). The parameters that specify the linear safety constraints are unknown to the algorithm. The algorithm has access to only the noisy observations of constraints for the chosen actions. We propose an algorithm, called the Safe Online Projected Gradient Descent (SO-PGD) algorithm, to address this problem. We show that, under the assumption of the availability of a safe baseline action, the SO-PGD algorithm achieves a regret O(T2/3). While there are many algorithms for online convex optimization (OCO) problems with safety constraints available in the literature, they allow constraint violations during learning/optimization, and the focus has been on characterizing the cumulative constraint violations. To the best of our knowledge, ours is the first work that provides an algorithm with provable guarantees on the regret, without violating the linear safety constraints (with high probability) at any time step.