Answers.Body: <p>I have found some clues in Maei's thesis (2011): <a href="https://era.library.ualberta.ca/items/fd55edcb-ce47-4f84-84e2-be281d27b16a" rel="nofollow noreferrer">“Gradient Temporal-Difference Learning Algorithms.”</a></p>
  
  <p>According to the thesis: </p>
  
  <ol>
  <li>GTD2 is a method that minimizes the projected Bellman error (MSPBE).</li>
  <li>GTD2 is convergent in non-linear function approximation case (and off-policy).</li>
  <li>GTD2 converges to a TD-fixed point (same point as semi-gradient TD).</li>
  <li>GTD2 is slower to converge than usual semi-gradient TD. </li>
  </ol>
  
  <blockquote>
    <p>It doesn't readily apply to non-linear function approximation.</p>
  </blockquote>
  
  <p>No, it does.</p>
  
  <blockquote>
    <p>It doesn't yield a good solution. </p>
  </blockquote>
  
  <p>No, it does. TD-fixed point is the same point for the solution of semi-gradient TD (which is generally used). There is no edge on that.</p>
  
  <p><strong>The only explanation seems to be practical convergence rate.</strong></p>
  
  <p>To quote his words: </p>
  
  <blockquote>
    <p>Some of our empirical results suggest that gradient-TD method maybe slower than conventional TD methods on problems on which conventional TD methods are sound (that is, on-policy learning problems).</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-09T02:33:26.430Z
