Dynamic Programming and Planning

Introduction and Context

Reinforcement learning (RL) concerns sequential decision-making by an agent interacting with an environment. At each time step, the agent observes a state, selects an action, receives a reward, and moves to a new state. In many RL problems the transition dynamics and reward mechanism are initially unknown, so the agent must learn from experience. However, in some settings an environment model is available. A model specifies the probability of each next state and reward for every state–action pair. When such a model is available, the agent can reason about future consequences without collecting new interaction data. This process is called planning.

Dynamic programming (DP) provides a family of planning methods for finite Markov decision processes (MDPs). The principal methods are policy evaluation, policy improvement, policy iteration, value iteration, and asynchronous dynamic programming. These methods are foundational because they introduce the Bellman equations, establish the relationship between prediction and control, and provide the conceptual basis for many modern RL algorithms.

This chapter assumes a finite state set and finite action set, a known model, and either episodic tasks or continuing discounted tasks. The methods are exact in principle, although practical implementations may use approximations, stopping thresholds, or limited computation.

Learning Objectives

By the end of this chapter, you should be able to:

1. Define an MDP model and distinguish prediction from control.

2. Derive and interpret the Bellman expectation and optimality equations.

3. Implement iterative policy evaluation.

4. Explain and implement policy improvement and policy iteration.

5. Derive value iteration and relate it to generalized policy iteration.

6. Explain asynchronous dynamic programming and its convergence requirements.

7. Select an appropriate planning method and analyze its assumptions, limitations, and practical implications.

The Model-Based Reinforcement-Learning Setting

An MDP is described by the tuple \((\mathcal{S},\mathcal{A},p,r,\gamma)\), where:

