Online allocation with risk information

Shigeaki Harada, Eiji Takimoto, Akira Maruoka

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)


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.

Original languageEnglish
Title of host publicationAlgorithmic Learning Theory - 16th International Conference, ALT 2005, Proceedings
Number of pages13
Publication statusPublished - Dec 1 2005
Externally publishedYes
Event16th International Conference on Algorithmic Learning Theory, ALT 2005 - Singapore, Singapore
Duration: Oct 8 2005Oct 11 2005

Publication series

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


Other16th International Conference on Algorithmic Learning Theory, ALT 2005

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Online allocation with risk information'. Together they form a unique fingerprint.

Cite this