Question 7 of 9: Probabilistic Dynamic Programming — The Parking-Space Problem

Question 7: Probabilistic Dynamic Programming — The Parking-Space Problem (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Spaces indexed $t=-T,\dots,-1,0,1,\dots,T$ in the order Robert reaches them (see Figure 2), with $t=0$ at the restaurant; $P(\text{space }t\text{ empty})=p_t$, independent across spaces; cost $|t|$ if he parks in space $t$; cost $M$ if he never parks. He observes emptiness only on arrival (no lookahead) and cannot revisit a passed space.

Find. A dynamic-programming formulation (state, Bellman recursion, boundary condition) yielding Robert's optimal stopping (parking) policy.

Approach. Work backward from the last space $T$. Define the expected cost-to-go before Robert learns whether the current space is empty; at each space he only faces a real choice (park vs. press on) when it turns out to be empty, so the recursion mixes "act optimally if empty" with "forced to continue if occupied."

1. State. Let the state be the current space index $t$, reached having already skipped every earlier empty space. Define $V(t)$ = Robert's minimum expected remaining cost on arriving at space $t$, before observing whether it is empty.
2. Boundary condition. If he reaches and skips the last space $T$, he ends up with no space at all: $V(T+1)=M$.
3. Bellman recursion. With probability $p_t$ space $t$ is empty, and Robert then chooses the cheaper of parking now (cost $|t|$) or continuing (expected cost $V(t+1)$); with probability $1-p_t$ it is occupied and he is forced onward, incurring $V(t+1)$: $$\boxed{V(t)=p_t\min\big[\,|t|,\,V(t+1)\,\big] + (1-p_t)\,V(t+1)},\qquad t=T,T-1,\dots,-T.$$
4. Solve backward. Compute $V(T),V(T-1),\dots,V(-T)$ in that order using the recursion (each step needs only the already-computed $V(t+1)$); $V(-T)$ is Robert's overall minimum expected cost for the whole approach.
5. Optimal policy — a threshold rule. At each space $t$, the recursion shows the optimal action when empty is: park if $|t|\le V(t+1)$, otherwise continue. Because $|t|$ decreases monotonically as $t\to0^-$ then increases for $t>0$, while $V(t+1)$ is non-increasing as $t$ approaches the restaurant (later stages have progressively better options), the optimal policy reduces to: skip empty spaces while still far from the restaurant, and start accepting the first empty space once $|t|$ drops to (or below) the expected cost of continuing — a critical-distance ("accept once close enough") rule, exactly analogous to the classical secretary/optimal-stopping structure.