Reinforce
Reinforce is a policy-based method, but instead of obtaining policy from Q-states or values, it parameterizes the policy \(\pi:\mathcal{S}\mapsto\mathbb{P}(\mathcal{A})\) that outputs a distribution of actions and trains the policy through gradients.
Table of Contents
1. Introduction of REINFORCE
In policy-gradient methods, we directly learn to approximate \(\pi^{\ast}\). The idea is to parameterize it, say a neural network, and it will output a distribution over actions, i.e., stochastic policy. Our objective is to maximize the performance of the parameterize policy using gradient ascent. To do that, we define an objective function \(J(\theta)\), expected cumulative reward, and we want to find the value \(\theta\) that maximizes it.
2. Derivation of Objective Function
Any trajectory can be expressed as
\[ \tau = (s_{0},a_{0},r_{0},s_{1},a_{1},r_{1},\dots,s_{T}) \]
Therefore, the probability of a certain trajectory \(\tau\) given policy \(\theta\) is
\[ \mathbb{P}(\tau;\theta) = \mathbb{P}(s_{0})\prod_{t=0}^{T-1} \pi_{\theta}(a_{t}|s_{t}) \mathbb{P}(s_{t+1}|s_{t},a_{t}) \]
Remember, the policy \(\pi_{\theta}\) is stochastic, and it outputs a distribution over actions.
Then, the objective function \(J(\theta)\) is the expected reward of trajectories, that is
\[ J(\theta) = \mathbb{E}_{\tau\sim\pi_{\theta}}[R(\tau)] = \sum_{\tau} \mathbb{P}(\tau;\theta)R(\tau) \]
where \(R(\tau)=\sum_{t=0}^{T} \gamma^{t}r_{t}\) is the discounted cumulative reward.
3. The Gradient
As we know the objective function, all we need to do is gradient ascent:
\[ \theta \gets \theta + \alpha \times \nabla J(\theta) \]
But the problem is, how to compute the derivative of \(J(\theta)\)?
- Since by definition, we have to sum over all possible trajectories, which is computationally unacceptable.
- By definition, we also need to compute the derivative of world dynamics \(\mathbb{P}(s_{t+1}|a_{t},s_{t})\) over \(\theta\), which is intractable.
Thankfully, we have a theorem to reformulate the objective function to a differentiable function, that does not involve the differentiation of the state distribution.
3.1. Decoupling World Dynamics from Gradients through Log Tricks
The Policy Gradient Theorem
\begin{equation} \nabla_{\theta}J(\theta) = \mathbb{E}_{\pi_{\theta}}\left[ \sum_{t} \nabla_{\theta}\log \pi_{\theta}(a_{t}|s_{t})R(\tau) \right] \end{equation}To prove it,
4. The REINFORCE Algorithm
Now, we can apply the Monte-Carlo trick. We sample \(m\) trajectories, for each of which, we compute their \(\sum_{t} \nabla_{\theta}\log \pi_{\theta}(a_{t}|s_{t})R(\tau)\), that is to say,
\[ \nabla_{\theta}J(\theta) \approx \hat{g} = \frac{1}{m} \sum_{i=1}^{m} \sum_{t=0} \nabla_{\theta} \log \pi_{\theta}(a_{t}^{(i)}|s_{t}^{(i)})R(\tau^{(i)}) \]
However, in practice, to eliminate the effect of the past, the full cumulative reward \(R(\tau^{(i)})\) is often replaced by reward starting from the current step \(\sum_{t'=t}^{T} R(s_{t'}, a_{t'}, s_{t'+1})\), a.k.a. reward-to-go from that point.
\[ \nabla_{\theta} J(\theta) = \boxed{\mathbb{E}_{\tau\sim\pi_{\theta}} \left[ \sum_{t=0}^{T} \nabla_{\theta} \log \pi_{\theta}(a_{t}|s_{t}) \sum_{t'=t}^{T} R(s_{t'}, a_{t'}, s_{t'+1}) \right] } \]
4.1. Variance Reduction
Intuitively, if in an environment, all rewards are positive. Then, almost every action will have its probability increased. This could cause (1) slower convergence; (2) higher variance, since the scale of \(G_{t}\) could largely affect the scale of gradient.
Therefore, in practice, in order to lower the variance without changing the expectation, we usually have a baseline \(b(s_{t})\), usually approximated by value function \(V(s_{t})\):
\[ \theta \gets \theta + \alpha \cdot \nabla_{\theta}\log \pi_{\theta}(a_{t}|s_{t}) \cdot (G_{t} - b(s_{t})) \]
This is the variance reduction trick. We can prove this only lowers the variance and unbiased.