Temporal difference (TD) learning is a central and novel idea in reinforcement learning.

• It is a combination of Monte Carlo and dynamic programing methods
• It is a Model-free learning algorithm
• It both bootstraps (builds on top of previous best estimate) and samples
• It can an be used for both episodic or infinite-horizon (non-episodic) domains
• Immediately updates estimate of V after each ${\displaystyle (s,a,r,s')}$
• Requires the system to be Markovian
• Biased estimator of value function but often much lower variance than Monte Carlo estimator
• Converges to true value in finite state cases, but does not always converge with infinite number of states (known as function approximation)

Algorithm

TD learning can be applied as a spectrum between pure Monte Carlo and dynamic programing, but the simplest TD learning is as follows

• Input: ${\displaystyle \alpha }$
• Initialize ${\displaystyle V^{\pi }(s)=0,\forall s\in S}$
• Loop
  • Sample tuple ${\displaystyle (s_{t},a_{t},r_{t},s_{t+1})}$
  • Update ${\displaystyle V^{\pi }(s_{t})}$
    $${\displaystyle V^{\pi }(s)=V^{\pi }(s)+\alpha {\big (}\underbrace {[r_{t}+\gamma V^{\pi }(s_{t+1}]} _{\text{TD target}}-V^{\pi }(s){\big )}}$$

    

Temporal difference error is defined as

$${\displaystyle \delta _{t}=r_{t}+\gamma V^{\pi }(s_{t+1})-V^{\pi }(s_{t})}$$