We start by focusing on the policy evaluation or prediction problem, the problem of estimating the value function $v_\pi$ for a given policy $\pi$.
Both TD and Monte Carlo methods use experience to solve the prediction problem. Given some experience following a policy $\pi$, both methods update their estimate $V$ of $v_\pi$ for the non-terminal states $S_t$ occurring in that experience. Roughly speaking, Monte Carlo methods wait until the return following the visit is known, then use that return as a target for $V (S_t)$. A simple every-visit Monte Carlo method suitable for non-stationary environments is
where $G_t$ is the actual return following time $t$, and $\alpha$ is a constant step-size parameter. Let us call this method constant-$\alpha$ MC.
Whereas Monte Carlo methods must wait until the end of the episode to determine the increment to $V (S_t)$ (only then is $G_t$ known), TD methods need to wait only until the next time step. At time $t + 1$ they immediately form a target and make a useful update using the observed reward $R_{t+1}$ and the estimate $V (S_{t+1})$.
The simplest TD method makes the update:
which can be rewritten into:
where the content between $[\text{ }]$ is known as the Temporal Difference (TD)-error, i.e., difference between old estimate and update taregt.
Immediately on transition to $S_{t+1}$ and receiving $R_{t+1}$. In effect, the target for the Monte Carlo update is $G_t$, whereas the target for the TD update is $R_{t+1} + \gamma V (S_{t+1})$. This TD method is called $\text{TD}(0)$, or one-step TD.
The box below specifies TD(0) completely in procedural form:
TD methods combine the sampling of Monte Carlo with the bootstrapping of DP.
Shown below is the backup diagram for tabular TD(0). The value estimate for the state node at the top of the backup diagram is updated on the basis of the one sample transition from it to the immediately following state.
We refer to TD and Monte Carlo updates as sample updates because they involve looking ahead to a sample successor state (or state–action pair), using the value of the successor and the reward along the way to compute a backed-up value, and then updating the value of the original state (or state–action pair) accordingly. Sample updates differ from the expected updates of DP methods in that they are based on a single sample successor rather than on a complete distribution of all possible successors.
Finally, note that the quantity in brackets in the TD(0) update is a sort of error, measuring the difference between the estimated value of St and the better estimate $R_{t+1} + \gamma V (S_{t+1})$. This quantity, called the TD error, arises in various forms throughout reinforcement learning: