All topics
Multi-Armed Bandits
Online decisions under uncertainty: exploration versus exploitation, epsilon-greedy, UCB, and when a bandit beats a fixed A/B split.
Sort:
6 questions
JuniorTheoryCommonWhy can a purely greedy multi-armed bandit lock onto the wrong arm, and how does ε-greedy fix it?
JuniorTheoryCommon
Why can a purely greedy multi-armed bandit lock onto the wrong arm, and how does ε-greedy fix it?
Greedy always pulls the arm with the best average so far, so one lucky early streak can take every pull while other arms are never re-measured. ε-greedy spends an ε share of pulls on random arms, keeping estimates honest.
Common mistakes
- ✗Assuming greedy converges with enough pulls: an arm it stops pulling gets no new data, so an unlucky early estimate for the best arm is never corrected.
- ✗Treating ε as a learning rate: in ε-greedy it is the probability of pulling a random arm instead of the current best one.
Follow-up questions
- →Why might you decay ε over time instead of keeping it fixed?
- →What does a fixed ε cost you once the best arm is already known?
JuniorTheoryCommonWhat does this program print?
JuniorTheoryCommon
What does this program print?
0.8
Open full question →Common mistakes
- ✗Expecting
3.2, the summed probabilities of the arms pulled: regret sums the gaps to the best arm,0.8minus each pulled arm's probability, so the three pulls of arm 2 add nothing. - ✗Expecting
0.16, the average gap: regret adds the losses over all steps,0.5 + 0.3 = 0.8, and it keeps growing while a weaker arm is still being pulled.
Follow-up questions
- →How does regret grow over time for a fixed 50/50 split, and for a strategy that stops pulling weak arms?
- →Why can regret be computed in a simulation but not in a live test?
JuniorTheoryCommonWhat does this program print?
JuniorTheoryCommon
What does this program print?
0.67 3
Open full question →Common mistakes
- ✗Expecting
0.5 3, two rewards over all four steps: each arm keeps its own count, and arm 0 was pulled 3 times, so its mean is2 / 3, rounded to0.67. - ✗Expecting
2.0 3, the sum of rewards: the update moves the mean by1 / countof the gap to the new reward, someans[0]stays the average, not the total.
Follow-up questions
- →Why does a bandit keep a running mean per arm instead of storing every reward?
- →What goes wrong if
counts[arm]is increased after the mean update instead of before it?
JuniorTheoryCommonWhat does this program print?
JuniorTheoryCommon
What does this program print?
1 0
Open full question →Common mistakes
- ✗Expecting
0 0, as if the bonus could not beat a higher mean: arm 1 has only 2 pulls, so its bonus is about1.76against0.56for arm 0, and its score wins. - ✗Expecting the bonus to penalize the rarely pulled arm: it is added to the mean and is largest where the count is smallest, which is what sends UCB to explore arm 1.
Follow-up questions
- →After many more pulls of both arms, which arm will UCB prefer, and why?
- →How does UCB decide when an arm has never been pulled?
JuniorTheoryCommonHow does the bandit strategy UCB (upper confidence bound) choose which arm to pull next?
JuniorTheoryCommon
How does the bandit strategy UCB (upper confidence bound) choose which arm to pull next?
UCB scores each arm as its mean reward plus a bonus that shrinks as the arm is pulled more, and pulls the top score. A rarely tried arm keeps a big bonus, so it gets tried: optimism under uncertainty, no random draws.
Common mistakes
- ✗Thinking UCB picks the highest observed mean: it adds a bonus that is large for rarely pulled arms, and that bonus is what makes it explore.
- ✗Thinking UCB explores at random like ε-greedy: its choice is deterministic, driven by the shrinking bonus rather than a coin flip.
Follow-up questions
- →Why does the UCB bonus grow slowly with the total number of pulls?
- →How would UCB behave on an arm that was pulled only once?
JuniorTheoryCommonWhat do you gain and what do you lose by running a bandit instead of a fixed-split A/B test?
JuniorTheoryCommon
What do you gain and what do you lose by running a bandit instead of a fixed-split A/B test?
A bandit shifts traffic to the leading variant mid-test, so fewer users see the worse one: less regret. The price is a less clean effect estimate, since the losing arm gets little data. A fixed split gives an unbiased one.
Common mistakes
- ✗Treating a bandit as a faster A/B test with the same guarantees: adaptive allocation starves the losing arm and biases its estimate, so its p-value is not a fixed split's.
- ✗Choosing a bandit when the effect size itself is the deliverable: to report a trustworthy lift, a fixed split is the right tool.
Follow-up questions
- →Which product situations favour a bandit over an A/B test?
- →Why does an adaptive split make the losing arm's estimate biased?
