Answers.Body: <p>Calculation of gradient
  <span class="math-container">\begin{align}
  \nabla_{\theta} \log(\pi_{\theta}(a|s)) &amp;= \phi(s,a) - \mathbb E[\phi (s, \cdot)]\\
  &amp;= \phi(s,a) - \sum_{a'} \pi(a'|s) \phi(s,a')
  \end{align}</span>
  is only valid for linear function approximation with action preferences of form
  <span class="math-container">\begin{equation}
  h(s, a, \theta) = \theta^T \phi(s,a)
  \end{equation}</span>
  and softmax policy
  <span class="math-container">\begin{equation}
  \pi(a|s) = \frac{e^{h(s,a,\theta)}}{\sum_{a'} e^{h(s,a',\theta)}}
  \end{equation}</span>
  The gradient would be calculated as it is written. For example, if your current state is <span class="math-container">$s = (1, 1)$</span> and in that state you have actions <span class="math-container">$a_0 = 0$</span> and <span class="math-container">$a_1 = 1$</span> and probabilities for those actions are <span class="math-container">$\pi(a_0|s) = 0.7$</span>, <span class="math-container">$\pi(a_1|s) = 0.3$</span> then gradient for action <span class="math-container">$a_0$</span> would be
  <span class="math-container">\begin{equation}
  \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
  \end{equation}</span>
  Feature vector <span class="math-container">$\phi$</span> 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.  </p>
  
  <p>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
  <span class="math-container">\begin{equation}
  J_\theta = \sum_t \log(\pi(a_t|s_t, \theta)) G_t
  \end{equation}</span>
  and software will automatically calculate gradient <span class="math-container">$\nabla J_{\theta}$</span> and update weights.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-06T08:23:35.207Z
Answers.Text: 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.
Answers.UserDisplayName: Gregor
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-05T21:27:55.147Z
Answers.LastActivityDate: 2019-12-05T22:20:03.893Z
Answers.LastEditDate: 2019-12-05T22:20:03.893Z
Answers.UserDisplayName: Brale
Body: <p>There is this nice result for policy gradients that the gradient of some performance measure, <span class="math-container">$\nabla v_{\pi_{\theta}}(s_0)$</span> (here, in the episodic case for the starting state <span class="math-container">$s_0$</span> and policy <span class="math-container">$\pi$</span>, parametrised by some weights <span class="math-container">$\theta$</span>) is equal to the expectation gradient of the logarithm of the policy, i.e.</p>
  
  <p><span class="math-container">$$\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{]},$$</span></p>
  
  <p>where <span class="math-container">$G_t$</span> is the discounted future reward from state <span class="math-container">$s_t$</span> onward and <span class="math-container">$s_T$</span> the final state of some trajectory <span class="math-container">$(s_0, a_0, s_1, a_1, ..., s_{T-1}, a_{T-1}, s_T)$</span>.</p>
  
  <p>Now, when using a softmax policy, <span class="math-container">$\nabla_\theta\log(\pi_{\theta}(a_t|s_t)$</span> can be written as</p>
  
  <p><span class="math-container">$$\nabla_\theta\log(\pi_{\theta}(a_t|s_t))=\phi(s_t,a_t)-\mathbb{E}[\phi(s_t,\cdot)],$$</span></p>
  
  <p>where <span class="math-container">$\phi(s,a)$</span> is some input vector of a state-action tuple.</p>
  
  <p>However: <strong>what exactly is this vector?</strong> 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. <span class="math-container">$(14, 15, 11, 17)^T$</span> for four possible actions. The softmax-function now scales these outputs, which results in the logits <span class="math-container">$(.042, .114, .002, .842)^T$</span> in this example.</p>
  
  <p>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. <span class="math-container">$\phi(s)=(1, 0, 0, 1)^T$</span>, and multiply that with my weight matrix <span class="math-container">$\theta$</span> (and add biases b), i.e. <span class="math-container">$\theta\phi(s)+b$</span>. So, continuing above example, <span class="math-container">$1\cdot \theta_{1,1} + 0\cdot \theta_{1,2} + 0\cdot \theta_{1,3} + 1\cdot \theta_{1,4} = 14$</span> and <span class="math-container">$1\cdot \theta_{2,1} + 0\cdot \theta_{2,2} + 0\cdot \theta_{2,3} + 1\cdot \theta_{2,4} = 15$</span>.</p>
  
  <p>But what is <span class="math-container">$\phi(s,a)$</span> here? And how would I compute <span class="math-container">$\nabla_\theta\log(\pi_{\theta}(a|s))=\phi(s,a)-\mathbb{E}[\phi(s,\cdot)]$</span>?</p>
  
Tags: <machine-learning><gradient-descent><policy-gradients><softmax-policy>
Title: Eligibility vector for softmax policy with policy gradients
UserDisplayName: Gregor
ThreadText: # Eligibility vector for softmax policy with policy gradients
  
  (Asked by: username_0 on 2019-12-05)
  
  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)]$?
  
  **Tags:** machine-learning, gradient-descent, policy-gradients, softmax-policy
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-12-05. Score: 5 | Accepted answer
  
  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
  \begin{equation}
  h(s, a, \theta) = \theta^T \phi(s,a)
  \end{equation}
  and softmax policy
  \begin{equation}
  \pi(a|s) = \frac{e^{h(s,a,\theta)}}{\sum\_{a'} e^{h(s,a',\theta)}}
  \end{equation}
  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
  \begin{equation}
  \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
  \end{equation}
  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
  \begin{equation}
  J\_\theta = \sum\_t \log(\pi(a\_t|s\_t, \theta)) G\_t
  \end{equation}
  and software will automatically calculate gradient $\nabla J\_{\theta}$ and update weights.
  
  > **Comments:**
  > **username_0**: 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.  
  
  ---
  
  