Jump to Content

On the Convergence of Regret Minimization Dynamics in Concave Games

Eyal Even-Dar
Yishay Mansour
Uri Nadav
41st Annual ACM Symposium on Theory of Computing, STOC, ACM (2009), pp. 523-532


We consider standard regret minimization setting where at each time step the decision maker has to choose a distribution over k alternatives, and then observes the loss of each alternative. The setting is very similar to the classical online job scheduling setting with three major differences: Information model: in the regret minimization setting losses are only observed after the actions (assigning the job to a machine) is performed and not observed before the action selection, as assumed in the classical online job scheduling setting, The comparison class: in regret minimization the comparison class is the best static algorithm (i.e., distribution over alternatives) and not the optimal offline solution. Performance measure: In regret minimization we measure the additive difference to the optimal solution in the comparison class, in contrast to the ratio used in online job scheduling setting. Motivated by load balancing and job scheduling, we consider a global cost function (over the losses incur by each alternative/machine), rather than simply a summation of the instantaneous losses as done traditionally in regret minimization. Such global cost functions include the makespan (the maximum over the alternatives/machines) and the Ld norm (over the alternatives/machines). The major contribution of this work is to design a novel regret minimization algorithm based on calibration that guarantees a vanishing average regret, where the regret is measured with respect to the best static decision maker, who selects the same distribution over alternatives at every time step. Our results hold for a wide class of global cost functions. which include the makespan and the Ld norms, for d>1. In contrast, we show that for concave global cost functions, such as Ld norms for d<1, the worst-case average regret does not vanish. In addition to the general calibration based algorithm, we provide simple and efficient algorithms for special interesting cases.