On Delayed Prediction of Individual Sequences

[摘要] Prediction of individual sequences is investigated for cases in which the decision maker observes a delayed version of the sequence, or is forced to issue his/her predictions a number of steps in advance, with incomplete information. For finite action and observation spaces, it is shown that the prediction strategy that minimizes the worst-case regret with respect to the Bayes envelope is obtained through sub- sampling of the sequence of observations. The result extends to the case of logarithmic loss. For finite- state reference prediction strategies, the delayed finite-state predictability is defined and related to its non-delayed counterpart. As in the non-delayed case, an efficient on-line decision algorithm, based on the incremental parsing rule, is shown to perform in the long run essentially as well as the best finite-state strategy determined in hindsight, with full knowledge of the given sequence of observations. An application to adaptive prefetching in computer memory architectures is discussed. 39 Pages

[发布机构] HP Development Company

[学科分类] 计算机科学（综合）

[关键词] delayed prediction;sequential decision;on-line algorithms;general loss functions;Lempel-Ziv algorithm