Combinatorial partial monitoring game with linear feedback and its applications

In online learning, a player chooses actions to play and receives reward and feedback from the environment with the goal of maximizing her re-ward over time. In this paper, we propose the model of combinatorial partial monitoring games with linear feedback, a model which simultane-ously addresses limited feedback, infinite out-come space of the environment and exponential-ly large action space of the player. We present the Global Confidence Bound (GCB) algorithm, which integrates ideas from both combinatorial multi-armed bandits and finite partial monitoring games to handle all the above issues. GCB only requires feedback on a small set of actions and achieves O(T 2 3 log T) distribution-independent regret and O(log T) distribution-dependent re-gret (the latter assuming unique optimal action), where T is the total time steps played. More-over, the regret bounds only depend linearly on log |X | rather than |X |, where X is the action space. GCB isolates offline optimization tasks from online learning and avoids explicit enumer-ation of all actions in the online learning part. We demonstrate that our model and algorithm can be applied to a crowdsourcing application leading to both an efficient learning algorithm and low re-gret, and argue that they can be applied to a wide range of combinatorial applications constrained with limited feedback.