Part 5 of 12 · 2 min read
Never trying anything new has a cost that compounds with time
Sticking with the first strategy that worked looks safe at first and gets steadily more expensive the longer the choice keeps getting made.
Think of always ordering the same dish at a restaurant with a changing menu. It feels safe. But suppose a new dish turns out to be better, or your old favourite quietly gets worse. You keep paying the difference every single visit without ever finding out.
In plain words: exploitation is using the strategy that looks best so far, exploration is trying other strategies to learn whether they're better, a multi-armed bandit is the problem of choosing among options with unknown success rates one trial at a time, and regret is the successes lost compared with always using the best option -- a policy that never explores accumulates regret that grows linearly with every trial it runs.
A worked example. A policy that always picks the first strategy accumulates regret of 32 after 100 trials and 160 after 500 -- it grows roughly in proportion to the number of trials, because the gap to the best strategy never closes. Adaptive policies such as Thompson sampling or epsilon-greedy learn which option is actually best and hold regret to 8 at 100 trials and 24 to 27 at 500 -- a quarter of the fixed policy's loss, because they stop paying the gap once they've learned.
The key lines. From code/mini-explore/bandit.py:
# from code/mini-explore/bandit.py
elif policy == "epsilon_greedy":
k = r.randrange(K) if (r.random() < 0.1 or t < K) else max(range(K), key=lambda i: wins[i] / max(1, pulls[i]))
Read it as: ten percent of the time (r.random() < 0.1), the policy picks a strategy at random. It does the same during the first K trials, while every option has not been tried once. That is the exploration. The rest of the time it picks whichever strategy has the best win rate so far. That one else branch is pure exploitation. The 10% random branch is the entire mechanism that keeps regret from growing linearly forever.
Exploitation, exploration, bandit, regret
Exploitation is using the strategy that looks best so far. Exploration is trying other strategies to learn whether they are better. A multi-armed bandit is the problem of choosing among options with unknown success rates, one trial at a time. Regret is the successes lost compared with always using the best option.
Example: regret of 320 for a policy that never explores against 83 to 114 for adaptive policies, over 1,000 trials where the best strategy changes halfway through, is the gap between a policy that can't notice the change and ones that can.