Stochastic and Dynamic Optimization

The most tempting way to handle an uncertain input is to replace it with its average and solve the deterministic problem that results. It feels reasonable, and it is almost always wrong. The trap has a name — the flaw of averages — and its essence is that the optimal decision for the average scenario is generally not the decision that performs best on average across all scenarios. Plan a factory for average demand and it will be idle in the slump and overwhelmed in the boom, and the cost of being wrong in both directions is exactly what averaging throws away.

The reason is structural. Costs are usually asymmetric and nonlinear in the uncertain quantity: running short might cost far more per unit than running long, or vice versa. When the cost of a decision is a curved (convex) function of the random outcome, the expected cost is not the cost at the expected outcome — a fact known as Jensen's inequality. A plan tuned to the mean sits at the bottom of the wrong curve.

Most decisions under uncertainty share a common shape: you commit to something now, the world then reveals itself, and you adjust as best you can. Two-stage stochastic programming formalises exactly this. The first-stage (or here-and-now) decision \(\mathbf{x}\) is made before the random outcome \(\omega\) is known. Then \(\omega\) is observed, and a second-stage (or recourse) decision \(\mathbf{y}(\omega)\) cleans up — meeting shortfalls, absorbing surpluses, correcting the plan for the outcome that actually happened.

Because the recourse cost depends on the random outcome, the objective minimises the first-stage cost plus the expected cost of the best recourse:

That last point is what makes stochastic programming practical. A continuous distribution is approximated by a scenario tree — a finite set of outcomes with probabilities — and the expectation collapses into a sum over the leaves. The art is keeping the tree small enough to solve yet rich enough to capture the uncertainty that actually drives the decision.

Two questions immediately follow. First, how much would a perfect forecast be worth — the ability to know \(\omega\) before deciding? Second, how much does it help to model the uncertainty at all, rather than just planning for the mean? Both answers are numbers you can compute, and they are among the most useful quantities in the whole subject because they justify the modelling effort in the language of money.

Three benchmark solutions frame them. The recourse problem value \(RP\) is the honest stochastic optimum of Section 28-2. The wait-and-see value \(WS\) is the expected cost if you could see each outcome before deciding — the best possible, and generally unattainable. The expected result of the expected-value solution \(EEV\) is what you actually pay if you optimize for the mean and then live in the random world.

The two numbers answer different management questions. A large EVPI says a better forecast — more sensors, a market survey, a weather service — could pay for itself, because uncertainty is genuinely costing you. A large VSS says the stochastic model itself is earning its keep, and that anyone still planning for the average is leaving that much on the table. A small VSS, conversely, is permission to use the simpler deterministic model with a clear conscience. Examples 1–3 compute all of this for one concrete decision.

Recourse handles uncertainty in the objective. But sometimes the uncertainty threatens a constraint — a reservoir must not overflow, a network must not exceed capacity, a structure must not fail — and demanding that the constraint hold for every conceivable outcome is often impossibly conservative or literally infeasible. Chance-constrained programming relaxes "always" to "almost always": the constraint need only hold with a specified high probability.

The reformulation is clean and worth seeing. If a buffer \(x\) must cover a normal demand \(D \sim \mathcal N(\mu,\sigma^2)\) with probability \(1-\alpha\), then \(\Pr[D \le x] \ge 1-\alpha\) becomes \(x \ge \mu + z_{1-\alpha}\,\sigma\). The uncertainty has been compressed into a single safety margin \(z_{1-\alpha}\sigma\), and tightening the service level simply buys a larger quantile — a cost you can read straight off the normal table, as Example 4 does.

A stricter philosophy abandons probabilities altogether. Robust optimization asks only that the solution remain feasible for every outcome in a bounded uncertainty set \(\mathcal U\), and optimizes against the worst case within it — \(\min_{\mathbf{x}} \max_{\omega\in\mathcal U} f(\mathbf{x},\omega)\). It needs no distribution, only the range of possibilities, which is exactly its appeal when probabilities are unknown or the cost of any failure is unacceptable. The price is conservatism: a robust plan pays a premium to be safe against outcomes that may be extremely unlikely, and the size of \(\mathcal U\) is the dial between safety and that premium.

