Optimism About the Untested Page

Epsilon-greedy explores at a fixed rate forever. A smarter learner explores where it is uncertain: it gives every arm an optimistic score, its observed rate plus a bonus that is large for arms tried only a few times, and pulls the arm with the highest score.

Write ucb1(rates, rounds, seed) that returns a tuple (total_reward, pulls, regret). Arm a gives reward 1 with probability rates[a]. Create rng = random.Random(seed) and for the rounds t = 1, 2, ..., rounds:

1. If some arm has never been pulled, pull the lowest such index.
2. Otherwise pull the arm with the highest score wins[a] / pulls[a] + sqrt(2 · ln(t) / pulls[a]), where t is the number of the current round (the lowest index on a tie).
3. The reward is 1 if rng.random() < rates[arm], else 0 (one random number per round).

regret is the expected regret: the sum over all pulls of max(rates) - rates[arm].

Examples

Input:  rates = [0.3, 0.5, 0.4], rounds = 8, seed = 2
Output: (3, [2, 2, 4], 0.7999999999999999)
Explanation: rounds 1 to 3 try each arm once; only arm 2 wins. In round 4 the scores are
0 + sqrt(2 ln 4 / 1) = 1.665 for arms 0 and 1 and 2.665 for arm 2, so arm 2 is pulled (and wins).
In round 6 arm 2's score has fallen to 1.760 (it has 3 pulls) and arm 0 gets a second chance.

Input:  rates = [0.3, 0.5, 0.4], rounds = 1000, seed = 0
Output: (460, [90, 686, 224], 40.39999999999999)

Constraints

• 1 to 50 arms, 0 <= rates[a] <= 1, 0 <= rounds <= 50000
• floats are compared with a tolerance of 1e-6

Goals

• Choose the arm with the highest optimistic estimate: observed rate plus an uncertainty bonus
• Simulate a seeded Bernoulli bandit and report the pulls and the expected regret
• See the bonus shrink for arms with many pulls, so exploration fades on its own