Answers.Body: <p>What you did is incorrect and that's not what authors got either (if you're refering to the equation above equation (5) in paper &quot;Non-parametric Policy Search with Limited Information Loss&quot;)</p>
  <p>What you need here is the derivative of a functional. Functional has a general form
  <span class="math-container">\begin{equation}
  J(f) = \int_x L(x, f(x), f'(x), \ldots, f^{(n)}(x)) dx
  \end{equation}</span></p>
  <p>Derivative with respect to <span class="math-container">$f$</span> is
  <span class="math-container">\begin{equation}
  \frac{\partial J}{\partial f} =  \frac{\partial L}{\partial f} - \frac{d}{dx}\frac{\partial L}{\partial f'} + \ldots
  \end{equation}</span></p>
  <p>Since your functional (expectation) is only dependant on <span class="math-container">$f$</span> then it simplifies to <span class="math-container">$\frac{\partial J}{\partial f} =  \frac{\partial L}{\partial f}$</span></p>
  <p>So what you have for example for the first term is
  <span class="math-container">\begin{equation}
  \frac{\partial \int_x H(x) \pi(x|\theta) dx}{\partial \pi(x|\theta)} = \frac{\partial H(x) \pi(x|\theta)}{\partial \pi(x|\theta)} = H(x)
  \end{equation}</span></p>
  <p>The more interesting functional is the one with term <span class="math-container">$\pi(x|\theta)\log(\frac{\pi(x|\theta)}{\pi(x|\hat \theta)})$</span>.
  Integral with respect to <span class="math-container">$\pi(x|\theta)$</span> is
  <span class="math-container">\begin{equation}
  \log(\frac{\pi(x|\theta)}{\pi(x|\hat \theta)}) + 1
  \end{equation}</span></p>
  <p>So in the end you get
  <span class="math-container">\begin{equation}
  \frac{\partial L}{\partial \pi(x|\theta)} = H(x) - \lambda - \eta \log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})} - \eta
  \end{equation}</span></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-02T17:51:49.373Z
