TY - GEN

T1 - Online learning with prior knowledge

AU - Hazan, Elad

AU - Megiddo, Nimrod

PY - 2007

Y1 - 2007

N2 - The standard so-called experts algorithms are methods for utilizing a given set of "experts" to make good choices in a sequential decision-making problem. In the standard setting of experts algorithms, the decision maker chooses repeatedly in the same "state" based on information about how the different experts would have performed if chosen to be followed. In this paper we seek to extend this framework by introducing state information. More precisely, we extend the framework by allowing an experts algorithm to rely on state information, namely, partial information about the cost function, which is revealed to the decision maker before the latter chooses an action. This extension is very natural in prediction problems. For illustration, an experts algorithm, which is supposed to predict whether the next day will be rainy, can be extended to predicting the same given the current temperature. We introduce new algorithms, which attain optimal performance in the new framework, and apply to more general settings than variants of regression that have been considered in the statistics literature.

AB - The standard so-called experts algorithms are methods for utilizing a given set of "experts" to make good choices in a sequential decision-making problem. In the standard setting of experts algorithms, the decision maker chooses repeatedly in the same "state" based on information about how the different experts would have performed if chosen to be followed. In this paper we seek to extend this framework by introducing state information. More precisely, we extend the framework by allowing an experts algorithm to rely on state information, namely, partial information about the cost function, which is revealed to the decision maker before the latter chooses an action. This extension is very natural in prediction problems. For illustration, an experts algorithm, which is supposed to predict whether the next day will be rainy, can be extended to predicting the same given the current temperature. We introduce new algorithms, which attain optimal performance in the new framework, and apply to more general settings than variants of regression that have been considered in the statistics literature.

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

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

U2 - 10.1007/978-3-540-72927-3_36

DO - 10.1007/978-3-540-72927-3_36

M3 - Conference contribution

AN - SCOPUS:38048999685

SN - 9783540729259

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

SP - 499

EP - 513

BT - Learning Theory - 20th Annual Conference on Learning Theory, COLT 2007, Proceedings

PB - Springer Verlag

T2 - 20th Annual Conference on Learning Theory, COLT 2007

Y2 - 13 June 2007 through 15 June 2007

ER -