Skip to content

12. Preparation for the Exam

12.1 The Master Modeling Template

Use this template for almost every modeling question:

  • Objective.
  • Decision points \(k=0,1,\ldots,K\).
  • State \(S_k\).
  • Feasible decisions \(x\in X(S_k)\).
  • Immediate reward/cost \(R(S_k,x)\).
  • Post-decision state \(S_k^x\).
  • Stochastic information \(\omega_{k+1}\).
  • Transition probabilities \(P(S_{k+1}\mid S_k,x)\) or transition function \(S_{k+1}=S^M(S_k,x,\omega_{k+1})\).
  • Policy \(\pi\).
  • Why exact DP is or is not feasible.
  • Suitable ADP method.

12.2 High-Value Exam Answers

Dynamic problem

The problem is dynamic because the decision maker makes repeated decisions over time and later decisions can react to new information. The solution is a policy rather than a fixed plan.

Stochastic problem

The problem is stochastic because some relevant information, such as demand, travel time, service time, or resource availability, is unknown when the decision is made and must be modeled with probabilities, distributions, or scenarios.

Post-decision state

The post-decision state \(S_k^x\) separates the deterministic effect of the decision from the stochastic information that arrives afterward.

ADP

ADP is needed because exact dynamic programming is infeasible when the state, decision, and information spaces become large. ADP constructs approximate policies such as PFA, RHO, CFA, look-ahead, and VFA.

12.3 Calculation Checklist

For Bellman/MDP graph questions:

1. Identify minimization or maximization.
2. Start at terminal values.
3. At stochastic transitions, compute probability-weighted averages.
4. At decision states, choose min or max.
5. Write values for states and post-decision states.
6. Highlight the policy.
7. Report initial expected value.

For RHO:

1. Choose decisions based on immediate/current cost.
2. Fix the RHO policy.
3. Still calculate total expected value under that policy.

For VFA:

  1. Identify each post-decision state \(S_k^x\).
  2. Find its aggregation or features, such as \(A(S_k^x)\).
  3. Look up or calculate \(\hat{V}(S_k^x)\).
  4. Add immediate \(R(S_k,x)\).
  5. Choose the best total.

12.4 Common Mistakes

Mistake Fix
State only includes location Include time, resources, demand, and environment
Future unknown demand is in the state Put it in \(\omega_{k+1}\)
One fixed route is called a policy Policy maps many possible states to decisions
RHO is treated as optimal Say it is practical but often myopic
VFA is treated as exact Say \(\hat{V}\) is an estimate
Sampling is treated as exact Say it approximates expected performance
Supervised learning is treated as decision making Say it supports the information model
RL notation replaces course notation Translate back to DDM notation

12.5 Final Cram Sheet

  • DDM = sequential decisions + new information + future consequences.
  • Policy \(\pi\) = rule mapping states to decisions.
  • State \(S_k\) = decision-relevant information before decision.
  • Post-decision state \(S_k^x\) = after decision, before new randomness.
  • Bellman = immediate \(R(S_k,x)\) + future value \(V(S_k^x)\).
  • ADP = approximate policies when exact DP is too large.
  • Sampling = approximate uncertain futures.
  • Supervised learning = prediction for information models.
  • RL = learning values/policies from experience.
  • Combined methods = practical mixtures of prediction, optimization, simulation, and learning.

12.6 Exam Strategy Diagram

flowchart TB
    A["Read the question"]:::start --> B{"Modeling or calculation?"}:::question
    B -->|Modeling| C["List DDM components<br/>S_k, x, R, S_k^x, omega, P"]:::model
    B -->|Calculation| D["Identify min/max<br/>then work backward"]:::calc
    C --> E["Explain uncertainty and dynamism"]:::explain
    D --> F["Immediate + future value"]:::value
    E --> G["Choose suitable ADP method if exact DP too large"]:::adp
    F --> H["Report policy and initial value"]:::answer
    G --> H
    classDef start fill:#e0f2fe,stroke:#0284c7,stroke-width:2px,color:#0f172a;
    classDef question fill:#fef9c3,stroke:#ca8a04,stroke-width:2px,color:#0f172a;
    classDef model fill:#dcfce7,stroke:#16a34a,stroke-width:2px,color:#0f172a;
    classDef calc fill:#ede9fe,stroke:#7c3aed,stroke-width:2px,color:#0f172a;
    classDef explain fill:#ffedd5,stroke:#ea580c,stroke-width:2px,color:#0f172a;
    classDef value fill:#f5f3ff,stroke:#7c3aed,stroke-width:2px,color:#0f172a;
    classDef adp fill:#fee2e2,stroke:#dc2626,stroke-width:2px,color:#0f172a;
    classDef answer fill:#f8fafc,stroke:#334155,stroke-width:2px,color:#0f172a;

12.7 High-Scoring Compare-Methods Template

Use this pattern whenever comparing PFA, RHO, CFA, look-ahead, and VFA:

Method:
What it approximates:
How it makes a decision:
Main merit:
Main drawback:
Best use case:

Example:

CFA approximates future consequences by modifying the immediate cost or constraints. It can preserve future flexibility without explicitly solving the full MDP. It is useful when a known myopic behavior can be corrected with a penalty or buffer, but the penalty must be tuned and may not capture all future uncertainty.

12.7 Course-Style Calculation Checklist

MDP graph calculation

Use this sequence for tutorial-style graph questions:

  1. Mark terminal states and set terminal values.
  2. Work backward one decision point at a time.
  3. For each decision, add immediate reward/cost and post-decision value.
  4. For each post-decision state, average over possible next states using probabilities.
  5. Choose max for reward problems or min for cost problems.
  6. Write the optimal decision next to each state.

Formula pattern

\[ V(S_k^x)=\sum_{S_{k+1}}P(S_{k+1}\mid S_k,x)V(S_{k+1}). \]
\[ V(S_k)=\min_{x\in X(S_k)}\left[R(S_k,x)+V(S_k^x)\right]. \]

For maximization, replace \(\min\) by \(\max\).

12.8 Exam Answer Templates From Tutorials

Pizza delivery modeling answer

State \(S_k\) should include current time, driver routes/availability, and open orders with locations, order times, and pizza quantities. Decision \(x\) is whether to dispatch drivers and which orders to assign. Post-decision state \(S_k^x\) updates driver routes and availability after the assignment. Stochastic information \(\omega_{k+1}\) includes new orders, travel times, and preparation completion. The objective is to minimize expected delay, travel cost, and lateness penalties.

Trucks & Barges modeling answer

Decision points are days. State \(S_k\) includes day, containers currently in the yard, destinations, due dates, and relevant known future containers. Decisions include shipping by truck, barge, train, or holding. Costs include transport, setup, lateness, and clean-up. Post-decision state is the yard after shipments. Stochastic information includes new arrivals and uncertain final clean-up costs. Objective: minimize expected total cost.

Dynamic knapsack policy answer

A PFA may accept an offer if money divided by space exceeds a threshold. A CFA may reserve capacity for future decision points. A look-ahead method samples future offers and implements only the current decision. A VFA estimates \(\hat{V}(t,b)\), the value of having capacity \(b\) at time \(t\).

Common exam traps

  • Forgetting the post-decision state.
  • Using future requests inside the current state before they are revealed.
  • Mixing minimization and maximization signs.
  • Calling a forecast a decision.
  • Saying RHO is future-aware without explaining that standard RHO uses \(V=0\) unless enriched.
  • Giving a generic RL formula when the question asks for DDM notation.

Chapter source note

Course basis: DDM exam/tutorial questions on modeling, MDP graph calculation, RHO, and VFA. Textbook enrichment: Kochenderfer et al. on validation and policy comparison; Powell on policy classes and modeling frameworks. Exam answers should be concise but component-complete.

12.8 Worked Exam Mini-Answer

Question

A same-day delivery company receives orders throughout the day. Drivers have limited capacity and travel times are uncertain. Explain why this is a stochastic dynamic decision problem and suggest an ADP method.

Formal answer structure

  • Decision points: \(k=\) each order arrival or replanning time.
  • State \(S_k\): current time, driver locations, driver capacities, open orders, travel-time information.
  • Decision \(x\in X(S_k)\): accept/reject orders, assign drivers, dispatch, wait, or reroute.
  • Immediate cost \(R(S_k,x)\): travel cost, lateness penalty, rejection penalty, service cost.
  • Post-decision state \(S_k^x\): driver routes/capacities and order list after the decision.
  • Stochastic information \(\omega_{k+1}\): new orders, travel-time realizations, cancellations, service times.
  • Objective: minimize expected total cost or maximize expected service/profit.

Worked response

The problem is dynamic because decisions are made repeatedly during the day and each decision changes future driver availability and capacity. It is stochastic because future orders and travel times are unknown when the current decision is made. A suitable model is an MDP with state \(S_k\) containing time, driver locations, capacities, and open orders; feasible decisions \(x\in X(S_k)\) such as assignment, dispatching, waiting, or rejection; immediate cost \(R(S_k,x)\); post-decision state \(S_k^x\); stochastic information \(\omega_{k+1}\); and an expected total-cost objective.

Exact dynamic programming is infeasible because the state, decision, and information spaces are large. A practical ADP approach is RHO with CFA: solve the current assignment/routing problem, but add penalties for using scarce flexible drivers or overcommitting capacity. If simulation is available, look-ahead or VFA can further improve anticipation of future demand.

Properties of a high-scoring answer

  • It explicitly says why the problem is dynamic.
  • It explicitly says why the problem is stochastic.
  • It lists MDP components using DDM notation.
  • It explains why exact DP is infeasible.
  • It names an ADP method and says what it approximates.
  • It avoids replacing the DDM model with generic RL notation.