Neural Stochastic Dual Dynamic Programming

2021/12/01 by Hanjun Dai, Yuan Xue, Dai, Hanjun +7 · 1 citation
Computer Science · Decision Sciences · #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and ELM #Reinforcement Learning in Robotics #Risk and Portfolio Optimization

paper · pdf · doi:10.48550/arxiv.2112.00874

openalex publication_date 2021/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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 (ν-SDDP) continually self-improves by solving successive problems. An empirical investigation demonstrates that ν-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.

Citations

• Playing Atari with Deep Reinforcement Learning
• Scenarios and Policy Aggregation in Optimization Under Uncertainty
• The Value of Multistage Stochastic Programming in Capacity Planning Under Uncertainty
• Learning Combinatorial Optimization Algorithms over Graphs
• Efficient Off-Policy Meta-Reinforcement Learning via Probabilistic\n Context Variables
• Meta Reinforcement Learning with Task Embedding and Shared Policy
• Learning to Plan in High Dimensions via Neural Exploration-Exploitation Trees
• Numerical optimization

Cited by

• ICNN-enhanced 2SP: Leveraging input convex neural networks for solving two-stage stochastic programming

Related

• Neur2SP: Neural Two-Stage Stochastic Programming
• Complexity of Stochastic Dual Dynamic Programming
• Alternating mixed-integer programming and neural network training for approximating stochastic two-stage problems
• NOVAS: Non-convex Optimization via Adaptive Stochastic Search for End-to-End Learning and Control
• Approximate Dynamic Programming with Neural Networks in Linear Discrete Action Spaces