REINFORCE with Baseline

Definition

REINFORCE with Baseline algorithm is a variant of the REINFORCE algorithm that helps reduce variance in Policy Gradient methods by adopting Actor-Critic Method. It modifies the objective function of the REINFORCE algorithm by subtracting a baseline from the returns, which helps reduce the variance of the gradient without introducing bias. ${\nabla }_{\theta }J(\theta )={\nabla }_{\theta }{E}_{{\pi }_{\theta }}[r(\tau )]=E_{{\pi }_{\theta }}\left[{\sum }_{t=0}^{T-1}(G_t-b(s_t)){\nabla }_{\theta }\ln {\pi }_{\theta }(a_t|s_t)\right]$ where $b(s_t)$ is a baseline function not related to $a_t$ (commonly chosen as a State-Value Function $V(s)=E_{{\pi }_{\theta }}[G_t|S_t=s]$).

Actor (Policy Gradient Update)

$\Delta \theta =\alpha (G_t-V(s_t;\varphi )){\nabla }_{\theta }\ln {\pi }_{\theta }(a_t|s_t)$

Critic (Value Network Update)

$\Delta \varphi =\beta (G_t-V(s_t;\varphi )){\nabla }_{\varphi }V(s_t;\varphi )$

Algorithm

1. Initialize state-value $V(s;\varphi )$ and policy $\pi (a|s;\theta )$ networks randomly.
2. Set the hyperparameters: step-sizes $\alpha ,\beta >0$, and discount factor $0<\gamma \le 1$
3. Repeat for each episode (Each starts from a state $s$ under the policy ${\pi }_{\theta }$):
   1. Repeat for each step of an episode until terminal, $t=0,1,\dots ,T-1$ :
      1. $\delta \leftarrow G_t-V(s_t;\varphi )$
      2. $\varphi \leftarrow \varphi +\beta \delta {\nabla }_{\varphi }V(s_t;\varphi )$ (minimize $L(\varphi )=E_{\pi }[{\sum }_{t=0}^{T-1}(G_t-V(s_t;\varphi ){)}^2]$)
      3. $\theta \leftarrow \theta +\alpha {\gamma }^t\delta {\nabla }_{\theta }\ln \pi (a_t|s_t;\theta )$ (maximize $J(\theta )$ with the Policy Gradient ${\nabla }_{\theta }J(\theta )=E_{{\pi }_{\theta }}\left[{\sum }_{t=0}^{T-1}(G_t-V(s_t;\varphi )){\nabla }_{\theta }\ln {\pi }_{\theta }(a_t|s_t)\right]$)