Playing in the Dark: No-regret Learning with Adversarial Constraints
Abhishek Sinha Rahul Vaze
We study a generalization of the classic Online Convex Optimization (OCO)
framework by considering additional long-term adversarial constraints.
Specifically, after an online policy decides its action on a round, in addition
to a convex cost function, the adversary also reveals a set of $k$ convex
constraints. The cost and the constraint functions could change arbitrarily
with time, and no information about the future functions is assumed to be
available. In this paper, we propose a meta-policy that simultaneously achieves
a sublinear cumulative constraint violation and a sublinear regret. This is
achieved via a black box reduction of the constrained problem to the standard
OCO problem for a recursively constructed sequence of surrogate cost functions.
We show that optimal performance bounds can be achieved by solving the
surrogate problem using any adaptive OCO policy enjoying a standard
data-dependent regret bound. A new Lyapunov-based proof technique is presented
that reveals a connection between regret and certain sequential inequalities
through a novel decomposition result. We conclude the paper by highlighting
applications to online multi-task learning and network control problems.