Best-Arm Identification in Linear Bandits
We study the best-arm identification problem in linear bandit, where the rewards of the arms depend linearly on an unknown parameter θ * and the objective is to return the arm with the largest reward. We characterize the complexity of the problem and introduce sample allocation strategies that pull arms to identify the best arm with a fixed confidence, while minimizing the sample budget. In particular, we show the importance of exploiting the global linear structure to improve the estimate of the reward of near-optimal arms. We analyze the proposed strategies and compare their empirical performance. Finally, as a by-product of our analysis, we point out the connection to the G-optimality criterion used in optimal experimental design.
This paper is one of the first to study best arm identification in bandit models with correlated arms. The authors consider the fixed-confidence setting. A new complexity notion, that takes into account the correlation between arms, is proposed, and algorithms that almost attain this complexity are proposed. Some of them are based on a static allocation strategy (i.e. that does not depend on the rewards collected), and one of them is adaptive. First, this paper is not exactly the first on best arm identification in linear bandit problem. Indeed,* Hoffmann, Shahriari, De Freitas, On correlation and budget constraints in model-based bandit optimization with application to automatic machine learning (AISTATS 2014)consider a linear bandit model with gaussian noise. However, they study the fixed-budget setting, and the complexity term featured in their work involves a sum over all arms of a squared gap (that is, it does not really take into account the correlations induced by the linear structured).The theoretical results of the paper rely on Propositions 1 and 2 given in Section 2. The statement of these results are a bit imprecise, and it should be mentionned whether n is fixed or not. Indeed, the result extracted from [1] given as Proposition 2 should be P(\forall n\in\N, (2) holds) \geq 1-\delta, whereas Proposition 1 should be written as: for every n, for every fixed sequence x_n,P( (1) holds) \geq 1- \delta. This makes a difference, as an extra union bound over n might be required when using Proposition 1, as even when the sampling rule is static, the sampling rule is adaptive. Also a precise reference for Proposition 1 should be given. The terminology should be made more precise. In best arm identification, in the fixed-confidence setting, algorithms consists in two elements: a sampling rule and a stopping rule (and also a recommendation rule, but quite naturally, when stopping you always choose the best arm as if the current least-square estimate were the true parameter). The "static and adaptive strategies" mentioned in the paper relates only to the sampling strategy  as the stopping strategy of the G-allocation strategy is adaptive. In the proof of Theorem 1, a union bound over n seems to be missing (see above comment on Proposition 1): you need the display of line 674 to hold for all n, hence the union bound will bring you a log(CK^2/t^2\delta) for some constant C for example. Besides, in the statement of Theorem 1, 'beta-approximation' is not defined (neither in the text nor in Lemma 5 and 6).About the oracle: Section 3 is a bit confusing as when you have access to the parameter \theta^*, there is nothing left to do. I understand that you assume that the algorithms are based on confidence intervals and stop when one of the confidence intervals is contained on the C(x). You then study which shape these confidence intervals should have in order to be as quickly as possible included in C(x^*). Still the definition of the oracle appears quite imprecise (again if \theta^* was known the problem would be solved). Usually the definition of a complexity in best arm identification comes from a lower bound on the number of sample used, for any $\delta$-PAC algorithm: you don't really have such a result here and I don't see what justifies the claim "We characterize the complexity of the problem" in the introduction.  The algorithms are built on allocation strategies coming from experimental design theory (many of the results of Appendix B are adapted from [16]) which are hard to implement and must be approximated. It is not clear what is the overall numerical complexity of the proposed algorithm and how it scales with the different parameters. In the numerical experiments section, it is always frustrating to see comparison only between the methods introduced in the paper. As such, this section is not very informative. In particular, an obvious benchmark would have been to compare to an algorithm designed for best arm identification in classic (unstructured) bandit problems (LUCB, UGapE, etc.) This is particularly true as the problem chosen in the experiments is such that the arms are orthogonal, except for two of them; a situation which is very close to the classic d-armed bandit model. Comments about the choice of such a particular setting for the simulations would also be appreciable.Minor comments* There is an overlap in the notation: in the paragraph "the setting", \Delta is defined in two ways, \Delta(x) and \Delta(y) (one beeing functions of vectors, the others of directions): it might be more convenient for the reader to distinguish explicitly these two notions.* In Footnote 1 "used of all direction y": should it be "for all vector x"?* Line 232, "inthe" (should be separated).* In the boxed environment of page 4 (Figure 2), it should be Eq. 24 in place of Eq. 22 on the second line.* Figures 2 and 3 (which actually define the algorithms) refer to Equations that only appear in the supplementary material; please make the main paper self-contained.