Stopping Rules

Purpose

This spec defines the available stopping rules for the Cobre SDDP solver, their configuration, and how they combine. It covers iteration limits, time limits, bound stalling, and the recommended gap-based stopping criterion.

1 Available Stopping Rules

SDDP can terminate based on multiple criteria. Each rule is evaluated independently, and the stopping_mode determines how they combine:

• "any": Stop when any rule triggers (OR logic)

• "all": Stop when all rules trigger (AND logic)

2 Iteration Limit (Mandatory)

Configuration:

{ "type": "iteration_limit", "limit": 50 }

Evaluation:

$$\text{STOP} \iff k \geq k_{max}$$

where $k$ is the current iteration and $k_{max}$ is the limit.

Purpose: Safety bound to prevent infinite loops. Must always be included.

3 Time Limit

Configuration:

{ "type": "time_limit", "seconds": 3600 }

Evaluation:

$$\text{STOP} \iff t_{elapsed} \geq t_{max}$$

Wall-clock time is checked at the end of each iteration.

4 Bound Stalling

Configuration:

{
  "type": "bound_stalling",
  "iterations": 10,
  "tolerance": 0.0001
}

Evaluation:

Track the deterministic lower bound $\underline{z}^k$ over iterations. Compute relative improvement over a window of $\tau$ iterations (the iterations parameter):

$$\Delta_k = \frac{\underline{z}^k - \underline{z}^{k-\tau}}{\max(1, |\underline{z}^k|)}$$

Stopping condition:

$$\text{STOP} \iff |\Delta_k| < \text{tolerance}$$

Interpretation: The bound has plateaued — the relative improvement over the last $\tau$ iterations is below the specified tolerance, indicating diminishing returns from further iterations.

Risk-averse note

Under risk-averse formulations (e.g., CVaR), the lower bound $\underline{z}^k$ may not be a valid bound in the classical sense. Bound stalling still detects convergence of the outer approximation, but the gap interpretation changes. See Risk Measures for details.

5 Gap-Based Stopping (Recommended)

Bound evolution across iterations $k$: the lower bound $\underline{z}^k$ rises monotonically (the append-only cut pool), while the upper bound $\bar{z}^k$ descends toward it. A confidence band around the descending series applies only when the upper bound is a statistical estimate — it tightens as sampling accumulates; the exact upper bound the gap rule compares against carries no such band.

The gap rule terminates training once the exact upper bound has closed on the lower bound.

Configuration:

{ "type": "gap", "tolerance": 1.0, "relative_tolerance": 0.1 }

Evaluation:

The gap is the clamped distance between the exact upper bound $\bar{z}$ and the lower bound $\underline{z}$:

$$\text{gap} = \max(0,\; \bar{z} - \underline{z})$$

In exact arithmetic the exact upper bound satisfies $\bar{z} \geq \underline{z}$; the clamp only absorbs floating-point noise once the gap has closed to (numerically) zero.

Stopping condition — two arms combined by disjunction (either is sufficient):

$$\text{STOP} \iff \text{gap} \leq \text{tolerance} \quad\text{or}\quad 100 \cdot \text{gap} / \max(1, |\underline{z}|) \leq \text{relative tolerance}$$

The absolute arm compares the gap directly against tolerance, in the objective’s own units. The relative arm normalizes the gap by the lower bound, $\max(1, |\underline{z}|)$ — floored so the ratio stays bounded when the lower bound is near zero — never by the upper bound; this is the same denominator the per-iteration reported gap uses, so the two never disagree on what “relative gap” means. Either bound may be configured alone; when both are configured, training stops as soon as either arm is satisfied.

Admissibility: the comparison above is only valid when the upper bound it uses is the exact bound, not a statistical estimate. Both of the following must hold:

