Dynamic Programming¶
Bellman, R. (1957). Dynamic Programming. Princeton University Press.
Cited by¶
16 citations across 16 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Backtracking
- Combining backtracking with memoisation yields a DP-like method, but they are distinct skeletons.
This sourceIntroduces dynamic programming, which reuses memoized subproblem solutions to avoid recomputation — distinct from plain backtracking.
- Combining backtracking with memoisation yields a DP-like method, but they are distinct skeletons.
- Constraint
- Curse Of Dimensionality
- The number of cells in a regular partition of a unit hypercube grows exponentially in the dimension.
This sourceCoins the "curse of dimensionality": exponential growth in the number of grid cells with dimension, defeating tabular dynamic programming and motivating mitigation.
- The number of cells in a regular partition of a unit hypercube grows exponentially in the dimension.
- Dimension
- Bellman's 1957 Dynamic Programming
This sourceIntroduces the principle of optimality and the Bellman equation, and coins 'the curse of dimensionality' for the exponential growth of sample/volume/search cost with dimension.
- Bellman's 1957 Dynamic Programming
- Dynamic Programming
- (2) The distinctive focus is on the recursive decomposition and the systematic reuse of subproblem solutions: where divide-and-conquer decomposes problems into independent subproblems (as in mergesort or quicksort), DP is the technique of choice when subproblems overlap — i.e., when the same subproblem appears many times in the recursive tree, making naive recursion catastrophically wasteful; where branch-and-bound explores a search tree pruning by dual bounds, DP exhaustively builds a table of optimal subproblem solutions and extracts the full problem's optimum by lookup.
This sourceFoundational monograph: introduces the principle of optimality ("an optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision") and codifies dynamic programming as a unifying framework for sequential decision-making under decomposability.
- (2) The distinctive focus is on the recursive decomposition and the systematic reuse of subproblem solutions: where divide-and-conquer decomposes problems into independent subproblems (as in mergesort or quicksort), DP is the technique of choice when subproblems overlap — i.e., when the same subproblem appears many times in the recursive tree, making naive recursion catastrophically wasteful; where branch-and-bound explores a search tree pruning by dual bounds, DP exhaustively builds a table of optimal subproblem solutions and extracts the full problem's optimum by lookup.
- Markov Decision Processes (MDPs)
- Markov Process
Domain-specific¶
- Bellman Equation
- This is Bellman's principle of optimality: an optimal policy has the property that, whatever the initial state and initial decision, the remaining decisions must constitute an optimal policy with respect to the state resulting from the first decision
This sourceBellman's principle of optimality, stated so that whatever the initial state and decision, the remaining decisions must constitute an optimal policy with regard to the state the first decision leaves.
SupportedVerified against the work's full text
“cases. It is the [principle] of [optimality] that furnishes the key. This [principle] tells us that”
- This is Bellman's principle of optimality: an optimal policy has the property that, whatever the initial state and initial decision, the remaining decisions must constitute an optimal policy with respect to the state resulting from the first decision
- Optimal Substructure
- Reinforcement learning
Mechanisms¶
- Coarse Grid Search
- First, cost explodes with dimensions — a grid of g points per axis over d axes is g^d evaluations, so even a coarse grid becomes unaffordable past a handful of dimensions, the curse of dimensionality.
This sourceThe cited work establishes First, cost explodes with dimensions; a grid of g points per axis over d axes is g^d evaluations; and so even a coarse grid becomes unaffordable past a handful of dimensions, the curse of dimensionality.
- First, cost explodes with dimensions — a grid of g points per axis over d axes is g^d evaluations, so even a coarse grid becomes unaffordable past a handful of dimensions, the curse of dimensionality.
- Dynamic Programming Recursion
- Epsilon-Net or Covering Grid
- The number of anchors needed to hold a fixed radius grows exponentially with dimension — the curse of dimensionality
This sourceIdentifies Bellman's curse of dimensionality as the computational burden created when a problem requires too many state-variable values.
- The number of anchors needed to hold a fixed radius grows exponentially with dimension — the curse of dimensionality
- Markov Decision Process Model
- The state space is also prone to blowing up: adding one variable multiplies the states, the curse of dimensionality
This sourceIdentifies rapid state-space growth and computational intractability in dynamic programming as the curse of dimensionality.
- The state space is also prone to blowing up: adding one variable multiplies the states, the curse of dimensionality
- Parameter Sweep Matrix
- Its failure mode is the curse of dimensionality
This sourceDefines the curse of dimensionality as multiplicative growth of grid size and computational cost as dimensions are added.
- Its failure mode is the curse of dimensionality
- Recurrence Equation
- Its failure mode is a state that doesn't capture everything the relation depends on — a recurrence that looks clean but references information its state variable doesn't carry, so the "smaller subproblems" it invokes are not actually determined, and every value computed from it is subtly wrong.
This sourceExplains that a dynamic-programming recurrence is valid only when its state captures the information needed to determine the remaining subproblem.
- Its failure mode is a state that doesn't capture everything the relation depends on — a recurrence that looks clean but references information its state variable doesn't carry, so the "smaller subproblems" it invokes are not actually determined, and every value computed from it is subtly wrong.
Verification¶
Does it exist? Not checked yet. This entry carries no identifier to resolve. It was extracted from the citation as written in the article, normalized, and deduplicated against the rest of the registry.
Does it back the claim? Read against the text for 1 of 16 citations: 1 supported. Each verdict is shown under its citation below, with what in the work backs the sentence.
Was it audited? Yes. A second, independent pass read the citation against the article text and recorded a verdict.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Links previously used in the corpus¶
Before the registry existed this work was also linked 5 other ways.
- https://books.google.com/books?id=ZzoS0QEACAAJ ×2
- https://assets.press.princeton.edu/chapters/i9234.pdf ×1
- https://books.google.com/books/about/Dynamic_Programming.html?id=ZzoS0QEACAAJ ×1
- https://lccn.loc.gov/57005444 ×1
- https://search.worldcat.org/title/dynamic-programming/oclc/220674 ×1
Registry ID ref:667f2fd1e03b · see in the full table