Predicting a binary sequence almost as well as the

optimal biased coin

Yoav Freund
AT&T Laboratories
yoav@research.att.com
http://www.research.att.com/orgs/ssr/people/yoav/

April 3, 1996

Abstract
We apply the exponential weight algorithm, introduced and Littlestone and
Warmuth [17] and by Vovk [24] to the problem of predicting a binary sequence
almost as well as the best biased coin. We first show that for the case of the logarith-
mic loss, the derived algorithm is equivalent to the Bayes algorithm with Jeffrey’s
prior, that was studied by Xie and Barron under probabilistic assumptions [26].
We derive a uniform bound on the regret which holds for any sequence. We also
show that if the empirical distribution of the sequence is bounded away from 0
and from 1, then, as the length of the sequence increases to infinity, the difference
between this bound and a corresponding bound on the average case regret of the
same algorithm (which is asymptotically optimal in that case) is only 1 2. We
show that this gap of 1 2 is necessary by calculating the regret of the min-max
optimal algorithm for this problem and showing that the asymptotic upper bound
is tight. We also study the application of this algorithm to the square loss and show
that the algorithm that is derived in this case is different from the Bayes algorithm
and is better than it for prediction in the worst-case.

1 Introduction
In this paper we show how some methods developed in computational on-line learning
theory can be applied to a very basic statistical inference problem and give what we
think are surprisingly strong results. In order to present these results within context,
we find it necessary to review some of the standard statistical methods used for this
problem.
Consider the following very simple prediction problem. You observe a sequence of
bits
1 
2  one bit at a time. Before observing each bit you have to predict its value.
The prediction of the  th bit
 is given in terms of a number
 0  1 . Outputting
  close to 1 corresponds to a confident prediction that
 1 while  close to 0

corresponds to a confident prediction that
 
0. Outputting  1 2 corresponds 
to making a vacuous prediction.1 Formally, we define a loss function 
from  


0  1 
0  1 to the non-negative real numbers 
. The value of  
 is the loss  
we associate with making the prediction  and then observing the bit

 . We shall
consider the following three loss functions: the square loss 2 

2 , the log      
  
loss log 


log      
1
log 1 and the absolute loss 1 

.      
The goal of the prediction algorithm is to make predictions that incur minimal
loss. Of course, one has to make some assumption about the sequences  in order to
have any hope of making predictions that are better than predicting 1 2 on all of the
turns. Perhaps the most popular simple assumption is that the sequence is generated
by independent random coin flips of a coin with some fixed bias . The goal is to
find an algorithm that minimizes the total loss incurred along the sequence. However,
as the minimal achievable loss depends on , it is more informative to consider the
difference between the incurred loss and the minimal loss achievable by an “omniscient
statistician” who knows the true value of and chooses the optimal prediction ˜ for this
distribution.
Let  
1  
denote a binary sequence of length  , and let   denote

the distribution of such sequences where each bit is chosen independently at random
to be 1 with probability . The average regret for the prediction algorithm  is the
average difference between the total loss incurred by  and the total loss incurred by
an omniscient statistician. In symbols, this is: 2
)
* *
 av       "! $#%'&(#
   
 ,  ˜ 
 . -  1
+ 1  + 1

We use the term average regret to differentiate it from the worst-case regret which we
define below.
In general, the optimal algorithm for minimizing the average regret is the Bayes
algorithm. There are two variants of the Bayesian methodology, we call these variants
the subjective Bayesianism and the logical Bayesianism:
/ Subjective Bayesianism
In this view, the notion of a distribution over the set of models is defined, axiomat-
ically, as a representation of the knowledge, or state of mind, of the statistician
regarding the identity of the correct model in the model class. Choosing an
appropriate prior distribution 0 is, in this case, the act of compiling all such
knowledge, that exists before seeing the data, into the form of a prior distribu-
tion. After 0 has been chosen, the goal of a prediction algorithm is to minimize
the expected average regret, where is chosen at random according to the prior
1 Strictly speaking, there exist non-symmetric loss function for which the vacuous prediction is not 1 2. 1
In this paper we concentrate on symmetric loss functions for which the vacuous prediction is always 1 2.
2 For the sake of simplicity, we restrict the discussion in the introduction to deterministic prediction
1
algorithms. In this case the prediction is a function of the previously observed bits.

1
 distribution and then $ is generated according to , i.e. to find  that minimizes
! &%
 av       . It is easy to show that the Bayes algorithm with 0 as a prior
achieves this optimality criterion with respect to the log loss.
/ Logical Bayesianism
In this view, which is attributed to Wald, no assumption is made on how the
model is chosen, and the optimality criterion is that the average regret for the
worst-case choice of should be minimized. Interestingly, if the number of trials
 is fixed ahead of time then the min-max optimal strategy for the adversary
who chooses the value of is to choose it according to some fixed distribution,

worst(T) , over 0  1 (see e.g. Blackwell [3] Ferguson [11] and Haussler [13]).
The min-max optimal prediction  strategy for this case is the Bayes prediction
algorithm with the prior set to worst(T) . However, these prior distributions are
very peculiar (see e.g. [28]), calculating them is hard, and, most importantly,
they are optimal only if  is known in advance. A more attractive option is to find
an algorithm which does not need to know  in advance. Bernardo [2] suggested
using the Bayes algorithm with Jeffrey’s prior 3 (which we denote here by BJ), and
Clarke and Barron [5] proved that this choice is asymptotically optimal for the
models that are in the interior of the set. Finally, Xie and Barron [26] performed
a detailed analysis of the BJ algorithm for the model class of biased coins and
have shown that for any  0 and any 0   1:4

1 1
lim  max  av  BJ      ln  ln   2

  &  1    2 2 2
