Minimax regret under log loss for general classes of experts
We study sequential strategies for assigning probabilities to the elements that may appear next in a sequence of data. The goal is to minimize the regret under log loss over the worst possible sequence. That is, to minimize the worst-case drop in the log-likelihood of the final sequence when measured under the assigned probabilities, as opposed to being measured under the best assignment in a given class of strategies (or experts). Using tools from empirical process theory, we prove a general upper bound on the best possible (minimax) regret that depends on the metric properties of the class of experts. This extends previous results by Opper and Haussler. In the special case of parametric experts, we obtain nonasymptotical versions of results proven by Rissanen and others under much stronger conditions on the expert class. Finally, we point out a suboptimal behavior of the popular Bayesian weighted average algorithm.