Temporal-difference learning and the previous methods
The main aspects of our previous two categories of methods:
Monte Carlo (MC): learning from experience, possibly without knowledge of a model, e.g., MC prediction with exploring starts: \[Q(s_t,a_t) = Q(s_t,a_t) + \frac{1}{n(s_t,a_t)} \left[g - Q(s_t,a_t)\right].\]
Dynamic programming (DP): bootstrapping\(\Rightarrow\) updating estimates based on estimates, e.g., iterative policy evaluation: \[ \textcolor{red}{V(s)} = \sum_{a\in\Ac} \pias \sum_{s'\in\Sc} \psprimesa \left[ r + \gamma \textcolor{red}{V(s')} \right]. \]
The concept of temporal difference (TD) learning is to combine both:
Model-free prediction and control in unknown MDPs.
Updates policy evaluation and improvement in an online fashion (i.e., not per episode) by bootstrapping.
Recall the incremental update of the type we discussed for multi-armed bandits or for MC control \(\Rightarrow\)\(\mathsf{NewEstimate} = \mathsf{OldEstimate} + StepSize \; [ \mathsf{Target} - \mathsf{OldEstimate} ]\): \[
\begin{equation}
V(s_t) = V(s_t) + \alpha \left[g_t - V(s_t)\right]. \label{eq:TD_MC-update}
\end{equation}
\]
\(\alpha \in (0,1)\) is the forget factor / step size.
\(g_t\) is the target of the incremental update rule.
To execute \(\eqref{eq:TD_MC-update}\), we have to wait until the end of the episode to get \(g_t\).
Using the target, we can define the TD error\(^*\)\(\delta\)\(\Rightarrow\) the expression inside the bracket of Eq. \(\eqref{eq:TD_TD0-update}\) we’re using to improve our estimate: \[ \delta_t = \mathsf{target} - V(s_t) = r_t + \gamma V(s_{t+1}) - V(s_t). \]
Batch mode: Let’s assume that the TD(0) estimate of \(V(s)\) does not change within an episode, but that we apply all updates simulatenously once the episode is finished (exactly as we need to do in MC prediction):\[
\begin{align*}
\underbrace{g_t - V(s_t)}_{\text{MC error}} &= r_{t}+\gamma g_{t+1} - V(s_t) \fragment{+\gamma V(s_{t+1}) - \gamma V(s_{t+1})}\\
&= \delta_t + \gamma (\underbrace{g_{t+1} - V(s_{t+1})}_{\text{MC error}}) \fragment{= \delta_t + \gamma \delta_{t+1} + \gamma^2(g_{t+2} - V(s_{t+2}))} \\
&= \delta_t + \gamma \delta_{t+1} + \gamma^2 \delta_{t+2} + \gamma^3(g_{t+3} - V(s_{t+3})) \fragment{= \ldots = \sum_{k=t}^T\gamma^{k-t} \delta_k.}
\end{align*}
\]
The MC error is the discounted sum of TD errors in this case.
If \(V(s)\) is updated during an episode (as is common in TD(0)), the above identity only holds approximately.
The driving home example
Imagine you want to predict your time to get home after work, starting with an estimate of 30 minutes.
Overview of elapsed time and your predictions of time to go and total time (Sutton and Barto 1998, Example 6.1)
State
Elapsed Time (minutes)
Predicted Time to Go
Predicted Total Time
leaving office, friday at 6
0
30
30
reach car, raining
5
35
40
exiting highway
20
15
35
2ndary road, behind truck
30
10
40
entering home street
40
3
43
arrive home
43
0
43
In MC, we estimate the returns \(g_t\)after we have reached home \(\Rightarrow\) it is hard to assess where the deviation was caused.
In TD, we can immediately shift our estimate in each time step.
With TD, we can even learn from continuing tasks!
MC vs. TD estimate
The batch training AB example
asf
Content
Recall GPI
GLIE
SARSA (on-policy)
Q-learning (off-policy)
Greedy in the limit with infinite exploration (GLIE)
A learning policy \(\pi\) is called GLIE if it satisfies the following two properties:
If a state is visited inifinitely often, then each action is choosen inifintely often: \[ \lim_{i \to \infty} \pi_i(a|s) = 1 \quad \forall \{s \in \Sc, a \in \Ac\}\]
In the limit (\(i \to \infty\)) the learning policy is greedy with respect to the learned action value: \[ \lim_{i \to \infty} \pi_i(a|s) = \pi(s) = \arg \max_{a \in \Ac} Q(s,a) \quad \forall s \in \Sc \]
GLIE Monte Carlo control
MC-based contro using \(\epsilon\)-greedy exploration is GLIE, if \(\epsilon\) is decreased at a rate \[ \epsilon_i = \frac{1}{i} \] with \(i\) being the increasing episode index. In this case, \[ \hat Q(s,a) = Q^*(s,a) \] follows.
SARSA
State-Action-Reward-Next-State-Next-Action
on-policy
Algorithm: SARSA.
initialize
\(Q(s,a)\) arbitrarily for \(s \in \Sc, a \in \Ac\)
