Online Decision Making under Stochastic Constraints

This paper proposes a novel algorithm for solving discrete online learning prob-lems under stochastic constraints, where the leaner aims to maximize the cumu-lative reward given that some additional constraints on the sequence of decisions need to be satisfied on average. We propose Lagrangian exponentially weighted average (LEWA) algorithm, which is a primal-dual variant of the well known ex-ponentially weighted average algorithm, and inspired by the theory of Lagrangian method in constrained optimization. We establish expected and high probability bounds on the regret and the violation of the constraint in full information and bandit feedback models for LEWA algorithm.