Upper Confidence Bound (UCB) Action Selection

EasyML Coding

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