Policy Gradient Algorithms - REINFORCE

Given that RL can be posed as an MDP, in this section we continue with a policy-based algorithm that learns the policy directly by optimizing the objective function. The algorithm we treat here, called REINFORCE, is important as it’s the basis of many other algorithms — including modern variants like PPO and GRPO that we use to fine-tune VLMs (see the browser-control GRPO tutorial). It took its name from the fact that during training actions that resulted in good outcomes should become more probable—these actions are positively reinforced. Conversely, actions which resulted in bad outcomes should become less probable. If learning is successful, over the course of many iterations, action probabilities produced by the policy, shift to a distribution that results in good performance in the environment we interact with. Action probabilities are changed by following the policy gradient, therefore REINFORCE is known as a policy gradient algorithm. The algorithm needs three components: Out of the three components, the most complicated one is the policy gradient that can be shown to be given by the differentiable quantity: $\nabla_\theta J(\pi_\theta)= \mathbb{E}_{\pi_\theta} \left[ \nabla_\theta \log \pi_\theta (a|s)\, Q^{\pi_\theta}(s, a) \right ]$ where $Q^{\pi_\theta}(s, a)$ is the action-value under the current policy. In REINFORCE we estimate $Q^{\pi_\theta}(s, a)$ by the Monte Carlo return $G_t$ (see the algorithm below) — using a learned $v_\pi(s)$ instead would make this an actor-critic method, which we treat in a later section. We understand that this expression came out of nowhere but the interested reader can find its detailed derivation in chapter 2 of this reference. For the derivation we use the log-derivative trick.

​

Step-by-step derivation

This transformation is crucial because it converts the problem of differentiating through an expectation into an expectation of a tractable quantity, enabling Monte Carlo estimation even when $f(x)$ is a black-box function without a closed-form gradient. We can approximate the value at state $s$ with the return over many sample trajectories $\tau$ that are sampled from the policy network. $\nabla_\theta J(\pi_\theta)= \mathbb{E}_{\tau \sim \pi_\theta} \left[ G_t \nabla_\theta \log \pi_\theta (a|s) \right ]$ where $G_t$ is the return - a quantity we have seen earlier albeit now the return is limited by the length of each trajectory just like in MC method, $G_t(\tau) = \sum_{k=0}^{T-t-1}\gamma^k R_{t+k+1}$ The $\gamma$ is a hyperparameter that is tuned, typically by searching over values in [0.01, …, 0.99] and selecting the one with the best results. We also have an expectation in the gradient expression that we need to address. The expectation $\mathbb E_{\tau \sim \pi_\theta}$ is approximated with a summation over each trajectory — a Monte Carlo (MC) approximation. Effectively, we are generating the right-hand side as in line 8 in the code below, by sampling a trajectory (line 4) and estimating its return (line 7) in a completely model-free fashion, i.e. without assuming any knowledge of the transition and reward functions. This is implemented next: Editable Mermaid source: images/reinforce-loop.mermaid.md It is important that a trajectory is discarded after each parameter update—it cannot be reused. This is because REINFORCE is an on-policy algorithm just like the MC it “learns on the job”. This is evidently seen in line 10 where the parameter update equation uses the policy gradient that itself (line 8) directly depends on action probabilities $\pi_\theta(a_t | s_t)$ generated by the current policy $\pi_\theta$ only and not some other policy $\pi_{\theta'}$. Correspondingly, the return $G_t(\tau)$ where $\tau \sim \pi_\theta$ must also be generated from $\pi_\theta$, otherwise the action probabilities will be adjusted based on returns that the policy wouldn’t have generated.

​

Policy Network

One of the key ingredients that REINFORCE introduces is the policy network that is approximated with a NN eg. a fully connected neural network (e.g. two RELU-layers). 1: Given a policy network net, a Categorical (multinomial) distribution class, and a state 2: Compute the output pdparams = net(state) 3: Construct an instance of an action probability distribution  pd = Categorical(logits=pdparams) 4: Use pd to sample an action, action = pd.sample() 5: Use pd and action to compute the action log probability, log_prob = pd.log_prob(action) Other discrete distributions can be used and many actual libraries parametrize continuous distributions such as Gaussians.

​

Applying the REINFORCE algorithm

It is now instructive to see a standalone example in Python for the CartPole-v1 environment ². The following is illustrative pseudocode — structurally faithful to SLM-Lab but modernized for the current Gymnasium API. PROTECTED_0 The REINFORCE algorithm presented here can be applied to both discrete and continuous action spaces, but it has high variance and is sample-inefficient.

​

Reducing variance with a baseline

A well-known fix is to subtract a state-dependent baseline $b(s)$ from the return: $\nabla_\theta J(\pi_\theta) = \mathbb{E}_{\tau \sim \pi_\theta} \left[ \left( G_t - b(s_t) \right) \nabla_\theta \log \pi_\theta(a_t \mid s_t) \right]$ Any baseline that does not depend on the action $a_t$ leaves the gradient unbiased but can dramatically reduce variance. The most common choice is $b(s_t) = v_\pi(s_t)$ — the state-value function estimated by a separate network. This gives rise to the advantage $A(s_t, a_t) = G_t - v_\pi(s_t)$ and leads directly to actor-critic methods (and from there to PPO and GRPO). See section 2.5.1 of Foundations of Deep Reinforcement Learning for further improvements. Key references: (Schulman et al., 2017; Schulman et al., 2015; Szepesvári et al., 2010; Wang et al., 2016; Rafati & Noelle, 2019)

​

References

• Rafati, J., Noelle, D. (2019). Learning sparse representations in reinforcement learning.
• Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O. (2017). Proximal Policy Optimization Algorithms.
• Schulman, J., Levine, S., Moritz, P., Jordan, M., Abbeel, P. (2015). Trust Region Policy Optimization.
• Szepesvári, C., Cochran, J., Cox, L., Keskinocak, P., Kharoufeh, J., et al. (2010). Reinforcement Learning Algorithms for MDPs. Wiley Encyclopedia of Operations Research and Management Science.
• Wang, J., Kurth-Nelson, Z., Tirumala, D., Soyer, H., Leibo, J., et al. (2016). Learning to reinforcement learn.

---

Footnotes

1. Notation wise, since we need to have a bit more flexibility in RL problems, we will use the symbol $J(\pi_\theta)$ as the objective function. ↩
2. Please note that SLM-Lab, is the library that accompanies this book. You will learn a lot by reviewing the implementations under the agents/algorithms directory to get a feel of how RL problems are abstracted. ↩