Answers.Body: <p>Using the related question and simplifying notation</p>
  <p><span class="math-container">$$\begin{align} E_{\mu,\pi}[E_{\mathcal{E}}[s'|s,a]^2] &amp;= \sum_\limits{s,a}\left(\sum_\limits{s'}s'p(s'|s,a)\right)^2p(s,a) \\
  &amp;=\sum_\limits{s,a}\left(\sum_\limits{s_1'}s_1'p(s'_1|s,a)\cdot\sum_\limits{s_2'}s_2'p(s'_2|s,a)\right)p(s,a) \\
  &amp;= \sum_\limits{s,a,s_1',s_2'}s_1's_2'p(s_1'|s,a)p(s_2'|s,a)p(s,a) \\
  &amp;= E_{\mathcal{E}\sim (s_1',s_2'),\mu,\pi}[s_1'\cdot s_2']
  \end{align}$$</span></p>
  <p>This is the closest I could come up with, basically instead of the same sample squared, we pick two samples independently given the pair <span class="math-container">$(s,a)$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-03-08T11:34:14.813Z
Answers.LastActivityDate: 2021-03-08T13:04:59.463Z
Answers.LastEditDate: 2021-03-08T13:04:59.463Z
Answers.UserDisplayName: quest ions
Body: <p>Is the expression for the DQN cost function, <a href="https://www.cs.toronto.edu/%7Evmnih/docs/dqn.pdf#page=3" rel="nofollow noreferrer">Equation (2) of the DQN paper</a></p>
  <p><span class="math-container">$$\begin{align}L_1 &amp;= E_{\mu,\pi}\left[\left(y_i - q(s,a;\theta)\right)^2\right]\\
  &amp;=E_{\mu,\pi}\left[\left(E_{\mathcal{E}}[r + \gamma \max\limits_{a'}q(s',a';\theta^-)] - q(s,a;\theta)\right)^2\right] \end{align}$$</span></p>
  <p>equivalent to this? (Substituting the expression for <span class="math-container">$y_i$</span> defined in the paragraph directly after, <span class="math-container">$\mathcal{E}$</span> represents the transition distribution governed by the environment, <span class="math-container">$\pi$</span> represents the behaviour policy and <span class="math-container">$\mu$</span> represents the stationary distribution of states)</p>
  <p><span class="math-container">$$L_2 = E_{\mu,\pi,\mathcal{E}}\left[\left(r + \gamma \max\limits_{a'}q(s',a';\theta^-) - q(s,a;\theta)\right)^2\right]$$</span></p>
  <p><strong>Can the law of iterated expectation be used to derive the second expression from the first, if not, is there another way to go about showing their equivalence IF they are equivalent.</strong></p>
  <p>It seems as though <span class="math-container">$L_2$</span> is used for sampling but I'm not sure how it's possible to get here from the original cost function <span class="math-container">$L_1$</span>. If it is possible to use <span class="math-container">$L_2$</span> to sample I assume that means the two expressions must be equivalent. <a href="https://www.cs.toronto.edu/%7Evmnih/docs/dqn.pdf#page=5" rel="nofollow noreferrer">The second expression is used for sampling in the DQN paper here.</a></p>
  <p>I do realise that the gradient for each function is the same and thus so is the <span class="math-container">$n^{th}$</span> derivative for some <span class="math-container">$n\geq1$</span> and since the curvature and optimas align I guess that also means they are the same function (minus some constant difference)?</p>
  <p><span class="math-container">$$\nabla_{\theta} L = E_{\mu,\pi,\mathcal{E}}\left[\left(r + \gamma \max\limits_{a'}q(s',a';\theta^-) - q(s,a;\theta)\right)\nabla q(s,a;\theta)\right]$$</span></p>
  <hr />
  <p><strong>Related Question</strong></p>
  <p>A related problem that concerns equivalence of sampling from <span class="math-container">$L_1$</span> and <span class="math-container">$L_2$</span>. <em>Is it possible to sample from a nested expectation that is squared as follows?</em></p>
  <p><span class="math-container">$$E[E[X|Y]^2] \approx \frac{1}{n}\sum X^2$$</span></p>
  <p>Where <span class="math-container">$X$</span> is generated according to the marginalised distribution <span class="math-container">$P(X)$</span>. I don't think it is true  since <span class="math-container">$E[X]^2 \neq E[X^2]$</span> which should mean sampling from <span class="math-container">$L_1$</span> and <span class="math-container">$L_2$</span> are not equivalent.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-04T16:32:38.967Z
Comments.Text: what is $\mathcal{E}$?
Comments.UserDisplayName: David
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-05T11:37:40.553Z
Comments.Text: I don't see your first expression/formula anywhere in the DQN paper. Can you clarify this?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-05T11:39:17.123Z
Comments.Text: @nbro Equation (2) substitute y_i for the expression specified in the paragraph below
Comments.UserDisplayName: quest ions
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-05T11:44:30.060Z
Comments.Text: It's better you add this information to your post, i.e. how you get to your first expression given the expressions in the DQN paper.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-03-05T16:16:43.113Z
Comments.Text: The related question is just a simpler way of rephrasing what they do in the psuedocode of the DQN paper using the first form of the objective function described in the question. Fiddling around with the expected expression it's not obvious to me that this it's possible to sample in this way, which further highlights the discrepancy to me, between the sampling done in the pseudocode and objective function.
Comments.UserDisplayName: quest ions
Tags: <deep-learning><dqn><proofs>
Title: Can the law of iterated expectation be used on the inner expectation of the DQN cost function described in the DQN paper
UserDisplayName: quest ions
ThreadText: # Can the law of iterated expectation be used on the inner expectation of the DQN cost function described in the DQN paper
  
  (Asked by: username_0 on 2021-03-04)
  
  Is the expression for the DQN cost function, [Equation (2) of the DQN paper](https://www.cs.toronto.edu/%7Evmnih/docs/dqn.pdf#page=3)
  
  $$\begin{align}L\_1 &= E\_{\mu,\pi}\left[\left(y\_i - q(s,a;\theta)\right)^2\right]\\
  &=E\_{\mu,\pi}\left[\left(E\_{\mathcal{E}}[r + \gamma \max\limits\_{a'}q(s',a';\theta^-)] - q(s,a;\theta)\right)^2\right] \end{align}$$
  
  equivalent to this? (Substituting the expression for $y\_i$ defined in the paragraph directly after, $\mathcal{E}$ represents the transition distribution governed by the environment, $\pi$ represents the behaviour policy and $\mu$ represents the stationary distribution of states)
  
  $$L\_2 = E\_{\mu,\pi,\mathcal{E}}\left[\left(r + \gamma \max\limits\_{a'}q(s',a';\theta^-) - q(s,a;\theta)\right)^2\right]$$
  
  **Can the law of iterated expectation be used to derive the second expression from the first, if not, is there another way to go about showing their equivalence IF they are equivalent.**
  
  It seems as though $L\_2$ is used for sampling but I'm not sure how it's possible to get here from the original cost function $L\_1$. If it is possible to use $L\_2$ to sample I assume that means the two expressions must be equivalent. [The second expression is used for sampling in the DQN paper here.](https://www.cs.toronto.edu/%7Evmnih/docs/dqn.pdf#page=5)
  
  I do realise that the gradient for each function is the same and thus so is the $n^{th}$ derivative for some $n\geq1$ and since the curvature and optimas align I guess that also means they are the same function (minus some constant difference)?
  
  $$\nabla\_{\theta} L = E\_{\mu,\pi,\mathcal{E}}\left[\left(r + \gamma \max\limits\_{a'}q(s',a';\theta^-) - q(s,a;\theta)\right)\nabla q(s,a;\theta)\right]$$
  
  ---
  
  **Related Question**
  
  A related problem that concerns equivalence of sampling from $L\_1$ and $L\_2$. *Is it possible to sample from a nested expectation that is squared as follows?*
  
  $$E[E[X|Y]^2] \approx \frac{1}{n}\sum X^2$$
  
  Where $X$ is generated according to the marginalised distribution $P(X)$. I don't think it is true since $E[X]^2 \neq E[X^2]$ which should mean sampling from $L\_1$ and $L\_2$ are not equivalent.
  
  **Tags:** deep-learning, dqn, proofs
  > **Comments:**
  > **username_1**: what is $\mathcal{E}$?  
  > **username_2**: I don't see your first expression/formula anywhere in the DQN paper. Can you clarify this?  
  > **username_0**: @nbro Equation (2) substitute y_i for the expression specified in the paragraph below  
  > **username_2**: It's better you add this information to your post, i.e. how you get to your first expression given the expressions in the DQN paper.  
  > **username_0**: The related question is just a simpler way of rephrasing what they do in the psuedocode of the DQN paper using the first form of the objective function described in the question. Fiddling around with the expected expression it's not obvious to me that this it's possible to sample in this way, which further highlights the discrepancy to me, between the sampling done in the pseudocode and objective function.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_0 on 2021-03-08. Score: 0
  
  Using the related question and simplifying notation
  
  $$\begin{align} E\_{\mu,\pi}[E\_{\mathcal{E}}[s'|s,a]^2] &= \sum\_\limits{s,a}\left(\sum\_\limits{s'}s'p(s'|s,a)\right)^2p(s,a) \\
  &=\sum\_\limits{s,a}\left(\sum\_\limits{s\_1'}s\_1'p(s'\_1|s,a)\cdot\sum\_\limits{s\_2'}s\_2'p(s'\_2|s,a)\right)p(s,a) \\
  &= \sum\_\limits{s,a,s\_1',s\_2'}s\_1's\_2'p(s\_1'|s,a)p(s\_2'|s,a)p(s,a) \\
  &= E\_{\mathcal{E}\sim (s\_1',s\_2'),\mu,\pi}[s\_1'\cdot s\_2']
  \end{align}$$
  
  This is the closest I could come up with, basically instead of the same sample squared, we pick two samples independently given the pair $(s,a)$.
  
  
  ---
  
  