Policy Gradient Methods

Policy Gradient Methods are a class of algorithms in reinforcement-learning that optimize the policy directly, rather than learning a value function and selecting actions greedily based on it. The policy is parameterized as a function ${\pi }_{\theta }(a|s)=\mathbb{P}(A_t=a\mid S_t=s;\theta )$, where $\theta \in {\mathbb{R}}^d$ is the parameter vector (such as the weights of a neural network).

Unlike value-based methods like Q-learning, policy gradient methods find an optimal policy ${\pi }^{\ast }$ by performing gradient ascent on the expected cumulative reward.

---

Direct Parameterization vs. Value-Based Methods

Feature	Value-Based (e.g., Q-Learning)	Policy Gradient (Direct Parameterization)
Objective	Learn action-value function $Q(s,a)$	Learn policy parameters $\theta$ directly
Policy Formulation	Implicitly derived (e.g., $ϵ$-greedy)	Explicitly parameterized ${\pi }_{\theta }(a\mid s)$
Action Space	Typically discrete	Discrete and continuous action spaces
Stochasticity	Deterministic (requires exploratory noise)	Can naturally learn optimal stochastic policies
Convergence	Can oscillate or diverge with function approximation	Guaranteed convergence to a local (or global) optimum

---

Mathematical Formulation

Let $\tau =(s_0,a_0,s_1,a_1,\dots ,s_T)$ be a trajectory (or rollout) of states and actions. The probability of trajectory $\tau$ under a policy ${\pi }_{\theta }$ and transition dynamics $P(s_{t+1}\mid s_t,a_t)$ is:

$P(\tau ;\theta )={\rho }_0(s_0){\prod }_{t=0}^{T-1}P(s_{t+1}\mid s_t,a_t){\pi }_{\theta }(a_t\mid s_t)$

The expected return $J(\theta )$ of the policy is defined as:

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

where $R(\tau )={\sum }_{t=0}^T{\gamma }^{t}r(s_t,a_t)$ is the cumulative discounted reward of the trajectory.

We want to find parameters $\theta$ that maximize $J(\theta )$:

${\theta }^{\ast }=\arg {\max }_{\theta }J(\theta )$

To optimize this using gradient ascent, we compute the gradient ${\nabla }_{\theta }J(\theta )$:

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

The Likelihood Ratio / Log-Derivative Trick

Because the expectation depends on $\theta$ through the distribution $P(\tau ;\theta )$, we cannot directly take the derivative inside the expectation. Instead, we use the identity ${\nabla }_{\theta }f(\theta )=f(\theta ){\nabla }_{\theta }\log f(\theta )$:

${\nabla }_{\theta }J(\theta )={\nabla }_{\theta }\int P(\tau ;\theta )R(\tau )d\tau$ ${\nabla }_{\theta }J(\theta )=\int {\nabla }_{\theta }P(\tau ;\theta )R(\tau )d\tau$ ${\nabla }_{\theta }J(\theta )=\int P(\tau ;\theta ){\nabla }_{\theta }\log P(\tau ;\theta )R(\tau )d\tau$ ${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{\tau \sim {\pi }_{\theta }}[{\nabla }_{\theta }\log P(\tau ;\theta )R(\tau )]$

Substituting the probability of the trajectory, the environmental transition dynamics drop out because they do not depend on $\theta$:

$\log P(\tau ;\theta )=\log {\rho }_0(s_0)+{\sum }_{t=0}^{T-1}\log P(s_{t+1}\mid s_t,a_t)+{\sum }_{t=0}^T\log {\pi }_{\theta }(a_t\mid s_t)$ ${\nabla }_{\theta }\log P(\tau ;\theta )={\sum }_{t=0}^T{\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)$

Thus, the policy gradient is:

${\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)R(\tau )\right]$

This is the foundational mathematical equation of policy gradient methods. Crucially, it does not require knowing the transition dynamics $P(s_{t+1}\mid s_t,a_t)$.

---

Policy Gradient Theorem

In continuing tasks (without a fixed episode length), the gradient can be expressed in terms of the stationary distribution $d^{\pi }(s)$:

