Abstract

We study two problems of online learning under restricted information access. In the first problem, prediction with limited advice, we consider a game of prediction with expert advice, where on each round of the game we query the advice of a subset of M out of N experts. q We present  an algorithm that achieves regret on T rounds of this game. The second problem, the multiarmed bandit with paid observations, is a variant of the adversarial N -armed bandit game, where on round t of the game we can observe the reward of any number of arms, but each observation has  c. We present an algorithm a cost that achieves regret on T rounds of this game in the worst case. Furthermore, we present a number of refinements that treat armand time-dependent observation costs and achieve lower regret under benign conditions. We present lower bounds that show that, apart from the logarithmic factors, the worst-case regret bounds cannot be improved.