# Online Convex Optimization with Stochastic Constraints

arXiv: https://arxiv.org/abs/1708.03741 · HTML: https://mlsanity.com/paper/1708.03741/

## Key facts

- Cited by 95 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Aug 2017.

## Built on by (most cited first, 30 of 95)

- [A Unifying Framework for Online Optimization with Long-Term Constraints](https://mlsanity.com/paper/2209.07454/) (2022)
- [Regret and Cumulative Constraint Violation Analysis for Online Convex Optimization with Long Term Constraints](https://mlsanity.com/paper/2106.05135/) (2021)
- [DOPE: Doubly Optimistic and Pessimistic Exploration for Safe Reinforcement Learning](https://mlsanity.com/paper/2112.00885/) (2021)
- [The Ideal Continual Learner: An Agent That Never Forgets](https://mlsanity.com/paper/2305.00316/) (2023)
- [Optimal Algorithms for Online Convex Optimization with Adversarial Constraints](https://mlsanity.com/paper/2310.18955/) (2023)
- [An Efficient Pessimistic-Optimistic Algorithm for Stochastic Linear Bandits with General Constraints](https://mlsanity.com/paper/2102.05295/) (2021)
- [Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs](https://mlsanity.com/paper/2206.02346/) (2022)
- [Non-stationary Bandits with Knapsacks](https://mlsanity.com/paper/2205.12427/) (2022)
- [On Kernelized Multi-Armed Bandits with Constraints](https://mlsanity.com/paper/2203.15589/) (2022)
- [Generative Auto-Bidding with Value-Guided Explorations](https://mlsanity.com/paper/2504.14587/) (2025)
- [Regret and Cumulative Constraint Violation Analysis for Distributed Online Constrained Convex Optimization](https://mlsanity.com/paper/2105.00321/) (2021)
- [Fairness-Aware Online Meta-learning](https://mlsanity.com/paper/2108.09435/) (2021)
- [Stochastic Inexact Augmented Lagrangian Method for Nonconvex Expectation Constrained Optimization](https://mlsanity.com/paper/2212.09513/) (2022)
- [Online Bidding Algorithms for Return-on-Spend Constrained Advertisers](https://mlsanity.com/paper/2208.13713/) (2022)
- [No-Regret Learning in Bilateral Trade via Global Budget Balance](https://mlsanity.com/paper/2310.12370/) (2023)
- [Distributed Online Convex Optimization with Adversarial Constraints: Reduced Cumulative Constraint Violation Bounds under Slater's Condition](https://mlsanity.com/paper/2306.00149/) (2023)
- [Provably Efficient Generalized Lagrangian Policy Optimization for Safe Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2306.00212/) (2023)
- [RTBAgent: A LLM-based Agent System for Real-Time Bidding](https://mlsanity.com/paper/2502.00792/) (2025)
- [Safe Online Convex Optimization with Unknown Linear Safety Constraints](https://mlsanity.com/paper/2111.07430/) (2021)
- [Learning to Persuade on the Fly: Robustness Against Ignorance](https://mlsanity.com/paper/2102.10156/) (2021)
- [Simultaneously Achieving Sublinear Regret and Constraint Violations for Online Convex Optimization with Time-varying Constraints](https://mlsanity.com/paper/2111.07707/) (2021)
- [Towards Fair Disentangled Online Learning for Changing Environments](https://mlsanity.com/paper/2306.01007/) (2023)
- [A single-loop SPIDER-type stochastic subgradient method for expectation-constrained nonconvex nonsmooth optimization](https://mlsanity.com/paper/2501.19214/) (2025)
- [Doubly Fair Dynamic Pricing](https://mlsanity.com/paper/2209.11837/) (2022)
- [Particle-based Online Bayesian Sampling](https://mlsanity.com/paper/2302.14796/) (2023)
- [Online Convex Optimization with Continuous Switching Constraint](https://mlsanity.com/paper/2103.11370/) (2021)
- [BanditQ: Fair Bandits with Guaranteed Rewards](https://mlsanity.com/paper/2304.05219/) (2023)
- [Online Learning under Adversarial Nonlinear Constraints](https://mlsanity.com/paper/2306.03655/) (2023)
- [No-Regret is not enough! Bandits with General Constraints through Adaptive Regret Minimization](https://mlsanity.com/paper/2405.06575/) (2024)
- [GAS: Generative Auto-bidding with Post-training Search](https://mlsanity.com/paper/2412.17018/) (2024)

## Abstract (arXiv)

This paper considers online convex optimization (OCO) with stochastic constraints, which generalizes Zinkevich's OCO over a known simple fixed set by introducing multiple stochastic functional constraints that are i.i.d. generated at each round and are disclosed to the decision maker only after the decision is made. This formulation arises naturally when decisions are restricted by stochastic environments or deterministic environments with noisy observations. It also includes many important problems as special cases, such as OCO with long term constraints, stochastic constrained convex optimization, and deterministic constrained convex optimization. To solve this problem, this paper proposes a new algorithm that achieves O(√T) expected regret and constraint violations and O(√Tlog(T)) high probability regret and constraint violations. Experiments on a real-world data center scheduling problem further verify the performance of the new algorithm.