This chapter introduces dynamic programming as the most direct way to solve a Markov decision process when the environment model is known. It contrasts model-based and model-free approaches, then positions dynamic programming as a planning method that uses transition probabilities and rewards to reason about future outcomes rather than relying only on experience. The key idea is to break decision-making into smaller recursive pieces and combine immediate reward with the discounted value of what follows.
The central mathematical tool is the Bellman equation, which decomposes the value of a state or action into present reward plus expected future value. The chapter explains both state-value and action-value functions, and uses backup diagrams to build intuition for how value is propagated backward through time. It also introduces the advantage function as a way to compare a specific action against the average behavior in a state. On top of this foundation, generalized policy iteration alternates between evaluating a policy and improving it, gradually pushing behavior toward optimality.
To make the method concrete, the chapter walks through two numerical applications: a small inventory-management problem and a resource-allocation problem implemented in code. In both examples, iterative evaluation and greedy improvement lead to stable policies that balance immediate costs against long-term gains. The resource-allocation case shows how a planner can learn state-dependent investment choices under uncertainty. The chapter closes by emphasizing dynamic programming’s major limitations: it becomes expensive in large state spaces and requires a complete model, which is rarely available in real-world problems.
Five different paradigms in solving Markov decision process.
State value function representation
Backup diagram for state value function.
Action value function representation.
Backup diagram for action value function.
General algorithm and schema of general policy iteration algorithm.
Generalized policy iteration algorithm.
Visualization of results for resource allocation problem.
Summary
Dynamic programming is a collection of model-based algorithms used to solve Markov decision processes by breaking a problem into a sequence of smaller, recursive subproblems.
Fundamental requirement of dynamic programming is the perfect model of the environment, meaning the state transition probabilities and reward function are completely and fully given and known.
The Bellman equations are the core mathematical tool, defining the value of a state or state-action pair recursively in terms of the values of successor states.
We use two key metrics: the state-value function which measures the long-term value of being in a state, and the action-value function which measures the value of taking an action from that state.
Generalized Policy Iteration is the central pattern for solving Markov decision process, involving an interaction between two processes:
Policy Evaluation: Calculating the value function for the current policy.
Policy Improvement: Greedily updating the policy based on the current values.
Value Iteration is an efficient dynamic programming algorithm that combines a single sweep of evaluation with an improvement step in each iteration, guaranteeing convergence to the optimal policy.
The hands-on resource allocation example showed dynamic programming uncovering a nuanced strategy—be conservative with low budgets, takes balanced actions with medium budgets, and acts opportunistically with high budgets.
Dynamic programming is severely limited by the curse of dimensionality, making it computationally and memory-wise intractable for problems with large state spaces.
The requirement of a perfect model is a second major weakness of dynamic programming as such models are unavailable or inaccurate for most real-world problems, motivating the need for model-free methods.
FAQ
What is dynamic programming in reinforcement learning, and how is it different from dynamic programming in classic computer science?Dynamic programming in reinforcement learning is a planning method for Markov decision processes that assumes the environment model is known, especially the transition probabilities and reward function. Unlike classic deterministic dynamic programming, which often solves overlapping subproblems in fixed algorithms, RL dynamic programming works in stochastic settings and uses Bellman equations to evaluate and improve policies.Why is dynamic programming considered a model-based method?It is model-based because it relies on having access to a model of the environment: the transition function P(s′|s,a) and the reward function R(s,a,s′). Using that model, the agent can plan ahead by computing expected future returns instead of learning only from experience.What are Bellman equations in simple terms?Bellman equations express the value of a state or action as the sum of immediate reward plus discounted expected future value. In other words, they break a long-term decision into the current payoff and the value of what happens next.What is the difference between the state-value function Vπ(s) and the action-value function Qπ(s,a)?Vπ(s) tells you how good it is to be in a state when following policy π, while Qπ(s,a) tells you how good it is to take a specific action in that state and then follow π afterward. V is state-focused; Q is action-focused.What does the advantage function measure?The advantage function Aπ(s,a) = Qπ(s,a) - Vπ(s) measures how much better or worse a particular action is compared with the average action under the policy in that state. Positive advantage means the action is better than average; negative means worse.What is generalized policy iteration?Generalized policy iteration is the alternating loop of policy evaluation and policy improvement. First, the current policy is evaluated using Bellman expectation equations; then the policy is improved by choosing actions greedily with respect to the estimated values. Repeating this process leads toward an optimal policy.How does policy evaluation work in generalized policy iteration?Policy evaluation estimates the value function for the current policy by repeatedly applying the Bellman expectation equation until the values stabilize. Each state’s value is updated using the expected reward and discounted value of successor states under the current policy.How does policy improvement choose a better policy?Policy improvement computes the expected return for all valid actions in each state using the current value estimates, then selects the action with the highest expected value. This greedy update replaces the old action choice with a better one for that state.What was the optimal inventory policy in the chapter’s numerical example?The optimal policy found by generalized policy iteration was {0→2, 1→1, 2→0, 3+→0}. That means order 2 units when inventory is 0, order 1 unit when inventory is 1, and order nothing when inventory is 2 or more.What are the main limitations of dynamic programming?The two major limitations are the curse of dimensionality and the need for a perfect model. Dynamic programming requires iterating over all states, which becomes infeasible in large spaces, and it also assumes the transition and reward model is known exactly, which is rarely true in real-world problems.
pro $24.99 per month
access to all Manning books, MEAPs, liveVideos, liveProjects, and audiobooks!
Applied Reinforcement Learning ebook for free
