Improving the Knowledge Gradient Algorithm

Le Yang; Siyang Gao; Chin Pang Ho

Improving the Knowledge Gradient Algorithm

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

2 Citations (Scopus)

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.

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
Event	37th Conference on Neural Information Processing Systems (NeurIPS 2023) - New Orleans Ernest N. Morial Convention Center, New Orleans, United States Duration: 10 Dec 2023 → 16 Dec 2023 https://papers.nips.cc/paper_files/paper/2023 https://nips.cc/Conferences/2023

Publication series

Name	Advances in Neural Information Processing Systems
ISSN (Print)	1049-5258

Conference

Conference	37th Conference on Neural Information Processing Systems (NeurIPS 2023)
Abbreviated title	NIPS '23
Place	United States
City	New Orleans
Period	10/12/23 → 16/12/23
Internet address	https://papers.nips.cc/paper_files/paper/2023 https://nips.cc/Conferences/2023

Access Output

https://proceedings.neurips.cc/paper_files/paper/2023/hash/c272409133942e2f4b7631c8cb7e507e-Abstract-Conference.html

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Yang, L., Gao, S., & Ho, C. P. (2023). Improving the Knowledge Gradient Algorithm. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, & S. Levine (Eds.), NIPS '23: Proceedings of the 37th International Conference on Neural Information Processing Systems (pp. 61747-61758). Article 2698 (Advances in Neural Information Processing Systems). Curran Associates Inc.. https://proceedings.neurips.cc/paper_files/paper/2023/hash/c272409133942e2f4b7631c8cb7e507e-Abstract-Conference.html

Yang, Le ; Gao, Siyang ; Ho, Chin Pang. / Improving the Knowledge Gradient Algorithm. NIPS '23: Proceedings of the 37th International Conference on Neural Information Processing Systems. editor / A. Oh ; T. Naumann ; A. Globerson ; K. Saenko ; M. Hardt ; S. Levine. Red Hook, NY : Curran Associates Inc., 2023. pp. 61747-61758 (Advances in Neural Information Processing Systems).

@inproceedings{b0dce947826a453ab9ed5a54e3942130,

title = "Improving the Knowledge Gradient Algorithm",

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. {\textcopyright} 2023 Neural information processing systems foundation. All rights reserved.",

author = "Le Yang and Siyang Gao and Ho, {Chin Pang}",

year = "2023",

month = dec,

language = "English",

series = "Advances in Neural Information Processing Systems",

publisher = "Curran Associates Inc.",

pages = "61747--61758",

editor = "A. Oh and T. Naumann and A. Globerson and K. Saenko and M. Hardt and S. Levine",

booktitle = "NIPS '23: Proceedings of the 37th International Conference on Neural Information Processing Systems",

note = "37th Conference on Neural Information Processing Systems (NeurIPS 2023), NIPS '23 ; Conference date: 10-12-2023 Through 16-12-2023",

url = "https://papers.nips.cc/paper_files/paper/2023, https://nips.cc/Conferences/2023",

}

Yang, L , Gao, S & Ho, CP 2023, Improving the Knowledge Gradient Algorithm. in A Oh, T Naumann, A Globerson, K Saenko, M Hardt & S Levine (eds), NIPS '23: Proceedings of the 37th International Conference on Neural Information Processing Systems., 2698, Advances in Neural Information Processing Systems, Curran Associates Inc., Red Hook, NY, pp. 61747-61758, 37th Conference on Neural Information Processing Systems (NeurIPS 2023), New Orleans, Louisiana, United States, 10/12/23. <https://proceedings.neurips.cc/paper_files/paper/2023/hash/c272409133942e2f4b7631c8cb7e507e-Abstract-Conference.html>

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).

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

TY - GEN

T1 - Improving the Knowledge Gradient Algorithm

AU - Yang, Le

AU - Gao, Siyang

AU - Ho, Chin Pang

PY - 2023/12

Y1 - 2023/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85191201819&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85191201819&origin=recordpage

M3 - RGC 32 - Refereed conference paper (with host publication)

T3 - Advances in Neural Information Processing Systems

SP - 61747

EP - 61758

BT - NIPS '23: Proceedings of the 37th International Conference on Neural Information Processing Systems

A2 - Oh, A.

A2 - Naumann, T.

A2 - Globerson, A.

A2 - Saenko, K.

A2 - Hardt, M.

A2 - Levine, S.

PB - Curran Associates Inc.

CY - Red Hook, NY

T2 - 37th Conference on Neural Information Processing Systems (NeurIPS 2023)

Y2 - 10 December 2023 through 16 December 2023

ER -

Improving the Knowledge Gradient Algorithm

Abstract

Publication series

Conference

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this