Neural Stochastic Dual Dynamic Programming
Authors: Hanjun Dai
Yuan Xue
Zia Syed
Dale Schuurmans
Bo Dai
Venue: ICLR 2022 Poster (2022)
Keywords: data-driven algorithm design
learning to optimize
multi-stage stochastic optimization
primal-dual dynamic programming

Abstract: Stochastic dual dynamic programming (SDDP) is a state-of-the-art method for solving multi-stage stochastic optimization, widely used for modeling real-world process optimization tasks. Unfortunately, SDDP has a worst-case complexity that scales exponentially in the number of decision variables, which severely limits applicability to only low dimensional problems. To overcome this limitation, we extend SDDP by introducing a trainable neural model that learns to map problem instances to a piece-wise linear value function within intrinsic low-dimension space, which is architected specifically to interact with a base SDDP solver, so that can accelerate optimization performance on new instances. The proposed Neural Stochastic Dual Dynamic Programming ($$\nu$$-SDDP) continually self-improves by solving successive problems. An empirical investigation demonstrates that $$\nu$$-SDDP can significantly reduce problem solving cost without sacrificing solution quality over competitors such as SDDP and reinforcement learning algorithms, across a range of synthetic and real-world process optimization problems.

Published as a conference paper at ICLR 2022
NEURAL STOCHASTIC DUAL DYNAMIC PROGRAMMING
Hanjun ; Yuan Xue Zia Syed", Dale Schuurmans Bo Dail GGoogle Research, Brain Team 9 Google Cloud AI {hadai, yuanxue, zsyed, schuurmans, bodai /egogleegogeecco
ABSTRACT
Stochastic dual dynamic programming (SDDP) is a state-of-the-art method for solving multi-stage stochastic optimization, widely used for modeling real-world process optimization tasks. Unfortunately, SDDP has worst-case complexity that scales exponentially in the number of decision variables, which severely limits applicability only low dimensional problems. To overcome this limitation, we extend SDDP by introducing a trainable neural model that learns to map problem instances piece-wise linear value function within intrinsic low-dimension space, which is architected specifically to interact with a base SDDP solver, so that can accelerate optimization performance on new instances. The proposed Neural Stochastic Dual Dynamic Programming (V-SDDP) continually self- ceff-impooves by solving successive problems. An empirical investigation demonstrates that v-SDDP can significantly reduce problem solving cost without sacrificing solution quality over competitors such as SDDP and reinforcement learning algorithms, across a range of synthetic and real-world process optimization problems.
INTRODUCTION
Multi-stage stochastic optimization (MSSO) considers the problem of optimizing sequence of decisions over a finite number of stages the presence of stochastic observations, minimizing an expected cost while ensuring stage-wise action constraints
satisfied (Birge & Louveaux, 2011; Shapiro et al., 2014). Such a problem formulation captures a diversity of real-world process optimization problems, such as asset allocation (Dantzig & Infanger, 1993), inventory control (Shapiro et al., 2014; Nambiar et al., 2021), energy planning (Pereira & Pinto, 1991), and bio-chemical process control (Bao al., 2019), name a few. Despite the importance and ubiquity the problem, has proved challenging to develop algorithms that can cope with high-dimensional action spaces and long-horizon problems (Shapiro & Nemirovski, 2005; Shapiro, 2006).
There have been a number of attempts to design scalable algorithms for MSSO, which generally attempt to exploit scenarios-wise or stage-wise decompositions. An example approach is Rockafellar & Wets (1991), which proposed progressive hedging algorithm that decomposes the sample averaged approximation of the problem into individual scenarios and applies an augmented Lagrangian method to achieve consistency in final solution. Unfortunately, the number of subproblems and variables grows exponentially in the number of stages, known as the "curse-of- horizon". A similar proposal in Lan & Zhou (2020) considers dynamic stochastic approximation, a variant of stochastic gradient descent, but the computational cost also grows exponentially in the number of stages. Alternatively, stochastic dual dynamic programming (SDDP) (Birge, 1985; Pereira & Pinto, 1991 I), considers a stage-wise decomposition that breaks the curse of horizon (Füllner & Rebennack, 2021) 1) and leads essentially applies an approximate cutting plane method that successively builds a piecewise linear convex lower bound on the optimal cost-to-go function. Unfortunately, SDDP can require an exponential number of iterations with respect to the number of decision variables (Lan, 2020), known as the "curse-of-dimenssinn " (Balázs al., 2015).
scenario-wise
algorithm that often considered state-of-the-art. The method
Beyond the scaling challenges, current approaches share a common shortcoming that they treat each optimization problem independently. It is actually quite common to solve family of problems that share structure, which intuitively should allow the overall computational cost to be reduced (Khalil et al., 2017; Chen et al., 2019). However, current methods, after solving each problem instance via
"Equal contribution

---

