Combining Expert Advice Efficiently

Understand

We show how models for prediction with expert advice can be defined concisely and clearly using hidden Markov models (HMMs); standard HMM algorithms can then be used to efficiently calculate, among other things, how the expert predictions should be weighted according to the model.

• We cast many existing models as HMMs and recover the best known running times in each case.
• We also describe two new models: the switch distribution, which was recently developed to improve Bayesian/Minimum Description Length model selection, and a new generalisation of the fixed share algorithm based on run-length coding.
• We give loss bounds for all models and shed new light on their relationships.