Reinforcement Learning

The agent's goal is not to grab the biggest immediate reward but the biggest return, the discounted sum of all future rewards, where a discount factor $\gamma \in [0,1)$ makes sooner rewards worth more than later ones:

1. 1Observe stateThe agent reads the current situation s
2. 2Choose actionε-greedy: mostly pick the best-known action, occasionally explore
3. 3Get reward and next stateThe environment returns r and the new state s'
4. 4Update the estimateNudge the value of (state, action) toward the reward plus the discounted value of s'
5. 5RepeatLoop until the values stop changing

Value, and the Bellman equation

The key object is a value: how good is it to be in a state (or to take an action in a state), measured in expected future return. The action-value $Q(s, a)$ estimates the return from taking action $a$ in state $s$ and behaving well thereafter. Its defining self-consistency, the Bellman equation, says the value now equals the immediate reward plus the discounted value of where you land:

Everything in tabular RL is a way of making an estimate satisfy this equation.

Q-learning, three ways

One update, with numbers

Put concrete numbers on the rule. Say the agent is in state $s$, every $Q$ value starts at $0$, and it takes an action that reaches the goal for a reward $r = 10$ (a terminal step, so the bootstrap term drops). With learning rate $\alpha = 0.5$:

Now the square that leads to the goal has a non-zero value. On a later visit, an action from a neighbouring state $s^{-}$ that lands in $s$ sees a target $r + \gamma \max_{a'} Q(s, a') = 0 + 0.9(5) = 4.5$, so its own value rises to $0 + 0.5(4.5) = 2.25$. The reward has taken one step backward along the path. Run enough episodes and a smooth gradient of values grows outward from the goal, the "trail" the intuition described, built by this one line of arithmetic.

The exploration–exploitation tension

Exploit too early and the agent locks onto the first mediocre route it found. Explore forever and it never cashes in what it learned. Every RL method is, at heart, a way of managing this trade-off, and it is why the same algorithm with a different $\varepsilon$ can either find the goal reliably or get stuck. The gridworld lab lets you feel this directly by turning $\varepsilon$ up and down.

From tables to deep RL

RL is also the backbone of a technique you have already met: RLHF (reinforcement learning from human feedback) fine-tunes language models by treating human preference as the reward signal. The gridworld and a chat model tuned to be helpful are, formally, the same problem.

Further reading

• Reinforcement Learning: An Introduction, Sutton & Barto (free, 2nd ed.)
• Playing Atari with Deep Reinforcement Learning (DQN), Mnih et al. (2013)
• Spinning Up in Deep RL, OpenAI

The bracket is the temporal-difference error: the gap between what we now believe and what we believed before. On a terminal transition the bootstrap term $\gamma \max_{a'} Q(s',a')$ is dropped (there is no next state). Under mild conditions this update provably converges to the optimal $Q^{*}$.

The bracket is the temporal-difference error: the gap between what we now believe and what we believed before. On a terminal transition the bootstrap term $\gamma \max_{a'} Q(s',a')$ is dropped (there is no next state). Under mild conditions this update provably converges to the optimal $Q^{*}$.