Dynamic Programming Recursion for an Expected Asset Position: 23-Ind-A1 Operations Research, May 2016, Q8

Question 8: Dynamic Programming Recursion for an Expected Asset Position (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. Months $t=1,\dots,60$; each month a job offer pays $d dollars if not captured, with capture probability $p_t$ (loses everything if captured); starting assets $50,000 at the start of month 1; each month Dirk may accept or decline the offer.

Find. A dynamic programming recursion — state, stage, decision, transition and boundary condition — that Dirk can use to maximize his expected end-of-month-60 asset position. Formulate only ($d$ and $p_t$ are given symbolically, not numerically, so the recursion is not evaluated).

Approach. Model each month as a DP stage, current cash as the state, and "accept/decline the job" as the decision; write the one-period expected-value recursion and its boundary condition at the planning horizon.

Define stage, state and decision. Stage = month $t=1,\dots,60$ (plus a fictitious closing stage $t=61$ marking "end of month 60"). State $x$ = Dirk's cash on hand at the start of month $t$ ($x_1=50{,}000$). Decision at stage $t$: $\text{Accept}$ the job or $\text{Decline}$ it.
Define the value function. Let $f_t(x)$ = the maximum expected asset position at the end of month 60, given cash $x$ at the start of month $t$ and an optimal policy followed from month $t$ onward.
Model the one-period transition. Declining leaves the state unchanged going into month $t{+}1$: $x\to x$. Accepting risks capture: with probability $p_t$ Dirk is caught and loses everything ($x\to 0$); with probability $1{-}p_t$ he keeps the job's $d dollars on top of his cash ($x\to x+d$).
Write the recursion. Taking the better of the two decisions each month: $$f_t(x) = \max\Big\{\ \underbrace{f_{t+1}(x)}_{\text{decline}},\ \ \underbrace{p_t\,f_{t+1}(0) + (1-p_t)\,f_{t+1}(x+d)}_{\text{accept}}\ \Big\},\qquad t=1,\dots,60.$$
Boundary condition and the answer sought. At the close of month 60 no further decisions remain, so the value is simply the cash on hand: $$f_{61}(x) = x.$$ Solving the recursion backward from $t=61$ down to $t=1$ and evaluating at Dirk's actual starting cash gives his maximum expected asset position, $\boxed{f_1(50{,}000)}$ — the numeric value cannot be produced because $d$ and the sequence $p_1,\dots,p_{60}$ are not given, consistent with the question asking only that the recursion be "formulated."

Check: the recursion assumes Dirk's decision each month depends only on his current cash $x$ (a Markov state) and that a captured Dirk has no further decisions to make (he loses everything and, implicitly, cannot re-offend) — both are the natural reading of "if Dirk is captured, all his money will be lost" and "maximize his expected asset position at the end of month 60."

Final results — Question 8 (recursion, not evaluated)
Item	Value
State	$x$ = cash on hand at start of month $t$
Stages	$t=1,\dots,60$, plus closing stage 61
Recursion	$f_t(x)=\max\{f_{t+1}(x),\ p_tf_{t+1}(0)+(1-p_t)f_{t+1}(x+d)\}$
Boundary	$f_{61}(x)=x$
Quantity sought	$f_1(50{,}000)$

Topic: Stochastic dynamic programming with an absorbing (ruin) state.

Key relations: One-period Bellman equation with a binary decision, $f_t(x)=\max_{\text{action}} E\big[f_{t+1}(x')\big]$; capture acts as an absorbing state where all future value collapses to $f_{t+1}(0)$, propagated forward at whatever cash level 0 arises.

Why this works: Because "expected asset position" is linear in the terminal cash and the accept/decline choice only ever depends on the current cash level (not on how it was accumulated), the state truly is Markov, so a one-dimensional value function $f_t(x) is sufficient — no need to track the full history of past decisions.

Common pitfall: Writing the accept branch as $f_{t+1}(x)+p_t\cdot 0+(1-p_t)d$ (adding the expected dollar gain directly to next month's value) instead of correctly branching on the two different resulting states, $0$ or $x+d$, each carried into its own $f_{t+1}(\cdot)$ — the two are only equal if $f_{t+1}$ is linear in $x$, which is not generally guaranteed once later stages' own optimal stopping is taken into account.

Source: Hillier & Lieberman, Introduction to Operations Research (11th ed.), ch. 11 (probabilistic dynamic programming).

Question 8 of 8: Dynamic Programming Recursion for an Expected Asset Position

Question 8: Dynamic Programming Recursion for an Expected Asset Position (20 marks)