Bandit Algorithms

5.6 Exercises 83

eachx∈[0,1] andt∈[n]. Prove for anyε >0 that

P

(n

∑

t=1

log(1/Xt)≥ε

)

≤

(ε

n

)n

exp(n−ε).

5.17(Concentration for categorical distributions) LetX 1 ,...,Xnbe
an independent and identically distributed sequence taking values in [m]. For
i∈[m] letp(i) =P(X 1 =i)andˆp(i) =^1 n

∑n
t=1I{Xt=i}. Show that for any
δ∈(0,1),

P

(

‖p−pˆ‖ 1 ≥

√

2 mlog(2/δ)

n

)

≤δ. (5.11)

This is quite a tricky exercise. The result is due to Weissman et al. [2003]. It

is worth comparing this to what can be obtained from Hoeffding’s inequality,

which implies for anyi∈[m] andδ∈(0,1) that with probability 1−δ,

|pˆ(i)−p(i)|<

√

2 log(2/δ)

n

.

By a union bound this ensures that with probability 1−δ,

∑

i

|pˆ(i)−p(i)|< m

√

2 log(2m/δ)

n

,

which is significantly weaker than the upper bound in(5.11). A standard

approach to deriving a stronger inequality is to use the fact that‖p−pˆ‖ 1 =

supx:‖x‖∞≤ 1 〈p−ˆp,x〉. Choose finite subsetS⊂B= [− 1 ,1]msuch that

for any point inx∈Bthere exists ay∈Ssuch that‖x−y‖∞≤ε/3.

Let x∗ = argmaxx∈B〈p−p,xˆ 〉 and s = argminu∈S‖s−x‖∞. Then

〈p−ˆp,x∗〉=〈p−p,sˆ 〉+〈p−p,sˆ −x∗〉≤〈p−p,sˆ 〉+ 2supp:‖p‖ 1 ≤ 1 〈p,s−x∗〉=

〈p−p,sˆ 〉+ 2‖s−x∗‖∞=〈p−p,sˆ 〉+ 2ε/3. By applying Hoeffding’s inequality

to〈p−p,sˆ 〉and a union bound we see that ifn≥ 2 log(|S|/δ)/ε^2 , then with

probability 1−δit holds that‖p−pˆ‖ 1 ≤ε. ChoosingSto have the fewest

elements gives a bound similar to that of Lemma 38.8. In particular,Scan

be chosen to be the regular grid with strideε/3, giving|S|= (6/ε)m. The

quantitysupx∈X〈p−ˆp,x〉is called anempirical process. Such empirical

processes are the subject of extensive study in the field of empirical process

theory, which has many applications within statistics, machine learning and

also beyond these field in almost all areas of mathematics [Vaart and Wellner,

1996, Dudley, 2014, van de Geer, 2000].

5.18 (Expectation of maximum) Let X 1 ,...,Xn be a sequence of σ-
subgaussian random variables (possibly dependent) andZ=maxt∈[n]Xi. Prove
thatE[Z]≤

√

2 σ^2 log(n).