Abstract

We consider the online distributed non-stochastic experts problem, where the distributed system consists of one coordinator node that is connected to k sites, and the sites are required to communicate with each other via the coordinator. At each time-step t, one of the k site nodes has to pick an expert from the set {1, . . . , n}, and the same site receives information about payoffs of all experts for that round. The goal of the distributed system is to minimize regret at time horizon T , while simultaneously keeping communication to a minimum. The two extreme solutions to this problem are: (i) Full communication: p This essentially simulates the nondistributed setting to obtain the optimal regret bound at the cost of T communication. p (ii) No communication: Each site runs an independent copy – the regret is and the communication is 0. This paper shows 0 the difficulty of simultaneously achieving regret asymptotically better than kT and communication better than T . We give a novel algorithm? that for an oblivious adversary achieves a non-trivial trade-off: regret and communication  for any value of  We also consider a variant of the model, where the coordinator picks the expert. In this model, we show that the label-efficient forecaster of Cesa-Bianchi et al. (2005) already gives us strategy that is near optimal in regret vs communication trade-off.