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 simulation-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 Simulation-Based Stopping (Recommended)

Partial Implementation

The current implementation computes distance against a zero baseline rather than consecutive snapshots; the bound_tol and bound_window parameters are parsed but not yet applied to the pre-check.

Bound evolution across iterations $k$: the lower bound $\underline{z}^k$ rises monotonically (the append-only cut pool), while the Monte-Carlo upper bound $\bar{z}^k$ descends with a 95% confidence band that tightens as sampling accumulates. The simulation-based rule fires once the gap $(\bar{z}^k - \underline{z}^k)/\max(1,|\bar{z}^k|)$ closes below tolerance and the policy stabilises.

{
  "type": "simulation",
  "replications": 100,
  "period": 20,
  "bound_window": 5,
  "distance_tol": 0.01,
  "bound_tol": 0.0001
}

Parameter	Description
replications	Number of Monte Carlo forward simulations to run
period	Check every this many iterations
bound_window	Number of past iterations over which to measure bound stability
distance_tol	Threshold for normalized distance between consecutive simulation results
bound_tol	Relative tolerance for bound stability check

Algorithm:

1. Check bound stability first:

   $$\text{Bound stable} \iff \left| \underline{z}^k - \underline{z}^{k - w} \right| < \text{bound\_tol} \times \max(1, |\underline{z}^k|)$$

   where $w$ is the bound_window parameter.

2. If bound is stable, run replications Monte Carlo simulations using the current policy. Compute per-stage total costs $c_t^{new}$ and compare to the previous simulation’s costs $c_t^{old}$:

   $$d = \sqrt{\sum_{t} \left( \frac{c_t^{new} - c_t^{old}}{\max(1, |c_t^{old}|)} \right)^2}$$

   The comparison metric is the mean per-stage cost across replications. Future extensions may compare other quantities (e.g., state variable trajectories or decision variable distributions).

3. Stopping condition:

   $$\text{STOP} \iff \text{Bound stable} \land d < \text{distance\_tol}$$

Interpretation: Both the outer approximation (bound) and the policy (simulated costs) have stabilized.

Why recommended: Combines a theoretical convergence indicator (bound) with practical policy quality (simulation), avoiding premature termination from statistical noise.

Risk-averse note

For risk-averse problems, the bound stability check monitors convergence of the risk-adjusted outer approximation. The simulation comparison remains valid since it measures policy stability directly, independent of bound interpretation. See Risk Measures.

Partial Implementation

The current implementation is a stub that compares simulation costs against a zero baseline rather than consecutive simulation snapshots. Specifically, when simulation_costs are available, the distance is computed as $d = \sqrt{\sum_t (c_t / \max(1, |c_t|))^2}$ against zero, which is conservative: it never triggers on the first evaluation and only triggers when per-stage costs are themselves near zero. The planned full version will store the previous simulation’s cost vector and compute the distance between consecutive snapshots as described above ($c_t^{new}$ vs $c_t^{old}$). The convergence monitor is responsible for managing the two-snapshot comparison externally.

Additionally, the bound stability pre-check (Phase 1) is not yet implemented: the bound_tol and bound_window parameters are parsed from configuration but currently discarded — the rule skips directly to the simulation distance comparison. Until Phase 1 is implemented, the rule may evaluate simulations even when the bound is still actively improving, which is conservative (wastes simulation time) but not incorrect.

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": "simulation",
      "replications": 100,
      "period": 20,
      "bound_window": 5,
      "distance_tol": 0.01,
      "bound_tol": 0.0001
    }
  ],
  "stopping_mode": "any"
}

This runs until simulation-based convergence 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 simulated upper bound (if available)
gap	Optimality gap: $(\bar{z} - \underline{z}) / \max(1, \lvert\bar{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 — Monte Carlo simulation for upper bound estimation, used by simulation-based stopping
• Risk Measures — Risk-averse formulations that affect bound interpretation
• Reproducibility and Provenance — Provenance commitment that the graceful-shutdown guarantee is a special case of