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.
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.