Proof that the addition of a baseline to the REINFORCE algorithm reduces the variance

Question

A widely used variation of REINFORCE is to subtract a baseline value $b$ from the return $G_t$ to reduce the variance of gradient estimation, such that

\begin{align} \nabla_\theta J(\theta) & \propto \sum_s d(s|\pi_\theta) \sum_a (q_\pi(s,a)-b(s)) \nabla_\theta \pi(a|s,\theta) \\ \end{align}

I haven't found any proof that the baseline reduces the variance of the gradient estimation, is there one?

Answer 1

I do not know any mathematical proof but this explanation may help:

Let's say all of our rewards are positive. Using this formula you wrote above without baseline function boosts the probability of all actions, because we are always multiplying the log probabilities with some positive rewards. This causes to reduce variance and that's why we want to boost the probability of actions better than the average.