Best arm identification in linear bandits with linear dimension dependency

Chao Tao, Saul A. Blanco, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We study the best arm identification problem in linear bandits, where the mean reward of each arm depends linearly on an unknown d-dimensional parameter vector 0, and the goal is to identify the arm with the largest expected reward. We first design and analyze a novel randomized 9 estimator based on the solution to the convex relaxation of an optimal G-allocation experiment design problem. Using this estimator, we describe an algorithm whose sample complexity depends linearly on the dimension d, as well as an algorithm with sample complexity dependent on the reward gaps of the best d arms, matching the lower bound arising from the ordinary top-arm identification problem. We finally compare the empirical performance of our algorithms with other state-of-the-art algorithms in terms of both sample complexity and computational time.

Original languageEnglish (US)
Title of host publication35th International Conference on Machine Learning, ICML 2018
EditorsAndreas Krause, Jennifer Dy
PublisherInternational Machine Learning Society (IMLS)
Pages7773-7786
Number of pages14
ISBN (Electronic)9781510867963
StatePublished - Jan 1 2018
Event35th International Conference on Machine Learning, ICML 2018 - Stockholm, Sweden
Duration: Jul 10 2018Jul 15 2018

Publication series

Name35th International Conference on Machine Learning, ICML 2018
Volume11

Other

Other35th International Conference on Machine Learning, ICML 2018
CountrySweden
CityStockholm
Period7/10/187/15/18

    Fingerprint

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Human-Computer Interaction
  • Software

Cite this

Tao, C., Blanco, S. A., & Zhou, Y. (2018). Best arm identification in linear bandits with linear dimension dependency. In A. Krause, & J. Dy (Eds.), 35th International Conference on Machine Learning, ICML 2018 (pp. 7773-7786). (35th International Conference on Machine Learning, ICML 2018; Vol. 11). International Machine Learning Society (IMLS).