Policy Gradients, Log Trick, Expectations, Softmax Policy In so-called "policy based" game playing algoritms (reinforcement learning in particular), there is a policy function $\pi_\theta(s,a)$ that gives the probability of action given state of the game and hidden parameter $\theta$, as shown in pg. 16 of lecture notes below.
http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/pg.pdf
In order to improve the score (let me drop the underscript $\theta$ from now on), instead of $\nabla \pi$ one usually tries to compute $\nabla \log \pi(s,a)$ based on this trick
$$ 
\nabla \pi(s,a) = \pi(s,a) \frac{\nabla \pi(s,a)}{\pi(s,a)}
$$
$$
= \pi(s,a)\nabla \log \pi(s,a)
$$
Now the author above calls $\nabla \log \pi(s,a)$ the score function and claims "he can compute it easier because the expectation of it is easy". As an example he picks softmax as $\pi$ which is,
$$
\pi(s,a) \propto e^{\phi(s,a)^T\theta}
$$
and jumps to score function
$$
\nabla \log \pi(s,a) = \phi(s,a) - E[\phi(s,\cdot)]
$$
I don't understand how the derivation could reach this statement. 
After some laboring, I have
$h(s,a,\theta) = \phi(s,a)^T\theta$
$$ 
\pi_\theta(s,a) = \frac{e^{h(s,a,\theta)}}{\sum_b e^{h(s,b,\theta)} }
$$
The gradient of the log 
$$ 
\nabla_\theta \log \pi_\theta = 
\nabla_\theta \log \frac{e^{h(s,a,\theta)}}{\sum_b e^{h(s,b,\theta)} }
$$
$$ = \nabla_\theta \big[ \log e^{h(s,a,\theta)} - \log \sum_b e^{h(s,b,\theta)}\big]$$
because 
$$ \log(\frac{x}{y}) = \log x - \log y $$
We continue
$$ = \nabla_\theta \big[ h(s,a,\theta) - \log \sum_b e^{h(s,b,\theta)} \big]$$
$$ 
= \phi(s,a) - \sum_b h(s,b,\theta)\frac{e^{h(s,b,\theta)}}{\sum_b e^{h(s,b,\theta)}} 
$$
$$ 
= \phi(s,a) - \sum_b h(s,b,\theta) \pi_\theta(b,s)
$$
The last term can be seen as expectation. Would this work? I am not sure of that last derivative of log of sum.  
 A: There is a small error in the second to last step:
$\nabla_\theta [ h(a,s,\theta) - log \sum_b h(b,s,\theta) \frac{\exp(h(b,s,\theta)}{\sum_b \exp(h(b,s,\theta))}]$
$\phi(a,s) - \nabla_\theta log \sum_b h(b,s,\theta) \frac{\exp(h(b,s,\theta)}{\sum_b \exp(h(b,s,\theta))}$
$\nabla_\theta \log(\sum_b \exp(h(b,s,\theta))) = \frac{\nabla_\theta \sum_b \exp(h(b,s,\theta))}{\sum_b \exp(h(b,s,\theta))} = \frac{\sum_b \exp(h(b,s,\theta))\hspace{0.2cm} \nabla_\theta [h(b,s,\theta)]}{\sum_b \exp(h(b,s,\theta))}$
(chain rule twice!)
Which gives:
$\phi(a,s) - \sum_b \frac{\exp(h(b,s,\theta)}{\sum_b \exp(h(b,s,\theta))}\hspace{0.2cm}\phi(b,s) $
$\phi(a,s) - \mathbb{E}_{b\sim \pi} \phi(b,s)$
A: If I understand correctly, the derivation is straight-forward and you just start with
$$
\nabla \log \pi(s,a) = \frac{\nabla \pi(s,a)}{\pi(s,a)} = \phi(s,a) + \theta
$$
and the $\theta$ should correspond to the expectation. Of course I am using the fact $\pi(s,a) \propto e^{-\phi(s,a)^{T}\theta}$. And the operator $\nabla$ is a total differentiation.
A: Dr. Silver graciously responded and forwarded the paper Monte-Carlo Simulation Balancing, found at
http://www.machinelearning.org/archive/icml2009/papers/500.pdf
There is a derivation there, looks similar to what I did.
