On the Finite-Time Performance of the Knowledge Gradient Algorithm

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review

2 Scopus Citations
View graph of relations

Detail(s)

Original languageEnglish
Title of host publicationProceedings of the 39th International Conference on Machine Learning
EditorsKamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, Sivan Sabato
PublisherML Research Press
Pages12741-12764
Publication statusPublished - Jul 2022

Publication series

NameProceedings of Machine Learning Research
Volume162
ISSN (Print)2640-3498

Conference

Title39th International Conference on Machine Learning (ICML 2022)
LocationHybrid
PlaceUnited States
CityBaltimore
Period17 - 23 July 2022

Abstract

The knowledge gradient (KG) algorithm is a popular and effective algorithm for the best arm identification (BAI) problem. Due to the complex calculation of KG, theoretical analysis of this algorithm is difficult, and existing results are mostly about the asymptotic performance of it, e.g., consistency, asymptotic sample allocation, etc. In this research, we present new theoretical results about the finite-time performance of the KG algorithm. Under independent and normally distributed rewards, we derive bounds for the sample allocation of the algorithm. With these bounds, existing asymptotic results become simple corollaries. Furthermore, we derive upper and lower bounds for the probability of error and simple regret of the algorithm, and show the performance of the algorithm for the multi-armed bandit (MAB) problem. These developments not only extend the existing analysis of the KG algorithm, but can also be used to analyze other improvement-based algorithms. Last, we use numerical experiments to compare the bounds we derive and the performance of the KG algorithm. © 2022 by the author(s).

Research Area(s)

  • BUDGET ALLOCATION, POLICY

Citation Format(s)

On the Finite-Time Performance of the Knowledge Gradient Algorithm. / Li, Yanwen; Gao, Siyang.
Proceedings of the 39th International Conference on Machine Learning. ed. / Kamalika Chaudhuri; Stefanie Jegelka; Le Song; Csaba Szepesvari; Gang Niu; Sivan Sabato. ML Research Press, 2022. p. 12741-12764 (Proceedings of Machine Learning Research; Vol. 162).

Research output: Chapters, Conference Papers, Creative and Literary WorksRGC 32 - Refereed conference paper (with host publication)peer-review