Q$3.$ The promises and pitfalls of randomization in sequence prediction $(25$

points$).$ We have learned in class that the weighted majority algorithm $($WMA$)$ and the

randomized weighted majority algorithm $($R$-$WMA$)$ share some key similarities: both of

them place weights on experts that become lower as experts make more inaccurate forecasts.

The key difference arises in how the algorithms aggregate the weights to make a prediction:

while WMA deterministically goes with the majority vote, RWMA randomizes its prediction

proportional to the weight on each expert. In this problem, you will implement both algo$-$

rithms in code and examine the implications of randomization on an "easy", i$.$e$.$ predictable

sequence and a "hard", i$.$e$.$ unpredictable$/$adversarial sequence.

$($a$)(10$ points$)$ Use the starter code provided in the Jupyter notebook $"$Q$3.$ipynb" to

implement the WMA and RWMA algorithms with the parameter choice $lon=\frac{1}{4}$ for

an arbitrary sequence $y_1,$dots,$y_T.$ Your code for each algorithm should consist of $3$

components: i$)$ the prediction rule $x_t($or prediction probability $p_t$ in the case of RWMA$)$

at round $t,$ ii$)$ the evaluation of loss or mistakes, iii$)$ the weight update from round $t$

to round $t+1.$

$($b$)(5$ points$)$ Use your starter code to return the sequence of cumulative mistakes up to

round $t,$ i$.$e$.M_t={\displaystyle \underset{s=1}{\overset{t}{}}}{m}_s$ as a function of $t($where $t$ ranges from $1$ to $T)$ for the

"easy" and "hard" sequences, which are pre$-$loaded into the Jupyter notebook. Plot

$M_t$ as a function of $t$ for each sequence comparing WMA and RWMA. You should

return two plots, one comparing WMA and RWMA for the easy sequence and the

other comparing WMA and RWMA for the hard sequence.

$($c$)(5$ points$)$ Which algorithm is better for the easy sequence and which algorithm is

better for the hard sequence?

$($d$)(5$ points$)$ Write code to calculate the eventual regret $R_T$ for WMA and RWMA for

the easy and hard sequence respectively. Which algorithm incurs a lower regret for

each case? Suppose Nature gave you the easy sequence with probability $\frac{1}{2}$ and the

hard sequence with probability $\frac{1}{2}.$ Should you use the randomized WMA or WMA?