I am trying to explain the value iteration method that is used in reinforcement learning. The method is used to estimate a solution to a recursive equation like:
$ Return(state_t,action_t) = Reward(state_t,state_{t+1}) + \gamma * \max \begin{bmatrix} Return(state_{t+1}, action_{t+1}=='n')\\ Return(state_{t+1}, action_{t+1}=='e')\\ Return(state_{t+1}, action_{t+1}=='w')\\ Return(state_{t+1}, action_{t+1}=='s') \end{bmatrix}$
Normally, if the sub-problems(RHS) are overlapping, a problem like this can be solved using recursive or iterative dynamic programming. However, in the case of reinforcement learning the recursion is often mutual, and thus the dynamic programming solution has no natural point of termination.
The value iteration method works by filling up the memorization table with arbitrary values and then repeatedly applying the recursive equation to every cell in the table until the values in the cell converge.
A similar approach is used in the HITS algorithm where the hub and authority values have mutual recursion.
Are there any good resources, preferably online, that deal with the application of dynamic programming to problems with mutual, indefinite recursion?
