Tractability of batch to sequential conversion

Abstract

We consider the problem of converting batch estimators into a sequential predictor or estimator with small extra regret. Formally this is the problem of merging a collection of probability measures over strings of length 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's famous estimator. Our main technical contribution is to determine the computational complexity of sequential estimators with good guarantees in general. We conclude with an open problem on how to derive tractable sequential from batch estimators with good guarantees in general. Show more