Two-Month Markov Decision Process — Advertising Policy: 23-Ind-A1 Operations Research, Undated paper, Q9

Question 9: Two-Month Markov Decision Process — Advertising Policy (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. Two states (High/Low sales); each month the company chooses Advertise / No-ad, then sales transition per the state- and action-dependent probabilities and returns tabulated below.

Transition probabilities and returns by current state and action
From \ Action	To High	To Low
High, no ad	p=0.5, ret 10	p=0.5, ret 4
High, ad	p=0.8, ret 7	p=0.2, ret 6
Low, no ad	p=0.2, ret 7	p=0.8, ret −2
Low, ad	p=0.4, ret 3	p=0.6, ret −5

Find. The optimal action (advertise / no ad) at each decision epoch (start of month 1 and start of month 2) for each possible current state, maximizing total expected 2-month return.

Approach. Solve by backward induction (finite-horizon dynamic programming) over the 2 decision epochs: first find the optimal month-2 (last-month) action and value for each state with no further future to consider, then use those values as continuation values to find the optimal month-1 action for each state.

Backward-induction result: month-1 optimal action depends on the current state; month-2 optimal action is "no ad" regardless of state. Node values $V$ are total expected return from that state to the end of month 2.

Stage 2 (last month, no continuation value) — state High: $$E[\text{no ad}\mid H]=0.5(10)+0.5(4)=7.0,\qquad E[\text{ad}\mid H]=0.8(7)+0.2(6)=6.8$$ $$\boxed{V_2(H)=7.0,\ \text{optimal: no ad}}$$
Stage 2 — state Low: $$E[\text{no ad}\mid L]=0.2(7)+0.8(-2)=-0.2,\qquad E[\text{ad}\mid L]=0.4(3)+0.6(-5)=-1.8$$ $$\boxed{V_2(L)=-0.2,\ \text{optimal: no ad}}$$
Stage 1 (month 1), using $V_2$ as the continuation value — state High: $$E[\text{no ad}\mid H]=0.5(10+V_2(H))+0.5(4+V_2(L))=0.5(17.0)+0.5(3.8)=10.4$$ $$E[\text{ad}\mid H]=0.8(7+V_2(H))+0.2(6+V_2(L))=0.8(14.0)+0.2(5.8)=12.36$$ $$\boxed{V_1(H)=12.36,\ \text{optimal: ADVERTISE}}$$
Stage 1 — state Low: $$E[\text{no ad}\mid L]=0.2(7+V_2(H))+0.8(-2+V_2(L))=0.2(14.0)+0.8(-2.2)=1.04$$ $$E[\text{ad}\mid L]=0.4(3+V_2(H))+0.6(-5+V_2(L))=0.4(10.0)+0.6(-5.2)=0.88$$ $$\boxed{V_1(L)=1.04,\ \text{optimal: no ad}}$$

Final results — Question 9 (optimal policy)
State \ Month	Month 1	Month 2
High	Advertise (V=12.36)	No ad (V=7.00)
Low	No ad (V=1.04)	No ad (V=−0.20)

Topic: Finite-horizon Markov decision process, solved by backward induction (dynamic programming).

Key relations: Bellman recursion $V_t(s)=\max_a\sum_{s'}P(s'\mid s,a)\big[r(s,a,s')+V_{t+1}(s')\big]$, with $V_{T+1}\equiv0$ at the horizon.

Why this works: Because the future only depends on the current state (Markov property), the optimal action at month 1 can be found once the optimal VALUE of being in each state at month 2 is known — there is no need to enumerate all $2\times2\times2\times2=16$ two-month action sequences explicitly.

Common pitfall: Optimizing month 1's action using only its OWN immediate expected return (ignoring $V_2$) — a myopic solver would pick no-ad from High (immediate no-ad $7.0$ beats immediate ad $6.8$), missing that advertising is actually optimal once each action's downstream consequences (via $V_2$) are included.

Source: Hillier & Lieberman, Introduction to Operations Research (11th ed.), ch. 16 (Markov decision processes).

Question 9 of 10: Two-Month Markov Decision Process — Advertising Policy

Question 9: Two-Month Markov Decision Process — Advertising Policy (20 marks)