General Loss Bounds for Universal Sequence Prediction
<|reference_start|>General Loss Bounds for Universal Sequence Prediction: The Bayesian framework is ideally suited for induction problems. The probability of observing $x_t$ at time $t$, given past observations $x_1...x_{t-1}$ can be computed with Bayes' rule if the true distribution $\mu$ of the sequences $x_1x_2x_3...$ is known. The problem, however, is that in many cases one does not even have a reasonable estimate of the true distribution. In order to overcome this problem a universal distribution $\xi$ is defined as a weighted sum of distributions $\mu_i\inM$, where $M$ is any countable set of distributions including $\mu$. This is a generalization of Solomonoff induction, in which $M$ is the set of all enumerable semi-measures. Systems which predict $y_t$, given $x_1...x_{t-1}$ and which receive loss $l_{x_t y_t}$ if $x_t$ is the true next symbol of the sequence are considered. It is proven that using the universal $\xi$ as a prior is nearly as good as using the unknown true distribution $\mu$. Furthermore, games of chance, defined as a sequence of bets, observations, and rewards are studied. The time needed to reach the winning zone is bounded in terms of the relative entropy of $\mu$ and $\xi$. Extensions to arbitrary alphabets, partial and delayed prediction, and more active systems are discussed.<|reference_end|>
@article{hutter2001general,
    title={General Loss Bounds for Universal Sequence Prediction},
    author={Marcus Hutter},
    journal={Proc. 18th Int. Conf. on Machine Learning ICML (2001) 210-217},
    year={2001},
    number={IDSIA-03-01},
    archivePrefix={arXiv},
    eprint={cs/0101019},
    primaryClass={cs.AI cs.LG math.ST stat.TH}
}