acceptodds
Under review as a conference paper at ICLR 2027

Differentiating Through Moving Recourse: Feasible Policy Optimization and Finite-Sample Certification for Multistage Stochastic Programs

Abstract

Multistage stochastic programs model decisions under uncertainty where earlier decisions change later feasible sets. We propose a feasible pathwise gradient method (FeasPG) that can update the policy as new sample paths arrive. The policy proposes a decision and projects it onto the current feasible set, so every decision is feasible. We derive the full trajectory gradient, accounting for how earlier decisions change later constraint bounds. Under regularity conditions, it is unbiased at almost every parameter value. We also bound the error from treating the constraint bounds as fixed during differentiation. We analyze a proposal-distance penalty that can provide a training signal where projection makes cost locally flat. We give a decreasing-weight schedule that preserves the stationarity rate for the expected cost over training updates under standard stochastic-gradient assumptions. To assess the learned policy, we use held-out trajectories to construct a finite-sample upper confidence bound on its optimality gap. The certificates are also anytime-valid across checkpoints, so the bounds can guide when training stops. In reservoir-management experiments, FeasPG obtains lower mean costs than stochastic dual dynamic programming and reinforcement-learning baselines on model-generated paths. A separate reservoir study demonstrates informative certificates with no coverage failures in 200 repetitions per setting.

Primary area:
reinforcement learning
Keywords:
Sequential Decision Making, Multistage Stochastic Program, Policy Optimization

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_nW5NOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper proposes Feasible Pathwise Gradient (FeasPG), an optimization method for multistage stochastic programs (MSPs) that learns policies satisfying constraints at every stage while accounting for how earlier decisions change the feasible sets of later decisions. It also develops a finite-sample certificate for bounding the selected policy’s optimality gap. The paper addresses two major questions, how can one differatinate through projected decisions when constraints themselves depend on a state altered by earlier decisions and after training how can we quantify with statistical confidence hoe far the learned feasible policy is from the optimal one.

Critical strengths
  1. The most important finding is the gradient error which deserves attention
  2. The feasibility presevtation without huge training is good.
Critical weaknesses
  1. The practical novelty relative to existing differentiable optimization methods needs to be sharper The paper combines differentiable projection, pathwise gradients through sequential dynamics, proposal-distance regularization, and information-relaxation certification. Each component has relevant prior work, including OptNet, differentiable optimization layers, PROF, and information-relaxation methods. The authors discuss related work and a concurrent paper on differentiating through projections for inventory policies. However, the manuscript should make the precise boundary of novelty unmistakable.

  2. How frequently do the experiments encounter nondifferentiable projection points, and how sensitive are the empirical results to these events? Can the authors validate the practical relevance of the assumptions beyond gradient checks on selected examples?

  3. What are the computational costs of constructing the inner lower bounds and calibration bands as the horizon, decision dimension, and history dimension increase? How often does the method return an uninformative certificate?

  4. How robust are the learned policies to errors in the fitted exogenous data model? Can the authors quantify the distribution shift between generated and historical trajectories and explain why the method loses its advantage in this case?

Questions for authors
  1. Is the main contribution the moving-recourse sensitivity formula, its theoretical analysis, the certificate, or their combination? The paper needs to demonstrate clearly what could not already be achieved by applying existing differentiable optimization and stochastic-programming tools together.

Also check weaknesses

5 comments
AuthorsOpenReview ↗

Response to Reviewer nW5N (1/2): Contribution, Nondifferentiable Points, and Gradient Checks

Thank you for the questions. We first state precisely what is new, then address the practical questions.

Main contribution and novelty boundary.
Our main contribution is the analysis of the gradient and of the penalty, and the certificate, not the gradient formula alone. Away from kinks, a differentiable QP layer such as OptNet inside a differentiable simulator computes the same gradient as FeasPG. Existing tools do not establish when this gradient is unbiased despite the projection's kinks, how much bias arises when the dependence of later constraints on earlier decisions is ignored, or what a proposal-distance penalty does over multiple stages. The certificate cannot be assembled from existing tools: information relaxation evaluates its penalty with conditional expectations from a known model, and when these must be estimated from a fixed set of sample paths, the bound is no longer guaranteed without our correction.
The table below summarizes what is new and what we inherit from prior work.

ComponentPrior workNot addressed in prior workNew in this paper
Projection layerGuigues & Henrion (2017); OptNet, cvxpylayers, OptLayer; PROF (Chen et al., 2021)NoneNone; used as is (Eq. 4)
Pathwise gradientPathwise (IPA) gradients (Glasserman, 1991); Differentiable simulation (Suh et al., 2022; Xu et al., 2022)No state-dependent constraints, so no moving-recourse termDerive the moving-recourse term in the gradient (Eq. 6); Prove that the full gradient is unbiased (Thm 1); Analyze the bias from omitting the term (Cor. B.2)
Proposal-distance penaltyPROF (Chen et al., 2021)Fixed weight only; Single-step analysis; True dynamics unknownProve that the penalty preserves the optimal value over multiple stages (Thm B.5); Prove convergence for the original cost with a decreasing weight (Thm B.2)
Optimality certificateInformation relaxation (Brown et al., 2010)Not valid when the penalty is estimated from dataDerive a finite-sample correction for penalties estimated from sample paths (Thm 2); Prove a confidence bound on the optimality gap (Thm 3); Prove a matching lower bound on the rate (Thm C.2)