These two methodologies, and most prediction methodologies in general, are based
on the following statistical assumption. One assumes that the sequence to be predicted
is generated by independent random draws from some unknown distribution that is
selected, once and for all, from a known class of distributions. The difference between
Bayesian and worst-case methodologies regards only the way in which the specific
distribution is chosen from the class. However, the assumption that a particular source
of sequences is really a so-called “random” source is problematic because in most real
world cases it is almost impossible to verify that a particular data source is indeed a
random source.5 Moreover, because of the lack of data or computing power, one often
wants to use a simple stochastic model even in situations where it is known that the
sequence is generated by a much more complex random process or by a mechanism
which is not random at all!
1 1
3 Jeffrey’s prior for this case is also known as the Krichevsky-Trofimov prior or the Dirichlet-  1 2  1 2 

prior, see Equation (28) for the exact definition.

4 Xie and Barron give their results in a slightly stronger form, our results can be presented in that form

too.
5 It seems that the most accepted approach to measuring the randomness of a particular sequence is to

measure its Kolmogorov complexity (see e.g.[15]), in other words, to compare the length of the sequence
with the length of the shortest program for generating it. Random sequences are those for which the program
is not significantly shorter than that of the sequence. While this measure is mathematically very elegant, it is
usually not a practical measure to compute.

2
 The question is: what weaker formal assumption can be made that would still
correspond to our intuition that a biased coin is a good approximate model for the data?
The assumption we study in this paper is that there exists a fixed model whose total loss
on the sequence is non-trivial. This direction builds upon the ideas of “prediction in
the worst-case” [12], “on-line learning” [7, 16, 17, 24], “universal coding” [9, 22, 20],
“universal portfolios” [8, 6] and “universal prediction” [10].
We define trivial per-trial loss as the maximal loss incurred by the best prediction.
More formally, it is
 inf
&
 0  1  max

 0  1
 
   3
It is easy to verify that the prediction that minimizes the loss for the log loss, the square
 2 and that
loss and the absolute
 loss is 1 the corresponding values of the trivial loss are
log 2, 1 4 and 1 2 respectively. We say that a prediction algorithm makes non-trivial
predictions on a particular sequence
1  
if the total loss the algorithm incurs on
the whole sequence is significantly smaller than  .

In the case of the biased coins, the assumption is that there exists some fixed value
of  0  1 for which the total loss
 + 1  
  is significantly smaller than  .
We do not define directly the concept of a “significant” difference. Instead, we define
our requirements from the prediction algorithm relative to the total loss incurred by
the optimal value of . We can then say that  is a significant difference in the total
prediction loss if there exists a prediction algorithm whose total loss is guaranteed to
be smaller than  if  
 + 1  
   .
We measure the performance of a prediction algorithm on a specific sequence

1  
using the difference

* *
  & min    
  
 

+ 1
 0  1  + 1

The worst-case regret of a prediction algorithm  is the maximum of this difference

for sequences of length  is defined to be
)
* *
 wc      max# 
   
   min
&
 0  1  + 1
 
 .-  4
+ 1

We denote the argument that minimizes the second term by ˆ. Note that for the log loss
and for the square loss ˆ is equal to the fraction of 1’s in  . We refer to the fraction of
1’s in  as the empirical and denote it by ˆ. Clearly,  ˆ is always a rational
number of the form
 distribution
 for some integer in the range 0    . For the absolute loss,

ˆ is 1 if ˆ  1 2 and is 0 otherwise. As we shall see, we can prove slightly better

bounds on the regret if we allow a dependence on ˆ, we therefor define the quantity
)
ˆ  * *
 wc     max    
   & min  
 -  5
; ˆ $# + ˆ
 
$#  
+ 1
 0  1  + 1

3
 Consider the situation in which the sequence is generated by a random source and
the analysis is done in terms of the worst-case regret. We have that
 wc     
*
max max
$# &ˆ
 0  1    
   ˆ 
 
(6)
+ 1
*
max !
& ˆ
 0  1  + 1   
     ˆ 
 


& $
 # '
% (
& # max (7)

*
max ! $# %'&(#    
    
 


(8)
& + 1
max  av       (9)
&
The first inequality follows from replacing a maximum with an average and the second
inequality follows from replacing the optimal per-sequence choice of ˆ with a global
choice of . We thus see that the worst-case regret is an upper bound on the average-
case regret. This relation is not very surprising. However, the surprising result, which
we prove in this paper, is that for the class of biased coins and with respect to the log
loss the worst case regret is only very slightly larger than the average case regret, as
described in Equation (2). In this paper we prove the following bound on the worst
case regret of the BJ algorithm for this problem. For any   0 and for any 0    1:
)
1 1
lim max  wc  BJ    ln  - ln    10

 # ; ˆ 
 # 
     1  
  2 2 2

Observe
 that the difference between this bound and the bound given in Equation (2) is
just 1 2.
We also show that this tiny gap is necessary. We do this by calculating the min-max
optimal  algorithm for the  worst-case regret and showing that its asymptotic difference
from  1 2  ln  is also  1 2  ln  2  . The only asymptotic advantage of the min/max

algorithm is for sequences with empirical distribution very close to either 0 or 1, in

which case the regret is larger by an additional 1 2. Thus the algorithm suggested by
the logical Bayesian analysis is also (almost) optimal with respect to the worst-case
regret. This result complements the results of Xie and Barron [26].
This result also merges nicely with the method of stochastic complexity advocated
by Rissanen [19]. That is because any prediction algorithm can be translated into a
coding algorithm and vice versa (for example, using arithmetic coding [20].) The length
of the code for a sequence $ is equal (within one bit) to the cumulative log loss of the
corresponding prediction algorithm on the same sequence. Thus our result means that
the Bayes method using Jeffrey’s prior is the optimal universal coding algorithm for the
models class of biased coins, including the additive constant in the expression for the
min-max redundancy, for all sequences but those whose empirical distribution is very
extreme.

4
 Thus, if our goal is to minimize the cumulative log loss or the total code length then
