Bandit Algorithms

20.4 Exercises 247

The definitions can be repeated for pseudo-metric spaces. LetXbe a set and

d:X×X→[0,∞) be a function that is symmetric, satisfies the triangle

inequality and for whichd(x,x) = 0 for allx∈X. Note thatd(x,y) = 0 is

allowed for distinctxandy, sodneed not be a metric. The basic results

concerning covering and packing stated in the next exercise remain valid

with this more general definition. In applications we often need the logarithm

of the covering and packing numbers, which are called themetric entropy

ofXat scaleε. As we shall see these are often close no matter whether we

consider packing or covering.

20.3(Coverings and Packings) LetA ⊂ Rd,B the unit ball ofRd,

vol(·) the usual volume (measure under the Lebesgue measure). For brevity

letN(ε) =N(A,ε) andM(ε) =M(A,ε). Show that the following hold:

(a)ε→N(ε) is increasing asε≥0 is decreasing.
(b)M(2ε)≤N(ε)≤M(ε).
(c) We have
(
1
ε

)d

vol(A)

vol(B)

≤N(ε)≤M(ε)≤

vol(A+ε 2 B)

vol(ε 2 B)

(∗)

≤

vol(^32 A)

vol(ε 2 B)

≤

(

3

ε

)d

vol(A)

vol(B)

,

where (∗) holds under the assumption thatεB⊂ Aand thatAis convex
and forU,V ⊂Rd,c ∈ R,U+V = {u+v : u∈ U ,v ∈V}and
cU={cu:u∈U};
(d)Fixε >0. ThenN(ε)<+∞if and only ifAis bounded. The same holds for
M(ε).

20.4 Use the results of the previous exercise to prove Lemma 20.1.

20.5 Complete the steps to show Eq. (20.6).

20.6 Prove Lemma 20.3.

20.7(Hoeffding–Azuma) LetX 1 ,...,Xnbe a sequence of random variables

adapted to a filtrationF= (Ft)t. Suppose that|Xt|∈[at,bt] almost surely for

arbitrary fixed sequences (at) and (bt) withat≤btfor allt∈[n]. Show that for

anyε >0,

P

(n

∑

t=1

(Xt−E[Xt|Ft− 1 ])≥ε

)

≤exp

(

−

∑^2 n^2 ε^2

n

t=1(bt−at)^2

)

.

Hint It may help to recall Hoeffding’s lemma from Note 4 in Chapter 5, which

states that for a random variableX∈[a,b] the moment generating function

satisfies

MX(λ)≤exp(λ^2 (b−a)^2 /8).