Efficient Constrained Regret Minimization
This work addresses constrained sequential decision-making in adversarial environments, offering a method for scenarios where average constraints must be met, representing an incremental advancement in online learning.
The paper tackles the problem of online learning with additional constraints on decisions, proposing the Lagrangian exponentially weighted average (LEWA) algorithm to maximize total reward while satisfying constraints, and establishes regret and constraint violation bounds for full information and bandit feedback models.
Online learning constitutes a mathematical and compelling framework to analyze sequential decision making problems in adversarial environments. The learner repeatedly chooses an action, the environment responds with an outcome, and then the learner receives a reward for the played action. The goal of the learner is to maximize his total reward. However, there are situations in which, in addition to maximizing the cumulative reward, there are some additional constraints on the sequence of decisions that must be satisfied on average by the learner. In this paper we study an extension to the online learning where the learner aims to maximize the total reward given that some additional constraints need to be satisfied. By leveraging on the theory of Lagrangian method in constrained optimization, we propose Lagrangian exponentially weighted average (LEWA) algorithm, which is a primal-dual variant of the well known exponentially weighted average algorithm, to efficiently solve constrained online decision making problems. Using novel theoretical analysis, we establish the regret and the violation of the constraint bounds in full information and bandit feedback models.