How often do nondifferentiable points occur? Across 150 selected checkpoints and all test paths, our diagnostics detected kinks in at most 0.0002% of stage projections. Under a 10−510^{-5} parameter perturbation, at most one in approximately 1.2 million stage projections changed its binding constraints.

Flat gradients are a separate issue. On the new inventory benchmark, we initialized the policy to propose orders exceeding warehouse capacity. Projection cuts these orders back to the limit, so a small reduction in the proposed order leaves the actual order unchanged. Without the proposal-distance penalty, training stayed in this flat region in every tested seed. With the penalty, training left the region and operating cost fell by 4.4–4.7%.

How sensitive are the results to the derivative convention? We retrained the policies with three alternatives: the derivative from the other side of a kink, zero within 10−910^{-9} of a kink, and smoothing, which computes gradients at small random perturbations of the parameters (Appendix B.10). We used five seeds for each treatment and selected checkpoints by validation cost.

On the same 4,096 test paths, costs changed by at most 0.34% on the synthetic system and 0.88% on ONS, less than the seed-to-seed standard deviation in each case. On ONS, the first two alternatives gave identical policies. Even widening the zero-derivative region enough to change gradients in 9–15% of updates changed test cost by at most 0.9%.

Do the checks extend beyond selected examples? Yes. We checked gradients every 25 updates throughout training, in all five seeds, using fresh paths. Autodiff and finite differences agreed closely, with median relative errors between 6×10−106\times10^{-10} and 10−610^{-6}. Every large discrepancy occurred when the finite-difference step crossed a kink.

The initialization needed separate attention. The synthetic MLP’s zero-initialized output layer placed 8.3% of projections at detected kinks, which the almost-everywhere result does not automatically cover. After one update, the largest relative error was 7×10−57\times10^{-5}. Across horizons from 12 to 96, measured gradient norms grew approximately as T1.2T^{1.2}, much more slowly than the general exponential worst-case bound.

AuthorsOpenReview ↗

Response to Reviewer nW5N (2/2): Certificate Cost and Informativeness, Robustness

Cost of the certificate. We tested scalability using the multi-item inventory model in Appendix E, with shared storage and serially dependent demand. Each inner problem is one LP per evaluation path. It took 2.5 milliseconds at the base size of 12 periods and four items, and 28.5 milliseconds at 96 periods. Measured solve times grew approximately linearly across the horizon and item-count sweeps.

Calibration took less than a second. A full certificate over 4,096 evaluation paths took a median of 15 seconds on one core, and at most 171 seconds in the 32-item case. On the power-flow benchmark, each per-path QP took 0.14 core-seconds. Once the policy and calibration are fixed, each evaluation path can be processed independently, so the per-path optimization problems can be solved in parallel.

How often is the certificate uninformative? Judging this requires a reference value for V⋆V^{\star}, so we computed one from the true model, which the certificate does not use.

In the reservoir experiment, the model is small enough that bounds on V⋆V^{\star} can be computed exactly over all 2182^{18} paths. They place the actual optimality gap between 3.3% and 4.4% of policy cost. The certificate reported 5.4% on average, a close assessment obtained without V⋆V^{\star} or the true probabilities.

In the larger inventory tests, we bounded V⋆V^{\star} from below by information relaxation with the exact conditional means, and from above by a base-stock policy computed from the true model. We observed no coverage failures in any of the 17 configurations, each tested over 100 repetitions. Under serially dependent demand, however, the certificate was conservative. At the base size (12 periods, four items, one history feature, 2142^{14} calibration paths), the true gap was at most 1.3% of policy cost, while UU was 78%. The information-relaxation part was accurate: the uncorrected gap averaged 3.83, against 3.75 with the exact conditional means. Nearly all of UU was the finite-sample correction for estimating conditional demand distributions from data.

Relative to policy cost, this correction did not depend on problem size: with 2142^{14} calibration paths, U/JU/J stayed between 0.76 and 0.81 as the horizon varied from 6 to 96 and the number of items from one to 32. It decreased with more data: increasing the sample to 2182^{18} paths reduced U/JU/J from 0.78 to 0.36. The number of history features that the correction conditions on mattered most. With one feature, 2122^{12} paths did not bring UU below JJ; with two and three features, approximately 2162^{16} and 2192^{19} paths were needed. These rates agree with Corollary C.1. Our calibration does not assume a parametric model for the uncertainty, and its rate attains the exponent of a minimax lower bound for uniformly valid one-sided corrections over Hölder classes (Theorem C.2), so corrections of this kind cannot remove this dependence without further assumptions. Additional knowledge of the stochastic process may yield tighter certificates. For example, a linear autoregressive model with a specified noise family could support model-specific confidence bounds instead of nonparametric estimation. We leave such certificates to future work.

