On Top-k Selection in Multi-Armed Bandits and Hidden Bipartite Graphs
This paper discusses how to efficiently choose from n unknown distributions the k ones whose means are the greatest by a certain metric, up to a small relative error. We study the topic under two standard settings-multi-armed bandits and hidden bipartite graphs-which differ in the nature of the input distributions. In the former setting, each distribution can be sampled (in the i.i.d. manner) an arbitrary number of times, whereas in the latter, each distribution is defined on a population of a finite size m (and hence, is fully revealed after m samples). For both settings, we prove lower bounds on the total number of samples needed, and propose optimal algorithms whose sample complexities match those lower bounds.
Summary - - - - - - -This paper studies the problem of finding the top k (out of n) arms (the k arms with the highest mean) in multi-armed bandits fixed confidence setting. More specifically, the goal is to derive an algorithm that with the smallest number of pulls returns a set of k arms such that with high probability (w.p. \geq 1-\delta)1) for each 1 \leq i \leq k, the mean of the i'th arm in the set is larger than (1-\epsilon) times the mean of the i'th arm (overall).  2) the average mean of the arms returned by the algorithm is larger than (1-\epsilon) times the average mean of the top k arms. The above settings are different and more general than those have been considered in the multi-armed bandits fixed confidence pure exploration literature (e.g., the work by Kalyanakrishnan et al., 2012 and the one by Gabillon et al, 2012), in the sense that the algorithms in those papers guarantee that every arm they return is (\epsilon,k)-optimal (the mean of every arm returned is not smaller than the mean of the k'th best arm minus \epsilon, with high probability).  For each of the above two problems, the authors present an algorithm and prove an upper-bound and a matching lower-bound for it. The authors motivate these two settings with the problem of crowdsourcing. The authors also show how their algorithm for the first problem should be changed to solve the same problem with additive instead of multiplicative guarantee (the mean of the i'th arm plus \epsilon instead of (1-\epsilon) times the mean of the i'th arm). Then the authors focus on the problem of exploring hidden bipartite graphs and state two problems, similar to those stated above. These two graph problems can be easily reduced to the two problems above, and thus, the algorithms for those problems can be easily used here. The only contribution in this part of the paper is the derivation of a lower-bound for each of these two graph problems.   Comments - - - - - - - -- The paper is well-written and is easy to follow. - To the best of my knowledge, the formulation considered in this paper is novel. The objective functions studied here (in Problems 1 and 2), although close, are different than those studied in the literature of pure exploration multi-armed bandits with fixed confidence. They are different in two senses: 1) the mean of each returned arm should be close to the mean of a specific top k arm (instead of being close to the mean of the k'th arm), and 2) the guarantee is multiplicative instead of additive ((1-\epsilon) times the mean of the i'th arm instead of the mean of the i'th arm plus \epsilon). The first difference could play an important role in the case where there exists many arms whose mean is in [\theta_k(B) - \epsilon, \theta_k(B)]. In this case, the existing (\epsilon,k)-optimal algorithms may return k arms, none of them among the top k, while this is not the case for the algorithm proposed in this paper. The authors have a discussion (on Pages 2 and 3) on the significance of multiplicative guarantee and mention its importance when the optimal solution is very small, which is apparently the case in many hidden graph problems. This is a good reason to consider multiplicative guarantee in addition to additive. They also discuss how we can define \epsilon'=\epsilon\theta_k(B), and use algorithms for additive guarantee to have multiplicative guarantee.  - In addition to the objective function, there is a very important difference between the top-k algorithms in the literature (e.g., the work by Kalyanakrishnan et al., 2012 and the one by Gabillon et al, 2012) and the one here, which is in the bound when the complexity appears in their bounds instead of 1 / \epsilon^2*\theta_k(B). This means that the bounds of the existing methods can be much tighter than the one for the algorithm in this paper. This is the main reason that those algorithms are more complex than the racing type algorithms presented in this paper. My main criticism about this work is the lack of discussion about this issue. As I mentioned above I admit that the formulation considered in the paper is novel, but the authors have considered the simplest approach (the racing type algorithms) and of course their bound is of the form 1 / \epsilon^2\theta_k(B). I think it would be possible to make the complexity appear in the bound for the problems considered in this paper, of course (probably) not by the type of algorithms considered here. It would be great if the authors make this difference clear and discuss the difficulties of having algorithms with the complexity in their bounds for the problems studied in this paper. Why didn't the authors derived algorithms of that form? - Why the proposed algorithms use the empirical mean based on the uniform allocation at that specific iteration instead of the empirical mean based on all the available samples from that arm? Is this just because of simplifying the proof and theory or has other reasons? Please clarify.   Minor Comments - - - - - - - - - - - -  - Line 102: "instead an additive" should be "instead of an additive". - Why the guess for the value of the mean of the k'th arm (\mu) starts at \mu=1 in ME-AS and QE-AS algorithms? This seems to be useless since \hat{\theta}^{US}(a_k) will never be greater than 2*\mu=2. I guess it should start at 1/2.