Is there a tutorial for understanding the proof of convergence for TD learning?

Question

I'm reading the article An Analysis of Temporal-Difference Learning with Function Approximation (1997), but the mathematics inside seems overly complicated for me. Answers to some similar questions had pointed out that these proof typically involves stochastic approximation.

My question is: are there any good tutorials (textbooks, list of papers, etc.) on stochastic approximation (or similar topics) that prepare you for reading proof like this? It will be best if it is rather self-contained under my mathematical maturity.

I have an undergraduate-level mathematical analysis and probability theory foundation and have touched some measure theory.

Answer 1

It's a pleasant surprise that somebody is interested in the fundamental convergence properties of TD, like me:)

It depends on which algorithm's convergence you want to know.

1. TD in the tabular case
2. TD with value function approximation: linear function approximation
3. TD with value function approximation: nonlinear function approximation by NN

Here TD mainly refers to TD($\lambda$).

1. If it is the first case, you can read the paper:

1993 - On the Convergence of Stochastic Iterative Dynamic Programming Algorithms

The most important result is Lemma 1, which is an extension of Dvoretzky's Theorem. If you would like to further study Dvoretzky's Theorem, you will see that the math behind the convergence proof is stochastic approximation (SA). If you go deep into SA, you may diverge from RL too far. One suggestion is to study Robbins-Monro Algorithm, which is easy to understand and inspiring.

2. If it is the second case, you have been reading the correct paper, though this paper is really complicated. But if you are determined to understand this paper, one suggestion is to consider the special TD(0) case, which will be easier to understand. Nevertheless, it is still nontrivial. But once you understand it, everything will be crystal.

3. If it is the third case, I doubt it could be proved. That is simply because convergence properties are extremely challenging to analyze when the function appropriator is nonlinear. But it does not mean the convergence analysis in the linear case is meaningless, nor the nonlinear case is impractical.