stochastic complexity, logical Bayesianism and worst-case prediction all suggest using
the same algorithm and all achieve essentially identical bounds. However, if we are
interested in a loss function different than the log loss, then the worst-case methodology
suggest an algorithm that differs significantly from the Bayes algorithm. Specifically,
we show that the algorithm suggested for  2  
 is very different from the algorithm
that is suggested by any Bayesian approach. Moreover, we give an example for which
the worst-case regret of the Bayesian algorithm is significantly larger than that of the
exponential weights algorithm.6
The prediction algorithms presented in this paper are very efficient. The prediction
rule is a function only of  , the number of bits that have been observed, and , the
number of bits that were equal 1. The suggested prediction rule for the cumulative log
loss is



1 2


1
  11
and a possible prediction rule for the square loss is




erf  2   
$

 2

1 


1
1 erf  2 
   
ln ln
1 4  2 erf   2 
erf   2  
1 $ 
 1
 1

 12
where  &
2  
erf ( )  
2


0

is the cumulative distribution
 for largefunction of the normal distribution. Both prediction rules
are close to   and  , but are slightly different for the initial part of
the sequences.
The paper is organized as follows. In section 2 we review the exponential weights
prediction algorithm and the well-known bound for the case where the number of
models is finite. In Section 3 we show how the algorithm and its analysis can be
extended to the case in which the class of models is uncountably infinite. In Section 4
we present our basic bound, that is based on the Laplace method of integration. In
Section 5 we apply our method to the case of the log-loss and in Section 6 we compare
our bound to other bounds regarding the cumulative log loss. In Section 7 we apply
our method to the square loss and in Section 8 we briefly review what is known about
the absolute loss. We conclude with some general comments and open problems in
Section 9. Details of the proof are given in the appendix.
6 It is a trivial observation that any prediction algorithm can be viewed as a Bayesian algorithm if the prior

distribution is defined over the set of sequences, rather than over the set of models. However, this observation
is of little value, because it does not suggest an interesting way for finding this distribution or for calculating
the predictions that would be generated by using it.

5
2 The algorithm
The algorithm we study is a direct generalization of the “aggregating strategy” of
Vovk [24, 23], and the “Weighted Majority” algorithm of Littlestone and Warmuth [17].
We refer to it as the “exponential weights” algorithm and denote it by EW. We denote
a class of models by . In this section we assume that is a finite set of values in 0  1
whose element are 1   
. We denote the cumulative loss of the model  at time

 by     
 + 1    
   .
The algorithm is simple. It receives two positive real numbers
and  , as pa-
rameters. With each model in the class, at each time step  , it associates a weight
   exp 
    
, The initial weights sum to 1, and, when the set of models is

finite, the initial weights are usually set to  1   1 for all models 1   .
The prediction of the algorithm at time  , which we denote by   , is a function of the
weights associated with the models at that time. Before describing how the predictions
are chosen, we describe the bound on the total of the algorithm. This might seem
backwards, but the choice of prediction is trivial once the bound is given. The bound
on the total loss of the algorithm, for every time step  , is of the form

* *

 
     ln
 1    13
 + 1 + 1

If we want this bound to hold at all times for all sequences, it is clear how to make the
predictions. The prediction should be chosen so that for both possible values of
  1


the bound will hold at  1 given that it holds at  . Specifically, this means that the
prediction   1 is chosen so that

  ln

 + 1    
   1    ln

 + 1    1   (14)
and   ln

 + 1    
    0    ln

 + 1    1   

The way this bound is usually used is to observe that if the total loss of the best
model after observing all of $ is   min     then the weight associated

with the best model, and thus also the total weight, are lower bounded by exp  
  .
Plugging this into Equation (13), we find, after some simple algebra, that

* 

  
    ln 
 
  15
 + 1

Thus if 
1 we immediately get a nice simple bound on the worst-case regret of the
algorithm: 
 wc  !      ln  16
It is thus also clear that we would like 
to be as small as possible. 1

Haussler, Kivinen and Warmuth [14] studied the problem of combining models for
predicting a binary sequence in detail. They give a formula for calculating the minimal

6
value of   for any loss function within a broad class such that the bound (13) holds
for
1  . In this paper we use their results for the log loss the square loss and the
absolute loss.

3 Uncountably infinite sets of models

We now apply the exponential weights algorithm to the case where the set of models
is the set of all biased coins. The natural extension of the notion of the weights that
are associated with each model in a finite class is to assume that there is a measure
defined over the set of models 0  1 ,7 and as the initial weights sum to one, the
initial measure, denoted by 0 1 is a probability measure. We shall sometimes refer to
this initial probability measure as the prior. For   1 we define a measure 0     as
follows:   1 
      &  
 0   1    0    

where 0    denotes integration with respect to the measure 0  over  

.
Similarly to the prediction rule given in Equation (14) the prediction at time  is any
   0  1 which satisfies
)
 

  1  0  & 


 0      ln 0
1

0    - (17)
 
)
0
1
0   
 1 
  1  &  
1
 0    -
and  1     
 0
 ln
1
0 0   

The bound that one is guaranteed in this case is

)
*  1



        ln 0   1   -  18
 + 1 0

Interestingly, the set of pairs  

 for which the bound of Equation (18) is guaranteed
is identical to the set for which Equation (13) holds. The proofs are also identical, one
has only to replace sums by integrals in the proofs given by Haussler et al. However,
it is not immediately clear how to relate this bound on the total loss  to the worst-case
regret. As the number of models is infinite a bound of the form  log is meaningless
and we need a different bound. In the rest of the paper we develop a bound which
is appropriate for the model class of the biased coins and is based on the method of
Laplace integration.
7 A measure over a space Ω is a function from the set of measurable sets (in our case, the Borel sets in

Ω  0  1 ) to the real numbers in the range  0  1 . A probability measure is a measure that assigns the value
1 to the set that consists of the whole domain.

7
 From Equation (18) we get the following bound on the worst-case regret

 wc  EW   

(19)
 ˆ
 ˆ +   max   ln 

