In this article, we will discuss the methods known as Policy Gradient Methods and their important theoretical result, the Policy Gradient Theorem. This article is related to Reinforcement Learning. For a quick introduction to the topic, we recommend reading the following 1

Several classical Reinforcement Learning methods are based on learning the action-value function $Q(s,a)$ and deriving the policy $\pi$ from it. That is, without this function, the policy cannot be found. However, policy gradient methods take a different approach: instead of computing $Q(s,a)$ and then estimating the policy, we directly parameterize the policy as $\pi_{\theta}(a,s)$. In this way, the problem transforms into learning the parameters $\theta$. Nevertheless, the value function $V(s)$ can still be used to improve the parameterized policy, as seen in actor-critic methods.

These methods aim to estimate the parameters $\theta$ to increase the value of $J(\theta)$, where:

$$J(\theta) = \mathbb{E}_{\tau \sim \pi}[R(\tau)]$$

Here, $\tau$ represents the trajectories generated by the policy. Thus, the goal is to update the parameters in such a way that we maximize $J(\theta)$. To achieve this, we perform gradient ascent:

$$\theta_{t+1} = \theta_t + \alpha \nabla_{\theta} J(\theta_t)$$

All methods that follow this general scheme are called policy gradient methods, regardless of whether they require learning an approximation of the value function $V(s)$ or not.

Advantages

Using these methods presents several advantages. First, their representation is highly versatile, as long as $\pi(a,s)$ is differentiable. Additionally, they integrate easily into continuous spaces, unlike other methods that require discretization. They also have the ability to approximate a deterministic policy, unlike $\epsilon$-greedy methods.

$\epsilon$-greedy policies are those that choose a random action with probability $\epsilon$ instead of selecting the most optimal action according to their current $Q(s,a)$ function.

For a deeper understanding of these topics, we recommend reading the book Reinforcement Learning: An Introduction by Sutton & Barto, Part 13.1.

Now, besides their practical advantages, these methods also offer theoretical advantages compared to $\epsilon$-greedy policies. The most important difference is that policy gradient methods directly parameterize the policy without needing to estimate another function and then apply an operator like:

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

The use of this operator can introduce discontinuities in the policy due to the very nature of the $\arg \max$ operator, as small changes in the function $Q^{\pi}(s,a)$ can cause abrupt variations in the policy.

On the other hand, if we parameterize $\pi_{\theta}(a|s)$, we can obtain a smoother estimation of the signals received from the environment and generate actions based on a state in a more stable manner. This is because differentiability and, in particular, continuity when parameterizing $\pi_{\theta}$ imply that small changes in the parameters translate into small changes in decision-making, resulting in a more robust and smooth process.

Policy Gradient Theorem

Our problem now is how to estimate the value of our gradient. Fortunately, there is a theoretical result that allows us to compute it. This was proposed by Sutton, and we will now see its derivation following the details in 2.

We can measure overall performance by assuming it is calculated as the expected value when starting in an initial state of an episode; that is:

$$J(\theta) = v_{\pi_{\theta}}(s_0)$$

