Policy Graphs

Purpose

The stage index $t \in \{1, \ldots, T\}$ used throughout SDDP Algorithm (the 1-based math convention) is the special case of a more general structure: a policy graph of nodes and transitions, in which a stage may hold more than one node and a node may carry its own local realization. This chapter defines that structure — nodes, transitions, and future-cost pools; the two probability axes a policy graph carries; why discount is a stage-level, not an edge-level, quantity; how the structure maps onto the SDDP.jl family; its current structural limitations; and the additional restriction an exact (enumerated) backward/forward pass imposes that a sampled pass does not. It is the structural foundation the rest of the stochastic-modelling chapters build on.

1. Nodes, Transitions, and Future-Cost Pools

A node $n$ has a unique identifier, sits at a study stage $t(n)$ , may point into that stage’s own realization column (present only where the node’s stage carries an externally supplied scenario), and may carry a label.

A transition is a directed edge from a node to a node exactly one stage later, weighted by a transition probability. Every edge advances the graph by exactly one stage — a policy graph has no same-stage or backward edges.

The simplest policy graph is an implicit stage chain: no nodes are declared, every stage holds exactly one (unnamed) node, and each transition’s endpoints are stage ids rather than node ids. This is the chain already described in SDDP Algorithm §2 and is the graph every prior chapter assumes. Declaring nodes explicitly generalises the same structure: a stage may then hold several nodes, each with its own identity and (optionally) its own realization pointer.

A node with no outgoing transition is a leaf; a node with no incoming transition is a root. Every non-leaf node owns its own future-cost (Benders cut) pool — the per-node generalisation of the per-stage cut pool described in Cut Management. On the implicit stage chain, one node per stage collapses this back to exactly the per-stage pool already documented there. All leaf nodes across the whole graph share a single pool, to which the backward pass adds no cut, because a leaf’s future cost is the shared terminal condition (§5).

The backward pass, run node by node from the leaves toward the root, builds a node’s cut from its children’s subproblems: at each trial point it solves every child under every opening of that child and aggregates all the (child, opening) pairs at once (§2). The forward pass samples a single root→leaf trajectory — one node per stage along the path it visits — and makes decisions using each visited node’s current cut approximation.

Circles are pool-owning (non-leaf) nodes; ovals are leaves sharing the one terminal pool. All three panels are valid finite/acyclic policy graphs. The stage chain and the terminal fan are trees — every node has in-degree at most 1 — while the recombining hybrid joins two stage-1 nodes into a single stage-2 node, giving that node in-degree 2. §6 returns to why this distinction matters.

2. Two Probability Axes

A policy graph carries two probability structures that stay conceptually distinct:

Between-node (edge) weights. Each node’s outgoing transition probabilities sum to 1 (the load-time check is in the Configure tab of Implementation in Novomodelo). This axis governs which child node a trajectory moves to.
Within-node openings. Independently of its outgoing edges, a node carries its own local set of openings $\Omega_n$ — the realizations $\omega \in \Omega_n$ its stage subproblem is evaluated under. This axis governs which realization is evaluated once the node itself has been reached; it is the same within-stage opening concept described for the chain in SDDP Algorithm §3 and Scenario Generation, scoped per node rather than per stage.

