RL Policy Gradient: How to deal with rewards that are strictly positive?

Question

In short:

In the policy gradient method, if the reward is always positive (never negative), the policy gradient will always be positive, hence it will keep making our parameters larger. This makes the learning algorithm meaningless. How do we get around this problem?

---

In detail:

In "RL Course by David Silver" lecture 7 (on YouTube), he introduced the REINFORCE algorithm for policy gradient (here just showing 1 step):

The actual policy update is:

Note that $v_t$ here stands for the reward we get. Let's say we're playing a game where the reward is always positive (eg. accumulating a score), and there are never any negative rewards, the gradient will always be positive, hence $\theta$ will keep increasing! So how do we deal with rewards that never change sign?

Answer 1

Let's say we're playing a game where the reward is always positive (eg. accumulating a score), and there are never any negative rewards, the gradient will always be positive, hence θ will keep increasing! So how do we deal with rewards that never change sign?

This is true. However, in many policy functions and in most situations, the gradient part $\nabla_{\theta} log \pi_{\theta}(s_t,a_t)$ will tend to zero as you reach a deterministic policy. This happens for a softmax action selection based on "preferences" (a matrix of softmax weights per action for each state) or as the output layer of a neural network. And it will counteract the tendency for the final layer preferences (or the logits of the neural network last layer) to grow uncontrollably.

You have identified a true weakness of REINFORCE. For instance, using the softmax action selection as an example and your always-positive returns:

• When the agent selects a non-maximising action, this will result in a positive return, the agent will add to its preference for that action.

• When the agent selects a maximising action, this will result in a larger positive return, the agent will add to its preference for that action more

• REINFORCE works by increasing the preferences of better actions faster than preferences of worse actions.

• This leads to a feedback process where better actions are chosen more often, increasing their preference values even faster.

• Ultimately the preference for best actions will be so much higher than the alternatives that the softmax function will saturate. The gradient $\nabla_{\theta} log \pi_{\theta}(s_t,a_t)$ for all actions will be close to zero.

This does not always happen quickly, and basic REINFORCE implementations can be numerically unstable for exactly the reason in your question. To improve stability (and often learning speed), you can use REINFORCE with baseline, which starts to address your concern by using offsetting values ($v_t - \bar{v}_t$ or similar). You can also then take that idea further and use Actor-Critic.

Answer 2

Had a struggle with this recently as well, and here is what I came away with:

I believe you can think of the policy update result as similar to total loss over an episode. Recall that in a vanilla neural net, eg a perceptron, loss will be positive as well, and the optimizer is calculating how much each parameter in theta would have to change to achieve that loss (via gradient descent), and then this is backpropagated or the final update.

The difference here is that in this case we are trying to maximize a reward. Why then does the reward not go to infinity at some point? because there is a finite number of episodes in each simulation, and each action can give a maximum of 1, so there is an upper bound on the total reward given by your setup.

I am not really great on theory, but code snippets make more sense to me, so seeing how they are implemented gives some intuition:

Pytorch version - see the finish_episode() function - which is fairly clear.

Tensorflow Example (sorry I do not know a better one) - see the bottom of the session loop.

Here a simulation is run over several episodes which entail:

For each step in an episode, an action is chosen by sampling policy action scores, and these are stored, along with reward from the game.

At end of episode, a total policy loss is calculated with the policy action log probs and actual rewards (averaging over all steps in this case). Gradients are calculated w.r.t to the final policy loss, and backpropagated.

For reference, here is the [http://www-anw.cs.umass.edu/~barto/courses/cs687/williams92simple.pdf ](original paper) on REINFORCE, see pages 4-5 which explains that the update vector is not necessarily increasing, but "lies in a direction for which [the] performance measure is increasing".