Online learning with expert advice and finitehorizon constraints

In this paper, we study a sequential decision making problem. The objective is to maximize the average reward accumulated over time subject to temporal cost constraints. The novelty of our setup is that the rewards and constraints are controlled by an adverse opponent. To solve the problem in a practical way, we propose an expert algorithm that guarantees both a vanish-ing regret and a sublinear number of violated constraints. The quality of the proposed algorithm is evaluated on a real-world power management problem. Our results clearly demonstrate that online learning with temporal cost constraints can be car-ried out successfully in practice