What Did the Exploring Cost?

A website tested several versions of its sign-up page. Each visitor saw one version (an arm), and either signed up (reward 1) or not (reward 0). After the experiment the analysts learned the true sign-up rates rates[a] of the versions and want to know how much the experiment cost compared with showing the best version to everyone.

Write bandit_regret(rates, arms, rewards) that returns a tuple (pulls, expected, realised):

• pulls: a list with the number of times each arm was chosen (arms[t] is the arm shown to visitor t, rewards[t] what that visitor did);
• expected: the expected regret, the sum over the visitors of best - rates[arms[t]], where best is the largest rate;
• realised: the realised regret, best · T - (total reward), with T the number of visitors. It can be negative when the experiment was lucky.

Examples

Input:  rates = [0.3, 0.5, 0.4], arms = [0, 1, 2, 1, 1], rewards = [1, 0, 1, 1, 0]
Output: ([1, 3, 1], 0.30000000000000004, -0.5)
Explanation: arm 0 cost 0.5 - 0.3 = 0.2 once and arm 2 cost 0.1 once, so the expected regret is 0.3.
Always showing the best page would earn 2.5 sign-ups on average; the experiment got 3.

Input:  rates = [0.2, 0.9], arms = [1, 1, 1, 1], rewards = [1, 1, 0, 1]
Output: ([0, 4], 0.0, 0.6000000000000001)

Constraints

• 1 to 50 arms, 0 <= rates[a] <= 1
• 0 <= T <= 10**5, len(arms) == len(rewards), every reward is 0 or 1
• floats are compared with a tolerance of 1e-6

Goals

• Count how often each arm of a bandit was pulled
• Compute the expected regret of a sequence of choices from the true arm rates
• Compare it with the realised regret, which also contains luck