Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors consider a popular multi-armed bandit setting. Working in the fixed-confidence setting, they focus on the problem of the identification of $m$ arms corresponding to the largest means for a given error rate $\delta$ with the goal of minimizing the sample complexity for a fixed error rate. The authors focus on the misspecified linear bandit setting, establish results concerning sample complexity and the scale of misspecification, and design an algorithm for Top-$m$ identification in misspecified linear bandit setting.  
main_review: The paper seems to represent a well-written and solid piece of work. However, being a non-expert in the area, it is hard for me to assess the novelty and significance of its contribution to the community.
limitations_and_societal_impact: The authors clearly state the contributions of their work and allocate a significant part of the paper to discussing the limitations of the proposed algorithm which also possibly opens up directions for future research.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper investigates the problem of top-m identification for misspecified linear bandits. Specifically, the reward samples, contrary to the setting in linear bandits, is assumed to be translated by unknown misspecifications, and the goal is to identify any subset of cardinality $$m$$ of arms having the highest mean rewards. An upper bound on the maximum possible misspecification $$\varepsilon$$ is assumed, and sequential design rules in the form of a sequence of estimators, arm selection rules and measurable stopping rules are proposed. The sequence of estimators comprise the sample means of each arm, followed by the projection of the estimated means on to the set of realizable models. The arm selection rules involve a no-regret learner to generate a distribution for sampling the next action. The stopping rule is a confidence-interval based decision where the confidence interval is a trade-off between the concentration rate due to unstructured (stochastic) bandits and linear bandits, where the trade-off is guided by the level of misspecification $$\varepsilon$$. A tractable lower bound is derived developing on the existing lower bounds on the sample complexity of stochastic bandits, and the proposed decision rules are shown to yield an asymptotically optimal sample complexity.
main_review: Following are the strengths and weaknesses 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 $$\varepsilon$$ is a key ingredient, as not knowing the same would yield sample complexity bounds which are no better than the bound obtainable from unstructured ($$\varepsilon=\infty$$) 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 $$\eta$$ in the higher dimensional space. Why is that disadvantageous?

2)	Can the authors explain how the lower bound in Theorem 1 explicitly captures the effect of the upper bound on misspecification $$\varepsilon$$? The relationship could be shown, for instance, by providing an example of a particular bandit environment (say, Gaussian bandits) ala [Kaufmann2016]. 

3)	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 $$\beta_{t,\delta}^{uns}$$ is approximately $$\log(\frac{1}{\delta})$$ in the limit of $$\delta\rightarrow 0$$, which is then used to argue that the sample complexity of MISLID is asymptotically optimal. However, $$\beta_{t,\delta}^{uns}$$ also depends on $$t$$. In fact, my understanding is that as $$\delta$$ goes to $$0$$, the stopping time $$t$$ goes to infinity, where it is not clear as to what value the overall expression $$\beta_{t,\delta}^{uns}$$ 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 $$\varepsilon$$)? 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. 

4)	Looking at Figure 1A (the second figure from the left, for the case of $$\varepsilon=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 $$\theta$$ instead of $$\theta_t$$ for the self-normalized concentration?

limitations_and_societal_impact: The authors have explained the limitations of the investigation in Section 6.
review_title: null

final_score: rating: 4: Ok but not good enough - rejection
review_content: summary: The paper deals with Misspecification In Fixed-Confidence Linear Top-m Identification. The authors define the problem of identifying thee best subset of size m in a K-armed contextual bandits and present a lower bound on the sample complexity. They also present an algorithm (MisLid) to solve the problem and analyse its correctness and establish an upper bound on its sample complexity. Finally, the authors support their claim by running experiments.
main_review: 
The paper presents some interesting results, but I find the following shortcomings:

I feel the term "misspecification" does not carry much significance to the problem setup; given that the algorithm has access to the upper bound of the additive misspecification parameter $\eta$, it could be conveniently absorbed into the random noise. Finally, the motivation behind the presented problem setup is not adequate.
 
The intuition and the high-level ideas behind the proof for lower bound on the sample complexity (Theorem 1) are unclear. A comparison of the presented lower bound with the existing results would help a lot.

The main paper does not provide any intuition behind proof of correctness for the algorithm MisLid.

The upper bound on sample complexity presented in Theorem 2 is not explicit; however, the following paragraph and Appendix E explains its asymptotic nature. A comparison of the upper bound with the existing results is very much needed.

In the experiment section it seems that LinGapE incurs almost similar samples as MisLId, thereby the advantage of the latter is not unclear. Further, in Figure 2, the rationale behind setting $\delta=1$ for LinGapE is not apparent.

limitations_and_societal_impact: I feel the presented motivation behind the problem setup is inadequate.
review_title: null

Meta-review: The paper studies a best-subset identification problem (top-m or top-k identification) in a bandit setting with linear function approximation. The twist is that the linear model is misspecified, so that existing results do not directly apply (of course misspecification is common in practice, which is the primary motivation).

The end results are novel, but the reviewers and I felt that the work does not have much technical depth beyond (carefully) combining techniques from online linear bandits with misspecification and the body of work on best arm identification. As such, we do not think the paper is ready for publication at this time. 

Decision: Accept (Poster)