The knowledge gradient algorithm for online subset selection

Ilya O. Ryzhov; Warren Powell

doi:10.1109/ADPRL.2009.4927537

The knowledge gradient algorithm for online subset selection

Ilya O. Ryzhov, Warren Powell

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

22 Scopus citations

Abstract

We derive a one-period look-ahead policy for online subset selection problems, where learning about one subset also gives us information about other subsets. The subset selection problem is treated as a multi-armed bandit problem with correlated prior beliefs. We show that our decision rule is easily computable, and present experimental evidence that the policy is competitive against other online learning policies.

Original language	English (US)
Title of host publication	2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009 - Proceedings
Pages	137-144
Number of pages	8
DOIs	https://doi.org/10.1109/ADPRL.2009.4927537
State	Published - 2009
Event	2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009 - Nashville, TN, United States Duration: Mar 30 2009 → Apr 2 2009

Publication series

Name	2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009 - Proceedings

Other

Other	2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009
Country/Territory	United States
City	Nashville, TN
Period	3/30/09 → 4/2/09

All Science Journal Classification (ASJC) codes

Computational Theory and Mathematics
Software

Access to Document

10.1109/ADPRL.2009.4927537

Cite this

Ryzhov, I. O., & Powell, W. (2009). The knowledge gradient algorithm for online subset selection. In 2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009 - Proceedings (pp. 137-144). Article 4927537 (2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009 - Proceedings). https://doi.org/10.1109/ADPRL.2009.4927537

@inproceedings{e76f12d0d3ed45338d3649e707b9f66e,

title = "The knowledge gradient algorithm for online subset selection",

abstract = "We derive a one-period look-ahead policy for online subset selection problems, where learning about one subset also gives us information about other subsets. The subset selection problem is treated as a multi-armed bandit problem with correlated prior beliefs. We show that our decision rule is easily computable, and present experimental evidence that the policy is competitive against other online learning policies.",

author = "Ryzhov, {Ilya O.} and Warren Powell",

note = "Copyright: Copyright 2012 Elsevier B.V., All rights reserved.; 2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009 ; Conference date: 30-03-2009 Through 02-04-2009",

year = "2009",

doi = "10.1109/ADPRL.2009.4927537",

language = "English (US)",

isbn = "9781424427611",

series = "2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009 - Proceedings",

pages = "137--144",

booktitle = "2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009 - Proceedings",

}

Ryzhov, IO & Powell, W 2009, The knowledge gradient algorithm for online subset selection. in 2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009 - Proceedings., 4927537, 2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009 - Proceedings, pp. 137-144, 2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009, Nashville, TN, United States, 3/30/09. https://doi.org/10.1109/ADPRL.2009.4927537

The knowledge gradient algorithm for online subset selection. / Ryzhov, Ilya O.; Powell, Warren.
2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009 - Proceedings. 2009. p. 137-144 4927537 (2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009 - Proceedings).

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

TY - GEN

T1 - The knowledge gradient algorithm for online subset selection

AU - Ryzhov, Ilya O.

AU - Powell, Warren

PY - 2009

Y1 - 2009

N2 - We derive a one-period look-ahead policy for online subset selection problems, where learning about one subset also gives us information about other subsets. The subset selection problem is treated as a multi-armed bandit problem with correlated prior beliefs. We show that our decision rule is easily computable, and present experimental evidence that the policy is competitive against other online learning policies.

AB - We derive a one-period look-ahead policy for online subset selection problems, where learning about one subset also gives us information about other subsets. The subset selection problem is treated as a multi-armed bandit problem with correlated prior beliefs. We show that our decision rule is easily computable, and present experimental evidence that the policy is competitive against other online learning policies.

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

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

U2 - 10.1109/ADPRL.2009.4927537

DO - 10.1109/ADPRL.2009.4927537

M3 - Conference contribution

AN - SCOPUS:67650505320

SN - 9781424427611

T3 - 2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009 - Proceedings

SP - 137

EP - 144

BT - 2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009 - Proceedings

T2 - 2009 IEEE Symposium on Adaptive Dynamic Programming and Reinforcement Learning, ADPRL 2009

Y2 - 30 March 2009 through 2 April 2009

ER -

The knowledge gradient algorithm for online subset selection

Abstract

Publication series

Other

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this