The second half of the chapter turns from a single uncertain decision to a sequence of them, where each choice not only earns an immediate reward but also moves the system into a new situation that shapes every choice to come. Chapter 17 handled the deterministic version of this with dynamic programming; here the transitions are random, and the right framework is the Markov decision process.

The defining feature is the Markov property: the transition depends only on the current state and action, not on the path that led there. The state is a sufficient summary of history — everything relevant about the past is baked into where you are now. That single assumption is what makes the problem tractable, because it lets a decision rule depend on the state alone.

The goal is a policy \(\pi\) that maximises the expected discounted sum of rewards, \(\mathbb{E}\big[\sum_{t=0}^{\infty} \gamma^{t} r(s_t, a_t)\big]\). The discount factor \(\gamma\) earns its place twice over: mathematically it keeps an infinite sum finite, and practically it encodes how far ahead the decision maker cares to look — a reward \(t\) steps away is worth \(\gamma^{t}\) of its face value, so the effective horizon is roughly \(1/(1-\gamma)\) steps. At \(\gamma = 0.9\) the planner sees about ten steps ahead; at \(0.99\), a hundred.

The value of a state under the best policy obeys a single self-referential equation — the stochastic form of Bellman's principle of optimality from Chapter 17. The optimal value of being in state \(s\) is the best immediate reward plus the discounted expected value of wherever that action lands you:

Two algorithms solve it, and both are foundational. Value iteration turns the equation into an update: start from any guess \(V_0\), and repeatedly apply the right-hand side as an assignment, \(V_{k+1}(s) \leftarrow \max_a[\,r(s,a) + \gamma\sum_{s'}P(s'|s,a)V_k(s')\,]\). The map is a contraction whenever \(\gamma < 1\), so the iterates converge geometrically to \(V^{\star}\) from any starting point — a guarantee as clean as the annealing schedule's, and far more usable. Example 5 runs two sweeps by hand.

Policy iteration alternates two steps instead. Given a policy, evaluate it by solving the linear system \(V^{\pi}(s) = r(s,\pi(s)) + \gamma\sum_{s'}P(s'|s,\pi(s))V^{\pi}(s')\); then improve it by making each state greedy with respect to those values. Each round produces a strictly better policy until none changes, and because there are finitely many policies it terminates exactly — usually in very few iterations. Example 6 does one improvement step and watches a lazy policy correct itself.

The methods of this chapter are best organised by two questions: is the uncertainty in the objective or a constraint, and is the decision a single commitment or a sequence over time?

The through-line of the chapter is a single correction to a natural mistake. The deterministic optimization of the earlier parts silently assumes the future is known — and the moment it is not, planning for the average quietly optimizes the wrong thing. Stochastic programming replaces the average with an expectation over scenarios; chance and robust methods replace "feasible" with "feasible often enough" or "feasible always"; and Markov decision processes replace a one-shot plan with a policy that keeps re-deciding as the world reveals itself. Different machinery, one correction: decide against the distribution of futures, not against a single imagined one.

Examples 1–3 share one setup. A firm orders a quantity \(x\) at \(2\) per unit before demand \(D\) is known; \(D = 40\) with probability \(0.7\) and \(D = 100\) with probability \(0.3\). Shortage costs \(5\) per unit (emergency buying), surplus costs \(1\) per unit (holding). The total cost of ordering \(x\) when demand turns out to be \(d\) is \(\;C(x,d) = 2x + 5\max(d-x,0) + \max(x-d,0)\).

For the recourse problems, always evaluate a candidate decision across all scenarios before comparing — the average of the costs, not the cost at the average. For the MDP problems, apply the Bellman backup one state at a time, taking the max over actions. Difficulty rises down the list.