Combining Expert Advice Efficiently
  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.
