Bandits & Exploration
Regret, UCB, Thompson sampling, contextual bandits, and exploration under a budget.
5concepts
54flashcards
35minutes of reading
- 01 Regret and the Exploration-Exploitation Tradeoff What regret measures, why the logarithmic lower bound says exploration can never stop entirely, and how the bandit setting differs from both supervised learning and full reinforcement learning.
- 02 Contextual Bandits Why conditioning on features turns an intractable problem with many arms into a learning problem, how LinUCB and its relatives work, and the modelling choice that determines everything.
- 03 Deploying Bandits in Production The gap between the bandit formalism and a real system, the four assumptions that fail first, and what a deployment needs that the algorithm does not describe.
- 04 Thompson Sampling Why sampling from a posterior and acting greedily on the sample is a near-optimal exploration strategy, the property that makes it fit production systems, and where its Bayesian assumptions bite.
- 05 UCB and Optimism Under Uncertainty The optimism principle, why an upper confidence bound automatically balances exploration against exploitation, and how the bound's construction determines the algorithm's behaviour.