Prediction With Expert Advice

Prediction with expert advice is a subfield of competitive on-line prediction in which the strategies in the benchmark class are free agents. When understood in a wide sense (as in Cesa-Bianchi and Lugosi 2006), prediction with expert advice is synonymous with competitive on-line prediction.

When strategies are free agents, or experts, the protocol of a game of prediction with expert advice is

Players: Experts, Forecaster, Reality
Protocol:

Initialize $L_0=0, L_0(k)=0, k=1,2,\dots$
FOR $t=1,2,\dots$:
Experts announce $\gamma^k\in\Gamma, k=1,2,\dots$
Forecaster announces $\gamma\in\Gamma$
Reality announces $\omega\in\Omega$
Update cumulative loss $L_t=L_{t-1} + \lambda(\omega,\gamma)$, $L_t(k)=L_{t-1}(k) + \lambda(\omega,\gamma_k), k=1,2,\dots$
END

These are some open problems:

Bibliography

  • Nicolo Cesa-Bianchi and Gabor Lugosi. Prediction, Learning, and Games. Cambridge: Cambridge University Press, 2006.