Robustness to errors in the uncertainty model. We trained under a perturbed inflow level, noise, autocorrelation, or load, then tested on the nominal model. Costs rose by 1.5–29% on ONS and 0.3–3.8% on CAMELS-BR. FeasPG still beat Seasonal in every tested case and seed, retaining 88–111% of its original cost advantage. Its costs were more sensitive to the perturbations than Seasonal’s, which uses little information from the uncertainty model.

Why the advantage was lost on the ONS history. Realized load during 2022–2025 was 56% higher than the seasonal average assumed in training. For both FeasPG and Seasonal, this historical record was costlier than all 4,096 model-generated test paths.

To investigate this mismatch, we refitted the uncertainty model on pre-2022 data with a load trend. After retraining, FeasPG beat Seasonal by approximately 5%, with an improvement in all five training runs. The historical cost also fell near the median of the revised model’s generated-path costs. Updating only the load level was not enough: FeasPG remained 1.2% worse than Seasonal. This follow-up experiment points to the demand trend as an important cause of the original performance loss. On CAMELS-BR, the DeepSets policy beat Seasonal in all five historical windows.

We thank the reviewer for the questions and hope these results clarify the contributions and address the practical concerns.

I thank the authors for the detailed response. However, there are some additional doubts.

i) The additional kink diagnostics are encouraging. However, how are nondifferentiable projection points identified, and how is their proximity to active-set transitions measured?

One major point is the presentation and portrayal of the contributions which is very hard to follow. Despite reading through the manuscript it is hard to find the contributions clearly as given in the rebuttal. I suggest the authors to keep this comparison table which can summarize the differences clearly. Further, in my opinion this paper will benefit from a revisit in terms of portrayal of contrbutions and writing.

Thus, I maintain my current score.

Reviewer_oE3fOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes a projection-based policy gradient method for multi-stage stochastic programming (MSSP) to ensure policy decisions satisfy MSSP's linear constraints. The authors also provide a certificate that bounds the policy based on held-out trajectories, which itself might be useful beyond the scope of the algorithm and paper. The method is validated on a reservoir-management problem, a classical MSSP benchmark.

Critical strengths
  • Empirical Results: Overall, the empirical results against the respective baselines and benchmarks show favorable performance for the method. I believe this is the paper's strongest point.
Critical weaknesses
  • Clarity, Novelty, & Presentation: In my view, the biggest concern with this paper is the clarity and presentation. After several passes on the main paper, I am still not entirely sure what algorithmic elements are novel relative to existing methods. For example, as the authors state, prior work has used projections in policy-based methods, and the specific contributions are unclear because the method section does not delineate them. It's unclear to me whether differentiating through moving recourse differs from standard projection-based policy methods in a standard constrained RL setting. Beyond this, Section 2 presents both the MSSP formulation and projection (part of the methodology), so a clearer distinction between the problem formulation and the method would be preferred. Section 4 is reasonable, but the connection to the algorithm implemented in Section 5 is unclear; for example, it is unclear whether the early-stopping certification is used at all. The paper also contains numerous spelling and grammatical errors. Overall, the paper has reasonable elements, but in its current state needs a much stronger delineation between its own novelty and prior work, with a stronger motivation for design choices throughout.

  • Benchmarks & Baselines. First, the benchmarks are limited. The authors primarily study one standard MSSP benchmark in three different settings. However, as far as I can tell, these are all structurally quite similar. Another benchmark with more structural variation, e.g., multi-stage optimal power flow, would provide a more convincing and comprehensive set of experiments. Second, comparing to SDDP is reasonable. However, in the finite-state setting, it has relatively large gaps with the proposed method, in a setting where I believe SDDP should converge with sufficient data, given the problem is convex. The authors should clarify this in the rebuttal. Beyond this, I am not entirely convinced by the choice of RL methods for comparison, as they select relatively standard methods and then apply projections to them. A more similar method, e.g., PROF, which the authors already cite, may be a better choice here. In addition, Projected SHAC is limited to 8 stages, which appears arbitrary and is not justified. I am definitely not an RL expert, so perhaps the authors could clarify this in the rebuttal as well. This point is consequential, as the method is currently evaluated only on a single problem class and the baseline choices aren't clearly justified.

Questions for authors
  • Can the authors clarify the SDDP setting and why it didn't converge in the convex case?
  • Can the authors clarify their choice of baselines and why more similar methods, e.g., PROF, were not used?
  • Can the authors provide a clearer delineation between what elements of the algorithm are novel and what are inherited from prior work (ideally referenced back to equations/sections of the paper itself)?
8 comments
AuthorsOpenReview ↗

Response to Reviewer oE3f (1/4): What Is New (Q3) and Comparison with Constrained RL

Thank you for the careful review. We first separate what is new from what we inherit, then explain how differentiating through moving recourse differs from projection-based constrained RL, and then answer your other questions.

