$4$ Stochastic Bandit Algorithms $[2+6=8$ points$]$

Consider the stochastic bandit problem with $3$ arms, where the $($random$)$ reward associated with the $3$ arms for the first $8$

rounds are as follows. Note that these numbers are unknown to the bandit algorithm $($see Slide $9$ of Module $14$ for details

of the model and assumptions$)$:

time t $12345678$

arm $1$: $0\mathrm{.}30\mathrm{.}20\mathrm{.}50\mathrm{.}30\mathrm{.}20\mathrm{.}40\mathrm{.}60\mathrm{.}3$

arm $2$: $0\mathrm{.}20\mathrm{.}30\mathrm{.}50\mathrm{.}80\mathrm{.}50\mathrm{.}30\mathrm{.}70\mathrm{.}2$

arm $3$: $0\mathrm{.}10\mathrm{.}050\mathrm{.}020\mathrm{.}10\mathrm{.}030\mathrm{.}020\mathrm{.}010$

A bandit algorithm A has respectively selected arms $1,2,3,$ and $1$ in the first $4$ rounds $($for t in $\{1,2,3,4\}).$

$($a$)$ Suppose A applies the $-$greedy algorithm with $=0\mathrm{.}2$ at round t $=5.$ Compute the chance of each arm being

selected. Show your work.

$($b$)$ Suppose A intends to apply the UCB algorithm in the rounds that follow. We want to trace the algorithm for these

rounds. Below, it is described how the algorithm works at round t $=5.$

Follow the same steps for the rounds t in $\{6,7,8\}.$

At time $5$ scores are as follows:

Arm$1$: $0\mathrm{.}3($exploitation$)+1\mathrm{.}26864($exploration$)=1\mathrm{.}56864($total score$)$

Arm$2$: $0\mathrm{.}3($exploitation$)+1\mathrm{.}79412($exploration$)=2\mathrm{.}09412($total score$)$

Arm$3$: $0\mathrm{.}02($exploitation$)+1\mathrm{.}79412($exploration$)=1\mathrm{.}81412($total score$)$

The selected arm is $2$ with payoff $0\mathrm{.}5$