We discuss the game of sequentially assigning probabilities
to symbols in a sequence. A cumulative logarithmic (entropic)
loss may be interpreted as the codelength for the sequence.
We give general upper and lower bounds on the cumulative minimax
regret (redundany) for two scenarios: In the random case, the
data are generated independently from an unknown distribution
from a given family and the player tries to minimize the expected
loss for the worst distribution in this family. In the worst
case over sequence scenario, NO probabilistic assumption about
the generation of the data is made. The player compares her
loss with the the loss of an adversary who knows the entire
sequence in advance and uses always the best distribution from
the family for each given sequence. In both cases it is possible
two bound the cumulative regret in terms of a metric entropy
for the family of distributions.
Back to Workshop Schedule