Online Prediction - Bayes versus Experts

Author:	Marcus Hutter (2004)
Comments:	4 pages
Subj-class:	Learning; Artificial Intelligence
Reference:	EU PASCAL Workshop on Learning Theoretic and Bayesian Inductive Principles (LTBIP 2004)
Paper:	PostScript  -  PDF  -  Html/Gif
Slides:	PostScript - PDF

Keywords: Bayesian sequence prediction; Prediction with Expert Advice; general weights, alphabet and loss.

Abstract: We derive a very general regret bound in the framework of prediction with expert advice, which challenges the best known regret bound for Bayesian sequence prediction. Both bounds of the form sqrt(Loss x complexity) hold for any bounded loss-function, any prediction and observation spaces, arbitrary expert/environment classes and weights, and unknown sequence length.

BibTeX Entry

@TechReport{Hutter:04bayespea,
  author =       "M. Hutter",
  title =        "Online Prediction -- Bayes versus Experts",
  month =        jul,
  year =         "2004",
  note =         "Presented at the EU PASCAL Workshop on
                  Learning Theoretic and Bayesian Inductive Principles (LTBIP-2004)",
  url =          "http://www.hutter1.net/ai/bayespea.htm",
  ps =           "http://www.hutter1.net/ai/bayespea.ps",
  pdf =          "http://www.hutter1.net/ai/bayespea.pdf",
  slides =       "http://www.hutter1.net/ai/sbayespea.pdf",
  keywords =     "Bayesian sequence prediction;
                  Prediction with Expert Advice;
                  general weights, alphabet and loss.",
  abstract =     "We derive a very general regret bound in the framework of
                  prediction with expert advice, which challenges the best known
                  regret bound for Bayesian sequence prediction. Both bounds of the
                  form $\sqrt{\mbox{Loss}\times\mbox{complexity}}$ hold for any
                  bounded loss-function, any prediction and observation spaces,
                  arbitrary expert/environment classes and weights, and unknown
                  sequence length.",
}