Efficient Partial Monitoring with Prior Information
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.
Summary=============The paper proposes a novel algorithm for the problem of online learning with partial monitoring against a stochastic adversary. The proposed algorithm (BPM) can incorporate a prior in the form of a Gaussian distribution over the parameter defining the outcome distribution. This Gaussian assumption is only used to define the algorithm, while its regret performance is analyzed for any possible outcome distribution. The regret analysis shows that BPM achieves similar performance as existing algorithms, while an empirical study on synthetic and real data shows a significant advantage both computationally and in terms of the regret.Quality==============The paper is of very good quality in general.1- The algorithm is very simple, since it boils down in computing a Gaussian posterior over a linear model and the selection rules are clear and well motivated as well. The only aspect which is not discussed in a rigorous way its the computational cost of the algorithm compared to existing algorithms. In fact, BPM still requires to invert a MxM matrix at each step and the selection rule BPM-LEAST requires a random sampling since its actual exact implementation is computationally very heavy.2- Although the theoretical analysis matches existing results, it is useful in assessing the soundness of BPM (at least in its BPM-LEAST variant). There are only a couple of aspects that I would ask the authors to comment in more detail:a- The regret is studied only in the case of locally observable games. What is the regret in case a non locally observable games? Is it possible to achieve the T^{2/3} regret for "hard" problems? This part is covered by the experiments but a theoretical comment would be useful.b- In the statement of Thm. 1, C is a problem-dependent quantity. It would useful to make explicit the characteristics of the problem contributing to C.c- The Thm. 2 used in the proof is defined for any *fixed* sequence of matrices. In the case of BPM the quantity X_s is random with dependence on the actions selected in the past. It seems like this may pose a problem since the samples are not iid anymore (which would require an Azuma version of the statement) and additional dependencies on the dimensionality of X_s may appear (in the same flavor as in the Lemma inYasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems (NIPS), 2011.It'd be great if the authors could explain whether this is the case or whether Thm.2 is indeed enough.3- In the experiments the authors consider non locally observable problems and show a significant improvement w.r.t. the state of the art with a much smaller regret in all the synthetic data considered in Section 5.2. The other interesting aspect is that a pseudo-real-data experiment is run. I call it "pseudo" since data are real but the experiment is still generated artificially from the data. Nonetheless, I think it is a significant result. The only thing which is really surprising is the difference in performance between the two variants of PBM. What is your explanation for it?Clarity==============The paper is well written and clear.Originality==============The idea used in the paper is not very original since it reuses tools available in the literature. Nonetheless, the result is novel enough.Significance==============Overall the result is significant since it provides an efficient and easy algorithm to solve the challenging problem of partial monitoring in online learning. Preliminary results including real data support the fact that the algorithm may find application in real problems.