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.
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
- MDPs: discounted returns and the Bellman expectation equation 15 min
- Value iteration and the greedy policy 18 min
- Learning from experience: TD error, Q-learning and SARSA 18 min
- Thompson sampling: picking by sampling your beliefs 14 min
Take the lesson
Short cards, one idea at a time, with quick checks as you go.