2021/11/02 by Clémence Réda, Réda, Clémence, Andrea Tirinzoni +3 · 1 citation
Decision Sciences · Computer Science · Mathematics · #Advanced Bandit Algorithms Research #Machine Learning and Algorithms #Advanced Causal Inference Techniques
paper · pdf · doi:10.48550/arxiv.2111.01479
We study the problem of the identification of m arms with largest means under\na fixed error rate \δ (fixed-confidence Top-m identification), for\nmisspecified linear bandit models. This problem is motivated by practical\napplications, especially in medicine and recommendation systems, where linear\nmodels are popular due to their simplicity and the existence of efficient\nalgorithms, but in which data inevitably deviates from linearity. In this work,\nwe first derive a tractable lower bound on the sample complexity of any\n\δ-correct algorithm for the general Top-m identification problem. We\nshow that knowing the scale of the deviation from linearity is necessary to\nexploit the structure of the problem. We then describe the first algorithm for\nthis setting, which is both practical and adapts to the amount of\nmisspecification. We derive an upper bound to its sample complexity which\nconfirms this adaptivity and that matches the lower bound when \δ\n\→ 0. Finally, we evaluate our algorithm on both synthetic and\nreal-world data, showing competitive performance with respect to existing\nbaselines.\n