Dealing With Misspecification In Fixed-Confidence Linear Top-m Identification
Authors: Clémence Réda
Andrea Tirinzoni
Rémy Degenne
Venue: NeurIPS 2021 Poster (2021)
Keywords: misspecification
linear bandits
fixed-confidence top-m identification
pure exploration
recommendation systems
multi-armed bandits

Abstract: We study the problem of the identification of m arms with largest means under a fixed error rate $\delta$ (fixed-confidence Top-m identification), for misspecified linear bandit models. This problem is motivated by practical applications, especially in medicine and recommendation systems, where linear models are popular due to their simplicity and the existence of efficient algorithms, but in which data inevitably deviates from linearity. In this work, we first derive a tractable lower bound on the sample complexity of any $\delta$-correct algorithm for the general Top-m identification problem. We show that knowing the scale of the deviation from linearity is necessary to exploit the structure of the problem. We then describe the first algorithm for this setting, which is both practical and adapts to the amount of misspecification. We derive an upper bound to its sample complexity which confirms this adaptivity and that matches the lower bound when $\delta \rightarrow 0$. Finally, we evaluate our algorithm on both synthetic and real-world data, showing competitive performance with respect to existing baselines.

Dealing With Misspecification In Fixed-Confidene Linear Top-m Identification
Clémence Réda
Université de Paris, NeuroDiderot, Inserm, F-75019 Paris, France clemence. reda@inria.fr
Andrea Tirinzoni
Univ. Lille, Inria, CNRS, Centrale Lille. UMR 9189 CRISIAL, F-59000 Lille, France andrea. wirinzoni@inria.....
Rémy Degenne
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRIStAL, F-59000 Lille, France remy. degennecinria.fr
Abstract
We study the problem of the identification of arms with largest means under a fixed error rate 8 (tixed-confidence Top-m identification), for misspecified linear bandit models. This problem is motivated by practical applications, especially in medicine and recommendation systems, where linear models are popular due their simplicity and the existence of efficient algorithms, but in which data inevitably deviates from linearity. In this work, we first derive tractable lower bound on the sample complexity of any 8-correct algorithm identification problem. We show that knowing the scale of the deviation from linearity necessary to exploit the structure of the problem. We then describe the first algorithm for this setting, which is both practical and adapts to the amount misspecification. We derive an upper bound to its sample complexity which confirms this adaptivity and that matches the lower bound when 8 - 0. Finally, we evaluate our algorithm on both synthetic and real-world data, showing competitive performance with respect to existing baselines.
the general Top-m
Introduction
The multi-armed bandit (MAB) is a popular framework to model sequential decision making problems. At each round t. O, learner chooses an arm k among finite of K E N possible options, and it receives a random reward X E R drawn from a distribution & with unknown mean μ* Among the many problem settings studied in this context, we focus on pure exploration, where the learner aims maximizing the information gain for answering a given query about the arms [5]. In particular, we are interested in finding a subset m 2 arms with largest expected reward, which is known as the Top-m identification problem [22]. This generalizes the widely-studied best-arm (i.c.. Top-1) identification problem [16]. This problem has several important applications, including online recommendation and drug repurposing [31, 35]. Two objectives are typically studied. On the one hand, in the fixed-budget setting [2], the learner is given a finite amount of samples and must return subset of m best arms while minimizing the probability of error in identification. On the other hand, in the fixed-confident confidence setting [16], the learner aims at minimizing the sample complexity for returning subset of m best arms with a fixed maximum error rate 6 E (0, 1), defined as the number of samples collected before the algorithm stops. This paper focuses on the latter.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In practice, information about the arms is typically available (e.g., the characteristics of an item in recommendation system. or the influence of drug on protein production in a clinical application). This side information influence the expected rewards of the arms, thus adding structure (i.e., prior knowledge) to the problem. This is in contrast to the classic unstructured MAB setting, where the learner has no prior knowledge about the arms. Due to their simplicity and flexibility, linear models have become the most popular to represent this structure. Formally, in the linear bandit setting [3], the mean reward μ² of each arm k E [K] == {1, ...,, }} is assumed to be an inner product between known d-dimensional arm features Φx E IR and an unknown parameter 0 E R This model has led to many provably-effieieee algorithms for both best-arm [38, 42, 17, 43, 13] and Top-m identification [24, 35]. Unfortunately, the strong guarantees provided by these algorithms hold only when the expected rewards are perfectly linear in the given features, property that is often violated in real- wolld applications. In fact, when using linear models with real data, one inevitably faces the problem of misspecification, i.c., the situation in which the data deviates from linearity.
A misspecified linear bandit model is often described as a linear bandit model with an additive term to encode deviation from linearity. Formally, the expected reward μ² 0 + 17 of each arm & E [K] can be decomposed into its linear part $. 9 and its misspecification ry R. Note the flexibility of this model: for ||>]|| = O, where n = In' 172
.......... ...,, " the problem is perfectly linear and thus highly structured, as the mean rewards of different arms are related through the common parameter 0; whereas when the misspecification vector 1) large in all components, the problem reduces to an unstructured one, since knowing the linear part alone provides almost no information about the expected rewards. Learning in this setting thus requires adapting to the scale of misspecification. typically under the assumption that some information about the latter is known (e.g., an upper bound 8 to [n]]). Due to its importance, this problem has recently gained increasing attention in the bandit community for regret minimization [20, 29, 18, 33, 39]. However it has not been addressed in the context of pure exploration. In this paper, we take a step towards bridging this gap by studying fixed-coniience Top-m identification in the context of misspecified linear bandits. Our detailed contributions are as follows.
Contributions. (I) We derive a tractable lower bound on the sample complexity of any 8-correct algorithm for the general Top-m identification problem. (2) Leveraging this lower bound, we show that knowing an upper bound to ||,]|| is necessary for adapting to the scale of misspecification, in the sense that any 8-correct algorithm without such information cannot achieve a better sample complexity than that obtainable when no structure is available. (3) We design the first algorithm for Top-m identification in misspecified linear bandits. We derive an upper bound to its sample complexity that holds for any 5 E (0, 1) and that matches our lower bound for ő -> O. Notably, our analysis reveals a nice adaptation to the value of e, recovering sate-of-thhe-ane dependences in the linear case (e = 0), where the sample complexity scales polynomially in d and not in K, and in the unstructured case (5 large), where only polynomial terms in K appear. (4) We evaluate our algorithm on synthetic problems and real datasets from drug repurposing and recommendation system applications, while showing competitive performance with state-of thetherrrt methods
Related work. While model misspecificationn has not been addressed in the pure exploration literature, several attempts to tackle this problem in the context of regret minimization exist. In [20], the authors show that, if T is the learning horizon, for any bandit algorithm which enjoys (dd regret scaling on linear models, there exists a misspecified instance where the regret is necessarily linear. As a workaround, the authors design a statistical test based on sampling a subset of arms prior to learning to decide whether linear or an unstructured bandit algorithm should be run on the data. Similar ideas are presented in [8], where the authors design a sequential test to switch online between linear and unstructured models. More recently, elimination-basel algorithms [29, 39] and model selection methods [33, 18] have attracted increasing attention. Notably, these algorithms adapt to the amount of misspecificatiion without knowing it beforehand, at the cost of an additive linear term that scales with e. Moreover, while best-arm identification has been the focus of many prior works in the realizable linear setting, some suggesting syymptotically-ppiime algorithms [13, 21]. Top-m identification has been seldom studied in terms of Top-m problem have been derived previously, focusing on explicit bounds [26], on getting the correct dependence in the problem parameters for any confidence [9, 37], or on asymptotic optimality (as 8 0) [19]. Because of the combinatorial nature of the Top-m identification problem, obtaining tractable, tight, problem-dependdnt lower bound is not straightforward.
dependent lower bounds. Lower bounds for the unstructured
2

---

2 Setting
At successive stages & N, the learner samples an arm k E [K] based on previous observations and internal randomization (a random variable U2 E [o, 1]) and observes a reward X Let J, ((U1, , Xx rewards until time 1. Then k, is Fi-1-measurable random variable. The reward X is sampled from v and is independent of all past observations, conditionally on kg. We suppose that the noise is Gaussian with variance 1, such that the observation when pulling arm Ke at time i is X ~ NN 1). The mean vector = (EE))][ E IR then fully describes the reward distributions.
..... U, kt, X Ut+1)) be the o-algebra associated with past sampled arms and
In a misspecified linear bandit, each arm & E [K] is described by a feature vector ΦR E R The corresponding feature matrix is denoted by A := 00,.,,...... Φx] E R and the maximum lg -norm of these vectors is L == maX | We assume that the feature vectors span R" (otherwise we could rewrite those vectors in a subspace of smaller dimension). We assume that the learner is provided with a set of realizable models
M = { E RK| 30 e R En E RK μ +0+ A |Allo S M A Inll S
(I)
where M, E I. are known upper bounds on the e -orm of the mean' and misspecification vectors, respectively. Intuitively, .M represents the set of bandit models whose mean vector μu is linear in the features A only up to some misspecification 77.
We consider Top-m identification in the fixed-confidence setting. Given a confidence parameter 5 E (0, 1), the learner is required to output the m [K] arms of the unknown bandit model μ M with highest means with probability at least 1 - 8. The strategy of a bandit algorithm designed for Top-m identification can be decomposed into three rules: a sampling rule, which selects the arm k; to sample at a given learning round according to past observations; a slopping rule, which determines the end of the learning phase, and is stopping time with respect to the filtration (Fi))so,, denoted by Ts; finally, decision rule, which returns Fr, measurable answer the pure exploration problem. An answer is set S. [K] with exactly arms: | = m. In our context, the "m best arms of p² might not be well defined since the set S* (p² == { E [K] μe 2 max μ ) might contain more than m elements if some arms have the same mean. Thus, let Sm (p) = {S S 5* (1) |S] = m) be the set containing all subsets of m elements of S (p)).
Definition (5-correctness). For 5 E (0, 1), we say that an algorithm 21 is 8-correct on M if, for all E M, To < too almost surely and 1 (S. & Sm(()) 6.
3 Tractable lower bound for the general Top-m identification problem
Let N denote the number of times arm has been sampled until time included. Suppose that the true model μ has exactly m arms that are among the top-m, iee, that (S* (14) = m and S., (1)) (S' (m)).
Consider the following set of alternatives to μ,,
(4) = {A M (A) n 0}
that is, the set of all bandit models À in M where the top-m arms of μr are not among the top-m arms of X. Note that, while we assumed that the set of top-m arms in j is unique, this might not be the case for A. Define the event F.,, {Smm E Sm)) that the answer returned by the algorithm at T3 is correct for fa and consider any 5-correct algorithm M. Let us call KL. the Kullback- Leibler divergence and kl the binary relative entropy. Then, using the change-of-measuu argument proposed in [19, Theorem 1]. for any À E Am (4) and < 1/2,
Σ kE[K]
E KL A*) kl (F (E.)),
Z kl(1 6, Z log
2.45
1 'The restriction ||2.|/c < M is required only for analysis, while it can be safely dropped in practice.
The expression max (1) denotes the th maximal value (f(i) i e S).
A We abuse notation denoting distributions in the same me-dimensional exponential family by their means.
3

---

where the second- inequality follows from the corrrectss of the algorithm and the monotonicity of the function kl. This holds for any X Am (p)), so we have that
sup inf WEAx
Σ AEAm (c) kE[K]
with WL (1* (ut,,,9))
log
1
(2)
2.46
with Ak := {p 10, Pk = 1 the simplex on [K]. We define the inverse complexity
Hy == Su imfxE (x) [K([K] KL (n* x²) Computing that lower bound might be diffi- cult: while the Dullback--eiblles is convex for Gaussians, the set (4) over which it is minimized is non-convex. Its description using (m(() is combinatorial: we can write Am (p) as a union convex sets, one for each subset of top-m arms of X, but this implies minimizing over (K) sets, which not practical. In order to rewrite this lower bound, we prove the following lemma in Appendix C.
Lemma 1. Vu, À E RK s.t. 1S (n)l m, Sn (A) = 9 + Di & (T) 3j E (1), > X.
Lemma allows us to go from an exponentially costly optimization problem, which implied mini- mizing over (k) sets, to optimizing across m K - m) halfspaces. Therefore, by replacing the set of alternative models as derived in Lemma 1, the lower bound in Equation 2 can be rewritten in the following more convenient form
Theorem 1. For any < 1/2, any 8-correct algorithum 2 on M. for any bandit instance E RR such that 1 (p)) = m, the following lower bound holds on the stopping time T8 of on instance ju:
E [T8] 2
inf wEAx (ES* jES XEMONSN
sup min
min
Σ kE[K]
WLLL (a* (ut,))))
log
1
2.45
Computing the lower bound now requires performing one maximization over the simplex (which can be still hard), and m(K - m) minimizations over half-spaces {) M X' > X}. where (i.j) E (S* (4)) x (w)). The minimizations are convex optimization problems and can be solved efficiently. Our algorithm inspired from that bound will need to perform only those minimizations.
Note that a lower bound for Top-m identification using the cited -faaaue argument has been obtained in [26]. Aiming to be more explicit, it relies on alternative models where one of the best arms is switched with the (m + 1)th best one (or one of the K - m worst ones with the m th best one). These models are strict subset of Am (u)) Hence this bound is not as tight the one in Theorem 1, which is why the algorithm we detail in the next sections will rely on the latter instead.
Note that with E = 0 and m = 1. this lower bound is exactly the one for best arm identification in perfectly linear models [17]. As the misspecification E grows, the set M becomes larger and so does the set of alternative models Am (H), thus the lower bound grows. In the limit + +oo, the model becomes the same as the unstructured model. We show that fact the lower bound becomes exactly equal to the unstructured lower bound as soon as Ep. finite value.
Lemma 2. There exists En R with en, S max; n² ming jºt such that if Ep. then the lower bound of Theorem is equal to the unstructured top-mn lower bound.
The proof in Appendix C. It considers finitely supported distributions over An (n) that realize the equilibrium in the max-min game of the lower bound. As soon as one of these equilibrium distributions for the unstructured problem has its whole support in the misspecified model, the two complexities are equal.
3.1 Adaptation to unknown misspecification is impossible
We now make important observation: knowing that a problem misspecified without knowing an upper bound E on |/7 is the same as not knowing anything about the structure of that problem.
The lower bound of Equation (2) is function of the set M of realizable models μ. Let B(u, 8, .M) be the hinht-hand side of that equation, such that E [Ta] 2 B(u, 8.M) for any algorithm 2 which is 8-correct on M. Suppose that we have Mj C M, subset of the model, for which we would like to have lower sample complexity (possibly at the cost of higher sample complexity on M \ M1). If

---

Algorithm 1 MISLID
Require: Set of models M, online learner L, stopping thresholds (82,81211 Compute a sequence of arms .i...., such that Díe Ok, = 2
// INITIALIZATION
for ( 1,...,,4 to do
Pull k,, receive X and set wi f- Cke end for
I/ PULL SPANNER
Compute empirical mean Pto and its projection Proo + arg min 1| Tito IB for = =o + t, + ...... do
if inf (innxeemm((-i)) ||i4- AIlaM 2,3 then
I/ STOPPING RULE
Stop and return S (Pe-1) end if
Obtain w. from & Compute closest alternative: d t- arg min (ãe-1) 11ñ4-1 AllBun
Update L with gain 9: EnE(K] wh (lit X + [ /
1/ UPDATE LEARNER ACTION SAMPLING I/ ESTIMATION
Pull h3 ~ wi and receive reward X,
Update Fy and compute projection b4 f- arg minxeM 1| - Fre p..lBbN.
end for
M is the misspecified linear model with deviation let us say that Mi is the set of problems with deviation lower than E < E that is, we want the algorithm to be faster on more linear models. This not achievable. The lower bound states that it is not possible for algorithm to have lower sample complexity on MM while being 5-correct on M. On every E M, the lower bound is B(,, 6, M).
An algorithm cannot adapt to the deviation to linearity: it has to use parameter set in advance, and its sample complexity will depend on that e, not on the actual deviation of the problem. Note that this observation does not contradict recent results for regret minimization [e.g., 29, 39], which show that adapting to an unknown scale of misspecification possible. In fact, such results involve "weak" form of adaptivity, where the algorithms provably leverage the linear structure at the price of suffering additive linear regret term of order O(evdl") where T is the learning horizon. Since the counterpart S-correctness for regret minimization is "the algorithm suffers sub-linear regret in T for all instances of the given family", this implies that algorithms with such "weak" adaptivity loose this important property of consistency.
The MISLID algorithm
We introduce MISLID (Misspecified Linear Identification), an algorithm to tackle misspecification in linear bandit models for fixed-confidence Top-m identification. We describe the algorithm in Section 4.1, while in Section 4.2 we report its sample complexity analysis.
4.1 Algorithm
The pseudocode of MISLID outlined Algorithm 1. On the one hand, the design of MISLID builds on top of recent approaches for constructing pure exploration algorithms from lower bounds [12, 13, 43, 21] J. On the other hand, its main components and their analysis introduce several technical novelties to deal with misspecified Top-m identification, that might be of independent interest for other settings. We describe these components below. Let us define D. = diag(e' ? ......K. for any vector E K and V4 == E.=1 Φk, oT,
Initialization phase. MISLID starts by pulling a deterministic sequence of to arms that make the minimum eigenvalue of the resulting design matrix Vo, larger than 2L".. Since the rows of span Rd, such sequence can be easily found by taking any subset of arms that span the whole space (e.g., by computing barycentric spanner [4]) and pulling them in a round robin fashion until the desired condition is met. This is required to make the design matrix invertible. While the literature typically avoid this step by regularizing (e.g., [l]), in misspecified setting it is crucial not to do
5

---

so to obtain tight concentration results for the estimator of as explained in the next paragraph. See Appendix D.1 for a discussion of the length to of that initialization phase.
Estimation. At each time step 1 2 lo. MISLID maintains an estimator t of the true bandit model This is obtained by first computing the empirical mean Pe. such that jit I E 1 (kg = kj X and then projecting it onto the family of realizable models MM according to the -N,-weighted norm, i.e. pe == arg min AEM || - pellBNN Since each À E M can be decomposed into X = A6' + rf for
NT.
some 0' E TR& and r E R.K this can he solved efficiently as the minimization of a quadratie objective in K + d variables subject to the linear constraints ||1/|| I and || + v'lloe S. The second constraint is only required for the analysis, while it often has a negligible impact in practice. Thus, we shall drop it in our implementation, which yields two independent optimization problems for the projection jı+ AO, + 1i: one for 0r, whose solution is available in closed form as the standard least-squares estimator 0, = Or V, -'=E X OR,, and one for nt. which is another quadratic program with K variables (see Appendix D).
A crucial component in the concentration of these estimators, and a key novelty of our work, is the adoption of an orthogonal parametrization of mean vectors. In particular, we leverage the following observation: any mean vector μ A0 + 1l can be equivalently represented, at any time 4, as A0; + Th, where 0, V Σ 1=** Φx. is the orthogonal projection (according to the design matrix Vi) of şt onto the feature space and 1): = μ - A0; is the residual. Then, is possible to show that |00 l2; is exactly the eeffnnormalized martingale considered in [i] and, thus, it enjoys the same bound we have in linear bandits with no misspecification (refer to Appendix B). This is an important advantage over prior works [29, 44] that, in order to concentrate 0, to 0. need to inflate the concentration rate by a factor s²t, which often makes the bound too large to be practical for misspecified models with 0. It allows us also avoid superlinear terms of the form e²t log(t) (t) which are present in related works and which would prevent us from deriving good problem- problem-dependent guarantees.
Stopping rule. MISLID uses the standard stopping rule adopted in most existing algorithms for pure exploration [19, 12, 36]. What makes it peculiar is the definition of the thresholds Se,a- MISLID requires a careful combination of concentration inequalities for (1) linear bandits, to make the algorithm adapt well to linear models with low e, and (2) unstructured bandits, to guarantee asymptotic optimality. The precise definition of Br,s is shown in the following result.
Lemma (MISLID is d-correct). Let W-1 be the negative branch of the Lambert W function and let W(x) ---1(-e--)) R x + log x. For 8 E (0, 1), define
2e
B = 2KW
log
+ log(8eK 1oog(8eKlogt). 2
(3)
2K
8
glin ==
1 AVie + v2
+ log z
1
+ (1+ log(1 15)
1
log 1
1 2d
log
(4)
x
Then, for the choice 3r,5 == m Bliy MISLID is 8-correct.
This result is a simple consequence of two (linear and unstructured) concentration inequalities. See Appendix F.
Sampling strategy and online learners. The sampling strategy of MISLID aims at achieving the optimal sample complexity from the lower bound in Theorem 1. As popularized by recent works [12, 13, 43], instead of relying on inefficient max- max-min oracles to repeatedly solve the optimization problem of Theorem 1 [17, 211. we compute it incrementally by employing no-regret online learners. At each step f, the learner C plays a distribution over arms W, E AK and it is updated with a gain function ge whose precise definition will be specified shortly. Then, MISLID directly samples the next arm pull from the distribution Wt. instead of using tracking as in the majority of previously mentioned works. Similarly to what was recently shown by [40] for regret minimization in linear bandits, sampling will be crucial in our analysis to reduce dependencies on and, in particular, to obtain only logarithmic dependencies in the realizable linear case.
Regarding the choice of C, two important properties are worth mentioning. First, MISLID requires only single learner, while existing asymptotically optimal algorithms for pure exploration [12, 13]

---

need to allocate one learner for each possible answer. Since the number of answers is (m), direct extension these algorithms to the Top-m setting would yield an impractical method with exponential (in K) number of learners, hence space complexity, and possibly sample complexity." Second, the choice of is highly flexible since any learner that satisfies the following property suffices.
Definition 2 (No-regret learner). A learner L over AK is said be no-regret if, for any 2 1 and any sequence of gains (ws) bounded in absolute value by B IR=,, there exists positive constant Cz(K, B) such that maX Σ (g 9s (w,)) & Cc(K,
Examples of algorithms in this class are Exponential Weights [7] and AdaHedge [15]. The latter shall be our choice for the implementation since does not use B parameter but adapts and thus does not suffer from a possibly loose bound on B.
Optimistic gains. Finally, need specify how the gains Ir computed. Clearly, if were known, one would directly use w + inf Ia All Since is un- known and must be estimated, we set ge(w) to an optimistic proxy for that quantity. In particular, we choose a sequence of bonuses (c] such that, with high probabil-
ity, ge(w)) = EnECK w/ ( - x + votz) N inf lll All for d ==
arg xeA, 1) | - Bl. As for the stopping thresholds, we construct of by care- ful combination of structured and unstructured concentration bounds:
& min (SLLK + e)²²²= + 4a,3 lim | (
20
4M²
N
where o.!n := B (55)) and a!th == ) + d dlog(1 + t/(2)) We show in Appendix F that
this choice of of suffices to guarantee optimism with high probability.
4.2 Sample complexity
Theorem 2. MISLID has expected sample complexity Ey([s] (T(o) + 2, where To(o) is the solution to the equation in
Bi, 2 tH + + minn +dvil, log K miimmminnn KL.) log log(1/0))
(5)
where 4, = log 1, Hµ is the inverse complexity appearing in the lower bound (see Equation 2), and of terms, each of which is O of one of the expressions shown.
Ö(a; b: represent
See Appendix for the proof. Since B ss log(1/5) for small ö, To(o) = - lgg)))((11)) (,o((og(1/))). where Cp. is dobleemddependett constant. Then lim inf [xT(T/] (tt//oog(///))) lim inf To( log(1/0) H1,1 and thus the upper bound matches the lower bound in that limit: MISLID is asymptotically optimal. The only polynomial factors in K are in a minimum with a term that depends on s. In the linear setting, when é = O, we have only logarithmic (and no polynomial) dependence on the number of arms, which is on par with the state of the art [40, 21, 27]. Moreover, the bound exhibits an adaptation to the value of E. If is small, then the minimums in Be, and in the inequality (5) are equal to the "linear" values which involve K and d instead of K. As grows, the upper bound transitions to terms matching the optimal unstructured bound.
Decoupling the stopping and sampling analyses. Our analysis decomposes into two parts: first, result on the stopping rule, then, a discussion of the sampling rule. The algorithm is shown to verify that, under favorable event, if it does not stop at time t,
2 inf ||u XI - O(Vi) 2 2tH, -(VI).
(f)
The sample complexity result is consequence of that bound on t. The first inequality is due solely the stopping rule, and the second one only to the sampling mechanism. The expression
'The fact that the optimization problem of the lower bound decomposes into m(K - -m) minimizations does not reduce the number of possible answers, which is still combinatorial in K.
7

---

infxes... (a) lp XI
DN, does not feature any variable specific to the algorithm: we can combine any stopping rule and any sampling rule, long they each verify the corresponding inequality.
more aggressive optimism. The optimistic gains that we have chosen, gr
Ene[K] w² (1Øt-1 - Mr1 + v(_1)², are tuned to ensure asymptotic optimality (with a factor I in the leading term). If we instead accept to be asymptotically optimal up to factor 2, we can use the gains (w( = Ene(K]] w/ (LAt_ x/)² d-1)) When using those, the learner takes decisions which are much closer to those it would take if using the empirical gains Exe(k] wh (p xb)² and the theoretical bound, while worse in the leading factor, has better lower order terms. The aggressive optimism sometimes has significantly better practical performance (see Experiment (C) in Figure 1).
5 Experimental evaluation
Since our algorithm is the first to apply to Top-m identification in misspecified linear models, we compare it against an efficient linear algorithm, LinGapE [42] (that is, its extension to Top-m as described in [35], which coincides with LinGapE for m 1). and an unstructured one, LUCB [23].
In all experiments, we consider 5 = 5%.- For each algorithm, we show boxplots reporting the average sample complexity on the y-axis, and the error frequency 8 across 500 (resp. 100) repetitions for simulated (resp. real-life) instances rounding up to the 5th decimal place. Individual outcomes are shown as gray dots. It has frequently been noted in the fixed-confidence literature that stopping thresholds which guarantee d-correctness tend to be too conservative and to yield empirical error frequencies that are actually much lower than d. Moreover, these thresholds are different from linear to unstructured models. In order to ensure a good trade-off between performance and computing speed, and fairness between tested algorithms, we use heuristic value for the stopping rule 3t,5 := In((1 + In(t + 1)) unless otherwise specified. For each experiment, we report the number of arms (K), the dimension of features (d), the size of the answer (m), the misspecification (e) and the gap between the mh and (m + 1)th best arms (A == _ax n²ah max 1n+1 μ²). The computational resources used, data licenses and further experimental details can be found in Appendix G.
(A) Simulated misspecified instances. (K = 10, = = 3, E (0,5), A R 0.28) First, we fix linear instance f4 := AO by randomly sampling the values of 0 E Rd and A E kxd from a zero-mean Gaussian distribution, and renormalizing them by their respective foo norm. Then, for E E 50, we build a misspecified linear instance μl A0 + ne, such that, if (4) is the index of the
fourth best arm, Vk + (4). n = O, and 1/ = e. Note that any value of E < A does not switch the third and fourth arms in the set of best arms of Mle contrary to values greater than A. The greater E is. the more different the answers from the linear and misspecified models are. This experiment was inspired by [20], where similar model is used to prove a lower bound in the setting of regret minimization. See the leftmost two plots on Figure 1. As expected, LUCB is always d-correct, but suffers from significantly larger sample complexity than its structured counterparts. Moreover, LinGapE does not preserve the d-correctness under large misspecification level e = (with error rate 5 = 0.96), which illustrates the effect of E on the answer set. Note that it is not due to the choice of stopping threshold, as running it with the theoreticalll-supportte an empirical error rate å = 1. MISL.D proves to be competitive against I LinGapE. Note that the case e = 0 is a perfectly linear instance. See Table 2 in Appendix for numerical results for algorithms LinGapE and MISLID.
threshold derived in [1] also yields
m 3, E E (0.5, 1, 2]. A x 0.4) MISLID erucially relies user-provided upper bound the scale of deviation from linearity. We test its robustness against perturbations to the input value E compared to the value e* : |l in the misspecified model μ A0 17. Values are sampled randomly for 8, A. n,, and the associated vectors are normalized by their goe norm (for 7), by /el)) where s* = > A is the true deviation to linearity. The results, shown in the third plot of Figure 1, display the behavior predicted by Lemma 2. Indeed, as the user- esor-provided value & increases, the associated sample complexity increases as well. The plateau in sample complexity when is large enough is noticeable. Cases E {1, 2} display a sample complexity close to that of unstructured bandits.
(B) Diserepancy between user-selected E and true ||^]|- (K = 15, d = m 3,
$ All the code and scripts available at https: //tp://gittt /ggggth.bbbb.. http://gtt....oererreaeeeeeeeeee
8

---

5000
means
5000
meons
30000
80000
Sample complesty.
Samee 2 2-400
4000
Somple tomgless
25000
20000
complesti
50000
2000
2000
15000
20000
2000
2000
10000
20000
1000
5000
Nisidd (.50
Sested to
Mistad te =2
Miald ideloutt)
Modid (agoressive)
a- Whila (empirical)
Luca Gw0.
Lidapt
0.0
MudLd 6we0
LUCB
LnGapp
0.34
Mulid dwa.
dwo.
5-60
d.00
Figure 1: Experiment (A) for E {0,5) 5) (first two from the left). Experiment (B) with = E {0.5, 1.2). Experiment (C) to compare different optimistic gains (right).
means
2500000
means
Sampo COP 5
2000000
500000
2300000
200000
1000000
300000
300000
LUCB
Mulid UnDapp
uucB 6 6.0.0
LinGapt 1.0
Misid 0.0.0
d.0.0
8.000
0.0
Figure 2: Experiment (D) for drug repurposing in epilepsy (left). Experiment (E) for online recom-
mendation.
(C) Comparing different optimisms. (K = 15, d d= m = 3, A 0.4) We use the same bandit model as in Experiment (B), and use = 5* described in Section 4.2, no optimism (that is, Ak E [K]. Vt > 0, 0,c² = 0), and the default optimistic gains given in Section 4.1. See the rightmost plot Figure The algorithm with no optimism is denoted "empirical", and is significantly faster than the optimistic variants.
We compare the aggressive optimism
(D) Application to drug repurposing, (K = 10, d 5, the drug repurposing problem for epilepsy proposed by [35] to investigate the practicality of our method. In order to speed up LUCB, we consider the PAC version of Top-m identification, choosing as stopping threshold 0.06 RV A, such that the algorithm stops earlier while returning the exact set of best arms. Following [34, Appendix F.4], we extract linear model from the data by fitting neural network and taking the features learned in the last layer. We compute é as the &o norm of the difference between the predictions of this linear model and the average rewards from the data, which yields é = 0.02. Since the misspecification is way below the minimum gap. and the linear model thus accurately fits the data, the results (lefumost plot in Figure 2) show that MisLid and LinGapE perform comparably on this instance. Moreover, both are an order of magnitude better than an unstructured bandit algorithm sample complexity-wist Please refer to Table in Appendix for numerical results for LinGapE and MISLID.
5, é z 0.02, A R 0.062) We use
(E) Application to a larger instance of online recommendation. (K 103, d = 8, m é Rv 0.206, A ~ 0.022) As in Experiment (D), a linear representation is extracted for an instance of online recommendation of music artists to users (Last.fm dataset [6]). We compute a proxy for e and feed the value A to the stopping threshold in LUCB in a similar fashion. Differently from Experiment (D), this yields a misspecification that is much larger than the minimum gap. To improve performance on these instances, we modified MISLID. To reduce the sample complexity, we use empirical gains instead of optimism. To reduce the computational complexity, we check the stopping rule infrequently (on a geometric grid) and use only a random subset of arms in each round to compute the sampling rule (see Appendix G for details and an empirical comparison to the theoretically supported MISLID). See the rightmost plot in Figure 2. This plot particularly illustrates our introductory claim: an unstructured bandit algorithm 8-correct, but too slow in practice for misspecified instances, whereas the guarantee on correctness for a linear bandit does not hold anymore on these models with large misspecification, Numerical results for LinGapE and MISLID are listed in Table in Appendix.
9

---

Discussion
We have designed the first algorithm to tackle misspecification in fixed-confidence Top-m identifica- tion, which has applications in online recommendation. However, the algorithm relies exclusively on the features provided in the input data, and as such might be subjected to bias and lack of fairness in its recommendation, depending on the dataset. The proposed algorithm can be applied to misspecified models which deviate from linearity (i.e., > 0), encompassing unstructured settings (for large values of s) and linear models (i.e., 8 =0) 0).
Our tests variants of algorithm suggest that the optimistic estimates have big influence the sample complexity. Removing the optimism completely and using the empirical gains leads to the best performance. We conjecture that other components of the algorithm like the learner are conservative enough for the optimism to be superfluous. The main limitation of our method is its computational complexity: at each round, ((K)) convex optimization problems need to be solved for both the sampling and stopping rules, which can be expensive if the number of arms is large. However, the "interesting" arms are much less numerous and we observed empirically that the sample complexity is not increased significantly if we consider only few arms. In general, theoretically supported methods to replace the alternative set by computationally simpler approximations would greatly help in reducing the computational cost of our algorithm.
Since the sampling our algorithm designed minimize a lower bound, we can expect to suffer from the same shortcomings as that bound. It is known that the bound in question does not capture some lower order (in 1/6) effects, in particular those due the multiple-hypothesis nature of the test we perform, which can be very large for small times. Work to take these effects into account to design algorithms has started recently [24, 25, 41] and we believe that it an essential avenue for further improvements in misspecified linear identification.
10

---

Acknowledgments and Disclosure of Funding
Clémence Réda was supported by the "Digital health challenge" Inserm-CNKs CNRS joint program, the French Ministry of Higher Education and Research [ENS. SOSRIITME-SALLLY19222. and the French National Research Agency [ANR- SANR-19-CE3, CE23-0026-04 (BOLD project).
References
[1] Abbasi-Yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. In Advances in Neural Information Processing Systems, pages 2312-2320.
[2] Audibert, J.-Y., Bubeck, S., and Munos, R. (2010). Best arm identification in multi-armes bandits. In COLT, pages 41-53.
[3] Auer, P. (2002). Using confidence bounds for exploitation-exploraiioo trade-offs. Journal of Machine Learning Research, 3(Nov):397-422.
[4] Awerbuch, B, and Kleinberg, R. (2008). Online linear optimization and adaptive routing. Journal of Computer and System Sciences, 74(1):97-114.
[5] Bubeck, S., Munos, R., and Stoltz, G. (2009). Pure exploration in multi-armed bandits problems. In International conference on Algorithmic learning theory, pages 23-37. Springer.
[6] Cantador, I., Brusilovsky, P., and Kuflik, T. (2011). Second workshop on information heterogene- ity and fusion in recommender systems (hetrec2011). pages 387-388.
[7] Cesa-Bianchi, N. and Lugosi, G. (2006). Prediction, learning, and games. Cambridge university press.
[8] Chatterji, N. S., Muthukumar, V., and Bartlett, P. L. (2020). OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits. In AISTATS, volume 108 of Proceedings of Machine Learning Research, pages
PMLR.
[9] Chen, L., Li, and Qiao, M. (2017), Nearly instance optimal sample complexity bounds for top-k arm selection. In Artificial Intellignnce and Statistics, pages 101-110. PMLR.
[10] De Rooij, S., Van Erven, T., Grünwald, P. D., and Koolen, W. M. (2014). Follow the leader if you can, hedge you must. The Journal of Machine Learning Research, 15(1):1281-1316
[11] Degenne, R. and Koolen, W. M.M. (2019). Pure exploration with multiple correct answers. arXiv preprint 1902v 1902.03475.
[12] Degenne, R., Koolen, W. M., and Ménard, (2019). Non-asymptotic pure exploration by solving games. In NeurlPS, pages
[13] Degenne, R., Ménard, P., Shang, X., and Valko, M. (2020a). Gamification of pure exploration for linear bandits. International Conference on Machine Learning, pages 1432-2442. PMLR.
[14] Degenne, R., Shao, H., and Koolen, W. (2020b). Structure adaptive algorithms for stochastic bandits. In International Conference on Machine Learning, pages 2443-24422 1442.. PMLR.
[15] Erven, T., Koolen, W. M., Rooij. S., and Grünwald, P. (2011), Adaptive hedge. Advances in Neural Information Processing Systems, 24: 10211656-160 1664.
[16] Even-Dar, E., Mannor, S., and Mansour, Y. (2003). Action elimination and stopping conditions for reinforcement learning. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pages 162-169.
[17] Fiez, T., Jain, L., Jamieson, K. G., and Ratliff, I.. (2019). Sequential experimental design for transductive linear bandits. In Advances in Neural Information Processing Systems, volume 32.
[18] Foster, J., Gentile, C.,, Mohri, M., and Zimmert, J. (2020). Adapting to misspecification in contextual bandits. Advances in Neural Information Processing Systems, 33.

---

[19] Garivier, A. and Kaufmann, E. (2016). Optimal best arm identification with fixed confidence. Conference on Learning Theory, pages 998-1927 PMLR.
[20] Ghosh, A., Chowdhury, S. R., and Gopalan, A. (2017). Misspecified linear bandits. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31.
[21] Jedra, and Proutiere, A. (2020). Optimal best-arm identification linear bandits. arXiv preprint 20X1v:2006.16073.
[22] Kalyanakrishnan, S. and Stone, P. (2010). Efficient selection of multiple bandit arms: Theory and practice. In ICML.
[23] Kalyanakrishnan, S., Tewari, A., Auer, P., and Stone, (2012). Pac subset selection in stochastic multi-armed bandits. In JCML, volume 12, pages 655-662.
[24] Katz-Samuels, J., Jain, L., Karnin, Z., and Jamieson, K. G. (2020). An empirical process approach to the union bound: Practical algorithms for combinatorial and linear bandits. In Advances Neural Information Processing Systems, volume 33, pages 10371-10382.
[25] Katz-Samuels, J. and Jamieson, K. (2020). The true sample complexity of identifying good arms. In International Conference on Artificial Intelligence and Statistics, pages 1781-1791. PMLR.
[26] Kaufmann, E., Cappé, O., and Garivier, A. (2016). On the complexity of best-arm identification in multi-armed bandit models. The Journal of Machine Learning Research, 17(1):1-42.
[27] Kirschner, J., Lattimore, T., Vernade, C., and Szepesvári, C. (2020). Asymptotically optimal information-directed sampling. arXiv preprint 1.X1v:2011.05944.
[28] Lattimore, T. and Szepesvári, C. (2020). Bandit algorithms. Cambridge University Press.
[29] Lattimore, T., Szepesvari, C., and Weisz, G. (2020). Learning with good feature representations in bandits and in with generative model. In International Conference on Machine Learning, pages 5662-5670. PMLR.
[30] Magureanu, S., Combes, R., and Proutiere, A. (2014). Lipschitz bandits: Regret lower bound and optimal algorithms. In Conference Learning Theory, pages 975-999. PMLR.
[31] Mason, B., Jain, L., Tripathy, A., and Nowak, R. (2020). Finding all s-good arms in stochastic bandits. Advances in Neural Information Processing Systems, 33.
[32] Orabona, F. (2019). A modern introduction to online learning. arXiv preprint 19X2v:1912.133
[33] Pacchiano, A., Phan, M., Abbasi Yadkori, Y., Rao, A., Zimmert, J., Lattimore, T., and Szepesvari, C. (2020). Model selection in contextual stochastic bandit problems. In Advances in Neural Information Processing Systems, volume 33, pages 10328-10333
[34] Papini, M., Tirinzoni, A., Restelli, M., Lazaric, A., and Pirotta, M. (2021). Leveraging good representations in linear contextual bandits. In Meila, M. and Zhang, T., editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 8371-833 1-880. PMLR.
[35] Réda, C., Kaufmann, E., and Delahaye-Durier A. (2021). Top-m identification for linear bandits. In International Conference on Artificial Intelligence and Statistics, pages 1108-1116 PMLR.
[36] Shang, X., Heide, R., Menard, P., Kaufmann, E., and Valko, M. (2020). Fixed-confidence guar- antecs for bayesian best-arm identification. In International Conference Artificial Intelligence and Statistics, pages 1823-1832. PMLR.
[37] Simchowitz, M., Jamieson, K., and Recht, B. (2017). The simulator: Understanding adaptive sampling the moderate-confidence regime. Conference on Learning Theory, pages 1794-1834. PMLR.
12

---

[38] Soare, M.. Lazaric, A., and Munos, R. (2014). Best-arm identification in linear bandits. In Advances Neural Information Processing Systems, volume 27.
[39] Takemura, K., Ito, S., Hatano, D., Sumita, H., Fukunaga, T., Kakimura, N., and Kawarabayashi,
K.-i. (2021). A parameter-free algorithm for misspecified linear contextual bandits. In International Conference on Artificial Intelligence and Statistics, pages 3367-3313 PMLR.
[40] Tirinzoni, A., Pirotta, M., Restelli, M., and Lazaric, A. (2020). An asymptotically optimal
primal-dual incremental algorithm for contextual linear bandits. Advances in Neural Information Processing Systems, 33.
[41] Wagenmaker, A., Katz-Samuels, J., and Jamieson, K. (2021). Experimental design for regret minimization in linear bandits. In International Conference on Artificial Intelligence and Statistics, pages
PMLR.
[42] Xu, I.., Honda, J., and Sugiyama, M. (2018) 8). A fully adaptive algorithm for pure exploration in linear bandits. International Conference on Artificial Intelligence and Statistics, pages 843-851. PMLR.
[43] Zaki, M.. Mohan, A., and Gopalan, A. (2020). Explicit best arm identification in linear bandits using no-regret learners. arXiv preprint XXXX:200006.7622..
[44] Zanette, A., Lazaric, A., Kochenderfer, J.,., and Brunskill, E. (2020). Learning near optimal policies with low inherent bellman error. In ICML, volume 119 of Proceedings of Machine Learning Research, pages 10978-10989. PMLR.
13


Reviews:
[{"review_id": "a27ANJw6kj", "reviewer": "Reviewer_dLDo", "summary": "This paper studied the fixed-confidence Top-m identification problem for linear bandit models. Different from previous linear bandit works, this paper considers the setting where there is some deviation from the linearity (called misspecified linear bandit models).\n\nAssuming the upper bound of this deviation is given (denoted as eps), the misspecified linear bandit model generalizes the unstructured bandit model and the linear bandit model: when eps = 0, it recovers the linear version, and when eps -> infinity, it recovers the unstructured version.\n\nSome interesting results have been developed under this misspecification concept, including a simple algorithm to select the top-m arms,  a lower-bound and an upper bound of the sample complexity, and they match when the maximum error rate -> 0. The authors also proved that when eps is unknown, even with the linearity assumption, we can not do anything better than what we have done for unstructured bandit models.\n\nFinally, preliminary experimental results are provided for both real-world datasets and synthetic datasets, showing the effectiveness of the proposed algorithm.\n", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nOverall I think the problems studied are quite interesting, and by introducing the concept of misspecification, the linearity assumption made in the linear bandit models is weakened, making the misspecified linear bandit better models the real-world problems.\n\nI also like the results the paper derived,\nWhen the upper bound of the misspecification is unknown, the problem is no easier than its unstructured version. This intuitively is true but requires non-trivial proof.\nThe algorithm proposed recovers the state-of-the-art dependencies in the linear case (eps = 0) and in the unstructured case (eps is large).\nThe algorithm has been empirically evaluated.\n\nThis paper is also well written and easy to follow when the audience is familiar with the mathematical tools/concepts being used.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "\nThe concept of misspecification is not entirely new, and has been studied in literature as specified in the Related Work Section. Of course, misspecification hasn’t been previously explored in the pure exploration literature.\n\nThe upper bound in Thm 5 is quite complicated to interpret, not sure if it is possible to further simplify it.\n\n\nMy biggest concern is on the experimental results, and I am not fully convinced. Let’s take Figure 1 as an example. In the left-most figure of Figure 1, all empirical error rate is 0.0, it is possible that even if we reduce the sample complexity of LUCB, we still get an empirical error rate of 0.0. So this does not seem to be a fair comparison. In my opinion, a better way to plot the figure is that set the X-axis as the number of pulls, and Y-axis as the empirical error rates (over e.g., over 500 runs). Then you can easily compare the sample complexities between different algorithms for a certain empirical error rate by drawing a horizontal line. See e.g., Figure 4 of http://proceedings.mlr.press/v70/chen17b/chen17b.pdf\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "_J4R_dY9k2N", "reviewer": "Reviewer_Q9sG", "summary": "The authors study the top-m identification for misspecified linear multi armed bandits. They propose theoretical results in the form of a lower bound on the sample complexity for any approximate algorithm for general top-m identification problem and also show that knowing the problem is misspecified without knowing the scale of the misspecification is the same as not knowing anything about the structure of the problem. They then propose the first algorithm MisLid for fixed confidence top-m identification in misspecified bandits, prove guarantees for delta-correctness and sample complexity, and perform experimental evaluation of the algorithm. \n", "questions": "", "limitations": "", "rating": 7, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The results presented appear to be novel and practical. While the result is well presented and seems to be correct, I am unable to accurately review the paper in the context of originality and significance because I feel like I lack the domain knowledge to accurately do so. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss the main limitation of their work being the computational complexity, but also present ideas on overcoming the limitations. They also briefly mention that the algorithm relies on features provided in the input data and could be subjected to bias and lack of fairness in the recommendation.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5-6"}, "extra_text": {}}, {"review_id": "19Yjgur-ge6", "reviewer": "Reviewer_vF9d", "summary": "In this work the authors tackle the problem of finding the (potentially not unique) top-m arms in the misspecified linear bandit setting. An instance dependent information theoretic lower bound is given for any delta-correct algorithm. From the computationally efficient reformulation of this lower bound the authors provide, an algorithm is proposed, for which finite sample guarantees are provided. Optimality is shown in the high confidence regime. Synthetic and real-world experiments validate the statistical and computational efficiency of this scheme.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Overall, the experimental evaluation of this scheme seems interesting and well done, particularly experiments (D) and (E) on real datasets. The numerical results, especially for the synthetic experiments, are hard to parse however; aside from table 2, the results are only displayed visually. For example, the inclusion of LUCB in experiment (A) makes it difficult to compare LinGapE and MisLid. It seems as though on all synthetic simulated instances, LinGapE outperforms MisLid, potentially quite significantly. If epsilon is taken to be larger in Experiment (A) (say epsilon = 5) will we see a similar hit in accuracy as in Experiment (E)? Additional justification for the heuristic stopping rule in line 291 would be helpful. Line 317 Experiment (B), no unstructured bandit baseline algorithm appears to be shown. Line 132, is it clear that for small m (e.g. m=3 or 4 as in experiments) the combinatorial optimization over (K choose m) sets is less efficient than the proposed scheme?\n2. The lower bound appears to show that for a given class of models (known epsilon,M) adaptation to the true infinity norm of eta is not possible (which is surprising). Is there some alternate assumption under which this is possible, for example knowledge on the relationship between the norms of mu and eta?\n3. I wasn’t able to find where t_0 the initialization time is bounded, which seems as though it could be poor (but constant) for ill-conditioned phi.\n\nMinor errors:\n- Line 17 K is a set\n- Line 36 mean rewards are inner products, not linear combinations\n- Line 96 \\ell_2\n- Algorithm 1 updating learner with \\omega_t\n- Line 186 D_{N_t} should be defined with respect to an arbitrary vector, not just N_t\n- Line 257: T_0(\\delta) is ‘a’ solution?\n- Fig 1: Experiment (B) ‘middle’\n- Line 302: most -> more\n- Line 310: a user-provided\n- Line 361: at each time -> in each round\n- Line 619 remainder\n- Line 630 V_{t_0}", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are no negative societal impacts in this theoretical paper that focuses on the top-m identification setting in misspecified linear bandits.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The review team seems aligned that the paper meets the NeurIPS threshold with one borderline vote. I wanted to thank the reviewers and authors for the detailed back and forth during the discussion period. I have also been informed from that process on how the authors consider their contributions and the limitations of the model and results. While several points remain hanging and there is some disagreement over the numerical results, I feel the paper has a good story to tell, and while the issue of misspecification is not new in the MAB literature, the pure exploration problem does raise its own challenges and hence this is a worthwhile paper that will have an audience. I have to agree with reviewer 2 (vF9d) about the bound on t_0. The relation to Kauffman (2016) in terms of lower bounds should also be better discussed and perhaps more broadly and more clearly laying out what additional complexity in analysis stems from misspecification relative to earlier work that study the fixed confidence setting. 
Decision: Accept (Poster)