Answers.Body: <p>As far as I know, there is no <em>very</em> simple proof of the convergence of temporal-difference algorithms. The proofs of convergence of TD algorithms are often based on <a href="https://en.wikipedia.org/wiki/Stochastic_approximation" rel="nofollow noreferrer">stochastic approximation theory</a> (given that e.g. <a href="https://papers.nips.cc/paper/764-convergence-of-stochastic-iterative-dynamic-programming-algorithms.pdf" rel="nofollow noreferrer">Q-learning can be viewed as a stochastic process</a>) and the work by <a href="http://mathworld.wolfram.com/Robbins-MonroStochasticApproximation.html" rel="nofollow noreferrer">Robbins and Monro</a> (in fact, the Robbins-Monro conditions are usually assumed in the theorems and proofs).</p>
  
  <p>The proofs of convergence of Q-learning (a TD(0) algorithm) and SARSA (another TD(0) algorithm), when the value functions are represented in tabular form (as opposed to being approximated with e.g. a neural network), can be found in different research papers.</p>
  
  <p>For example, the <strong>proof of convergence of tabular Q-learning</strong> can be found in the paper <a href="https://papers.nips.cc/paper/764-convergence-of-stochastic-iterative-dynamic-programming-algorithms.pdf" rel="nofollow noreferrer">Convergence of Stochastic Iterative Dynamic Programming Algorithms</a> (1994) by Tommi Jaakkola et al. The <strong>proof of convergence of tabular SARSA</strong> can be found in the paper <a href="https://link.springer.com/content/pdf/10.1023/A:1007678930559.pdf" rel="nofollow noreferrer">Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms</a> (2000) by Satinder Singh et al.</p>
  
  <p>See also <a href="https://ai.stackexchange.com/q/13973/2444">How to show temporal difference methods converge to MLE?</a>.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-02-27T15:17:37.403Z
Answers.LastActivityDate: 2020-02-27T15:22:44.197Z
Answers.LastEditDate: 2020-02-27T15:22:44.197Z
Answers.UserDisplayName: nbro
Body: <p>Does anybody know a simple proof of the convergence of the TD(0) value function prediction algorithm?</p>
  
  <p><a href="https://i.sstatic.net/DL575.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/DL575.png" alt="enter image description here"></a></p>
  
Tags: <reinforcement-learning><reference-request><proofs><convergence><temporal-difference-methods>
Title: Is there a simple proof of the convergence of TD(0)?
UserDisplayName: KaneM
ThreadText: # Is there a simple proof of the convergence of TD(0)?
  
  (Asked by: username_0 on 2020-02-22)
  
  Does anybody know a simple proof of the convergence of the TD(0) value function prediction algorithm?
  
  [![enter image description here](https://i.sstatic.net/DL575.png)](https://i.sstatic.net/DL575.png)
  
  **Tags:** reinforcement-learning, reference-request, proofs, convergence, temporal-difference-methods
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-02-27. Score: 3
  
  As far as I know, there is no *very* simple proof of the convergence of temporal-difference algorithms. The proofs of convergence of TD algorithms are often based on [stochastic approximation theory](https://en.wikipedia.org/wiki/Stochastic_approximation) (given that e.g. [Q-learning can be viewed as a stochastic process](https://papers.nips.cc/paper/764-convergence-of-stochastic-iterative-dynamic-programming-algorithms.pdf)) and the work by [Robbins and Monro](http://mathworld.wolfram.com/Robbins-MonroStochasticApproximation.html) (in fact, the Robbins-Monro conditions are usually assumed in the theorems and proofs).
  
  The proofs of convergence of Q-learning (a TD(0) algorithm) and SARSA (another TD(0) algorithm), when the value functions are represented in tabular form (as opposed to being approximated with e.g. a neural network), can be found in different research papers.
  
  For example, the **proof of convergence of tabular Q-learning** can be found in the paper [Convergence of Stochastic Iterative Dynamic Programming Algorithms](https://papers.nips.cc/paper/764-convergence-of-stochastic-iterative-dynamic-programming-algorithms.pdf) (1994) by Tommi Jaakkola et al. The **proof of convergence of tabular SARSA** can be found in the paper [Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms](https://link.springer.com/content/pdf/10.1023/A:1007678930559.pdf) (2000) by Satinder Singh et al.
  
  See also [How to show temporal difference methods converge to MLE?](https://ai.stackexchange.com/q/13973/2444).
  
  
  ---
  
  