Bandit Algorithms

5.3 The Cramer-Chernoff method and subgaussian random variables 75

A similar inequality holds for the left tail. By using the union bound
P(A∪B)≤P(A)+P(B)we also find thatP(|X|≥ε)≤ 2 exp(−ε^2 /(2σ^2 )).
An equivalent form of these bounds is:

P

(

X≥

√

2 σ^2 log(1/δ)

)

≤δ P

(

|X|≥

√

2 σ^2 log(2/δ)

)

≤δ.

This form is often more convenient and especially the latter, which for smallδ
shows that with overwhelming probabilityXtakes values in the interval
(
−

√

2 σ^2 log(2/δ),

√

2 σ^2 log(2/δ)

)

.

To study the tail behavior of ˆμ−μ, we need one more lemma.

Lemma5.4. Suppose thatXisσ-subgaussian andX 1 andX 2 are independent
andσ 1 andσ 2 -subgaussian respectively, then:

(a)E[X] = 0andV[X]≤σ^2.
(b)cXis|c|σ-subgaussian for al lc∈R.
(c)X 1 +X 2 is

√

σ 12 +σ^22 -subgaussian.

The proof of the lemma is left to the reader (Exercise 5.7). Combining

Lemma 5.4 and Theorem 5.3 leads to a straightforward bound on the tails

of ˆμ−μ.

Corollary5.5.Assume thatXi−μare independent,σ-subgaussian random
variables. Then for anyε≥ 0

P(ˆμ≥μ+ε)≤exp

(

−nε

2

2 σ^2

)

and P(ˆμ≤μ−ε)≤exp

(

−nε

2

2 σ^2

)

,

whereμˆ=^1 n

∑n

t=1Xt.

Proof By Lemma 5.4 it holds thatμˆ−μ=

∑n

i=1(Xi−μ)/nisσ/

√

n-subgaussian.
Then apply Theorem 5.3.

Forx > 0 it holds thatexp(−x)≤ 1 /(ex), which shows that the above
inequality is stronger than what we obtained via Chebyshev’s inequality except
whenεis very small. It is exponentially smaller ifnε^2 is large relative toσ^2. The
deviation form of the above result says that under the conditions of the result,
for anyδ∈[0,1], with probability at least 1−δ,

μ≤μˆ+

√

2 σ^2 log(1/δ)

n

. (5.6)

Symmetrically, it also follows that with probability at least 1−δ,

μ≥μˆ−

√

2 σ^2 log(1/δ)

n. (5.7)

Again, one can use a union bound to derive a two-sided inequality.

Example5.6.The following random variables are subgaussian: