of the paper:
Strengths: 1) To the best of my knowledge, the problem investigated in the paper is original in the sense that top-m identification has not been studied in the misspecified setting. 2) The paper provides some interesting results:
i) (Section 3.1) Knowing the level of misspecification ε
is a key ingredient, as not knowing the same would yield sample complexity bounds which are no better than the bound obtainable from unstructured ( ε = ∞
) stochastic bandits. ii) A single no-regret learner is used for the sampling strategy instead of assigning a learner for each of the (N choose k) answers, thus exponentially reducing the number of online learners. iii) The proposed decision rules are shown to match the prescribed lower bound asymptotically. 3) Sufficient experimental validation is provided to showcase the empirical performance of the prescribed decision rules.
Weaknesses: Some of the explanations provided by the authors are a bit unclear to me. Specifically, I have the following questions: 1) IMO, a better explanation of investigating top-m identification in this setting is required. Specifically, in this setting, we could readily convert the problem to the general top-m identification by appending the constant 1 to the features (converting them into d + 1
dimensional features) and trying to estimate the misspecifications η
in the higher dimensional space. Why is that disadvantageous?
Can the authors explain how the lower bound in Theorem 1 explicitly captures the effect of the upper bound on misspecification ε
? The relationship could be shown, for instance, by providing an example of a particular bandit environment (say, Gaussian bandits) ala [Kaufmann2016].
Sample complexity: Theorem 2 states the sample complexity in a very abstract way; it provides an equation which needs to be solved in order to get an explicit expression of the sample complexity. In order to make a comparison, the authors then mention that the unstructured confidence interval β t , δ u n s
is approximately log ⁡ ( 1 δ )
in the limit of δ → 0
, which is then used to argue that the sample complexity of MISLID is asymptotically optimal. However, β t , δ u n s
also depends on t
. In fact, my understanding is that as δ
goes to 0
, the stopping time t
goes to infinity, where it is not clear as to what value the overall expression β t , δ u n s
converges. Overall, I feel that the authors need to explicate the sample complexity a bit more. My suggestions are: can the authors find a solution to equation (5) (or at least an upper bound on the solution for different regimes of ε
)? Using such an upper bound, even if the authors could give an explicit expression of the (asymptotic) sample complexity and show how it compares to the lower bound, it would be a great contribution.
Looking at Figure 1A (the second figure from the left, for the case of ε = 2
), it looks like LinGapE outperforms MISLID in terms of average sample complexity. Please correct me if I’m missing something, but if what I understand is correct, then why use MISLID and not LinGapE?
Probable typo: Line 211: Should it be θ
instead of θ t
for the self-normalized concentration?
The authors have explained the limitations of the investigation in Section 6.
2) The paper provides some interesting results: i) (Section 3.1) Knowing the level of misspecification ε is a key ingredient, as not knowing the same would yield sample complexity bounds which are no better than the bound obtainable from unstructured ( ε = ∞ ) stochastic bandits. ii) A single no-regret learner is used for the sampling strategy instead of assigning a learner for each of the (N choose k) answers, thus exponentially reducing the number of online learners. iii) The proposed decision rules are shown to match the prescribed lower bound asymptotically.