Policy Gradient Methods

Instead of learning action values and deriving a policy (like ε-greedy), we can directly learn a parameterized policy π(a|s,θ) that maps states to action probabilities. The parameter vector θ is what we learn.

The Basic Update

Policy gradient methods perform gradient ascent on the performance measure:

where the estimate approximates the true gradient of performance with respect to θ.

Soft-max Policy Parameterization

For discrete actions, a common approach is to learn action preferences h(s,a,θ) and convert them to probabilities using a soft-max:

The preferences can be linear: h(s,a,θ) = θ⊤x(s,a), or computed by a neural network.

Advantages Over Value-Based Methods

A fundamental challenge: performance depends on both action selections AND the state distribution, both of which change when we update θ. How can we compute the gradient when the state distribution is unknown?

Performance Measure

For episodic tasks, performance is the value of the start state:

The Theorem

The policy gradient theorem establishes:

Smooth Updates

Policy gradient methods have better convergence properties than value-based methods because:

• Action probabilities change smoothly as θ changes
• No sudden policy changes from small value estimate changes
• Guaranteed improvement for small enough step sizes

REINFORCE is the simplest policy gradient algorithm. It uses complete episode returns to estimate the gradient, making it a Monte Carlo method for policy learning.

Deriving the Update

Starting from the policy gradient theorem, we can derive a sample-based update:

This leads to the REINFORCE update:

The Eligibility Vector

The fraction ∇π(a|s,θ)/π(a|s,θ) is called the eligibility vector. It equals ∇ln π(a|s,θ). For soft-max policies with linear preferences:

This is the feature vector for the taken action minus the average feature vector across all actions.

REINFORCE Algorithm

Input: differentiable policy parameterization π(a|s,θ)
Parameters: step size α > 0
Initialize: θ arbitrarily

Loop forever (for each episode):
    Generate episode S₀, A₀, R₁, ..., S_{T-1}, A_{T-1}, R_T
    following π(·|·,θ)

    Loop for each step t = 0, 1, ..., T-1:
        G ← Σ_{k=t+1}^T γ^{k-t-1} R_k    # Return from step t
        θ ← θ + α γ^t G ∇ln π(A_t|S_t,θ)

We can reduce REINFORCE's variance by subtracting a baseline from the return. As long as the baseline doesn't depend on the action, it doesn't change the expected update but can dramatically reduce variance.

Why Baselines Work

Adding a baseline b(s) doesn't change the expected gradient:

Since action probabilities sum to 1, the gradient of their sum is zero. So adding any state-dependent baseline doesn't bias the update.

REINFORCE with Baseline Update

Complete Algorithm

Input: differentiable policy π(a|s,θ)
Input: differentiable state-value function v̂(s,w)
Parameters: step sizes α^θ > 0, α^w > 0
Initialize: θ, w arbitrarily

Loop forever (for each episode):
    Generate episode following π(·|·,θ)

    Loop for each step t = 0, 1, ..., T-1:
        G ← Σ_{k=t+1}^T γ^{k-t-1} R_k
        δ ← G - v̂(S_t,w)                    # Advantage estimate
        w ← w + α^w δ ∇v̂(S_t,w)             # Update critic
        θ ← θ + α^θ γ^t δ ∇ln π(A_t|S_t,θ)  # Update actor

REINFORCE uses the full return, which requires waiting until episode end. Actor-criticmethods use TD learning to update on every step, dramatically reducing variance at the cost of some bias.

One-Step Actor-Critic

Instead of the full return G_t, use the one-step TD target:

where the TD error is:

One-Step Actor-Critic Algorithm

Input: differentiable policy π(a|s,θ) and value function v̂(s,w)
Parameters: step sizes α^θ > 0, α^w > 0
Initialize: θ, w arbitrarily

Loop forever (for each episode):
    Initialize S, I ← 1

    Loop while S is not terminal:
        A ~ π(·|S,θ)
        Take action A, observe R, S'

        δ ← R + γv̂(S',w) - v̂(S,w)   # TD error
        w ← w + α^w δ ∇v̂(S,w)        # Update critic
        θ ← θ + α^θ I δ ∇ln π(A|S,θ) # Update actor

        I ← γI
        S ← S'

Actor-Critic with Eligibility Traces

We can add eligibility traces to both actor and critic for n-step or λ-return methods:

Eligibility trace updates:
    z^w ← γλ^w z^w + ∇v̂(S,w)           # Critic trace
    z^θ ← γλ^θ z^θ + I ∇ln π(A|S,θ)    # Actor trace

Weight updates:
    w ← w + α^w δ z^w                   # Update critic
    θ ← θ + α^θ δ z^θ                   # Update actor

For continuing problems without episode boundaries, we define performance as the average reward rate rather than the start state value.

Average Reward Setting

Performance is the average reward per time step:

This equals the expected immediate reward under the stationary distribution μ.

Differential Returns

Values are defined with respect to differential returns (rewards minus the average):

Continuing Actor-Critic

Initialize: R̄ ← 0, w, θ, z^w ← 0, z^θ ← 0

Loop forever (for each time step):
    A ~ π(·|S,θ)
    Take action A, observe R, S'

    δ ← R - R̄ + v̂(S',w) - v̂(S,w)    # Differential TD error
    R̄ ← R̄ + α^R̄ δ                    # Update average reward

    z^w ← λ^w z^w + ∇v̂(S,w)
    z^θ ← λ^θ z^θ + ∇ln π(A|S,θ)

    w ← w + α^w δ z^w
    θ ← θ + α^θ δ z^θ

    S ← S'

One of the biggest advantages of policy gradient methods is their natural handling of continuous action spaces. Instead of learning probabilities for each action, we learn the parameters of a probability distribution.

Gaussian Policy

The policy is defined as a normal distribution over actions:

Linear Parameterization

A simple linear form:

The exponential ensures σ is always positive.

Eligibility Vectors for Gaussian Policy

The eligibility vectors (∇ln π) for the Gaussian policy:

Policy gradient methods represent a fundamental shift from value-based to policy-based learning. They offer unique advantages and have become central to modern reinforcement learning, especially in deep RL.

Method Comparison