Answers.Text: thanks for pointing that out, I will try to derive it until I get the dual. I think my confusion arises from not knowing/understanding the functional derivative.
Answers.UserDisplayName: Sanyou
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-02T09:45:50.413Z
Answers.LastActivityDate: 2022-01-03T10:51:45.577Z
Answers.LastEditDate: 2022-01-03T10:51:45.577Z
Answers.UserDisplayName: Brale
Body: <p>TL:DR, (Why) is one of the terms in the expectation not derived properly?</p>
  <p>Relative entropy policy search or REPS is used to optimize a policy in an MDP. The update step is limited in the policy space (?) by the KL-divergence metric to stabilize the update. Based on the KL-divergence constraints, and some constraints about the definition of a policy, we can derive its Lagrangian, and its dual optimization problem afterwards. And lastly, we find the appropriate update step (delta) by solving the dual problem.</p>
  <p>However, I think we can also use it to find multiple optimal solutions in an optimization problem, just like (CMA)-evolutionary strategy algorithm.</p>
  <p>So, based on the original <a href="https://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1851/2264" rel="nofollow noreferrer">paper</a> and a section of REPS in this <a href="https://jmlr.org/papers/v18/16-142.html" rel="nofollow noreferrer">paper</a>, I'm trying to derive the dual problem.</p>
  <p>Suppose that we're finding set of solutions represented as a parametrized distribution <span class="math-container">$\pi(x|\theta)$</span> that maximizes <span class="math-container">$H(x)$</span>. Suppose that the last parameters we came up with is denoted as <span class="math-container">$\hat{\theta}$</span>, we find the optimal parameters <span class="math-container">$\theta$</span> by:</p>
  <blockquote>
  <p>max <span class="math-container">$\int_x H(x)\pi(x|\theta) dx$</span></p>
  </blockquote>
  <blockquote>
  <p>s.t.  <span class="math-container">$\int_x \pi(x|\theta) dx = 1$</span></p>
  </blockquote>
  <blockquote>
  <p><span class="math-container">$D_\text{KL}\left(\pi(.|\theta) || \pi(.|\hat{\theta})\right) \leq \epsilon $</span></p>
  </blockquote>
  <blockquote>
  <p>with <span class="math-container">$D_\text{KL}\left(\pi(.|\theta) || \pi(.|\hat{\theta})\right) = \int_x \pi(x|\theta)\log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})}$</span></p>
  </blockquote>
  <p>Based on the equations above, we can write the Lagrangian as follows:</p>
  <blockquote>
  <p><span class="math-container">$L(\theta, \lambda, \eta) = \int_x H(x)\pi(x|\theta) dx + 
  \lambda(1-\int_x \pi(x|\theta) dx) + 
  \eta(\epsilon-\int_x \pi(x|\theta)\log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})})$</span></p>
  </blockquote>
  <p>Now, we can see that the term <span class="math-container">$\lambda(1-\int_x \pi(x|\theta) dx)$</span> is <span class="math-container">$0$</span>, right? But <a href="https://jmlr.org/papers/v18/16-142.html" rel="nofollow noreferrer">here</a>, it was not cancelled out. So, following the flow based on the two papers, We can simplify the Lagrangian by treating the integral wrt to <span class="math-container">$x$</span> as an expectation.</p>
  <blockquote>
  <p><span class="math-container">$L(\theta, \lambda, \eta) = \lambda + \eta\epsilon + \underset{\pi(x|\theta)}{\mathbb{E}}\left[H(x) -\lambda -\eta \log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})} \right]$</span></p>
  </blockquote>
  <p>We will find the optimal <span class="math-container">$\pi(x|\theta)$</span> by solving <span class="math-container">$\frac{\partial L}{\partial \pi(x|\theta)} = 0$</span>. Now, I got confused starting from this step.
  If I mindlessly copy/follow the notations from <a href="https://jmlr.org/papers/v18/16-142.html" rel="nofollow noreferrer">here</a>, the derivative of <span class="math-container">$L$</span> wrt the policy parametrized by <span class="math-container">$\theta$</span> is:</p>
  <blockquote>
  <p><span class="math-container">$\frac{\partial L}{\partial \pi(x|\theta)} = H(x) - \lambda - \eta \log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta}}$</span></p>
  </blockquote>
  <p>Where's the integral wrt <span class="math-container">$x$</span> goes? Is it because they are all multiplied by <span class="math-container">$\pi(x|\theta)$</span>, so that it can cancel the integral/the expectation? If so, then why the derivative of the KL term in the expectation derived into this <span class="math-container">$\eta \log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})}$</span>? Isn't the <span class="math-container">$\pi(x|\theta)$</span> in the log will derive something more?</p>
  
