RL Policy Gradient: How to deal with rewards that are strictly positive?
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.