RL Foundations
A track of P9 · Reinforcement Learning.
Learning by acting: bandits, Markov decision processes and Q-learning on a gridworld small enough to trace by hand.
Three slot machines and a hundred pulls. The first machine you try pays out twice in three goes, which is the best rate you have seen, so you keep pulling it — and you will never find out that the third machine pays out four times in five, because you stopped looking. Acting on the best information you have is exactly what loses here, and no label anywhere tells you so.
Reinforcement learning has one irreducible idea, and this track builds it from nothing: an agent takes an action, the world returns a reward and a new situation, and over many such steps the agent learns to act well — with no teacher ever saying what the right action was. Every concept here is worked on examples small enough to trace with a pencil.
It opens with the explore-exploit dilemma in its purest setting: a multi-armed bandit, a row of machines with hidden payouts. Pure greed gets stuck — it locks onto the first arm that looks good and never discovers the better one — so you meet epsilon-greedy and measure the cost of being wrong as regret. Markov decision processes then add state and delayed reward: a gridworld where the payoff comes only at the goal, so acting greedily one step at a time fails. Value iteration solves such a world exactly through the Bellman backup — you will hand-compute a three-cell corridor to V = [0.9, 1.0, 0.0] — and Q-learning reaches the same policy knowing none of the rules, purely from experience.