A Criterion for the Existence of Predictive Complexity for Binary Games
Abstract
It is well known that there exists a universal (i.e., optimal to within an additive constant if allowed to work infinitely long) algorithm for lossless data compression (Kolmogorov, Levin). The game of lossless compression is an example of an on-line prediction game; for some other on-line prediction games (such as the simple prediction game) a universal algorithm is known not to exist. In this paper we give an analytic characterisation of those binary on-line prediction games for which a universal prediction algorithm exists.
Cite
Text
Kalnishkan et al. "A Criterion for the Existence of Predictive Complexity for Binary Games." International Conference on Algorithmic Learning Theory, 2004. doi:10.1007/978-3-540-30215-5_20Markdown
[Kalnishkan et al. "A Criterion for the Existence of Predictive Complexity for Binary Games." International Conference on Algorithmic Learning Theory, 2004.](https://mlanthology.org/alt/2004/kalnishkan2004alt-criterion/) doi:10.1007/978-3-540-30215-5_20BibTeX
@inproceedings{kalnishkan2004alt-criterion,
title = {{A Criterion for the Existence of Predictive Complexity for Binary Games}},
author = {Kalnishkan, Yuri and Vovk, Vladimir and Vyugin, Michael V.},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2004},
pages = {249-263},
doi = {10.1007/978-3-540-30215-5_20},
url = {https://mlanthology.org/alt/2004/kalnishkan2004alt-criterion/}
}