Problem 670255 · medium · Level 06 Heuristics & Optimization

Mostly Greedy, Sometimes Curious

multi-armed bandit · epsilon-greedy · exploration and exploitation · simulation · seeded randomness

Simulate the sign-up page experiment with an epsilon-greedy learner. Arm a gives reward 1 with the hidden probability rates[a] and 0 otherwise. The learner keeps, for every arm, the number of pulls and the number of wins (rewards of 1).

Write epsilon_greedy(rates, rounds, epsilon, seed) that returns a tuple (total_reward, pulls). Create rng = random.Random(seed) and, in every round:

  1. Draw u = rng.random(). If u < epsilon, explore: the arm is rng.randrange(len(rates)).
  2. Otherwise exploit: if some arm has never been pulled, take the lowest such index; else take the arm with the highest observed rate wins / pulls (the lowest index on a tie).
  3. Pull it: the reward is 1 if rng.random() < rates[arm], else 0. Update that arm's counts.

(In rounds that exploit, rng is used once for u and once for the reward; in rounds that explore, a randrange comes between them.)

Examples

Input:  rates = [0.3, 0.5, 0.4], rounds = 10, epsilon = 0.2, seed = 1
Output: (5, [6, 3, 1])
Explanation: round 1 explores (u = 0.134) and draws arm 0, which wins; rounds 2 and 3 try the
untried arms 1 and 2 (arm 1 wins, arm 2 loses); round 4 explores arm 0 again (a loss); from
then on the learner exploits and ends up favouring arm 0, which wins its last three pulls.

Input:  rates = [0.3, 0.5, 0.4], rounds = 2000, epsilon = 0.1, seed = 0
Output: (992, [65, 1830, 105])

Input:  rates = [0.3, 0.5, 0.4], rounds = 2000, epsilon = 0.0, seed = 0
Output: (987, [1, 1998, 1])

Constraints

  • 1 to 50 arms, 0 <= rates[a] <= 1, 0 <= epsilon <= 1, 0 <= rounds <= 50000

Goals

  • Simulate a Bernoulli bandit with a precisely specified use of randomness
  • Choose arms epsilon-greedily: explore at random with probability epsilon, otherwise exploit
  • Compare runs with and without exploration on the same seeded environment
Starting Python…