  We investigate the problem of bandits with expert advice when the experts are
fixed and known distributions over the actions. Improving on previous analyses,
we show that the regret in this setting is controlled by information-theoretic
quantities that measure the similarity between experts. In some natural special
cases, this allows us to obtain the first regret bound for EXP4 that can get
arbitrarily close to zero if the experts are similar enough. While for a
different algorithm, we provide another bound that describes the similarity
between the experts in terms of the KL-divergence, and we show that this bound
can be smaller than the one of EXP4 in some cases. Additionally, we provide
lower bounds for certain classes of experts showing that the algorithms we
analyzed are nearly optimal in some cases.
