Interactive lesson · Dynamic programming

Two parking lots.
One optimal policy.

Learn the classic Jack’s Car Rental problem by watching expected value emerge from thousands of possible rental-and-return outcomes.

Begin with the story

A single day, decoded

Location 110cars

Location 210cars

state(10, 10)+actionmove 2 →

Next: random requests and returns

Scroll to unpack the model

THE PROBLEM

Jack manages two car-rental locations.

Every evening, he can move cars. Every morning, demand and returns vary.

A rented car earns $10. Moving a car overnight costs $2. Demand and returns vary independently at each location, so Jack must optimize for expected long-run reward—not for one lucky day.

$10reward per rental

−$2per car moved

γ = .9future discount

±5max nightly move

Statecars at each location

Actioncars moved overnight

Environmentrandom requests & returns

Rewardrentals minus moving

THE STATES

The state is a pair, not a place.

441 possible mornings: (cars at 1, cars at 2)

Each location can hold 0–20 cars. One square in the grid is one complete state. The selected state below, (10, 10), means ten cars are ready at each location.

cars at location 2

cars at location 1

Selected states = (10, 10)

Markov property: once we know these counts, the past adds no information needed to predict the next state.

First coordinate
Cars at location 1

Second coordinate
Cars at location 2

Action
Positive means 1 → 2

RANDOMNESS IN THE ENVIRONMENT

A distribution, not a forecast.

Poisson tells us how likely each count is.

Requests · Location 1λ = 3

Returns · Location 1λ = 3

Requests · Location 2λ = 4

Returns · Location 2λ = 2

λ is an average, not a promise. With λ = 4, four requests is the most characteristic count—but zero, two, seven, or more can still occur. Policy iteration sums over all these possibilities.

ONE DAY

Sample the environment.

Same state. Same action. Different tomorrow.

Set the morning state

Location 1 10 carsLocation 2 10 carsOvernight action move 2 →

Move cost−$4

Ready for the overnight moveClick simulate to draw random events

LOCATION 110

requests —rented —returns —

LOCATION 210

requests —rented —returns —

reward this day$0$10 × rentals − $2 × cars moved

What did the simulator just do? It randomly drew four numbers from the Poisson distributions above: requests at location 1 (λ = 3), requests at location 2 (λ = 4), returns at location 1 (λ = 3), and returns at location 2 (λ = 2). Together, those four draws make one possible day—often called one Monte Carlo sample. The Bellman calculation below does not trust this one day; it averages all possible days, giving more likely combinations more weight.

THE VALUE

Value looks beyond today.

How good is a state if we keep following policy π?

V_π(s)=Σ_s′,rp(s′,r | s,π(s))[ r + γV_π(s′) ]

p(…) weights each possible rental/return outcome.

r is rental income minus transfer cost.

γV(s′) keeps 90% of tomorrow’s value.

For selected state (10, 10)$70.0

expected immediate reward$70.0

discounted future value$0.0

WORKED BELLMAN BACKUP

Where do those dollars come from?

policy action: move none

Start(10, 10)

After the overnight move(10, 10)

Moving 0 cars costs $0.

Demand is not replaced by its average. We consider every possible Poisson demand count d, limit rentals to the cars available, then weight that result by how likely d is:

E[rentals] = Σ_d=0…∞ min(d, cars available) × P(D = d)

LOCATION 1 · D₁ ~ POISSON(3)Cars available: 10E[rentals₁] = 3.00

LOCATION 2 · D₂ ~ POISSON(4)Cars available: 10E[rentals₂] = 4.00

Expected immediate reward$10 × (3.00 + 4.00) − $0= $69.95

THEN ADD TOMORROW0.9 × Σ_s′ P(s′ | s,a)V(s′) = 0.9 × $0.00 = $0.00

This is $0 at the start because policy evaluation initializes every next-state value V(s′) to zero. After one sweep, those values contain estimated future rewards, so this term becomes positive.

Where do returns enter? Poisson returns do not create today’s rental income. Together with demand, they determine the probability of each next state s′—so they affect the future-value term and tomorrow’s available cars.

Live dynamic programming

The policy iteration lab

Manual mode separates the loop: first evaluate the current policy by updating V, then improve the policy once by choosing the best action in every state.

Initial policyStart with policy: move no cars

Next: evaluate the current policy.One sweep applies a Bellman expectation backup to all 441 states while keeping π fixed.

POLICY ITERATION1current cycle

EVALUATION SWEEP0under current π

VALUE CELLS CHANGED0of 441 this sweep

LARGEST CELL ΔV0.00white ring = larger change

VALUE FUNCTIONCars at location 2 ↑

min $0max $0

Cars at location 1 →

INSPECTING STATE(10, 10)

Current value$0.00

Policy actionmove none

Latest max Δ0.000

IF WE BACKED UP THIS STATE NOWV_new(s) ← E[R + .9V_old(s′)]

Current estimate · “old V”$0.0

The value stored for state (10, 10) before another evaluation backup.

Bellman backup target · “new V”$70.0

The expected one-day reward plus 90% of the expected next-state value, using the current policy and current value table.

State residual · |target − old V|$69.95

The amount this state would change if backed up now. A large residual means its estimate is still inconsistent with the Bellman equation; near zero means it has nearly settled.

