@inproceedings{6157b7ddcddb4449a72885f49c70a075,
title = "Offline to online conversion",
abstract = "We consider the problem of converting offline estimators into an online predictor or estimator with small extra regret. Formally this is the problem of merging a collection of probability measures over strings of length 1,2,3,… into a single probability measure over infinite sequences. We describe various approaches and their pros and cons on various examples. As a side-result we give an elementary non-heuristic purely combinatoric derivation of Turing{\textquoteright}s famous estimator. Our main technical contribution is to determine the computational complexity of online estimators with good guarantees in general.",
keywords = "Batch, Bayes, Combinatorics, Estimation, Good-Turing, Laplace, Normalization, Offline, Online, Prediction, Probability, Regret, Ristad, Sequential, Time-consistency, Tractable",
author = "Marcus Hutter",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2014.; 25th International Conference on Algorithmic Learning Theory, ALT 2014 ; Conference date: 08-10-2014 Through 10-10-2014",
year = "2014",
doi = "10.1007/978-3-319-11662-4_17",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "230--244",
editor = "Peter Auer and Alexander Clark and Thomas Zeugmann and Sandra Zilles",
booktitle = "Algorithmic Learning Theory - 25th International Conference, ALT 2014, Proceedings",
address = "Germany",
}