Optimistic Safety for Online Convex Optimization with Unknown Linear Constraints
Not on the map. Why?
Abstract (arXiv)
We study the problem of online convex optimization (OCO) under unknown linear constraints that are either static, or stochastically time-varying. For this problem, we introduce an algorithm that we term Optimistically Safe OCO (OSOCO) and show that it enjoys tildeO(√T) regret and no constraint violation. In the case of static linear constraints, this improves on the previous best known tildeO(T2/3) regret under the same assumptions. In the case of stochastic time-varying constraints, our work supplements existing results that show O(√T) regret and O(√T) cumulative violation under more general convex constraints and a different set of assumptions. In addition to our theoretical guarantees, we also give numerical results that further validate the effectiveness of our approach.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 32 of its 63 references that are in the map. First posted on arXiv 9 Mar 2024.
Builds on
32 of 63 references.
References · 32
- 2017Constrained Policy Optimizationcited by 928
- 2019Introduction to Online Convex Optimizationcited by 793
- 2020Safe Reinforcement Learning in Constrained Markov Decision Processescited by 109
- 2017Online Convex Optimization with Stochastic Constraintscited by 94
- 2019Linear Stochastic Bandits Under Safety Constraintscited by 90
- 2020Improper Learning for Non-Stochastic Controlcited by 83
- 2018Stagewise Safe Bayesian Optimization with Gaussian Processescited by 79
- 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
- 2020Stochastic Bandits with Linear Constraintscited by 68
- 2019Learning Linear-Quadratic Regulators Efficiently with only √T Regretcited by 67
- 2017Online Convex Optimization with Time-Varying Constraintscited by 55
- 2018Online Linear Quadratic Controlcited by 55
20 more
- 2018Online convex optimization for cumulative constraintscited by 47
- 2017An Online Convex Optimization Approach to Dynamic Network Resource Allocationcited by 42
- 2022A Unifying Framework for Online Optimization with Long-Term Constraintscited by 41
- 2020Faster Projection-free Online Learningcited by 39
- 2019Safe Linear Thompson Sampling with Side Informationcited by 37
- 2021Safe Reinforcement Learning with Linear Function Approximationcited by 33
- 2019Online Non-Convex Learning: Following the Perturbed Leader is Optimalcited by 31
- 2019Online Primal-Dual Mirror Descent under Stochastic Constraintscited by 31
- 2021Efficient Projection-Free Online Convex Optimization with Membership Oraclecited by 29
- 2018Learning in Non-convex Games with an Optimization Oraclecited by 24
- 2021Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimizationcited by 21
- 2020Revisiting Projection-free Online Learning: the Strongly Convex Casecited by 20
- 2019Safe Convex Learning under Uncertain Constraintscited by 17
- 2021Safe Online Convex Optimization with Unknown Linear Safety Constraintscited by 13
- 2023Directional Optimism for Safe Linear Banditscited by 8
- 2020Safe Learning under Uncertain Objectives and Constraintscited by 7
- 2023Online Learning under Adversarial Nonlinear Constraintscited by 6
- 2018Learning Aided Optimization for Energy Harvesting Devices with Outdated State Informationcited by 5
- 2022Rate-Optimal Online Convex Optimization in Adaptive Linear Controlcited by 5
- 2023Dynamic Regret Analysis of Safe Distributed Online Optimization for Convex and Non-convex Problemscited by 4
Built on by
Citing papers per year: 2024: 1.
1 paper.