Proposition 5, p. 16 — the nested risk-adjusted cost v(π̂) of the inner-approximation policy is at most y

Consider a $T$-stage stochastic linear program with stagewise independent finite outcomes,

where $T\ge2$ and each one-step risk measure $\rho_t$, $t=2,\dots,T$, is coherent (subadditive, monotone, positively homogeneous and translation equivariant). For $s=2,\dots,T$ let $x^1_{s-1},\dots,x^{J_{s-1}}_{s-1}$ be points with numbers $q^j_s$, and let $\hat{\mathcal Q}_s$ be the inner approximation they define (the lower boundary of the convex hull of the $(x^j_{s-1},q^j_s)$), with $\hat{\mathcal Q}_{T+1}\equiv0$. Assume the $q^j_s$ are upper bounds:

Let $\hat\pi$ be a policy defined by these Bellman functions: at every state and outcome with a feasible stage problem its action $\hat x_t(x_{t-1},\omega_t)$ minimizes $c_t^\top x_t+\hat{\mathcal Q}_{t+1}(x_t)$ over $\mathcal X_t(\omega_t)$, and $\hat x_1$ solves

Let $v(\hat\pi)=c_1^\top\hat x_1+\bar\rho_2\big(\hat v_2(\hat x_1,\omega_2)\big)$ be the nested risk-adjusted cost of $\hat\pi$, where $\hat v_t(x_{t-1},\omega_t)=c_t^\top\hat x_t+\bar\rho_{t+1}(\hat v_{t+1}(\hat x_t,\omega_{t+1}))$ is the actual risk-adjusted cost of $\hat\pi$ over stages $t,\dots,T$. Then

Thus the optimal value $y$ of the first-stage problem built on the inner approximation is a deterministic upper bound on the risk-adjusted cost of the policy it defines; together with the lower bound from outer approximation it brackets the cost of a computable risk-averse policy, which is otherwise hard to estimate by sampling under a nested risk measure.

Formalization Note Costs live in $\mathbb R\cup\{+\infty\}$ (EReal); $\bar\rho_t$ is $+\infty$ when some outcome has infinite cost, an infeasible stage costs $+\infty$, and $\hat{\mathcal Q}_s$ is $+\infty$ off the convex hull of its points. The bound is trivially true when $y=+\infty$; it is informative when $\hat x_1$ lies in the convex hull of the stage-1 points. Standing assumptions made explicit: $T\ge2$; $\rho_t$ coherent for $t=2,\dots,T$; the terminal convention $\rho_{T+1}(Q_{T+1})=0$ (the first option on p. 4, used in the proof); (8) without $x_1\ge0$, as printed. The upper-bound hypothesis is stated for the risk-adjusted optimal value of the stage problem (13) at the points, the form the proof uses on p. 17 ("$\hat{\mathcal Q}_t(x_{t-1})$ is an inner approximation of the risk-adjusted optimal value function of (13)") and the Upper Bound Computation (U) computes on p. 18; p. 16 phrases it as a bound on the true value $\rho_{t+1}(Q_{t+1}(x_t,\omega_{t+1}))$, under which the proof does not go through. The policy is any selection with the minimizing property, required at every feasible state.