Stochastic DP

342. Stochastic DP

Extends deterministic DP to problems with random transitions. The framework underlying Markov Decision Processes (MDPs), reinforcement learning, and most multi-period stochastic optimization in operations.

342.1. Setup

At stage $𝑡$ in state $𝑠_{𝑡}$ :

Choose action $𝑎_{𝑡} \in 𝒜︀ (𝑠_{𝑡})$
Pay immediate cost $𝑐_{𝑡} (𝑠_{𝑡}, 𝑎_{𝑡})$
Next state is random: $𝑠_{𝑡 + 1} \sim 𝑃_{𝑡} (\cdot | 𝑠_{𝑡}, 𝑎_{𝑡})$ — transition probability depending on current state and action

After the last decision: terminal cost $𝑐_{𝑇} (𝑠_{𝑇})$ .

342.2. Policy (not plan)

A fixed plan $(𝑎_{0}, 𝑎_{1}, \dots, 𝑎_{𝑇 - 1})$ no longer works — you don’t know which state will realize at each step. Instead, a policy is a function:

𝜋_{𝑡} : 𝒮︀ \to 𝒜︀, 𝜋_{𝑡} (𝑠) is the action taken in state 𝑠 at stage 𝑡

Total cost is a random variable; we minimize its expectation:

𝐽^{𝜋} (𝑠_{0}) = 𝐸 [\sum_{𝑡 = 0}^{𝑇 - 1} 𝑐_{𝑡} (𝑠_{𝑡}, 𝜋_{𝑡} (𝑠_{𝑡})) + 𝑐_{𝑇} (𝑠_{𝑇})]

342.3. Stochastic Bellman equation

Same argument as the deterministic case (additivity + principle of optimality, now applied to expected cost):

𝐽_{𝑡} (𝑠) = min_{𝑎 \in 𝒜︀ (𝑠)} {𝑐_{𝑡} (𝑠, 𝑎) + \sum_{𝑠^{'}} 𝑃_{𝑡} (𝑠^{'} | 𝑠, 𝑎) 𝐽_{𝑡 + 1} (𝑠^{'})}

Equivalently:

𝐽_{𝑡} (𝑠) = min_{𝑎} {𝑐_{𝑡} (𝑠, 𝑎) + 𝐸_{𝑠^{'} \sim 𝑃_{𝑡} (\cdot | 𝑠, 𝑎)} [𝐽_{𝑡 + 1} (𝑠^{'})]}

The expectation over $𝑠^{'}$ replaces the deterministic transition $𝑓_{𝑡} (𝑠, 𝑎)$ from the deterministic Bellman.

342.4. Side-by-side comparison

deterministic: 𝐽_{𝑡} (𝑠) = min_{𝑎} {𝑐_{𝑡} (𝑠, 𝑎) + 𝐽_{𝑡 + 1} (𝑓_{𝑡} (𝑠, 𝑎))}

stochastic: 𝐽_{𝑡} (𝑠) = min_{𝑎} {𝑐_{𝑡} (𝑠, 𝑎) + 𝐸 [𝐽_{𝑡 + 1} (𝑠^{'})]}

342.5. Worked example

From state $𝐵$ at stage $1$ , action “right” leads to:

$𝐶$ with probability $0.7$ (immediate cost $1$ , $𝐽_{2} (𝐶) = 2$ )
$𝐷$ with probability $0.3$ (immediate cost $6$ , $𝐽_{2} (𝐷) = 4$ )

𝑄_{1} (𝐵, right) = 0.7 (1 + 2) + 0.3 (6 + 4) = 2.1 + 3.0 = 5.1

If action “left” gives $4.5$ , optimal action at $(𝑡 = 1, 𝐵)$ = left.

342.6. Examples

(s, S) inventory policy — order up to $𝑆$ when inventory drops below $𝑠$ ; optimality is a stochastic-DP result
Multi-period newsvendor — stochastic demand each period, carry inventory between periods
Revenue management — DP on (remaining capacity, time-to-go)
Optimal stopping — secretary problem, asset selling, exercise of American options
Reinforcement learning — model-free / sample-based stochastic DP

342.7. Finite vs infinite horizon

Finite horizon: just solve backward in time as in deterministic case
Infinite horizon: leads to value iteration / policy iteration

342.8. Curse of dimensionality + curse of randomness

Stochastic DP inherits the dimensionality curse from deterministic DP, plus the cost of computing expectations over the next-state distribution. Approximations:

Sampling: replace exact expectation with Monte Carlo estimate
Approximate DP / Neuro-DP: function approximation for $𝐽_{𝑡}$
Reinforcement learning: sample-based, model-free

342.9. See also

Bellman Equation — deterministic version
Value Iteration
Policy Iteration
Markov Chains — underlying state-transition model