Q3: What is new and what is inherited. We do not claim the projection layer, pathwise gradients, the proposal-distance penalty itself, or information relaxation. Away from kinks, a differentiable QP layer inside a differentiable simulator computes the same gradient as FeasPG; our contribution is the analysis of this gradient and of the penalty, and the certificate.

ComponentPrior workNot addressed in prior workNew in this paper
Projection layerGuigues & Henrion (2017); OptNet, cvxpylayers, OptLayer; PROF (Chen et al., 2021)NoneNone; used as is (Eq. 4)
Pathwise gradientPathwise (IPA) gradients (Glasserman, 1991); Differentiable simulation (Suh et al., 2022; Xu et al., 2022)No state-dependent constraints, so no moving-recourse termDerive the moving-recourse term in the gradient (Eq. 6); Prove that the full gradient is unbiased (Thm 1); Analyze the bias from omitting the term (Cor. B.2)
Proposal-distance penaltyPROF (Chen et al., 2021)Fixed weight only; Single-step analysis; True dynamics unknownProve that the penalty preserves the optimal value over multiple stages (Thm B.5); Prove convergence for the original cost with a decreasing weight (Thm B.2)
Optimality certificateInformation relaxation (Brown et al., 2010)Not valid when the penalty is estimated from dataDerive a finite-sample correction for penalties estimated from sample paths (Thm 2); Prove a confidence bound on the optimality gap (Thm 3); Prove a matching lower bound on the rate (Thm C.2)

How this differs from projection-based constrained RL. Safe and action-constrained RL also project actions onto feasible sets that change with the state (Gros et al. 2020; Lin et al. 2021; Markgraf et al. 2026). The main difference is that these methods are model-free. Their gradient comes from a learned critic or from likelihood ratios, and the way the feasible set changes with the state is part of an unknown environment. In a multistage stochastic program (MSP), the dynamics are known and the uncertainty does not depend on our decisions, so a recorded path can be replayed under any policy and differentiated exactly. The resulting gradient contains a term for how today’s decision changes tomorrow’s feasible set (the moving-recourse term DsPˉtStD_s\bar P_t S_t in Eq. 6). We show that omitting this term biases the gradient and that the bias accumulates over the horizon (Cor. B.2). On the new benchmarks, omitting it raises cost by 1.6–3.2% on power flow and 1.1–1.3% on inventory, in every seed and at every data budget. Away from kinks, where the set of binding constraints changes, a differentiable QP layer inside a differentiable simulator would compute the same gradient. What we contribute is the analysis of this gradient.

One further difference follows because the uncertainty is exogenous, so a recorded path stays valid under any policy. FeasPG needs no interaction with the environment: it trains on a fixed set of sample paths. Projected PPO and SAC, given the same paths, cost up to 120% more on the new benchmarks.

When the policy proposes an infeasible decision, nearby proposals can project to the same feasible decision, so the gradient can be exactly zero. This problem is known in action-constrained RL (Lin et al. 2021), and PROF’s penalty on the distance between a proposal and its projection is one remedy. We analyze this penalty over multiple stages. We show when it helps and when it fails, and we give a decreasing weight that still converges for the original cost (Thm B.2, Thm B.5, Remark B.1). In App. I, we construct a case where training without the penalty has exactly zero gradient in all 5 seeds; with the penalty, test cost drops by 8.6%.

We also tested this on the new inventory benchmark, where the policy adds a learned correction to an ordering rule. If the rule orders more than the shared warehouse can hold (a target 1.4–3 times the mean lead-time demand), the projection cuts the orders back to the limit, so the gradient gives no signal to order less. Without the penalty, training stays there in every seed; with it, test cost falls by 4.4–4.7%, close to the cost reached with a well-chosen target.

Thank you also for pointing out the spelling and grammatical errors; we will correct them throughout.

AuthorsOpenReview ↗

Response to Reviewer oE3f (2/4): SDDP Setting (Q1)

Q1: SDDP setting. The reviewer asks why SDDP, which should converge with sufficient data on a convex problem, shows a noticeable gap to FeasPG on ONS and CAMELS-BR in Table 1. With stagewise independent uncertainty, as the reviewer correctly points out, SDDP should converge on the sample average approximation (SAA) problem, and that SAA problem approaches the true one as the sample grows. Our inflows, however, are serially dependent. Linear autoregressive dependence can be handled by adding past inflows to the state (TS-SDDP), but our inflow model is log-linear, which breaks the convexity this requires (Löhndorf & Shapiro, 2019). We therefore used Markov-chain SDDP (MC-SDDP) proposed in the same paper (Löhndorf & Shapiro, 2019). The inflow states of each stage are clustered into K = 6 regimes, transition probabilities between regimes are estimated from the training paths, and each regime has its own cost-to-go function, which SDDP approximates iteratively. This is the "finite-state SDDP" of the paper (App. K: "empirical joint scenarios per stage and hydrology regime"), and we will call it MC-SDDP in the revision.

