Skip to content
LearnMLByDoing
Free

7.2 Q-learning, SARSA and exploration

34 minProintermediateS&BHOMLCompendium

Without a model of the world an agent can still learn which moves pay off, by trying them and nudging a table of scores toward what each move earned, and the cliff walk shows how the way it explores changes what it learns.

01Learning without a model: try things, keep score

Lesson 7.1 solved its board because it knew the dice: P(s′∣s,a)P(s'\mid s,a) and the rewards were written down, and value iteration averaged over them. Most agents get no such rulebook. A robot does not know its motor noise and a recommender does not know how a user will react. What they can do is act, see what happens, and keep score. Reinforcement learning without a model is that loop, run carefully.

Start with the smallest version. Below are four doors, each paying a random number of points around a hidden average. You cannot read the averages, but you can keep a score for each door: after every try, move that door's score part of the way toward what it paid.

Loading figure
The update under the bars is Q(a)←Q(a)+α (r−Q(a))\tok{qvalue}{Q}(a) \leftarrow Q(a) + \tok{alpha}{\alpha}\,(\tok{reward}{r} - Q(a)): new score = old score + step size × surprise. With α=1/n\alpha = 1/n it is the exact average of the payouts so far; a fixed α\alpha weights recent payouts more. From a fresh start, set ε=0\tok{epsilon}{\varepsilon} = 0 and press agent: 50: the greedy agent opens door A, the first to pay anything, all 50 times for about 1 point per pull, and never learns what the other doors pay. Reset, set ε=0.1\varepsilon = 0.1 and press agent: 50 four times: random tries discover D and then B, and the score per pull climbs past 3.

Every method in this lesson is that update with a better target. A door's payout ends the story; a move on a board does not, because it also changes where you stand, so the target has to include what the next square is worth. That is where the Bellman equation of lesson 7.1 comes back.

The viewport is the cliff walk from Sutton and Barto: a 4 × 12 grid with the start S at the bottom left, the goal G at the bottom right, and a cliff along the ten cells between them. Every move pays r=−1\tok{reward}{r} = -1. Stepping into the cliff pays −100 and sends the agent back to S without ending the episode; reaching G ends it. There is no discount (γ=1\tok{gamma}{\gamma} = 1), so an episode's return is minus its number of moves, minus another 100 per fall. The best episode goes up, along the row next to the cliff and down: 13 moves, a return of −13.

Each cell carries four triangles, one per action, holding the agent's current estimate Q(s,a)\tok{qvalue}{Q}(\tok{state}{s},\tok{action}{a}): taller and greener is better, dark and flat means about −20 or worse, rose is far worse (the moves into the cliff), and dim grey has never been tried. The agent starts knowing nothing (Q=0Q = 0 everywhere) and plays 500 episodes at 10 per second. The grey trail is the current episode, amber dots mark random moves and a rose ring marks a fall. The emerald line is the greedy path, the route the agent would take if it stopped exploring. The chart behind the grid plots the return of every episode (dots) and the average of the last 20 (line); the faint line is the other algorithm of step 3 with the same seed.

Hold the table after the very first episode.

Jump to episode 100 and slow down to half an episode per second.

Reinforcement Learning: An Introduction, Sutton & Barto, Ch. 2.1 to 2.4, Multi-armed bandits and incremental averages

Reinforcement Learning: An Introduction, Sutton & Barto, Ch. 6.5, Example 6.6: Cliff Walking

02Temporal-difference learning and the TD error

Lesson 7.1 ended on the Bellman expectation equation: the value of a state is the average, over the policy and the dice, of one reward plus the discounted value of where you land.

Vπ(s)=Eπ[ rt+1+γ Vπ(st+1)  ∣  st=s ]V^{\tok{policy}{\pi}}(\tok{state}{s})=\mathbb{E}_{\pi}\big[\,\tok{reward}{r_{t+1}}+\tok{gamma}{\gamma}\,V^{\pi}(s_{t+1})\;\big|\;s_t=s\,\big]

A model-free agent cannot compute that average, but every move hands it one sample of the quantity inside: the reward it got and the state it landed in. Feed that sample to the running-score update of the doors and you get temporal-difference (TD) learning.

From a running average to TD(0)1/5
  1. 1
    xˉn=xˉn−1+1n(xn−xˉn−1)\bar x_n=\bar x_{n-1}+\tfrac{1}{n}\big(x_n-\bar x_{n-1}\big)

    The mean of x_1 … x_n written as an update: old estimate plus a step toward the newest sample. The doors use exactly this.

To choose moves the agent needs action values, because picking an action from VV requires the model again. The same update on QQ, with the target written yty_t:

Q(st,at)←Q(st,at)+α δt,δt=yt−Q(st,at)\tok{qvalue}{Q}(\tok{state}{s_t},\tok{action}{a_t})\leftarrow Q(s_t,a_t)+\tok{alpha}{\alpha}\,\tok{tderror}{\delta_t},\qquad \tok{tderror}{\delta_t}=\tok{target}{y_t}-Q(s_t,a_t)
What goes into the target y_t is the whole difference between the two algorithms of the next step.
Q (the table)[,]192 values

192 numbers, of which 148 belong to cells with moves (cliff and goal cells never act). Each move updates exactly one entry, the triangle that flickers in the viewport.

The very first update of the run, by hand. The agent is on S with Q=0Q = 0 everywhere and moves North to (2,0) (cells are written (row, column) from the top left), collecting r=−1r = -1. With γ=1\gamma = 1 and the best value at (2,0) still 0, the target is y=−1+1⋅0=−1y = -1 + 1 \cdot 0 = -1, the TD error is δ=−1−0=−1\delta = -1 - 0 = -1, and with α=0.5\alpha = 0.5 the entry becomes Q(S,N)=0+0.5⋅(−1)=−0.5Q(S,N) = 0 + 0.5 \cdot (-1) = -0.5. After 500 episodes the same entry reads Q(S,N)=−13Q(S,N) = -13 and the update has nothing left to do: the target is −1+max⁡aQ((2,0),a)=−1+(−12)=−13-1 + \max_a Q((2,0),a) = -1 + (-12) = -13, so δ=0\delta = 0.

Jump to episode 20 at half an episode per second, then hover δ\tok{tderror}{\delta}, y\tok{target}{y} and α\tok{alpha}{\alpha} in the equation above.

Reinforcement Learning: An Introduction, Sutton & Barto, Ch. 6.1 to 6.3, TD prediction and its advantages

03Q-learning (off-policy) and SARSA (on-policy)

Both algorithms run the update above while behaving ε-greedily: most moves take the best-looking action and a fraction ε\tok{epsilon}{\varepsilon} are random. They differ in one term, the value they assume for the next state.

Q-learning:yt=rt+1+γmax⁡a′Q(st+1,a′)\text{Q-learning:}\quad \tok{target}{y_t}=\tok{reward}{r_{t+1}}+\tok{gamma}{\gamma}\max_{a'}\tok{qvalue}{Q}(s_{t+1},a')
SARSA:yt=rt+1+γ Q(st+1,at+1),at+1∼πε(⋅∣st+1)\text{SARSA:}\quad \tok{target}{y_t}=\tok{reward}{r_{t+1}}+\tok{gamma}{\gamma}\,\tok{qvalue}{Q}(s_{t+1},a_{t+1}),\qquad a_{t+1}\sim\tok{policy}{\pi}_\varepsilon(\cdot\mid s_{t+1})
SARSA is named after the quintuple each update uses: (s, a, r, s′, a′). At the goal both targets are r alone, because a terminal state has no future.

Q-learning bootstraps from the best next action, whatever the agent will actually do there. Its target is the Bellman *optimality* equation of 7.1 with one sampled move in place of the average, so it learns Q∗Q^*, the values of the greedy policy, while behaving ε-greedily. Learning about one policy (the target policy, here greedy) from moves made by another (the behaviour policy, ε-greedy) is called off-policy learning. SARSA bootstraps from the action a′a' its ε-greedy policy really picks in s′s', so it learns QπεQ^{\pi_\varepsilon}, the values of the exploring policy it follows: on-policy learning.

Loading figure
A frozen table from the viewport's run (seed 1). Click a cell to choose ss, pick aa, and for SARSA the next action a′a'. The default sits on the edge route at (2,5): East lands on (2,6) with r=−1r = -1. Q-learning's target is −1+max⁡a′Q((2,6),a′)=−1+(−6.00)=−7.00-1 + \max_{a'} Q((2,6),a') = -1 + (-6.00) = -7.00, the current Q=−7.00Q = -7.00, so δ=0\delta = 0. If the next move is a random South into the cliff, SARSA's target is −1+Q((2,6),S)=−1+(−112.99)=−113.99-1 + Q((2,6),S) = -1 + (-112.99) = -113.99, so δ=−106.99\delta = -106.99 and QQ drops to −60.50-60.50. The presets show a fall, the terminal step into G and the very first update.

That one term decides the cliff walk. Along the edge, one move in forty is a random South (ε=0.1\varepsilon = 0.1 times a 1-in-4 chance of picking South), and it ends in the cliff. SARSA's targets carry those falls back into the cells beside the cliff, which end up worse than the cells further up, so SARSA learns to keep its distance. Q-learning's max ignores them: its values describe a future in which the agent never explores again, and in that future the edge is both safe and shortest.

Hold Q-learning's table at the end of the run.

Switch to SARSA and hold its table at the end of the run.

Reinforcement Learning: An Introduction, Sutton & Barto, Ch. 6.4 to 6.6, SARSA, Q-learning and Expected SARSA

The rest of this lesson is in Pro

  • 04Exploration: ε-greedy, decaying ε, optimism and the cliff
  • 05Convergence, the step size α and maximisation bias
  • 06Function approximation, DQN, and where RL is used
  • Python challenge: ε-greedy, Q-learning and SARSA on the cliff walk
  • Knowledge check, 4 questions

Pro opens all 45 lessons, every graded Python challenge and the full 3D labs.

Compiling scene

The Python challenge and knowledge check for this lesson are part of Pro.

Questions learners ask

What is the difference between Q-learning and SARSA?
Both learn action values Q(s, a) from experience with the same temporal-difference update. Q-learning uses the best next action in its target, so it learns the values of the greedy policy even while exploring; that makes it off-policy. SARSA uses the next action it actually takes, so it learns the values of the exploring policy it follows; that makes it on-policy. On the cliff walk Q-learning learns the shortest route along the edge but falls more while exploring, while SARSA learns a safer route and scores more during training.
What is epsilon-greedy exploration?
An epsilon-greedy agent takes the action with the highest estimated value most of the time and a uniformly random action with probability epsilon. With epsilon 0.1 and four actions it takes the best action 92.5 percent of the time. Exploration lets the agent discover actions whose value it has underestimated. A common schedule starts epsilon high and decays it toward a small value or zero, so the agent explores early and exploits once its estimates are good.
What are experience replay and target networks in DQN?
Deep Q-networks replace the Q-table with a neural network trained by regression on temporal-difference targets. Experience replay stores past transitions in a buffer and trains on random minibatches from it, which breaks the correlation between consecutive steps and reuses each experience many times. A target network is a frozen copy of the Q-network used to compute the targets and refreshed only every few thousand updates, so the targets do not move with every gradient step. Together they made Q-learning with deep networks stable enough to play Atari games from pixels.

Next in Reinforcement Learning

7.3Policy gradients, actor-critic and PPODifferentiate expected reward directly: REINFORCE, baselines and advantages, and the clipped objective that made PPO the default.

Sources

  • Reinforcement Learning: An Introduction, Sutton & Barto
  • Hands-On Machine Learning, Aurélien Géron
  • Maths, CS & AI Compendium, Henry Ndubuaku