• \(\mathcal{S}\) is the set of states;
• \(\mathcal{A}(s)\) is the set of actions available in state \(s\);
• \(p(s',r\mid s,a)\) is the probability of moving to state \(s'\) and receiving reward \(r\) after taking action \(a\) in state \(s\);
• \(r\) is the immediate reward; and
• \(\gamma\in[0,1]\) is the discount factor.

The model must satisfy

\[

\sum_{s'\in\mathcal{S}}\sum_r p(s',r\mid s,a)=1.

\]

For a policy \(\pi(a\mid s)\), the return from time \(t\) is

\[

G_t=R_{t+1}+\gamma R_{t+2}+\gamma^2R_{t+3}+\cdots.

\]

The state-value function and action-value function are

\[

v_\pi(s)=\mathbb{E}_\pi[G_t\mid S_t=s],

\qquad

q_\pi(s,a)=\mathbb{E}_\pi[G_t\mid S_t=s,A_t=a].

\]

These expectations are taken over the environment transitions and, when relevant, the policy's action choices.

A model enables direct computation of expected future value:

\[

v_\pi(s)=\sum_a\pi(a\mid s)\sum_{s',r}p(s',r\mid s,a)[r+\gamma v_\pi(s')].

\]

This is the Bellman expectation equation. It is an exact consistency relationship: the value of a state equals the expected immediate reward plus discounted value of the next state.

For a deterministic policy \(\pi(s)\), the equation reduces to

\[

v_\pi(s)=\sum_{s',r}p(s',r\mid s,\pi(s))[r+\gamma v_\pi(s')].

\]

If transitions and rewards are deterministic, it simplifies further to

\[

v_\pi(s)=r(s,\pi(s),s')+\gamma v_\pi(s').

\]

The last expression is a special case and must not be used when outcomes are stochastic without taking an expectation.

Prediction: Iterative Policy Evaluation

Prediction means computing the value of a given policy. Although the Bellman expectation equations form a system of linear equations, direct matrix solution can be expensive for large state spaces. Iterative policy evaluation instead repeatedly applies a Bellman backup.

Given an estimate \(V\), the one-step backup for state \(s\) is

\[

V_{\text{new}}(s)=\sum_a\pi(a\mid s)\sum_{s',r}p(s',r\mid s,a)[r+\gamma V(s')].

\]

Starting from an arbitrary bounded value function, such as \(V(s)=0\), the estimates are updated until the largest change is below a tolerance \(\theta>0\):

\[

\Delta=\max_s|V_{\text{new}}(s)-V(s)|.

\]

For a finite discounted MDP with \(\gamma<1\), the Bellman expectation operator is a contraction under the maximum norm. Consequently, repeated synchronous backups converge to the unique value function \(v_\pi\), provided the model is correctly specified.

Iterative Policy Evaluation: Pseudocode

```text

Input: policy π, model p, discount γ, threshold θ

Initialize V(s) arbitrarily for every nonterminal state

Repeat:

Δ ← 0

For each state s:

old ← V(s)

V(s) ← Σa π(a|s) Σs',r p(s',r|s,a)[r + γV(s')]

Δ ← max(Δ, |old − V(s)|)

Until Δ < θ

Return V

```

The displayed pseudocode uses in-place updates if the newly computed values are immediately available to later states. A strictly synchronous implementation stores all new values separately and replaces the old vector after a complete sweep. Both versions converge under standard conditions, although their numerical trajectories differ.

Worked Example: Evaluating a Fixed Policy

Consider two nonterminal states, \(A\) and \(B\), and a terminal state whose value is zero. Under a fixed policy:

• From \(A\), the agent receives reward 2 and moves to \(B\) with certainty.
• From \(B\), the agent receives reward 1 and returns to \(A\) with certainty.

Let \(\gamma=0.5\). The Bellman equations are

\[

v(A)=2+0.5v(B),

\qquad

v(B)=1+0.5v(A).

\]

Substitution gives

\[

v(A)=2+0.5(1+0.5v(A))=2.5+0.25v(A),

\]

so \(0.75v(A)=2.5\), yielding

\[

v(A)=\frac{10}{3}\approx3.333,

\qquad

v(B)=1+0.5\left(\frac{10}{3}\right)=\frac{8}{3}\approx2.667.

\]

Iterative evaluation approaches these values from any bounded initialisation. For example, starting with zeros, the first synchronous sweep gives \(V(A)=2\) and \(V(B)=1\); the second gives \(V(A)=2.5\) and \(V(B)=2\).

Control Through Policy Improvement

Control means finding an optimal policy rather than merely evaluating a specified one. Once \(v_\pi\) is known, the value of selecting action \(a\) in state \(s\) and then following \(\pi\) is

\[

q_\pi(s,a)=\sum_{s',r}p(s',r\mid s,a)[r+\gamma v_\pi(s')].

\]

A greedy policy with respect to \(v_\pi\) chooses

\[

\pi'(s)\in\arg\max_{a\in\mathcal{A}(s)}q_\pi(s,a).

\]

If the current policy is stochastic, an improved policy may assign probability one to a maximizing action, with a specified tie-breaking rule when several actions maximize the expression.

The policy improvement theorem states that if \(\pi'\) is greedy with respect to \(v_\pi\), then

\[

v_{\pi'}(s)\ge v_\pi(s)\quad\text{for every }s.

\]

If the inequality is strict for at least one state under appropriate reachability conditions, improvement is strict for at least one state. The theorem follows because choosing the greedy action is at least as good as following \(\pi\) for one step, after which the improved policy continues to act at least as well. In a finite MDP, repeated improvement cannot continue indefinitely through distinct deterministic policies; it therefore reaches an optimal policy.

Policy improvement should not be confused with simply selecting the action with the largest immediate reward. The comparison uses immediate reward plus discounted expected future value. A temporarily unattractive action may be optimal because it leads to valuable states.

Policy Iteration

Policy iteration alternates complete policy evaluation and policy improvement:

1. Start with an arbitrary policy \(\pi_0\).

2. Evaluate \(\pi_k\) to obtain \(v_{\pi_k}\).

3. Improve the policy greedily using \(v_{\pi_k}\).

4. Stop if the policy does not change; otherwise repeat.

```text

Input: model p, discount γ

Initialize a policy π

Repeat:

Evaluate π to obtain Vπ

policy_stable ← true

For each state s:

old_action ← π(s)

π(s) ← argmaxa Σs',r p(s',r|s,a)[r + γVπ(s')]

If old_action ≠ π(s): policy_stable ← false

If policy_stable: return π, Vπ

```

When a policy is stable under greedy improvement, it satisfies the Bellman optimality condition and is optimal under the standard finite discounted assumptions. In practice, exact evaluation is not always necessary. Truncated or approximate evaluation can be sufficient, leading to modified policy iteration.

Value Iteration

Policy iteration performs a full evaluation before each improvement. Value iteration combines these operations into a single optimality backup:

\[

V_{k+1}(s)=\max_{a\in\mathcal{A}(s)}

\sum_{s',r}p(s',r\mid s,a)[r+\gamma V_k(s')].

\]

The Bellman optimality equation is

\[

v_(s)=\max_a\sum_{s',r}p(s',r\mid s,a)[r+\gamma v_(s')].

\]

For finite discounted MDPs, the Bellman optimality operator is a contraction with factor \(\gamma\). Thus value iteration converges to the unique optimal value function from any bounded initial value function. An optimal deterministic policy can then be extracted by

\[

\pi_*(s)\in\arg\max_a\sum_{s',r}p(s',r\mid s,a)[r+\gamma V(s')].

\]

```text

Input: model p, discount γ, threshold θ

Initialize V(s) arbitrarily

Repeat:

Δ ← 0

For each state s:

old ← V(s)

V(s) ← maxa Σs',r p(s',r|s,a)[r + γV(s')]

Δ ← max(Δ, |old − V(s)|)

Until Δ < θ

For each state s:

π(s) ← argmaxa Σs',r p(s',r|s,a)[r + γV(s')]

Return π, V

```

A useful error bound explains the stopping rule. If the maximum change in a synchronous value-iteration sweep is at most \(\delta\), then, under standard discounted assumptions, the distance between the current value and the optimal value can be bounded using a factor proportional to \(\gamma/(1-\gamma)\). A commonly used sufficient criterion is to stop when \(\Delta<\theta\) with \(\theta\) selected according to the desired value accuracy; exact policy stability can also be checked separately. The precise bound depends on whether \(\Delta\) is measured before or after a complete contraction sweep, so implementations should document their convention.

Policy Iteration and Value Iteration Compared

Policy iteration may require expensive policy-evaluation sweeps but often needs relatively few policy changes. Value iteration performs inexpensive one-step optimality backups and may require more sweeps. Policy iteration is attractive when accurate values for each candidate policy are useful; value iteration is attractive when rapid approximate control is preferred. Both require enumeration of model outcomes and therefore can become impractical when the state or action space is very large.

Generalized Policy Iteration

Generalized policy iteration (GPI) is the general pattern of interleaving two processes:

• Policy evaluation: make the value estimate more consistent with the current policy.
• Policy improvement: make the policy more greedy with respect to the current value estimate.

The processes need not be completed exactly or in a fixed order. Policy iteration is GPI with complete evaluation; value iteration is GPI with extremely limited evaluation, often one optimality backup per sweep. Many RL algorithms can be understood through this perspective. For example, approximate actor–critic methods maintain a policy-like actor and a value-estimating critic, although they generally do not have an exact model and use sampled updates.

GPI is conceptually important because it separates two sources of progress: improving knowledge of the consequences of a policy and improving the policy based on current knowledge. If evaluation is too weak, improvement may be based on inaccurate values. If evaluation is excessively precise, computation may be spent estimating a policy that will soon be discarded. Good algorithms balance these costs.

Asynchronous Dynamic Programming

Synchronous DP updates every state in an organised sweep. Asynchronous dynamic programming updates only selected states at selected times. For a policy-evaluation backup, an individual update may be

\[

V(s)\leftarrow\sum_a\pi(a\mid s)\sum_{s',r}p(s',r\mid s,a)[r+\gamma V(s')].

\]

For value iteration, it may be

\[

V(s)\leftarrow\max_a\sum_{s',r}p(s',r\mid s,a)[r+\gamma V(s')].

\]

Other state values are left unchanged.

Asynchronous methods are useful when:

• only a subset of states is relevant to a current decision;
• computational resources are distributed across processors;
• states can be prioritised according to estimated importance or Bellman error;
• memory or latency constraints make full sweeps undesirable.

For discounted finite MDPs, convergence is guaranteed under fair updating conditions: every state must be updated sufficiently often, and the updates must use increasingly accurate backups. Updating only a permanently restricted subset of states generally does not guarantee a correct global solution. Terminal states should be handled consistently, usually by fixing their value at zero or by incorporating their terminal reward into the preceding transition.

A simple asynchronous value-iteration scheme is:

```text

Initialize V

For t = 1, 2, …:

Select a state s_t

V(s_t) ← maxa Σs',r p(s',r|s_t,a)[r + γV(s')]

Leave all other V(s) unchanged

Return a greedy policy when a stopping condition is satisfied

```

State selection may be cyclic, random, demand-driven, or prioritised. Prioritised sweeping updates states whose values are likely to change substantially and then considers their predecessors. This can reduce computation in sparse planning problems, but it requires predecessor information and careful queue management.

A Detailed Applied Scenario: Warehouse Robot Routing

This is an illustrative case rather than a report of a particular deployed system.

Background and problem

A warehouse robot must move packages through a grid. Each grid cell is a state, and actions are north, south, east, or west. Some actions lead to neighbouring cells; walls prevent movement. Reaching a delivery station gives reward +10, each ordinary movement gives reward −1, and entering a hazardous cell gives reward −8 and returns the robot to a safe location. The warehouse simulator supplies transition probabilities because wheel slippage makes movement stochastic. The engineering team wants a route policy before operating the robot on the real floor.

Analysis

A model-based approach is appropriate because the simulator supplies \(p(s',r\mid s,a)\). A discount factor, for example \(\gamma=0.95\), values prompt delivery while still considering future rewards. The model must represent hazardous transitions and blocked actions explicitly; ignoring slippage would produce a policy that is optimal only for an unrealistic deterministic environment.

Approach

The team first runs value iteration. It initializes all nonterminal state values to zero and repeatedly applies the Bellman optimality backup. After convergence, it extracts a greedy action from each reachable cell. To validate the result, it evaluates the extracted policy independently using policy evaluation. The validation values should agree with the converged optimal values within the selected tolerance.

Because most warehouse cells are irrelevant to the current order, the team then experiments with asynchronous updates. It updates cells near the robot and cells that are predecessors of high-value delivery locations. A priority queue orders states by estimated Bellman error. This reduces computation while preserving convergence when all relevant states continue to receive updates.

Outcome

The resulting policy avoids the hazardous shortcut when its expected risk outweighs the additional movement cost. Compared with a policy based only on immediate rewards, it selects safer routes and accounts for stochastic slippage. Independent simulation is used to check average return, delivery time, collision frequency, and sensitivity to model errors.

Learning points

1. Planning requires a usable transition and reward model.

2. Expected future return, not immediate reward alone, determines action choice.

3. Model validation is essential because an optimal policy for an inaccurate model may perform poorly in reality.

4. Asynchronous and prioritised updates can improve computational efficiency without changing the underlying objective.

5. Safety metrics should supplement reward when policies affect physical systems.

Assumptions, Limitations, and Implementation Practice

Model accuracy and the reality gap

DP assumes that the model is correct or sufficiently accurate. A biased transition probability can systematically favour unsafe or ineffective actions. In robotics and operations, model uncertainty should be assessed through simulation, held-out data, stress testing, and conservative constraints.

State-space growth

Tabular DP requires storing values for states and enumerating actions and possible outcomes. If there are \(|\mathcal{S}|\) states, \(|\mathcal{A}|\) actions, and at most \(b\) possible outcomes per state–action pair, one sweep is approximately \(O(|\mathcal{S}||\mathcal{A}|b)\). Memory is at least proportional to the number of states, with additional cost for the model. Large or continuous spaces require state aggregation, function approximation, sampling, or alternative planning methods.

Discounting and episodic tasks

The contraction arguments given above rely most directly on \(\gamma<1\) in discounted tasks. Episodic undiscounted problems can also be well-defined when episodes terminate under suitable conditions, but convergence and boundedness must be analysed using the task's termination structure. One should not assume that every undiscounted continuing problem has a finite value.

Numerical and software practices

Use a consistent terminal-state convention, explicit tie-breaking, and a documented tolerance. Separate model code, backup code, stopping logic, and policy extraction so that policy evaluation can independently test value iteration. Unit tests should include deterministic transitions, a one-state self-loop, terminal transitions, ties between actions, and known analytical solutions. Track Bellman residuals and test the final policy in simulation rather than relying only on iteration count.

Ethics and governance

Planning systems may allocate scarce resources, control robots, or influence safety-critical decisions. A reward function that omits fairness, safety, energy consumption, or human override can produce technically optimal but socially unacceptable behaviour. Professional deployment should include clearly defined objectives, audit logs, access controls, simulation-based safety testing, monitoring for distribution shift, and a human escalation mechanism. If the model was estimated from personal or operational data, privacy, data governance, and applicable regulation must also be considered.

Contemporary Relevance

Modern systems rarely apply tabular DP directly to enormous real-world state spaces, but its ideas remain central. Model-based RL uses learned world models to perform approximate planning. Monte Carlo tree search uses selective lookahead rather than exhaustive state sweeps. Dyna-style systems combine direct experience with model-based simulated updates. Prioritised sweeping and related methods focus computation on states affected by important changes. Even deep RL systems often use Bellman backups, target values, and policy improvement concepts derived from DP.

The main contemporary challenge is balancing model learning, planning cost, and model uncertainty. A learned model may enable efficient hypothetical experience but can amplify errors through repeated simulated backups. Practical systems therefore use uncertainty estimates, short planning horizons, conservative policies, or periodic correction from real data.

Chapter Summary

Dynamic programming solves finite model-based reinforcement-learning problems through repeated Bellman backups. Policy evaluation predicts the value of a specified policy using the Bellman expectation equation. Policy improvement forms a greedy policy from those values and is guaranteed not to reduce performance under standard assumptions. Policy iteration alternates complete evaluation and improvement until the policy is stable. Value iteration applies the Bellman optimality backup directly and converges to the optimal value function in finite discounted MDPs. Generalized policy iteration provides a unifying view in which evaluation and improvement interact at varying degrees of completeness. Asynchronous DP updates selected states rather than full sweeps and can improve efficiency when updates are fair and relevant states are eventually covered.

These methods are powerful when a reliable environment model is available, but they face computational growth, model error, continuous spaces, and safety concerns. Correct implementation requires explicit assumptions, careful terminal-state handling, verified stopping criteria, independent testing, and evaluation in realistic simulations or operations.

Key Terms

MDP: A formal model of sequential decision-making defined by states, actions, transitions, rewards, and usually a discount factor.

Environment model: A specification of transition and reward probabilities.

Planning: Computing actions or policies by reasoning with an environment model.

Policy: A rule defining action probabilities or choices in each state.

Return: The cumulative discounted reward from a time step onward.

Value function: Expected return from a state under a specified policy.

Action-value function: Expected return from a state–action pair under a specified policy.

Bellman expectation equation: Recursive equation defining the value of a policy.

Bellman optimality equation: Recursive equation defining the optimal value function.

Prediction: Computing the value of a given policy.

Control: Finding a policy that maximizes expected return.

Policy evaluation: Iterative or exact computation of a policy's value function.

Policy improvement: Replacing a policy with one greedy with respect to its value function.

Policy iteration: Alternating policy evaluation and policy improvement.

Value iteration: Repeated application of the Bellman optimality backup.

Generalized policy iteration: Interleaving partial or complete evaluation and improvement.

Asynchronous dynamic programming: Updating selected states rather than all states in each sweep.

Bellman backup: A one-step update using expected immediate reward and future value.

Contraction: An operator property that brings value estimates closer by a fixed factor and supports convergence.

Model error: The discrepancy between an assumed environment model and actual environment dynamics.

Review Questions

Short Answer Questions

1. What information must an environment model provide for tabular dynamic programming?

2. Distinguish policy evaluation from policy improvement.

3. Why does value iteration use a maximum over actions?

4. What is meant by generalized policy iteration?

5. State one convergence condition for asynchronous dynamic programming.

Long Answer Questions

1. Derive the Bellman expectation equation for a stochastic policy and explain each term.

2. Explain the policy improvement theorem and its significance for policy iteration.

3. Compare policy iteration and value iteration in terms of computation, convergence, and practical use.

4. Describe how terminal states, discounting, and stopping tolerances should be handled in a DP implementation.

5. Explain why an inaccurate model can produce an unsafe or ineffective policy even when the DP algorithm has converged.

Analytical / Application Questions

1. A state has two actions. Action X gives reward 3 and moves to a state valued at 4 with probability 1. Action Y gives reward 5 and moves to a state valued at 1 with probability 1. With \(\gamma=0.5\), which action is greedy, and why?

2. Design an asynchronous value-iteration update strategy for a sparse grid-world in which only states near a changing goal are relevant. State how you would preserve eventual convergence.

3. A warehouse planner produces a high-return policy in simulation but causes frequent collisions in deployment. Analyse at least three possible causes and propose model, reward, and validation changes.

Multiple Choice Questions with Answers

Question 1

Which expression is the Bellman expectation equation for a policy π?

A. vπ(s) = maxa qπ(s,a)

B. vπ(s) = Σa π(a|s) Σs',r p(s',r|s,a)[r + γvπ(s')]

C. vπ(s) = r(s) − γvπ(s')

D. vπ(s) = Σa p(a|s)r(s,a)

Correct Answer: B. vπ(s) = Σa π(a|s) Σs',r p(s',r|s,a)[r + γvπ(s')]

Question 2

What is the principal purpose of policy evaluation?

A. To compute the value of a specified policy

B. To remove the environment model

C. To maximise immediate reward only

D. To enumerate unreachable actions

Correct Answer: A. To compute the value of a specified policy

Question 3

In policy improvement, a greedy action is selected by maximising which quantity?

A. The immediate reward only

B. The transition probability only

C. Expected reward plus discounted next-state value

D. The number of available actions

Correct Answer: C. Expected reward plus discounted next-state value

Question 4

Which operation is central to value iteration?

A. A minimum over policies

B. A maximum over actions in a Bellman backup

C. Random action selection without a model

D. Averaging rewards without future values

Correct Answer: B. A maximum over actions in a Bellman backup

Question 5

For a finite discounted MDP, why does value iteration converge?

A. The optimality operator is a contraction

B. Every policy has identical value

C. Rewards must all be positive

D. The state space is necessarily continuous

Correct Answer: A. The optimality operator is a contraction

Question 6

What happens when policy iteration reaches a policy that is greedy with respect to its own value function?

A. It must be discarded

B. It is stable and optimal under the standard finite discounted assumptions

C. Its value is necessarily zero

D. The model is no longer required for evaluation

Correct Answer: B. It is stable and optimal under the standard finite discounted assumptions

Question 7

Which statement best describes generalized policy iteration?

A. It forbids policy evaluation

B. It alternates or interleaves policy evaluation and policy improvement

C. It applies only to unknown models

D. It updates rewards but never values

Correct Answer: B. It alternates or interleaves policy evaluation and policy improvement

Question 8

What is a defining feature of asynchronous dynamic programming?

A. All states must be updated simultaneously

B. Only terminal states can be updated

C. Selected states are updated while others may remain unchanged

D. No model is used

Correct Answer: C. Selected states are updated while others may remain unchanged

Question 9

A deterministic transition gives reward 2 and leads to a state with value 6. If γ = 0.5, what is the backed-up action value?

A. 3

B. 5

C. 8

D. 12

Correct Answer: B. 5

Question 10

Which implementation practice is most appropriate for a DP planner?

A. Ignore terminal-state conventions

B. Use undocumented tie-breaking and arbitrary stopping

C. Test against known analytical solutions and monitor Bellman residuals

D. Evaluate only immediate rewards

Correct Answer: C. Test against known analytical solutions and monitor Bellman residuals