How do I derive the gradient with respect to the parameters of the softmax policy?
Softmax policy $\pi_\theta(s,a)$ is defined as $\frac{\exp{(\phi(s,a)^T \theta})}{\Sigma \exp{(\phi(s,a) ^T \theta) }}$, where the summation is over the action space.
Taking log, this becomes
$$
\log \pi_\theta(s,a) = log(e^{\phi(s,a) ^T \theta}) - log({\Sigma e^{\phi(s,a) ^T \theta }}) \\
= \phi(s,a) ^T \theta - log({\Sigma e^{\phi(s,a)^T \theta }})
$$

Taking derivative wrt $\theta$, this becomes
$$
\nabla_\theta \log \pi_\theta(s,a) = \phi(s,a) - \nabla_\theta log({\Sigma e^{\phi(s,a) ^T \theta }})
$$

We can rewrite $\nabla_\theta log({\Sigma e^{\phi(s,a)^T \theta }})$ as follows.
$$
\nabla_\theta log({\Sigma e^{\phi(s,a)^T \theta }}) 
= \frac{\nabla_\theta \Sigma e^{\phi(s,a)^T \theta}}{\Sigma e^{\phi(s,a) ^T \theta}} 
= \frac{\Sigma \phi(s,a) e^{\phi(s,a) ^T \theta}}{\Sigma e^{\phi(s,a) ^T \theta}}
= \Sigma \phi(s,a) \pi_\theta(s,a)
$$ 

The final equation then becomes
$$
\nabla_\theta \log \pi_\theta(s,a) = \phi(s,a) - \Sigma \phi(s,a) \pi_\theta(s,a)
$$