Value Functions & Q-Learning

The action-value function (the "Q function") is similar, but it commits to a specific first action $a$ before letting $\pi$ take over:

$Q^{\pi}(s, a) = \mathbb{E}_{\pi}\left[\, G_t \mid s_t = s,\; a_t = a \,\right].$

Why prefer $Q$? Because it tells you directly what to do. If you know $Q^{\pi}$, you can improve the policy simply by picking the highest-valued action in each state, no model of the environment required. This is the whole reason action values dominate practical value-based RL.

The Bellman equation: value is recursive

The key structural fact of RL is that value functions obey a self-consistency condition. The value of a state equals the immediate reward plus the discounted value of wherever you land next. Writing this out for action values under a policy gives the Bellman expectation equation:

$Q^{\pi}(s,a) = \mathbb{E}\left[\, r_{t+1} + \gamma\, Q^{\pi}(s_{t+1}, a_{t+1}) \;\middle|\; s_t = s,\, a_t = a \,\right].$

We do not usually want the value of some policy, though, we want the value of the best policy. That gives the Bellman optimality equation, where instead of averaging over the policy's next action we take the best one:

$Q^{\star}(s,a) = \mathbb{E}\left[\, r_{t+1} + \gamma \max_{a'} Q^{\star}(s_{t+1}, a') \;\middle|\; s_t = s,\, a_t = a \,\right].$

That $\max$ is the heart of the matter. It says: the best value of doing $a$ now is the reward you get, plus the discounted value of acting optimally from the next state onward. Once you have $Q^{\star}$, the optimal policy is greedy with respect to it:

$\pi^{\star}(s) = \arg\max_{a} Q^{\star}(s,a).$

Q-learning: bootstrapping toward $Q^{\star}$

Q-learning learns $Q^{\star}$ from experience without knowing the environment's transition probabilities. It keeps a table of estimates $Q(s,a)$ and, after each transition $(s, a, r, s')$, nudges the relevant entry toward the Bellman target:

$Q(s,a) \leftarrow Q(s,a) + \alpha \left[\, \underbrace{r + \gamma \max_{a'} Q(s', a')}_{\text{TD target}} - \underbrace{Q(s,a)}_{\text{old estimate}} \,\right].$

The bracketed quantity is the TD error: how surprised we were, compared to what we predicted. The learning rate $\alpha \in (0,1]$ controls how much of that surprise we absorb into the estimate. The pieces:

• $r + \gamma \max_{a'} Q(s',a')$ is the target, a better estimate that uses one step of real reward plus the discounted best future value.
• $Q(s,a)$ is our current estimate.
• $\alpha$ scales the correction. Small $\alpha$ learns slowly but stably; large $\alpha$ learns fast but jitters.

# Tabular Q-learning, one episode
def q_learning_episode(env, Q, alpha=0.1, gamma=0.99, epsilon=0.1):
    s = env.reset()
    done = False
    while not done:
        # epsilon-greedy action selection (exploration covered next lesson)
        if random.random() < epsilon:
            a = env.sample_action()
        else:
            a = argmax(Q[s])
        s_next, r, done = env.step(a)
        best_next = 0.0 if done else max(Q[s_next])   # no bootstrap past terminal
        td_target = r + gamma * best_next
        Q[s][a] += alpha * (td_target - Q[s][a])       # the update rule
        s = s_next
    return Q

Note the detail that trips up beginners: at a terminal state there is no future, so the target is just $r$ (bootstrap value zero). Getting this wrong quietly corrupts every value estimate that leads to the terminal state.

A worked Q-update with numbers

Let us do one update by hand. Suppose:

• Current estimate $Q(s,a) = 2.0$.
• We take action $a$, receive reward $r = 1$, and land in $s'$.
• In $s'$ the best action value is $\max_{a'} Q(s', a') = 5.0$.
• Learning rate $\alpha = 0.1$, discount $\gamma = 0.9$.

First the TD target:

$r + \gamma \max_{a'} Q(s',a') = 1 + 0.9 \times 5.0 = 5.5.$

Then the TD error: $5.5 - 2.0 = 3.5$. Finally the update:

$Q(s,a) \leftarrow 2.0 + 0.1 \times 3.5 = 2.35.$

The estimate moved 10% of the way from 2.0 toward the target 5.5. Repeat this across many transitions and, under mild conditions, the table converges to $Q^{\star}$.

On-policy vs off-policy

Q-learning has a subtle and powerful property: it learns about the greedy policy (via the $\max$) while behaving according to a different, more exploratory policy. That makes it off-policy. Its close cousin SARSA uses the action actually taken next instead of the max, which makes it on-policy.

The distinction becomes practically important later: replay buffers and most deep value-based methods rely on off-policy learning, while many policy-gradient methods (next lesson) are on-policy.

Where this leads: the exploration problem

The Q-learning loop above has a hidden dependency: it only converges if the agent keeps trying every state–action pair often enough. If it always acts greedily on its current estimates, it can lock onto a mediocre action and never discover a better one whose value it underestimated. Deciding when to trust current estimates versus gather more information is the exploration–exploitation tradeoff, the subject of a dedicated lesson later in this course. The epsilon in the code above is a first taste of the fix.

Further reading

• Sutton & Barto, Reinforcement Learning: An Introduction (2nd ed.), Chapters 3–6 develop value functions, the Bellman equations, and TD/Q-learning rigorously: http://incompleteideas.net/book/the-book.html
• OpenAI Spinning Up, "Intro to RL, Part 2: Kinds of RL Algorithms", situates value-based methods among the alternatives: https://spinningup.openai.com/en/latest/spinningup/rl_intro2.html
• Mnih et al., "Human-level control through deep reinforcement learning" (DQN, Nature 2015), scales Q-learning to pixels with function approximation: https://www.nature.com/articles/nature14236
• UC Berkeley CS285, "Deep Reinforcement Learning", lecture notes on value functions and Q-learning: https://rail.eecs.berkeley.edu/deeprlcourse/