1
0   1         
 ;  + 0


0

Notice now that in the case of the biased coin the cumulative loss of model on the
sequence  can be written in the form
ˆ
 1   ˆ   0



       1 


Using this expression for both   ˆ   and 0
  1   and rewriting the second term
(which is always positive) in an exponential form we get
 ˆ
 1   ˆ   0   
 

 wc  EW    ˆ +   max   ln 
1
exp   
 1  

 0 1   
 ;  + 0


 0


 ˆ
 1   ˆ    0  ˆ


  ln exp  
 1  ˆ

 

and we can combine the exponents of the two terms and get:
)  1   ˆ &  
 wc  EW    ˆ +   max   ln
  0 1  .-  20
 ;  + 0




where 

  ˆ    1 ˆ  1   ˆ    0   ˆ  0






  1   ˆ  1
  21

We refer to  ˆ   as the gap function. The gap function is proportionalto the additional
loss-per-trial that the model suffers over and above the model
 ˆ which is the optimal
model for any sequence whose empirical distribution is ˆ. Thus the exponent of the
integral in Equation 20 is zero when is an optimal model and is negative elsewhere.

4 Laplace method of integration

In this section we describe a general method for calculating the integral in Equation (20).
The derivation given in this section was done independently, for a much more general
scenario, by Yamanishi in [27]. However, as we shall see, this method, by itself, is not
sufficient to prove a bound on the worst-case regret. Later in this paper we describe the
additional steps required to do that.
We require that the loss function  
 has the following three properties. It is
easy to verify that the log loss and the square loss over the model class of biased coins
have properties 2 and 3. The proof that property 1 holds for these loss functions can be
found in Haussler et al [14].

8
 1.  
 
is   1   achievable for some 0 


. From here on we use the
symbol  to denote the minimal value that satisfies this criterion.
2. For all values of
,  
 has a continuous second derivative as a function of .
3. There exists a function ˆ : 0  1 
0  1 such that the unique optimal model for
 
any sequence 
  whose empirical distribution is ˆ is ˆ  ˆ  . We use ˆ to denote
$ˆ  ˆ  when ˆ is clear from the context.
The setting of the EW algorithm we suggest is to use the constants  and
1 

defined in condition 1 and to use as the initial probability measure the following density
measure:

0 1    
 
(22)



   
    
2
  1
where


 
2
&+& ˆ

and
  1
 
   & + &    

2

2
(23)
0 ˆ

The following theorem gives a bound on the performance of this algorithm:


Theorem 1 For any fixed 0  ˆ  1, the loss suffered by the exponential weights
algorithm described above on any sequence x whose empirical distribution is ˆ
satisfies
 wc       ˆ  2 ln 2  2 ln
 1    
 24

where  and are as defined above.

This bound is almost a bound on the worst-case regret. However, it is an asymptotic
result which applies only to sets of finite sequences in which all the sequences have the

same empirical distribution, ˆ. Of course, any sequence has some empirical distribution,

and so it belongs
 to some set of sequences for which  the theorem holds. However, the
term  1  might have a hidden dependence on ˆ.8 What we need is a uniform
bound, i.e. a bound that does not have any dependence on properties of the sequence.
To get such a bound we need a more refined analysis which, at this point, we know
how to do only for the special cases described in later sections. However, Theorem 1 is
important because it bounds the regret for important sets of sequences, and because it
suggests a choice for the initial probability measure.
The proof of Theorem 1 is based on the Laplace method of integration which is a
method for approximating integrals of the form
  
     
   25

any fixed 

8 As we show later, such a dependence does indeed exist, but it vanishes as

0.
    
if  1  for

9
for large values of  , when and are
the reals.9 The intuition



sufficiently smooth functions from 
  to
behind this method is that for large  the contribution of a
small neighborhood of  min  argmin    dominates the integral. Thus, by using a
Taylor expansion of    around   min one can get a good estimate of the integral.
The dependence of the contribution of the maximum on  depends on whether the
maximum is also a point of derivative zero. This is always the case if
  min  
and might be the case if 
or   . We concentrate on the first case. Laplace

method, or, more formally, Watson’s Lemma [25], gives us the following asymptotic
approximation for the integral in this case10

 
Theorem 2 (Watson) Let and be functions from the segment 
  to the reals.
Assume that for all   
  ,    0 and         2    exist and are continuous.
2

Assume also that there exists
  min   such that $  

 
0 for
    if and
only if   min, and that        +

expansion in a neighborhood of  min . Then
min
0. Finally assume that    has a Taylor

  

  
 
 
 
  min    2  2




   3 2 

 26
    + 
  2 
 min
We can now prove the theorem:

Proof of Theorem 1: We fix an empirical distribution ˆ and let   be any sequence
ˆ
whose empirical distribution is . we use the fact the 0 1 is defined by the density
function  and rewrite the bound given in Equation (20), without taking the maximum
over the sequence:
) 

* *  1
  
 ,      ˆ        '-

     ln exp 
+ 1 + 1 0

      , $  


This integral is of the form defined in Equation (25), where   


    and  min ˆ. From Watson’s Lemma we thus get that, for any fixed value of  ˆ:
ˆ


 1 
    ˆ  &   0 1      ˆ     2     3 2    27


ˆ 

0  &    & + & ˆ  ˆ 


2
2 

In order to minimize the bound, we want the integral to be large. More precisely, we
want to choose  so as to maximize the minimal value achieved over all choices of
ˆ
 0  1 .11 As  is a distribution, it is easy to see that the minimum of the first term
9 For
a good description of the Laplace method, see chapter 2 of Murray’s book [18].

 1
10 Seethe derivation of Equation (2.33) in [18].


11 Actually, if we fix , we need to consider only values of ˆ of the form
. Indeed, we can find slightly


better choices of  for fixed values of . However, our goal is to choose a single distribution that will work
well for all large . We thus have
is equivalent to considering all ˆ  0  1 .


