Q-Learning and SARSA | AI Pathshala

Definition

Q-learning is a model-free reinforcement learning algorithm that learns Q(s, a), the value of taking action a in state s. It updates its estimate using the reward received plus the best value available from the next state. It's off-policy: it learns the best policy even while acting differently, for example while exploring.

In simple words

It's a cheat sheet with a row for each situation and a column for each move. At first it's all zeros. Each time you try something, you adjust that cell using what you got and the best you could do next. Eventually the sheet tells you the best move everywhere.

Why it matters

It needs no model of the environment, only trial and error. It's the classic starting point of RL, and deep Q-networks, which learned to play Atari from raw pixels, replaced its table with a neural network.

How it works

Fill a Q table with zeros.
In the current state, choose an action. Usually take the best one, and sometimes a random one (ε-greedy).
Do it, and observe the reward and next state.
Update that one cell using the rule below.
Repeat for many episodes.

	Q-learning	SARSA
Next value uses	The best next action	The next action actually taken
Type	Off-policy	On-policy
Behaviour	More optimistic	More cautious while exploring

The maths

Q-learning update

Q (s, a) \leftarrow Q (s, a) + α [r + γ a^{'} max Q (s^{'}, a^{'}) - Q (s, a)]

$α$: The learning rate
$r$: The reward received
$γ$: The discount factor
$max_{a^{'}} Q (s^{'}, a^{'})$: The best value available from the next state
$r + γ max Q - Q (s, a)$: The TD error: how surprised we were

Q(s, a) = 2, r = 1, the best next Q value is 4, α = 0.5 and γ = 0.9.

Target   = 1 + 0.9 × 4 = 4.6
TD error = 4.6 − 2 = 2.6
New Q    = 2 + 0.5 × 2.6 = 3.3

In code

An agent learns to walk along a line of 5 cells to reach the goal on the far right.

q_learning.py

import random

random.seed(0)
n_states = 5                # cells 0 to 4, and the goal is cell 4
actions = [-1, +1]          # left, right
Q = [[0.0, 0.0] for _ in range(n_states)]
alpha, gamma, epsilon = 0.5, 0.9, 0.2

for episode in range(200):
    state = 0
    while state != 4:
        if random.random() < epsilon:
            a = random.randrange(2)
        else:
            a = Q[state].index(max(Q[state]))
        next_state = max(0, min(4, state + actions[a]))
        reward = 10 if next_state == 4 else 0
        best_next = max(Q[next_state])
        Q[state][a] += alpha * (reward + gamma * best_next - Q[state][a])
        state = next_state

for s in range(4):
    best = "right" if Q[s][1] > Q[s][0] else "left"
    print(f"cell {s}: left {Q[s][0]:5.2f}, right {Q[s][1]:5.2f}, best: {best}")

Output

cell 0: left  6.56, right  7.29, best: right
cell 1: left  6.56, right  8.10, best: right
cell 2: left  7.29, right  9.00, best: right
cell 3: left  8.10, right 10.00, best: right

Common mistakes

Never exploring. With no random moves, the agent can stay stuck on its first decent idea.
Using a table with too many states. Chess has far too many, so use function approximation such as DQN.

Check yourself

1. Q-learning is off-policy because:

2. Q = 1, r = 2, best next Q = 3, α = 1 and γ = 1. What's the new Q?

3. What does DQN replace?

Summary

It learns a table of action values by trial and error.
Update: move towards reward + γ × best next value.
It's off-policy, needs exploration, and DQN scales it with a network.

Read it. Now try it yourself.

Open the interactive activity

Finished reading?

Sources: Sutton & Barto, Reinforcement Learning: An Introduction