Tags: <reinforcement-learning><math><policy-based-methods>
Title: How to derive the dual function step by step in relative entropy policy search (REPS)?
UserDisplayName: Sanyou
ThreadText: # How to derive the dual function step by step in relative entropy policy search (REPS)?
  
  (Asked by: username_0 on 2021-12-30)
  
  TL:DR, (Why) is one of the terms in the expectation not derived properly?
  
  Relative entropy policy search or REPS is used to optimize a policy in an MDP. The update step is limited in the policy space (?) by the KL-divergence metric to stabilize the update. Based on the KL-divergence constraints, and some constraints about the definition of a policy, we can derive its Lagrangian, and its dual optimization problem afterwards. And lastly, we find the appropriate update step (delta) by solving the dual problem.
  
  However, I think we can also use it to find multiple optimal solutions in an optimization problem, just like (CMA)-evolutionary strategy algorithm.
  
  So, based on the original [paper](https://www.aaai.org/ocs/index.php/AAAI/AAAI10/paper/viewFile/1851/2264) and a section of REPS in this [paper](https://jmlr.org/papers/v18/16-142.html), I'm trying to derive the dual problem.
  
  Suppose that we're finding set of solutions represented as a parametrized distribution $\pi(x|\theta)$ that maximizes $H(x)$. Suppose that the last parameters we came up with is denoted as $\hat{\theta}$, we find the optimal parameters $\theta$ by:
  
  > max $\int\_x H(x)\pi(x|\theta) dx$
  
  > s.t. $\int\_x \pi(x|\theta) dx = 1$
  
  > $D\_\text{KL}\left(\pi(.|\theta) || \pi(.|\hat{\theta})\right) \leq \epsilon $
  
  > with $D\_\text{KL}\left(\pi(.|\theta) || \pi(.|\hat{\theta})\right) = \int\_x \pi(x|\theta)\log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})}$
  
  Based on the equations above, we can write the Lagrangian as follows:
  
  > $L(\theta, \lambda, \eta) = \int\_x H(x)\pi(x|\theta) dx +
  > \lambda(1-\int\_x \pi(x|\theta) dx) +
  > \eta(\epsilon-\int\_x \pi(x|\theta)\log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})})$
  
  Now, we can see that the term $\lambda(1-\int\_x \pi(x|\theta) dx)$ is $0$, right? But [here](https://jmlr.org/papers/v18/16-142.html), it was not cancelled out. So, following the flow based on the two papers, We can simplify the Lagrangian by treating the integral wrt to $x$ as an expectation.
  
  > $L(\theta, \lambda, \eta) = \lambda + \eta\epsilon + \underset{\pi(x|\theta)}{\mathbb{E}}\left[H(x) -\lambda -\eta \log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})} \right]$
  
  We will find the optimal $\pi(x|\theta)$ by solving $\frac{\partial L}{\partial \pi(x|\theta)} = 0$. Now, I got confused starting from this step.
  If I mindlessly copy/follow the notations from [here](https://jmlr.org/papers/v18/16-142.html), the derivative of $L$ wrt the policy parametrized by $\theta$ is:
  
  > $\frac{\partial L}{\partial \pi(x|\theta)} = H(x) - \lambda - \eta \log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta}}$
  
  Where's the integral wrt $x$ goes? Is it because they are all multiplied by $\pi(x|\theta)$, so that it can cancel the integral/the expectation? If so, then why the derivative of the KL term in the expectation derived into this $\eta \log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})}$? Isn't the $\pi(x|\theta)$ in the log will derive something more?
  
  **Tags:** reinforcement-learning, math, policy-based-methods
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2022-01-02. Score: 1 | Accepted answer
  
  What you did is incorrect and that's not what authors got either (if you're refering to the equation above equation (5) in paper "Non-parametric Policy Search with Limited Information Loss")
  
  What you need here is the derivative of a functional. Functional has a general form
  \begin{equation}
  J(f) = \int\_x L(x, f(x), f'(x), \ldots, f^{(n)}(x)) dx
  \end{equation}
  
  Derivative with respect to $f$ is
  \begin{equation}
  \frac{\partial J}{\partial f} = \frac{\partial L}{\partial f} - \frac{d}{dx}\frac{\partial L}{\partial f'} + \ldots
  \end{equation}
  
  Since your functional (expectation) is only dependant on $f$ then it simplifies to $\frac{\partial J}{\partial f} = \frac{\partial L}{\partial f}$
  
  So what you have for example for the first term is
  \begin{equation}
  \frac{\partial \int\_x H(x) \pi(x|\theta) dx}{\partial \pi(x|\theta)} = \frac{\partial H(x) \pi(x|\theta)}{\partial \pi(x|\theta)} = H(x)
  \end{equation}
  
  The more interesting functional is the one with term $\pi(x|\theta)\log(\frac{\pi(x|\theta)}{\pi(x|\hat \theta)})$.
  Integral with respect to $\pi(x|\theta)$ is
  \begin{equation}
  \log(\frac{\pi(x|\theta)}{\pi(x|\hat \theta)}) + 1
  \end{equation}
  
  So in the end you get
  \begin{equation}
  \frac{\partial L}{\partial \pi(x|\theta)} = H(x) - \lambda - \eta \log\frac{\pi(x|\theta)}{\pi(x|\hat{\theta})} - \eta
  \end{equation}
  
  > **Comments:**
  > **username_0**: thanks for pointing that out, I will try to derive it until I get the dual. I think my confusion arises from not knowing/understanding the functional derivative.  
  
  ---
  
  