TY - GEN
T1 - Online allocation with risk information
AU - Harada, Shigeaki
AU - Takimoto, Eiji
AU - Maruoka, Akira
PY - 2005/12/1
Y1 - 2005/12/1
N2 - We consider the problem of dynamically apportioning resources among a set of options in a worst-case online framework. The model we investigate is a generalization of the well studied online learning model. In particular, we allow the learner to see as additional information how high the risk of each option is. This assumption is natural in many applications like horse-race betting, where gamblers know odds for all options before placing bets. We apply the Aggregating Algorithm to this problem and give a tight performance bound. The results support our intuition that we should bet more on low-risk options. Surprisingly, however, the Hedge Algorithm without seeing risk information performs nearly as well as the Aggregating Algorithm. So the risk information does not help much. Moreover, the loss bound does not depend on the values of relatively small risks.
AB - We consider the problem of dynamically apportioning resources among a set of options in a worst-case online framework. The model we investigate is a generalization of the well studied online learning model. In particular, we allow the learner to see as additional information how high the risk of each option is. This assumption is natural in many applications like horse-race betting, where gamblers know odds for all options before placing bets. We apply the Aggregating Algorithm to this problem and give a tight performance bound. The results support our intuition that we should bet more on low-risk options. Surprisingly, however, the Hedge Algorithm without seeing risk information performs nearly as well as the Aggregating Algorithm. So the risk information does not help much. Moreover, the loss bound does not depend on the values of relatively small risks.
UR - http://www.scopus.com/inward/record.url?scp=33646515068&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=33646515068&partnerID=8YFLogxK
U2 - 10.1007/11564089_27
DO - 10.1007/11564089_27
M3 - Conference contribution
AN - SCOPUS:33646515068
SN - 354029242X
SN - 9783540292425
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 343
EP - 355
BT - Algorithmic Learning Theory - 16th International Conference, ALT 2005, Proceedings
T2 - 16th International Conference on Algorithmic Learning Theory, ALT 2005
Y2 - 8 October 2005 through 11 October 2005
ER -