Answers.Body: <p>Apparently there is an example of non-convergence for semi-gradient sarsa, <a href="https://media.nips.cc/Conferences/2015/tutorialslides/SuttonIntroRL-nips-2015-tutorial.pdf" rel="nofollow noreferrer">according to Rich Sutton</a> (check slide 35). I guess TD(0) is not so different. So, probably your approximator will need to satisfy certain conditions to proof convergence. </p>
  
  <p>Maybe <a href="https://openreview.net/pdf?id=SJezGp4YPr" rel="nofollow noreferrer">this paper</a> will be useful for you. It seems that they show that constraining your network to have relu activation functions allow you to show some convergence properties. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-12-04T23:45:48.713Z
Answers.LastActivityDate: 2019-12-04T23:45:48.713Z
Answers.UserDisplayName: Diego Gomez
Body: <p>I am looking for a result that shows the convergence of semi-gradient TD(0) algorithm with non-linear function approximation for on-policy prediction. Specifically, the update equation is given by (borrowing notation from Sutton and Barto (2018))</p>
  
  <p><span class="math-container">$$\mathbf w \leftarrow \mathbf w +\alpha [R + \gamma \hat v(S', \mathbf w) - \hat v(S, \mathbf w)] \nabla \hat v(S, \mathbf w)$$</span></p>
  
  <p>where <span class="math-container">$\hat v(S, \mathbf w)$</span> is the approximate value function parameterized by <span class="math-container">$\mathbf w$</span>.</p>
  
  <p>Sutton and Barto (2018) mention that the above update equation converges when <span class="math-container">$\hat v$</span> is linear in <span class="math-container">$\mathbf w$</span>. But I couldn't find a similar result for non-linear function approximation. Any help would be greatly appreciated.</p>
  
Tags: <reinforcement-learning><convergence><function-approximation><temporal-difference-methods><on-policy-methods>
Title: Convergence of semi-gradient TD(0) with non-linear function approximation
UserDisplayName: srinivas tunuguntla
ThreadText: # Convergence of semi-gradient TD(0) with non-linear function approximation
  
  (Asked by: username_0 on 2019-11-05)
  
  I am looking for a result that shows the convergence of semi-gradient TD(0) algorithm with non-linear function approximation for on-policy prediction. Specifically, the update equation is given by (borrowing notation from Sutton and Barto (2018))
  
  $$\mathbf w \leftarrow \mathbf w +\alpha [R + \gamma \hat v(S', \mathbf w) - \hat v(S, \mathbf w)] \nabla \hat v(S, \mathbf w)$$
  
  where $\hat v(S, \mathbf w)$ is the approximate value function parameterized by $\mathbf w$.
  
  Sutton and Barto (2018) mention that the above update equation converges when $\hat v$ is linear in $\mathbf w$. But I couldn't find a similar result for non-linear function approximation. Any help would be greatly appreciated.
  
  **Tags:** reinforcement-learning, convergence, function-approximation, temporal-difference-methods, on-policy-methods
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-12-04. Score: 2
  
  Apparently there is an example of non-convergence for semi-gradient sarsa, [according to Rich Sutton](https://media.nips.cc/Conferences/2015/tutorialslides/SuttonIntroRL-nips-2015-tutorial.pdf) (check slide 35). I guess TD(0) is not so different. So, probably your approximator will need to satisfy certain conditions to proof convergence.
  
  Maybe [this paper](https://openreview.net/pdf?id=SJezGp4YPr) will be useful for you. It seems that they show that constraining your network to have relu activation functions allow you to show some convergence properties.
  
  
  ---
  
  