8. Sampling Methods II¶

8.1 Look-Ahead With Sampling¶

Intuition

Sampling Methods II is about using samples inside decision-making. We do not only estimate average performance after the fact. We use sampled futures to choose the current action.

Formal procedure

For each candidate decision \(x\):

Create \(S_k^x\).
Sample futures \(\omega^1,\ldots,\omega^N\).
Simulate or optimize decisions in each future.
Estimate total cost/reward.
Choose the best current \(x\).

Properties

Future decisions in samples are tentative.
Only the first real decision is implemented.
More scenarios improve representation but increase runtime.

8.2 Rollout¶

Intuition

Rollout improves a base policy by testing first decisions.

Plain language:

Try each possible first move.
After that, use a simple rule.
Simulate the result.
Pick the first move that looks best.

Formal expression

\[ \text{estimated value of first decision }x =R(S_k,x)+\text{average future performance under the base policy}. \]

Properties

Requires a base policy.
Often improves the base policy.
Can be expensive if many first decisions exist.
Quality depends on simulation and base policy.

Worked example

Base policy:

assign closest driver

Rollout:

test each current assignment
simulate future requests
after the first assignment, use closest-driver rule
choose the first assignment with lowest average delay

8.3 Multiple Scenario Approach¶

Intuition

MSA samples several future scenarios and chooses a current decision that performs well across them.

Formal idea

minimize average scenario cost

For \(N\) scenarios:

\[ x=\arg\min_x \frac{1}{N}\sum_{n=1}^{N} \text{cost of }x\text{ in scenario }n \]

Properties

Captures multiple possible futures.
Works well for dynamic routing and service systems.
Scenario quality matters.
Computational burden can be high.

flowchart TB
    A["Current state S_k"] --> B["Candidate first decisions"]
    B --> C1["Scenario 1"]
    B --> C2["Scenario 2"]
    B --> C3["Scenario 3"]
    C1 --> D["Average scenario performance"]
    C2 --> D
    C3 --> D
    D --> E["Implement best first decision"]

Worked example: sampled current decision

Decision options:

x1 = use central driver now
x2 = use outer driver now

Sampled future costs:

Scenario	Cost if `x1`	Cost if `x2`
1	20	25
2	70	35
3	80	40

Average:

x1 = (20 + 70 + 80) / 3 = 56.7
x2 = (25 + 35 + 40) / 3 = 33.3

Decision:

choose x2

8.4 Sparse Sampling and Tree Search¶

Intuition

Full look-ahead trees are huge. Sparse sampling keeps only a limited number of sampled branches. Monte Carlo tree search is a more advanced form that spends more simulation effort on promising branches.

Formal idea

At each state:

sample only m possible next outcomes
look ahead only h decision steps

where:

\(m\) is branching sample size,
\(h\) is horizon depth.

Properties

Method	Merit	Disadvantage
Full tree	accurate for small problems	explodes quickly
Sparse sampling	controls tree size	can miss important rare outcomes
Monte Carlo tree search	focuses search effort	more complex to explain and tune

DDM exam use

You usually do not need to implement MCTS. It is enough to say:

Advanced online planning methods approximate the future tree by sampling only part of it and focusing computation on useful decisions.

8.5 Rollout, MSA, Sparse Sampling, and Tree Search¶

Intuition

Sampling Methods II uses samples to choose decisions, not just evaluate policies. Imagine looking down several possible future roads before taking the first step.

flowchart TB
    A["Current state S_k"]:::state --> B1["First decision x1"]:::decision
    A --> B2["First decision x2"]:::decision
    B1 --> C1["Sampled futures"]:::sample
    B2 --> C2["Sampled futures"]:::sample
    C1 --> D1["Base policy / optimization"]:::policy
    C2 --> D2["Base policy / optimization"]:::policy
    D1 --> E1["Estimated value"]:::value
    D2 --> E2["Estimated value"]:::value
    E1 --> F["Implement best first decision only"]:::choice
    E2 --> F
    classDef state fill:#e0f2fe,stroke:#0284c7,stroke-width:2px,color:#0f172a;
    classDef decision fill:#ffedd5,stroke:#f97316,stroke-width:2px,color:#0f172a;
    classDef sample fill:#fef9c3,stroke:#ca8a04,stroke-width:2px,color:#0f172a;
    classDef policy fill:#ede9fe,stroke:#7c3aed,stroke-width:2px,color:#0f172a;
    classDef value fill:#dcfce7,stroke:#16a34a,stroke-width:2px,color:#0f172a;
    classDef choice fill:#f8fafc,stroke:#334155,stroke-width:2px,color:#0f172a;

