7
$\begingroup$

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):

enter image description here

The actual policy update is:

enter image description here

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?

$\endgroup$

2 Answers 2

6
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Similarly, if the returns are almost always 0 (say on MountainCar), then vanilla REINFORCE won't learn anything from these unsuccessful episodes, correct? $\endgroup$ May 16, 2019 at 16:35
  • $\begingroup$ @MasterScrat Returns are always some negative number from MountainCar (unless you have found an unusual version), and lower values represent longer times to complete the episode. It is not possible to get a return of zero in that environment from any non-terminal state. However, yes REINFORCE does not learn well from low or zero returns, even if they are informative (e.g. when other values of return are possible, and could be taken into account, which is what the baseline would allow for). $\endgroup$ May 16, 2019 at 17:03
3
$\begingroup$

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".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.