• The forward pass enumerates the scenario tree exhaustively rather than sampling it, so the upper bound is exact — carrying no sampling error — rather than a sampled approximation.
• The risk measure is uniform across all stages: either expectation at every stage, or one CVaR measure (the same risk-aversion weight and tail level) at every stage. Under expectation the exact bound is the probability-weighted cost $\sum_{\ell} P(\ell)\, C(\ell)$ over every scenario $\ell$; under a uniform CVaR it is the nested, time-consistent risk bound over the same enumerated tree (Upper Bound Evaluation §2). A stage-varying measure — a risk-aversion weight or tail level that differs across stages — is not admissible, because no single measure then aggregates the tree.

Under a sampled forward pass, or a stage-varying measure, the exact-bound comparison the rule depends on is unavailable, and the gap rule is rejected at setup with a named validation error rather than silently evaluating against an unsound comparison.

Why recommended: unlike bound stalling (a proxy for convergence) or the iteration and time limits (safety bounds unrelated to convergence), a closed gap is a direct optimality certificate under the exact-bound regime the rule requires — an enumerated forward pass with a risk measure held uniform across stages.

Known discrepancy: convergence flag

A closed exact gap is a genuine optimality certificate — the deterministic upper bound has met the lower bound, so the policy already realizes that bound. The machine-readable convergence indicator, however, is set only when training stops via the bound-stalling rule; a run that terminates via the gap rule reports that indicator unset even though the exact gap has closed. This is a known discrepancy between the indicator and the underlying optimality guarantee, tracked as an upstream defect in the training-output layer rather than a limitation of the gap rule itself.

6 Graceful Shutdown

An external signal interrupts the training loop at the next iteration boundary, terminating cleanly with the latest completed iteration’s policy persisted.

Guarantee: The policy at the moment of termination is usable. The last completed iteration’s cuts and bounds are recorded; partial-iteration work begun after the signal arrives is discarded. The graceful-shutdown guarantee is a special case of the broader provenance commitment described in Reproducibility and Provenance: the output artefacts are always in a consistent state, whether the run reached a configured stopping rule or was interrupted.

Unconditional: Graceful shutdown is not a configurable rule; it is an unconditional safety property of the training loop. It is not listed in stopping_rules in the case configuration and is not subject to stopping_mode combination logic.

Trade-off: Graceful shutdown costs at most one partial-iteration’s runtime — the work performed after the signal arrives is discarded. The alternative (immediate termination) would leave the policy state inconsistent.

7 Combining Rules

Mode: "any" (default):

$$\text{STOP} \iff \text{Rule}_1 \lor \text{Rule}_2 \lor \ldots$$

First rule to trigger causes termination.

Mode: "all":

$$\text{STOP} \iff \text{Rule}_1 \land \text{Rule}_2 \land \ldots$$

All rules must trigger simultaneously.

Example (conservative setup):

{
  "stopping_rules": [
    { "type": "iteration_limit", "limit": 500 },
    { "type": "gap", "tolerance": 1.0, "relative_tolerance": 0.1 }
  ],
  "stopping_mode": "any"
}

This runs until the gap closes OR 500 iterations, whichever comes first.

Graceful shutdown is independent of the stopping_mode combination logic — it terminates the training loop regardless of whether any or all of the configured rules have triggered.

8 Output on Termination

When any stopping rule triggers, the output includes:

Field	Description
stopping_rule	Which rule triggered
final_iteration	Iteration count at termination
lower_bound	Final deterministic lower bound
upper_bound	Final upper bound (statistical or exact)
gap	Optimality gap: $(\bar{z} - \underline{z}) / \max(1, \lvert\underline{z}\rvert)$

The stopping_rule field carries the rule that triggered, including "graceful_shutdown" when an external signal terminated the run.

Cross-References

• Notation Conventions — Symbol definitions for bounds and statistical quantities
• SDDP Algorithm — Main iteration loop that evaluates stopping rules
• Cut Management — Cut generation and selection that affect convergence speed
• Upper Bound Evaluation — The exact (deterministic) and statistical upper-bound estimators; the exact bound is what the gap rule compares against
• Risk Measures — Risk-averse formulations that affect bound interpretation
• Reproducibility and Provenance — Provenance commitment that the graceful-shutdown guarantee is a special case of