Published as a conference paper at ICLR 2022
intensive computation, discard all intermediate results, and tackle all new problems from scratch. Such methods are destined to behave as a perpetual novice that never shows any improvement with problem solving experience.
In this paper, we present a meta-learning approach, Neural Stochastic Dual Dynamic Programming (v- SDDP), that, with problem solving experience, learns to significantly improve the efficiency of SDDP in high-dimensional and long- horizon problems. In particular, v-SDDP exploits specially designed neural network architecture that produces outputs interacting directly and conveniently with a base SDDP solver. The idea is to learn an operator that take information about the specific problem instance, and map it to a piece-wise linear function the intrinsic low-dimension space for accurate value function approximation, so that can be plugged into a SDDP solver. The mapping is trainable, leading to an overall algorithm that self-improves as solves more problem instances. There are three primary benefits of the proposed approach with carefully designed components:
By adaptively generating a low-dimension projection for each problem instance, v-SDDP reduces the aurse-of-dimensin effect for SDDP.
ii) By producing reasonable value function initialization given description of the problem instance, 1-SDDP is able to amortize its solution costs, and gain a significant advantage over the initialization in standard SDDP on the two benchmarks studied in the paper.
iii) By restricting value function approximations to a piece-wise affine form, v-SDDP can be seamlessly incorporated into base SDDP solver for further refining solution, which allows solution time to be reduced.
Figure provides an illustration of the overall DDSDDP method developed in this paper.
X.0
R
GR 47
Imstance
Forvard Paxa
Selt-Inproved
Scpeat
Learning
N+
Figure 1: Overall illustration of DDDDD. For training, the algorithm iterates N times solve different problem instances. For each instance, it repeats two passes: forward (solving LPs to estimate an optimal action sequence) and backward rd (adding new affine components to the value function estimate). Once a problem instance is solved, the optimal value function and optimal actions are used for neural network training. During inference time for a new problem, it can predict high-quality value function with little cost, which can be embedded into SDDP for further improvements.
The remainder of the paper is organized as follows. First, provide the necessary background on MSSO and SDDP in Section 2. Motivated by the difficulty of SDDP and shortcomings of existing learning-base based approaches, component and the learning algorithm described in Section 3.1 and Section 3.2 respectively. We compare the proposed approach with existing algorithms that also exploit supervised learning (SL. and reinforcement learning (RL) for MSSO problems in Section 4. Finally, in Section 5 we conduct an empirical comparison on synthetic and real-worid problems and find that v-SDDP is able to effectively exploit successful problem solving experiences to greatly accelerate the planning process while maintaining the quality of the solutions found.
then propose SDDD in Section 3, with the design of the neural
2 PRELIMINARIES
We begin by formalizing the multi-stage stochastic optimization problem (MSSO), and introducing the stochastic dual dynamic programming (SDDP) strategy we exploit in the subsequent algorithmic development. We emphasize the connection and differences between MSSO and Markov decision process (MDP), which shows the difficulties applying the advanced RL methods for MSSO.
Multi-Stage Stochastic Optimization (MSSO). Consider a multi-stage decision making problem with stages &. 1 1,..., T, where observation & P((-) is drawn at each stage from known
2

---

Published as a conference paper at ICLR 2022
observation distribution Pt. A full observation history { forms scenario, where the obser- vations are assumed independent between stages. At stage t, an action is specified by a vector zt- The goal is to choose a sequence of actions {2+)z=1 T" to minimize the overall expected sum of linear costs Ex= (E{E)) T x, under known cost function ct. This is particularly challenging with feasible constraints on the action set. Particularly, the feasible action set Xt at stage is given by
(1( = [ (Ex) 5t (Ex) B.-1 (Ex) 1 It 0}, VI 2, ..... X1 (E1) = (an/Ar(G)
(1)
(5i) (01))11:1) m120
(2)
where A, Bd and by are known functions. Notably, the feasible set X ( Et) at stage L depends on the previous action Tt-1 and the current stochastic observation & The MSSO problem can then be expressed as
ming, (11 21 Bg, ming, C2 (E2) Ir + Eer [miner er (Ex) FT)
s.t. E 1,) 41 (l,....
where E and the problem context U {(e) )= for u= (Pr, A,, Br, be) are provided. Given the context U given, the MSSO is specified. Since the elements in U are probability functions, the definition of U is only conceptual. In practice, we implement U with its sufficient representations. We will demonstrate the instantiation of U in our experiment section. MSSO often used to formulate real-world inventory control and portfolio management problems; we provide formulations for these specific problems in Appendix B.1 and Appendix B.2.
Similar to MDPs, value functions provide useful concept for capturing the structure of the optimal solution in terms of a temporal recurrence. Following the convention in the MSSO literature (Füllner & Rebennack, 2021), let Qs (x) == min
Ct (E.) 34. Rege+ (Q++1 (12, Ee+))
VI 2, ......
==E
which expresses Bellman optimality condition the feasible action set. Using this definition, the MSSO problem (3) can then be rewritten as
(5) Theorem (informal, Theorem 1.1 and Corollary 1.2 in Füllner & Rebennack (2021)) When the optimization (5) almost surely has a feasãble solution for every realized scenario, the value functions Qz (-g) and Ve (-) are piecewise linear and convex in F, for all t 1,...,??
{iina ei (E1) x1 V2 (x1), S.l. x xI(E)))
Stochastic Dual Dynamic Pro-
Algorithm 1 SDDP (DDP((VV)) -I,n)
gramming (SDDP). Given the
problem specification (3) we now consider solution strate-
1: Sample ( Pt (.) for = =2, =2...., T..,.
2:
for i ......77 do
gies. Stochastic dual dynamic
3: Select J samples from uniform
1, ... m}
b minibatch
programming (SDDP) (Shapiro
4: for l = I,..., and l,..., J do forward pass
et al., 2014; Füllner Reben- nack, 2021) is a state-of-the-art approach that exploits the key ob- servation in Theorem that the optimal V function can be ex-
5:
si (rr min mi (E()) T xe + Vit1 (xx),
(6)
end for s.t. Izj E x((x)-1,)
6:
7:
for t TT...,, do
b backward pass
8:
Calculate the dual variables of (6) for each & in (29); Update V/7 with dual variables via (32) (Appendix C)
pressed as maximum over 9: finite number of linear compo- nents. Given this insight, SDDP applies Bender's s decomposition to the sample averaged approximation of (3). In particular, performs two steps each iteration: (i) in forward pass from t = 0, trial solutions for each stage are generated by solving subproblems (4) using the current estimate the future expected-cost-to-pe function V++1; (ii) a backward pass from t T. each of the V-functions are then updated by adding cutting planes derived from the optimal actions It-1 obtained in the forward pass. (Details for the cutting plan derivation and the connection to TD-learning are given in Appendix C due to lack of space.) After each iteration, the current V provides lower bound on the true optimal expected-cost cosettedcostt-ogggo go function, which being successively tightened; see Algorithm 1.
10: end for
11: end for
3

---

Published as a conference paper at ICLR 2022
MSSO vs. MDPs. At the first glance, the dynamics in MSSO (3) is describing markovian relationship on actions, i.e., the current action 2y is determined by current state & and previous action 2/-1. which is different from the MDPs on markovian states. However, we can equivalently reformulate MSSO as
a MDP with state-dependent feasible action set, by defining the t-th step state as s; := (It-1, Et). and action as 0t = Fa E Xt (I Et). This indeed leads the markovian transition Pset (#14 |8, (z, = 1 (I2 E Xx (Z) Pe41 (5e+1), where 1 (rz E Xt (1)) == {1 if x E
Xr (xr- 0 otherwise].
Although we can represent MSSO equivalently in MDP, the MDP formulation introduces extra difficulty in maintaining state-dependent feasible action and ignores the linear structure in feasibility, which may lead to the inefficiency and infeasibility when applying RL algorithms (see Section 5). Instead MSSO take these into consideration, especially the feasibility.
Unfortunately, MSSO and MDP comes from different communities, the notational conventions of the MSSO versus MDP literature are directly contradictory: the Q-function in (4) corresponds to the state-value V-function in the MDP literature, whereas the V-function in (4) is particular to the MSSO setting, integrating out of randomness in state-value function, which has no standard correspondent in the MDP literature. In this paper, we will adopt the notational convention of MSSO.
3 NEURAL STOCHASTIC DUAL DYNAMIC PROGRAMMING
Although SDDP is state-of-the-ard approach that is widely deployed in practice, it does not scale well in the dimensionality of the action space (Lan, 2020). That is, as the number of decision variables in 2, increases, the number of generated cutting planes in the V4+1 approximations tends to grow exponentially, which severely limits the size of problem instance that can be practically solved. To overcome this limitation, we develop new approach to scaling up SDDP by leveraging the generalization ability of deep neural networks across different MSSO instances in this section.
We first formalize the learning task by introducing the contextual MSSO. Specifically, as discussed in Section 2, the problem context U = {wr)²= with u, == (Pr, ct, A,, Br, by) soly defines the MSSO problem, therefore, we denote W (U) as an instance of MSSO (3) with explicit dependence on U. We assume the MSSO samples can be instantiated from contextual MSSO following some distribution, i.e., W(U) P (W)), equivalently, U ~ P (U). Then, instead of treating each MSSO independently from scratch, we can learn to amortize and generalize the optimization across different MSSOs in P (W). We develop a weta-neerning strategy where a model is trained map the u and to a piecewise linear convex Ve-approximator that can be directly used to initialize the SDDP solver in Algorithm 1. In principle, if optimal value information can be successfully transferred between similar problem contexts, then the immense computation expended to recover the optimal V/2 functions for previous problem contexts can be leveraged to shorteut the nearly identical computation of the optimal V4 functions for novel but similar problem context. In fact, as we will demonstrate below, such a transfer strategy proves to be remarkably effective.
3.1 NEURAL ARCHITECTURE FOR MAPPING TO VALUE FUNCTION REPRESENTATIONS
To begin the specific development, we consider the structure of the value functions, which are desired in the deep neural approximator.
Small approximation error and easy optimization over action: recall from Theorem I that the optimal V,-function must be a convex, piecewise linear function. Therefore, it is sufficient for the output representation from the deep neural model to express max-affine function approximations for V,, which conveniently are also directly usable in the minimization (6) of the SDDP solver.
Encode the instance-dependent information: to ensure the learned neural mapping can account for instance specific structure when transferring between tasks, the output representation needs to
encode the problem context information, {PP,, Ct2 Ar, B,, bo))
Low-dimension representation of state and action: the complexity of subproblems in SDDP depends on the dimension of the state and action exponentially, therefore, the output Vy-function approximations should only depend on a low-dimension representation of æ.
For the first two requirements, we consider a deep neural representation for functions ff (s, u.) E EMK fort 1,....22 T. where K is the picce-wise function class with K components, i.e.,
MK K = { () x = max 3 x + oz Br E Rdd 0g E R k=I...,K K
(7)
4

---

Published as a conference paper at ICLR 2022
That is, such a function ff takes the problem context information u input, and outputs set of parameters ( }. {5x}) that define a max-affine function Φ. We emphasize that although we consider M with fixed number of linear components, it is straightforward to generalize to the function class with context-depenlent number of components via introducing learnable K ((e)) E N. A key property of this output representation is that it always remains within the set of valid V- functions, therefore, it can be naturally incorporated into SDDP as a warm start to refine the solution. This approach leaves design flexibility around the featurization the problem context U and actions I, while enabling the use of neural networks for f (-, u), which can be trained end-to-end
To further achieve low- low-dimensional dependence on the action space while retaining convexity of the value function representations for the third desideratum, we incorporate linear projection r = Gy with y E TRP and p < d, such that G = v (u) satisfies GO G I. With this constraint, the mapping f (; u. will be in:
M = o()) R HG (v) = max By Gy + Okk, 8k E RR G E RRdxp,a E
(8)
k=I....K
We postpone the learning of f and v Section 3.2 and first illustrate the accelerated SDDP solver in the learned effective dimension of the action space in Algorithm 2. Note that after we obtain the solution y in line in Algorithm of the projected problem, we can recover x Gy as coarse solution for fast inference. If one wanted more refined solution, the full SDDP could be run on the un-projected instance starting from the updated algorithm state after the fast call.
Practical representation de- tails: In our implementation, we first encode the index of time
Algorithm 2 Fast -erss--Iniae Inferencee(ee).. f. 1h E1)
step by a positional encoding (Vaswani et al., 2017) and exploit sufficient statistics to encode the distribution P(E) (assuming in addition that the Ps are station- ary). As the functions ct. A., B, and be are typically static and problem specific, there structures will remain the same for differ- P.. In our paper focus the generalization within a problem type (e.g., the inventory management) and do not expect the generalization across problems (e.g., train on portfolio management and deploy on inventory manage- ment). Hence we can safely ignore these LP specifications which are typically of high dimensions. The full set of features are vectorized, concatenated and input to a 2-layer MLP with 512-hidden relu neurons. The MLP outputs k linear components, {ax} } and (3x.). that form the piece-wise linear convex approximation for V,, For the projection G, we simply share one G across all tasks, although it is not hard to incorporate neural network parametrized G. The overall deep neural architecture is illustrated in Figure in Appendix D.
1: Set G vb (U)
fast inference
2: Projected problem instance {ge (gt)==1 = {Gu)
3: J (<t (t))., =SDDP (IS (.))))
& we only
need one forward pass in low-dimension space.
{ T ( (<)),. }.,
{Gi (st }
4:
1.j
A Optional refinement */
0 (c)(())) = SDDP (L (L &1, refine solution.
5:
3.2
META SEL.FIMPROVED LEARNING
The above architecture will be trained using a meta- learning strategy, where we collect successful prior experience D,, : 2 = U, (V } {xj (C))) ). by using SDDP to solve a set of training problem instances. Here, U {wi) denotes a problem context, and (V²) T Y and { T.m are the optimal value functions and actions obtained by SDDP for each stage.
Given the dataset D,,, the parameters of and v. W: == [W,, W can be learned by optimizing the following objective via stochastic gradient descent (SGD):
minw
Σ (W;
Σ
( To
(ct)
T
i EMD (f(:n)) vo' vi()) Ao (W),
ZEDn
s.t. (G')
G Ip.
Vi I,...,
(9)
where Gp := (u), EMD (f.V) denotes the Earth Mover's Distance between ff and V, and (W) denotes convex regularizer W. Note that the loss function (9) is actually seeking
5

---

Published as a conference paper at ICLR 2022
Algorithm 3 V-SDDP
1: Initialize dataset Du;
2: for epoch .,..., , do
3: Sample a multi-stage stochastic decision problems U fue ~ P(U);
4: Initial {Vi)) T = (1 7)0 + fw (:fm))=))
with 7 (p:):
L=D
(for(e)) 11 (( SDDP ((V)) 1=1 mI;
T.m
5:
6:
Collect solved optimization instance D; = D
(U, (U. (1
7:
for iter = b
8:
Sample 21 ~ D;;
9:
Update parameters W with stochastic gradients: W W - V//V (W;w((W;)))
10: end for
end for
under orthonormality constraints, hence it seeks principle components the action spaces to achieve dimensionality reduction.
to maximize Ei= Ei (xtj) (a G&G
To explain the role of EMD, recall that [(x, u) outputs convex piecewise linear function represented
by {( + a ) while the optimal value function (z) := {(8))Tz + at (E) [-1 in SDDP is also convex piecewise linear function, hence expressible by maximum over affine
functions. Therefore, EMD (f, Vi*) is used to calculate the distance between the sets {B/ % ) km1
and (Bi, (8), which can be recast
min D), 1(K,t) = {M E RK & 1, M, & 1,,1 (E)(
M1 min(K, (10)
where D E denotes the pairwise distances between elements of the two sets. Due to space limits, please refer to Figure in Appendix D for illustration of the overall training setup. The main reason we use EMD is due to the fact that f and V are order invariant, and EMD provides an optimal transport comparison (Peyré al., 2019) in terms of the minimal cost all pairings.
Remark (Alternative losses): One could argue that it suffices to use the vanilla regression losses, such as the L2 loss ||ʃ (-, u. {) V (- 1l fit f to V*. However, there are several drawbacks with such direct approach. First, such a loss ignores the inherent structure of the functions. Second, to calculate the loss, the observations x are required, and the optimal actions from SDDP are not sufficient to achieve a robust solution. This approach would require an additional sampling strategy that is not clear how to design (Defourny et al., 2012).
Training algorithm: The loss (9) pushes to approximate the optimal value functions for the training contexts, while also pushing the subspace G. to acquire principle components in the action space. The intent is to achieve an effective approximator for the value function in low-dimensional space that can be used warm-star start SDDP inference Algorithm 2. Ideally, this should result in an efficient optimization procedure with fewer optimization variables that can solve a problem instance passes. an on-line deployment, the learned components, and vh,
with fewer forward-backwar can be continually improved from the results of previous solves. One can also optinally exploit the learned component for the initialization of value function in SDDP by annealing with a mixture of zero function, where the weight is sampled from a Bernolli distribution. Overall, this leads to the Meta Self-Improved SDDP algorithm, V-SDDP, shown in Algorithm
4 RELATED WORK
The importance of MSSO and the inherent difficulty of solving MSSO problems at practical scale has motivated research on hand-designed approximation algorithms, as discussed in Appendix A. Learning-basee MSSO approximations have attracted more attentions. Rachev & Römisch (2002); Høyland et al. (2003); Hochreiter & Pflug (2007) learn sampler for generating a small scenario tree while preserving statistical properties. Recent advances in RL is also exploited. Defourny al. (2012) imitate a parametrized policy that maps from scenarios actions from some SDDP solvers. Direct policy improvement from RL have also been considered. Ban & Rudin (2019) parametrize a policy as linear model in (25), but introducing large approximation errors. As extension, Bertsimas & Kallus (2020): Oroojlooyjadid et al. (2020) consider more complex function approximators for the policy parameterization in (25). Oroojlooyjadid et al. (2021); Hubbs et al. (2020); Balaji et al.

---

Published as a conference paper at ICLR 2022
(2019); Barat et al. (2019) directly apply deep RL methods. Avila et al. (2021) exploit off-policy RL tricks for accelerating the SDDP Q-update. More detailed discussion about Avila et al. (2021) can be found in Appendix A. Overall, the majority of methods not able to easily balance MSSO problem structures and flexibility while maintaining strict feasibility with efficient computation. They also tend focus on learning a policy for single problem, which does not necessarily guarantee effective generalization to new cases, as we find in the empirical evaluation.
Context-based meta-RL is also relevant, where the context- teneext-dependent policy (Hausman et al., 2018; Rakelly et al., 2019; Lan et al., 2019) context-dependent value function (Fakoor et al., 2019; Arnekvist et al., 2019; Raileanu et al., 2020) is introduced. Besides the difference in MSSO vs. MDP in Section 2, the most significant difference is the parameterization and inference usage of context-dependent component. In D-SD we design the specific neural architecture with the output as picce-wise wise linear function, which takes the structure of MSSO into account and can be scamlessly integrated with SDDP solvers for further solution refinement with the feasibility guaranteed; while in the vanilla context-based RL methods, the context-dependent component with arbitrary neural architectures, which will induce extra approximation error, and is unable to handle the constraints. Meanwhile, the design of the neural component in v-SDDP also leads our particular learning objective and stochastic algorithm, which exploits the inherent piece-wise linear structure of the functions, meanwhile bypasses the additional sampling strategy required for alternatives.
5 EXPERIMENTS
Problem Definition. We first tested on inventory optimization with the prob- lem configuration in Table. 1. We break the problem contexts into two sets: 1) topology, parameterized via the number of suppliers S, inventories I, and cus- tomers C; 2) decision horizon T. Note Table 1: Problem Configuration in Inventory Optimization. that in the Mid-L.g Lng setting there are 310 continuous action variables, which is of magnitudes larger than the ones used in inventory control literature (Graves & Willems, 2008) and benchmarks, e.g., ORL (Balaji et al., 2019) or meta-RL (Rakelly et al., 2019) on MuJoCo (Todorov et al., 2012).
Problem Setting
Configuration (S-T-C, T)
Smull size topology, Sheet botizon (Sml Shi)
2-2-4.5
Mid-size topology, Long horizon (Mid-I.ng) Portfolio Optimizationn
10-10:20, 10
T=
Within each problem setting, a problem instance is further captured by the problem context. In inventory optimization, a forecast model is usually used to produce continuous demand forecasts and requires re-opiimization of the inventory decisions based on the new distribution of the demand forecast, forming a group of closely related problem instances. We treat the parameters of the demand forecast the primary problem context. In the experiment, demand forecasts are synthetically generated from a normal distribution: de ~ ~VN(pa Ga). For both problem settings, the mean and the standard deviation of the demand distribution are sampled from the meta uniform distributions: Ma U(11, 20), aa ~ U(0, 5). Transport costs from inventories to customers are also subject to frequent changes. We model it via a normal distribution: C, ~ ([He Ge) and use the distribution mean Me ~ 1/00.3, 0.7) as the secondary problem context parameter with fixed oe = 0.2. Thus in this case, the context for each problem instance that f( 24) needs to care about u (Ja, Ta Mc).
The second environment is portfolio optimization. A forecast model is ususally used to produce updated stock price forcasts and requires re-optimization of asset allocation decisions based on the new distribution of the price forecast, forming group of closely related problem instances. We use an autoregressive process of order 2 to learn the price forecast model based on the real daily stock prices in the past 5 years. The last two-day historical prices are used problem context parameters in our experiments. In this case the stock prices of first two days are served as the context U for f.
Due to the space limitation, we postpone the detailed description of problems and additional perfor- mances comparison in Appendix E.
Baselines. In the following experiments, we compare D-SDDP with mainstream methodologies:
SDDP-optimal:
This is the SDDP solver that runs each test problem instance until convergence, and is expected to produce the best solution and serve as the ground-truth for comparison.
SDDP-mean: is trained once based on the mean values of the problem parameter distribution, and the resulting V -ffunction will be applied in all different test problem instances as surrogate of the true V-function. This approach enjoys the fast runtime time during inference, but would yield suboptimal results as it cannot adapt to the change of the problem contexts.
7

---

Published as a conference paper at ICLR 2022
Task
Parameter Domain
SDDP-
P-SDDI-fast
D-SDDP-accurate
Best RL
Mid- Aid-LLog Smnl Shi
demand mean (Maa
16.15 + 18.61%
2.42 :: 1.84%
1.32 1.13%
38.42 + 17.78%
joint (pa & oaa
20.93 22.31%
4.77 + 3.80%
1.81 2.19%
33.08 8.05%
demand moan (paa
24.77 + 27. 37.04%
2.90 + 1.11%
1,51 + 1.08% %
17.81 + 10.26%
joint (Ha & aa)
27.02 29 19.04%%
1 3.22%
3.32 3.06%
50.19 5.57%
joint (jia & dg & Me)
29.99 32.33%
7.05 + 3.60%
3.29 + 3.23%
135.78 + 17.12%
Table 2: Average Error Ratio of Objective Value.
Task
Parameter Domain
SpDP-aptimal
SDDP-mean
P-SDDaaaccurrte SDDD
Best RI
Mid- Sml Sht
demand mean (jaa)
6.80 7.45
14.83 1 17.90
9.60 3.35
1:
3.90.1 8.39
joint (Ha & ma)
10.79 1: 19.75
19.83 1. 22.02
11.04 1 10.83
13.73 16.64
1.183.1 4.251
demand (paa)
51,96 d: 14.90
73.39 1. 59.90
44.27 1. 9.00
33.42 18.01
1,98. 2.65
joint (Ma & oaa)
54.89 = 32.35
85.76 + 77.62
45.53 = 24.14
36.31 = 20.49
205.5 + 150.90
joint (jAd an & pP)
55.14 38.93
86.26 +: 81.14
28.57
563.19 114.03
Table 3: Objective Value Varianec.
Model-free RL algorithms: Four RL algorithms, including DQN, DDPG, SAC, PPO, are directly trained online on the test instances without the budget limit of number of samples. So this setup has more privileges compared to typical me settings. We only report the best RL result Table 2 and Table due to the space limit. Detailed hyperparameter tuning along with the other performance results are reported in Appendix E.
SSDDD-fast: This is our algorithm where the the meta-trained neural-based V-function is directly evaluated on each problem instance, which corresponds to Algorithm 2 without the last refinement step. In this case, only one forward pass of SDDP using the neural network predicted V /ffunction is needed and the V-function will not be updated. The only overhead compared to SDDP-mean is the fordard time of neural network, which can be ignored compared to the expensive LP solving. >-SDDPaacuurate: It is our full algorithm presented in Algorithm 2 where the meta-trained neural-based V-function is further refined with 10 more iterations of vanilla SDDP algorithm.
5.1 SOLUTION QUALITY COMPARISON
For each new problem instance, we evaluate the algorithm performance by solving and evaluating the optimization objective value using the trained V-funetion model over 50 randomly sampled trajectories. We record the rreanccandidaee and the standard derivation of these objective values produced by each candidate method outlined above. As SDDP-optinal is expected to produce the best solution, we use its mean on each problem instance to normalize the difference in solution quality. Specifically, error ratio of method candidate with respect SDDP-optimal is:
(11)
abs (Ds
Inventory optimization: We report the average optimalty ratio of each method on the held-out test problem set with 100 instances in Table 2. By comparison, =-SDDP learns to adaptive to each problem instance, and thus is able outperform these baselines by a significantly large margin. Also we show that by tuning the SDDP with the V-function initialized with the neural network generated cutting planes for just 10 more steps, we can further boost the performance addition, despite the recent reported promising results in applying deep RL algorithms in small-scale inventory optimization problems (Bertsimas Hubbs et al., 2020; Balaji et al., 2019; Barat et al., 2019), it seems that these algorithms get worse results than SDDP and DDSDDP variants when the problem size increases.
WDSDDDDaacuurttee In
Kallus, 2020; Oroojlooyjadid et al., 2020; 2021;
We further report the average variance along with its standard deviation of different methods in Table 3. We find that generally our proposed sDSDP (both fast and accurate variants) can yield solutions with comparable variance compared to SDDP-optimal. SDDP-mean gets higher variance, as its performance purely depends on how close the sampled problem parameters are to their means.
Portfolio optimization: We evaluated the same metrics as above. We train multi-dimensionn second-orde -oddr autoregressive model for the selected US stocks over last years as the price forecast model, and use either synthetic (low) estimated (high) variance of the price test different models. When the variance is high, the best policy found by SDDP is to buy (with appropriate but different asset allocations at different days) and hold for each problem instance. We found our
8

---

Published as a conference paper at ICLR 2022
104
500R-3 500P4
Relative Error
Relative Errar
500M
ratio/%
500P-33
300P-32
530P52
075
10
322
UP
0.0
2.5
5.0
7.5 10.0 12.5 37.5
Time (5)
Time (5)
Time (s)
Sml-Sht-joint (Ma & oa)
Mid-Lng-joint (ua & oa nt) Mid-Lng-joont (μa & oa & He)
Figure 2: Time-solution trade-off. In the left two plots, each dot represents a problem instance with the runtime and the solution quality obtained by corresponding algorithm. The right most plot shows how v-SDDD-accuurae improves further when integrated into SDDP solver.
1000
200
MSDDP fast 50DP mean
Error Errorratiof ratio/
800
rati/%
150
Error ratio/%
50
600
125
40
100
400
75
20
200
25
10
20
40
60
50
100
150
200
250
300
# generated cutting planes
generated cutting planes
Dimension of generated cutting planes
Sml-Sht-joint (ja & oa)
Mid-Lng-joint (Jla & aa & (ee)
Performance of y- Figure 3: V-SDDP-fast with different # generated cutting planes. SDDP with low-rank projection.
Figure 4:
p-SDDP is able to rediscover this policy; when the variance is low, our model is also able to achieve much lower error ratio than SDDP-mean. We provide study details in Appendix E.2.
5.2
TRADE-OFF BETWEEN RUNNING TIME AND ALGORITHM PERFORMANCE
We study the trade-off between the runtime and the obtained solution quality in Figure 2 based on the problem instances in the test problem set. In addition to V-SDDP-fas and SDDP-mean, we plot the solution quality and its runtime obtained after different number of iterations of SDDP (denoted as SDDP-n with n iterations). We observe that for the small-scale problem domain, SDDP-mean runs the fastest but with very high variance over the performance. For the large-scale problem domain, D-SDDP-fast achieves almost the same runtime as SDDP-mean (which roughly equals to the time for round of SDDP forward pass). Also for large instances, SDDP would need to spend magnitudes of runtime to match the performance of y-SDDP-fass If we leverage r-SDDP-accurad to further update the solution in each test problem instance for just 10 iterations, we can further improve the solution quality. This suggests that our proposed 5-SDDP achieves better time-solution trade-offs.
5.3 STUDY OF NUMBER OF GENERATED CUTTING PLANES
In Figure we show the performance of v-SDDP-fast with respect to different model capacities, captured by the number of cutting planes the neural network can generate. A general trend indicates that more generated cutting planes would yield better solution quality. One exception lies in the Mid-Lng setting, where increasing the number of cutting planes beyond 64 would yield worse results. As we use the cutting planes generated by last n iterations of SDDP solving in training D-SDDP-FR fast, hypothesis is that the cutting planes generated by SDDP during the early stages in large problem settings would be of high variance and low-quality, which in turn provides noisy supervision. A more careful cutting plane pruning during the supervised learning stage would help resolve the problem.
5.4 NOW-DIMENSION PROJECT MANCORMANCE
Finally in Figure 4 we show the performance using low-rank projection. We believe that in reality customers from the same cluster (e.g., region/job based) would express similar behaviors, thus we created another synthetic environment where the customers form 4 clusters with equal size and thus have the same demand/transporrttionn cost within each cluster. We can see that as long as the dimension goes above 80, our approach can automatically learn the low-dimension structure, and achieve much better performance than the baseline JDDP-mean Given that the original decision problem is in 3 310-dimensional space, expect having 310/4 dimensions would be enough, where the experimental results verified our hypothesis. We also show the -indemmenioon projection results for the problems with full-rank structure in Appendix E.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
The authors would like thank Sherry Yang, Bethany Wang, Ben Sprecher and others from Cloud Al optimization, and the anonymous reviewers for their valuable feedbacks.
REFERENCES
Isac Arnekvist, Danica Kragic, and Johannes A Stork. Vpe: Variational policy embedding for transfer reinforcement learning. In 2019 International Conference on Robotics and Automation (ICRA), pp. 36-42. IEEE, 2019.
Daniel Avila, Authony Papavasiliou, and Nils Löhndorf. Batch learning in stochastic dual dynamic programming. submitted, 2021.
Bharathan Balaji, Jordan Dell-Masterson, Enes Bilgin, Andreas Damianou, Pablo Moreno Garcia, Arpit Jain, Runfei Luo, Alvaro Maggiar, Balakrishnan Narayanaswamy, and Chun Ye. Orl: Reinforcement learning benchmarks for online stochastic optimization problems. arXiv preprint 191 2019.
G. Balázs, A. György, and Cs. Szepesvári. Near-optimal max-affine estimators for convex regression. In AISTATS, pp. 56-64, 2015.
Gah- Yi Ban and Cynthia Rudin. The big data newsvendor: Practical insights from machine learning. Operations Research, 67(1):90-108, 2019.
Hanxi Bao, Zhiqiang Zhou, Georgios Kotsalis, Guanghui Lan, and Zhaohui Tong. Lignin valorization process control under feedstock uncertainty through dynamic stochastic programming approach. Reaction Chemistry & Engineering, 4(10):1740-174) 2019.
Souvik Barat, Harshad Khadilkar, Hardik Meisheri, Vinay Kulkarni, Vinita Baniwal, Prashant Kumar, and Monika Gajrani. Actor based simulation for closed loop control of supply chain using reinforcement learning. In Proceedings of the 18th International Conference Autonomous Agents and MultiAgent Systems, pp. 1802-1804, 2019.
Gilles Bareilles, Yassine Laguel, Dmitry Grishchenko, Franck lutzeler, and Jérôme Malick. Random- ized progressive hedging methods for multi-stage stochastic programming. Annals of Operations Research, 295(2):535-566 2020.
Richard Bellman. Dynamic Programming. Princcton University Press, Princcton, NJ, USA, edition, 1957.
Dimitri Bertsekas. Dynamic Programming and Optimal Control, Two Volume Set. Athena Scientific, 2001.
Dimitris Bertsimas and Nathan Kallus. From predictive to prescriptive analytics. Management Science, 66(3):1025-100 2020.
Birge. The value of the stochastic solution in stochastic linear programs with fixed recourse. Mathematical Programming. 24:314-325 1982.
John Birge. Decomposition and partitioning methods for multistage stochastic linear programs. Operations research, 33(5):989-1007, 1985.
John R Birge and Francois Louveaux. Introduction stochastic programming. Springer Science & Business Media, 201
Binghong Chen, Bo Dai, Qinjie Lin, Guo Ye, Han Liu, and Le Song. Learning to plan in high dimensions via neural exploration-explootation trees. In International Conference on Learning Representations, 2019.
George B Dantzig and Gerd Infanger. Multi-stage stochastic linear programs for portfolio optimization. Annals of Operations Research, 45(1):59-76, 1993.
10

---

Published as a conference paper at ICLR 2022
Boris Defoumy,, Damien Ernst, and Louis Wehenkel. Multistage stochastic programming: A scenario tree based approach to planning under uncertainty. In Decision theory models for applications in artificial intelligence: concepts and solutions, pp. 97-143. IGI Global, 2012.
Rasool Fakoor, Pratik Chaudhari, Stefano Soatto, and Alexander Smola. Meta-q-learning. arXiv preprinl 1xXiv:9900.000 2019.
Christian Füllner and Steffen Rebennack. Stochastic dual dynamic programming a review. 2021.
Stephen Graves and Sean Willems. Strategic inventory placement in supply chains: Nonstationary demand. Manufacturing & service operations management, 10(2):78-287,, 2008
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. In International Conference on Machine Learning, pp. 1861-1870. PMLR, 2018.
Karol Hausman, Jost Tobias Springenberg, Ziyu Wang, Nicolas Heess, and Martin Riedmiller. Learning an embedding space for transferable robot skills. International Conference on Learning Representations, 2018.
Pascal Van Hentenryck and Russell Bent. Online stochastic combinatorial optimization. The MIT Press, 2006.
Ronald Hochreiter and Georg Ch Pflug. Financial scenario generation for stochastic multi-stage decision processes as facility location problems. Annals of Operations Research, 152(1):257-272, 2007.
Kjetil Høyland, Michal Kaut, and Stein W Wallace. A heuristic for moment-matching scenario generation. Computational optimization and applications, 24(2):169-185, 2003.
Kai Huang and Shabbir Ahmed. The value of multistage stochastic programming in capacity planning under uncertainty. Operations Research, 57(4):8933990 904,, 2009.
Christian Hubbs, Hector D) Perez, Owais Sarwar, Nikolaos V Sahinidis, Ignacio E Grossmann, and John M Wassick. Or-gym: A reinforcement learning library for operations research problem. arXiv preprint arXiv:2008.0633 06319, 2020.
Elias B Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. NIPS, 2017.
K. Kim, M. O. Franz, and B. Schölkopf. Iterative kernel principal component analysis for image modeling. IEEE Transactions on Pattern Analysis and Machine Intelligence, 270))1351-1166. 2005.
Guanghui Lan. Complexity of stochastic dual dynamic programming. Mathematical Programming, pp. 1-38, 2020.
Guanghui Lan and Zhiqiang Zhou Dynamic stochastic approximation for multi-stage stochastic optimization. Mathematical Programming, pp. 1-46, 2020.
Lin Lan, Zhenguo Li, Xiaohong Guan, and Pinghui Wang. Meta reinforcement learning with task embedding and shared policy. arXiv preprint /905
2019.
Timothy P. Lillicrap. Jonathan J. Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. In ICLR. 2016.
RE Mahony, U Helmke, and JB Moore. Gradient algorithms for principal component analysis. The ANZIAM Journal, 37(4):430-450, 1996.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, loannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint 132.5623 2013.
11

---

Published as a conference paper at ICLR 2022
Mila Nambiar, David Simchi-Levi, and He Wang. Dynamic inventory allocation with demand learning for seasonal goods. Production and Operations Management, 30(3)7550-765, 2021.
Jorge Nocedal and Stephen Wright. Numerical optimization. Springer Science & Business Media, 2006.
Afshin Oroojlooyjadid, Lawrence Snyder, and Martin Takáč. Applying deep learning to the newsvendor problem. IISE Transactions, 52(4):444 463, 2020.
Afshin Oroojlooyjadid, MohammadReza Nazari, Lawrence V Snyder, and Martin Takáč. A deep q network for the beer game: Deep reinforcement learning for inventory optimization. Manufacturing & Service Operations Management, 2021.
Mario V. F. Pereira and Leontina M. V. G. Pinto. Multi-stage stochastic optimization applied to energy planning. Mathematical Programming, 52(2):359-375, 1991.
Gabriel Peyré, Marco Cuturi, et al. Computational optimal transport: With applications to data science. Foundations and Trends@ Machine Learning, 116-6))355-607, 2019.
Svetlozar T Rachev and Werner Römisch. Quantitative stability in stochastic programming: The
method of probability metrics. Mathematics of Operations Research, 27(4):792 818, 2002.
Roberta Raileanu, Max Goldstein, Arthur Szlam, and Rob Fergus. Fast adaptation to environ- ments via policy-dynamics value functions. In International Conference on Machine Learning, pp. 7920-7931. PMLR, 2020.
Kate Rakelly, Aurick Zhou, Chelsea Finn, Sergey Levine, and Deirdre Quillen. Efficient off oof-po meta-reinforcemeen learning via probabilistic context variables. In International conference on machine learning, pp. 5331-5340. PMLR, 2019.
Tyrrell Rockafellar and Roger J-B Wets. Scenarios and policy aggregation in optimization under uncertainty. Mathematics of operations research, 16(1):119-144) 1991.
T. D. Sanger. Optimal unsupervised learning in single-layer linear feedforward network. Neural Networks, 2:459-473, 1989.
John Schulman. Optimizing expectations: From deep reinforcement learning to stochastic computa- fion graphs. PhD thesis, UC Berkeley, 2016.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06333 2017.
Alexander Shapiro. On complexity of multistage stochastic programs. Operations Research Letters, 34(1):1-8, 2006.
Alexander Shapiro and Arkadi Nemirovski. On complexity of stochastic programming problems, In Continuous optimization, pp. 111-146. Springer, 2005.
Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszezyóski. Lectures on stochastic program- ming: modeling and theory. SIAM, 2014.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Emanuel Todorov, Tom Erez, and Yuval Tassa. Mujoco: A physics engine for model-based control. In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 5026-5033, IEEE, 2012.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. arXiv preprint arxiv:1706.03762, 2017.
Bo Xie, Yingyu Liang, and Le Song. Scale up nonlinear component analysis with doubly stochastic gradients. CoRR, aass/5504.0355 2015.
12

---

Appendix
A MORE RELATED WORK
To scale up MSSO solvers, a variety of hand-designed approximation schemes have been investigated. One natural approach is restricting the size of the scenario tree using either scenario- wise or state-wise simplification. For example, as a scenario-wise approach, the expected value of perfect information (EVPI, (Birge, 1982; Hentenryck & Bent, 2006)) has been investigated for optimizing decision sequences within a scenario, which are then heuristically combined to form a full solution. Bareilles et al. (2020) instantiates EVPI by considering randomly selected scenarios in progressive hedging algorithm (Rockafellar & Wets, 1991) with consensus combination. For stage-wise approach, two-stage model can be used as a surrogate, leveraging bound on the approximation gap (Huang & Ahmed, 2009). All of these approximations rely on fixed prior design for the reduction mechanism, and cannot adapt to a particular distribution of problem instances. Consequently, we do not expect such methods to be competitive with learning approaches that can adapt the approximation strategy to given problem distribution.
Difference to Learning from Cuts in Avila et al. (2021): the Batch LearningSSDDP (BL-SDDP) released recently, where machine learning technique is also used for accelerating MSSO solver. However, this work significant different from the proposed v-SDDP:
Firstly and most importantly, the setting and target of these works are orthogonal: the BL-SDDP speeds up the SDDP for a particular given MSSO problem via parallel computation; while D-SDDP works for the meta-learning setting that learns from dataset composed by plenty of MSSO problems sampled from a distribution, and the learning target to generalize to new MSSO instances from the same distribution well;
The technique contribution in BL-SDDP and SDDD are differrntt Specifically, BL-SDDP exploits existing off-policy RL tricks for accelerating the SDDP Q-update; while we proposed two key techniques for quick initialization i). with predicted convex functions; ii), dimension reduction techniques, to generalize different MSSOs and alleviate curse-of-dimension issues in SDDP, which has not been explored in BL-SDDP.
Despite being orthogonal, we think that the BL-SDDP can be used in our framework to provide better supervision for our cut function prediction, and serve as an alternative for fine-tuning after y-SDDP-fast
One potential drawback of our v-SDDP is that, when the test instance distributions deviate lot from what has been trained on, the neural initialization may predict cutting planes that are far away from the good ones, which may slow down the convergence of SDDP learning. Characterizing in-distribution out-o--distribution generalization and building the confidence measure is important future work of current approach.
B PRACTICAL PROBLEM INSTANTIATION
In this section, we reformulate the inventory control and portfolio management as multi-stage stochastic decision problems.
B.1 INVENTORY CONTROL
Let S, V, be the number of suppliers, inventories, and customers, respectively. We denote the parameters of the inventory control optimization as:
procurement price matrix: Pa E SVx1
sales price matrix: q RVC1,
unit holding cost vector: h, gx1,
demand vector: d, E Cx1,
13

---

Published as a conference paper at ICLR 2022
supplier capacity vector: i, R
inventory capacity vector: V, R Rxx,
initial inventory vector Wo RVXI
The decision variables of the inventory control optimization are denoted as:
sales variable: y, RVCx1 iindicating the amount sales from inventories to customers
at the beginning of stage t;
procurement variable: Z, E SV indicating the amount of procurement at the beginning stage after sales;
inventory variable: W, E Vxl indicating the inventory level at the beginning of stage after procurement.
We denote the decision variables
It = lye, Ze, Wels
the state
& = [pss qr, he: d,, uc Vt, wol
The goal of inventory management is maximize the net profit for each stage, i.e.,
c 2t p. 2. + h w. -- yr,
and subject to the constraints of 1) supplier capacity; 2) inventory capacity; 3) customer demand, i.e.
Xt (1) Yr. Ze, We
yi d2
(demand bound constraints),
(12)
2 < u (supplier capacity constraints)
(13)
We
&
(inventory capacity constraints)
(14)
C
W < 0 (sales bounded by inventory)
(15)
Gml
8
C
2
yi + W =w;
(inventory transition)
(16)
==1
24, Yt, Wo,
(non-negativity constraints)
(17)
To sum up, the optimization problem can be defined recursively as follows:
min
c Eca min Cz (6x) (Ex) Egs
Ber min (Er) or (Er) ....
(18)
s.t. E x (x. Vi (1....,T)
(19)
In fact, the inventory control problem (18) is simplified the multi-stage stochastic decision problem (3)
by considering state independent transition.
B.2 PORTFOLIO MANAGEMENT
Let / be the number of assets, e.g. stocks, being managed. We denote the parameters of the portfolio optimization are:
ask (price to pay for buying) open price vector pa E R R
bid (price to pay for sales) open price vector qı E R /x1;
initial amount of investment vector wo E R/x1.
initial amount of cash ro R..
14

---

Published as a conference paper at ICLR 2022
The decision variables of the portfolio optimization are:
sales vector Yr E TR. 1x1 indicating the amount sales of asset at the beginning of stage t.
purchase vector 2, xx1 indicating the amount of procurement at the beginning of stage
t;
holding vector W; E RTx1, ,indicating the amount of assets the beginning of stage after purchase and sales;
cash scalar indicating the amount of cash at the beginning of stage t.
We denote the decision variables as
(y,, Zz, W., W., rr],
and the state as The goal of portfolio optimization is to maximize the net profit i.e.
Pt: qt)
c 2t == P, z, q Ye. subject to the constraints of initial investment and the market prices, i.e.,
Xt (It-1. Er) = yv, Ze, Wes rt
yr W < 0
(individual stock sales constraints)
(20)
P. 2, r < (stock purchase constraints)
(21)
yr - 2, + w, r--1 =
(22)
(individual stock position transition)
q. Y: p. Tt + 1
(23)
(cash position transition)
With the e and X (z)-1,Eı) defined above, we initiate the multi-stage stochastic decision problem (3) for portfolio management.
C DETAILS ON STOCHASTIC DUAL DYNAMIC PROGRAMMING
We have introduced the SDDP in Section 2. In this section, provide the derivation of the updates forward and backward pass,
Forward pass, updating the action according to (5) based on the current estimation of the value function at each stage via (4). Specifically, for i-th iteration of t-stage with sample E/ solve the optimization
Iz argmin Ca (s) It + V4L (Ir)..
(24)
ExEx (#)
In fact, the V-function is convex piece-wise function. Specifically, for i-th iteration of I-stage, have
Vi+1 (xt) = max ((ti1) T 2t + at+1). kši
Then, rewrite the optimization (24) into standard linear programming, i.e.,
min
ce
Ft + 0.+1
(25)
A 3t b. (4)) Br-1 (E) It-1,
(26)
+ 0e+1 2 h Vk = 1 I,...,
(27)
(28)
15

---

Published as a conference paper at ICLR 2022
Backward pass, updating the estimation of the value function via the dual of (25), i.e., for i-th iteration of t-stage with sample E/. we calculate
max MIPt
B
(1
+ We
Σ
a k
pi
i+1.
(29)
k=1
s.t.
A E3 Wi Σ
pe (Dftz)
c ( (
(30)
k=1
-1 & p 1.
(31)
Then, we have the
V (Ia-1) = max (V² (xI-1), oftt! (x--1))
(32)
which is still convex piece-wise linear function, with
0/2 ++1 (x+-1) (B)+ Iz-1 + oj
(33)
where
(8t+1) T
1
m
B 5
T
(
Wi
m
j=1
Σ chn (ct) pe (t))
0f 1-1
be
with (we (Ex), Pt (5e) as the optimal dual solution with realization E
In fact, although we split the forward and backward pass, in our implementation, we exploit the primal-dual method for LP, which provides both optimal primal and dual variables, saving the computation cost.
Note that SDDP can be interpreted as form of TD-leamnng using non an-paaametric piecewise linear model for the V-function. exploits the property induced by the parametrization of value functions, leading to the update w.r.t. V-function via adding dual component by exploiting the piecewise linear structure in a closed-form functional update. That is, TD-Icaming (Sutton & Barto, 2018; Bertsekas, 2001) essentially conducts stochastic approximate dynamic programming based the Bellman recursion (Bellman, 1957).
D NEURAL NETWORK AND LEARNING SYSTEM DESIGN
Neural network design: In Figure we present the design of the neural network that tries to approximate the V-function. The neural network takes two components as input, namely the fcature vector that represents the problem configuration, and the integer that represents the current stage of the multi-stage solving process. The stage index is converted into 'time-encoding' which is 128-dimensional learnable vector. We use the parameters of distributions as the feature of á (P(E)) for simplicity. The characteristic function or kernel embedding of distribution can be also used here. The feature vector will also be projected to the same dimension and added together with the time encoding to form as the input the MLP. The output of MLP is matrix of size i (N + 1), where & is the number of linear pieces, N is the number of variable (and we also need one additional dimension for intercept). The result is a piecewise linear function that specifies convex lowerbound. We show an illustration of 2D case on the right part of the Figure 5.
This neural network architecture is expected adapt to different problem configurations and time steps, so as to have the generalization and transferability ability across different problem configura- tions.
Remark (Stochastic gradient computation): Aside from G,s, unbiased gradient estimates for all other variables the loss (9) can be recovered straightforwardly, However, Ge requires special treatment since we would like to satisfy the constraints G G Ip. Penalty method is one of the
choices, which switches the constraints to a penalty in objective, i.e., n | G. T.113 However, the solution satisfies the constraints, only if y co (Nocedal & Wright, 2006, Chapter 17). We
16

---

Published as a conference paper at ICLR 2022
Problem Context
_1,00
82,00 002
Dg. Crg
Minear Projectsion
HTLP
V(z]
Index
Bk Oxk
Vime Pow Eacoding
Figure 5: Hypernet style parameterization neural V V-function.
Forward
Traling Exinsks
Tranirg Tooks
paas
Tisk cerere
Wiire
V Vunnzons
caree
bak iradance
Took iratenra
Sempling
SDOP
delon Evarples
Va laliofon Tasks
SOGP
isskirsincc
+SDDP Inference
xSDDP Trainin
Test Tasks
bak Iradenza
Neural V-Functions
Neural Functioons
Figure Illustration of the overall system design.
derive the gradient over the Stiefel manifold (Mahony al., 1996), which ensures the orthonormal constraints,
grad l = (I - E
(34)
with = = EE can be recognized as an expectation over samples.
Note that this gradient can be estimated stochastically since =\p
The gradients Stiefel manifold {GIGT G /} can be found in Mahony et al. (1996). We derive the gradient (34) via Lagrangian for celf-completeness, following Xie et al. (2015).
Consider the Lagrangian
L (G,,
A) = Σ (W; + -
ZED,
where the A is the Lagrangian multiplier. Then, the gradient of the Lagrangian w.r.t Gy is
VG, L = 2 + G (A+AT).
(35)
With the optimality condition
VG 0= G - 1=0 2 + (A+
2G AAT
(36)
Plug (36) into the gradient (35), we have the optimality condition.
G-G.. EG 0.
(37)
grad
To better numerical isolation of the individual eigenvectors, into the gradient estimator (34), which leads to the generalized Hebbian rule (Sanger, 1989; Kim et al., 2005; Xie et al., 2015),
exploit Gram-Schmice process
grad l = (I CT (G) EG = =c - LT GG) EG
(38)
The CT (-) extracts the lower triangular part of a matrix, setting the upper triangular part and diagonal zero, therefore, is mimicking the Gram-Schmidt process subtracts the contributions from each
17

---

Published as a conference paper at ICLR 2022
500m-3
500R-
Relative Error
Relative Error
5X04
5009-31
500m-32
530P-32
1.4
-500P-
SCEP
0.0
UP
UP
Time (s)
Time (5)
Sml-Sht-mean (pa)
Sul-Sht-joint (Pa & oa)
52024
ScBP3
Relative Ener
Relative Error
$20745
50CP-35
Relative
SCDP
Soch-man
02
Time
Time
Time (s)
Mid-Lng-mean (pa)
Mid-Lng-joint (μa & oa)
Mid-Lng-joint (Ma oa Nc)
Figure Time-solution trade-off.
other eigenvectors to achieve orthonormality. Sanger (1989) shows that the updates with (38) will converges to the first p cigenvectors of E.
System design: Next we present the entire system end-to-end in Figure 6.
Task sampling: the task sampling component draws the tasks from the same meta distribution. Note that each task is specification of the distribution (e.g., the center of Gaussian distribution), where the specification follows the same meta distribution.
We split the task instances into train, validation and test splits:
Train: We solve each task instance using SDDP. During the solving of SDDP we need to perform multiple rounds of forward pass and backward pass to update the cutting planes (V (V-functions), well sampling trajectories for monte-carlo approximation. The learned neural V function will used as initialization. After SDDP solving converges, we collect the corresponding task instance specification (parameters) and the resulting cutting planes at each stage to serve as the training supervision for our neural network module.
Validation:
We do the same thing for validation tasks, and during training of neural network will dump the models that have the best validation loss.
Test: In the test stage, we also solve the SDDP until convergence as groundtruth, which is only used for evaluating the quality of different algorithms, For our neural network approach, we can generate the convex lower-bound using the trained neural nework, conditioning on each pair of (test task instance specification, stage index). With the predicted V-functions, we can run the forward pass only once to retrieve the solution at each stage. Finally we can evaluate the quality of the obtained solution with respect to the optimal ones obtained by SDDP.
E MORE EXPERIMENTS
E. INVENTORY OPTIMIZATION
E.1.1 ADDITIONAL RESULTS ON SDDP
We first show the full results of time-solution quality trade-off in Figure 7, and how y-SDDP-accuraa improves from D-SDDP-fast with better trade-off than SDDP solver iterations in Figure 8. We can see the conclution holds for all the settings, where our proposed D-SDDP achieves better trade-off.
Then also show the ablation results of using different number of predicted cutting planes in Figure 9. We can see in all settings, generally the more the cutting planes the better the results. This suggests that in higher dimensional case might be harder obtain high quality cutting planes, and
18

---

Published as a conference paper at ICLR 2022
101
10a
104
VIDOR SOLDOO
Error ratio/%
Error ratio/%
Error ratio/%
SOOP
10a
10a
2
8
10
12
0.0
2.5
5.0
7.5
10.0 12.5
15.0 17.5
0.0
2.5
5.0
7.5
15.0 20.0 Time (s)
10.0 12.5
Time (s)
Time (s)
Mid-Lng Len--annmean (Fa)
Mid-Lng-joint (μa & oa)
Mid-Lng-joint (Ha aa & (ee
Figure 8: Time-solution trade-off when --SDDP-accurate improves the solution from V-SDDP-fast further.
1000
1000
Error Error ratio%%
800
Error ratio/%
800
800
600
400
200
200
# generated cutting planes
# generated cutting planes
Sml-Sht-mean (Pa)
Sml-Sht-joint (jaa & oaa)
160
200
140
Error rabio%%
120
Error rabio/%
120
150
100
100
125
80
60
Error
40
50
20
0-
0
20
40
60
80
100
20
40
60
800
100
20
40
60
80
100
# generated cutting planes
generated cutting planes
generated cutting planes
Mid-Lng-mant Lng-mean (Ha)
Mid-Lng-joint (ja & oaa)
Mid-Lng-joint (μa & aa & (ee)
Figure 9: Ablation: number of generated cutting planes.
due to the convex-lowerbound nature of the V-function, having bad cutting plane could possibly hurt the overall quality. How to prune and prioritize the cutting planes will an important direction for future works.
We provide the full ablation results of doing low-dimensional projection for solving SDDP in Figure 10. The trend generally agrees with our expectation that, there is trade-off of the low- dimensionality that would balance the quality LP solving and the difficulty of neural network learning.
Longer horizon: we further experiment with the Mid-Lng-joint (Ha8o,&&pe)) by varying in (10, 20, 30, 40, 50). See Table for more information.
Table 4: Average error ratio of v-SDDP-fast Mid-Lng-joint (ua80 setting with varying T.
Horizon length
10
20
30
40
50
Average еттоr ratio
3.29%
3.47%
3.53%
2.65%
0.82%
E.1 ADDITIONAL RESULTS MODEL-FREE RL ALGORITHMS
We implemented the inventory control problem as an environment in the Tensorflow TF-Agents library and used the implementation of DQN (Mnih et al., 2013)', DDPG (Lillicrap al., 2016), PPO (Schulman et al., 2017) and SAC (Haarnoja et al., 2018) from the TF-Agent to evaluate the performance of these four model-free RL algorithms. Note that the TF-Agent environment follows
We provided simple extension of DQN support multi-dimensional actions.
19

---

Published as a conference paper at ICLR 2022
Enror ratio/6
Error ratio
2.8
2.6
6.0
23-
244
5.4
200 205 290 295
300 305
310
200
205
250
295
300 305
310
280
285 290 295 300 305 310
Dimension of generated cutting planes
Dimension of generated cutting planes
Dimension of generated cutting planes
Mid-Lng-mean (Ha)
Mid-Lng-joint (Ha & oa)
Mid-Lng-joim (pa da Me))
Figure 10: Low-dim projection results when the underlying problem does not have low-rank structure.
Tusk
Parumeter Domain
DQN
DDPG
PPО
SAC
Mid- Long Stnt Sta
demand mean (paa)
1157.86 452.50%
28.62 8.69
2849.931 + 829.91%
38.42 17.78%
joint (pt & cra)
3609.62 1: 912.54%
100.00 + 0.00 %
3273.71 + 953.13%
33.08 + 8.05%
demand mean
5414.15 + 1476.211
100.00 + 0.00%
5411.16 + 1474.19%
17.81 + 10.26%
joint (Ha oa)
5739.68 +:: 1584.63%
100.00 + 0.00%
5734.75
1582.68
$0.19 + 5.57%
joint (ja da pe)
6382.87 2553.527%
100.00 0.00%
6377.93 #:550.033
135.78 + 17.12%
Table 6: Average Error Ratio of Objective Value.
MDP formulation. When adapting the inventory control problem, the states of the environment are the levels of the inventories and the actions are the amount of procurement and sales. As comparison. the states and actions in the MDP formulation collectively form the decision varialbles linear
in the MSSO formulation and their relationship inventory level transition, is captured constraint. Following Schulman (2016), we included the timestep into state these RI. algorithms to have non non-stationary policies for finite-horizon problems. In the experiments, input parameters for each problem domain and instances are normalized for model training for policy gradient algorithms and the results are scaled back for reporting.
We report average error ratio of these four RL algorithms in Table. along with the average variance in Table. 7. Note that the SAC performance is also reported in the main text in Table. 2 and Table. The model used in the evaluation is selected based on the best mean return over the 50 trajectories from the validation environment, based which the hyperparameters report the selected hyperparameters for each algorithm in Table. 5. We use MLP with 3 layers as the Q-network for DQN, as the actor network and the critic/value network for SAC, PPO and DDPG. All networks have the same learning rate and with dropout parameter as 0.001.
also tuned. We
Table Hyperparameter Selections.
Algorithm
Hyperparameters
SAC
learning r0te() num MLP units (50), target update period (5), target update tau (0.5)
PPO
learning ratc(0.001), num MLP units (50), target update period (5), target update tau (0.5)
DQN
learning r0t0() num MLP units (100), target update period (5), target update tau (0.5)
DDPG
learning (0.001. num MLP units (50), ou stddev (0.2), ou damping (0.15)
We see that SAC performs the best among the four algorithms in terms of solution quality. All the algorithms can not scale to Mid-Long setting. DDPG, for example, produces trivial policy of no action in most of setups (thus has an error ratio of 100). The policies learned by DQN and PPO are even worse, producing negative returns?.
To understand the behavior of each RL algorithm, we plotted the convergence of the average mean returns in Figure. 11 for the Sml-Sht task. In each plot, we show four runs of the respective algorithm under the selected hparameter. We could see that though SAC converges the slowest, able to
Negative returns caused by over-procurement in the early stages and the leftover inventory at the last.
stage.
20

---

Published as a conference paper at ICLR 2022
Task
Parameter Domain
DQN
DDPG
PPO
SAC
Mid- Long Sant Shr
demand mean (y-a)
46.32 + 85.90
0.34 + 0.22
119.08 112000
3.90 8.19
joint (jka da)
86,097 = 100.81
0.00 + 0.00
169.08 + 147.24
1.183: 4.251
demand mean (pia)
1334.30 + 270.00
0.00 + 0.00
339.97 + 620.01
1.98: 2.68
joint (jka oa)
1983.71 + 1874.61
1323.24
joint (pa & da & Me)
1983.74 = 1874.66
0.00 + 0.00
462.74 1332,30
563.19 + 114.03
Table 7: Objective Value Variance.
SAC
PRO
DD"G
-00
5.9
Aerations
102 20
SAC
PPO
DQN
DDPG
Figure 11: Average mean return (values are normalized with optimal mean value as 1.736) )
achieve the best return. For all algorithms, their performance is very sensitive to initialization. DDPG, for example, has three runs with 0 return, while one run with a return of 1.2. For PPO and DQN, the average mean returns both negative.
We further check the performance of these algorithms the validation environment based on the same problem instance (i.e., the same problem parameters) in SDDP-meaa, where the model is trained and selected. We expect this would give the performance upper bound for these algorithms. Again similar results are observed. The best return mean over the validation environment is 388.51 for PPO, 0.95 for DQN, 1.31 for SAC and 1.41 for DDPG, while the SDDP optimal return value 1.736. It is also worth noting that DDPG shows the strongest sensitivity to initialization and its performance drops quickly when the problem domain scales up.
E.2 PORTFOLIO OPTIMIZATION
We use the daily opening prices from selected Nasdaq stocks in our case study. This implies that the asset allocation and rebalancing in our portfolio optimization is performed once each stock market opening day. We first learn a probabilistic forecasting model from the historical prices ranging from 2015-1-1 2020-01-01. Then the forecasted trajectories sampled from the model for the stochastic optimization. Since the ask price is always slightly higher than the bid price, at most one of the buying selling operation will be performed for each stock, but not both, given day.
E.2. STOCK PRICE FORECAST
The original model for portfolio management in Appendix B.2 is too restrict. We generalize the model with autoregressive process (AR) of order o with independent noise is used to model and predict the stock price:
a P Σ (o.Pit +5)+ t
where d; the autoregressive coefficient and e", oV( is white noise of order i, e" NOO,, og) is a white noise of the observation. Each noise term is assumed to be independent. It is easy check that the MSSO formulation for portfolio management is still valid by replacing the expectation for and setting the concatenate state (p qr), where p.-" ;= [p:-ji-o-
We use variational inference to the model. A variational loss function (i.c., the negative evidence lower bound (ELBO)) is minimized to fit the approximate posterior distributions for the above parameters. Then we use the posterior samples as inputs for forecasting. In our study, we have studied the forecasting performance with different length of history, different orders of the AR process and different groups of stocks. Figure. 12 shows the ELBO loss convergence behavior under different setups. As see, AR models with lower orders converge faster and smoother.
21

---

Published as a conference paper at ICLR 2022
1050--
3000
0002
2503
2003
0002
9002
2000
5002
3003
a300
2002
1000
200
100
200
230
250
(a) 5 Stocks with AR order
(b) Stocks with AR order=
(c) Stock Clusters with AR order
Figure 12: Evidence lower bound (ELBO) loss curve.
miriink
AR order
AR order
Figure 13: Probablistic Forecast of 5 Stocks with Different AR Orders.
We further compare the forecasting performance with different AR orders. Figure. 13 plots a side- by-side comparison of the forecasted mean trajectory with a confidence interval of two standard deviations (95%) for 5 randomly selected stocks (with tickers GOOG, COKE, LOW, JPM, BBBY) with AR order of and 5 from 2016-12-27 for trading days. As we could see, a higher AR order (5) provides more varivvaratiion in forecast and closer match to the ground truth.
In addition, we cluster the stocks based on their price time series (i.e., each stock is represented by T --dimensional vector in the clustering algorithm, where T is the number of days in the study). We randomly selected 1000 stocks from Nasdaq which are active from 2019-1-1 to 2020-1-1 and performed k-means clustering form clusters of stocks. We take the cluster center time series as the training input. Figure. 12(c) shows the ELBO loss convergence of an AR process of order based on these 8 cluster center time series. As we see, the stock cluster time series converge smoother and faster compared with the individual stocks as the aggregated stock series are less fluctuated. The forecasting trajectories of these stock clusters starting from 2019-03-14 14 are plotted in Figure. 14.
E.2.2 SOLUTION QUALITY COMPARISON
Table 8: Portfolio optimization with synthetic standard deviation of stock price.
SDDP-mean
r-SDDP-zeroshot
5 stocks (STD scaled by 0.01)
290.05 = 2.9. %
1.72 4.39 %
stocks (STD scaled by 0.001)
271.65 + 221.13 %
1.84 = 3.67 %
8 clusters (STD scaled by 0.1)
69.18 + 77.47
1.43e 6 + 4.30e -
-5%
clusters (STD scaled by 0.01)
65.81 = 77.33 %
3.25e 3.44e 5%
22

---

Published as a conference paper at ICLR 2022
Sepcost Sepcait.ctt
182
1NC
2114
2040014
3013310
camee
2023
202 24
20224547
X00000
WERR cwated
Xidibos
aiboon
X00000
nuuu
3000000
Figure 14:
Probablistic Forecast of 8 Stock Clusters.
With an AR forecast model of order o, the problem context of a protfolio optimizaton instance is then captured by the joint distribution of the historical stock prices over a window of o days. We learn this distribution using kernel density estimation. To sample the scenarios for each stage using the AR model during training for both SDDP and D-SDDP, we randomly select the observations from the previous stage seed the observation sampling in the next stage. Also we approximate the state representation by dropping the term of P t-o With such treatments, we can obtain SDDP results with managcable computation cost. We compare the performance of SDDP-optimal SDDP-mes mean and >-SDDoP-zeoosho under different forecasting models for a horizon of 5 trading days. First we observe that using the AR model with order 2 the forecasting model, suggested by the work (Dantzig & Infanger, 1993), produce a very simple forecasting distribution where the mean is monotonic the forecasting horizon. As result, all the algorithms will lead simple "buy and hold" policy which make no difference in solution quality. We further increase the AR order gradually
23

---

Published as a conference paper at ICLR 2022
from 2 to 5 and find AR order at produces sufficient time variation that better fits the ground truth. Second we observe that the variance learned from the real stock data based on variational inference is significant. With high variance, both SDDP-optimal and --SDDD--zroshppe would achieve the similar result, which is obtained by a similar "buy and hold" policy. To make the task more challenging, we rescale the standard deviation (STD) of stock price by factor in Table 8 for both the 5-stock and 1000-stock case with 8 clusters situations. For the cluster case, the y-SDDP-zeroshot can achieve almost the same performance the SDDP-optimal.
E.3 COMPUTATION RESOURCE
For the SDDP algorithms using multi-core CPUs, where the LP solving can be parallelized at each stage. For RL based approaches and our v-SDDP, we train using a single V100 GPU for each hparameter configuration for most 1 day till convergence.
24


Reviews:
[{"review_id": "wx8JTMolV7q", "reviewer": "Reviewer_RrLt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, the paper is clear and investigates an intuitive extension of an SDDP framework with a learning mechanism. In particular, it is natural to consider more sophisticated value-function estimate procedures when the method is inherently iterative, such as in the case of SDDP and other cut-generation procedure methods. The numerical results, while still somewhat restricted to only two benchmarks, provide interesting insights on the trade-off between computational times and solution quality, as well as promising results.\n\nHowever, I have two major concerns. First, this broader idea of learning from cuts is not new, even within the context of SDDPs. More specifically, I wonder what would be the connections and differences with respect to \"batch learning\" in SDDPs, which is similar in that it learns a \"Q\" function while traversing the state paths. Nonetheless, I believe that any other learning model could also be suitable. A recent reference is from EJOR:\n\nhttp://www.optimization-online.org/DB_FILE/2021/05/8397.pdf\n\nSecond, the paper lacks a deeper, more thorough investigation of when the procedure is beneficial or not. It tends to oversell with somewhat bold statements (e.g., \"v-SSDP reduces the curse of dimensionality effect,\" \"gain a significant advantage over random initialization\" etc), but it is not clear to me whether that should always be the case rigorously. Further, only two benchmarks are not sufficient to make such general statements. \n\nFor instance, what are the properties of the value function (in view of the piecewise elements) so that learning is effective? Could there be a case where the convergence of learning is so slow so that the procedure just adds an overhead? Why only random starts, and not something possibly more systematic but easier to implement (e.g., perhaps https://www.sciencedirect.com/science/article/pii/S0377042715002794?) It would be relevant to precisely identify, at least intuitive, problem structure where we can more easily grasp that random, or any more systematic procedure, could still be beneficial. \n\n\n", "summary_of_the_paper": "The paper develops a stochastic dual dynamic programming (SDDP) approach that incorporates a value-function prediction component. Specifically, the authors use opportunistic forward and backward passes to train a neural network model that estimates the value function, which is subsequently used to initialize and guide the basis SDDP iteration procedure. The procedure also leverages the actual value functions SDDP updates to re-train the predictive model for further epochs. Numerical results on inventory and portfolio optimization suggest better error ratios in comparison to SDDP variants and a reinforcement learning model.\n", "summary_of_the_review": "The paper develops an intuitive and natural idea, with promising results on two benchmarks. However, the paper (i) lacks connection with closely related literature (batch learning in SDDPs), and, in my view, (ii) it does not deeply investigate trade-offs of the methodology and underlying structural properties, besides a limited study on the cut generation procedure.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "hmr9XXTIfHw", "reviewer": "Reviewer_meaA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "** Strengths:\n\n- The paper presents a method that seems sound and non-trivial theoretically with good practical performance.\n\n\n- Comparisons with RL algorithms are included.\n\n\n- The paper is relatively easy to follow given its high degree of technical content\n\n** Weaknesses:\n\n- The subject area is of limited significance to ICLR community. MSSO does not have a history at top ML conferences and this paper does little to show it is a mistake.\n\n\n- The experimental setting is very synthetic. The first problem is completely synthetic and as for portfolio optimization, I doubt there are real-world instances of portfolio optimization that do not optimize a quadratic objective that includes a risk term. This suggests that MSSO as a framework is potentially not rich and flexible enough to spark wider interest.\n\n\n- Additionally, there are no strong baselines (e.g. coming from earlier benchmark-oriented research) available which makes it hard to judge how substantial the progress is.\n\n** Suggestions\n\n- What I believe would help this paper the most would be to invest in convincing the ML community of the relevance of the MSSO framework. If we can now indeed solve larger instances, can this be applied to any already established RL problems? Or is the linear objective too restrictive? Any steps in this direction would increase my assessment of the paper.", "summary_of_the_paper": "The authors address the Multi-Stage Stochastic Optimization Problem. In this \"MDP-like\" setup, the underlying stochastic process generating state transitions is fixed (independent of actions) but the executed actions determine the subspace of action available in future steps. To solve this problem, the traditional approach is to solve a sequence of LPs, and \"backpropagate\" dual variables. This process includes heuristical choices of cutting planes. This paper improves uses a data-driven algorithm to improve this process. As a result, instances with a larger number of variables become manageable.\n\n", "summary_of_the_review": "I believe the paper presents a sound and functional method that improves algorithmic performance on the MSSO problem. It is well-written and evaluated.\n\nI remain unconvinced about the wider significance of MSSO but I am willing to listen to new arguments.\n\nOverall, I have a mild tendency to primarily appreciate the technical quality and lean towards acceptance. However, at this point, I do not see myself championing the paper in case of a large variance of opinions.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JkBhH0kY0_", "reviewer": "Reviewer_doAC", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n-The application to MSSO is interesting. There has been significant attention in using neural methods for deterministic optimization problems (integer programming, for instance). Given the utility of MSSO in OR problems, this learning-based framework could be impactful.\n\n-The use of Earth mover’s distance in learning convex value functions is also interesting.\n\n-There are some strong empirical results, showing significantly improved optimization times with little reduction in performance.\n\nWeaknesses:\n\n-Novelty of the overall framework is relatively limited. As I pointed out above, there have been many papers combining machine learning and existing optimization techniques and therefore I feel that the conceptual novelty of the current paper is low.\n\n-How do RL algorithms, which focus on infinite horizon problems, get ported to the finite horizon case?\n\n-The discussion of MSSO vs MDP is bizarre to me. It is accepted in the OR community that the MSSO formulation is essentially an MDP (see e.g. [1, 2]), where the state is (x_{t-1}, \\epsilon_t) and the action is x_t.  In trying to understand the authors’ comment about using feasible sets as states, I’m wondering if perhaps they are working with a definition of “MDP” that doesn’t allow for state-dependent action sets? However, in many definitions of MDP (e.g., Sec 2.1.2 of Puterman’s text [3]), the set of feasible actions is explicitly allowed to depend on the state.\n\n-In the conclusion of the paper claims that it works well in long-horizon settings, but In the inventory problem, problems of horizon 5 and 10 are considered (what is the horizon of the portfolio problem? I could not find it. Parameters for the portfolio problem should also be included in Table 1). In real-world instances, I would be worried that neural SDDP would need to accurately predict too many value functions to be practical. In such settings, perhaps infinite horizon MSSO models would be more appropriate approximation (see, e.g., [4, 5])? Discussion on this point and more evidence would improve the paper.\n\n[1] ​​http://www.optimization-online.org/DB_FILE/2009/12/2509.pdf\n[2] https://arxiv.org/abs/1605.01521\n[3] https://onlinelibrary.wiley.com/doi/book/10.1002/9780470316887\n[4] http://www.optimization-online.org/DB_FILE/2019/09/7367.pdf\n[5] https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2942921", "summary_of_the_paper": "This paper considers a class of problems called multistage stochastic optimization (MSSO) (also known as stochastic programming) problems, which are essentially MDPs but with linear rewards and constraints. Such problems are very commonly studied in the OR community and solved using a technique called stochastic dual dynamic programming. The main contribution of the paper is a way to learn a neural mapping from MSSO problem instances to value functions, which can be used to warm-start the SDDP solver. Since the output of the neural network is a convex value function parameterized by a list of order invariant affine cuts, the authors propose using an Earth mover’s distance in their loss function.", "summary_of_the_review": "My assessment is that the paper has a nice application to MSSO problems (which could be impactful due to their usage in OR models), but conceptually the novelty is low. The empirical work shows that the algorithms are generally impressive, but some details are missing. The paper could also use more clarity in writing -- see some of the comments that I brought up above.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Ai0yrc3DJnO", "reviewer": "Reviewer_hKKH", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n- The paper is well-written, motivated, and organized. The comparison of MSSO and MDP makes the paper easier to follow for different communities. The motivation of the structure of the value functions is well explained.\n- The proposed neural variant of SDDP addresses the exponential dependency of traditional SDDP over the size of the action space. \n- The paper provides a thorough empirical investigation of their algorithm, which shows the advantage of $\\nu$-SDDP.\n\nWeakness:\n- MSSO problem assumes that the problem context is completely known, while model-free RL does not require any knowledge on the model (such as reward function and transition kernel) and can directly learn from the data. It would be better if the paper could compare $\\nu$-SDDP with RL methods with known MDP. \n- Following the previous question, is it possible to solve MSSO via a completely data-driven approach? Specifically, the feasible action set is revealed at time t without knowing $A_t, B_t, b_t$.\n\n\n", "summary_of_the_paper": "The paper studies the neural variant of stochastic dual dynamic programming for solving multistage stochastic optimization, which overcomes the limitation of SDDP. The paper proposes the algorithm $\\nu$-SDDP, which continually self-improves by solving successive problems. The empirical investigation shows that $\\nu$-SDDP outperforms SDDP and reinforcement learning in several synthetic and real-world process optimization problems.\n", "summary_of_the_review": "The paper is well motivated. The proposed algorithm is novel and interesting. Thus, I recommend acceptance for the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper applies deep learning to a problem from OR, namely multistage stochastic optimization (MSSO). The main contribution is a method for learning a neural mapping from MSSO problem instances to value functions, which can be used to warm-start the SDDP solver, a state-of-the-art method for solving MSSO. The method is tested on two typical OR problems, inventory control and portfolio management. The reviewers think that the idea is interesting, the empirical results are impressive, and the paper is well-written. However, there are reservations on its relevance to the ICLR community.
Decision: Accept (Poster)