esc

↑↓ navigate↵ open

Multistage policies · State targets · Dual gradients

DecisionRules.jl

A policy for a constrained multistage system must return actions that satisfy the operating model at every stage, and a network that outputs actions directly gives no such assurance. DecisionRules.jl trains policies whose outputs are state targets, realized by an optimization over the operating model written in JuMP, with gradients read from the multipliers of the target constraints instead of differentiated through solver iterations.

Andrew W. Rosemberg · Author

01 · DesignThe policy prescribes a state, the model realizes it

Targets, realization and the dual gradient

A policy \(\pi(\cdot;\theta)\) maps the realized uncertainty \(w_t\) and the previous state to a target \(\hat{\mathbf x}_t\). The stage problem, a JuMP model of the operating system, enforces the target through a constraint \(\mathbf x_t=\hat{\mathbf x}_t\), or \(\mathbf x_t+\boldsymbol\delta_t=\hat{\mathbf x}_t\) with a penalty on the slack \(\boldsymbol\delta_t\), and the multiplier \(\boldsymbol\lambda_t\) of that constraint is the derivative of the realized cost with respect to the target. Along a sampled trajectory \(\mathbf w\),

\[\frac{d\mathcal Q(\mathbf w;\theta)}{d\theta}=\sum_{t=1}^T\boldsymbol\lambda_t^{\top}\frac{d\hat{\mathbf x}_t}{d\theta}.\]

Automatic differentiation supplies the derivative of the policy; the stage solves contribute their multipliers, and in a stage-by-stage rollout DiffOpt.jl adds the sensitivity of each realized state to its inputs.

Every executed action is a solution of the operating model, so feasibility at deployment belongs to the model. No solver iteration is differentiated, any solver that returns multipliers can be used, and the gradient of a sampled trajectory costs only the stage solves already needed to evaluate it.

Training a state-consistent decision rule: a recurrent policy with shared weights emits targets stage by stage; independent stage problems, solved in parallel, return the multipliers that form the gradient.
Training with exact targets over a horizon. A recurrent policy \(\pi\) emits each target \(\hat{\mathbf x}_t\) from the realized uncertainty \(w_t\) and its memory \(\boldsymbol\zeta_t\). Stage \(t\) fixes its incoming state to \(\hat{\mathbf x}_{t-1}\) and its outgoing state to \(\hat{\mathbf x}_t\), so the stage problems can be solved independently; their multipliers \(\boldsymbol\mu_{t+1}\) and \(\bar{\boldsymbol\lambda}_t\) add up to \(\boldsymbol\lambda_t\), and the sum at the bottom is the policy gradient. The construction of Policies for Multistage Decisions, Section 04.

The interface is a parametric JuMP model

A problem is given as one JuMP model per stage in which the incoming state, the stage uncertainty and the target are parameters, together with pairs that link each target to the variable whose value becomes the realized state. The function compute_parameter_dual reads the derivative of the optimal value with respect to any parameter from the multipliers of every affine, quadratic or vector-affine constraint, and from the objective term, in which the parameter appears. Mixed-integer stage problems are handled by strategies that read multipliers from the continuous problem with the discrete decisions fixed at their optimal values, or from a continuous relaxation, with an optional score-function correction.

Any operating model that can be written in JuMP can be trained against at its full fidelity, and replacing it changes no training code.

Three ways to couple the horizon

The same policy trains against the deterministic equivalent of a sampled trajectory, one coupled problem over the horizon; against a stage-wise rollout, one problem per stage solved in sequence from the realized state; or against windows of stages chained by their realized end states. A strict mode removes the slack when the policy is built to emit only reachable targets, and the multiplier is then the pure shadow price of the target. The companion package DecisionRulesExa.jl solves the strict deterministic equivalent on GPUs with ExaModels.jl and MadNLP.jl.

Horizon coupling trades gradient information against the size of each solve. Long horizons and large networks need different points on that trade-off, and here they are reached with one policy object.

Evaluated as it will be deployed

The evaluator RolloutEvaluation scores a policy stage by stage on a fixed set of held-out scenarios. It reports the operating cost without the target penalty and the share of the objective spent on target violations, with either the realized or the targeted state fed back to the policy. A coupled solve can absorb unreachable targets through the slack, which deployment cannot do; the stage-wise rollout measures what deployment realizes.

02 · ExampleAn inventory policy trained through its stage problems

The example below is a simplified version of the package's lot-sizing example. Each stage is a small linear program with the incoming inventory, the demand and the policy's target as parameters; the target constraint carries a penalized slack, so every target is realizable during training.

using DecisionRules, JuMP, HiGHS, Flux
import DiffOpt

# One stage of an inventory system; the policy's target enters as a parameter.
function stage_problem(s0, d̄; Q = 100.0, c = 1.0, h = 0.5, b = 4.0)
    sp = Model(() -> DiffOpt.diff_optimizer(HiGHS.Optimizer))
    @variable(sp, 0 <= q <= Q)                      # order
    @variable(sp, s_out)                            # realized inventory
    @variable(sp, hold >= 0)
    @variable(sp, back >= 0)
    @variable(sp, s_in in MOI.Parameter(s0))        # incoming state
    @variable(sp, demand in MOI.Parameter(d̄))       # stage uncertainty
    @variable(sp, s_target in MOI.Parameter(s0))    # policy output
    @constraint(sp, s_out == s_in + q - demand)
    @constraint(sp, hold - back == s_out)
    @objective(sp, Min, c * q + h * hold + b * back)
    _, δ = create_deficit!(sp, 1; penalty_l1 = 100.0)
    @constraint(sp, δ[1] == s_in + q - s_target)    # target constraint: its multiplier trains the policy
    return sp, [s_in], [(s_target, s_out)], demand
end

T, s0 = 12, 10.0
stages = [stage_problem(s0, 50.0) for t in 1:T]
subproblems = [s[1] for s in stages]
state_params_in = [s[2] for s in stages]
state_params_out = [s[3] for s in stages]
uncertainty_samples = [[(s[4], 30.0 .+ 40.0 .* rand(100))] for s in stages]

policy = Chain(Dense(policy_input_dim(1, 1), 64, relu), Dense(64, 1))
train_multistage(policy, [s0], subproblems, state_params_in, state_params_out,
    uncertainty_samples; num_batches = 100, optimizer = Flux.Adam(1e-3))

Replacing the penalized target by the equality s_in + q == s_target, together with a policy whose outputs are confined to \([s_{\text{in}},\,s_{\text{in}}+Q]\), gives the strict mode. Replacing the stage model by an optimal power flow with storage changes nothing below the function.

03 · ResearchWhere the package carries the theory

  • Policies for Multistage Decisions. The state-target policies, the dual gradient of Section 03 and the exact realization of Section 04 are the package's formulations; the hydrothermal comparison against SDDP and model-free agents is its hydro case, with the SDDP baselines built by HydroPowerModels.jl.

04 · CitationHow to cite

The repository asks users to cite the paper that introduced the method:

@misc{rosemberg2024efficiently,
  title         = {Efficiently Training Deep-Learning Parametric Policies using Lagrangian Duality},
  author        = {Rosemberg, Andrew W. and Street, Alexandre and Vallad{\~a}o, Davi M. and Van Hentenryck, Pascal},
  year          = {2024},
  eprint        = {2405.14973},
  archivePrefix = {arXiv},
  primaryClass  = {cs.LG}
}