Unlike standard SDDP on an SAA problem, MC-SDDP has no convergence guarantee with respect to the true process (Löhndorf and Shapiro, 2019). In their 120-stage hydrothermal problem, increasing the Markov chain from 10 to 1,000 nodes per stage narrows the gap between the bounds after 1,000 iterations from roughly 25–30% to roughly 12–14% (read from their Fig. 6), but "the gap between lower and upper bound does not close within 1000 iterations." Its policy is optimal for the Markov chain, not for the actual data process, so its performance depends on how accurately the chain approximates that process. When the chain is accurate, MC-SDDP performs well in out-of-sample tests. When it is not, the policy can remain suboptimal even after SDDP has converged on its own model. The new power-flow benchmark is consistent with this: MC-SDDP’s bound gap is below 1% in 23 of 25 runs, yet its test cost is 7.8% above the perfect-information bound and about 6.3% above FeasPG.

In the submitted paper, SDDP ran a fixed budget of 80 forward/backward iterations (App. K). We reran both methods on the same 48-stage instances with much larger budgets.

ONS (×1e9)CAMELS-BRtime per seed (ONS / CAMELS-BR)
MC-SDDP, paper budget (80 iterations)63.9174.81.5 min / 2.5 min
MC-SDDP, extended (8 forward paths per iteration, up to 6 h)57.2161.56 h
FeasPG, paper budget (1,250 updates)55.46167.400.9 h / 11 min
FeasPG, extended (5,000 updates)49.80164.382.7 h / 39 min

With up to 6 hours per seed and 8 forward paths per iteration, SDDP improves from 63.9 to 57.2 on ONS and from 174.8 to 161.5 on CAMELS-BR, but the gap between its bounds on its own model is still 56–59% and 32–34%. FeasPG also improves with more updates. Given the same training time as the extended FeasPG, SDDP costs 14.8% more on ONS and ties on CAMELS-BR (+0.2%, 95% CI [−0.01%, +0.4%]). With the full 6 hours, more than five times FeasPG's training time on CAMELS-BR, SDDP still costs 14.9% more on ONS and costs 1.8% less on CAMELS-BR.

Lastly, we would like to emphasize the limited update capability of SDDP under online data, which motivated this project in the first place. SDDP first constructs an approximate problem, e.g., here, an approximate problem based on a Markov chain learned from the NN training sample paths, then approximates its value functions, and the policy comes out of these value functions. Incorporating new sample paths therefore requires constructing a new approximate problem and rerunning SDDP on it from scratch to approximate its value functions. Some existing works relax this limitation (Gangammanavar & Sen, 2021), but they still rely on the standard assumptions of SDDP (e.g., convex stage problems and stagewise independent uncertainty). Policy optimization, in contrast, is designed to directly update the policy as new samples become available, which is our main motivation to develop an online alternative for solving MSPs.

AuthorsOpenReview ↗

Response to Reviewer oE3f (3/4): Choice of Baselines (Q2)

Q2: Choice of baselines. PROF puts a projection layer inside the policy and adds a fixed-weight penalty on the distance between the proposal and its projection. It trains with PPO or a one-step loss, without differentiating through the dynamics. We added both PROF variants on the synthetic system (matched MLP policy, same hyperparameter grid, N=2500N = 2500 training paths):

VariantTest cost (×1e3)vs FeasPG (55.84)
One-step gradient, fixed penalty67.30+20.5%
PROF-PPO79.76+43%

Both are clearly worse than FeasPG. The one-step loss ignores how today's decision affects later stages, and PPO estimates the gradient from sampled returns instead of differentiating through the known dynamics.

Following SHAC (Xu et al. 2022), which uses a short window to avoid exploding or vanishing gradients and a learned critic to smooth out local minima in contact-rich robot control, the submission used an 8-stage window. To test this choice, we swept the window up to the full horizon on all five problems, with the same learning-rate grid for SHAC and FeasPG. The original SHAC has no feasibility projection. To compare only its two design choices, our SHAC baseline uses FeasPG's projection layer, including our moving-recourse derivative. The two methods then differ only in that SHAC truncates the gradient after the window and uses the critic for the cost beyond it. With a full window, the critic plays no role and SHAC computes exactly FeasPG's gradient. On the new benchmarks, validation chose this full window in all 25 seed–budget combinations on power flow, where SHAC and FeasPG give the same cost on every test path, and in 12 of 15 on inventory, where their mean costs differ by at most 0.02 (0.004%). Shorter windows hurt: going from the full horizon to a window of 4 raises cost by 86% on the synthetic system, 20% on CAMELS-BR and 2.5% on inventory. In other words, on the new benchmarks validation selects FeasPG's design, and FeasPG reaches it with 0.5–0.8× SHAC's tuning compute, without a window to tune or a critic network to train.

Reviewer_8midOpenReview ↗
Rating
4
Confidence
2
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper propose a projected policy gradient method for multistage stochastic dynamic programming problems. The author solve the MSD problem use project policy gradient descent. The author provide rate of convergence analysis, certification of the solution method, and numerical experiments comparing against pure policy gradient methods such as PPO.

Critical strengths

The paper addresses an important problem in stochastic optimization, reinforcement learning, and constrained sequential decision-making. I particularly appreciate that the framework considers assessing the quality of the resulting solution.

