Online Learning with Regularized Knowledge Gradients

Donghun Lee; Warren B. Powell

doi:10.1007/978-3-031-05936-0_26

Online Learning with Regularized Knowledge Gradients

Donghun Lee, Warren B. Powell

Department of Physics

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

1 Citation (Scopus)

Abstract

We introduce a simple and effective regularization of knowledge gradient (KG) and use it to present the first sublinear regret bound result for KG-based algorithms. We construct online learning with regularized knowledge gradients (ORKG) algorithm with independent Gaussian belief model, and prove that ORKG algorithm achieves sublinear regret upper bound with high probability facing bounded independent Gaussian multi-armed bandit (MAB) problems. The theoretical properties of regularized KG and ORKG algorithm are analyzed, and the empirical characteristics of ORKG algorithm are empirically validated with MAB benchmark simulations. ORKG algorithm shows top-tier performance comparable to select MAB algorithms with provable regret bounds.

Original language	English
Title of host publication	Advances in Knowledge Discovery and Data Mining - 26th Pacific-Asia Conference, PAKDD 2022, Proceedings
Editors	João Gama, Tianrui Li, Yang Yu, Enhong Chen, Yu Zheng, Fei Teng
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	328-339
Number of pages	12
ISBN (Print)	9783031059353
DOIs	https://doi.org/10.1007/978-3-031-05936-0_26
Publication status	Published - 2022
Event	26th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2022 - Chengdu, China Duration: 2022 May 16 → 2022 May 19

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13281 LNAI
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	26th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2022
Country/Territory	China
City	Chengdu
Period	22/5/16 → 22/5/19

Bibliographical note

Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.

Keywords

Knowledge gradient
Online learning
Regret analysis

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-031-05936-0_26

Cite this

Lee, D., & Powell, W. B. (2022). Online Learning with Regularized Knowledge Gradients. In J. Gama, T. Li, Y. Yu, E. Chen, Y. Zheng, & F. Teng (Eds.), Advances in Knowledge Discovery and Data Mining - 26th Pacific-Asia Conference, PAKDD 2022, Proceedings (pp. 328-339). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13281 LNAI). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-05936-0_26

Online Learning with Regularized Knowledge Gradients. / Lee, Donghun; Powell, Warren B.
Advances in Knowledge Discovery and Data Mining - 26th Pacific-Asia Conference, PAKDD 2022, Proceedings. ed. / João Gama; Tianrui Li; Yang Yu; Enhong Chen; Yu Zheng; Fei Teng. Springer Science and Business Media Deutschland GmbH, 2022. p. 328-339 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13281 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Lee, D & Powell, WB 2022, Online Learning with Regularized Knowledge Gradients. in J Gama, T Li, Y Yu, E Chen, Y Zheng & F Teng (eds), Advances in Knowledge Discovery and Data Mining - 26th Pacific-Asia Conference, PAKDD 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13281 LNAI, Springer Science and Business Media Deutschland GmbH, pp. 328-339, 26th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2022, Chengdu, China, 22/5/16. https://doi.org/10.1007/978-3-031-05936-0_26

Lee D, Powell WB. Online Learning with Regularized Knowledge Gradients. In Gama J, Li T, Yu Y, Chen E, Zheng Y, Teng F, editors, Advances in Knowledge Discovery and Data Mining - 26th Pacific-Asia Conference, PAKDD 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 328-339. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-05936-0_26

Lee, Donghun ; Powell, Warren B. / Online Learning with Regularized Knowledge Gradients. Advances in Knowledge Discovery and Data Mining - 26th Pacific-Asia Conference, PAKDD 2022, Proceedings. editor / João Gama ; Tianrui Li ; Yang Yu ; Enhong Chen ; Yu Zheng ; Fei Teng. Springer Science and Business Media Deutschland GmbH, 2022. pp. 328-339 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{f154e6ead3204555a0ada8ee6726d64e,

title = "Online Learning with Regularized Knowledge Gradients",

abstract = "We introduce a simple and effective regularization of knowledge gradient (KG) and use it to present the first sublinear regret bound result for KG-based algorithms. We construct online learning with regularized knowledge gradients (ORKG) algorithm with independent Gaussian belief model, and prove that ORKG algorithm achieves sublinear regret upper bound with high probability facing bounded independent Gaussian multi-armed bandit (MAB) problems. The theoretical properties of regularized KG and ORKG algorithm are analyzed, and the empirical characteristics of ORKG algorithm are empirically validated with MAB benchmark simulations. ORKG algorithm shows top-tier performance comparable to select MAB algorithms with provable regret bounds.",

keywords = "Knowledge gradient, Online learning, Regret analysis",

author = "Donghun Lee and Powell, {Warren B.}",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 26th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2022 ; Conference date: 16-05-2022 Through 19-05-2022",

year = "2022",

doi = "10.1007/978-3-031-05936-0_26",

language = "English",

isbn = "9783031059353",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "328--339",

editor = "Jo{\~a}o Gama and Tianrui Li and Yang Yu and Enhong Chen and Yu Zheng and Fei Teng",

booktitle = "Advances in Knowledge Discovery and Data Mining - 26th Pacific-Asia Conference, PAKDD 2022, Proceedings",

address = "Germany",

}

TY - GEN

T1 - Online Learning with Regularized Knowledge Gradients

AU - Lee, Donghun

AU - Powell, Warren B.

PY - 2022

Y1 - 2022

N2 - We introduce a simple and effective regularization of knowledge gradient (KG) and use it to present the first sublinear regret bound result for KG-based algorithms. We construct online learning with regularized knowledge gradients (ORKG) algorithm with independent Gaussian belief model, and prove that ORKG algorithm achieves sublinear regret upper bound with high probability facing bounded independent Gaussian multi-armed bandit (MAB) problems. The theoretical properties of regularized KG and ORKG algorithm are analyzed, and the empirical characteristics of ORKG algorithm are empirically validated with MAB benchmark simulations. ORKG algorithm shows top-tier performance comparable to select MAB algorithms with provable regret bounds.

AB - We introduce a simple and effective regularization of knowledge gradient (KG) and use it to present the first sublinear regret bound result for KG-based algorithms. We construct online learning with regularized knowledge gradients (ORKG) algorithm with independent Gaussian belief model, and prove that ORKG algorithm achieves sublinear regret upper bound with high probability facing bounded independent Gaussian multi-armed bandit (MAB) problems. The theoretical properties of regularized KG and ORKG algorithm are analyzed, and the empirical characteristics of ORKG algorithm are empirically validated with MAB benchmark simulations. ORKG algorithm shows top-tier performance comparable to select MAB algorithms with provable regret bounds.

KW - Knowledge gradient

KW - Online learning

KW - Regret analysis

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

U2 - 10.1007/978-3-031-05936-0_26

DO - 10.1007/978-3-031-05936-0_26

M3 - Conference contribution

AN - SCOPUS:85130246772

SN - 9783031059353

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 328

EP - 339

BT - Advances in Knowledge Discovery and Data Mining - 26th Pacific-Asia Conference, PAKDD 2022, Proceedings

A2 - Gama, João

A2 - Li, Tianrui

A2 - Yu, Yang

A2 - Chen, Enhong

A2 - Zheng, Yu

A2 - Teng, Fei

PB - Springer Science and Business Media Deutschland GmbH

T2 - 26th Pacific-Asia Conference on Knowledge Discovery and Data Mining, PAKDD 2022

Y2 - 16 May 2022 through 19 May 2022

ER -