${\nabla }_{\theta }J(\theta )={\sum }_s{d}^{\pi }(s){\sum }_a{\nabla }_{\theta }{\pi }_{\theta }(a\mid s)Q^{{\pi }_{\theta }}(s,a)$

Using the log-derivative trick:

${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{s\sim d^{\pi },a\sim {\pi }_{\theta }}\left[{\nabla }_{\theta }\log {\pi }_{\theta }(a\mid s)Q^{{\pi }_{\theta }}(s,a)\right]$

---

Variance Reduction & Baselines

A major limitation of the basic policy gradient formula is high variance, since the return $R(\tau )$ is computed from sample trajectories. We can subtract a state-dependent baseline $b(s)$ from the return to reduce variance without introducing bias.

${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{s\sim d^{\pi },a\sim {\pi }_{\theta }}\left[{\nabla }_{\theta }\log {\pi }_{\theta }(a\mid s)(Q^{{\pi }_{\theta }}(s,a)-b(s))\right]$

The baseline $b(s)$ must not depend on the action $a$. A common choice is the state-value function $V^{{\pi }_{\theta }}(s)$. The difference $Q^{{\pi }_{\theta }}(s,a)-V^{{\pi }_{\theta }}(s)$ is known as the Advantage Function $A(s,a)$:

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

The advantage measures how much better action $a$ is than the average action in state $s$. Using the advantage function yields the policy gradient update:

${\nabla }_{\theta }J(\theta )={\mathbb{E}}_{s\sim d^{\pi },a\sim {\pi }_{\theta }}\left[{\nabla }_{\theta }\log {\pi }_{\theta }(a\mid s)A(s,a)\right]$

---

Key Algorithms

1. REINFORCE (Monte Carlo Policy Gradient)

REINFORCE is the simplest policy gradient algorithm. It estimates the return $R(\tau )$ using Monte Carlo rollout returns $G_t={\sum }_{k=t}^T{\gamma }^{k-t}{r}_t$:

$\theta \leftarrow \theta +\alpha {\sum }_{t=0}^T{\gamma }^t{G}_t{\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t)$

• Pros: Unbiased gradient estimates, simple to implement.
• Cons: Extremely high variance, requires complete episodes before making updates.

2. Actor-Critic Methods

Actor-Critic methods reduce variance by combining policy gradient with a learned value function:

• Actor: Represents the policy ${\pi }_{\theta }(a\mid s)$ and updates it via gradient ascent.
• Critic: Learns a parametric value function $V_{\varphi }(s)$ to estimate the expected return (e.g., temporal-difference learning).
• Update Rule: The policy update uses the TD error ${\delta }_t=r_t+\gamma V_{\varphi }(s_{t+1})-V_{\varphi }(s_t)$ as an estimate of the advantage: $\theta \leftarrow \theta +\alpha {\nabla }_{\theta }\log {\pi }_{\theta }(a_t\mid s_t){\delta }_t$

3. Proximal Policy Optimization (PPO) & Trust Region Policy Optimization (TRPO)

• TRPO constrains policy updates using the Kullback-Leibler (KL) divergence to prevent the policy from changing too drastically.
• proximal-policy-optimization (PPO) simplifies this by using a clipped surrogate objective that achieves similar stability with first-order optimization.

---

Advantages and Disadvantages

Advantages

1. Continuous Action Spaces: Value-based methods require calculating ${\max }_{a}Q(s,a)$, which is intractable for infinite action spaces. Policy gradient methods parameterize continuous distributions (e.g., Gaussian policies) and sample from them directly.
2. Stochastic Policies: In partially observable environments or competitive games, the optimal policy may be stochastic (e.g., rock-paper-scissors). Policy gradient methods can learn these distributions naturally.
3. Smooth Optimization: Because the policy is direct, small parameter changes lead to small policy changes. Value-based methods can have abrupt changes in behavior.

Disadvantages

1. High Variance: High variance in returns leads to noisy gradients and slow learning.
2. Sample Inefficiency: Typically require a vast number of environment steps to learn effective policies compared to off-policy value-based algorithms.
3. Local Optima: Prone to converging to local optima rather than the global optimum.

---

Related Topics

• reinforcement-learning
• proximal-policy-optimization
• machine-learning
• reinforcement-learning-from-human-feedback (RLHF)