Dynamic Programming

By Ryuichi Oka, Martin L. Puterman, Jonathan Patrick, Aizu Wakamatsu. 2018

7,395 citations recorded by the source corpus.

We have now studied two ways of solving dynamic optimization problems, one based on the Kuhn-Tucker theorem and the other based on the maximum principle. These two methods both lead us to the same sets of optimality conditions; they differ only in terms of how those optimality conditions are derived. Here, we will consider a third way of solving dynamic optimization problems: the method of dynamic programming. We will see, once again, that dynamic programming leads us to the same set of optimality conditions that the Kuhn-Tucker theorem does; once again, this new method differs from the others only in terms of how the optimality conditions are derived. While the maximum principle lends itself equally well to dynamic optimization problems set in both discrete time and continuous time, dynamic programming is easiest to apply in discrete time settings. On the other hand, dynamic programing, unlike the Kuhn-Tucker theorem and the maximum principle, can be used quite easily to solve problems in which optimal decisions must be made under conditions of uncertainty. Thus, in our discussion of dynamic programming, we will begin by considering dynamic programming under certainty; later, we will move on to consider stochastic dynamic programming.

Subfields: Artificial Intelligence, Mathematical Optimization, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

  1. Peter Stone
  2. Sergey Levine
  3. Matthew E. Taylor
  4. Pieter Abbeel
  5. Jan Peters
  6. Shimon Whiteson
  7. J. Urgen Schmidhuber
  8. Yoshua Bengio

In Mathematical Optimization

  1. Amy Greenwald
  2. Juan Carlos Santamaría
  3. Susan A. Murphy
  4. Peter Stone
  5. Min Qian
  6. Daniel J. Lizotte
  7. Richard S. Sutton
  8. Takeo Kanade

In Algorithms & Complexity

  1. Amy Greenwald
  2. Susan A. Murphy
  3. Peter Stone
  4. Min Qian
  5. Daniel J. Lizotte
  6. Richard S. Sutton
  7. Takeo Kanade
  8. Andrew W. Moore

Citations in the corpus