Bandits & Exploration
Regret, UCB, Thompson sampling, contextual bandits, and exploration under a budget.
7concepts
68flashcards
50minutes of reading
- 01 Best-Arm Identification When the goal is to find the best option with confidence rather than to earn reward while searching, the right objective is simple regret, the problem splits into fixed-confidence and fixed-budget versions, and elimination-style algorithms need samples in proportion to the sum of inverse squared gaps.
- 02 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.
- 03 Adversarial Bandits and EXP3 When rewards are chosen by an adversary rather than drawn from fixed distributions, deterministic optimism fails and the right tool is randomised exponential weighting over importance-weighted reward estimates, which guarantees regret of order the square root of T K log K against any reward sequence.
- 04 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.
- 05 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.
- 06 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.
- 07 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.