Answers.Body: <p>Just as the <a href="https://www.cs.toronto.edu/%7Evmnih/docs/dqn.pdf" rel="nofollow noreferrer">paper</a> says</p>
  <p><span class="math-container">$$L_i(\theta_i)= E_{(s,a)\sim p}[(y_i-Q(s,a;\theta_i))^2]$$</span></p>
  <p>where</p>
  <p><span class="math-container">$$y_i = E_{s' \sim \mathcal{E}}[r+\gamma \max_{a'}Q(s',a';\theta_{i+1})\mid s,a]$$</span></p>
  <p>Then in the <em>Background</em> section of the paper, it says</p>
  <blockquote>
  <p>Differentiating the loss function with respect to the weights we arrive at the following gradient:</p>
  </blockquote>
  <p><span class="math-container">$$\nabla_{\theta_i} L_i(\theta_i)\\= E_{(s,a)\sim p,s'\sim\mathcal{E}}\left[\left(r+\gamma \max_{a'}Q(s',a';\theta_{i+1})-Q(s,a;\theta_i)\right)\nabla_{\theta_i}Q(s,a;\theta_i)\right]\tag{1}$$</span></p>
  <blockquote>
  <p>Rather than computing the full expectations in the above gradient, it is often computationally expedient to optimize the loss function by <strong>stochastic gradient descent</strong>.</p>
  <p>...</p>
  <p>and the expectations <strong>are replaced by single samples</strong> from the behavior distribution <span class="math-container">$ρ$</span> and the emulator <span class="math-container">$\mathcal{E}$</span> respectively.</p>
  </blockquote>
  <p>If you're familiar with SGD and <a href="https://pdfs.semanticscholar.org/34dd/d8865569c2c32dec9bf7ffc817ff42faaa01.pdf" rel="nofollow noreferrer">Stochastic Optimization</a> then you know what happens here:</p>
  <p>The expression inside the expectation of (1), i.e. <span class="math-container">$\left(r+\gamma \max_{a'}Q(s',a';\theta_{i+1})-Q(s,a;\theta_i)\right)\nabla_{\theta_i}Q(s,a;\theta_i)$</span> , is an <a href="https://en.wikipedia.org/wiki/Bias_of_an_estimator" rel="nofollow noreferrer">unbiased estimation</a> of the real gradient <span class="math-container">$\nabla_{\theta_i}L_i(\theta_i)$</span> - its expectation is the real gradient. In other words,</p>
  <p><span class="math-container">$$\widehat{\nabla L}=\left(r+\gamma \max_{a'}Q(s',a';\theta_{i+1})-Q(s,a;\theta_i)\right)\nabla_{\theta_i}Q(s,a;\theta_i).$$</span></p>
  <p>Then by theory of Stochastic Optimization we can optimize <span class="math-container">$L$</span> by <span class="math-container">$\theta\leftarrow \theta - \alpha\widehat{\nabla L}$</span> , which is how SGD works.</p>
  <p>The unbiased estimation <span class="math-container">$\left(r+\gamma \max_{a'}Q(s',a';\theta_{i+1})-Q(s,a;\theta_i)\right)\nabla_{\theta_i}Q(s,a;\theta_i)$</span> can be sampled and calculated directly - you can run the emulator <span class="math-container">$\mathcal{E}$</span> and current behavior policy to collect <span class="math-container">$r, s', a'$</span> and calculate the gradient of your Q network <span class="math-container">$\nabla Q$</span> using TensorFlow. So the gradient to <span class="math-container">$L$</span> can be approximated.</p>
  <p>The <span class="math-container">$y_j$</span> in the pseudocode  of the paper is also an estimation. It'll be more proper to denote it as <span class="math-container">$\hat{y_j}$</span>.</p>
  <p>(I'm not an native English speaker so forgive my poor expression.)</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-28T02:12:06.960Z
Answers.Text: Welcome to AI SE! Thanks for contributing! This answer seems consistent with knowledge. Maybe you could spend more words on why that is an "unbiased estimator of the gradient" (maybe just link to a paper that shows that this an unbiased estimator of the gradient) and how this estimator is actually called. Furthermore, what do you mean by "which can be sampled and calculated directly", i.e. how can an estimator be sampled? Also, which pseudocode are you talking about where $\hat{y_j}$ is present?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-28T03:58:10.073Z
Answers.Text: Thank you for your feedback. I have tried to edit my post to make it more clear. My English writing skill is not so good.
Answers.UserDisplayName: Shuai
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-28T04:02:03.377Z
Answers.Text: Thanks for addressing my questions. Now your answer is clearer! And thanks again for contributing! I've already upvoted your answer. Feel free to stick around and contribute more :)
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-28T09:17:44.320Z
Answers.Text: Thanks for your contribution. I must admit that I haven't watched enough into stochastic gradient. As I understand it we try to find a zero of the gradient via the Robbins-Monro-Algorithm. In general, does that mean you have to check the prerequisites of Robbins-Monro before using stochastic gradient ? I think here they are satisfied.
Answers.UserDisplayName: Leroy Od
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-04-23T01:07:39.137Z
Answers.Text: I don't understand how it is an unbiased estimator, can someone elucidate?
Answers.UserDisplayName: r4bb1t
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-31T21:35:17.593Z
Answers.Text: Why is expectation in Loss function is with respect to (s,a)?  (s,a) is given.
Answers.UserDisplayName: DSPinfinity
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-28T01:33:27.630Z
Answers.LastActivityDate: 2020-02-28T03:53:54.283Z
Answers.LastEditDate: 2020-06-17T09:57:20.710Z
Answers.UserDisplayName: Shuai
Body: <p>In <a href="https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf" rel="nofollow noreferrer">Deep Q Learning</a> the parametrized Q-functions <span class="math-container">$Q_i$</span> are optimised by performing gradient descent on the series of loss functions </p>
  
  <p><span class="math-container">$L_i(\theta_i)= E_{(s,a)\sim p}[(y_i-Q(s,a;\theta_i))^2]$</span> , where </p>
  
  <p><span class="math-container">$y_i = E_{s' \sim \mathcal{E}}[r+\gamma \max_{a'}Q(s',a';\theta_{i+1})\mid s,a]$</span>.</p>
  
  <p>In the actual algorithm, however, the expected value is never computed. Also, I think it cannot be computed since the transition probabilities of the underlying MDP remain hidden from the agent. Instead of the expected value, we compute <span class="math-container">$y_i = r_i + \gamma \max_a Q(\phi_{i+1},a;\theta)$</span>. I assume some sort of stochastic approximation is taking place here. Can someone explain the details?</p>
  
Tags: <reinforcement-learning><q-learning><math><dqn>
Title: How is the expected value in the loss function of DQN approximated?
UserDisplayName: Leroy Od
ThreadText: # How is the expected value in the loss function of DQN approximated?
  
  (Asked by: username_0 on 2020-02-27)
  
  In [Deep Q Learning](https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf) the parametrized Q-functions $Q\_i$ are optimised by performing gradient descent on the series of loss functions
  
  $L\_i(\theta\_i)= E\_{(s,a)\sim p}[(y\_i-Q(s,a;\theta\_i))^2]$ , where
  
  $y\_i = E\_{s' \sim \mathcal{E}}[r+\gamma \max\_{a'}Q(s',a';\theta\_{i+1})\mid s,a]$.
  
  In the actual algorithm, however, the expected value is never computed. Also, I think it cannot be computed since the transition probabilities of the underlying MDP remain hidden from the agent. Instead of the expected value, we compute $y\_i = r\_i + \gamma \max\_a Q(\phi\_{i+1},a;\theta)$. I assume some sort of stochastic approximation is taking place here. Can someone explain the details?
  
  **Tags:** reinforcement-learning, q-learning, math, dqn
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-02-28. Score: 2 | Accepted answer
  
  Just as the [paper](https://www.cs.toronto.edu/%7Evmnih/docs/dqn.pdf) says
  
  $$L\_i(\theta\_i)= E\_{(s,a)\sim p}[(y\_i-Q(s,a;\theta\_i))^2]$$
  
  where
  
  $$y\_i = E\_{s' \sim \mathcal{E}}[r+\gamma \max\_{a'}Q(s',a';\theta\_{i+1})\mid s,a]$$
  
  Then in the *Background* section of the paper, it says
  
  > Differentiating the loss function with respect to the weights we arrive at the following gradient:
  
  $$\nabla\_{\theta\_i} L\_i(\theta\_i)\\= E\_{(s,a)\sim p,s'\sim\mathcal{E}}\left[\left(r+\gamma \max\_{a'}Q(s',a';\theta\_{i+1})-Q(s,a;\theta\_i)\right)\nabla\_{\theta\_i}Q(s,a;\theta\_i)\right]\tag{1}$$
  
  > Rather than computing the full expectations in the above gradient, it is often computationally expedient to optimize the loss function by **stochastic gradient descent**.
  >
  > ...
  >
  > and the expectations **are replaced by single samples** from the behavior distribution $ρ$ and the emulator $\mathcal{E}$ respectively.
  
  If you're familiar with SGD and [Stochastic Optimization](https://pdfs.semanticscholar.org/34dd/d8865569c2c32dec9bf7ffc817ff42faaa01.pdf) then you know what happens here:
  
  The expression inside the expectation of (1), i.e. $\left(r+\gamma \max\_{a'}Q(s',a';\theta\_{i+1})-Q(s,a;\theta\_i)\right)\nabla\_{\theta\_i}Q(s,a;\theta\_i)$ , is an [unbiased estimation](https://en.wikipedia.org/wiki/Bias_of_an_estimator) of the real gradient $\nabla\_{\theta\_i}L\_i(\theta\_i)$ - its expectation is the real gradient. In other words,
  
  $$\widehat{\nabla L}=\left(r+\gamma \max\_{a'}Q(s',a';\theta\_{i+1})-Q(s,a;\theta\_i)\right)\nabla\_{\theta\_i}Q(s,a;\theta\_i).$$
  
  Then by theory of Stochastic Optimization we can optimize $L$ by $\theta\leftarrow \theta - \alpha\widehat{\nabla L}$ , which is how SGD works.
  
  The unbiased estimation $\left(r+\gamma \max\_{a'}Q(s',a';\theta\_{i+1})-Q(s,a;\theta\_i)\right)\nabla\_{\theta\_i}Q(s,a;\theta\_i)$ can be sampled and calculated directly - you can run the emulator $\mathcal{E}$ and current behavior policy to collect $r, s', a'$ and calculate the gradient of your Q network $\nabla Q$ using TensorFlow. So the gradient to $L$ can be approximated.
  
  The $y\_j$ in the pseudocode of the paper is also an estimation. It'll be more proper to denote it as $\hat{y\_j}$.
  
  (I'm not an native English speaker so forgive my poor expression.)
  
  > **Comments:**
  > **username_2**: Welcome to AI SE! Thanks for contributing! This answer seems consistent with knowledge. Maybe you could spend more words on why that is an "unbiased estimator of the gradient" (maybe just link to a paper that shows that this an unbiased estimator of the gradient) and how this estimator is actually called. Furthermore, what do you mean by "which can be sampled and calculated directly", i.e. how can an estimator be sampled? Also, which pseudocode are you talking about where $\hat{y_j}$ is present?  
  > **username_1**: Thank you for your feedback. I have tried to edit my post to make it more clear. My English writing skill is not so good.  
  > **username_2**: Thanks for addressing my questions. Now your answer is clearer! And thanks again for contributing! I've already upvoted your answer. Feel free to stick around and contribute more :)  
  > **username_0**: Thanks for your contribution. I must admit that I haven't watched enough into stochastic gradient. As I understand it we try to find a zero of the gradient via the Robbins-Monro-Algorithm. In general, does that mean you have to check the prerequisites of Robbins-Monro before using stochastic gradient ? I think here they are satisfied.  
  > **username_3**: I don't understand how it is an unbiased estimator, can someone elucidate?  
  > **username_4**: Why is expectation in Loss function is with respect to (s,a)?  (s,a) is given.  
  
  ---
  
  