EE675 Assignment 1 Solved

Description

Part-A

(Chernoff Bound) [10 Marks] Suppose 𝑋1, 𝑋2, ⋯ , 𝑋𝑛 are i.i.d. copies of a (0, 𝜎2
) r.v. Then
for 𝑋 =
1
𝑛 ∑
𝑛

𝑖=1 𝑋𝑖 we know that
ℙ[𝑋 ≥ 𝜀] ≤ exp(
−𝑛𝜀2
2𝜎
2 )
.

Write a Python code to run Monte Carlo simulations that verify the inequality. Specifically,
for a given 𝜀 and 𝜎, generate 𝑛 samples from the zero mean Gaussian distribution 𝑥1, 𝑥2, … , 𝑥𝑛
and check whether the sample average is more than 𝜀. Repeat this experiment 500 times and
1

observe in how many experiments out of those 500 experiments, the sample average is more
than 𝜀. This will gives us an empirical estimate of 𝑃[𝑋 ≥ 𝜀].
Take 𝜎 = 0.1, 𝜀 = 0.05, and plot the empirical estimate as a function of 𝑛 ∈ {100, 200, … , 1000}.
In the same plot, include the Chernoff upper bound as a function of 𝑛.

Part-B

(Multi arm bandits | Explore-then-Commit and UCB) [20 Marks] Consider a two-armed
Bernoulli bandit scenario with true means given by 𝜇1 =
1
2
, 𝜇2 =
1
2

+ Δ, for some Δ <
1
2
. Let the

time horizon be 𝑇 = 10000.
1. Take Δ = 1
4
and run the Monte Carlo simulations to estimate the expected regret of the
ETC algorithm which explores each arm 𝑚 = 𝑇
2/3(log 𝑇 )

1/3 times before committing.
Specifically, you run the ETC algorithm to compute the sample regret
𝜇2 ⋅ 𝑇 −
𝑇
∑
𝑡=1
𝑅𝑡
,
where 𝑅𝑡
is the reward obtained in time step 𝑡.

Repeat this experiment 500 times and estimate the expected regret by taking the average
of the sample regrets you obtained in all those 500 experiments. [5 Marks]
2. Repeat the above for various values of Δ ∈ {0.05, 0.1, 0.2, 0.3, 0.4, 0.45} and plot the estimated regret as a function of Δ and verify whether it satisfies the regret upper bound

we derived in class. [5 Marks]
3. Repeat the experiment with the UCB algorithm and plot the comparison with ETC. [10
Marks]

4. (Bonus) In the ETC algorithm, assume that we know Δ, and choose a better 𝑚 as
function of Δ and repeat the experiments and compare with UCB. What did you observe?
Hint: Check how many samples of exploration are required to make 𝜀 < Δ
2 with a high

probability of 1 − 1
𝑇
. [5 Marks]
2