Improving the Knowledge Gradient Algorithm
Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review
Author(s)
Related Research Unit(s)
Detail(s)
| Original language | English |
|---|---|
| Title of host publication | NIPS '23: Proceedings of the 37th International Conference on Neural Information Processing Systems |
| Editors | A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, S. Levine |
| Place of Publication | Red Hook, NY |
| Publisher | Curran Associates Inc. |
| Pages | 61747-61758 |
| Publication status | Published - Dec 2023 |
Publication series
| Name | Advances in Neural Information Processing Systems |
|---|---|
| ISSN (Print) | 1049-5258 |
Conference
| Title | 37th Conference on Neural Information Processing Systems (NeurIPS 2023) |
|---|---|
| Location | New Orleans Ernest N. Morial Convention Center |
| Place | United States |
| City | New Orleans |
| Period | 10 - 16 December 2023 |
Link(s)
| Document Link | Links |
|---|---|
| Link to Scopus | https://www.scopus.com/record/display.uri?eid=2-s2.0-85191201819&origin=recordpage |
| Permanent Link | https://scholars.cityu.edu.hk/en/publications/publication(b0dce947-826a-453a-b9ed-5a54e3942130).html |
Abstract
The knowledge gradient (KG) algorithm is a popular policy for the best arm identification (BAI) problem. It is built on the simple idea of always choosing the measurement that yields the greatest expected one-step improvement in the estimate of the best mean of the arms. In this research, we show that this policy has limitations, causing the algorithm not asymptotically optimal. We next provide a remedy for it, by following the manner of one-step look ahead of KG, but instead choosing the measurement that yields the greatest one-step improvement in the probability of selecting the best arm. The new policy is called improved knowledge gradient (iKG). iKG can be shown to be asymptotically optimal. In addition, we show that compared to KG, it is easier to extend iKG to variant problems of BAI, with the ϵ-good arm identification and feasible arm identification as two examples. The superior performances of iKG on these problems are further demonstrated using numerical examples. © 2023 Neural information processing systems foundation. All rights reserved.
Citation Format(s)
Improving the Knowledge Gradient Algorithm. / Yang, Le; Gao, Siyang; Ho, Chin Pang.
NIPS '23: Proceedings of the 37th International Conference on Neural Information Processing Systems. ed. / A. Oh; T. Naumann; A. Globerson; K. Saenko; M. Hardt; S. Levine. Red Hook, NY: Curran Associates Inc., 2023. p. 61747-61758 2698 (Advances in Neural Information Processing Systems).
NIPS '23: Proceedings of the 37th International Conference on Neural Information Processing Systems. ed. / A. Oh; T. Naumann; A. Globerson; K. Saenko; M. Hardt; S. Levine. Red Hook, NY: Curran Associates Inc., 2023. p. 61747-61758 2698 (Advances in Neural Information Processing Systems).
Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review
