From Q-Learning to Policy Gradients

Q-learning is elegant – as long as the action space is discrete and small. As soon as robot arms, torques or trading volumes enter the picture, the argmax operation breaks down. This article shows the conceptual leap from value-based to policy-based methods, explains the likelihood-ratio trick and implements REINFORCE on a numpy mini world.

1. The Problem With Q-Values on Continuous Actions

Q-learning picks actions via $a^* = \arg\max_a Q(s, a)$. That operation is trivial when $A$ is small and discrete (e.g. "left/right/up/down"). It immediately becomes hard once $A$ is continuous:

❌ Workaround: Discretisation

# Naive: continuous torque [-1, 1] into 11 bins.
actions = np.linspace(-1, 1, 11)
best_q = max(q_net(state, a) for a in actions)

For a 7-DoF arm this explodes to $11^7 \approx 2 \cdot 10^7$ actions per step – unusable.

✅ Idea: Parametrise the Policy Directly

Instead of learning $Q(s, a)$ and then searching for $\arg\max$, we learn the policy itself: $\pi_\theta(a \mid s)$ is a neural network that outputs a distribution over actions directly from $s$ (or, for continuous actions, the parameters of a Gaussian). There is no argmax any more – actions are sampled.

2. The Policy-Gradient Objective

The agent maximises the expected return under its policy:

$$J(\theta) = \mathbb{E}{\tau \sim \pi\theta}\left[\sum_{t=0}^{T} \gamma^t r_t\right]$$

The naive idea would be to differentiate $J(\theta)$ directly. The problem: the expectation is over trajectories $\tau$ whose distribution itself depends on $\theta$. We cannot simply "differentiate the reward w.r.t. $\theta$" – rewards are a black box.

3. The Likelihood-Ratio Trick

The central trick of policy-gradient theory makes the problem tractable:

$$\nabla_\theta J(\theta) = \mathbb{E}{\tau \sim \pi\theta}\left[\sum_{t=0}^{T} \nabla_\theta \log \pi_\theta(a_t \mid s_t) \cdot G_t\right]$$

In words: the gradient of the expected return equals the expected gradient of the log-policy, weighted by the return. Two-line proof sketch:

$$\nabla_\theta \mathbb{E}\pi[f] = \int \nabla\theta \pi \cdot f \, da = \int \pi \cdot \nabla_\theta \log \pi \cdot f \, da = \mathbb{E}\pi[\nabla\theta \log \pi \cdot f]$$

The substitution $\nabla \pi = \pi \cdot \nabla \log \pi$ is the trick. The result: we can estimate the gradient by sampling – we do not need to know the environment dynamics.

4. REINFORCE – the Smallest Policy-Gradient Algorithm

REINFORCE (Williams, 1992) is the direct implementation of the formula above:

1. Collect a full episode under $\pi_\theta$.
2. For each step compute the return $G_t$.
3. Update: $\theta \leftarrow \theta + \alpha \cdot \nabla_\theta \log \pi_\theta(a_t \mid s_t) \cdot G_t$.

That is the whole complexity – one law of nature plus one update step.

5. Runnable: REINFORCE on 1D Gridworld

We use the same GridWorld setup as in article 01 and learn a policy that prefers the goal (right field). The policy is a simple table: one logit per state, softmax gives probabilities for left/right.

import numpy as np

rng = np.random.default_rng(0)
LENGTH = 7
GAMMA = 0.95
LR = 0.1
EPISODES = 2000

# Policy parameters: 2 logits per state (left, right).
theta = np.zeros((LENGTH, 2))

def softmax(x):
    z = x - x.max()
    e = np.exp(z)
    return e / e.sum()

def policy_probs(s):
    return softmax(theta[s])

def sample_action(s):
    return int(rng.choice(2, p=policy_probs(s)))

def step(state, action):
    state += 1 if action == 1 else -1
    state = max(0, min(LENGTH - 1, state))
    done = state in (0, LENGTH - 1)
    if done:
        r = 1.0 if state == LENGTH - 1 else -1.0
    else:
        r = 0.0
    return state, r, done

def run_episode():
    s = LENGTH // 2
    transitions = []
    for _ in range(50):
        a = sample_action(s)
        s_next, r, done = step(s, a)
        transitions.append((s, a, r))
        s = s_next
        if done:
            break
    return transitions

def compute_returns(rewards):
    g, returns = 0.0, []
    for r in reversed(rewards):
        g = r + GAMMA * g
        returns.insert(0, g)
    return np.array(returns)

# Training.
ep_returns = []
for ep in range(EPISODES):
    traj = run_episode()
    states  = [t[0] for t in traj]
    actions = [t[1] for t in traj]
    rewards = [t[2] for t in traj]
    G = compute_returns(rewards)

    # REINFORCE update per step.
    for s, a, g in zip(states, actions, G):
        probs = policy_probs(s)
        grad_log = -probs.copy()
        grad_log[a] += 1.0      # ∂/∂θ_a log π(a|s) = 1 - π(a|s); others: -π
        theta[s] += LR * grad_log * g

    ep_returns.append(sum(rewards))

# Evaluation: first vs. last 200 episodes.
print(f"Mean return (first 200) : {np.mean(ep_returns[:200]):+.3f}")
print(f"Mean return (last  200) : {np.mean(ep_returns[-200:]):+.3f}")
print("Learned P(right) per state:")
for s in range(LENGTH):
    print(f"  s={s}: {policy_probs(s)[1]:.2f}")

Expected result: the return starts near 0 and rises towards +1. The learned $P(\text{right})$ is clearly elevated in the middle and especially on the right – the agent has learned that "right" is the profitable default.

6. The Weakness of REINFORCE: Variance

REINFORCE works – but slowly. The reason is high variance of the gradient estimate. Three sources:

1. Stochastic environment: the same action yields different rewards.
2. Stochastic policy: the same situation leads to different actions.
3. Long episodes: a single bad move at the very beginning changes all $G_t$ in the episode.

The result: the estimator is unbiased but very noisy – gradient steps often point the wrong way, and only averaging over many episodes drives learning forward.

"REINFORCE is unbiased but high-variance. Almost every improvement in modern policy gradient methods – baselines, critics, GAE, trust regions – is a variance-reduction technique." – paraphrased from Schulman et al., High-Dimensional Continuous Control (2015).

7. Discussion: Value vs. Policy

The next articles (actor-critic, PPO, SAC) solve the variance problem with additional critics, trust regions and off-policy replay – uniting the strengths of both worlds.

8. Wrap-up Quiz

9. Further Reading

• Next article: Actor-Critic Architecture (article 03 of this series).
• Cross reference: self-learning-agents/02-rl-fuer-code-agenten.
• Knowledge base: masteringpytorch-secondedition.md – chapter on policy gradients.

Sources

• Williams, R. J. (1992) – Simple Statistical Gradient-Following Algorithms for Connectionist RL, Machine Learning, 8(3-4).
• Sutton & Barto – Reinforcement Learning: An Introduction, 2nd ed., ch. 13 (Policy Gradient Methods).
• Schulman, J. et al. (2015) – High-Dimensional Continuous Control Using Generalized Advantage Estimation.