<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>

CC BY-SA 4.0
2019-12-04T23:45:48.713Z
2019-12-04T23:45:48.713Z
Diego Gomez
<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>

<reinforcement-learning><convergence><function-approximation><temporal-difference-methods><on-policy-methods>
Convergence of semi-gradient TD(0) with non-linear function approximation
srinivas tunuguntla
# 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.


---

