# Eligibility vector for softmax policy with policy gradients

There is this nice result for policy gradients that the gradient of some performance measure, $$\nabla v_{\pi_{\theta}}(s_0)$$ (here, in the episodic case for the starting state $$s_0$$ and policy $$\pi$$, parametrised by some weights $$\theta$$) is equal to the expectation gradient of the logarithm of the policy, i.e.

$$\nabla v_{\pi_{\theta}}(s_0)=\mathbb{E}\Big{[}\sum_{t=0}^{T-1}\nabla_\theta\log(\pi_{\theta}(a_t|s_t)]\cdot G_t\Big{]},$$

where $$G_t$$ is the discounted future reward from state $$s_t$$ onward and $$s_T$$ the final state of some trajectory $$(s_0, a_0, s_1, a_1, ..., s_{T-1}, a_{T-1}, s_T)$$.

Now, when using a softmax policy, $$\nabla_\theta\log(\pi_{\theta}(a_t|s_t)$$ can be written as

$$\nabla_\theta\log(\pi_{\theta}(a_t|s_t))=\phi(s_t,a_t)-\mathbb{E}[\phi(s_t,\cdot)],$$

where $$\phi(s,a)$$ is some input vector of a state-action tuple.

However: what exactly is this vector? A typical input with policy gradients (for example in a neural network) is a feature vector for the state and the output a vector with dimensions equal to the number of actions, e.g. $$(14, 15, 11, 17)^T$$ for four possible actions. The softmax-function now scales these outputs, which results in the logits $$(.042, .114, .002, .842)^T$$ in this example.

What I would usually do in neural networks is take some input vector, for example something that describes if there are borders in a grid world, e.g. $$\phi(s)=(1, 0, 0, 1)^T$$, and multiply that with my weight matrix $$\theta$$ (and add biases b), i.e. $$\theta\phi(s)+b$$. So, continuing above example, $$1\cdot \theta_{1,1} + 0\cdot \theta_{1,2} + 0\cdot \theta_{1,3} + 1\cdot \theta_{1,4} = 14$$ and $$1\cdot \theta_{2,1} + 0\cdot \theta_{2,2} + 0\cdot \theta_{2,3} + 1\cdot \theta_{2,4} = 15$$.

But what is $$\phi(s,a)$$ here? And how would I compute $$\nabla_\theta\log(\pi_{\theta}(a|s))=\phi(s,a)-\mathbb{E}[\phi(s,\cdot)]$$?

Calculation of gradient \begin{align} \nabla_{\theta} \log(\pi_{\theta}(a|s)) &= \phi(s,a) - \mathbb E[\phi (s, \cdot)]\\ &= \phi(s,a) - \sum_{a'} \pi(a'|s) \phi(s,a') \end{align} is only valid for linear function approximation with action preferences of form $$$$h(s, a, \theta) = \theta^T \phi(s,a)$$$$ and softmax policy $$$$\pi(a|s) = \frac{e^{h(s,a,\theta)}}{\sum_{a'} e^{h(s,a',\theta)}}$$$$ The gradient would be calculated as it is written. For example, if your current state is $$s = (1, 1)$$ and in that state you have actions $$a_0 = 0$$ and $$a_1 = 1$$ and probabilities for those actions are $$\pi(a_0|s) = 0.7$$, $$\pi(a_1|s) = 0.3$$ then gradient for action $$a_0$$ would be $$$$\nabla_{\theta} \log(\pi_{\theta}(a_0|s)) = (1, 1, 0)^T - (0.7 \cdot (1, 1, 0)^T + 0.3\cdot (1,1,1)^T) = (0, 0, -0.3)^T$$$$ Feature vector $$\phi$$ can be basically anything you want. For example you could stack state feature and action (like I did in small example), you could use polynomials, radial basis functions, tile coding, etc.
If you're using multilayered neural network you would have to propagate gradients through all layers, usually done with backpropagation algorithm. Easiest way is to use automatic differentiation software (e.g. Tensorflow) which can do that for you so you don't have to write your implementation. All you have to do is define your objective function that you want to optimize $$$$J_\theta = \sum_t \log(\pi(a_t|s_t, \theta)) G_t$$$$ and software will automatically calculate gradient $$\nabla J_{\theta}$$ and update weights.
• Thanks a lot! Just for the sake of completion I wanted to add the "likelihood ratios trick", i.e. $\nabla_\theta \log{\pi_\theta (a|s)}=\frac{\nabla_\theta \pi_\theta (a|s)}{\pi_\theta (a|s)}$, that could be used to derive the gradient of the log by hand. – Gregor Dec 6 '19 at 8:23