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
- Peter Stone
- Sergey Levine
- Matthew E. Taylor
- Pieter Abbeel
- Jan Peters
- Shimon Whiteson
- J. Urgen Schmidhuber
- Yoshua Bengio
In Mathematical Optimization
- Amy Greenwald
- Juan Carlos Santamaría
- Susan A. Murphy
- Peter Stone
- Min Qian
- Daniel J. Lizotte
- Richard S. Sutton
- Takeo Kanade
In Algorithms & Complexity
- Amy Greenwald
- Susan A. Murphy
- Peter Stone
- Min Qian
- Daniel J. Lizotte
- Richard S. Sutton
- Takeo Kanade
- Andrew W. Moore
Citations in the corpus
- Value Iteration Networks (2016, neutral): “A standard model for sequential decision making and planning is the Markov decision process (MDP) (Bellman, 1957; Bertsekas, 2012).”
- Unifying Count-Based Exploration and Intrinsic Motivation (2016, neutral): “g (Jaksch et al., 2010). Model-based interval estimation with exploratory bonus (MBIE-EB) is a simplification which augments the estimated reward function at every state and solves Bellman’s equation (Bellman, 1957): V(x) = max a2A " R^(x;a) + E x0˘P^(x;a) V(x0) + p N n(x;a) # ; where is a theor”
- Deep learning in neural networks: An overview (2014, neutral): “n some it would, e.g., Sec. 6.1. 6 4 Recurring Themes of Deep Learning 4.1 Dynamic Programming for Supervised / Reinforcement Learning (SL / RL) One recurring theme of DL is Dynamic Programming (DP) (Bellman, 1957), which can help to facilitate credit assignment under certain assumptions. For exampl”
- A survey of data fusion in smart city applications (2019, neutral): “approach has gained so much attention is due to its capability of handling high dimensional data. The problem of high dimensional data is also known as curse of dimensionality as described by Bellman [254]. In this context, we discuss two research trends on applying machine learning techniques in da”
- A practical tutorial on autoencoders for nonlinear feature fusion: Taxonomy, models, software and guidelines (2018, neutral): “k with raw input features, it is also true that, for the most part, their behavior is degraded as the number of variables grows. This is mainly due to the problem known as the curse of dimensionality [16], as well as the justi- cation for a eld of study called feature engineering. Engineering of fea”
- Reinforcement learning in robotics: A survey (2013, neutral): “In addition, as the dimensionality of both states and actions can be high, we face the “curse of dimensionality” (Bellman, 1957) as discussed in Section 3.1.”
- The value of precision feeding technologies for grow–finish swine (2010, neutral): “The economic model is based on a dynamic optimisation, which follows the Bellman equation (Bellman, 1957) of the form:”
- Path Planning for Autonomous Mobile Robots: A Review (2021, neutral): “In the first of them, PDE Solving , algorithms solve a Partial Derivative Equation (PDE) on a grid, based on the Dynamic Programming Principle (DPP) [203].”
- Projection Pursuit Multivariate Transform (2014, neutral): “While very effective in certain settings, these techniques suffer from issues related to the curse of dimensionality with an increasing number of variables (Bellman 1957); say more than 2–4 variables depending on the available number of data.”
- Convex Optimization: Algorithms and Complexity (2015, neutral): “The Markov Decision Process (MDP) is a framework for sequential decision-making in Markovian dynamical systems [Bellman, 1957, Puterman, 1994].”