Skip to content
All tags

#multi-armed-bandit

2 posts
aiguideReading Stanford CS234

CS234 Data Efficiency I: Multi-Armed Bandits, Regret, and UCB

CS234 L9 and the first half of L10 turn exploration from a rule of thumb like ε-greedy into something you can prove. First, regret: how much you lose compared with always pulling the best arm. Greedy locks onto a suboptimal arm, and ε-greedy with fixed ε spends an ε fraction of its time choosing at random, so both have regret that grows linearly with time. The Lai-Robbins lower bound says the best possible is logarithmic growth, and UCB gets there by being optimistic about uncertain arms: Theorem 7.1 of Bandit Algorithms shows each suboptimal arm is pulled only about 16 log n / Δ² times.

#cs234#ai-course#stanford#reinforcement-learning#exploration#multi-armed-bandit
aiguideReading Stanford CS234

CS234 Data Efficiency II: Bayesian Bandits, Thompson Sampling, and the Gittins Index

CS234 L11 switches the logic of exploration from optimism to sampling. Thompson sampling keeps a posterior for each arm, draws one value from each posterior at every step, and pulls the arm with the largest draw. With Bernoulli rewards and a Beta prior, the update just adds one to the success or failure count. It implements probability matching: each arm is chosen with the posterior probability that it is the best arm. Under Bayesian regret it matches UCB's order, and with batched, delayed feedback it suits the problem better than deterministic UCB. The cost: a badly wrong prior can make it perform poorly.

#cs234#ai-course#stanford#reinforcement-learning#exploration#multi-armed-bandit#bayesian-statistics