Online learning and bandits
Drop the assumption that data are random. Against an adversary who picks the losses, you can still promise to do almost as well as the best expert in hindsight — derive the √(T log N) regret of multiplicative weights. Then hide the losses of the options you didn't choose, and meet the explore–exploit trade-off, UCB, Thompson sampling and the lower bound no algorithm can beat.
55 min
After this lesson you can
- Define regret and explain why a deterministic learner can be forced to have linear regret
- Derive the regret bound for exponential weights and tune to get
- State the online gradient descent regret bound
- Set up the stochastic multi-armed bandit, derive the regret decomposition, and explain why ε-greedy with fixed ε has linear regret
- Explain UCB1 and Thompson sampling, and state the Lai–Robbins lower bound with its conditions
In this lesson
- Learning with expert advice
- Multiplicative weights
- Bandits: paying to learn
- How well can anyone do? The lower bounds
- In code
- What was expected, and what is open
This lesson is part of Descent Pro
Descent Pro unlocks every lesson on the route, from base camp to the summit. Every plan starts with a free trial.