where $v_{\pi_{\theta}}$ is the true value function of $\pi_{\theta}$. The difficulty in computing the gradient of $J(\theta)$ with respect to $\theta$ lies in the fact that this value depends on both the actions generated by the policy $\pi_{\theta}$ and the distribution of states in which the agent finds itself, $p(s'|s,a)$. However, this distribution is determined by the environment and does not directly depend on the policy $\pi_{\theta}$.

This is where our theorem becomes important. To derive it, we start by computing the gradient of the value function:

$$\nabla v_{\pi}(s) = \nabla \left[ \sum_{a}\pi(a|s) q_{\pi}(s,a) \right]$$

We distribute the gradient operator and apply the product rule:

$$\nabla \pi(a|s)q_{\pi}(s,a) = q_{\pi}(s,a)\nabla\pi(a|s) + \pi(a|s)\nabla q_{\pi}(s,a)$$

Replacing in the initial equation:

$$\begin{aligned} \nabla v_{\pi}(s) = \sum_{a}\left[ q_{\pi}(s,a)\nabla\pi(a|s) + \pi(a|s)\nabla q_{\pi}(s,a) \right] \end{aligned}$$

Using the identity

$$q_{\pi}(s,a) = \sum_{s',r} p(s',r|s,a) (r + v_{\pi}(s'))$$

we can rewrite the expression as:

$$\nabla v_{\pi}(s) = \sum_{a}\left[ q_{\pi}(s,a)\nabla\pi(a|s) + \pi(a|s)\nabla \sum_{s',r} p(s',r|s,a)(r + v_{\pi}(s')) \right]$$

Since $p(s',r|s,a)$ does not depend on $\theta$ and using that $p(s',r|s,a) = p(s'|s,a)$, we can rewrite it as:

$$\nabla v_{\pi}(s) = \sum_{a}\left[ q_{\pi}(s,a)\nabla\pi(a|s) + \pi(a|s) \sum_{s'} p(s'|s,a) \nabla v_{\pi}(s') \right]$$

We observe that we have obtained a recursive equation: to compute $\nabla v_{\pi}(s)$, we also need the values of $\nabla v_{\pi}(s')$ for all future states $s'$. To continue with the derivation, we introduce the following notation.

$p^{\pi}(s\to x,k)$

We define the probability that, starting from a state $s$, we reach a state $x$ after $k$ steps following the policy $\pi$. We can construct this probability recursively:

• For $k=0$:

  $$p^{\pi}(s\to s, k=0) = 1$$

• For $k=1$:

  $$p^{\pi}(s\to s', k=1) = \sum_{a} \pi_{\theta}(a|s) p(s'|s,a)$$

• For $k+1$:

  $$p^{\pi}(s \to x, k+1) = \sum_{s'} p^{\pi}(s\to s',k) p^{\pi}(s'\to x,1)$$

This expression considers all the ways we can reach $x$ from $s$ in $k+1$ steps, using the information from the previous step.

Now we will see how this probability allows us to continue with the derivation of our initial equation.

Let’s reduce the expression into its recursive and non-recursive components:

$$\nabla v_{\pi}(s) = \sum_{a} q_{\pi}(s,a)\nabla\pi(a|s) + \sum_{a} \pi(a|s) \sum_{s'} p(s'|s,a)\nabla v_{\pi}(s')$$

Let’s denote $\phi(s) = \sum_{a} q^{\pi}(s,a)\nabla\pi(a|s)$. Then, our expression rewrites as:

$$\begin{aligned} \nabla v_{\pi}(s) &= \phi(s) + \sum_{a} \pi(a|s) \sum_{s'} p(s'|s,a)\nabla v_{\pi}(s') \\ &= \phi(s) + \sum_{s'} \sum_{a} \pi(a|s) p(s'|s,a)\nabla v_{\pi}(s') \end{aligned}$$

From the above, we obtain:

$$\nabla v_{\pi}(s) = \phi(s) + \sum_{s'} p(s \to s',k=1)\nabla v_{\pi}(s')$$

Since we can express $\nabla v_{\pi}(s')$ recursively as:

$$\nabla v_{\pi}(s') = \phi(s') + \sum_{s''} p(s' \to s'',k=1)\nabla v_{\pi}(s''),$$

substituting it into the previous equation, we get:

$$\begin{aligned} \nabla v_{\pi}(s) &= \phi(s) + \sum_{s'} p(s \to s',k=1) \left[ \phi(s') + \sum_{s''} p(s' \to s'',k=1)\nabla v_{\pi}(s'') \right] \\ &= \phi(s) + \sum_{s'} p(s \to s',k=1) \phi(s') + \sum_{s'} p(s \to s',k=1) \sum_{s''} p(s' \to s'',k=1)\nabla v_{\pi}(s'') \\ &= \phi(s) + \sum_{s'} p(s \to s',k=1) \phi(s') + \sum_{s''} \sum_{s'} p(s \to s',k=1) p(s' \to s'',k=1)\nabla v_{\pi}(s'') \end{aligned}$$

Since $p(s\to s'',k=2) = \sum_{s'} p(s\to s',k=1) p(s' \to s'',k=1)$, we can write:

$$\nabla v_{\pi}(s) = \phi(s) + \sum_{s'} p(s \to s',k=1)\phi(s') + \sum_{s''} p(s\to s'',k=2)\nabla v_{\pi}(s'')$$

Repeating the same process for any initial state $s$, we obtain:

$$\nabla v_{\pi}(s) = \sum_{x\in S} \sum_{k=0}^{\infty} p^{\pi}(s\to x,k)\phi(x)$$

This allows us to compute the gradient of the value function without needing to compute the gradients of $q^{\pi}(s,a)$.

Application in the Objective Function

If we take the objective function as $J(\theta) = v^{\pi}(s_0)$, where $s_0$ is the random initial state, we have:

$$\nabla J(\theta) = \sum_{s} \sum_{k=0}^{\infty} p^{\pi}(s_0\to s,k)\phi(s)$$

Let’s define $\eta(s) = \sum_{k=0}^{\infty} p^{\pi}(s_0\to s,k)$. Then:

$$\nabla J(\theta) = \sum_{s} \eta(s)\phi(s)$$

Since $\sum_s \eta(s)$ is a constant, we can write:

$$\nabla J(\theta) = \left(\sum_{s} \eta(s) \right) \sum_s \frac{\eta(s)}{\sum_s\eta(s)}\phi(s) \propto \sum_s \frac{\eta(s)}{\sum_s\eta(s)}\phi(s)$$

Defining the stationary distribution as:

$$d^{\pi}(s) = \sum_s \frac{\eta(s)}{\sum_s\eta(s)}$$

The stationary distribution represents the probability of being in a given state after an infinite number of steps in a Markov chain under policy $\pi$. Formally, it is defined as:

$$d^{\pi}(s) = \lim_{t\to\infty} P(s_t = s | s_0, \pi)$$

Thus, we finally obtain:

$$\nabla J(\theta) \propto \sum_s d^{\pi}(s) \sum_a q^{\pi}(s,a)\nabla\pi(a|s)$$

Rewriting the expression:

$$\nabla J(\theta) \propto \sum_s d^{\pi}(s) \sum_a \pi_{\theta}(a|s) q^{\pi}(s,a) \frac{\nabla \pi_{\theta}(a|s)}{\pi_{\theta}(a|s)}$$

Using the identity $\frac{d}{dx} \ln(x) = \frac{1}{x}$, we obtain:

$$\nabla J(\theta) = \mathbb{E}_{\pi} \left[ q^{\pi}(s,a)\nabla\ln \pi_{\theta}(a|s) \right]$$

where $\mathbb{E}_{\pi}$ denotes the expectation over the distribution $s \sim d^{\pi}, a \sim \pi$.

This formulation allows computing the gradient of the objective function without explicitly calculating the gradients of $q^{\pi}(s,a)$, which is useful since this function is usually unknown and depends more on the environment. In contrast, the policy $\pi$ is fully parameterizable.

Derivations of $\nabla J(\theta)$

As seen in various works 3, this is not the only way to compute $\nabla J(\theta)$. In fact, it can be generally expressed as:

$$\mathbb{\nabla} J(\theta) = \mathbb{E}_{\pi}[f(s,a)\nabla \ln \pi_{\theta}(s,a)]$$

Next, we will analyze some examples of functions used in relevant research and the theoretical conditions that the function $f(s,a)$ should satisfy. Additionally, we will compare these functions by evaluating their bias and variance.

Bias and Variance in $f(s,a)$

In practice, access to the true gradient $\nabla J(\theta)$ is not available. Instead, estimates based on samples, denoted as $\nabla \hat{J(\theta)}$, are used. The idea is that these estimates should, on average, be similar to $\nabla J(\theta)$ to ensure effective parameter updates.

The function $f(s,a)$ plays a fundamental role in this process. As mentioned earlier, the objective function $J(\theta)$ represents the expected value of the rewards from trajectories generated by the policy $\pi_{\theta}$. Therefore, to maintain this relationship, $f(s,a)$ must be unbiased, thus ensuring a correct estimation of the objective function.

Mathematically, this is expressed as:

$$\mathbb{E}_{a_{t+1},s_{t+1},... \sim \pi_{\theta}}[f(s,a)] = Q^{\pi}(s_t,a_t)$$

That is, on average, both values must be equal, guaranteeing that the estimation of the objective function remains consistent.

However, the choice of $f(s,a)$ also influences another important characteristic: variance. Variance measures the dispersion in gradient estimates due to the inherent randomness of the environment, the policy, or the samples used. High variance implies that gradient updates may fluctuate significantly from one iteration to another, making learning unstable or requiring more samples to converge.

Below, we present some examples of functions $f(s,a)$ along with an analysis of their variance and bias.

Examples of Functions $f(s,a)$

$R(\tau)$

In the context of Reinforcement Learning, given a trajectory $\tau$, the accumulated reward $R(\tau)$ is defined as:

$$R(\tau) = \sum_{t=1}^{T}r_t$$

In the work of R. J. Williams 4, the gradient of the objective function is estimated as:

$$\nabla J(\theta) = \mathbb{E}_{\pi}[R(\tau)\nabla \ln \pi_{\theta}(s,a)]$$

This function is valid because it satisfies the condition that $\mathbb{E}[R(\tau)] = Q(s,a)$. Below is the proof:

The total reward $R(\tau)$ includes all rewards from $t = 0$ to $T$. However, when conditioning on $s_t, a_t$, the rewards prior to $t$—that is, $( r(s_0,a_0), \dots, r(s_{t-1}, a_{t-1}) )$—are constants, since $s_t$ and $a_t$ are fixed. Therefore, the expectation of $R(\tau)$ given $s_t, a_t$ depends only on future rewards:

$$\mathbb{E}_{\tau \sim \pi_\theta}[R(\tau) | s_t, a_t] = \sum_{k=0}^{t-1} r(s_k, a_k) + \mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{k=t}^{T} r(s_k, a_k) | s_t, a_t \right]$$

However, in the policy gradient, the term $\nabla_\theta \log \pi_\theta(a_t | s_t)$ does not depend on past rewards. Therefore, when computing the expectation of the gradient:

$$\mathbb{E}_{\tau \sim \pi_\theta} \left[ \nabla_\theta \log \pi_\theta(a_t | s_t) R(\tau) \right] = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \nabla_\theta \log \pi_\theta(a_t | s_t) \sum_{k=t}^{T} r(s_k, a_k) \right]$$

Since past rewards are independent of $\nabla_\theta \log \pi_\theta(a_t | s_t)$, they can be canceled in the expectation. Finally, we obtain:

$$\mathbb{E}_{\tau \sim \pi_\theta} \left[ \sum_{k=t}^{T} r(s_k, a_k) | s_t, a_t \right] = Q^{\pi_\theta}(s_t, a_t)$$

Thus, we conclude that:

$$\mathbb{E}[R(\tau) | s_t, a_t] = Q(s_t, a_t)$$

Variance Analysis

The variance when $f(s,a) = R(\tau)$ is high. This is because $R(\tau)$ depends on a single trajectory, which can vary significantly due to the randomness of the environment and policy decisions. In stochastic environments or those with long horizons, two trajectories starting from the same initial state may have very different returns. This large fluctuation results in high variance, slowing down learning and making it less stable, as gradient updates can oscillate significantly between iterations.

$Q(s,a)$

This estimation appears in the classical work on Actor-Critic by Barto, Sutton, and Anderson (1983). Here, the original formulation of the gradient of $J(\theta)$ is used:

$$\nabla J(\theta) = \mathbb{E}_{\pi}\left[q^{\pi}(s,a)\nabla\ln \pi_{\theta}(a|s)\right]$$

The proof is trivial, so we will not include it. However, let's move on to the variance analysis.

Variance Analysis

The variance in the gradient estimator when using $Q(s, a)$ is moderate, as it smooths out fluctuations present in individual returns by taking an expectation over multiple trajectories. Compared to using $R(\tau)$ directly, where variance is high due to total dependence on observed rewards in each trajectory, $Q(s, a)$ provides a more stable estimate by considering the expectation over all possible sequences of actions and states.

However, despite this reduction, variance is not completely low. The estimation of $Q(s, a)$ is still affected by the inherent randomness in action selection and environment dynamics, introducing some fluctuation in gradient updates. This may require more samples to stabilize training compared to methods that use the advantage function $A(s, a)$. Nevertheless, its use in Actor-Critic methods has proven to be a viable alternative, balancing variance reduction and bias in policy gradient estimation.

$A(s,a)$

This estimation appears in the work of Schulman et al. (2016) 5. This function is defined as:

$$A(s,a) = Q(s,a) - V(s)$$

The advantage function $A(s, a)$ measures how much better taking action $a$ in state $s$ is compared to the average value of the state $V(s)$. Since $V(s)$ does not depend on action $a$, subtracting it does not affect the gradient direction, and the estimate remains unbiased. Now, let's see the proof that validates this property.

Consider the policy gradient estimator when using the advantage function:

$$\hat{g} = \mathbb{E}_{\tau \sim \pi_\theta}\Big[ \nabla_\theta \log \pi_\theta(a_t|s_t) \, A^{\pi_\theta}(s_t,a_t) \Big].$$

Substituting the definition of the advantage function, we obtain:

$$\hat{g} = \mathbb{E}_{\tau \sim \pi_\theta}\Big[ \nabla_\theta \log \pi_\theta(a_t|s_t) \, \big( Q^{\pi_\theta}(s_t,a_t) - V^{\pi_\theta}(s_t) \big) \Big].$$

Splitting the expectation into two terms:

$$\hat{g} = \underbrace{\mathbb{E}_{\tau \sim \pi_\theta}\Big[ \nabla_\theta \log \pi_\theta(a_t|s_t) \, Q^{\pi_\theta}(s_t,a_t) \Big]}_{\text{(I)}} - \underbrace{\mathbb{E}_{\tau \sim \pi_\theta}\Big[ \nabla_\theta \log \pi_\theta(a_t|s_t) \, V^{\pi_\theta}(s_t) \Big]}_{\text{(II)}}.$$

Since $V^{\pi_\theta}(s_t)$ is independent of action $a_t$, we can write term (II) as:

$$\text{(II)} = \mathbb{E}_{s_t}\Big[ V^{\pi_\theta}(s_t) \, \mathbb{E}_{a_t \sim \pi_\theta}\big[\nabla_\theta \log \pi_\theta(a_t|s_t)\big] \Big].$$

Here, we use the score function property, which states that:

$$\mathbb{E}_{a_t \sim \pi_\theta}\big[\nabla_\theta \log \pi_\theta(a_t|s_t)\big] = 0.$$

Thus, term (II) cancels out:

$$\text{(II)} = \mathbb{E}_{s_t}\Big[ V^{\pi_\theta}(s_t) \cdot 0 \Big] = 0.$$

Consequently, the estimator remains:

$$\hat{g} = \mathbb{E}_{\tau \sim \pi_\theta}\Big[ \nabla_\theta \log \pi_\theta(a_t|s_t) \, Q^{\pi_\theta}(s_t,a_t) \Big].$$

This shows that using the advantage function eliminates the $V^{\pi_\theta}(s_t)$ term without introducing bias in the gradient.

Conclusions

In this article, we have discussed the general methodology of policy gradient-based methods, their advantages over other approaches, and the theoretical result that supports them: the Policy Gradient Theorem. Finally, we provided its proof and explored different functions $f(s,a)$ within this theoretical framework.

In future articles, we will examine various algorithms based on these methods in more detail. For a more comprehensive reference, we recommend reading the following article by OpenAI researcher Lilian Weng 6

References

1. Lilian Weng. "A (Long) Peek into Reinforcement Learning".
2. R. S. Sutton and A. G. Barto. "Reinforcement Learning: An Introduction". MIT Press, 2018.
3. J. Schulman, P. Moritz, S. Levine, M. I. Jordan, and P. Abbeel. "High-dimensional continuous control using generalized advantage estimation". ICLR, 2016.
4. R. J. Williams. "Simple statistical gradient-following algorithms for connectionist reinforcement learning". Machine Learning, 1992.
5. A. G. Barto, R. S. Sutton, and C. W. Anderson. "Neuronlike adaptive elements that can solve difficult learning control problems". IEEE Transactions on Systems, Man, and Cybernetics, 1983.
6. Lilian Weng. "Policy Gradient Algorithms".