to consider all rational ˆ, which, as the second derivative of  is continuous,

10
 
in the bound is maximized if the value of this term is equal for all values of ˆ. We thus
arrive at the choice of  given in Equation (22) which exactly cancels the dependence

on ˆ of the first term. We thus get

    
ˆ   2   3 2   
 1 


2 2
 ˆmax
  

  
   3 2  1


  


 0  1    & 2  ˆ   & + & ˆ  ˆ
2

and when we plug this estimate into the bound given in Equation 20 we get the statement
of the theorem.
We now move on to show that the suggested exponential weights algorithm does
indeed achieve a very strong bound on the worst-case regret for the log loss and for the
square loss on the class of biased coins.

5 Log-loss
The loss function in this case is  log   
  
 1, and the optimal value of for aloggiven  1  
   , the optimal
ˆ
parameters
are  1
sequence is ˆ .
It is easy to check that in this case the prediction rule
 1
 
  
 exp      ˆ ln ˆ  1  ˆ  ln  1  ˆ   0 1   
0

satisfies Equation (14) for the log loss. Note also that this rule is equivalent to the Bayes
optimal prediction rule using the prior distribution 0 1 .
The gap function in this case is (minus) the KL-divergence.
)  ) 
ˆ 1 ˆ
    log -   1   log 1  - 
KL   ˆ   
ˆ ˆ ˆ

The second derivative of


is the Fisher information:

 2

2

  
& + & ˆ  
$   
1

So the optimal prior is


1 1
 

 


& 
  & + & ˆ  
2
2  
$ 1  
  28

This prior is the Jeffrey’s prior for this model class, thus the algorithm suggested in this
case is the Bayes algorithm using Jeffrey’s prior (BJ).
To bound the worst-case regret we calculate the integral of Equation (18) which, in
this case, is equal to
 1
  KL (
 ˆ  & ) 
   
0

11
Details of this calculation will be given in appendix A. Here we state the resulting
bound:
Theorem 3 The regret of the Exponential weights algorithm over the class of biased
coins, which uses the prior distribution described in Equation (28) with respect to the
log loss is bounded, for any 

1 by

 wc  EW     ˆ  (29)
1

1
1 1
1
ln   1 ln    

2 2 2 2 2
  min  ˆ  1  ˆ    1 360   1 3

which implies that

1


 wc  EW   
2
ln   1 1  30
The last inequality
 shows that the regret of the exponential weights algorithm holds
uniformly for all ˆ  0  1 , i.e., for all sequences. It is worthwhile to consider the
more precise bound given in Inequality (29). If for some fixed   0 we have that
ˆ
   1    then, for 

1

the last two terms converge
ˆ  to zero  and the bound
converges to 21 ln  ln . This bound also holds if    1.
 2 2
However, if ˆ 0, we get a slightly larger bound of 21 ln 


 1 ln 
  1for.12any
 1
Finally, if
ˆ 
Θ  1  then we get an intermediate bound.
2 2 2

6 Comparison to other results regarding log-loss

It is interesting to compare these bounds to the ones given by Xie and Barron [26]. They
analyze the same algorithm on a very similar problem, but they consider the expected
regret and not the worst-case regret. As was shown in the introduction, the worst-case
regret upper bounds the average-case regret. However, our definition of regret is much
stronger then theirs, because we make no probabilistic assumption about the mechanism
that is generating the sequence. It is therefor surprising that the bounds that we get are
so very close to their bounds.
From the arguments given in the previous section we get that, Theorem 3 implies the
bound given in Equation (10). The difference between this  bound and the bound derived

by Xie and Barron [26] described in Equation (2) is  1 2  ln 2    1 2  ln  2  
0  5 nits
 
0  721 bits . In other words, knowing that the sequence is actually generated
by independent random draws of a random coin is worth less than one bit!
As Xie and Barron show, the BJ algorithm is not an asymptotically optimal algorithm
with respect to the average prior. That is because on the endpoints 0 and 1 the
loss is larger than for the interior points, and this difference does not vanish as  . 
by 1  2
where


In order to achieve the asymptotic min/max they suggest multiplying Jeffrey’s prior
  
 for some   1 2 and putting a probability mass of

12 Theactual asymptotic value of the regret (both worst case and average case) of the BJ algorithm for

ˆ 0 or ˆ 1 is slightly smaller: 21 ln
 1 ln  .
2

12

on each of the two points 
 
and 1    for some constant  . This reduces the
asymptotic average regret at the endpoints to the asymptotically optimal value without
changing the asymptotic average regret in the interior points. Similar observations and
the same fix hold for the worst case regret.
As we show  at the
end of the last section, the regret of algorithm BJ on the interior
of 0  1 is  1 2  ln   1 2 ln    2 , larger by 1 2 from the optimal performance with
respect to the average regret. We now show that this small gap cannot be removed. We
do this by calculating the regret of the min-max optimal algorithm for the worst-case
regret with respect to the log loss.
We use a rather well known lemma, stated for instance in Starkov [21, 22] and in
Cesa-Bianchi et al. [4]. The lemma states that the min/max optimal prediction algorithm
defines the following distribution over the set of sequences of length  :

    1 max&  &     where
 *
max

&     31
$ # &


and that the regret suffered by this optimal algorithm on any sequence is equal to ln .

Using this we can explicitly calculate the worst-case regret of the min/max optimal
algorithm (this result was previously shown by Starkov [22]).
Lemma 1 The worst-case regret of the min/max optimal prediction algorithm for se-
quences of length  , which we denote by MM , with respect to the class of biased coins
and the log loss, is

) 
*    
 wc  MM   ln     - (32)
+

0
1
ln  

1

1
ln 
 2   1 

2 2 
The proof is given in Appendix B.

7 Square loss
In this section we consider the loss function 
  
  2. As was shown 
 by
Vovk [24] and Haussler et al.  the optimal parameters in this case are  1 2,
2
and the optimal
 model is ˆ ˆ. The gap function in this case is
