REINFORCE Algorithm

Building upon the idea of directly optimizing a parameterized policy $\pi_\theta(a|s)$, we now introduce a specific algorithm to achieve this: REINFORCE. Also known as Monte Carlo Policy Gradient, REINFORCE provides a straightforward way to adjust the policy parameters $\theta$ based on the outcomes of interactions with the environment.

The core principle of REINFORCE is intuitive: increase the probability of actions that lead to good outcomes and decrease the probability of actions that lead to poor outcomes. Since we're dealing with parameterized policies, "increasing the probability" means adjusting the parameters $\theta$ in a direction suggested by the gradient of the policy's performance.

REINFORCE is a Monte Carlo method because it learns only after observing the complete return from an entire episode. It doesn't update parameters mid-episode like Temporal Difference methods (SARSA, Q-learning). Instead, it waits until the episode finishes, calculates the return ($G_t$) obtained from each state $S_t$ onwards, and then updates the policy parameters based on these returns.

The REINFORCE Update Rule

Let $J(\theta)$ represent the objective function we want to maximize, typically the expected return from the start state. The Policy Gradient Theorem provides a way to calculate the gradient of this objective with respect to the policy parameters $\theta$. REINFORCE uses a sampled version of this gradient based on experiences from episodes.

For a single episode, the update applied to the parameters $\theta$ after the episode concludes, considering each time step $t$, is:

$$\theta \leftarrow \theta + \alpha \sum_{t=0}^{T-1} G_t \nabla_\theta \log \pi_\theta(A_t|S_t)$$

Alternatively, updates can happen incrementally at each step $t$ of the episode, using the return $G_t$ calculated after the episode finishes:

$$\theta \leftarrow \theta + \alpha G_t \nabla_\theta \log \pi_\theta(A_t|S_t)$$

Let's break down the components of this update rule:

• $\alpha$: The learning rate, a small positive scalar determining the step size.
• $G_t$: The total discounted return starting from time step $t$ until the end of the episode. It's calculated as $G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + ... + \gamma^{T-t-1} R_T$, where $T$ is the terminal time step and $\gamma$ is the discount factor. This $G_t$ value represents the actual outcome experienced after taking action $A_t$ in state $S_t$ (and following policy $\pi_\theta$ thereafter).
• $\nabla_\theta \log \pi_\theta(A_t|S_t)$: This is the gradient of the logarithm of the probability of taking the specific action $A_t$ in state $S_t$, according to the current policy parameterization $\theta$. This term is often called the "eligibility vector". It points in the direction in parameter space that most rapidly increases the log-probability of the action $A_t$ being chosen in state $S_t$.

The update rule essentially pushes the parameters $\theta$ in the direction specified by $\nabla_\theta \log \pi_\theta(A_t|S_t)$, scaled by the return $G_t$.

• If $G_t$ is positive (better than average outcome, loosely speaking), the update increases the probability of taking action $A_t$ in state $S_t$ in the future.
• If $G_t$ is negative (worse than average outcome), the update decreases the probability of taking action $A_t$ in state $S_t$ in the future.

The magnitude of the update is proportional to the return $G_t$, so actions leading to significantly better or worse outcomes result in larger parameter adjustments.

The REINFORCE Algorithm Steps

Here's a typical outline of the REINFORCE algorithm:

1. Initialize: Choose a policy parameterization $\pi_\theta(a|s)$ (e.g., a neural network with parameters $\theta$) and initialize $\theta$ randomly or with predetermined weights. Set a learning rate $\alpha$.
2. Loop (for each episode): a. Generate Episode: Run one full episode by following the current policy $\pi_\theta$. This means starting in $S_0$, choosing $A_0 \sim \pi_\theta( \cdot | S_0)$, observing $R_1, S_1$, choosing $A_1 \sim \pi_\theta( \cdot | S_1)$, observing $R_2, S_2$, and so on, until a terminal state $S_T$ is reached. Store the sequence of states, actions, and rewards: $(S_0, A_0, R_1, S_1, A_1, R_2, ..., S_{T-1}, A_{T-1}, R_T)$. b. Calculate Returns: For each time step $t$ in the episode (from $t = 0$ to $T-1$): Calculate the return $G_t = \sum_{k=t+1}^{T} \gamma^{k-t-1} R_k$. c. Update Parameters: For each time step $t$ in the episode (from $t = 0$ to $T-1$): Compute the gradient $\nabla_\theta \log \pi_\theta(A_t|S_t)$. Update the policy parameters: $\theta \leftarrow \theta + \alpha G_t \nabla_\theta \log \pi_\theta(A_t|S_t)$.
3. Repeat: Go back to step 2 to generate and learn from more episodes.

The updates can be accumulated across all steps within an episode and applied once at the end, or applied incrementally after calculating each $G_t$. Modern deep learning frameworks often facilitate calculating $\nabla_\theta \log \pi_\theta(A_t|S_t)$ using automatic differentiation.

Representing the Policy

The policy $\pi_\theta(a|s)$ needs to be a function that takes the state $s$ and parameters $\theta$ as input and outputs probabilities for each possible action $a$. For discrete action spaces, a common approach is to use a neural network that outputs scores (logits) for each action, followed by a softmax function to convert these scores into probabilities:

$$\pi_\theta(a|s) = \text{softmax}(\text{NN}_\theta(s))_a = \frac{e^{\text{logit}_a}}{\sum_{b} e^{\text{logit}_b}}$$

Where $\text{NN}_\theta(s)$ is the output vector of the neural network for state $s$, and $\text{logit}_a$ is the element corresponding to action $a$. The gradient $\nabla_\theta \log \pi_\theta(a|s)$ can then be computed with respect to the network parameters $\theta$.

Advantages and Disadvantages

REINFORCE is simple and serves as a foundation for more advanced policy gradient methods.

Advantages:

• Can learn stochastic policies naturally.
• Can handle continuous action spaces by parameterizing the policy appropriately (e.g., outputting parameters of a Gaussian distribution).
• Relatively easy to understand and implement compared to some other methods.

Disadvantages:

• High Variance: The biggest drawback. The update depends on the Monte Carlo return $G_t$, which can vary significantly between episodes even with the same policy, purely due to randomness in the environment or the policy itself. This high variance makes learning slow and unstable.
• Sample Inefficiency: Learning only occurs at the end of an episode, potentially requiring many episodes to make substantial progress, especially for long episodes.
• Convergence: Can sometimes converge to local optima rather than the global optimum.

The high variance issue is particularly important. Imagine an episode where most actions were good, but one random unlucky event near the end resulted in a very low overall return $G_t$ for all preceding steps. REINFORCE would incorrectly penalize all actions taken earlier in that episode. This motivates the development of techniques like baselines and Actor-Critic methods, which we will discuss next, to mitigate this variance and improve learning stability and efficiency.