Upper Confidence Bound (UCB) Action Selection
Problem statement
Implement the Upper Confidence Bound (UCB1) action selection rule for the multi-armed bandit problem. Write ucb_action(counts, values, t, c) that, given how many times each action has been selected, the average reward of each action, the current timestep $t$ and an exploration coefficient $c$, returns the index of the action with the highest score
$$UCB(a) = Q(a) + c \sqrt{\frac{\ln t}{N(a)}}$$
counts: numpy array, $N(a)$ for each action.values: numpy array, $Q(a)$ for each action.t: int, current timestep ($t \ge 1$).c: float, exploration coefficient ($c \ge 0$).
An action that has never been tried ($N(a) = 0$) should look maximally attractive (an effectively infinite bonus) when $t > 1$. Break ties by the lowest index. Return a Python int. Use only NumPy.
Example
Input:
counts = [1, 1, 1, 1], values = [1.0, 2.0, 1.5, 0.5], t = 4, c = 2.0
Output:
1
Reasoning: every action has been tried once, so all exploration bonuses are equal ($2\sqrt{\ln 4}$). Action 1 has the highest average reward (2.0), so it has the highest UCB score.
Show hint
How can you turn uncertainty about an arm's mean into a reason to try it, rather than just its current average?
Relevant roles: Research Scientist, Applied Scientist, ML Engineer and Data Scientist.
Related free problems
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium