Supermartingales in Prediction with Expert Advice

Alexey V. Chernov, Yuri Kalnishkan, Fedor Zhdanov, Vladimir Vovk

ALT 2008 pp. 199-213

doi:10.1007/978-3-540-87987-9_19 /alt/2008/chernov2008alt-supermartingales/

Abstract

This paper compares two methods of prediction with expert advice, the Aggregating Algorithm and the Defensive Forecasting, in two different settings. The first setting is traditional, with a countable number of experts and a finite number of outcomes. Surprisingly, these two methods of fundamentally different origin lead to identical procedures. In the second setting the experts can give advice conditional on the learner's future decision. Both methods can be used in the new setting and give the same performance guarantees as in the traditional setting. However, whereas defensive forecasting can be applied directly, the AA requires substantial modifications.

PDF ALT Semantic Scholar

Cite

Text

Chernov et al. "Supermartingales in Prediction with Expert Advice." International Conference on Algorithmic Learning Theory, 2008. doi:10.1007/978-3-540-87987-9_19

Markdown

[Chernov et al. "Supermartingales in Prediction with Expert Advice." International Conference on Algorithmic Learning Theory, 2008.](https://mlanthology.org/alt/2008/chernov2008alt-supermartingales/) doi:10.1007/978-3-540-87987-9_19

BibTeX

@inproceedings{chernov2008alt-supermartingales,
  title     = {{Supermartingales in Prediction with Expert Advice}},
  author    = {Chernov, Alexey V. and Kalnishkan, Yuri and Zhdanov, Fedor and Vovk, Vladimir},
  booktitle = {International Conference on Algorithmic Learning Theory},
  year      = {2008},
  pages     = {199-213},
  doi       = {10.1007/978-3-540-87987-9_19},
  url       = {https://mlanthology.org/alt/2008/chernov2008alt-supermartingales/}
}