2
$\begingroup$

Why does TD (0) converge to the MLE solution of the Markov model?

Let's take the Example 6.4 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}$?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Oct 16 '21 at 15:16
  • $\begingroup$ Your question is very similar to this one, but you also provide a specific example, so I will not close this one as a duplicate of that one. $\endgroup$
    – nbro
    Oct 16 '21 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.