Lower Regret Bound Value

Problem

Compute the Lai-Robbins asymptotic lower bound on regret for a Bernoulli bandit.

For every suboptimal arm a, add (mu* - mu_a) / KL(mu_a || mu*) and multiply the total by ln(T). KL is the Bernoulli divergence mu_a * log(mu_a / mu*) + (1 - mu_a) * log((1 - mu_a) / (1 - mu*)). Means must be strictly between 0 and 1.

Hint

Regret grows logarithmically; KL divergence sets how hard the arms are to tell apart.

Test cases

case 1

in: [[0.2,0.5],100]

expected: 7.16777502612159

case 2

in: [[0.1,0.4,0.6],1000]

expected: 23.308857375680173

case 3

in: [[0.5],100]

expected: 0

case 4

in: [[0.25,0.5],10]

expected: 4.400560461481861

Starter codePython

import math
def lower_regret_bound(means, T):
    # Your code here
    pass

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