Chapter 5: Reinforcement learning and post-training

Bandits: regret, epsilon-greedy and UCB

Ads, recommendations and tests all choose between options whose payoffs are unknown. If you always take the option that looks best, you can stop learning and lose for ever. Interviewers ask you to measure that loss and to compute the next pick under epsilon-greedy and UCB.

16 minInteractive lessonChapter 5: Reinforcement learning and post-trainingLesson 4 of 14

What you will learn

  • Explain regret and why pure greedy play can get stuck
  • Compute the next arm under epsilon-greedy and under UCB

Key terms

arm
one option, like one slot machine, that pays 1 or 0
pull
one try of an arm, which pays 1 or 0
pure greedy
always pull the arm with the best average so far
N
the number of times an arm was pulled
regret
what you lost against always pulling the best arm

Prerequisites

Take Learning from experience: TD error, Q-learning and SARSA first. It comes right before this lesson in the course.

Where this lesson picks up: In the Q-learning lesson, the agent nudged its estimate toward what one step showed. Now there is only one state, so how do you choose an action while you still learn what each action pays?

What comes next

UCB adds a bonus where it is unsure. Next, another way: keep a belief curve for each arm and pick by sampling it.

Next lesson: Thompson sampling: picking by sampling your beliefs

More lessons in this part

Take the lesson

Short cards, one idea at a time, with quick checks as you go.