Worst Case Prediction over Sequences under Log Loss

. We consider the game of sequentially assigning probabilities to future data based on past observations under logarithmic loss. We are not making probabilistic assumptions about the generation of the data, but consider a situation where a player tries to minimize his loss relative to the loss of the (with hindsight) best distribution from a target class for the worst sequence of data. We give bounds on the minimax regret in terms of the metric entropies of the target class with respect to suitable distances between distributions. 1. Introduction. The assignment of probabilities to the possible outcomes of future data which is based on past observations has important applications to prediction, data compression and gambling. In a scenario where the data are assumed to occur at random with an unknown probability distribution, this problem can be treated as a well known statistical estimation problem. Optimal strategies can be found within a game theoretic approach, where a statistician ..