Timezone: »

Efficient Partial Monitoring with Prior Information
Hastagiri P Vanchinathan · Gábor Bartók · Andreas Krause

Tue Dec 09 04:00 PM -- 08:59 PM (PST) @ Level 2, room 210D

Partial monitoring is a general model for online learning with limited feedback: a learner chooses actions in a sequential manner while an opponent chooses outcomes. In every round, the learner suffers some loss and receives some feedback based on the action and the outcome. The goal of the learner is to minimize her cumulative loss. Applications range from dynamic pricing to label-efficient prediction to dueling bandits. In this paper, we assume that we are given some prior information about the distribution based on which the opponent generates the outcomes. We propose BPM, a family of new efficient algorithms whose core is to track the outcome distribution with an ellipsoid centered around the estimated distribution. We show that our algorithm provably enjoys near-optimal regret rate for locally observable partial-monitoring problems against stochastic opponents. As demonstrated with experiments on synthetic as well as real-world data, the algorithm outperforms previous approaches, even for very uninformed priors, with an order of magnitude smaller regret and lower running time.

Author Information

Hastagiri P Vanchinathan (1plusX)
Gábor Bartók (Google Zürich)
Andreas Krause (ETH Zurich)

More from the Same Authors