Bandit Algorithms

14.3 Notes 182

This indeed is sufficient since

∫

p∧q=

∫

Ap∧q+

∫

Acp∧q≤

∫

Ap+

∫

Acq=

P(A) +Q(Ac). We start with an inequality attributed to French mathematician

Lucien Le Cam, which lower bounds the left-hand side of Eq. (14.7). The inequality

states that

∫

p∧q≥

1

2

(∫

√

pq

) 2

. (14.8)

Starting from the right-hand side above usingpq= (p∧q)(p∨q) and Cauchy-

Schwarz we get

(∫

√

pq

) 2

=

(∫ √

(p∧q)(p∨q)

) 2

≤

(∫

p∧q

) (∫

p∨q

)

Now, using∫ p∧q+p∨q = p+q, the proof is finished by substituting

p∨q= 2−

∫

p∧q≤2 and dividing both sides by two. It remains to lower
bound the right-hand side of(14.8). For this, we use Jensen’s inequality. First,
we write (·)^2 as exp(2 log(·)) and then move the log inside the integral:
(∫
√
pq

) 2

= exp

(

2 log

∫ √

pq

)

= exp

(

2 log

∫

p

√q

p

)

≥exp

(

2

∫

p^1

2

log

(

q

p

))

= exp

(

−

∫

pq> 0

plog

(

p

q

))

= exp

(

−

∫

plog

(

p

q

))

= exp (−D(P,Q)).

In the fourth and the last step we used that sincePQ,q= 0 impliesp= 0

and sop >0, which impliesq >0, and eventuallypq >0. The result is completed

by chaining the inequalities.

14.3 Notes

1 A codec:N+→ { 0 , 1 }∗is uniquely decodable ifi 1 ,...,in7→c(i 1 )···c(in)

is injective, where on the right-hand side the codes are simply concatenated.

Kraft’s inequalitystates that for any uniquely decodable codec,

∑∞

i=1

2 −`(c(i))≤ 1. (14.9)

Furthermore, for any (`n)∞n=1satisfying

∑∞

i=1^2

−`≤1 there exists a prefix code

c:N+→{ 0 , 1 }∗such that`(c(i)) =`i. The second part justifies our restriction

to prefix codes rather than uniquely decodable codes in the definition of the

entropy.

2 The supremum in the definition given in Eq. (14.5) may often be taken over

a smaller set. Precisely, let (X,G) be a measurable space and suppose that

G=σ(F) whereFis a field. Note that a field is defined by the same axioms