UCB Action Choice

Problem

Pick an action with the UCB1 rule.

If any action has count 0, return the first such action. Otherwise return the argmax of Q[a] + c * sqrt(ln(t) / counts[a]), breaking ties toward the smallest index. t is the total number of pulls so far.

Hint

The exploration bonus shrinks as 1 / sqrt(count), so rare actions get sampled first.

Test cases

case 1

in: [[0.5,0.4],[5,2],10,1]

expected: 1

case 2

in: [[1,1,1],[0,3,3],6,2]

expected: 0

case 3

in: [[0.5,0.4],[5,2],10,0.1]

expected: 0

case 4

in: [[0.9,0.1],[100,1],10,1]

expected: 1

Starter codePython

import math
def ucb_action(Q, counts, t, c):
    # Your code here
    pass

4 test cases · run your code against them in the editor