Abstract: Consider a sequence of bits where we are trying to predict the next
bit from the previous bits. Assume we are allowed to say `predict 0' or `predict
1', and our payoff is *+1* if the prediction is correct and *-1*
otherwise. We will say that at each point in time the loss of an algorithm is the
number of wrong predictions minus the number of right predictions so far. In this
paper we are interested in algorithms that have essentially zero (expected) loss
over any string at any point in time and yet have small regret with respect to
always predicting *0* or always predicting *1*. For a sequence of
length *T* our algorithm has regret *14ε T * and loss
*2√Te ^{-ε2 T} * in expectation for all
strings. We show that the tradeoff between loss and regret is optimal up to
constant factors. Our techniques extend to the general setting of