Algorithms like policy iteration and value iteration are often classified as dynamic programming methods that try to solve the Bellman optimality equations.

My current understanding of dynamic programming is this:

  1. It is a method applied to optimization problems.
  2. DP problems exhibit optimal substructure, i.e., the optimal solution to a problem contains the optimal solution to a subproblem.
  3. These subproblems are not independent of each other, but are overlapping.
  4. There are two approaches - one is a bottom-up, the other is top-down.

I have the following questions:

  1. Is this understanding of DP comprehensive? Does every DP algorithm have an optimal substructure with overlapping subproblems?

  2. How does policy iteration and value iteration fit into this scheme? Can we call it bottom-up or top-down?

  • $\begingroup$ You may have better luck getting an answer to this question at CS.SE, which has a dynamic programming tag. $\endgroup$ Commented Feb 3, 2017 at 14:20

1 Answer 1


Have you seen Silver's lecture? Did you know Bellman coined the dynamic programming term, his first book was called "Dynamic programming" in 1957, see Wikipedia?

  1. DP is an algorithm technique to problems that have an optimal substructure and overlapping subproblems. In contrast, if problems have the non-overlapping subproblems property, you only need to solve it once.
  2. In the top-down DP approach (see below) we find a solution based on previously stored results. In policy iteration (policy evaluation + iteration) and value iteration we update the value of each state, from older estimates of the optimal policy and state values.

I think there is also a difference between "classical" DP, because in policy and value iteration we apply update steps iteratively until convergence. In DP updates can be done in one pass.

enter image description here

enter image description here


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.