ˆ
   1   ˆ 2   1   2

 1   ˆ   0   ˆ 2   0   2 
And its second derivative is a constant:



  4
So the optimal prior is the uniform distribution
 
 1

13
 To bound the worst-case regret we calculate the integral of Equation (18) which, in
this case, is equal to
 1
 
  
exp  2 ˆ   1  ˆ  2   1   2  2  1  ˆ    0  ˆ 2   0   2  
0

Details are given in appendix C. The resulting bound is:

Theorem 4 The regret of the Exponential weights algorithm over the class of biased
coins, which uses the uniform prior distribution with respect to the the squared loss,
for any 

1, is bounded by
 1
1 2 1
 wc  EW    ˆ   ln  ln
2 erf   ˆ

ˆ  ln   33
4   erf  1     4 2

which implies
1
1 2 1
 wc  EW   
4
ln  ln
2 erf  2
 ln 
4 2
 34

Similar to the detailed analysis of the log-loss case, Inequality (34) gives us a
uniform upper bound that does not depend on the sequence, while if we assume that
ˆ
   1    for some constant   0 then Inequality (33) gives a slightly better
asymptotic bound. In the second case each of the two erf ( ) functions converges   to 1
and so the second term vanishes and we are left with the negative term   1 4  ln  2  .
 
If ˆ 0 or ˆ 1 then only one of the two erf ( ) terms

converges to 1 while the other

remains 0, and we get an additional term of ln  2  2 in the regret. For the square loss
ˆ
the restriction on the distance between  and 0  (or 1) is a bit stronger then
 in the log-loss
ˆ
case. Here we have that if    
 1   
 for some   1 2 then the better
bound holds and if ˆ  Θ  1  then we get a bound that is between the interior
bound and the bound for ˆ 0.
Two comments are in order. First, although we have not concerned ourselves with
the computational efficiency of our algorithms, both the log-loss version and the square-
loss version require small constant time to calculate the predictions, whose formulas
are given in Equations 11 and 12. Second, it is not hard to give examples of finite
model classes in which using the EW algorithm is much better than using any Bayes
algorithm when the data is generated by a model outside the class (See Appendix D). We
conjecture that such an example exists also for the continuous model class 0  1 .

8 Absolute Loss
In this section we consider the absolute loss, which has very different properties than
the log loss and the square loss. Haussler
 et al. [14] there is no finite value of  such
that the bound (13) holds for
1  . Moreover, as was shown by Cesa-Bianchi at

14
al. [4], there is no prediction algorithm whose worst-case regret does not depend  on
the loss of the best model. On the other hand, there are choices of  and
 1  for
which Equation (13) holds, and Cesa-Bianchi et. al. have shown that, based on this

the worst-case regret of this algorithm is bounded



fact, an exponential weights algorithm for finite model classes,
by  ln
 can be devised. And
  .
As we cannot choose  finite and

1  for the multiplicative
 weights algorithm,
we cannot use the technique of Theorem 1 for this case. However, we do not need to
use an infinite set of models in our analysis for this case. This is because in this case
the optimal model in the class 0  1 is always either 0 or 1. Thus we can
consider a EW algorithm that combines only these two models and get close to optimal
bounds on the regret.

9 Conclusions and open problems

We have demonstrated, in a simple case, that the Bayes algorithm that has been shown
by Xie and Barron to be optimal with respect to the average-case regret is also optimal
with respect to the worst-case regret. Moreover, the bound on the worst-case regret is
only very slightly worse than the average-case regret.
We have also shown that a very different algorithm results if one is interested in the
square loss, rather than in the log loss.
These results give evidence that sometimes accurate statistical inference can be done
without assuming that the world is random. We are currently working on extended this
work to more general classes of models of sequences over larger alphabets.

Acknowledgments
Special thanks to Sebastian Seung for his help on understanding and solving the integral
equations used in this paper. Thanks to Andrew Barron, Meir Feder, David Haussler,
Rob Schapire, Volodya Vovk, Qun Xie and Kenji Yamanishi for helpful discussion and
suggestions.

References
[1] Abramowitz and Stegun. Handbook of Mathematical Functions. National Bureau
of Standards, 1970.
[2] J. M. Bernardo. Reference posterior distributions for bayesian inference. J. Roy.
Statistic. Soc. Ser. B., 41:113–147, 1979.
[3] David Blackwell and M.A. Girshick. Theory of Games and Statistical Decisions.
Dover Publications, Inc, New York, 1954.

15
 [4] Nicolò Cesa-Bianchi, Yoav Freund, David P. Helmbold, David Haussler, Robert E.
Schapire, and Manfred K. Warmuth. How to use expert advice. In Proceedings
of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages
382–391, 1993. To appear, Journal of the Association for Computing Machinery.
[5] Bertrand S. Clarke and Andrew R. Barron. Jeffrey’s prior is asymptotically least
favorable under entropic risk. J. Stat Planning and Inference, 41:37–60, 1994.
[6] T. Cover and E. Ordentlich. Universal portfolios with side information. Unpub-
lished Manuscript, 1995.
[7] Thomas M. Cover. Behavior of sequential predictors of binary sequences.
[8] Thomas M. Cover. Universal portfolios. Mathematical Finance, 1(1):1–29, Jan-
uary 1991.
[9] L. D. Davisson. Universal noiseless coding. IEEE Trans. Inform. Theory, 19:783–
795, 1973.
[10] M. Feder, N. Merhav, and M. Gutman. Universal prediction of individual se-
quences. IEEE Transactions on Information Theory, 38:1258–1270, 1992.
[11] Thomas S. Ferguson. Mathematical Statistics: A Decision Theoretic Approach.
Academic Press, 1967.
[12] Dean P. Foster. Prediction in the worst case. The Annals of Statistics, 19(2):1084–
1090, 1991.

