liveBook · Manning

Dynamic programming

As explained in Applied Reinforcement Learning

Dynamic programming is an algorithmic technique that solves sequential decision or optimization problems by decomposing them into overlapping subproblems and combining their solutions.

Dynamic programming plans in a Markov decision process (MDP) when the environment’s transition probabilities and rewards are known. Rather than learning from sampled experience, it uses this complete model to compute behavior through Bellman equations. section 4.0 section 4.1

Two iterative algorithms refine values and policies:

  • Value iteration recursively updates value functions toward convergence. section 4.1
  • Policy iteration recursively improves policies and value functions until convergence. section 4.1

Resource allocation and scale

A resource-allocation problem with a budget of 12 and four projects has 1,053 states. Raising the budget to 100 and the number of projects to 10 produces nearly six million states, illustrating how computation can grow. section 4.5

Figure 4.1 Five different paradigms in solving Markov decision process.

Compare dynamic programming with other paradigms for solving MDPs. section 4.1

The method’s main constraints are large state spaces and the need for a complete, accurate model. That makes it difficult to scale to complex real-world problems, while its Bellman-based ideas provide a foundation for reinforcement learning methods that work without a full model. section 4.5 section 6.7

How Applied Reinforcement Learning covers it

How deep it goes
Explains value and policy iteration, then identifies state-space growth and complete-model requirements as practical limits.
Examples
Uses resource allocation to illustrate state-space growth, comparing 1,053 states with nearly six million.
What it assumes
Assumes an MDP formulation and known transition probabilities and rewards rather than experience-based model learning.
What you can do after
Understand how known environment dynamics support planning and why state-space size can limit practical use.
How it connects
Connects MDPs, Bellman equations, value iteration, policy iteration, and model-free learning.

Also explained in

Compare how 8 books explain dynamic programming →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Applied Reinforcement Learning. The section links point to the parts of the book it draws on.