Grid operators decide each day which power plants to switch on for the next 24 hours. With a lot of wind and solar on the grid, that decision rests on forecasts that can be badly wrong, and the costly mistakes are the rare ones: a wind lull at evening peak that forces load shedding. Averaging over forecast scenarios hides these events. Planning for the worst case keeps too many plants running. Conditional Value-at-Risk (CVaR), the average cost over the worst α-fraction of outcomes, sits between the two. Optimizing CVaR over many decision stages has a known cost, though. The planner has to track how much cost has built up so far, and adding that quantity to the state multiplies the number of states. This proposal compiles risk-averse multi-stage unit commitment into a decision diagram, a compressed graph that stores shared subproblems once. The key observation is that the accumulated-cost dimension only needs to be tracked for a thin band of states. Everywhere else it can be merged away exactly.
Put in two sentences: for a fixed tail threshold, CVaR becomes an ordinary expected-cost problem on a cost-augmented state. In that problem, every state whose remaining cost can no longer cross the threshold, or can no longer stay below it, has a value independent of the exact accumulated cost. A symbolic compiler can prove which states fall in each case and merge them, so the state space grows with the width of the uncertain band rather than with the full cost range. This keeps the Bellman recursion exact, allows 24 to 96 stages, and yields as a by-product the set of states from which catastrophe is still reachable. That set is exactly what is needed to avoid CVaR's habit of being needlessly cautious in safe states.
Core Claim
Rockafellar and Uryasev's identity, as used by Chow et al., writes the tail cost as a one-dimensional search over a threshold $\gamma$:
$$\mathrm{CVaR}_\alpha(Z)=\min_{\gamma}\Big\{\gamma+\tfrac{1}{\alpha}\,\mathbb{E}\big[(Z-\gamma)^+\big]\Big\},$$
where $Z$ is total operating cost including load shedding and $(\cdot)^+=\max(\cdot,0)$. For a fixed $\gamma$, the inner term is an expected-value problem. Its state is the grid state $x$ plus the accumulated cost $c$, and it pays a single terminal loss $(c-\gamma)^+$.
Suppose $\underline{R}(x)$ and $\overline{R}(x)$ are lower and upper bounds on the cost still to come from state $x$, each computed once. Then the value $V(x,c)$ splits into three cases:
$$V(x,c)=\begin{cases}0 & c+\overline{R}(x)\le\gamma,\\ c-\gamma+\mathbb{E}[R(x)] & c+\underline{R}(x)\ge\gamma,\\ \text{solved by recursion} & \text{otherwise.}\end{cases}$$
In the first case, every $(x,c)$ collapses into one terminal node. In the second case, the problem reduces to the risk-neutral subproblem on $x$ alone, shifted by a constant, and that subproblem is shared across all $c$. Only the third case, the band where the tail is still undecided, needs nodes indexed by accumulated cost. We claim the band is narrow for realistic unit-commitment instances. The reason is physical: most of the day's cost is fixed early by commitment decisions, and tail cost comes from a small set of ramp-limited, low-reserve states. We further claim that compiling the band symbolically makes exact multi-stage CVaR unit commitment tractable at horizons where scenario-tree mixed-integer programs stall.
Relation to Prior Work
The mechanism comes from Babaki et al.. They compile multi-stage stochastic constraint programs into And-Or decision diagrams by merging search nodes that share an "active factor context," which let them reach 25 stages where branch-and-bound failed past 6. They state explicitly that their compiler handles only expected utility, with no chance constraints or CVaR. We supply the missing piece: a cost-augmented context whose merging rule is the three-case split above. The supporting symbolic machinery comes from Kwiatkowska et al., who run value iteration entirely on multi-terminal decision diagrams (diagrams with real-valued leaves) for games with over 17 million states, but only for reachability and expected-reward objectives. Speck and Katz contribute two things. They track utilities with real-valued diagrams during layered reachability search. They also warn that real-valued diagrams lack complement edges and use more memory than bit-sliced Boolean encodings. That warning constrains our design: we store the budget index bit-sliced rather than as real-valued leaves.
The risk side builds on Rigter et al., whose CVaR-EV method first optimizes CVaR, then minimizes expected cost subject to never exceeding the resulting VaR threshold, switching to the expected-value policy once the tail is out of reach. Their method uses explicit states, reports roughly 150% runtime overhead from augmentation, and was never applied to power systems. Our "safe" region (case one) is exactly their switching condition, but we compute it as a symbolic set over all states at once rather than checking it along each executed path. The application gap comes from Mahmutoğulları et al., who show that multi-stage risk-averse unit commitment beats two-stage commitment, especially under high uncertainty. Their solver is a scenario-tree mixed-integer program that needs about 2,000 seconds on a 10-generator fleet, and they fall back on a rolling-horizon heuristic. Campion et al. motivate a structured, non-MIP representation of unit commitment but remain deterministic. Puggelli et al. verify wind-dependent pricing strategies against probability thresholds, which ignore how bad a violation is. That is the gap CVaR closes. Finally, Accurate Forecasts Do Not Ensure Safe Decision motivates judging methods on realized tail cost rather than forecast error.
Research Program
Model. Each generator has an on/off status, a minimum-up/down counter, and a few discrete output levels. Stochastic net load follows a Markov lattice built from wind and solar forecast residuals. We strip the deterministic daily shape before fitting the residual chain, following the ensemble-mean subtraction in Marikkar et al.. Stages are hourly (24) and quarter-hourly (96). Load shedding carries a high penalty and is the main source of tail cost.
Compilation. We extend the And-Or compiler so that each node's cache key is its active-factor context plus a budget tag, which is one of three values: saturated-safe, saturated-lost, or a discretized residual budget $\gamma-c$ inside the band. The bounds $\underline{R}$ and $\overline{R}$ come from a cheap backward symbolic pass over a relaxed model that drops minimum-up/down timing. That pass makes the bounds valid but loose. Discretizing the budget introduces error bounded by the grid step times the number of stages. We will state this bound and verify it empirically against a fine-grid solution on small instances.
Outer search and tie-breaking. The objective is convex in $\gamma$, so an outer golden-section search over $\gamma$ reuses subdiagrams between iterations where the band overlaps. A lexicographic second pass then minimizes expected cost over the CVaR-optimal actions, restricted to case-one states.
Analysis. We will measure how band width scales with fleet size, reserve margin, α, and variable ordering. Ordering matters because of Babaki et al.'s finding that late hidden variables inflate contexts. Here, placing weather variables before commitment variables in each stage is the ordering we expect to help.
Baselines
Naive reference. Deterministic unit commitment on the point forecast plus a fixed spinning-reserve margin, re-solved each stage. This represents current practice and fixes the scale for tail improvement.
Strongest existing method. The multi-stage risk-averse scenario-tree mixed-integer program of Mahmutoğulları et al., together with their rolling-horizon heuristic, reimplemented with CVaR in place of mean-upper-semideviation. Both are coherent risk measures, so the swap is minimal. Their reported figure is roughly 2,000 seconds for the multi-stage model on a 10-generator fleet. No reported result found on Lacuna for their CVaR cost values on a public instance, so we will reproduce their 10-generator setting and report our own numbers.
Explicit risk-averse planner. The explicit-state CVaR-EV planner of Rigter et al. run on our discretized model. It solves the same objective without compression and isolates the value of the symbolic representation.
Unmodified symbolic expected-value planner. The Babaki et al. compiler with expected cost only. It shows what compression gives without risk.
Key ablation. Our compiler with full budget augmentation but without the three-case merging. This isolates the band idea itself.
Fairness. All methods share one scenario lattice, one discretization, one CPU budget, and one memory cap. The mixed-integer program gets a commercial-grade solver and a tuning pass over its gap tolerance. The proposal wins if two things hold. First, it matches the exact scenario-tree CVaR within the stated discretization bound where that program solves at all. Second, it solves instances with 30 to 100 generators or 96 stages to optimality where the program either times out or returns rolling-horizon solutions with higher out-of-sample CVaR.
Why not just…?
Why not just use rolling-horizon mixed-integer programming, as Mahmutoğulları et al. already do? This is the real threat. On small fleets the program is exact and fast enough, and we expect no advantage there. Rolling horizon gives up the multi-stage coupling whose value those same authors measure, and that coupling matters most in the high-uncertainty regime where tail risk lives. The experiments settle it directly. If rolling horizon's out-of-sample CVaR stays within a few percent of our exact solution on large instances, the contribution shrinks to a runtime story, and we will report that.
Why not just run CVaR-EV on explicit states? Rigter et al. already report substantial augmentation overhead on small domains. Unit commitment states multiply generator statuses, timing counters, and weather levels, so explicit enumeration fails early. The explicit-baseline scaling curve will show at what fleet size this happens.
Why not just train a risk-averse reinforcement learning policy with worst-trajectory sampling, as in EPOpt or ADA-CVaR? EPOpt and ADA-CVaR scale to large spaces but give no optimality certificate. They also estimate the tail from few samples, which is the sample-inefficiency problem that quantile gradients such as Boosting CVaR Policy Optimization with Quantile Gradients try to fix. Our exact solutions on mid-size instances will serve as ground truth for measuring how far such a policy's CVaR falls from optimal. That comparison is informative whether or not the policy is competitive.
Proposed Experiments
Primary study. We reproduce the 10-generator day-ahead setting of Mahmutoğulları et al. with wind-driven net load. We then scale to 30, 60, and 100 generators and to 96 stages. The primary metrics are out-of-sample CVaR at α = 0.05 and 0.01, expected cost, load-shedding frequency, wall-clock time, and peak diagram size.
Decisive test of the core claim. We measure the fraction of cost-augmented nodes that fall in the undecided band, and how that fraction varies with α and reserve margin. If the band covers most of the augmented space, the premise fails and the method reduces to plain augmentation. The key ablation measures this directly.
Test of the lexicographic pass. We compare expected cost in case-one states against pure CVaR solutions. The pass should reduce expected cost without raising CVaR, reproducing Rigter et al.'s effect in a power-system setting.
Stress test. We rebuild the scenario lattice from extreme-weather residuals. Following Doudi et al., we will use these only for the tail stress test, since they show climate simulations add little for short-term forecasting. This checks whether the band widens under heavier tails.
References
- Risk-Constrained Reinforcement Learning with Percentile Risk Criteria
- Compiling Stochastic Constraint Programs to And-Or Decision Diagrams
- Symbolic Verification and Strategy Synthesis for Turn-Based Stochastic Games
- Symbolic Search for Oversubscription Planning
- Lexicographic Optimisation of Conditional Value at Risk and Expected Value for Risk-Averse Planning in MDPs
- The Value of Multi-Stage Stochastic Programming in Risk-Averse Unit Commitment Under Uncertainty
- Challenge: Modelling Unit Commitment as a Planning Problem
- Robust strategy synthesis for probabilistic systems applied to risk-limiting renewable-energy pricing
- Accurate Forecasts Do Not Ensure Safe Decision
- Modified Auto Regressive Technique for Univariate Time Series Prediction of Solar Irradiance
- EPOpt: Learning Robust Neural Network Policies Using Model Ensembles
- Adaptive Sampling for Stochastic Risk-Averse Learning
- Boosting CVaR Policy Optimization with Quantile Gradients
- Impact of Simulated Climate Data on Wind Power Prediction and Long-Term Grid Planning