Phased Exploration with Greedy Exploitation in Stochastic Combinatorial Partial Monitoring Games
Partial monitoring games are repeated games where the learner receives feedback that might be different from adversary's move or even the reward gained by the learner. Recently, a general model of combinatorial partial monitoring (CPM) games was proposed [1], where the learner's action space can be exponentially large and adversary samples its moves from a bounded, continuous space, according to a fixed distribution. The paper gave a confidence bound based algorithm (GCB) that achieves O(T 2/3 log T ) distribution independent and O(log T ) distribution dependent regret bounds. The implementation of their algorithm depends on two separate offline oracles and the distribution dependent regret additionally requires existence of a unique optimal action for the learner. Adopting their CPM model, our first contribution is a Phased Exploration with Greedy Exploitation (PEGE) algorithmic framework for the problem. Different algorithms within the framework achieve O(T 2/3 √ log T ) distribution independent and O(log 2 T ) distribution dependent regret respectively. Crucially, our framework needs only the simpler "argmax" oracle from GCB and the distribution dependent regret does not require existence of a unique optimal action. Our second contribution is another algorithm, PEGE2, which combines gap estimation with a PEGE algorithm, to achieve an O(log T ) regret bound, matching the GCB guarantee but removing the dependence on size of the learner's action space. However, like GCB, PEGE2 requires access to both offline oracles and the existence of a unique optimal action. Finally, we discuss how our algorithm can be efficiently applied to a CPM problem of practical interest: namely, online ranking with feedback at the top.
The paper considers partial monitoring in the stochastic combinatorial setting with linear feedback mechanism, the version of the original problem that was introduced by Lin et al. in [1], and improves on some of the results in [1]. In particular, the paper proposes two algorithms, PEGE and PEGE2, for globally observable problems, both of which avoids some (but not all!) of the limitations of algorithm GCB of [1], including uniqueness constraint of the optimum, having access to oracles that solve (potentially) hard optimization tasks, and having a sample complexity that depends on the size of the action space.
The advantages of the PEGE algorithms, compared to GCB is that - they do not require an oracle that returns the second best solution of an optimization problem - they do not require the uniqueness of the optimal solution - their regret do not depend on the size of the action set. The disadvantages of the PEGE algorithms, compared to GCB are that - the claimed distribution dependent bound requires setting parameter h so that it satisfies some distribution-dependent conditions, which is not clear how to do efficiently if the parameters of the problem are not known - the distribution dependent bound has worse dependence on the time horizon T, and has an extremely bad (exponential) dependence on h. - to guarantee the claimed distribution dependent bounds requires different parameter setting than to guarantee the claimed distribution independent bounds.  The issue with parameter h is a serious one, and thus the paper proposes a solution to it in form of another algorithm, PEGE2. However, the obtained algorithm does not provide a satisfactory solution to this issue, and suffers from other shortcomings too, as discussed below. Advantages, compared to GCB: - its regret does not depend on the size of the action set Disadvantages, compared to GCB: - the distribution dependent bound is not guaranteed in every case (see Equation (7)). It is not clear what kind of distribution dependent bound can be guaranteed in general.  Finally, none of the proposed algorithms can avoid solving linear optimization problems in every step.  In view of this, the results in the paper should be considered as interesting additions to our knowledge of the combinatorial partial monitoring problem, but it is not clear whether they take us any closer to an actual, effective solution of the problem. In particular, the obtained distribution dependent bounds seem particularly week. The strongest part, however, seems to be that the regret bounds do not depend on the size of the action set any more. It would be nice to highlight the main idea behind this in the main part of the paper.   Additional remarks - The paper could benefit from adding a formal (algorithm-like) presentation of the protocol. - Please make it explicit that sigma in line 4 of Algorithm 1 is the globally observable set. - The remark in lines 176-180 is confusing. In what sense is the bound in [6] less explicit? Additionally, there should be an "is" between "in" and "not" in line 177. - Why do you introduce \delta, when it is always set to 1/T? - When adapting the combinatorial partial monitoring games to online ranking, how do the obtained results compare to existing methods? - "note -ve sign" in line 304 seems to be a typo. - Citation 4 in line 317 does not have all the authors names.