Two Methods For Updating Utility Values

• Naive
  • Least mean squares
  • U[i] = RunningAverage(U[i], CumReward, N[i])
  • N[i] is number of times visit state i
  • Does not use transition probabilities constraints
  • Converges slowly
• Adaptive dynamic programming (ADP)
  • 
  • $R(i)$ = reward for being in state $i$
  • is probability of transition from state $i$ to state $j$
  • Solve $n$ equations in $n$ unknowns, $n = \vert states\vert$
  • Is this practical?