1
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ This is not dynamic programming. You are trying to find some sort of fixed point. $\endgroup$ – Yuval Filmus Apr 18 at 15:32
  • $\begingroup$ Yes, both of these problems are finding sort of fixed-points. But if the problem has optimal substructure and overlapping subproblems and we're using memoization to solve it, why is it not DP? $\endgroup$ – farhanhubble Apr 19 at 17:16
  • $\begingroup$ There's no formal definition of dynamic programming, but in my book, dynamic programming is just an implementation of memoization. In particular, it it an implementation of a well-founded recurrence. $\endgroup$ – Yuval Filmus Apr 19 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.