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": "y8yB3uwFTtK", "reviewer": "Reviewer_1wnn", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Following are the strengths and weaknesses of the paper:\n\nStrengths:\n1)\tTo 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.\n2)\tThe paper provides some interesting results:\n\ni)\t(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.\nii)\tA 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.\niii)\tThe proposed decision rules are shown to match the prescribed lower bound asymptotically.\n3)\tSufficient experimental validation is provided to showcase the empirical performance of the prescribed decision rules.\n\nWeaknesses: Some of the explanations provided by the authors are a bit unclear to me. Specifically, I have the following questions:\n1)\tIMO, 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?\n\n2)\tCan 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]. \n\n3)\tSample 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. \n\n4)\tLooking 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?\n\nProbable typo: Line 211: Should it be $$\\theta$$ instead of $$\\theta_t$$ for the self-normalized concentration?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have explained the limitations of the investigation in Section 6.", "review_text": "", "extra_scores": {"ethical_concerns": ": N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7 hours"}, "extra_text": {}}, {"review_id": "pjd-ZWjn4Y7", "reviewer": "Reviewer_sjPk", "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.  ", "questions": "", "limitations": "", "rating": 6, "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 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "6Lln665IOP", "reviewer": "Reviewer_TZ2B", "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.", "questions": "", "limitations": "", "rating": 4, "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": "\nThe paper presents some interesting results, but I find the following shortcomings:\n\nI 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.\n \nThe 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.\n\nThe main paper does not provide any intuition behind proof of correctness for the algorithm MisLid.\n\nThe 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.\n\nIn 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.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I feel the presented motivation behind the problem setup is inadequate.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

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)