Answers.Body: <p>The convergence and optimality proofs of (linear) temporal-difference methods (under batch training, so not online learning) can be found in the paper <a href="https://link.springer.com/content/pdf/10.1007%2FBF00115009.pdf" rel="noreferrer">Learning to predict by the methods of temporal differences</a> (1988) by Richard Sutton, specifically section 4 (p. 23). In this paper, Sutton uses a different notation than the notation used in the famous book <a href="http://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf" rel="noreferrer">Reinforcement Learning: An Introduction</a> (2nd ed.), by Sutton and Barto, so I suggest you get familiar with the notation before attempting to understand the theorem and the proof. For example, Sutton uses letters such as <span class="math-container">$i$</span> and <span class="math-container">$j$</span> to denote <em>states</em> (rather than <span class="math-container">$s$</span>), <span class="math-container">$z$</span> to denote (scalar) <em>outcomes</em> and <span class="math-container">$x$</span> to denote (vector) <em>observations</em> (see section 3.2 for example of the usage of this notation).</p>
  
  <p>In the paper <a href="https://link.springer.com/content/pdf/10.1023%2FA%3A1022632907294.pdf" rel="noreferrer">The Convergence of TD(<span class="math-container">$\lambda$</span>) for General <span class="math-container">$\lambda$</span></a> (1992), Peter Dayan, apart from recapitulating the convergence proof provided by Sutton, he also shows the convergence properties of TD(<span class="math-container">$\lambda$</span>) and he extends Watkins' Q-learning convergence theorem, whose sketch is presented in his PhD thesis <a href="https://www.cs.rhul.ac.uk/home/chrisw/new_thesis.pdf" rel="noreferrer">Learning from Delayed Rewards</a> (1989), and defined in detail in <a href="http://www.gatsby.ucl.ac.uk/~dayan/papers/cjch.pdf" rel="noreferrer">Technical Note: Q-learning</a> (1992), by Dayan and Watkins, to provide the first strongest guarantee or convergence proof for TD(0).</p>
  
  <p>There is much more research work on the convergence properties of TD methods, such as Q-learning and SARSA. For example, in the paper <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.4499&amp;rep=rep1&amp;type=pdf" rel="noreferrer">On the Convergence of Stochastic Iterative Dynamic Programming Algorithms</a> (1994), where Q-learning is presented as a stochastic form of dynamic programming methods, the authors provide a proof of convergence for Q-learning by making direct use of <a href="http://www.stat.columbia.edu/~liam/teaching/compstat-spr14/lauren-notes.pdf" rel="noreferrer">stochastic approximation theory</a>. See also <a href="http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf" rel="noreferrer">Convergence of Q-learning: a simple proof</a> by Francisco S. Melo. In the paper <a href="https://link.springer.com/content/pdf/10.1023%2FA%3A1007678930559.pdf" rel="noreferrer">Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms</a>, the authors provide a proof of the convergence properties of on-line temporal difference methods (e.g. SARSA).</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-09T14:47:06.267Z
Answers.Text: Notes by Francisco S. Melo are deeply inspired by the paper On the Convergence of Stochastic Iterative Dynamic Programming Algorithms (1994) I think ! Nothing about "Likelihood" however?
Answers.UserDisplayName: Rémy Hosseinkhan Boucher
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-10T12:32:26.140Z
Answers.Text: @RémyHosseinkhanBoucher I'm not sure whether I fully read the 1994 paper, and, if I did, it was already a few years ago, so I don't remember the details and I can't confirm that's the case. I had read Melo's paper though. Anyway, thanks for pointing this out. Regarding your question, now, I don't remember the details of the proofs  to tell you if they mention anything about the "convergence to the MLE". I would need to read them again. Let me know if you figure out anything about this issue.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-10T14:17:19.733Z
Answers.Text: By the way, I have seen an article saying on your blog MDP are PO-MDP. Reciprocally, PO-MDP can be transformed into MDP but with larger spaces! see p. 96 from Adaptive Markov Control Processes - O. Hernandez Lerma
Answers.UserDisplayName: Rémy Hosseinkhan Boucher
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-03-10T14:36:04.347Z
Answers.Text: @RémyHosseinkhanBoucher Yes! Are you referring to Belief MDPs? Basically, you treat belief states as the states.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-08-18T13:36:08.887Z
Answers.LastActivityDate: 2019-08-18T19:13:15.377Z
Answers.LastEditDate: 2019-08-18T19:13:15.377Z
Answers.UserDisplayName: nbro
Body: <p>In chapter 6 of <a href="http://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf" rel="nofollow noreferrer">Sutton and Barto</a> (p. 128), they claim temporal difference converges to the maximum likelihood estimate (MLE). How can this be shown formally?</p>
  
