Reviews: Online Convex Optimization with Stochastic Constraints

The paper considers online convex optimization with constraints revealed in an online manner. In an attempt to circumvent a linear regret lower bound by Mannor et al [17] for adaptively chosen constraints, the paper deals with the setting where constraints are themselves generated stochastically. As a side effect, superior results are obtained for related problems such as OCO with long-term constraints. The paper does a nice job of introducing previous work and putting the contribution in perspective. The main algorithm of the paper is a first order online algorithm that performs an optimization step using the instantaneous penalty and constraint functions.