The backward pass composes the two axes into one joint law. The cut of a node $n$ is built over the pairs $(n', \omega)$ of a child $n'$ and an opening $\omega \in \Omega_{n'}$ of that child, each pair weighted by the product $P(n \to n')\, p_{n'}(\omega)$ of the edge’s transition probability and the opening’s probability within the child, uniform over $\Omega_{n'}$ . The risk measure of node $n$ ‘s stage acts once on that joint law, not on each child’s openings with the results then averaged across the children.

Node Bellman Equation and Cut

Let $V_n$ denote the cost-to-go that node $n$ ‘s future-cost pool approximates, a function of the state $x$ that node $n$ passes to its children; on the stage chain, $V_n = V_{t(n)+1}$ , the value function of SDDP Algorithm §2 at the stage after the node’s own. Under the expectation,

V_n(x) = \sum_{n'} P(n \to n') \sum_{\omega \in \Omega_{n'}} p_{n'}(\omega) \min_{(x', u) \in \mathcal{X}_{n'}(x, \omega)} \Big\{ c_{n'}(x', u) + d_{t(n') \to t(n')+1}\, V_{n'}(x') \Big\}

where the outer sum runs over the children $n'$ of $n$ , $\mathcal{X}_{n'}(x, \omega)$ is the feasible set of child $n'$ ‘s state $x'$ and control $u$ given the incoming state $x$ and the opening $\omega$ , $c_{n'}$ is the child’s immediate cost and $d_{t(n') \to t(n')+1}$ the discount factor of its stage (§3). At a leaf, $V_n$ is the terminal function every leaf shares (§5): zero, or the fixed imported terminal function of SDDP Algorithm §7.

The cut of node $n$ at a trial point $\hat{x}$ bounds node $n$ ‘s future-cost variable $\theta_n$ :

\theta_n \geq \bar{\beta}_0 + \bar{\beta}^{\top} x

with

\bar{\beta}_0 = \sum_{(n', \omega)} P(n \to n')\, p_{n'}(\omega)\, \beta_0(n', \omega), \qquad \bar{\beta} = \sum_{(n', \omega)} P(n \to n')\, p_{n'}(\omega)\, \beta(n', \omega)

where $\beta(n', \omega)$ is the coefficient vector read from child $n'$ ‘s subproblem at $\hat{x}$ under opening $\omega$ , and $\beta_0(n', \omega) = Q_{n'}(\hat{x}, \omega) - \beta(n', \omega)^{\top} \hat{x}$ its intercept, $Q_{n'}(\hat{x}, \omega)$ being that subproblem’s optimal value (Cut Management §2 and §3). Under a risk measure, the double sum of $V_n$ is replaced by the risk measure of node $n$ ‘s stage applied once to the joint law of the pairs $(n', \omega)$ , and the products $P(n \to n')\, p_{n'}(\omega)$ in the cut by the risk-adjusted probabilities of Risk Measures computed on that law.

3. Discount Is Stage-Separate, Not Edge-Separate

The discount factor $d_{t \to t+1}$ defined in Discount Rate Formulation is a property of the stage transition $t \to t+1$ , not of a policy-graph edge. The stage- $t$ template carries it once, as the objective coefficient of $\theta$ , and carries the delivery discount of Discount Rate Formulation on each anticipated decision column (State Augmentation); both are fixed per stage.

An explicit node graph keeps this stage-level convention: a discount override applies to a stage, and a transition between two declared nodes may not carry its own discount override. The reason is structural, not incidental — because the discount factors are fixed in the stage template once per stage, an edge-level (and therefore potentially per-node) override would force a separate template per node, which the single shared stage template does not support. A future-proof declaration point exists per transition precisely because the implicit stage chain has one transition per stage, so a per-edge spelling there is equivalent to a per-stage one; once a stage can hold several nodes, that equivalence breaks and only the per-stage declaration remains meaningful.

4. Mapping onto the SDDP.jl Family

The node/transition/pool structure above is the same abstraction Dowson (2020) defines as a policy graph and the SDDP.jl package implements (Dowson & Kapelevich, 2021): nodes each carry a local subproblem and their own cut pool, connected by probability-weighted arcs, with the backward pass aggregating successor pools into a parent’s cut exactly as §1 describes. Novomodelo’s graph is the finite, acyclic, leaf-terminated member of that family — every trajectory starts at a root and ends at a leaf after a bounded number of stages, with no cycle back to an earlier stage. §5 states the further restrictions Novomodelo imposes within that member.

5. Known Limitations

Novomodelo’s policy graph carries three structural limitations beyond the finite/acyclic/leaf-terminated shape itself:

A single initial node. A case supplies one initial-conditions record for the whole graph, so the incoming state that anchors the graph is shared by construction — the graph is anchored at one root even where the schema would structurally permit more than one node at stage 0.
A single terminal value shared across leaves. Every leaf, regardless of which node or path reaches it, resolves to the same shared terminal pool, to which the backward pass adds no cut. This generalises the terminal condition of SDDP Algorithm §2: there is one terminal future-cost value for the whole graph, not one per leaf, either zero, $V_{T+1}(x) = 0$ , or the fixed imported terminal function of SDDP Algorithm §7.
Finite-horizon only. Only the acyclic, leaf-terminated graph shape is accepted; the cyclic (infinite periodic horizon) variant is reserved and rejected when the case is loaded. See Horizon Modes for the cyclic target design this reservation anticipates.

6. The Enumerated-Tree Structural Requirement

An enumerated (exact) backward/forward pass — as opposed to a sampled one — visits every node deterministically and reconstructs each node’s incoming state along a single path from its parent. That reconstruction is only well-defined under two additional restrictions on the graph, beyond the finite/acyclic/leaf-terminated shape:

A singleton within-node opening set at every node ( $|\Omega_n| = 1$ ). An exact pass evaluates exactly one opening per node: a node with more than one opening is rejected at setup, so branching is expressed structurally instead, as distinct sibling nodes each carrying its own single opening.
In-degree 1 everywhere — a pure tree, no recombination. A node reached from more than one predecessor (the recombining hybrid panel in §1) has more than one candidate incoming state. Reconstructing its state along only one parent’s path would silently discard the trajectories that arrive through the other parent.

Both restrictions exist for the same reason: an exact pass has no per-trajectory memory of how it reached a node, so a node’s incoming state must be exactly and unambiguously the one path leading to it. A sampled pass carries its own incoming state along with each trajectory it evaluates, so it is not subject to either restriction — it evaluates a node’s opening set by drawing from it rather than enumerating it, and it resolves a recombination join natively rather than reconstructing a single path.

Because the enumerated count grows multiplicatively along every root→leaf path, the total number of leaves an enumerated pass would visit is checked against overflow before the pass runs; a graph whose exact enumeration would overflow is rejected at setup rather than silently truncated or wrapped.

Of the three panels in §1: the stage chain and the terminal fan are pure trees and admit an exact pass (subject to the singleton-opening restriction at each node); the recombining hybrid is rejected for an exact pass at its in-degree-2 join and requires a sampled pass instead.

Implementation in Novomodelo

The methodology above defines nodes, transitions and their probabilities; the tab below covers how Novomodelo’s software surface spells them and checks the probabilities at load.

Configure

Novomodelo reads the policy graph from the policy_graph object of stages.json. This tab gives the spellings of the nodes, transitions and probabilities that Policy Graphs defines above, and the rule that checks the probabilities at load; the full field table is in stages.json.

Node and transition fields

A policy_graph.nodes[] entry has the keys id, stage_id, scenario_id and label. The keys id and stage_id are required, label is an optional human-readable name, and scenario_id is present only at a node whose stage carries an externally supplied scenario.

A policy_graph.transitions[] entry has the keys source_id, target_id and probability. The two endpoints are node ids when nodes[] is declared and stage ids otherwise. In the stage-chain dialect (no nodes[]) a transition may also carry annual_discount_rate_override; under nodes[] it is rejected. The override’s rules are in the Configure tab of Discount Rate Formulation.

The key scenario_id applies only under an enumerated forward pass. There it is required at every node whose stage carries an externally supplied scenario, and it must index a valid column of every such external class; it is rejected at a node whose stage carries none. A sampled forward pass rejects any scenario_id at setup, naming the first node that declares one and its stage.

The following policy_graph object declares a terminal fan under an enumerated forward pass: a trunk node at stage 0 that pins its stage’s one external scenario, and three children at stage 1 that each pin one of three externally supplied scenarios.

{
  "policy_graph": {
    "type": "finite_horizon",
    "annual_discount_rate": 0.06,
    "nodes": [
      { "id": 0, "stage_id": 0, "scenario_id": 0, "label": "trunk" },
      { "id": 1, "stage_id": 1, "scenario_id": 0, "label": "dry" },
      { "id": 2, "stage_id": 1, "scenario_id": 1, "label": "normal" },
      { "id": 3, "stage_id": 1, "scenario_id": 2, "label": "wet" }
    ],
    "transitions": [
      { "source_id": 0, "target_id": 1, "probability": 0.25 },
      { "source_id": 0, "target_id": 2, "probability": 0.5 },
      { "source_id": 0, "target_id": 3, "probability": 0.25 }
    ]
  }
}

Transition probabilities

The outgoing probability values of each source must sum to 1 within 1e-6; a source whose sum is further off fails the load, and the error names the source and the sum. When the check passes, the loader rescales the outgoing probabilities of each source so that they sum to 1. A zero or non-finite sum is rejected.

Cross-References

SDDP Algorithm — the forward/backward pass structure and terminal condition this chapter generalises to a graph
Cut Management — the append-only cut pool this chapter generalises from per-stage to per-node
Discount Rate Formulation — the per-stage discount factor referenced in §3
Scenario Generation — the within-node opening set referenced in §2
Horizon Modes — the cyclic graph variant reserved in §5
Stage Files — the stages.json field-level reference for the node/transition shape introduced conceptually in §1
Configuration — how a study selects an enumerated versus a sampled pass (§6)
Glossary — term definitions for node, transition, and policy graph

References

See the full Bibliography for every source cited across the methodology.