Temporal Difference Learning

Instead of solving equations for all states, incrementally update visited states

TD reduces discrepancies between current and past states

If previous state has utility -100 and current state has utility +100, increase previous state utility to lessen discrepancy

• Temporal difference (TD)
  • When observed transition from state $i$ to state $j$
  • $U(i) = U(i) + \alpha * (R(i) + U(j) - U(i))$
    • $\alpha$ = learning rate
    • $\alpha(N[i]) \sim 1/N[i]$
• Slower convergence