The theoretical development is substantial and technically motivated.

I find the finite-sample certification framework particularly interesting.

Critical weaknesses

My concerns are relatively minor and do not substantially affect my recommendation.

  1. First, the certification procedure requires certified global lower bounds for the inner perfect-information optimization problems, which can be challenging for large scale problems.

  2. Finally, the method relies on known system dynamics and constraints, and the empirical performance results are primarily obtained on model-generated trajectories.

Questions for authors

see limitations.

1 comment
AuthorsOpenReview ↗

Response to Reviewer 8mid

Thank you for the positive assessment and for your interest in the certification framework. We address your two concerns below.

Certified lower bounds for large problems. The certificate compares the policy with a benchmark that sees the future. Each evaluation path requires one deterministic optimization problem, rather than a branching scenario tree. In our benchmark formulations, each additional period adds one block of variables and constraints. The inventory and power-flow inner problems are LPs and QPs, respectively, and dual-feasible solutions provide lower bounds by weak duality.

To assess the computational cost, we ran scaling tests on the multi-item inventory model in Appendix E, with horizons up to 96 periods and item counts up to 32. Each LP solved in milliseconds, and measured solve times grew approximately linearly across these sweeps. A full certificate over 4,096 evaluation paths took a median of 15 seconds on one core and less than three minutes in the largest tested case. On the new 24-stage power-flow benchmark, each per-path QP took 0.14 core-seconds. Once the policy and calibration are fixed, each evaluation path can be processed independently, so the per-path optimization problems can be solved in parallel.

The certificate also gave a useful assessment in the reservoir experiment in Section 5.2: the paired construction produced a mean upper confidence bound of 5.4% of policy cost, while independent reference calculations placed the actual optimality gap between 3.3% and 4.4%. For this small instance, dynamic programming exploits the model’s structure to solve the inner problems and support the reference calculations. This is a solver choice for that instance, not a requirement of the certificate. We will clarify this distinction in the revision.

Known dynamics and model-generated paths. FeasPG assumes known physical dynamics and constraints, but does not require the uncertainty distribution to be known. This is a standard setting in multistage stochastic programming (Füllner & Rebennack, 2025). For example, reservoir balance equations and storage capacities are known, while future inflows must be estimated from data. Policy optimization uses these physical relationships together with sample paths of the uncertainty.

Our hydrology experiments include both model-generated tests and historical evaluation. In the former, uncertainty paths are simulated from statistical models fitted to historical records. We also evaluate policies using the recorded 2022–2025 ONS history and five historical windows from CAMELS-BR. In these historical evaluations, the physical model computes each policy’s decisions and costs using recorded inputs rather than generated paths. Thus, the assessment is not restricted to uncertainty drawn from the fitted models. We will distinguish these two types of evaluation more explicitly in the revision.

We hope these results address your concerns, and we thank you again for your positive assessment.

Comments on the paper

4 comments
AuthorsOpenReview ↗

General Response to All Reviewers (1/2): What Is New

We thank the reviewers for their careful reading. Two reviewers found it hard to tell what is new in the paper. We state it here, and the table below separates each component from the prior work it builds on.

Our setting is a general multistage stochastic program (MSP): known constraints on the decisions and known dynamics, exogenous uncertainty, and costs and dynamics that need not be convex. As Reviewer oE3f correctly points out, SDDP is the natural comparison, and it is indeed what motivated this work. SDDP assumes convex stage problems and stagewise independent (or Markov) uncertainty, and it is offline: when new sample paths arrive, the policy can only be updated by constructing a new approximation problem and solving it from scratch. Some related value-function approximation methods avoid this (Gangammanavar & Sen, 2021), but they still require convex stage problems and stagewise independent uncertainty. We believe policy optimization can be an online alternative for solving more general MSPs. Because the dynamics are known and the uncertainty is exogenous, a recorded path can be replayed under any policy and its cost differentiated exactly. To our knowledge, no existing MSP method uses this structure to train a feasible policy with an unbiased gradient and to certify the result; this is the gap we fill.

The paper claims three things.

  1. The pathwise gradient of a projected policy contains a term for how an earlier decision moves a later feasible set (Eq. 6). Under regularity conditions, the gradient is unbiased (Thm 1), and omitting this term introduces a bias that does not vanish with more samples (Cor. B.2).

  2. Penalizing the distance between a proposal and its projection preserves the optimal value over multiple stages (Thm B.5). A fixed weight can change the best policy (Remark B.1), whereas a decreasing weight converges to a stationary point of the original cost (Thm B.2).

  3. An upper confidence bound on the optimality gap J(π̂) − V* is valid in finite samples when the information-relaxation penalty is estimated from sample paths (Thms 2–3).

We do not claim the projection layer, pathwise gradients, the penalty itself, or information relaxation; these are inherited and listed in the table. Nor do we claim that the gradient cannot be computed by other means; a differentiable QP layer in a differentiable simulator computes the same gradient away from kinks, provided the constraint bounds enter as differentiable functions of the state. Our contribution is the analysis of this gradient and of the penalty, and the certificate.

