Body: <p>Why does TD (0) converge to the MLE solution of the Markov model?</p>
  <p>Let's take the <a href="https://incompleteideas.net/book/RLbook2020.pdf#page=149" rel="nofollow noreferrer"><strong>Example 6.4</strong></a> in Sutton and Barto's book as an example.</p>
  <blockquote>
  <p>Example 6.4: <strong>You are the Predictor</strong> Place yourself now in the role of the predictor of returns for an unknown Markov reward process. Suppose you observe the following eight episodes:</p>
  <p><span class="math-container">$A,0,B,0; B,1;B,1 ;B,1 ;B,1 ;B,1 ;B,1 ;B,0$</span></p>
  <p>...</p>
  <p>But what is the optimal value for the estimate <span class="math-container">$V(A)$</span> given this data? Here there are two reasonable answers. One is to observe that <span class="math-container">$100 \%$</span> of the times the process was in state <span class="math-container">$A$</span> it traversed immediately to <span class="math-container">$B$</span> (with a reward of <span class="math-container">$0$</span>); and because we have already decided that <span class="math-container">$B$</span> has value <span class="math-container">$\frac{3}{4}$</span>, therefore <span class="math-container">$A$</span> must have value <span class="math-container">$\frac{3}{4}$</span> as well. One way of viewing this answer is that it is based on first modeling the Markov process, in this case as shown to the right, and then computing the correct estimates given the model, which indeed in this case gives <span class="math-container">$V(A)=\frac{3}{4}$</span>. This is also the answer that batch <span class="math-container">$\mathrm{TD}(0)$</span> gives.</p>
  </blockquote>
  <p>Given the TD(0) update rule <span class="math-container">$V(S) \leftarrow V(S)+\alpha\left\lceil R+\gamma V\left(S^{\prime}\right)-V(S)\right]$</span>, how can we deduce that it will get the MLE solution and thus <span class="math-container">$V(A) =\frac{3}{4}$</span>?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-16T15:16:34.753Z
Comments.Text: As a general comment, convergence proofs in RL don't really exist for any nontrivial settings. Q learning, discrete spaces and I have read something involving linear approximation but overall they are extremely difficult.
Comments.UserDisplayName: FourierFlux
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-10-16T18:02:53.103Z
Comments.Text: Your question is very similar to [this one](https://ai.stackexchange.com/q/13973/2444), but you also provide a specific example, so I will not close this one as a duplicate of that one.
Comments.UserDisplayName: nbro
Tags: <reinforcement-learning><reference-request><proofs><convergence><temporal-difference-methods>
Title: Why does TD (0) converge to the MLE solution of the Markov model?
UserDisplayName: XXX
ThreadText: # Why does TD (0) converge to the MLE solution of the Markov model?
  
  (Asked by: username_0 on 2021-10-16)
  
  Why does TD (0) converge to the MLE solution of the Markov model?
  
  Let's take the [**Example 6.4**](https://incompleteideas.net/book/RLbook2020.pdf#page=149) in Sutton and Barto's book as an example.
  
  > Example 6.4: **You are the Predictor** Place yourself now in the role of the predictor of returns for an unknown Markov reward process. Suppose you observe the following eight episodes:
  >
  > $A,0,B,0; B,1;B,1 ;B,1 ;B,1 ;B,1 ;B,1 ;B,0$
  >
  > ...
  >
  > But what is the optimal value for the estimate $V(A)$ given this data? Here there are two reasonable answers. One is to observe that $100 \%$ of the times the process was in state $A$ it traversed immediately to $B$ (with a reward of $0$); and because we have already decided that $B$ has value $\frac{3}{4}$, therefore $A$ must have value $\frac{3}{4}$ as well. One way of viewing this answer is that it is based on first modeling the Markov process, in this case as shown to the right, and then computing the correct estimates given the model, which indeed in this case gives $V(A)=\frac{3}{4}$. This is also the answer that batch $\mathrm{TD}(0)$ gives.
  
  Given the TD(0) update rule $V(S) \leftarrow V(S)+\alpha\left\lceil R+\gamma V\left(S^{\prime}\right)-V(S)\right]$, how can we deduce that it will get the MLE solution and thus $V(A) =\frac{3}{4}$?
  
  **Tags:** reinforcement-learning, reference-request, proofs, convergence, temporal-difference-methods
  
  > **Comments:**
  > **username_1**: As a general comment, convergence proofs in RL don't really exist for any nontrivial settings. Q learning, discrete spaces and I have read something involving linear approximation but overall they are extremely difficult.  
  > **username_2**: Your question is very similar to [this one](https://ai.stackexchange.com/q/13973/2444), but you also provide a specific example, so I will not close this one as a duplicate of that one.  
  
  ---
  
  ## 0 answers
  
  