[13] David Haussler. A general minimax result for relative entropy. Unpublished
manuscript.
[14] David Haussler, Jyrki Kivinen, and Manfred K. Warmuth. Tight worst-case loss
bounds for predicting with expert advice. In Computational Learning Theory:
Second European Conference, EuroCOLT ’95, pages 69–83. Springer-Verlag,
1995.
[15] Ming Li and Paul Vitányi. An introduction to Kolmogorov complexity and its
applications. Texts and Monogaraphs in Computer Science. Springer-Verlag,
1993.
[16] Nick Littlestone. Learning when irrelevant attributes abound. In 28th Annual
Symposium on Foundations of Computer Science, pages 68–77, October 1987.
[17] Nick Littlestone and Manfred K. Warmuth. The weighted majority algorithm.
Information and Computation, 108:212–261, 1994.
[18] J.D. Murray. Asymptotic Analysis. Springer Verlag, 1973.

16
[19] Jorma Rissanen. Stochastic Complexity in Statistical Inquiry, volume 15 of Series
in Computer Science. World Scientific, 1989.
[20] Jorma Rissanen and Glen G. Langdon, Jr. Universal modeling and coding. IEEE
Transactions on Information Theory, IT-27(1):12–23, January 1981.
[21] Yu. M. Shtarkov. Coding of descrete sources with unknown statistics. In I. Csiszar
and P. Elias, editors, Topics in InformationTheory, pages 559–574. North Holland,
Amsterdam, 1975.

[22] Yu. M. Shtarkov. Universal sequential coding of single messages. Problems of

Information Transmission, 23:175–186, July-September 1987.
[23] V. G. Vovk. A game of prediction with expert advice. In Proceedings of the Eighth
Annual Conference on Computational Learning Theory, 1995.
[24] Volodimir G. Vovk. Aggregating strategies. In Proceedings of the Third Annual
Workshop on Computational Learning Theory, pages 371–383, 1990.
[25] G. N. Watson. Theory of Bessel functions. Cambridge University Press, 1952.
[26] Qun Xie and Andrew Barron. Minimax redundancy for the class of memoryless
sources. Unpublished Manuscript, 1995.
[27] Kenji Yamanishi. A decision-theoretic extension of stochastic complexity and its
applications to learning. Unpublished Manuscript, 1995.
[28] Zhongxin Zhang. Discrete Noninformative Prioirs. PhD thesis, Yale University,
1994.

A Proof of Theorem 3
We want to calculate the following integral:
 

( ˆ & )
1
  
   KL

Which we can expand and write as follows:

   
1
1 ˆ ˆ 1 
exp  log ˆ  1  log  ˆ 
$ 1   1
0
 
1 1 ˆ   1   ˆ   1 2 
ˆ ˆ  ˆ  1   ˆ  1 2
 1    
  1  0

Luckily, the last integral


is a well studied

quantity,
 called the Beta function. More
specifically, it is   ˆ 1 2    1  ˆ  1 2  , which can also be expressed in terms

17
of the Gamma function, 

 Γ 
 Γ    Γ


. 13
Using these relations we
get:
    ˆ

1 2    1  ˆ


1 2
( ˆ & )
1
  
   KL
ˆ ˆ  ˆ  1  ˆ
0
ˆ
 
 1   


Γ  1 2 Γ    1  ˆ 1 2

    1   ˆ
Γ  1  ˆ ˆ  1  ˆ  

Plugging this formula into Equation 20 we get:

Γ  ˆ

1 2 Γ    1 
ˆ

 1 2
 ln
   ˆ  1  ˆ
Γ  1  ˆ ˆ  1  

ln Γ  


1


ln



   ˆ ln  ˆ
 1   ˆ ln  1   ˆ 
 ln Γ    ˆ
1 2  ln Γ    1  ˆ 


1 2

The asymptotic expansion of ln Γ   for large values of  can be used to give upper and
lower bounds on this function for positive values of  (See Equations 6.1.41 and 6.1.42
in [1]).

 1 2 ln 

 1 2 ln 2 
1
12 
 1
360  3

 ln Γ     (35)
 1 2 ln 
 

 1 2 ln 2 
1
12 
Using these bounds we get the statement of the theorem (details in appendix A).

ln Γ  

1  ln Γ   ˆ

1 2  ln Γ    1   ˆ
1 2
ln


  

 ˆ ln  ˆ   1   ˆ ln  1   ˆ 



1 2  ln 

1  

1


 1 2 ln  2 
1


12   1


  ˆ
ln   ˆ

  1 2 ln  2 , 12
1 2


 ˆ

1 2
1
1
ˆ
 ˆ

 1 2 360   1 2 3
   1   ˆ ln    1   ˆ
1 2
   1   ˆ
1 2  1 2 ln 2   1


12    1  ˆ 1 2

1
360    1   ˆ
1 2 3


ln



   ˆ ln  ˆ
 1   ˆ ln  1   ˆ 
13 Essentially,the Gamma function is an extension of the Factorial to the reals and the Beta function is an
extension of the reciprocal of the Binomial function.

18
 ) 

1
ln 

1
ln  

1


 ˆ
ln
2 ˆ 2 ˆ


1  ˆ
ln
2  1   ˆ
 2  1   ˆ -
1



360   1

2 2 2 2 ˆ 1 2  1  ˆ  1 3

1

1
1 1
1
ln   1 ln    
(36)


 min  ˆ  1  ˆ   360   1

2 2 2 2 2 1 3

1


 ln   1 1 (37)
2

B Proof of Lemma 1.

where

Given that the bound on the regret of the min-max optimal algorithm is equal to ln ,

is the normalization factor of the min/max distribution for sequences of

length T, our goal is to calculate
* 
max &    
lim ln
 lim ln


 
  $ # &  

The probability assigned to a sequence $ by the model depends only on the

number of 1’s in  , i.e., on  ˆ. It is

&   

 ˆ  1    
 1   ˆ

ˆ
 1   1 