The table below summarizes what is new and what we inherit from prior work.

ComponentPrior workNot addressed in prior workNew in this paper
Projection layerGuigues & Henrion (2017); OptNet, cvxpylayers, OptLayer; PROF (Chen et al., 2021)NoneNone; used as is (Eq. 4)
Pathwise gradientPathwise (IPA) gradients (Glasserman, 1991); Differentiable simulation (Suh et al., 2022; Xu et al., 2022)No state-dependent constraints, so no moving-recourse termDerive the moving-recourse term in the gradient (Eq. 6); Prove that the full gradient is unbiased (Thm 1); Analyze the bias from omitting the term (Cor. B.2)
Proposal-distance penaltyPROF (Chen et al., 2021)Fixed weight only; Single-step analysis; True dynamics unknownProve that the penalty preserves the optimal value over multiple stages (Thm B.5); Prove convergence for the original cost with a decreasing weight (Thm B.2)
Optimality certificateInformation relaxation (Brown et al., 2010)Not valid when the penalty is estimated from dataDerive a finite-sample correction for penalties estimated from sample paths (Thm 2); Prove a confidence bound on the optimality gap (Thm 3); Prove a matching lower bound on the rate (Thm C.2)
AuthorsOpenReview ↗

General Response to All Reviewers (2/2): Baselines and New Benchmarks

Baselines. Relevant to clarifying the novelty, here we also want to clarify how the baselines in our experiments (Sec. 5) differ from FeasPG, which we did not make fully clear in the paper.

To the best of our knowledge, no existing method addresses the general MSP setting in the way FeasPG does, so we modified the baselines, where needed, to apply them to MSPs. The table shows what each method provides and what it lacks relative to FeasPG.

MethodFeasibility guaranteedPathwise gradient through the dynamics over full horizon TMoving-recourse termNonconvex dynamics and serially dependent uncertainty, no discretizationUses the known dynamicsOptimality-gap certificate
FeasPG (ours)YesYesYesYesYes (model required)Yes (Algorithm 2 applies to any feasible nonanticipative policy)
SHAC (Xu et al., 2022)— (projection added by us)No (truncated window)— (derivative added by us)YesYes (model required)No
PPO, SAC (Schulman et al., 2017; Haarnoja et al., 2018)— (projection added by us)NoNoYesNoNo
PROF (Chen et al., 2021)YesNo (PPO or a one-step loss)NoYesNoNo
SDDPYesn/a (cutting planes)n/aNoYes (model required)Discretized model only

As suggested by Reviewer oE3f, we added two experiments beyond reservoir management. The first is a multistage DC optimal power-flow problem on the IEEE 30-bus network, with 24 hourly stages and four storage units. The second is an eight-item inventory system with a two-period lead time, 26 stages, and serially dependent demand. The table reports test cost with N = 2500 training paths (power flow in $/day). FeasPG achieves the best reported cost on both additional benchmarks, matching tuned SHAC with a substantially smaller total tuning budget and outperforming the other tested baselines. Omitting the moving-recourse term increases cost in both experiments, further supporting the importance of accounting for how earlier decisions change later constraints. SDDP uses a 10-node Markov chain per stage; on power flow it converges on its own model, so its gap reflects the discretization, and on inventory it had not converged after 10 times FeasPG's tuning compute.

MethodPower flowInventory
Lower bound on the optimal cost9,684556.2
FeasPG9,822560.0
Projected SHAC, tuned window†9,822560.0
Scenario MPC9,912580.1
Projected SHAC, 8-stage window†10,075562.4
FeasPG without moving recourse10,120566.4
Base-stock—565.3
Deterministic MPC10,267776.9
SDDP10,440748.1
SAC11,944592.7
PPO21,520652.9

† As in the submission, Projected SHAC uses FeasPG's projection layer, including the moving-recourse derivative. It differs from FeasPG only in truncating the gradient after a window and in using a learned critic for the cost beyond it. With the 8-stage window used in the submission, it costs more than FeasPG in every seed at every training-set size: 2.6–3.3% more on power flow and 0.4–0.7% more on inventory. When the window is tuned, validation chooses the full horizon in all 25 seed–budget combinations on power flow and in 12 of 15 on inventory. With the full horizon, the critic plays no role and the gradient equals FeasPG's. FeasPG reaches this result with 0.5–0.8× of SHAC's tuning compute.

Revised PDF. We thank all reviewers for their thoughtful comments and suggestions, which have helped us improve the paper. We uploaded a revised PDF. Changes are marked in blue.

  • Contributions. The introduction now includes the comparison table from our response (Table 1), and the contribution list follows its rows. The related-work paragraph is shortened where the table covers the same ground.
  • Additional benchmarks. Table 2 now reports, next to ONS and CAMELS-BR, the DC optimal power flow and inventory benchmarks from our response and an additional multiperiod portfolio problem (below). Appendix N gives their setups, baselines, lower bounds, and full results, and Table 3 (Appendix F) compares the properties of all methods.
  • SDDP . Finite-state SDDP is now called MC-SDDP (Markov-chain SDDP; Löhndorf & Shapiro, 2019).
  • Certificate . Section 5.2 now states that Algorithm 2 needs only a certified lower bound per evaluation path, which any dual-feasible solution provides for linear or convex quadratic inner problems.
  • SHAC. Section 5.1 states that our Projected SHAC includes the moving-recourse derivative and also reports SHAC with a validation-tuned window.

