I am trying to understand the UCB algorithm and I'm trying to understand it using an exercise. Here's the Upper Confidence Bound algorithm explanation: enter image description here

Now I have the following exercise: Suppose we have two actions, $a$ and $b$. Consider the initial exploration bonus for each to be infinite, as long as we have not selected the corresponding action, so that the algorithm first selects each action at least once.

Suppose action $a$ yields a Bernoulli random reward with $P(R=1|a) = 1/3$ and $P(R=0|a)=2/3$. Action also yields a Bernoulli random reward, but with $P(R=1|b)=2/3$ and $P(R=0|b)=1/3$.

What is the probability (before seeing any data) of selecting action $a$ on the third time step (at which point we will have selected both $a$ and $b$ exactly one)? (Break ties uniformly, if relevant).

Now, I think I understand how the algorithm works, so please let me know if my understanding is correct.

So, the probability of selecting action $a$ is the event where we select it with probability $1$, given the reward for action $a$ was bigger than that of $b$ before time step $3$. Or we select it randomly, given that before time step $3$, the rewards of $a$ and $b$ were equal.

Mathematically: Define $R_a$ and $R_b$ to be the rewards that $a$ and $b$ yielded respectively before time step $3$. So, $$P(\text{selecting action a on time ste 3}) = \underbrace{P(\text{selecting a}| R_a > R_b)}_{=1}P(R_a>R_b) + \underbrace{P(\text{selecting a}|R_a=R_b)}_{=1/2}P(R_a=R_b)$$

Now, we have that $P(R_a>R_b) = P(R_a=1)P(R_b=0) = \frac{1}{3}\frac{1}{3} = \frac{1}{9}$

and $P(R_a= R_b) = P(R_a = 1) P(R_b = 1) + P(R_a = 0)P(R_b = 0) = \frac{1}{3}\frac{2}{3} + \frac{2}{3}\frac{1}{3} = \frac{4}{9}$

Hence, $$P(\text{selecting action a on time ste 3}) = \frac{1}{9}+\frac{2}{9} = \frac{3}{9} = \frac{1}{3}$$

Is my understanding correct?



You must log in to answer this question.