Problem 664040 · hard · Level 06 Heuristics & Optimization

A Strategy for Unknown Machines

multi-armed bandit · exploration and exploitation · UCB1 · epsilon-greedy · regret · online learning

An arcade has a row of k new machines. Machine a pays out 1 with a hidden probability (somewhere between 0.2 and 0.6) and 0 otherwise, and you may play rounds times in total. Earn as much as you can.

Write play(k, rounds, pull). Call pull(arm) with a machine number from 0 to k - 1; it returns the reward, 1 or 0. You may call it at most rounds times (a call beyond that raises TooManyPulls); pulls you do not use earn nothing. The return value of play is ignored.

The tests call judge_bandit(play, k, rounds, seed). It runs your strategy 5 times, each time on a fresh row of machines with new hidden probabilities, and adds up the rewards. judge_bandit is available in your code, so you can try strategies on seeds of your own.

How this problem is scored

Two reference points are computed from the true probabilities: random arms (the average total of choosing a machine at random in every round) and the best arm (the average total of always playing the best machine, which nobody can do without knowing the probabilities). Your quality is the share of the gap between them that you close, in percent: 0 at random arms, 100 at the best arm. A strategy passes a test when it closes at least a fifth of the gap (quality 20). The rewards are random, so a strategy's quality varies a little from test to test. Match the reference solution's quality (the par in the header) for the third star.

Examples

Input:  judge_bandit(play, 5, 500, 1)
Output: a summary such as {"reward": 1123, "random_policy": 964.410588, "best_arm": 1336.100041, "runs": 5}
        quality 100 · (1123 - 964.4) / (1336.1 - 964.4) = 42.7: a pass
        (always playing machine 0 earns 728 on these rows: quality -63.6, a fail)

Constraints

  • 5 <= k <= 50, 500 <= rounds <= 3000
  • each test must finish in well under a second in your browser
  • if your strategy uses randomness, use a random.Random with a fixed seed

Goals

  • Design a bandit strategy that learns while it earns, with a fixed budget of pulls
  • Tune how much to explore when the budget is short compared with the number of arms
  • Measure a strategy over several seeded runs against random choices and the best arm
Starting Python…