ˆ

  38
 ˆ
The value of &     for a given  is maximized when thus we get that

 *  ˆ 
 ˆ  1  ˆ 1   ˆ 
# 
 
As there are   ˆ
sequences of length  in which the fraction of 1s is ˆ, and as ˆ achieves
the values   for 0    , we can rewrite the last equation in the following form.

 *           39
 + 0
where    ln   1   ln  1   is the binary entropy of .
To approximate
 the value of Equation 39 we replace  
by the equivalent expression




Γ  1   Γ  1  Γ    1   move the log of this expression to the exponent, and
get:

 *
exp ln Γ  

1  ln Γ 


1 (40)
 + 0
 ln Γ   


1 ,

 

19
Replacing Γ   by its series expansion around  and   by its definition, we
get, in the exponent, the expression


1
 ln  
1   
1
12 ln 2
  1 
2
 
12  ln 
1

1  12 ln 2
  1 
   
12  ln   
1
  
1  1
ln 2

  1 
2 


ln


     ln   
1
1
ln 2

 
 1  
2  


 
 
1 2 ln 

1   1 2  ln 


1   


1 2  ln   


1



ln    ln       ln   
1
1
ln 2

  1 
2 


 ln 1
 1   ln  1

1

      ln  1
 1 

1
ln


1


2  1    1
In the first line of the last expression, the first two terms are constant and the third term

1

is  1  . All the terms in the second line are in the range 0  1 . The first term is equal to
 1  , and if  ˆ    1    for some fixed   0 then the second and third term
have the same asymptotic behavior. The dominant term, in any case, is the last one.
Returning to Equation (39), we separate the sum into three parts as follows

 *         *         
1*           
* 
 
  
  
 + 0    
+ 0
   
+ 
   
 +  1  
 
 
Using the approximations shown above we can upper bound the summands in the first
and third sums by

            2  12 ln 2   1   
1



 1    1
and estimate the summands in the second term by


     1  


1
      
1
ln 2

 1   1
2

A convenient way for writing the common factor is


1



1 1


 1    1  1

 2 
  1
      2
1
2

20
 Using these equalities we can write the second, and major summation as follows:
 1     1  
*       1  1 *  1 1


      

1

 1   1 
+  2 +   2
 
 2 2
 
Observe the last sum, it is easy to see that it a Riemann Sum which is a finite approxi-
mation to the integral
 1  

1 

  1  

And, as  
, and the function 1 $ 1   is Riemann integrable this sum


approaches the value of the integral, so we get:
 1     1 
*       1 


1 1 
     

 1 2 


+  $  1 

 
Similarly, we get that the sum that corresponds to the first and last terms approach
*          2  1 
1  


1 
         1


+ 0 2 0 
 1  


and
*  
     1  1


1 1 
     2
  

1


 +  1   

2
 1  $   
1

The last two integrals are

    , thus, after we take the limit   we can take the
limit  and get that
 *     
 1  
*  
    * 
   

   

   

   

lim

  1 lim lim



0
)

 + 0 +   +  1   
  

 1  


 1


2 1 1 
1 1 
2 1 1 
lim0 

2
 0 $  
1

2

  1  


2
 1   1   -

 1


1 1 

2
 0 $   
1


2
Finally taking the log we get that
 1
1
lim ln

   2
ln   1 ln 
2 2
which completes the proof of the theorem.

21
C Proof of Theorem 4
We need to calculate a lower bound on the following integral:
 1
 
exp  2 ˆ   1  ˆ 2
  1   2
0



2  1   ˆ (  0   ˆ 2   0   2   

This integral simplifies to

 1

exp   2   ˆ   2  
0

This is another well-known integral, it is (up to a multiplicative constant) an integral

of the normal distribution on part of the real line. This integral does not have a closed
algebraic form, but can be expressed using the error function erf ( ).
 1
exp  2   ˆ   2  (41)
0
  
 
 ˆ &  &
   1 ˆ  2
1    
2
 2
2

2 0 0
1 
ˆ
2

2
 erf  ˆ   erf  1     

where  &
2  
erf ( )  
2


0

is the cumulative distribution function of the normal distribution. As erf (
) is an


increasing function we find that erf  ˆ 2  erf   1  ˆ  2  is minimized when
 1, and as erf (
) is concave for


0 we find that the minimum is achieved for
ˆ 0 or ˆ 1. Thus we get that the integral is uniformly (w.r.t.  ˆ) lower bound by


 1 erf  2
ˆ
exp   2     2
 
2

2
 42
0

We now plug this lower bound into Equation (20) and get that the regret is uniformly
upper bounded by

 1 erf  2
 1
ln 

1 2
 1
 43
2
ln
 2

2 4
ln
2 erf  2
ln 
4 2

22
D An example for which the exponential weights algo-
rithm is better than any Bayes algorithm
Suppose the model class consists of just three biased coins: 1 0 2
1 2 3
1, and that a sequence is generated by flipping a random coin whose bias is 0  9.
Consider first the Bayes algorithm, whatever is the choice of the prior distribution,
once the algorithm observes both a zero and a one in the sequence, the posterior
 2 and
distribution becomes concentrated
 on 2 1 all predictions from there on would
necessarily be  
1 2. This would causes the algorithm an average loss per trial
of  0  5  0  1  2 0  16. On the other hand, consider the EW algorithm which uses
the uniform prior distribution over the three models. The total loss of this algorithm 
is guaranteed to be larger than that of the best model in the class by at most  2  4.


For large  , with very high probability, the best model is 2 1 whose average loss
per trial is  0  9  1  2 0  01. Thus the average loss per trial of the EW algorithm is
guaranteed to quickly approach 0  01, making it a clearly better choice than the Bayes
algorithm for this problem. We conjecture that a gap between the performance of there
algorithms exists when the class of models is the set of all the biased coins. However,
we have yet not been able to calculate optimal prior for the optimal Bayes algorithm
for this case.

23