Answers.Body: <p>We cannot approximate <span class="math-container">$ E^2(x)$</span> by <span class="math-container">$\frac{1}{N} \sum_i x_i \frac{1}{N} \sum_j x_j $</span>. Because <span class="math-container">$cov(x)=E(x^2)-E^2(x)$</span>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-28T13:40:05.993Z
Answers.Text: Hello. This answer is quite short. Maybe you could elaborate a little bit more and tell us more in detail how this answers the question(s). For example, how does this answer the question "what is the double sample problem"?
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-05-28T01:27:02.647Z
Answers.LastActivityDate: 2021-05-28T13:38:47.587Z
Answers.LastEditDate: 2021-05-28T13:38:47.587Z
Answers.UserDisplayName: Jason King
Answers.Body: <p>The double sampling problem is referenced in Chaper 11.5 <em>Gradient Descent in the Bellman Error</em> in <a href="http://incompleteideas.net/book/the-book.html" rel="nofollow noreferrer">Reinforcement Learning: An Introduction (2nd edition)</a>.</p>
  <p>From the book, this is the full gradient descent (as opposed to semi-gradient descent) update rule for weights of an estimator that should converge to a minimal distance from the Bellman error:</p>
  <blockquote>
  <p><span class="math-container">$$w_{t+1} = w_t + \alpha[\mathbb{E}_b[\rho_t[R_{t+1} + \gamma\hat{v}(S_{t+1},\mathbf{w})] - \hat{v}(S_{t},\mathbf{w})][\nabla\hat{v}(S_{t},\mathbf{w})- \gamma\mathbb{E}_b[\rho_t\nabla\hat{v}(S_{t+1},\mathbf{w})]]$$</span></p>
  <p>[...] But this is naive, because the equation above involves the next state, <span class="math-container">$S_{t+1}$</span>, appearing in two
  expectations that are multiplied together. To get an unbiased sample of the product,
  two independent samples of the next state are required, but during normal interaction
  with an external environment only one is obtained. One expectation or the other can be
  sampled, but not both.</p>
  </blockquote>
  <p>Basically, unless you have an environment that you can routinely re-wind and re-sample to get two independent estimates (for <span class="math-container">$\hat{v}(S_{t+1},\mathbf{w})$</span> and <span class="math-container">$\nabla\hat{v}(S_{t+1},\mathbf{w})$</span>) then the update rule that naturally arises from gradient descent on the Bellman error does will work any better than other approaches, such as semi-gradient methods. If you can do this rewind process on every step, then it may be worth it because of the guarantees of convergence, even in off-policy with non-linear approximators.</p>
  <p>The paper proposes a workaround for this issue, keeping the robust convergence guarantees, but dropping the need to collect two independent samples of the same estimate on each step.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-28T09:25:18.977Z
Answers.LastActivityDate: 2019-10-28T09:25:18.977Z
Answers.LastEditDate: 2020-06-17T09:57:20.710Z
Answers.UserDisplayName: Neil Slater
Body: <p>According to the <a href="https://arxiv.org/pdf/1712.10285.pdf" rel="noreferrer">SBEED: Convergent Reinforcement Learning with
  Nonlinear Function Approximation</a> for convergent reinforcement learning, the Smoothed Bellman operator is a way to dodge the double sample problem? Can someone explain to me what the double sample problem is and how SBEED solves it?</p>
  
Tags: <reinforcement-learning>
Title: What is the double sample problem in reinforcement learning?
UserDisplayName: Dhanush Giriyan
ThreadText: # What is the double sample problem in reinforcement learning?
  
  (Asked by: username_0 on 2019-10-26)
  
  According to the [SBEED: Convergent Reinforcement Learning with
  Nonlinear Function Approximation](https://arxiv.org/pdf/1712.10285.pdf) for convergent reinforcement learning, the Smoothed Bellman operator is a way to dodge the double sample problem? Can someone explain to me what the double sample problem is and how SBEED solves it?
  
  **Tags:** reinforcement-learning
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_3 on 2019-10-28. Score: 6 | Accepted answer
  
  The double sampling problem is referenced in Chaper 11.5 *Gradient Descent in the Bellman Error* in [Reinforcement Learning: An Introduction (2nd edition)](http://incompleteideas.net/book/the-book.html).
  
  From the book, this is the full gradient descent (as opposed to semi-gradient descent) update rule for weights of an estimator that should converge to a minimal distance from the Bellman error:
  
  > $$w\_{t+1} = w\_t + \alpha[\mathbb{E}\_b[\rho\_t[R\_{t+1} + \gamma\hat{v}(S\_{t+1},\mathbf{w})] - \hat{v}(S\_{t},\mathbf{w})][\nabla\hat{v}(S\_{t},\mathbf{w})- \gamma\mathbb{E}\_b[\rho\_t\nabla\hat{v}(S\_{t+1},\mathbf{w})]]$$
  >
  > [...] But this is naive, because the equation above involves the next state, $S\_{t+1}$, appearing in two
  > expectations that are multiplied together. To get an unbiased sample of the product,
  > two independent samples of the next state are required, but during normal interaction
  > with an external environment only one is obtained. One expectation or the other can be
  > sampled, but not both.
  
  Basically, unless you have an environment that you can routinely re-wind and re-sample to get two independent estimates (for $\hat{v}(S\_{t+1},\mathbf{w})$ and $\nabla\hat{v}(S\_{t+1},\mathbf{w})$) then the update rule that naturally arises from gradient descent on the Bellman error does will work any better than other approaches, such as semi-gradient methods. If you can do this rewind process on every step, then it may be worth it because of the guarantees of convergence, even in off-policy with non-linear approximators.
  
  The paper proposes a workaround for this issue, keeping the robust convergence guarantees, but dropping the need to collect two independent samples of the same estimate on each step.
  
  
  ---
  
  ### Answer by username_1 on 2021-05-28. Score: 0
  
  We cannot approximate $ E^2(x)$ by $\frac{1}{N} \sum\_i x\_i \frac{1}{N} \sum\_j x\_j $. Because $cov(x)=E(x^2)-E^2(x)$.
  
  > **Comments:**
  > **username_2**: Hello. This answer is quite short. Maybe you could elaborate a little bit more and tell us more in detail how this answers the question(s). For example, how does this answer the question "what is the double sample problem"?  
  
  ---
  
  