Bandit Algorithms

5.6 Exercises 84

Hint Use Jensen’s inequality to show thatexp(λE[Z])≤E[exp(λZ)] and then

provide a naive bound on the moment generating function ofZ.

5.19(Almost surely bounded sums) LetX 1 ,X 2 ,...,Xnbe a sequence of

nonnegative random variables adapted to filtration (Ft)nt=0such that

∑n

t=1Xt≤^1

almost surely. Prove that for allx >1,

P

(n

∑

t=1

E[Xt|Ft− 1 ]≥x

)

≤fn(x) =







(

n−x

n− 1

)n− 1

, ifx < n;

0 , ifx≥n,

where the equality serves as the definition offn(x).

Hint This problem does not use the techniques introduced in the chapter.

Prove that Bernoulli random variables are the worst case and use backwards

induction. Although this result is new to our knowledge, a weaker version was

derived by Kirschner and Krause [2018] for the analysis of information directed

sampling. The bound is tight in the sense that there exists a sequence of random

variables and filtration for which equality holds.