Chapter 4: Perfect Knowledge, Optimal Policy: Dynamic Programming
This introduction contrasts model-based and model-free methods and situates dynamic programming as a recursive approach to solving Markov decision processes with a known model.
After this chapter you will be able to
- Model Based and Model Free Methods. Distinguish model-based planning from model-free learning, including their use of rewards and transition information.
- Dynamic Programming Under Uncertainty. Explain how dynamic programming adapts recursive problem decomposition to a stochastic Markov decision process.
- Bandit decisions and exploration. Explain how multi-armed bandits learn from repeated action rewards and balance exploration against exploitation.
- Temporal difference stepwise learning. Describe how temporal difference learning updates value estimates as experience arrives and why it need not wait for a complete episode.
- Monte Carlo complete returns. Explain how Monte Carlo learning uses complete episode outcomes and distinguish its timing and trade-offs from stepwise learning.
- Dynamic programming with models. Explain how dynamic programming uses a complete environment model to compute optimal behavior and why that assumption limits direct use.
- Tree search through simulation. Describe how tree search simulates possible actions and outcomes to guide a current decision.
- Bellman Recursive Decomposition. Explain how a Bellman equation relates immediate reward to future value and why this matters for sequential decisions.
- State Value Backup. Trace how the state-value equation evaluates a state under a given policy.
- Action Value Backup. Trace how the action-value equation evaluates a specific action and distinguish its backup from the state-value backup.
- State and Action Value Relationship. Explain how state value relates to action values under the same policy and why both views are useful.
- Advantage Function Comparison. Explain what the advantage function compares and how to interpret its sign.
- Generalized policy iteration loop. Explain how generalized policy iteration alternates policy evaluation and greedy policy improvement to find a policy for long-term return.
- Inventory iteration calculations. Trace how the example evaluates and improves its initial order-one policy over two rounds.
- Adaptive inventory policy. Explain the example's stabilized inventory policy and the business trade-offs behind it.
- Allocation States and Actions. Describe the state and valid actions in the resource allocation MDP, including the option to stop allocating.
- Uncertain Project Success. Explain how allocation affects a project’s success probability and the trade-off this creates.
- Allocation Reward Structure. Describe how the reward accounts for project outcomes, investment costs, and unused budget.
- Policy Evaluation and Improvement. Distinguish policy evaluation from policy improvement and explain how each uses possible future outcomes.
- Solver Iteration and Stopping. Trace the implementation’s initialization, alternating updates, and stopping condition.
- Massive State Space. Explain why a large or continuous state space makes dynamic programming impractical, using the resource allocation example.
- Perfect Model Requirement. Explain why dynamic programming requires a perfect model and why that limits its use in real-world problems.
- Foundational Value of Dynamic Programming. Describe why dynamic programming remains valuable to reinforcement learning despite its practical limitations.
What it builds on
- Markov decision process (chapter 2) · The Markov decision process and its state, action, transition, and reward components.
- Markov chain and Markov property (chapter 2) · The Markov property underlies the one-step decomposition.
- Use action masking with penalties to handle hard constraints (chapter 2) · The need to restrict invalid actions.
- Handle soft constrains with stepwise penalties (chapter 2) · Using penalties to represent undesirable outcomes.
- Avoid mismatched scales with reward normalization / balancing (chapter 2) · Balancing reward components.
Section by section
Introduction
This introduction contrasts model-based and model-free methods and situates dynamic programming as a recursive approach to solving Markov decision processes with a known model.
- Model Based and Model Free Methods: Distinguish model-based planning from model-free learning, including their use of rewards and transition information.
Why it matters: This distinction helps you understand the main choices for solving a decision problem. - Dynamic Programming Under Uncertainty: Explain how dynamic programming adapts recursive problem decomposition to a stochastic Markov decision process.
Why it matters: This connects the familiar idea of reusing subproblem solutions to decision-making under uncertainty. - Dynamic Programming Practical Limitations: Describe why dynamic programming can be difficult to use in real-world settings.
Why it matters: Knowing these limitations helps you recognize when a clean theoretical approach may be hard to apply.
Key terms: model-based methods, model-free methods, transition function, reward function, sampled transitions, dynamic programming, overlapping subproblems, recursive components, stochastic environments, transition and reward information
4.1 Paradigms on solving Markov decision process
This section compares five decision-making paradigms by how they use rewards, experience, models, and simulated futures.
- Bandit decisions and exploration: Explain how multi-armed bandits learn from repeated action rewards and balance exploration against exploitation.
Why it matters: This distinction helps identify decisions that can be treated as repeated choices without modeling future states. - Temporal difference stepwise learning: Describe how temporal difference learning updates value estimates as experience arrives and why it need not wait for a complete episode.
Why it matters: Stepwise updates allow learning in ongoing processes where waiting for a complete outcome is impractical. - Monte Carlo complete returns: Explain how Monte Carlo learning uses complete episode outcomes and distinguish its timing and trade-offs from stepwise learning.
Why it matters: Understanding the wait for complete outcomes helps explain when learning may be slow or noisy. - Dynamic programming with models: Explain how dynamic programming uses a complete environment model to compute optimal behavior and why that assumption limits direct use.
Why it matters: The full-model assumption explains both the power of dynamic programming and why it may be impractical in real businesses. - Tree search through simulation: Describe how tree search simulates possible actions and outcomes to guide a current decision.
Why it matters: Simulating alternatives lets a decision-maker compare possible consequences before acting.
Key terms: Multi-Armed Bandits, exploration-exploitation trade-off, temporal difference learning, bootstrapping, value estimates, Monte Carlo learning, episode, full return, variance, dynamic programming
4.2 The domino decision rule: Bellman equations
This section explains Bellman equations as recursive ways to evaluate states and actions under a policy, and relates their values to the advantage function.
- Bellman Recursive Decomposition: Explain how a Bellman equation relates immediate reward to future value and why this matters for sequential decisions.
Why it matters: This decomposition lets you reason about consequences beyond the next reward. - State Value Backup: Trace how the state-value equation evaluates a state under a given policy.
Why it matters: This shows how a policy and uncertain transitions together determine a state's expected value. - Action Value Backup: Trace how the action-value equation evaluates a specific action and distinguish its backup from the state-value backup.
Why it matters: Action values let you compare specific choices while accounting for what the policy does afterward. - State and Action Value Relationship: Explain how state value relates to action values under the same policy and why both views are useful.
Why it matters: The relationship connects an overall state assessment to the individual actions that produce it. - Advantage Function Comparison: Explain what the advantage function compares and how to interpret its sign.
Why it matters: Advantage puts an action's value in context by comparing it with the policy's usual choices in the same state.
Key terms: Bellman equations, immediate reward, discounted expected value, domino rule, state-value function, Vπ(s), policy, discount factor, backup diagram, action-value function
4.3 Solving bellman equations: Generalized Policy Iteration
This section explains generalized policy iteration and demonstrates policy evaluation and improvement with a simplified inventory problem.
- Generalized policy iteration loop: Explain how generalized policy iteration alternates policy evaluation and greedy policy improvement to find a policy for long-term return.
Why it matters: This feedback loop turns value estimates into progressively better decisions. - Inventory example model: Describe the simplified inventory problem's states, actions, demand, and transition rule.
Why it matters: The model defines the decisions and consequences that the worked example evaluates. - Inventory iteration calculations: Trace how the example evaluates and improves its initial order-one policy over two rounds.
Why it matters: The calculations show how the abstract evaluation-improvement loop operates on a concrete business problem. - Adaptive inventory policy: Explain the example's stabilized inventory policy and the business trade-offs behind it.
Why it matters: The result illustrates why a state-dependent decision can outperform a fixed ordering rule within the example's assumptions.
Key terms: Generalized Policy Iteration, Policy Evaluation, Policy Improvement, Bellman expectation equations, greedy, discounted value, state, action, transition dynamics, deterministic demand
4.4 Hands-on code: solving a resource allocation problem
This section models a startup’s resource allocation problem as an MDP, solves it with generalized policy iteration, and interprets the resulting policy.
- Allocation States and Actions: Describe the state and valid actions in the resource allocation MDP, including the option to stop allocating.
Why it matters: The state and action constraints define which decisions the solver can make at each point. - Uncertain Project Success: Explain how allocation affects a project’s success probability and the trade-off this creates.
Why it matters: The probability model makes the cost of buying more confidence explicit. - Allocation Reward Structure: Describe how the reward accounts for project outcomes, investment costs, and unused budget.
Why it matters: The reward determines which financial and behavioral trade-offs the policy optimizes. - Policy Evaluation and Improvement: Distinguish policy evaluation from policy improvement and explain how each uses possible future outcomes.
Why it matters: Separating the two steps shows how the solver measures a strategy and then makes better choices. - Solver Iteration and Stopping: Trace the implementation’s initialization, alternating updates, and stopping condition.
Why it matters: This is how the example combines evaluation and improvement into a runnable solver. - State Dependent Allocation Results: Describe how the plotted first investment choice changes with the available budget in the example.
Why it matters: The visualization shows how an optimal decision can change with the resources available.
Key terms: budget remaining, project status vector, action space, do nothing, action constraints, transition probability function, base success probability, enhancement factor, allocation, reward function
4.5 Limitations of dynamic programming
This section explains why dynamic programming is difficult to apply at scale despite its foundational role in reinforcement learning.
- Massive State Space: Explain why a large or continuous state space makes dynamic programming impractical, using the resource allocation example.
Why it matters: The size of the state space can make an otherwise sound planning method impossible to run. - Perfect Model Requirement: Explain why dynamic programming requires a perfect model and why that limits its use in real-world problems.
Why it matters: A planning method that needs known rules is hard to apply when those rules cannot be specified accurately. - Foundational Value of Dynamic Programming: Describe why dynamic programming remains valuable to reinforcement learning despite its practical limitations.
Why it matters: Dynamic programming helps explain the principles behind methods designed for problems where its direct use is too costly.
Key terms: curse of a massive state space, value function, state, curse of a perfect model, transition probabilities, reward function, planning algorithm, model-free methods, generalized policy iteration, Bellman equations
4.6 Summary
Where this is used later
- Temporal difference learning (chapter 6) · Provides context for learning from experience without a known transition function.
- Bandits as lightweight reinforcement learning (chapter 5) · Provides the basic one-step decision setting for bandits.
- Tradeoff between exploitation and exploration (chapter 5) · Introduces the tension between trying alternatives and using the current best choice.
- (chapter intro) (chapter 7) · Paradigms for solving sequential decision problems.
- Tree data structure and its applications in business (chapter 7) · Builds on the representation of alternatives as branches in a tree.
- Monte Carlo tree search theory and algorithm (chapter 7) · Develops a reinforcement-learning-based tree search approach.
- Tabular Reinforcement Learning: Q-learning and SARSA (chapter 6) · Tabular methods use action values to assess choices.
- Variance reduction through baselines (chapter 9) · Baselines provide context for assessing actions in policy-based methods.
Concepts explained in this chapter
- Bellman equationA Bellman equation expresses the value of a state or state-action pair as an immediate reward plus the appropriately discounted value of future states.
- value functionA value function estimates the expected cumulative return from a state or state-action pair under a specified policy or optimal behavior.
- action-value functionAn action-value function maps a state-action pair to the expected return from taking the action and then following a policy.
- value iterationValue iteration is a dynamic-programming algorithm that repeatedly applies a Bellman optimality update to approximate optimal state values and derive an optimal policy.
- generalized policy iterationGeneralized policy iteration is a reinforcement-learning framework that alternates policy evaluation with policy improvement until the policy stabilizes or reaches an optimum.
- policy evaluationPolicy evaluation is the process of estimating the value of states or state-action pairs under a fixed policy.
- policy improvementPolicy improvement is the process of deriving a policy that selects actions with higher estimated value than the current policy.
- policyA policy is a decision rule, possibly probabilistic, that assigns actions or action probabilities to states for an agent.
- state spaceA state space is the set of possible states of an environment in a decision process.
- Markov decision processA Markov decision process is a formal model of sequential decision-making in which an agent selects actions in states, receives rewards, and causes probabilistic transitions whose relevant future behavior depends on the current state.
- action spaceAn action space is the set or structured specification of actions that an agent can submit to an environment.
- constraintA restriction that limits the values or combinations allowed in an optimization problem, including which actions are valid in a state.
- resource allocation problemA resource allocation problem is a decision problem that assigns limited resources among competing activities to optimize an objective subject to constraints.
- reward functionA reward function is a mapping that assigns numerical feedback to states, actions, transitions, or outcomes in a decision process.
- transition dynamicThe rules governing how an environment changes from one state to another after an action, including effects of randomness.
- transition probabilityA transition probability is the probability of moving from one state to another in a stochastic system.
- greedy policyA greedy policy selects the product with the lower current stock level, resolving equal stock levels by choosing scooter.
- dynamic programmingDynamic programming is an algorithmic technique that solves sequential decision or optimization problems by decomposing them into overlapping subproblems and combining their solutions.
- advantage functionAdvantage measures how much an action's expected return exceeds or falls below the value of its state under a policy.
- discount factorA numerical factor that determines how strongly future rewards and values are weighted relative to immediate rewards.
- model-free methodModel-free learning is reinforcement learning in which an agent learns action selection directly from experience without an explicit environment transition model.
- model-based approachA model-based method solves a decision problem by using a known or learned model of the environment to plan ahead.
- sequential decision-makingA decision process in which actions are chosen over multiple steps while relevant states, outcomes, or future conditions are not fully known.
- curse of dimensionalityThe curse of dimensionality is the rapid growth of computational complexity as the number of dimensions or tracked variables increases.
- convergenceConvergence is the approach of successive numerical estimates or policies toward a stable limiting result.
- Monte Carlo simulationMonte Carlo estimation approximates a quantity by averaging values obtained from random samples.
- TD-learningTemporal-difference learning updates value estimates incrementally using observed rewards and estimates of subsequent values.
- bootstrappingBootstrapping is an estimation technique that updates a prediction using another prediction or value estimate rather than waiting for a complete realized outcome.
- exploration-exploitation trade-offThe exploration-exploitation trade-off is the tension between gathering information through unfamiliar actions and selecting actions currently expected to yield high rewards.
- multi-armed banditA multi-armed bandit is a sequential decision model in which an agent repeatedly chooses among actions and observes their rewards without modeled state transitions.
- search treeA search tree is a branching data structure whose nodes represent states or decision points and whose edges represent possible actions or outcomes.
- tree searchTree search is a planning technique that represents possible action sequences and outcomes as branches of a search tree and uses them to guide decisions.
- experienceExperience is a recorded interaction tuple containing a state, action, reward, and next state.
These guides are generated from the text of Manning books by Manning's knowledge graph and link to the sections they draw on. The full books are available on liveBook and at manning.com.