Tags: <reinforcement-learning><proofs><convergence><temporal-difference-methods>
Title: How to show temporal difference methods converge to MLE?
UserDisplayName: fool
ThreadText: # How to show temporal difference methods converge to MLE?
  
  (Asked by: username_0 on 2019-08-14)
  
  In chapter 6 of [Sutton and Barto](http://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf) (p. 128), they claim temporal difference converges to the maximum likelihood estimate (MLE). How can this be shown formally?
  
  **Tags:** reinforcement-learning, proofs, convergence, temporal-difference-methods
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-08-18. Score: 9 | Accepted answer
  
  The convergence and optimality proofs of (linear) temporal-difference methods (under batch training, so not online learning) can be found in the paper [Learning to predict by the methods of temporal differences](https://link.springer.com/content/pdf/10.1007%2FBF00115009.pdf) (1988) by Richard Sutton, specifically section 4 (p. 23). In this paper, Sutton uses a different notation than the notation used in the famous book [Reinforcement Learning: An Introduction](http://www.andrew.cmu.edu/course/10-703/textbook/BartoSutton.pdf) (2nd ed.), by Sutton and Barto, so I suggest you get familiar with the notation before attempting to understand the theorem and the proof. For example, Sutton uses letters such as $i$ and $j$ to denote *states* (rather than $s$), $z$ to denote (scalar) *outcomes* and $x$ to denote (vector) *observations* (see section 3.2 for example of the usage of this notation).
  
  In the paper [The Convergence of TD($\lambda$) for General $\lambda$](https://link.springer.com/content/pdf/10.1023%2FA%3A1022632907294.pdf) (1992), Peter Dayan, apart from recapitulating the convergence proof provided by Sutton, he also shows the convergence properties of TD($\lambda$) and he extends Watkins' Q-learning convergence theorem, whose sketch is presented in his PhD thesis [Learning from Delayed Rewards](https://www.cs.rhul.ac.uk/home/chrisw/new_thesis.pdf) (1989), and defined in detail in [Technical Note: Q-learning](http://www.gatsby.ucl.ac.uk/~dayan/papers/cjch.pdf) (1992), by Dayan and Watkins, to provide the first strongest guarantee or convergence proof for TD(0).
  
  There is much more research work on the convergence properties of TD methods, such as Q-learning and SARSA. For example, in the paper [On the Convergence of Stochastic Iterative Dynamic Programming Algorithms](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.83.4499&rep=rep1&type=pdf) (1994), where Q-learning is presented as a stochastic form of dynamic programming methods, the authors provide a proof of convergence for Q-learning by making direct use of [stochastic approximation theory](http://www.stat.columbia.edu/~liam/teaching/compstat-spr14/lauren-notes.pdf). See also [Convergence of Q-learning: a simple proof](http://users.isr.ist.utl.pt/~mtjspaan/readingGroup/ProofQlearning.pdf) by Francisco S. Melo. In the paper [Convergence Results for Single-Step On-Policy Reinforcement-Learning Algorithms](https://link.springer.com/content/pdf/10.1023%2FA%3A1007678930559.pdf), the authors provide a proof of the convergence properties of on-line temporal difference methods (e.g. SARSA).
  
  > **Comments:**
  > **username_2**: Notes by Francisco S. Melo are deeply inspired by the paper On the Convergence of Stochastic Iterative Dynamic Programming Algorithms (1994) I think ! Nothing about "Likelihood" however?  
  > **username_1**: @RémyHosseinkhanBoucher I'm not sure whether I fully read the 1994 paper, and, if I did, it was already a few years ago, so I don't remember the details and I can't confirm that's the case. I had read Melo's paper though. Anyway, thanks for pointing this out. Regarding your question, now, I don't remember the details of the proofs  to tell you if they mention anything about the "convergence to the MLE". I would need to read them again. Let me know if you figure out anything about this issue.  
  > **username_2**: By the way, I have seen an article saying on your blog MDP are PO-MDP. Reciprocally, PO-MDP can be transformed into MDP but with larger spaces! see p. 96 from Adaptive Markov Control Processes - O. Hernandez Lerma  
  > **username_1**: @RémyHosseinkhanBoucher Yes! Are you referring to Belief MDPs? Basically, you treat belief states as the states.  
  
  ---
  
  