A new evaluation sweep would replace $0.0 with about $70.0 for this state.

Residual vs. max Δ: the residual predicts this selected state’s next change. “Latest max Δ” reports the largest change that actually occurred anywhere in the previous completed sweep.

Click any grid cell to inspect it. Try low inventory at location 2; the learned policy often sends cars toward its higher request rate.

VALUE THROUGH TIME · STATE (10, 10)$0.0

Run the first sweep. Values begin at zero.

sweep 0current 0

1Policy evaluationπ fixed; update V for all states

2Policy improvementV fixed; choose argmaxₐ q(s,a)

✓Is the policy stable?Test after the first improvement

Stability criterion

The policy is stable only when improvement chooses the same action as before in every state: π_new(s) = π_old(s) for all 441 states. In this lab, that means actions changed = 0. If even one state changes action, evaluate the new policy and improve again.

Do not confuse this with value convergence. A small max ΔV says evaluation of the current policy is nearly settled; zero changed actions says policy iteration itself can stop. For animation speed, “Run full loop” improves when max ΔV < 0.5 or after 12 evaluation sweeps.

Teaching implementation: the canonical 21×21 state space and ±5 actions are exact. Poisson sums collect probability mass at 11+ events into a tail bucket; evaluation is improved after convergence or 12 sweeps so the animation stays responsive.

VALUE ITERATION

Same model. A tighter loop.

What if we improve the action inside every value update?

Policy iteration keeps an action fixed while it evaluates that policy, then pauses to improve it. Value iteration skips that separation: every sweep evaluates all legal actions and immediately keeps the best one.

POLICY ITERATION

Evaluate, then improve

Fix πSeveral evaluation sweepsImprove π

The expectation backup uses only the action prescribed by the current policy. Once that policy is sufficiently evaluated, a separate improvement step compares actions.

VALUE ITERATION

Evaluate and improve together

Try every aKeep max q(s,a)Repeat

Each state gets one Bellman optimality backup. The winning action is also the current greedy policy for that state.

THE BELLMAN OPTIMALITY BACKUP

V_k+1(s) ← max_a Σ_s′,r p(s′,r | s,a)[r + γV_k(s′)]

The new ingredient is max_a. For each of the 441 states, we still average over every Poisson request-and-return combination. But now we do that once for every legal overnight move, then store the largest action value.

POLICY EVALUATIONV_k+1(s) ← Σ_s′,r p(s′,r | s,π(s))[r + γV_k(s′)]

Use one action: the action π(s) currently prescribes. This asks, “How good is this state if I keep following this policy?”

VALUE ITERATIONV_k+1(s) ← max_a Σ_s′,r p(s′,r | s,a)[r + γV_k(s′)]

Try every legal action: calculate the expectation for each one and keep the largest. That single backup evaluates and improves at the same time.

Everything inside the expectation is otherwise the same. Both methods use the same rental reward, movement cost, discount factor, and Poisson transition probabilities. The difference is whether the action is fixed by π or selected by max_a.

INTERACTIVE VALUE ITERATION

Watch the optimality backup sweep the same state space

Ready at V₀ = 0

OPTIMALITY SWEEP0one max backup per state

VALUE CELLS CHANGED0of 441 this sweep

LARGEST CELL ΔV0.00stop below $0.50

GREEDY ACTIONS CHANGED0during the latest sweep

VALUE ITERATION · V₀(s)Cars at location 2 ↑

min $0max $0

Cars at location 1 →

Question	Policy iteration	Value iteration
What happens in one update?	Use π(s) to update V^π(s)	Try every action and store max_a q(s,a)
When does the policy change?	In a separate improvement phase	During every optimality sweep
How much evaluation before improvement?	Several sweeps—ideally until V^π settles	One sweep, then immediately maximize again
What does the lab stop on?	No state changes action	The largest value change is below $0.50
What do they converge to?	The same optimal value V* and an optimal policy, for this finite discounted MDP.

Important: both are dynamic-programming methods. Both use the known Poisson transition probabilities and expected rewards; neither learns from the single-day samples above. The $0.50 threshold is for a readable animation—the mathematical sequence continues toward V*.

What to carry forward

Plan with a model of the environment.

DP uses a model

Jack’s Car Rental sums over known transition probabilities to perform expected-value backups.

Average the outcomes

Demand and returns are random. Planning weights possible outcomes by their Poisson probabilities.

Evaluate, then improve

Policy iteration evaluates a fixed policy before choosing better actions.

Maximize each sweep

Value iteration compares all legal actions at each update and keeps the largest expected value.

How can we learn without a transition table? Explore Monte Carlo prediction with Blackjack →

Two parking lots.One optimal policy.

Every evening, he can move cars. Every morning, demand and returns vary.

441 possible mornings: (cars at 1, cars at 2)

Poisson tells us how likely each count is.

Same state. Same action. Different tomorrow.

Set the morning state

How good is a state if we keep following policy π?

Where do those dollars come from?

The policy iteration lab

What if we improve the action inside every value update?

Evaluate, then improve

Evaluate and improve together

Watch the optimality backup sweep the same state space

Plan with a model of the environment.

DP uses a model

Average the outcomes

Evaluate, then improve

Maximize each sweep

Two parking lots.
One optimal policy.