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' or
'no prediction'. We will say that for a sequence of bits the loss of a strategy
is the number of wrong predictions minus the number of right predictions. In
this paper we are interested in strategies that never have a (expected) loss
over any string -- for example the strategy that always makes no prediction can
never have a loss however it also never has a gain. We would also like to have
a small regret against the strategy that always predicts 1 or always predicts
0. It can be shown that any strategy that has a positive gain over some
sequence must also have a positive loss over some sequence. But we can show
that there is a strategy that has a small regret and exponentially small loss
(in expectation). For a sequence of length $T$ our strategy has an amortized
per time step regret $\epsilon $ and loss $e^{-\epsilon^2 T}/\sqrt{T}$ in
expectation for all strings.