Answers.LastActivityDate: 2019-10-09T02:33:26.430Z
Answers.UserDisplayName: Phizaz
Answers.Body: <p>As I understand it above-mentioned projection operator project into linear feature subspace produced from set of feature vectors (or feature functions), that is space of linear combinations of features. Vanilla DQN don't have any feature space, projection into linear subspace doesn't make sense in DQN context. If you attempt to produce feature space for values/Q with some NN it wouldn't be DQN (because Q wouldn't be produced) and it wouldn't work anyway on anything but toy problems because amount of degrees of freedom of output would be too high.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-11T04:41:36.310Z
Answers.Text: The proof in [Maei's thesis](https://era.library.ualberta.ca/items/fd55edcb-ce47-4f84-84e2-be281d27b16a) on the convergence of GTD2 on non-linear case is based on a "tangent" plane. He argued that there exists a differentiable manifold which is locally linear (given that a learning rate is arbitrarily small). This extends the proof of linear case onto the non-linear case.
Answers.UserDisplayName: Phizaz
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-12T07:13:13.613Z
Answers.Text: Output space of DNN is not even a manifold  strictly speaking because input (and in some treatments even weights) are random variables. Manifold of random variables is hard math problem (unlike random variable *on* manifold). Tangent hyperplane could be approximated sometimes but it's hard anyway.
Answers.UserDisplayName: mirror2image
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-10-09T10:50:28.163Z
Answers.LastActivityDate: 2019-10-09T10:50:28.163Z
Answers.UserDisplayName: mirror2image
Body: <p>Projected Bellman error has shown to be stable with linear function approximation. The technique is not at all new. I can only wonder why this technique is not adopted to use with non-linear function approximation (e.g. DQN)? Instead, a less theoretical justified target network is used. </p>
  
  <p>I could come up with two possible explanations:</p>
  
  <ol>
  <li>It doesn't readily apply to non-linear function approximation case (some work needed)</li>
  <li>It doesn't yield a good solution. This is the case for <em>true</em> Bellman error but I'm not sure about the projected one.</li>
  </ol>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-10T14:47:55.903Z
Comments.Text: Can you define the "projected Bellman error"?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-11T14:06:29.650Z
Comments.Text: @nbro It literally means what it says. Projecting a Bellman error onto a representable space of a function approximation. I think Sutton's Gradient TD minimize this. But it is proposed for a linear approximation case.
Comments.UserDisplayName: Phizaz
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-11T16:48:17.960Z
Comments.Text: It might be clear to you, but what does it mean to project something onto a representable space of a function approximation model? Moreover, what is the Bellman error? Do you have a specific source that talks about this topic more in detail?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2019-05-13T09:41:48.773Z
Comments.Text: @nbro I refer to chapter 11.7 in Sutton's 2018 book which he describes Gradient TD methods. The projection you're talking about refers to p. 268 in the same book. Honestly, I don't really understand it that much.
Comments.UserDisplayName: Phizaz
Tags: <reinforcement-learning><dqn><deep-rl><function-approximation>
Title: Why don't people use projected Bellman error with deep neural networks?
UserDisplayName: Phizaz
ThreadText: # Why don't people use projected Bellman error with deep neural networks?
  
  (Asked by: username_0 on 2019-04-12)
  
  Projected Bellman error has shown to be stable with linear function approximation. The technique is not at all new. I can only wonder why this technique is not adopted to use with non-linear function approximation (e.g. DQN)? Instead, a less theoretical justified target network is used.
  
  I could come up with two possible explanations:
  
  1. It doesn't readily apply to non-linear function approximation case (some work needed)
  2. It doesn't yield a good solution. This is the case for *true* Bellman error but I'm not sure about the projected one.
  
  **Tags:** reinforcement-learning, dqn, deep-rl, function-approximation
  > **Comments:**
  > **username_1**: Can you define the "projected Bellman error"?  
  > **username_0**: @nbro It literally means what it says. Projecting a Bellman error onto a representable space of a function approximation. I think Sutton's Gradient TD minimize this. But it is proposed for a linear approximation case.  
  > **username_1**: It might be clear to you, but what does it mean to project something onto a representable space of a function approximation model? Moreover, what is the Bellman error? Do you have a specific source that talks about this topic more in detail?  
  > **username_0**: @nbro I refer to chapter 11.7 in Sutton's 2018 book which he describes Gradient TD methods. The projection you're talking about refers to p. 268 in the same book. Honestly, I don't really understand it that much.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_0 on 2019-10-09. Score: 3
  
  I have found some clues in Maei's thesis (2011): [“Gradient Temporal-Difference Learning Algorithms.”](https://era.library.ualberta.ca/items/fd55edcb-ce47-4f84-84e2-be281d27b16a)
  
  According to the thesis:
  
  1. GTD2 is a method that minimizes the projected Bellman error (MSPBE).
  2. GTD2 is convergent in non-linear function approximation case (and off-policy).
  3. GTD2 converges to a TD-fixed point (same point as semi-gradient TD).
  4. GTD2 is slower to converge than usual semi-gradient TD.
  
  > It doesn't readily apply to non-linear function approximation.
  
  No, it does.
  
  > It doesn't yield a good solution.
  
  No, it does. TD-fixed point is the same point for the solution of semi-gradient TD (which is generally used). There is no edge on that.
  
  **The only explanation seems to be practical convergence rate.**
  
  To quote his words:
  
  > Some of our empirical results suggest that gradient-TD method maybe slower than conventional TD methods on problems on which conventional TD methods are sound (that is, on-policy learning problems).
  
  
  ---
  
  ### Answer by username_2 on 2019-10-09. Score: 0
  
  As I understand it above-mentioned projection operator project into linear feature subspace produced from set of feature vectors (or feature functions), that is space of linear combinations of features. Vanilla DQN don't have any feature space, projection into linear subspace doesn't make sense in DQN context. If you attempt to produce feature space for values/Q with some NN it wouldn't be DQN (because Q wouldn't be produced) and it wouldn't work anyway on anything but toy problems because amount of degrees of freedom of output would be too high.
  
  > **Comments:**
  > **username_0**: The proof in [Maei's thesis](https://era.library.ualberta.ca/items/fd55edcb-ce47-4f84-84e2-be281d27b16a) on the convergence of GTD2 on non-linear case is based on a "tangent" plane. He argued that there exists a differentiable manifold which is locally linear (given that a learning rate is arbitrarily small). This extends the proof of linear case onto the non-linear case.  
  > **username_2**: Output space of DNN is not even a manifold  strictly speaking because input (and in some treatments even weights) are random variables. Manifold of random variables is hard math problem (unlike random variable *on* manifold). Tangent hyperplane could be approximated sometimes but it's hard anyway.  
  
  ---
  
  