6. Dynamic Programming
Many OR decisions are not made once but in sequence: how much to produce each month, whether to keep or replace a machine each year, what to do in each state of a system that evolves at random. Dynamic programming (DP) solves these problems by splitting them into stages and solving one small problem per stage and state, reusing those answers instead of enumerating every sequence of decisions. This chapter covers the deterministic theory (Bellman's principle, the recursions and two classic applications) and its stochastic extension, Markov decision processes, which underlie inventory control, maintenance planning, revenue management and reinforcement learning.
<a id="61-deterministic-dynamic-programming"></a>
6.1 Deterministic Dynamic Programming
This subchapter covers DP for problems where the outcome of every decision is known in advance. It introduces the principle that makes DP correct, the vocabulary used to model a problem (stages, states, decisions, returns), the two directions in which the recursion can run, two classic applications, and the main obstacle to using DP: the size of the state space. DP has already appeared several times in this guide: shortest paths on DAGs and Bellman-Ford (Section 3.2), the knapsack table (Section 4.3) and Held-Karp for the TSP (Section 4.4). This subchapter explains the method behind all of them.
Bellman's Principle of Optimality
Why it matters. A sequence of $N$ decisions with $k$ options each has $k^N$ combinations. Evaluating them all is hopeless beyond toy sizes. DP replaces this enumeration with a number of operations roughly equal to (stages) $\times$ (states per stage) $\times$ (decisions per state). Bellman's principle is what makes the shortcut valid, and knowing when it fails tells you how to choose a correct state.
Theory. Richard Bellman (1957) stated it as follows:
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.
Put simply: every tail of an optimal solution is optimal for its own subproblem. If the fastest road trip from Milan to Naples passes through Rome, its Rome-Naples portion must be the fastest way from Rome to Naples. If it were not, replacing that portion with a faster one would make the whole trip faster, which is a contradiction.
This turns into a recursion. Let $f(s)$ be the optimal cost to finish starting from state $s$. A decision $x$ costs $c(s, x)$ and leads to state $\tau(s, x)$. Then
$$ f(s) = \min_{x} \big{ c(s, x) + f(\tau(s, x)) \big}, $$
which is the Bellman equation (also called the functional equation of DP). We never need to look at complete decision sequences. We only need the optimal value of each tail, computed once and reused by every sequence that passes through that state.
When it holds. Two conditions are required:
| Condition | Meaning | Violated by |
|---|---|---|
| Decomposable objective | the total is built from stage terms with an operation that is monotone in the tail value: sum, max, product of positive factors | "make the total as close as possible to 12": a cheaper tail is not always better |
| Sufficient state | the state contains everything about the past that affects future costs or feasibility | "cheapest route taking at most 10 hours" with state = city only: the best tail depends on the time already used |
When the second condition fails, the fix is to enlarge the state. For the time-limited route, the state becomes (city, hours used). The principle then holds again, at the cost of more states. Choosing the state is the central modeling decision in DP, as the next topic shows.
Example: the staged road network. A truck travels from depot A to customer J through three intermediate regions and pays a toll on every leg. This is the classic "stagecoach problem".
Stage: 1 2 3 4 5
A --> B, C, D --> E, F, G --> H, I --> J
Tolls: A->B 2 B->E 7 B->F 4 B->G 6 E->H 1 E->I 4 H->J 3
A->C 4 C->E 3 C->F 2 C->G 4 F->H 6 F->I 3 I->J 4
A->D 3 D->E 4 D->F 1 D->G 5 G->H 3 G->I 3
The greedy route (always take the cheapest next leg) is A-B-F-I-J with cost $2 + 4 + 3 + 4 = 13$. The code compares brute-force enumeration with the backward DP:
from itertools import product
# Staged road network: (from, to) -> toll. Stages: A | B C D | E F G | H I | J
COST = {("A","B"): 2, ("A","C"): 4, ("A","D"): 3,
("B","E"): 7, ("B","F"): 4, ("B","G"): 6,
("C","E"): 3, ("C","F"): 2, ("C","G"): 4,
("D","E"): 4, ("D","F"): 1, ("D","G"): 5,
("E","H"): 1, ("E","I"): 4, ("F","H"): 6, ("F","I"): 3,
("G","H"): 3, ("G","I"): 3, ("H","J"): 3, ("I","J"): 4}
STAGES = [["A"], ["B","C","D"], ["E","F","G"], ["H","I"], ["J"]]
# 1) Brute force: enumerate every A -> J path and add up its tolls
additions, best = 0, None
for mid in product(*STAGES[1:-1]): # 3 * 3 * 2 = 18 paths
path = ("A",) + mid + ("J",)
total = 0
for u, v in zip(path, path[1:]):
total += COST[u, v]; additions += 1
if best is None or total < best[0]:
best = (total, path)
print(f"brute force: cost {best[0]}, path {'-'.join(best[1])}, {additions} additions")
# 2) DP (backward): f[node] = cheapest cost from node to J, reusing the tails
f, nxt, additions = {"J": 0}, {}, 0
for stage in reversed(STAGES[:-1]):
for u in stage:
options = {v: COST[u, v] + f[v] for v in STAGES[STAGES.index(stage) + 1]}
additions += len(options)
nxt[u] = min(options, key=options.get) # optimal decision at u
f[u] = options[nxt[u]]
path = ["A"]
while path[-1] != "J":
path.append(nxt[path[-1]])
print(f"dynamic prog: cost {f['A']}, path {'-'.join(path)}, {additions} additions")
print("f =", f)
# brute force: cost 11, path A-C-E-H-J, 72 additions
# dynamic prog: cost 11, path A-C-E-H-J, 20 additions
# f = {'J': 0, 'H': 3, 'I': 4, 'E': 4, 'F': 7, 'G': 6, 'B': 11, 'C': 7, 'D': 8, 'A': 11}
Brute force pays 4 additions for each of the 18 paths. DP pays one addition per arc, because the cost-to-go of E, F and G is computed once and shared by every path that reaches them. With $N$ stages of $k$ nodes, the gap is $k^{N-1}$ paths against about $N k^2$ arcs. Three routes tie at cost 11 (A-C-E-H-J, A-D-E-H-J and A-D-F-I-J). The DP reports one of them, and the $f$ table contains all of them. The greedy route costs 13: the cheapest first leg (A-B) leads to an expensive region.
Key takeaways
- Bellman's principle: every tail of an optimal solution is optimal for the state where the tail starts.
- It gives the Bellman equation $f(s) = \min_x { c(s, x) + f(\tau(s, x)) }$, solved once per state instead of once per sequence.
- It requires a decomposable, monotone objective and a state that summarizes all relevant history.
- When the principle fails, enlarge the state (for example, add the resource already consumed).
Practice
- (Beginner) Using the printed $f$ table, list all three optimal routes by following, from each node, every successor $v$ with $c(u, v) + f(v) = f(u)$.
- (Intermediate) Give every arc a travel time as well as a toll, and find the cheapest A-J route whose total time is at most a limit $T_{\max}$. Build an instance where the DP over cities alone returns an infeasible or suboptimal route. Then fix it with the state (city, time used) and count the states.
- (Interview) "Shortest paths satisfy the Bellman equation. Why can't you use the same recursion to find the longest simple path in a general graph?" Hint: what must the tail subproblem know about the nodes already visited, and why does the problem disappear on a DAG (Section 3.2)?
Stages, States and Decisions
Why it matters. The DP recursion is mechanical once the model is right. The hard part, and the part examiners and interviewers focus on, is the model: what a stage is, what the state must contain, which decisions are feasible, and how one state leads to the next. A poorly chosen state makes the recursion either wrong (too little information) or impossibly large (too much).
Theory. Every deterministic DP is defined by six elements:
| Element | Symbol | Meaning | Road network | Production planning |
|---|---|---|---|---|
| Stage | $t = 1, \dots, T$ | a point at which a decision is made | leg of the trip | month |
| State | $s_t \in S_t$ | what we must know about the past to decide optimally | current city | stock at the start of the month |
| Decision | $x_t \in X_t(s_t)$ | the feasible choices in that state | next city | units produced |
| Transition | $s_{t+1} = \tau_t(s_t, x_t)$ | the state that results | the chosen city | $s + x - d_t$ |
| Stage return | $c_t(s_t, x_t)$ | immediate cost or reward | toll | setup + production + holding cost |
| Value function | $f_t(s)$ | best total from stage $t$ in state $s$ to the end | cheapest toll to J | cheapest cost of months $t, \dots, T$ |
The recursion and its boundary condition are
$$ f_t(s) = \min_{x \in X_t(s)} \big{ c_t(s, x) + f_{t+1}(\tau_t(s, x)) \big}, \qquad f_{T+1}(s) = \text{terminal cost of } s . $$
The total work is $\sum_t \lvert S_t \rvert \cdot \lvert X_t \rvert$: every (state, decision) pair is evaluated once.
Choosing the state. A good state is:
- Sufficient (Markov): given $s_t$, the future does not depend on how we reached it.
- Minimal: it contains nothing the future does not need, because every extra component multiplies the number of states.
- Able to express future constraints: if a later stage needs "remaining budget" or "cities not yet visited", the state must carry it.
Many well-known algorithms are DPs with a particular choice of state:
| Problem | Stage | State | Decision | States |
|---|---|---|---|---|
| 0-1 knapsack (Section 4.3) | item $j$ | remaining capacity | take or skip | $nW$ |
| Shortest path on a DAG (Section 3.2) | topological position | current node | outgoing arc | $n$ |
| Held-Karp TSP (Section 4.4) | number of cities visited | (set visited, last city) | next city | $n 2^n$ |
| Lot sizing (Wagner-Whitin) | period | stock level, or last setup period | production quantity | $T \times$ stock levels |
| Edit distance | prefix lengths | $(i, j)$ | delete, insert, substitute | $mn$ |
| Viterbi decoding (HMMs) | time step | hidden state | previous hidden state | $T \times$ states |
Example: production planning. A plant must meet monthly demands of 2, 3, 2 and 4 units. It can make up to 5 units a month. Producing costs a setup of 6 (if anything is made) plus 2 per unit. Stock left at the end of a month costs 1 per unit, the warehouse holds at most 4 units, and the year must end with no stock. The trade-off is setup cost against holding cost: producing for two months at once saves a setup but pays to hold the stock.
The state is the stock at the start of the month, $s \in {0, \dots, 4}$. The decision is the quantity $q$, restricted so that demand is met ($s + q \ge d_t$). The transition is $s' = s + q - d_t$. The code is a generic backward solver: it takes the six elements as functions, so the same code solves any finite-horizon deterministic DP.
import math
def backward_dp(T, states, decisions, transition, cost, terminal):
"""Generic finite-horizon DP. Returns value tables f[t][s] and policy x[t][s]."""
f = [dict() for _ in range(T + 1)]
x = [dict() for _ in range(T)]
f[T] = {s: terminal(s) for s in states}
for t in reversed(range(T)): # stages T-1, ..., 0
for s in states:
best, arg = math.inf, None
for d in decisions(t, s):
s2 = transition(t, s, d)
if s2 in f[t + 1]: # next state must be valid
val = cost(t, s, d) + f[t + 1][s2]
if val < best:
best, arg = val, d
f[t][s], x[t][s] = best, arg
return f, x
# Monthly production planning
demand = [2, 3, 2, 4] # units per month
CAP, MAXINV = 5, 4 # production capacity, warehouse size
SETUP, UNIT, HOLD = 6, 2, 1 # setup cost if producing, cost per unit, holding per unit
f, x = backward_dp(
T=len(demand),
states=range(MAXINV + 1), # state: stock at start of month
decisions=lambda t, s: [q for q in range(CAP + 1) if s + q >= demand[t]], # meet demand
transition=lambda t, s, q: s + q - demand[t], # stock carried to next month
cost=lambda t, s, q: (SETUP if q > 0 else 0) + UNIT * q + HOLD * (s + q - demand[t]),
terminal=lambda s: 0 if s == 0 else math.inf) # end the year with no stock
print("month f_t(s) for s = 0..4 x_t(s)")
for t in range(len(demand)):
vals = " ".join(f"{f[t][s]:>4}" if f[t][s] < math.inf else " inf" for s in range(MAXINV + 1))
print(f" {t + 1} {vals} {[x[t][s] for s in range(MAXINV + 1)]}")
s, plan = 0, []
for t in range(len(demand)):
plan.append(x[t][s]); s = s + x[t][s] - demand[t]
print("optimal plan from empty stock:", plan, "cost", f[0][0])
# month f_t(s) for s = 0..4 x_t(s)
# 1 42 40 32 31 30 [2, 1, 0, 0, 0]
# 2 32 30 28 24 21 [5, 4, 3, 0, 0]
# 3 24 20 14 13 12 [2, 5, 0, 0, 0]
# 4 14 12 10 8 0 [4, 3, 2, 1, 0]
# optimal plan from empty stock: [2, 5, 0, 4] cost 42
The optimal plan makes 5 units in month 2, covering months 2 and 3 with one setup. With a capacity of 5, only one pair of consecutive months can share a setup: months 1-2 (5 units, holding 3 for a month), or months 2-3 (5 units, holding 2). Months 3-4 together need 6. Each merge saves a setup of 6, and merging months 2-3 holds one unit less, so it wins 42 to 43. The tables contain more than one plan: $x_t(s)$ is a feedback policy that gives the best decision for every stock level. If a delivery is lost and month 3 starts with 1 unit instead of 2, the row for month 3 already gives the answer (produce 5).
Key takeaways
- A DP model has six parts: stages, states, feasible decisions, transitions, stage returns and the value function with its boundary condition.
- The state must be sufficient (Markov) and as small as possible. Its size determines the running time, $\sum_t \lvert S_t \rvert \lvert X_t \rvert$.
- Constraints are enforced through the feasible decision sets and an infinite terminal cost on forbidden end states.
- DP returns a policy for every state, not just one plan, which is useful when reality deviates from the plan.
Practice
- (Beginner) Verify the month-4 row $f_4(s) = (14, 12, 10, 8, 0)$ by hand, using the fact that the stock at the end of month 4 must be 0.
- (Intermediate) Allow backlogging: unmet demand can be delivered a month late at a penalty of 5 per unit, but all demand must be met by the end of the year. How does the state space change? Modify the code and compare the optimal cost.
- (Interview) "You must sequence 25 jobs on one machine to minimize total weighted tardiness, and someone suggests DP. What is the state, and is it practical?" Hint: the completion time of the next job depends on which jobs are already done, not on their order. Count the subsets.
Forward and Backward Recursion
Why it matters. The same DP can be computed from the end towards the start (backward) or from the start towards the end (forward). The two directions answer different questions, and the right choice depends on what is fixed (start, end or both) and on whether you need a policy for every state. In programming terms, the same choice appears as bottom-up tabulation against top-down memoization.
Theory.
- Backward recursion computes the cost-to-go $f_t(s)$: the best cost from state $s$ at stage $t$ to the end. $$ f_t(s) = \min_{x} { c_t(s, x) + f_{t+1}(\tau_t(s, x)) }, \qquad f_{T+1} = \text{terminal cost}. $$
- Forward recursion computes the cost-so-far $g_t(s)$: the best cost from the fixed initial state to state $s$ at stage $t$. $$ g_{t+1}(s') = \min_{(s, x),:\ \tau_t(s, x) = s'} { g_t(s) + c_t(s, x) }, \qquad g_1(s_1) = 0 . $$
Both give the same optimum: $f_1(s_1) = \min_{s} { g_{T+1}(s) + \text{terminal}(s) }$. Combining them gives a useful test: a state lies on some optimal solution if and only if $g_t(s) + f_t(s)$ equals the optimal value.
| Backward | Forward | |
|---|---|---|
| Computes | best from each state to the end | best from the start to each state |
| Natural when | the start state may change, or a feedback policy is needed | the start is fixed and the end state is free, or data arrive over time |
| Stochastic problems | yes: the future is averaged over before deciding (Section 6.2) | generally no |
| Typical use | production plans, replacement, MDPs | shortest paths from one source, Viterbi decoding, sequence alignment |
Top-down and bottom-up. Computer scientists implement the same recursion in two styles. Bottom-up tabulation fills the table stage by stage in a fixed order. It visits every state, but it needs no recursion and can keep only the last stage in memory when the plan itself is not needed. Top-down memoization writes the recursion directly and caches each result. It evaluates only states reachable from the start, but recursion depth and cache overhead can be a problem for long horizons.
Example. The code runs both recursions on the road network from the first topic, plus a memoized top-down version:
from functools import lru_cache
COST = {("A","B"): 2, ("A","C"): 4, ("A","D"): 3,
("B","E"): 7, ("B","F"): 4, ("B","G"): 6,
("C","E"): 3, ("C","F"): 2, ("C","G"): 4,
("D","E"): 4, ("D","F"): 1, ("D","G"): 5,
("E","H"): 1, ("E","I"): 4, ("F","H"): 6, ("F","I"): 3,
("G","H"): 3, ("G","I"): 3, ("H","J"): 3, ("I","J"): 4}
STAGES = [["A"], ["B","C","D"], ["E","F","G"], ["H","I"], ["J"]]
succ = {u: [v for (a, v) in COST if a == u] for st in STAGES for u in st}
pred = {v: [u for (u, b) in COST if b == v] for st in STAGES for v in st}
# Backward recursion: f(u) = min_v { c(u,v) + f(v) }, f(J) = 0 (cost-to-go)
f = {"J": 0}
for stage in reversed(STAGES[:-1]):
for u in stage:
f[u] = min(COST[u, v] + f[v] for v in succ[u])
# Forward recursion: g(v) = min_u { g(u) + c(u,v) }, g(A) = 0 (cost-so-far)
g = {"A": 0}
for stage in STAGES[1:]:
for v in stage:
g[v] = min(g[u] + COST[u, v] for u in pred[v])
# Top-down with memoization: same recursion as f, evaluated on demand
calls = 0
@lru_cache(maxsize=None)
def cost_to_go(u):
global calls; calls += 1
return 0 if u == "J" else min(COST[u, v] + cost_to_go(v) for v in succ[u])
print("node g (from A) f (to J) g + f")
for st in STAGES:
for v in st:
mark = " <- on an optimal path" if g[v] + f[v] == f["A"] else ""
print(f" {v} {g[v]:>2} {f[v]:>2} {g[v] + f[v]:>2}{mark}")
print("memoized:", cost_to_go("A"), "with", calls, "distinct evaluations")
# node g (from A) f (to J) g + f
# A 0 11 11 <- on an optimal path
# B 2 11 13
# C 4 7 11 <- on an optimal path
# D 3 8 11 <- on an optimal path
# E 7 4 11 <- on an optimal path
# F 4 7 11 <- on an optimal path
# G 8 6 14
# H 8 3 11 <- on an optimal path
# I 7 4 11 <- on an optimal path
# J 11 0 11 <- on an optimal path
# memoized: 11 with 10 distinct evaluations
$g(J) = f(A) = 11$, as expected. The $g + f$ column shows that B and G are on no optimal route, while every other node is on at least one of the three tied routes. Without the cache, the top-down recursion would recompute the cost-to-go of E, F and G once for each path that reaches them. With it, each of the 10 nodes is evaluated exactly once.
Key takeaways
- Backward recursion computes cost-to-go and yields a policy for every state. Forward recursion computes cost-so-far from a fixed start.
- Both give the same optimal value. A state is on an optimal solution exactly when $g + f$ equals the optimum.
- Stochastic DPs must be solved backward, because decisions depend on expectations over the future.
- Bottom-up tabulation and top-down memoization implement the same recursion. Memoization evaluates only reachable states.
Practice
- (Beginner) Compute the forward labels $g$ for the road network by hand, stage by stage, and check them against the table.
- (Intermediate) Rewrite the production planning example with a forward recursion, where $g_t(s)$ is the minimum cost of meeting the demand of months $1..t$ and ending month $t$ with stock $s$. Which entry is the answer, and how do you recover the plan?
- (Interview) "Your DP has a million states per stage and 365 stages. You need the optimal value, and later the optimal plan. How much memory do you need in each case?" Hint: the value needs only two stages at a time. For the plan, compare storing all decisions compactly, checkpointing some stages and recomputing, and Hirschberg-style divide and conquer.
Resource Allocation Problems
Why it matters. Splitting a limited budget, workforce or capacity among competing activities is one of the most common decisions in practice: sales staff across regions, engineers across product teams, ad budget across channels, servers across services. The returns are often nonlinear and only known as tables from estimates, so LP does not apply and the greedy rule "give the next unit to whoever gains most" can fail. DP handles any return table exactly.
Theory. Distribute $B$ indivisible units among $n$ activities. Activity $j$ returns $r_j(x)$ when it receives $x$ units:
$$ \max \sum_{j=1}^{n} r_j(x_j) \quad \text{s.t.} \quad \sum_{j=1}^{n} x_j \le B, \qquad x_j \in {0, 1, \dots, B} . $$
Activities are the stages even though the problem has nothing to do with time. The state is the number of units still available, $b$. The decision is how many units to give activity $j$:
$$ f_j(b) = \max_{0 \le x \le b} \big{ r_j(x) + f_{j+1}(b - x) \big}, \qquad f_{n+1}(b) = 0 , $$
and the answer is $f_1(B)$. There are $n(B+1)$ states with up to $B + 1$ decisions each, so the running time is $O(nB^2)$. The knapsack DP (Section 4.3) is the special case where each $x_j$ is 0 or 1.
Why greedy can fail. If every $r_j$ is concave (diminishing returns), assigning units one at a time to the largest marginal gain is optimal. This is the discrete form of the "equal marginal returns" condition given by Lagrange multipliers (Section 5.2). If some $r_j$ is S-shaped, for example a team that is only productive after reaching a critical mass, the first units look worthless to greedy and the activity is never funded.
| Return shape | Greedy marginal allocation | DP |
|---|---|---|
| Concave | optimal | optimal |
| Convex or S-shaped | can be arbitrarily bad | optimal |
| Arbitrary table | heuristic only | optimal |
Variants handled by the same recursion include upper limits per activity ($x \le u_j$), minimum allocations, and multiplicative objectives such as system reliability $\prod_j p_j(x_j)$ with redundant spare components, where the product of positive factors keeps the principle valid.
Example. Six engineers are allocated to three teams. The values (k$ per month) come from team estimates. Payments needs at least three engineers before it produces much:
| Engineers | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|---|
| Search | 0 | 5 | 9 | 12 | 14 | 15 | 15 |
| Payments | 0 | 1 | 3 | 10 | 14 | 16 | 17 |
| Mobile | 0 | 4 | 7 | 9 | 10 | 11 | 11 |
# Allocate 6 engineers to 3 teams. r[team][k] = value (k$/month) with k engineers.
r = {"search": [0, 5, 9, 12, 14, 15, 15], # concave: diminishing returns
"payments": [0, 1, 3, 10, 14, 16, 17], # S-shaped: needs a critical mass of 3
"mobile": [0, 4, 7, 9, 10, 11, 11]}
teams, B = list(r), 6
# Stage j = team, state b = engineers still available, decision x = engineers given to team j
# f_j(b) = max_{0 <= x <= b} r_j(x) + f_{j+1}(b - x), f_{n}(b) = 0
f = {len(teams): [0] * (B + 1)}
best_x = {}
for j in reversed(range(len(teams))):
f[j], best_x[j] = [], []
for b in range(B + 1):
vals = [r[teams[j]][x] + f[j + 1][b - x] for x in range(b + 1)]
f[j].append(max(vals)); best_x[j].append(vals.index(max(vals)))
for j in range(len(teams)):
print(f"f_{j + 1}(b) {teams[j]:9s}", f[j], " x* =", best_x[j])
b, alloc = B, {}
for j, team in enumerate(teams): # walk forward through the decisions
alloc[team] = best_x[j][b]; b -= alloc[team]
print("DP :", alloc, "value", f[0][B])
# Greedy: give each engineer to the team with the largest marginal gain
alloc_g = dict.fromkeys(teams, 0)
for _ in range(B):
gain = {t: r[t][alloc_g[t] + 1] - r[t][alloc_g[t]] for t in teams}
alloc_g[max(gain, key=gain.get)] += 1
print("greedy :", alloc_g, "value", sum(r[t][alloc_g[t]] for t in teams))
# f_1(b) search [0, 5, 9, 13, 16, 19, 23] x* = [0, 1, 1, 2, 2, 1, 1]
# f_2(b) payments [0, 4, 7, 10, 14, 18, 21] x* = [0, 0, 0, 3, 3, 4, 4]
# f_3(b) mobile [0, 4, 7, 9, 10, 11, 11] x* = [0, 1, 2, 3, 4, 5, 5]
# DP : {'search': 1, 'payments': 4, 'mobile': 1} value 23
# greedy : {'search': 4, 'payments': 0, 'mobile': 2} value 21
Read the tables from the bottom up. $f_3$ is mobile alone. $f_2(b)$ is the best split of $b$ engineers between payments and mobile. For example, $f_2(6) = 21$ gives 4 to payments and 2 to mobile. $f_1(6) = 23$ is the overall optimum. Greedy never gives payments its first engineer, because a marginal gain of 1 always loses to search or mobile, so it misses the critical mass completely. The allocation (2, 3, 1) also achieves 23, and the DP keeps the first optimum it finds.
Key takeaways
- Resource allocation is a DP with activities as stages and remaining resource as the state. It runs in $O(nB^2)$ time.
- It works with arbitrary return tables: nonlinear, non-concave, or known only from estimates.
- Greedy marginal allocation is optimal only for concave returns. S-shaped returns (critical mass) break it.
- Several resources make the state a vector, which leads to the curse of dimensionality (last topic of this section).
Practice
- (Beginner) Compute $f_2(3)$ (3 engineers shared by payments and mobile) by listing all four splits, and check it against the table.
- (Intermediate) A system has three components in series with reliabilities 0.80, 0.90 and 0.85. Each spare added in parallel to component $j$ costs 1 unit, and the budget is 4. Maximize system reliability $\prod_j \big(1 - (1 - p_j)^{1 + x_j}\big)$ by adapting the code (product instead of sum).
- (Interview) "Marketing wants to split a 1 M budget across five channels, using concave response curves fitted to past data. Would you use DP?" Hint: with concave, continuous curves the problem is convex, and the optimum equalizes marginal returns (KKT, Section 5.2). When would DP become the better tool?
Equipment Replacement Problems
Why it matters. Machines, vehicles, servers and laptops age. Running costs rise (energy, repairs, downtime) and resale value falls. Replacing too early wastes capital, and replacing too late wastes running cost. The equipment replacement model is the classic DP application in maintenance and fleet management, and it shows two features that appear in many DPs: decisions that depend on how much of the horizon remains, and an equivalent shortest-path formulation.
Theory. At the start of each year $t = 1, \dots, T$ we own one machine of age $a$. We either keep it (pay its running cost, and it becomes one year older) or replace it (sell it at salvage value $S(a)$, buy a new one at price $P$, and run that). At the end of the horizon the machine is sold. With $OP(a)$ the running cost of a machine of age $a$ and $a_{\max}$ the age at which it must be retired:
$$ f_t(a) = \min \begin{cases} OP(a) + f_{t+1}(a + 1) & \text{keep, if } a < a_{\max} \ P - S(a) + OP(0) + f_{t+1}(1) & \text{replace} \end{cases} \qquad f_{T+1}(a) = -S(a) . $$
The stage is the year, the state is the age, and there are two decisions. The work is $O(T \cdot a_{\max})$.
Shortest-path view. A replacement plan is just the list of years in which a new machine is bought. Let node $i$ mean "buy a new machine at the start of year $i$", with node $T + 1$ for the end of the horizon. An arc $i \to j$ means "keep that machine for $j - i$ years, then sell it":
$$ c_{ij} = P + \sum_{k=0}^{j-i-1} OP(k) - S(j - i), \qquad j - i \le a_{\max} . $$
The best plan is the shortest path from node 1 to node $T + 1$ in this DAG (Section 3.2). The same structure appears in the Wagner-Whitin lot-sizing model, where an arc means "produce in period $i$ for periods $i, \dots, j - 1$".
node i = "buy a new rack at the start of year i" (node 7 = end of horizon)
1 ------> 2 ------> 3 ------> 4 ------> 5 ------> 6 ------> 7
| ^| ^
+-----------------------------+ +---------------------------+
arc 1 -> 4: run 3 years arc 4 -> 7: run 3 years
100 + 10 + 14 + 20 - 27 = 117 same cost: 117 total 234
Example. A data center plans the next 6 years for one server rack (values in k$). A new rack costs 100. Running costs by age are 10, 14, 20, 29 and 41. Resale values after 1 to 5 years are 62, 41, 27, 16 and 8, and a rack must be retired at age 5. The code solves the DP, prints the decision for every (year, age) pair, and checks the result with the shortest-path formulation. Replacing a brand-new rack is excluded, so the decision set depends on the state.
import math
PRICE = 100 # new server rack (k$)
OP = [10, 14, 20, 29, 41] # running cost during a year, by age at start of year
SALVAGE = [None, 62, 41, 27, 16, 8] # resale value at age 1..5
MAXAGE, T = 5, 6 # must be retired at age 5; plan over 6 years
# DP: state = (year t, age a at start of year). Decisions: Keep or Replace.
f = {(T, a): -SALVAGE[a] for a in range(1, MAXAGE + 1)} # sell whatever is left
policy = {}
for t in reversed(range(T)):
for a in range(0, MAXAGE + 1):
options = {}
if a < MAXAGE: # keep: pay running cost, age 1 year
options["K"] = OP[a] + f[t + 1, a + 1]
if a > 0: # replace: trade in, run a new one
options["R"] = PRICE - SALVAGE[a] + OP[0] + f[t + 1, 1]
f[t, a] = min(options.values())
best = [d for d in options if options[d] == f[t, a]]
policy[t, a] = best[0] if len(best) == 1 else "=" # "=" marks a tie
print("year decision by age at start of year (0..5)")
for t in range(T):
print(f" {t + 1} ", " ".join(policy[t, a] for a in range(MAXAGE + 1)))
a, plan = 0, ""
for t in range(T):
plan += policy[t, a]; a = a + 1 if policy[t, a] == "K" else 1
print("start with a new rack:", plan, " net cost", PRICE + f[0, 0])
# Shortest-path view: node i = "buy a new rack at the start of year i+1"
# arc i -> j = run that rack for j - i years, then sell it
def arc(i, j):
return PRICE + sum(OP[:j - i]) - SALVAGE[j - i]
d, pred = [0] + [math.inf] * T, [None] * (T + 1)
for j in range(1, T + 1):
for i in range(max(0, j - MAXAGE), j):
if d[i] + arc(i, j) < d[j]:
d[j], pred[j] = d[i] + arc(i, j), i
buys, j = [], T
while j > 0:
j = pred[j]; buys.append(j + 1)
print("shortest path: buy in years", sorted(buys), " net cost", d[T])
# year decision by age at start of year (0..5)
# 1 K K K R R R
# 2 K K K K R R
# 3 K K K = R R
# 4 K K = R R R
# 5 K K K R R R
# 6 K K K K R R
# start with a new rack: KKKRKK net cost 234
# shortest path: buy in years [1, 4] net cost 234
The optimal plan buys racks in years 1 and 4 and runs each for three years, at a net cost of 234. Both formulations agree. The policy table shows that the decision for an age-3 rack depends on the year: replace in year 1, keep in year 2, either in year 3 (marked =), replace in years 4 and 5, keep in year 6. The remaining horizon has to be split into whole service lives, and a rack bought late is sold after a year or two at a large loss: 100 drops to 62 after one year. In year 6, buying a new rack would cost $100 - 27 + 10 - 62 = 21$ net for the last year, while keeping the old one costs $29 - 16 = 13$. These end-of-horizon effects fade far from the end, which leads to the infinite-horizon models of Section 6.2.
Key takeaways
- Equipment replacement is a DP with state = age, stage = year and two decisions, keep or replace.
- It is equivalent to a shortest path on a DAG whose arcs are "buy in year $i$, sell in year $j$".
- Decisions near the end of a finite horizon differ from those far from it (end effects). Salvage values matter.
- Ties are common in DP: when two decisions have equal value, both are optimal, and the code should report it rather than hide it.
Practice
- (Beginner) Use the arc formula to compute the cost of replacing every two years (buy in years 1, 3 and 5) and of replacing every year. How much worse are they than 234?
- (Intermediate) Add technological progress: a rack bought in year $t$ costs $100 \cdot 0.95^{t-1}$ and has running costs 10% lower for each year later it is bought. Which state do you need now? Update both formulations and check that they still agree.
- (Interview) "How would you decide when to refresh a fleet of 10,000 employee laptops?" Hint: the single-machine DP gives a replacement age, but an annual budget couples the machines (resource allocation, or Lagrangian pricing of the budget), cohorts of identical age can serve as states, and failures are random (Section 6.2).
Curse of Dimensionality
Why it matters. DP is exact and often elegant, but its running time is proportional to the number of states, and that number grows exponentially with the number of state variables. Bellman himself called this the curse of dimensionality. Recognizing it early saves weeks of work, and knowing the remedies lets you use DP ideas where exact DP is impossible.
Theory. If the state is a vector of $K$ components, each taking $m$ values, there are $m^K$ states. The work per stage is (states) $\times$ (decisions) $\times$ (random outcomes, in the stochastic case), so Powell distinguishes three curses:
| Curse | Grows with | Example |
|---|---|---|
| State space | number of state variables | stock levels of 10 products |
| Decision space | number of decision variables | how much of each product to order |
| Outcome space | number of random variables | the joint demand of all products (Section 6.2) |
Typical state-space sizes:
| Problem | State | Number of states |
|---|---|---|
| One product, stock 0 to 100 | stock | 101 |
| Ten products, stock 0 to 100 each | stock vector | $101^{10} \approx 1.1 \times 10^{20}$ |
| Held-Karp TSP, $n = 30$ (Section 4.4) | (set visited, last city) | $2^{29} \cdot 29 \approx 1.6 \times 10^{10}$ |
| Knapsack with $K$ constraints, capacity 1,000 each | remaining capacities | $1001^K$ |
| 50 trucks spread over 20 depots | trucks per depot | $\binom{69}{19} \approx 4.6 \times 10^{16}$ |
A related effect appears even with one state variable: the knapsack DP runs in $O(nW)$, which is polynomial in the value $W$ but exponential in its number of digits. It is pseudo-polynomial (Section 4.4).
Example. The code solves a knapsack with $K$ resource constraints exactly, for $K = 1, \dots, 5$. The state is the vector of remaining capacities, so the table has $21^K$ cells. It is vectorized with numpy, so the time measures the size of the table rather than Python overhead. For $K \ge 6$ it only reports the table size.
import time
import numpy as np
rng = np.random.default_rng(0)
n, C = 20, 20 # 20 items, capacity 20 in every resource
def knapsack_dp(K):
"""Exact DP for a K-resource knapsack. State = remaining capacity in each resource."""
w = rng.integers(1, 8, size=(n, K)) # item weights, one per resource
v = rng.integers(5, 30, size=n)
best = np.zeros((C + 1,) * K) # best[c_1, ..., c_K]: (C+1)^K states
for j in range(n):
take = np.full_like(best, -np.inf)
dst = tuple(slice(w[j, k], None) for k in range(K)) # capacities that fit item j
src = tuple(slice(None, C + 1 - w[j, k]) for k in range(K))
take[dst] = best[src] + v[j] # take item j: value + best with less capacity
best = np.maximum(best, take) # or skip it
return best.size, best.flat[-1]
for K in range(1, 6):
t0 = time.perf_counter()
states, value = knapsack_dp(K)
print(f"K = {K}: {states:>14,} states {states * 8 / 1e6:>10,.1f} MB "
f"time {time.perf_counter() - t0:7.3f} s optimum {value:.0f}")
for K in range(6, 9): # do not run: just size the table
states = (C + 1) ** K
print(f"K = {K}: {states:>14,} states {states * 8 / 1e6:>10,.1f} MB")
# K = 1: 21 states 0.0 MB time 0.000 s optimum 150
# K = 2: 441 states 0.0 MB time 0.000 s optimum 139
# K = 3: 9,261 states 0.1 MB time 0.001 s optimum 115
# K = 4: 194,481 states 1.6 MB time 0.012 s optimum 125
# K = 5: 4,084,101 states 32.7 MB time 0.355 s optimum 123
# K = 6: 85,766,121 states 686.1 MB
# K = 7: 1,801,088,541 states 14,408.7 MB
# K = 8: 37,822,859,361 states 302,582.9 MB
(Each $K$ draws new random weights, so the optima are not comparable across rows, and timings depend on the machine.) Every extra resource multiplies the table by 21. The same 20-item problem goes from instant to 33 MB at $K = 5$, and at $K = 8$ it would need 300 GB. A MILP solver typically handles $K = 8$ with 20 items in a fraction of a second, because branch and bound (Section 4.2) does not enumerate capacity levels.
Remedies.
| Remedy | Idea | Where it is used |
|---|---|---|
| Exploit structure | prove that the optimal policy has a simple form (threshold, base-stock, $(s, S)$) and search only within that family | inventory (Chapter 10), replacement |
| Decomposition and Lagrangian relaxation | price the constraint that couples the components and solve one small DP per component | multi-item inventory with shared capacity (Section 4.2) |
| Dominance and pruning | discard states that cannot beat another state (labels with more cost and more resource use) | resource-constrained shortest paths in column generation (Section 2.6) |
| Aggregation and discretization | group similar states, use a coarser grid | continuous states |
| Approximate DP | approximate the value function instead of tabulating it | Section 6.2 |
| A different method | MILP, heuristics, metaheuristics | when the state is huge but an LP relaxation is strong |
Key takeaways
- The number of states grows exponentially with the number of state variables. DP is exact but often infeasible for vector states.
- Powell's three curses: states, decisions and random outcomes.
- Remedies: exploit structure, decompose with Lagrangian prices, prune dominated states, aggregate, approximate the value function, or use another method.
- Before writing a DP, multiply out the state space. If it does not fit in memory, change the model or the method.
Practice
- (Beginner) How many (set, last city) states does Held-Karp have for $n = 20$ cities, and how much memory do they need at 8 bytes per value? Repeat for $n = 25$.
- (Intermediate) For the $K = 5$ instance, relax four of the five constraints with Lagrange multipliers $\lambda \ge 0$ (subtracting $\lambda^\top w_j$ from each item's value), solve the remaining one-constraint DP, and compare the resulting upper bound with the exact optimum for a few values of $\lambda$ (Section 4.2).
- (Interview) "Your manager asks for an exact DP to set reorder levels for 200 SKUs sharing one warehouse. What do you say?" Hint: count the states first. Then consider how strongly the SKUs are coupled, pricing the shared space with a multiplier, the known optimal policy structure for one item, and approximate DP.
<a id="62-stochastic-dynamic-programming"></a>
6.2 Stochastic Dynamic Programming
When the outcome of a decision is random, a plan fixed in advance is no longer enough. The best decision depends on the state actually reached, so the goal becomes a policy: a rule that maps every state to a decision. This subchapter formalizes the model (Markov decision processes), distinguishes finite and infinite horizons, presents the two classic algorithms (value iteration and policy iteration), compares the discounted and average-reward criteria, and ends with approximate methods for problems too large to solve exactly. Under a fixed policy the system is a Markov chain (Chapter 9). An MDP adds the decisions that control it.
All examples use one small machine-maintenance MDP, defined in the first topic.
Markov Decision Processes
Why it matters. Maintenance planning, inventory control, revenue management, dynamic pricing, admission control in queues, cloud autoscaling, clinical treatment plans and game-playing agents all share the same structure: observe the state, act, collect a reward, and let chance determine the next state. The Markov decision process (MDP) is the standard model for this loop. It is also the formal foundation of reinforcement learning.
Theory. An MDP consists of:
| Element | Notation | Meaning |
|---|---|---|
| States | $s \in \mathcal{S}$ | condition of the system (finite here) |
| Actions | $a \in \mathcal{A}(s)$ | decisions available in state $s$ |
| Transition probabilities | $P(s' \mid s, a)$ | distribution of the next state, given the current state and action |
| Rewards | $r(s, a)$ | expected immediate reward (or negative cost) |
| Criterion | horizon $N$, discount $\gamma$, or average | how rewards over time are combined (next topics) |
The Markov property says that the next state depends only on the current state and action, not on the earlier history. As in deterministic DP, it is a modeling requirement: if it does not hold, add the missing information to the state. Each period follows the same loop:
observe s_t --> choose a_t = pi(s_t) --> receive r(s_t, a_t) --> nature draws s_{t+1} ~ P(. | s_t, a_t)
^ |
+--------------------------------------------------------------------------------+
A policy $\pi$ maps states to actions. In principle it could depend on the whole history and could randomize. A fundamental result for finite MDPs with the criteria in this chapter is that a deterministic Markov policy (one action per state, possibly depending on time) is optimal, and for infinite horizons a stationary one (the same rule every period) is optimal. So we search only over rules of the form $a = \pi(s)$.
Under a fixed policy $\pi$, the state process is a Markov chain with transition matrix $P_\pi$ (row $s$ is $P(\cdot \mid s, \pi(s))$) and reward vector $r_\pi$. The value of the policy is an expectation over the trajectories it generates. The optimal values satisfy the stochastic Bellman equation, in which the deterministic next state is replaced by an expectation:
$$ V^(s) = \max_{a \in \mathcal{A}(s)} \Big{ r(s, a) + \gamma \sum_{s'} P(s' \mid s, a), V^(s') \Big}. $$
It is often convenient to work with the action-value (Q-value) $Q^(s, a) = r(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V^(s')$, so that $V^(s) = \max_a Q^(s, a)$ and the optimal policy is $\pi^(s) = \arg\max_a Q^(s, a)$.
| Deterministic DP (Section 6.1) | MDP | |
|---|---|---|
| Effect of a decision | known next state | probability distribution over next states |
| Output | an optimal plan (and policy) | an optimal policy; a fixed plan is suboptimal |
| Recursion | $\min_x { c + f(\tau(s, x)) }$ | $\max_a { r + \gamma, \mathbb{E}[V(s')] }$ |
| Direction | forward or backward | backward (expectation over the future) |
Example: machine maintenance. A production machine is in one of four conditions: new, good, worn or broken. Each week the manager chooses an action:
- run: earn the weekly profit of the current condition (10, 9, 4 or 0 k$). The machine then degrades at random according to the matrix below.
- maintain: the machine is offline for the week (cost 8) and comes back one condition better.
- replace: the machine is offline for the week (cost 20) and comes back new.
| From \ to (under "run") | new | good | worn | broken | Weekly profit |
|---|---|---|---|---|---|
| new | 0.6 | 0.3 | 0.1 | 0 | 10 |
| good | 0 | 0.6 | 0.3 | 0.1 | 9 |
| worn | 0 | 0 | 0.6 | 0.4 | 4 |
| broken | 0 | 0 | 0 | 1 | 0 |
The code stores the model as arrays P[a, s, s'] and R[s, a], the standard layout used in the rest of this subchapter, and simulates three simple policies to estimate their long-run weekly profit:
import numpy as np
STATES = ["new", "good", "worn", "broken"]
ACTIONS = ["run", "maintain", "replace"]
S, A = len(STATES), len(ACTIONS)
REVENUE = [10, 9, 4, 0] # weekly profit when running, by condition (k$)
COST_MAINTAIN, COST_REPLACE = 8, 20 # machine is offline for the week in both cases
DRIFT = np.array([[0.6, 0.3, 0.1, 0.0], # new -> new / good / worn / broken
[0.0, 0.6, 0.3, 0.1], # good
[0.0, 0.0, 0.6, 0.4], # worn
[0.0, 0.0, 0.0, 1.0]]) # broken stays broken while "running"
P = np.zeros((A, S, S)) # P[a, s, s'] = Pr(next = s' | state s, action a)
R = np.zeros((S, A)) # R[s, a] = expected reward this week
for s in range(S):
P[0, s] = DRIFT[s]; R[s, 0] = REVENUE[s] # run: earn, then degrade
P[1, s, max(s - 1, 0)] = 1; R[s, 1] = -COST_MAINTAIN # maintain: one level better
P[2, s, 0] = 1; R[s, 2] = -COST_REPLACE # replace: new next week
assert np.allclose(P.sum(axis=2), 1) # every row is a probability distribution
def simulate(policy, weeks=200_000, seed=0):
"""Average weekly profit of a stationary policy (one action per state)."""
rng, s, total = np.random.default_rng(seed), 0, 0.0
for _ in range(weeks):
a = policy[s]
total += R[s, a]
s = rng.choice(S, p=P[a, s]) # sample the next state
return total / weeks
policies = {"never fix ": [0, 0, 0, 0], # run in every state
"run to failure ": [0, 0, 0, 2], # replace only when broken
"maintain when worn": [0, 0, 1, 2]}
for name, pol in policies.items():
print(f"{name}: {simulate(pol):.3f} k$/week")
# never fix : 0.000 k$/week
# run to failure : 4.053 k$/week
# maintain when worn: 4.134 k$/week
"Never fix" ends up with a broken machine (an absorbing state), so its long-run profit is 0. The other two policies are close, and the simulation alone cannot say whether another policy beats both, or by how much. The exact values are 4.051 and 4.119 k$/week (computed in the Discounted and Average Reward Criteria topic). The algorithms in the next topics find the optimal policy without simulating, by solving the Bellman equation.
Key takeaways
- An MDP is (states, actions, transition probabilities, rewards, criterion). The Markov property must hold for the chosen state.
- The goal is a policy, a decision for every state, because the future state is random.
- Deterministic Markov policies are optimal for finite MDPs, and stationary ones for infinite horizons.
- Under a fixed policy the system is a Markov chain $(P_\pi, r_\pi)$. The Bellman equation adds a maximization over actions.
Practice
- (Beginner) Write out $P_\pi$ and $r_\pi$ for the "run to failure" policy. Which states are transient and which are recurrent under it?
- (Intermediate) Compute the exact long-run average profit of "run to failure" by solving $\mu P_\pi = \mu$, $\sum_s \mu_s = 1$ for the stationary distribution $\mu$ and evaluating $\mu^\top r_\pi$. Compare it with the simulation estimate.
- (Interview) "Model cloud autoscaling as an MDP. What are the states, actions and rewards, and where does the randomness come from?" Hint: think about load or queue length and the number of running servers, add or remove server actions, server cost against SLA penalties, random arrivals, and what happens to the state if new servers take several minutes to boot.
Finite and Infinite Horizon Problems
Why it matters. Some decisions have a natural end: a contract that expires, a selling season, a product that will be discontinued. Others continue indefinitely: a factory, a data center, an insurance portfolio. The two cases need different mathematics. A finite horizon gives time-dependent policies computed in one backward pass. An infinite horizon needs a criterion that keeps the total reward finite, and gives a stationary policy that solves a fixed-point equation.
Theory.
Finite horizon. With $N$ periods and terminal value $V_0(s)$ (salvage value), let $V_k(s)$ be the optimal expected reward with $k$ periods to go. Backward induction computes
$$ V_k(s) = \max_{a} \Big{ r(s, a) + \sum_{s'} P(s' \mid s, a), V_{k-1}(s') \Big}, \qquad k = 1, \dots, N . $$
The optimal action depends on both the state and the number of periods left, so the policy is nonstationary. Close to the end, investments whose payoff arrives after the horizon are not worth making: these are end effects.
Infinite horizon. The plain sum of rewards can diverge, so a criterion is needed:
- Discounted: maximize $\mathbb{E}\big[\sum_{t \ge 0} \gamma^t r_t\big]$ with $0 \le \gamma < 1$. With bounded rewards the sum is finite, $V^*$ is the unique solution of the Bellman equation $V = TV$, and a stationary policy is optimal.
- Average reward: maximize $\lim_{N \to \infty} \frac{1}{N} \mathbb{E}\big[\sum_{t < N} r_t\big]$ (topic below).
- Total reward to absorption: the process stops in a terminal state with probability 1, as in stochastic shortest path problems (the stochastic version of Section 3.2).
The two settings are connected: the finite-horizon values converge to the infinite-horizon ones. With discount $\gamma$,
$$ \lVert V_N - V^* \rVert_\infty \le \gamma^N \frac{\max \lvert r \rvert}{1 - \gamma} , $$
and the finite-horizon policy for $N$ periods to go becomes stationary once $N$ is large enough. In practice, ongoing operations are often run with a rolling horizon: solve an $N$-period problem, apply the first decision, observe the new state and solve again. This is the idea behind model predictive control.
| Finite horizon | Infinite horizon (discounted) | |
|---|---|---|
| Equation | $V_k = T V_{k-1}$, $k = 1, \dots, N$ | $V = T V$ (fixed point) |
| Optimal policy | depends on time to go | stationary |
| Algorithm | one backward pass | value iteration, policy iteration, LP |
| Terminal value | needed, and it matters | irrelevant |
| Typical use | contracts, seasons, end of life | ongoing operations |
Example. The code solves the machine problem for horizons up to 12 weeks with no discounting and no salvage value, then repeats with $\gamma = 0.9$ for longer horizons:
# Reuses STATES, ACTIONS, P, R from the Markov Decision Processes topic.
def backward_induction(N, gamma=1.0):
"""Finite horizon: V_0 = 0 (machine worthless at the end), V_k = max_a R + gamma P V_{k-1}."""
V, policies = np.zeros(S), []
for k in range(1, N + 1): # k = weeks to go
Q = R + gamma * np.einsum("ast,t->sa", P, V) # Q[s, a] = R[s, a] + gamma * sum_t P[a, s, t] V[t]
policies.append(Q.argmax(axis=1)); V = Q.max(axis=1)
return V, policies
V, policies = backward_induction(12)
print("weeks to go new good worn broken")
for k in (1, 2, 3, 4, 5, 12):
print(f" {k:>2} ", "".join(f"{ACTIONS[a]:<10}" for a in policies[k - 1]))
# Infinite horizon with discount 0.9: V_N converges to V*, error <= gamma^N * max|R| / (1 - gamma)
for N in (10, 50, 100, 200):
V_N, pol = backward_induction(N, gamma=0.9)
print(f"N = {N:>3}: V_N = {np.round(V_N, 2)} policy {[ACTIONS[a] for a in pol[-1]]}")
# weeks to go new good worn broken
# 1 run run run run
# 2 run run run run
# 3 run run run run
# 4 run run maintain replace
# 5 run run maintain replace
# 12 run run maintain replace
# N = 10: V_N = [41.05 31.08 18.78 15.74] policy ['run', 'run', 'maintain', 'replace']
# N = 50: V_N = [52.81 42.83 30.53 27.51] policy ['run', 'run', 'maintain', 'replace']
# N = 100: V_N = [52.99 43. 30.7 27.69] policy ['run', 'run', 'maintain', 'replace']
# N = 200: V_N = [52.99 43. 30.7 27.69] policy ['run', 'run', 'maintain', 'replace']
With three weeks or fewer to go, the optimal action is always "run", even for a broken machine: a repair or replacement could not earn back its cost before the end. From four weeks to go the policy settles into "maintain when worn, replace when broken" and stays the same for longer horizons. In the discounted case, $V_N$ stops changing (to two decimals) around $N = 100$, consistent with the bound $0.9^{100} \cdot 20 / 0.1 \approx 0.005$.
Key takeaways
- Finite horizon: backward induction over "periods to go", giving a nonstationary policy with end effects driven by the terminal value.
- Infinite horizon needs a criterion: discounted, average reward, or total reward until absorption.
- Discounted values from $N$-period problems converge geometrically to $V^*$, and the policy becomes stationary.
- A rolling horizon applies the first decision of a finite-horizon problem and re-solves each period.
Practice
- (Beginner) Without computing, explain why "run" is optimal in every state with one week to go. Then show that replacing a broken machine with three weeks to go yields at most $-20 + 10 + 9.1 = -0.9$ in expectation, which is worse than running it for 0.
- (Intermediate) Give the machine a resale value at the end of the horizon, $V_0 = (8, 5, 2, 0)$ for (new, good, worn, broken). Re-run the backward induction. Which end-of-horizon decisions change, and why?
- (Interview) "A product line will be shut down in six months. Should the maintenance policy change as the date approaches, and how would you compute it?" Hint: finite horizon with a terminal (salvage) value. Compare the payback time of each action with the time left.
Value Iteration
Why it matters. Value iteration is the simplest algorithm for infinite-horizon MDPs: apply the Bellman equation as an update rule until the values stop changing. Every iteration is cheap and easy to parallelize, and the method underlies most approximate and learning-based algorithms (Q-learning is a sampled version of it).
Theory. Define the Bellman operator $T$, which maps a value vector to another:
$$ (TV)(s) = \max_{a} \Big{ r(s, a) + \gamma \sum_{s'} P(s' \mid s, a), V(s') \Big}. $$
$V^$ is a fixed point: $V^ = TV^*$. The key property is that $T$ is a contraction in the max-norm:
$$ \lVert TV - TU \rVert_\infty \le \gamma, \lVert V - U \rVert_\infty . $$
By the Banach fixed-point theorem, the fixed point is unique and the iteration $V_{k+1} = TV_k$ converges to it from any starting vector, with the error shrinking by a factor $\gamma$ per iteration. Starting from $V_0 = 0$, $V_k$ is exactly the optimal value of the $k$-period problem from the previous topic: value iteration is backward induction run until the values stop changing.
V <- 0
repeat
for each state s:
V_new(s) = max over a of [ r(s, a) + gamma * sum over s' of P(s' | s, a) * V(s') ]
delta = max over s of | V_new(s) - V(s) |
V <- V_new
until delta < eps * (1 - gamma) / (2 * gamma)
return the greedy policy pi(s) = argmax over a of [ r(s, a) + gamma * sum P V ]
Stopping rule. If $\lVert V_{k+1} - V_k \rVert_\infty < \varepsilon (1 - \gamma) / (2\gamma)$, the greedy policy with respect to $V_{k+1}$ is $\varepsilon$-optimal. The number of iterations needed grows like $\log(1/\varepsilon) / (1 - \gamma)$, so value iteration slows down sharply as $\gamma \to 1$. Each iteration costs $O(\lvert \mathcal{S} \rvert^2 \lvert \mathcal{A} \rvert)$ with dense transitions, and much less when each state has few successors.
Variants. Gauss-Seidel value iteration updates $V(s)$ in place, so later states in the same sweep already use the new values. Asynchronous and prioritized versions update states in any order, focusing on those whose values changed most. A span-based stopping rule ($\max_s \Delta(s) - \min_s \Delta(s)$) often stops much earlier when $\gamma$ is close to 1.
Example. Value iteration on the machine MDP with $\gamma = 0.9$, tracking when the greedy policy stops changing:
# Reuses STATES, ACTIONS, P, R from the Markov Decision Processes topic.
SHORT = ["run", "mnt", "rep"]
def value_iteration(gamma, eps=1e-3, verbose=False):
V, last_change, prev = np.zeros(S), 0, None
for k in range(1, 100_000):
Q = R + gamma * np.einsum("ast,t->sa", P, V) # one Bellman backup for every (s, a)
V_new, greedy = Q.max(axis=1), Q.argmax(axis=1)
delta = np.abs(V_new - V).max() # sup-norm change
if prev is None or (greedy != prev).any():
last_change, prev = k, greedy # iteration where the greedy policy last changed
if verbose and k in (1, 2, 3, 5, 10, 50):
print(f" iter {k:>2}: V = {np.round(V_new, 2)} change {delta:6.3f} "
f"greedy {[SHORT[a] for a in greedy]}")
V = V_new
if delta < eps * (1 - gamma) / (2 * gamma): # guarantees an eps-optimal greedy policy
return V, greedy, k, last_change
V, pi, k, settled = value_iteration(0.9, verbose=True)
print(f"gamma 0.9 : {k:>5} iterations (policy final from iteration {settled}), V = {np.round(V, 2)}")
for gamma in (0.95, 0.99, 0.999):
_, _, k, settled = value_iteration(gamma)
print(f"gamma {gamma:<5}: {k:>5} iterations (policy final from iteration {settled})")
# iter 1: V = [10. 9. 4. 0.] change 10.000 greedy ['run', 'run', 'run', 'run']
# iter 2: V = [18.19 14.94 6.16 0. ] change 8.190 greedy ['run', 'run', 'run', 'run']
# iter 3: V = [24.41 18.73 7.33 0. ] change 6.221 greedy ['run', 'run', 'run', 'run']
# iter 5: V = [32.1 22.96 10.98 6.01] change 4.039 greedy ['run', 'run', 'mnt', 'rep']
# iter 10: V = [41.05 31.08 18.78 15.74] change 1.351 greedy ['run', 'run', 'mnt', 'rep']
# iter 50: V = [52.81 42.83 30.53 27.51] change 0.020 greedy ['run', 'run', 'mnt', 'rep']
# gamma 0.9 : 106 iterations (policy final from iteration 4), V = [52.99 43. 30.7 27.69]
# gamma 0.95 : 233 iterations (policy final from iteration 4)
# gamma 0.99 : 1355 iterations (policy final from iteration 4)
# gamma 0.999: 15916 iterations (policy final from iteration 4)
The values at iterations 10 and 50 are exactly the finite-horizon values $V_{10}$ and $V_{50}$ from the previous topic. The greedy policy is already optimal at iteration 4, but the values need about 100 more iterations before the stopping rule can certify it. This gap is typical and is what policy iteration exploits. The iteration count grows roughly tenfold with each extra 9 in $\gamma$ (0.9, 0.99, 0.999), as predicted by the $1/(1 - \gamma)$ factor.
Key takeaways
- Value iteration repeats $V \leftarrow TV$. Because $T$ is a $\gamma$-contraction, it converges to the unique $V^*$ from any start.
- $V_k$ starting from 0 equals the optimal $k$-period value: value iteration is backward induction without a fixed end.
- Stop when the change is below $\varepsilon (1 - \gamma)/(2\gamma)$ to guarantee an $\varepsilon$-optimal greedy policy.
- Iterations grow like $1/(1 - \gamma)$. The policy usually becomes optimal long before the values converge.
Practice
- (Beginner) Starting from $V_1 = (10, 9, 4, 0)$, compute $V_2(\text{worn})$ by hand for all three actions and check the printed 6.16.
- (Intermediate) Implement Gauss-Seidel value iteration (update
V[s]in place, state by state) and compare the number of sweeps with the standard version for $\gamma = 0.99$. Does the state ordering matter?- (Interview) "Value iteration on your MDP with $\gamma = 0.999$ takes too long. What can you do?" Hint: policy or modified policy iteration, span-based stopping, Gauss-Seidel sweeps, a warm start from a good heuristic policy's values, or switching to the average-reward criterion.
Policy Iteration
Why it matters. Policy iteration usually finds the exact optimal policy in a handful of iterations, regardless of the discount factor. It alternates between evaluating the current policy exactly and improving it greedily, and it terminates with a certificate of optimality. Its structure (an evaluation that solves linear equations, followed by a local improvement) closely mirrors the simplex method.
Theory.
- Policy evaluation. For the current policy $\pi$, solve the linear system $$ V^\pi = r_\pi + \gamma P_\pi V^\pi \quad \Longleftrightarrow \quad (I - \gamma P_\pi), V^\pi = r_\pi , $$ with $\lvert \mathcal{S} \rvert$ equations and unknowns. The matrix is invertible for $\gamma < 1$.
- Policy improvement. Act greedily with respect to $V^\pi$: $$ \pi'(s) = \arg\max_{a} \Big{ r(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V^\pi(s') \Big}, $$ keeping the current action when it ties for the maximum.
- Stop when $\pi' = \pi$. The Bellman equation then holds, so $\pi$ is optimal.
Policy improvement theorem. $V^{\pi'} \ge V^\pi$ in every state, with strict improvement in at least one state unless $\pi$ is already optimal. No policy can repeat, and a finite MDP has finitely many deterministic policies ($\lvert \mathcal{A} \rvert^{\lvert \mathcal{S} \rvert}$), so policy iteration terminates. In practice it needs very few iterations. It can be viewed as Newton's method applied to the Bellman equation, which explains its fast convergence near the solution.
Modified policy iteration replaces the exact solve with $m$ sweeps of $V \leftarrow r_\pi + \gamma P_\pi V$. With $m = 1$ it is value iteration, and as $m \to \infty$ it becomes policy iteration. Intermediate values of $m$ are often fastest for large MDPs.
The LP formulation. $V^*$ is also the optimal solution of the linear program
$$ \min \sum_s \alpha(s) V(s) \quad \text{s.t.} \quad V(s) \ge r(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V(s') \quad \text{for all } s, a , $$
for any weights $\alpha > 0$. Its dual variables are discounted state-action frequencies, and adding side constraints on them (for example, "replace at most 5% of the time") gives constrained MDPs, which value and policy iteration cannot handle. Policy iteration that changes one action at a time is equivalent to the simplex method on the dual LP (Chapter 2).
| Value iteration | Policy iteration | Linear programming | |
|---|---|---|---|
| Work per iteration | $O(\lvert \mathcal{S} \rvert^2 \lvert \mathcal{A} \rvert)$ | $O(\lvert \mathcal{S} \rvert^3 + \lvert \mathcal{S} \rvert^2 \lvert \mathcal{A} \rvert)$ | one LP solve |
| Iterations | many, grows like $1/(1-\gamma)$ | few, almost independent of $\gamma$ | simplex pivots or IPM steps |
| Result | $\varepsilon$-optimal | exactly optimal | exactly optimal, plus state-action frequencies |
| Best for | very large sparse MDPs, moderate $\gamma$ | medium MDPs, $\gamma$ close to 1 | side constraints on behavior |
Example. Policy iteration on the machine MDP with $\gamma = 0.9$, starting from the worst reasonable policy, "never fix":
# Reuses STATES, ACTIONS, P, R from the Markov Decision Processes topic.
def evaluate(policy, gamma):
"""Exact policy evaluation: solve (I - gamma P_pi) V = r_pi."""
P_pi = P[policy, np.arange(S)] # row s = P[policy[s], s, :]
r_pi = R[np.arange(S), policy]
return np.linalg.solve(np.eye(S) - gamma * P_pi, r_pi)
def policy_iteration(gamma, policy):
for it in range(1, 100):
V = evaluate(policy, gamma)
Q = R + gamma * np.einsum("ast,t->sa", P, V)
keep = Q[np.arange(S), policy] >= Q.max(axis=1) - 1e-9 # current action still optimal?
improved = np.where(keep, policy, Q.argmax(axis=1)) # switch only on strict improvement
print(f" iter {it}: policy {[ACTIONS[a] for a in policy]} V = {np.round(V, 2)}")
if (improved == policy).all():
return policy, V
policy = improved
pi, V = policy_iteration(0.9, policy=np.array([0, 0, 0, 0])) # start from "never fix"
# iter 1: policy ['run', 'run', 'run', 'run'] V = [37.92 24.67 8.7 0. ]
# iter 2: policy ['run', 'maintain', 'maintain', 'replace'] V = [44.91 32.42 21.18 20.42]
# iter 3: policy ['run', 'run', 'run', 'replace'] V = [52.63 42.6 30.12 27.37]
# iter 4: policy ['run', 'run', 'maintain', 'replace'] V = [52.99 43. 30.7 27.69]
Four evaluations reach the same $V^*$ that value iteration needed 106 iterations to certify. Iteration 2 overreacts: the "never fix" values make every repair look attractive, so it maintains even good machines. The next evaluation corrects this. The values never decrease in any state from one iteration to the next, as the policy improvement theorem guarantees.
Key takeaways
- Policy iteration alternates exact evaluation (a linear system) with greedy improvement, and stops when the policy no longer changes.
- Each new policy is at least as good as the previous one in every state. Termination is finite and usually very fast.
- Modified policy iteration interpolates between value iteration ($m = 1$) and policy iteration ($m = \infty$).
- MDPs can also be solved as LPs, which allows side constraints on how often actions are used.
Practice
- (Beginner) Verify $V^\pi(\text{worn}) = 8.70$ for "never fix" by hand: write the evaluation equation for the worn state and solve it, using $V^\pi(\text{broken}) = 0$.
- (Intermediate) Implement modified policy iteration with $m$ evaluation sweeps per improvement. For $\gamma = 0.99$, count the total number of Bellman backups needed for $m = 1, 5, 20$ and for exact evaluation.
- (Interview) "Why does policy iteration typically converge in fewer than ten iterations even on MDPs with thousands of states?" Hint: relate it to Newton's method, and to how many states change their action in one improvement step.
Discounted and Average Reward Criteria
Why it matters. The choice of criterion is a modeling decision that changes the optimal policy. A discount factor that is too low makes the model short-sighted: it will refuse investments that pay off in the long run. The average-reward criterion removes time preference entirely and is natural for steady operations measured "per week" or "per hour". Knowing what each criterion means, and how they relate, prevents a whole class of modeling mistakes.
Theory.
Discounted criterion. $V^\pi_\gamma(s) = \mathbb{E}^\pi \big[ \sum_{t \ge 0} \gamma^t r_t \mid s_0 = s \big]$. There are two interpretations of $\gamma$:
- Time value of money: with an interest rate $i$ per period, $\gamma = 1/(1 + i)$.
- Random termination: the process stops after each period with probability $1 - \gamma$, so the expected lifetime is $1/(1-\gamma)$ periods, the effective horizon.
Average-reward criterion. The gain is $g^\pi(s) = \lim_{N \to \infty} \frac{1}{N} \mathbb{E}^\pi \big[ \sum_{t < N} r_t \mid s_0 = s \big]$. For unichain MDPs (every stationary policy produces a single recurrent class), the gain does not depend on the starting state, and the optimality equation is
$$ g + h(s) = \max_{a} \Big{ r(s, a) + \sum_{s'} P(s' \mid s, a), h(s') \Big} , $$
where the bias $h$ measures the transient advantage of starting in $s$. It is defined up to an additive constant, so one fixes $h(s_{\text{ref}}) = 0$. Relative value iteration solves it by iterating $h \leftarrow Th - (Th)(s_{\text{ref}})$. The subtracted constant converges to $g$. If the chain is periodic, the transformation $\tilde{P} = \tau P + (1 - \tau) I$ with $0 < \tau < 1$ restores convergence without changing the optimal policy. Policy iteration and LP formulations also exist for the average criterion.
The connection. As $\gamma \to 1$,
$$ V^_\gamma(s) = \frac{g}{1 - \gamma} + h(s) + o(1), \qquad (1 - \gamma) V^_\gamma(s) \to g . $$
A policy that is optimal for all $\gamma$ close enough to 1 is called Blackwell optimal. Such a policy exists for finite MDPs, and it is also average-optimal.
| Discounted | Average reward | |
|---|---|---|
| Objective | $\mathbb{E}[\sum_t \gamma^t r_t]$ | $\lim \frac{1}{N} \mathbb{E}[\sum_{t<N} r_t]$ |
| Time preference | yes, effective horizon $1/(1-\gamma)$ | none |
| Equation | $V = TV$ (contraction) | $g + h = Th$ (no contraction) |
| Algorithms | value or policy iteration, LP | relative value iteration, policy iteration, LP |
| Natural for | finance, investments, uncertain lifetime | throughput, cost per unit time, queues, maintenance |
| Pitfall | $\gamma$ too low gives short-sighted policies | ignores transient costs; needs chain-structure assumptions |
Example. The code solves the machine MDP for several discount factors and for the average criterion:
# Reuses STATES, ACTIONS, P, R from the Markov Decision Processes topic.
def discounted(gamma, iters=20_000):
V = np.zeros(S)
for _ in range(iters):
V = (R + gamma * np.einsum("ast,t->sa", P, V)).max(axis=1)
return V, (R + gamma * np.einsum("ast,t->sa", P, V)).argmax(axis=1)
def relative_value_iteration(ref=0, tol=1e-10):
"""Average reward: h <- T h - (T h)[ref]. The subtracted constant converges to the gain g."""
h = np.zeros(S)
while True:
Th = (R + np.einsum("ast,t->sa", P, h)).max(axis=1)
g, h_new = Th[ref], Th - Th[ref] # pin h(ref) = 0 to stop the drift
if np.abs(h_new - h).max() < tol:
return g, h_new, (R + np.einsum("ast,t->sa", P, h_new)).argmax(axis=1)
h = h_new
print("criterion 1/(1-gamma) policy (1-gamma) V(new)")
for gamma in (0.5, 0.8, 0.9, 0.99, 0.999):
V, pi = discounted(gamma)
print(f"gamma = {gamma:<5} {1 / (1 - gamma):>8.0f} {str([ACTIONS[a] for a in pi]):40s} {(1 - gamma) * V[0]:.3f}")
g, h, pi = relative_value_iteration()
print(f"average reward inf {str([ACTIONS[a] for a in pi]):40s} g = {g:.3f}")
print("bias h relative to 'new':", np.round(h, 2))
# criterion 1/(1-gamma) policy (1-gamma) V(new)
# gamma = 0.5 2 ['run', 'run', 'run', 'run'] 8.856
# gamma = 0.8 5 ['run', 'run', 'run', 'replace'] 6.322
# gamma = 0.9 10 ['run', 'run', 'maintain', 'replace'] 5.299
# gamma = 0.99 100 ['run', 'run', 'maintain', 'replace'] 4.248
# gamma = 0.999 1000 ['run', 'run', 'maintain', 'replace'] 4.132
# average reward inf ['run', 'run', 'maintain', 'replace'] g = 4.119
# bias h relative to 'new': [ 0. -11.67 -23.79 -24.12]
The discount factor changes the decision:
- With $\gamma = 0.5$ (effective horizon 2 weeks), the model abandons a broken machine. A replacement costs 20 now and pays back over several weeks, which the model heavily discounts.
- With $\gamma = 0.8$ it replaces broken machines but runs worn ones to failure.
- From $\gamma = 0.9$ on, it maintains worn machines, which is also the average-optimal policy.
$(1 - \gamma) V^*_\gamma(\text{new})$ converges to the gain $g = 4.119$ k$/week. For $\gamma = 0.5$ it is larger because a myopic model mostly counts the high profit of the first weeks. The bias explains the replacement decision: the optimality equation for (broken, replace) reads $g + h(\text{broken}) = -20 + h(\text{new})$, that is, $4.119 - 24.12 = -20.0$. A broken machine is worth 24.12 k$ less than a new one, which is exactly the replacement cost plus one week of average profit lost while the machine is offline.
Key takeaways
- Discounting models the time value of money or a random lifetime. The effective horizon is $1/(1-\gamma)$ periods.
- The average-reward criterion optimizes steady-state profit per period. It is solved with gain and bias $(g, h)$ by relative value iteration or policy iteration.
- $(1 - \gamma) V^*_\gamma \to g$ as $\gamma \to 1$, and Blackwell-optimal policies are optimal for both.
- A discount factor that is too small makes the policy short-sighted. Derive $\gamma$ from the cost of capital per period, not from habit.
Practice
- (Beginner) A weekly discount factor of 0.99 corresponds to what annual interest rate? Which weekly $\gamma$ corresponds to 8% per year?
- (Intermediate) Using $g = 4.119$ and $h = (0, -11.67, -23.79, -24.12)$, verify the average-reward optimality equation for the worn state: compute the right-hand side for all three actions and check that the maximum equals $g + h(\text{worn})$.
- (Interview) "A capacity planner built an MDP with $\gamma = 0.9$ per month, and it never recommends hardware upgrades that pay back in 18 months. What is wrong?" Hint: compare the effective horizon with the payback period, and ask what interest rate $\gamma = 0.9$ per month implies.
Approximate Dynamic Programming
Why it matters. Exact DP needs a table with one entry per state and a known model. Real problems often have neither: fleet management, energy storage, ride-hailing dispatch and multi-product inventory have astronomically many states (the curse of dimensionality, Section 6.1), and the transition probabilities are often unknown and available only through a simulator or historical data. Approximate dynamic programming (ADP, the OR term) and reinforcement learning (RL, the computer science term) are the same family of methods. They keep the Bellman structure but approximate the parts that are too large or unknown.
Theory. ADP combines four ideas:
- Approximate the value function instead of tabulating it. With features $\phi_k(s)$ such as stock levels, their squares or interactions: $$ V(s) \approx \sum_k \theta_k \phi_k(s) . $$ Fitted value iteration samples states, computes Bellman targets $y = \max_a { r + \gamma, \mathbb{E}[V_\theta(s')] }$, and fits $\theta$ by regression. Neural networks replace the linear model in deep RL.
- Replace expectations with samples. Instead of $\sum_{s'} P(s' \mid s, a) V(s')$, use one observed transition and average over time with a decreasing step size (stochastic approximation). Q-learning applies this to Q-values: $$ Q(s, a) \leftarrow Q(s, a) + \alpha \big[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \big]. $$ It converges to $Q^*$ in a finite MDP if every state-action pair is visited infinitely often and the steps satisfy $\sum \alpha = \infty$, $\sum \alpha^2 < \infty$.
- Post-decision states (Powell). Split each transition into the deterministic effect of the decision (for example, stock after ordering) and the random outcome (demand). Approximating the value of the post-decision state moves the expectation outside the maximization, so decisions can be optimized with deterministic tools, even an LP or MILP.
- Lookahead and policy search. Rollout evaluates each action by simulating a good heuristic policy afterwards and picks the best one, which is one step of policy iteration done by simulation. Rolling horizon solves a deterministic or scenario-based model and applies the first decision. Policy search tunes the parameters of a policy family directly by simulation, such as the $(s, S)$ thresholds of Chapter 10.
| Method | What is approximated | Needs the model? | Typical use |
|---|---|---|---|
| State aggregation | $V$ on groups of states | yes | coarse discretizations |
| Fitted value iteration | $V$ by regression | samples from it | fleet management, energy storage |
| Q-learning, SARSA | $Q$ as a table | no, a simulator suffices | small and medium problems, control |
| Deep RL (DQN, PPO) | $Q$ or the policy as a neural network | simulator | huge or image-like state spaces |
| Approximate LP | $V$ restricted to a basis, in the LP of the previous topics | yes | revenue management |
| Rollout | one-step improvement of a heuristic | simulator | scheduling, routing |
| Policy search | parameters of a policy | simulator | inventory thresholds, pricing rules |
The guarantees weaken as the approximations grow: tabular Q-learning provably converges, while fitted value iteration with function approximation can oscillate or diverge. Approximate policies should always be evaluated by simulation against simple benchmark policies.
Example. Q-learning on the machine MDP. The algorithm interacts only with a black-box step function, as it would with a real system or a simulator, and never reads P or R directly. The exact solution is computed at the end only to check the result.
# Reuses STATES, ACTIONS, P, R from the Markov Decision Processes topic and value_iteration()
# from the Value Iteration topic (only to check the answer at the end).
# Q-learning sees only a simulator: it never reads P or R directly.
rng = np.random.default_rng(42)
def step(s, a): # black-box environment
return R[s, a], rng.choice(S, p=P[a, s])
gamma, eps = 0.9, 0.1
Q = np.zeros((S, A)); visits = np.zeros((S, A))
s = 0
for t in range(1, 300_001):
a = rng.integers(A) if rng.random() < eps else Q[s].argmax() # epsilon-greedy exploration
r, s2 = step(s, a)
visits[s, a] += 1
alpha = 1 / visits[s, a] ** 0.6 # decaying step size
Q[s, a] += alpha * (r + gamma * Q[s2].max() - Q[s, a]) # sample Bellman backup
s = s2
if t in (1_000, 10_000, 100_000, 300_000):
print(f"{t:>7} steps: policy {[ACTIONS[a] for a in Q.argmax(axis=1)]} V ~ {np.round(Q.max(axis=1), 2)}")
V_star, pi_star, _, _ = value_iteration(gamma, eps=1e-8) # model-based answer
print(f"{'exact':>13}: policy {[ACTIONS[a] for a in pi_star]} V* = {np.round(V_star, 2)}")
# 1000 steps: policy ['run', 'run', 'run', 'replace'] V ~ [47.31 36.06 24.36 22.15]
# 10000 steps: policy ['run', 'run', 'run', 'replace'] V ~ [52.14 40.77 29.4 27.13]
# 100000 steps: policy ['run', 'run', 'maintain', 'replace'] V ~ [53.06 42.56 30.52 27.72]
# 300000 steps: policy ['run', 'run', 'maintain', 'replace'] V ~ [53.08 42.87 30.73 27.74]
# exact: policy ['run', 'run', 'maintain', 'replace'] V* = [52.99 43. 30.7 27.69]
Q-learning finds the optimal policy from samples alone, but it is sample-hungry: about 100,000 simulated weeks for a problem with 12 state-action pairs, which policy iteration solved exactly with four $4 \times 4$ linear solves. For the first 10,000 steps it prefers running worn machines to failure: the advantage of maintenance is small (in the worn state the exact Q-values of maintain and run differ by only about 0.16 at $\gamma = 0.9$) and hard to estimate from noisy samples. Exploration is essential: without the random actions, the agent would never learn what maintain or replace are worth.
Key takeaways
- ADP and RL keep the Bellman structure but approximate the value function, the expectation, or both.
- Value function approximation with features or neural networks addresses large state spaces. Sampling addresses unknown models.
- Q-learning is value iteration on Q-values with sampled transitions. It needs exploration and decaying step sizes, and many samples.
- Post-decision states, rollout, rolling horizons and policy search are practical alternatives. Always benchmark approximate policies by simulation.
Practice
- (Beginner) Run the Q-learning code with
eps = 0. Starting from $Q = 0$, which actions does the agent ever try in the broken state, and what policy does it end with? Explain why exploration is necessary in this MDP.- (Intermediate) Implement rollout with "run to failure" as the base policy: in each state, estimate the value of each action by simulating that action followed by the base policy for 60 weeks (discount 0.9, 500 runs), and pick the best. Compare the resulting policy with the first improvement step of policy iteration started from the same base policy.
- (Interview) "When would you choose exact DP over reinforcement learning for an operations problem, and the reverse?" Hint: think about state-space size, whether a reliable model exists, the cost of collecting samples, the need for optimality guarantees, and explainability to stakeholders.
<a id="7-multi-objective-optimization-and-decision-analysis"></a>