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.
The previous two posts covered UCB and Thompson sampling, which only handle one-step decisions. CS234 Lecture 12 carries the same two ideas into MDPs, where states matter. First it swaps the yardstick: PAC bounds the number of steps where you act badly, not total regret. Then it covers the optimistic approach (MBIE-EB: counts plus an exploration bonus) and the sampling approach (PSRL: draw one MDP per episode and solve it). When states are too many to count, the bonus moves into the Q-learning target, which is what beat ε-greedy DQN on Montezuma's Revenge. The last section asks whether exploration itself can be learned; one answer is the Decision-Pretrained Transformer.
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.
The final seven lectures move from exploration and theoretical limits through two review lectures to advanced exploration, multitask RL, and unresolved research problems.