I'd like to better understand temporal-difference learning. In particular, I'm wondering if it is prudent to think about TD($\lambda$) as a type of "truncated" Monte Carlo learning?
$\begingroup$
$\endgroup$
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
TD($\lambda$) can be thought of as a combination of TD and MC learning, so as to avoid to choose one method or the other and to take advantage of both approaches.
More precisely, TD($\lambda$) is temporal-difference learning with a $\lambda$-return, which is defined as an average of all $n$-step returns, for all $n$, where an $n$-step return is the target used to update the estimate of the value function that contains $n$ future rewards (plus an estimate of the value function of the state $n$ steps in the future). For example, TD(0) (e.g. Q-learning is usually presented as a TD(0) method) uses a $1$-step return, that is, it uses one future reward (plus an estimate of the value of the next state) to compute the target. The letter $\lambda$ actually refers to a parameter used in this context to weigh the combination of TD and MC methods. There are actually two different perspectives of TD($\lambda$), the forward view and the backward view (eligibility traces).
The blog post Reinforcement Learning: Eligibility Traces and TD(lambda) gives a quite intuitive overview of TD($\lambda$), and, for more details, read the related chapter of the book Reinforcement Learning: An Introduction.
$\begingroup$
$\endgroup$
I am a novice in Reinforcement Learning and I have been struggling for several monthes about the TD()'s logic. Initially it seemed to me that it was a successfull purely heuristic formula without any theoretical foundation. But nowadays, I understand it simply as a mean's calculation, using the recurrent formula that states that when you a have a mean and a new value arrives, it modifies the mean by an amount equal to its difference with it (the mean) divided by the new values number.
To summarize, the exposed mean calculation is an instance of a general formula of recurrent mean calculation that uses as increasing factor for the difference between the new value and the actual mean multiplied by any number between 0 and 1. By the way, this number - usually called step size parameter - can be dynamic, and in the first paragraph (usual mean calculation) its amount is the inverse of the number of values considered in the mean's calculation.
Intuitively, we can understand that it is an accurate estimation procedure independently the initial (guessed or not) value. With a high number of estimates (new values arriving), the initial values fades its importance, and that it can be extended to treat many (lambda) new values simultaneously.
Until now I have not found this explanation nowhere, even if it is very simple, and I am not so sure that it is sound. I will appreciate if someone let me know if this intuition is correct and if it has already been exposed somewhere.
$\begingroup$
$\endgroup$
I would argue that maybe the word "incremental" could be better.
Instead of directly comparing the Monte Carlo and the TD($\lambda$), I would like to compare the $\lambda$-return and the TD($\lambda$) algorithm, since Monte Carlo is an extreme case of $\lambda$-return method.
The $\lambda$-return algorithm is a forward view algorithm, which means that it requires waiting up to $n$ steps after the current step to gather all the necessary information for updating the current state. This can be unsatisfactory because updates are not made in real time. An extreme case of this scenario is the Monte Carlo method, in which updates for all states are delayed until the end of an episode.
TD($\lambda$) is a backward view algorithm that can alleviate this issue. Unlike the $\lambda$-return, which gathers all information at once and then performs a "complete update" of the current state via n-step bootstrapping, TD($\lambda$) performs "incremental updates" through eligibility traces. As it encounters a new state, it uses the new information to update those previous states that need this piece of information. Since those previous states might need more information than this single piece, they are "incrementally updated" or "partially updated" by this new information. As the process proceeds, the information that a previous state needs to complete its update will eventually be gathered completely, allowing for a complete update of that state.
Chapter 12 - Eligibility Traces of Sutton and Barto's book provides more accurate information about this topic.