Detailed comparison

Method	Main idea	Merit	Disadvantage
rollout	test first decisions, then follow base policy	improves a known rule	depends on base policy
MSA	choose first decision across multiple scenarios	anticipates uncertainty	scenario model can be large
sparse sampling	sample limited branches of future tree	controls computation	may miss important branches
Monte Carlo tree search	focus simulations on promising branches	efficient for large trees	harder to explain and tune

Worked example: sparse look-ahead delivery

At 5:00 PM, choose whether to keep one driver downtown. A full tree would model every possible future order. Sparse sampling uses only two sampled futures per decision:

x1 = keep driver downtown
sampled costs: 30, 35
average = 32.5

x2 = send driver to suburb
sampled costs: 20, 80
average = 50

Decision:

choose x1 because sampled look-ahead suggests lower expected cost.

Business interpretation:

The suburb trip is attractive in one future, but risky if downtown demand appears.

8.7 Slide Enrichment: Look-Ahead, Rollout, MSA, and Sparse Sampling¶

Mental model

Sampling Methods II uses samples inside the decision rule. Instead of merely evaluating a policy after the fact, the method asks: if I choose this current decision, what futures might follow?

Deterministic look-ahead

Use one forecast future:

\[ \min_x \left[R(S_k,x)+\text{forecast future cost}\right]. \]

Merit: fast and easy. Weakness: ignores uncertainty.

Stochastic look-ahead / MSA

Use multiple sampled futures:

\[ \min_x \frac{1}{N}\sum_{n=1}^{N}\text{cost of decision }x\text{ in scenario }n. \]

Merit: explicitly considers uncertainty. Weakness: scenario design and runtime matter.

Rollout

Evaluate current candidates by simulating a base policy afterward:

\[ \text{score}(x)=R(S_k,x)+\frac{1}{N}\sum_{n=1}^{N}J^{n}(\text{base policy after }x). \]

Merit: improves a simple policy. Weakness: quality depends on the base policy.

Sparse sampling intuition

Instead of expanding every possible future, sample only a limited number of branches at each depth. This is useful when the tree is huge.

flowchart TB
    A["Current state S_k"]:::state --> B1["Try x=A"]:::decision
    A --> B2["Try x=B"]:::decision
    B1 --> C1["sample a few futures"]:::sample
    B2 --> C2["sample a few futures"]:::sample
    C1 --> D1["simulate base policy"]:::policy
    C2 --> D2["simulate base policy"]:::policy
    D1 --> E["compare estimated totals"]:::value
    D2 --> E
    E --> F["implement first decision only"]:::decision
    classDef state fill:#dbeafe,stroke:#2563eb,stroke-width:2px,color:#0f172a;
    classDef decision fill:#ffedd5,stroke:#f97316,stroke-width:2px,color:#0f172a;
    classDef sample fill:#fee2e2,stroke:#dc2626,stroke-width:2px,color:#0f172a;
    classDef policy fill:#dcfce7,stroke:#16a34a,stroke-width:2px,color:#0f172a;
    classDef value fill:#ede9fe,stroke:#7c3aed,stroke-width:2px,color:#0f172a;

Worked example: delivery request acceptance

A courier can accept a current request for 12 profit, but it moves the courier away from a high-demand zone. Sampled futures estimate:

Decision	Immediate profit	Average future profit	Total
Accept	12	20	32
Reject	0	38	38

A look-ahead policy rejects because preserving position has higher sampled total value.

Chapter source note

Course basis: DDM look-ahead, rollout, MSA, and sampling slides. Textbook enrichment: Kochenderfer et al. on receding horizon planning, rollout, sparse sampling, and Monte Carlo tree search; Powell on direct lookahead policies. Only the first real decision is implemented.