Paul's Python CoursePPC

Multi-armed bandits

Not met yet

A multi-armed bandit is a row of choices, the arms, each paying off at its own rate that nobody tells you. You learn about an arm only by trying it. For each arm keep a count and an estimate, the average reward so far, updated with estimate += (reward - estimate) / count so no list of old rewards is needed. Always taking the best estimate so far is called greedy, and it can lock onto a poor arm for ever, because the arms it never tries never get a chance to look better.

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks an agent that always takes the best estimate so far will discover the best arm on its own, without exploring.
  • Thinks one bad result makes a greedy agent abandon an arm, even though its estimate is still above the untried arms'.
  • Thinks a running average needs a list of every past reward, rather than nudging the estimate by (reward - estimate) / count.
  • Thinks an arm's estimate is the most recent reward it gave, not the average of all of them.

Where it comes up