To further address the request for broader benchmarks, we have added a portfolio optimization experiment (see the table below and Appendix N). Here, uncertain asset returns multiply the holdings carried between periods, introducing a different form of state dynamics from the resource-management applications. Our experiments now cover four major applications of multistage stochastic programming: reservoir management, power flow, inventory control, and portfolio optimization. These span energy, supply chains, and finance, with different constraints and state dynamics. FeasPG's strong performance across these settings supports its applicability well beyond the reservoir problems in the original submission.

Test cost on 4,096 generated test paths at N = 2500, in percent of initial wealth (lower is better; −110 corresponds to terminal wealth 1.10 without loss), mean over five seeds:

MethodPortfolio
FeasPG−116.2
SHAC, tuned window−115.8
SAC−110.0
MC-SDDP−109.4
SHAC, 8-stage window−109.2
Buy-and-hold (tuned)−107.5
Constant mix (tuned)−107.3
PPO−106.9

We hope that the additional experiments and clarifications address the reviewers' concerns, and we would be glad to answer any further questions during the remaining discussion period.

AuthorsOpenReview ↗

Final Response to All Reviewers: Contributions and Summary of Revisions

We thank all three reviewers for their constructive feedback. As the discussion period draws to a close, we summarize our contributions and explain how the revised PDF, with changes highlighted in blue, addresses the main concerns.

Contributions. FeasPG learns feasible policies for MSPs whose constraints depend on earlier decisions and certifies how far a policy is from optimal. We make contributions in several areas that have not been addressed in the literature. Table 1 and the contribution list in the introduction state precisely what is new.

  • Performance: FeasPG achieves the lowest test cost among the compared methods on all five benchmarks, tying with tuned SHAC on two. These results demonstrate state-of-the-art performance on standard problem instances in energy, supply chains, and finance.
  • General setting: FeasPG accommodates nonconvex costs and dynamics, as well as serially dependent uncertainty, and learns from sample paths without discretization. To our knowledge, no other method handles such general settings.
  • Scalable computation: Our method requires neither a scenario tree, whose size grows exponentially with the planning horizon, nor a discretized Markov-chain approximation of the dependent uncertainty process. Our scheme therefore avoids the curse of dimensionality in the state and decision variables, as well as the planning horizon.
  • General certificate: Our certificate is valid for any feasible nonanticipative policy, including one returned by SDDP, even when the information-relaxation penalty is estimated from data.

Revisions. Below, we summarize the changes made in response to each main concern and what they show.

  • Unclear contributions (nW5N, oE3f). Table 1 in the introduction now separates inherited components from new contributions, followed by the contribution list. Table 3 in Appendix F compares the properties of all methods. Each contribution is explicitly linked to the result that establishes it.
  • Limited benchmarks (oE3f). The original experiments were all reservoir problems. We have added multistage optimal power flow, multi-item inventory, and portfolio optimization experiments in Appendix N. FeasPG also achieves the lowest cost on these benchmarks, showing that its advantage is not specific to reservoirs.
  • SDDP and ground truth (oE3f). We reran SDDP with larger budgets (Response 2/4) and on all new benchmarks (Appendix N). With serially dependent data, SDDP’s convergence establishes optimality only for its discretized model. On power flow, it converges, with a bound gap below 1% in 23 of 25 runs, yet its test cost is 7.8% above a valid lower bound on the optimal cost, while FeasPG is within 1.4% (0.7% on inventory). These lower bounds, together with the certificate experiments with a known true gap in Section 5.2 and Appendix L, provide the ground-truth references.
  • Choice of baselines (oE3f). We added two PROF variants, whose costs are 20–43% higher than FeasPG’s on the synthetic system (Response 3/4), and tuned the SHAC window up to the full horizon (Section 5.1). On the new benchmarks, validation mostly selects the full horizon, where SHAC’s gradient equals FeasPG’s.
  • How the certificate is used (oE3f). Sections 2 and 4 now explain how Algorithms 1 and 2 work together, and Appendix M uses the certificate to stop training. For the policy studied in Section 5.2, the stopping rule terminates training after 10% of the updates in all 200 repetitions, with every certificate remaining above the true gap.
  • Other questions (8mid, nW5N). Our responses show that nondifferentiable points are rare and that alternative derivative choices change test cost by at most 0.34%. A full certificate takes under three minutes in our largest scaling test. The advantage lost on the ONS historical data is recovered once the data model incorporates the load trend.
  • Appendix and writing (oE3f). Each appendix section now begins by explaining what it shows and which main-text claim it supports. We have also corrected typographical errors.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.