Monte Carlo Sampling Approach to Solving Stochastic Multistage Programs
summary
Argues that multistage stochastic linear programs are tractable with Monte Carlo discretization when decisions do not affect the data distribution, using rectangular (marginal) sampling to avoid tracking full histories and cutting-plane approximations (SDDP‑style backward cuts and forward simulation) to approximate convex cost‑to‑go functions. Shows how sampling gives statistical lower and upper bounds, reports empirical success on problems with ~120 stages, 10–20 state dimensions, and warns of exponential sample complexity and difficulty when discount factors approach 0.99.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 1:19Stochastic optimization
- 4:24Computational challenges
- 7:33Distributional robustness
- 9:59Risk measures
- 14:07Dynamic formulation
- 20:03Numerical solutions
- 24:22Performance and complexity
- 28:16Periodicity and conclusion
related talks
31mLearning to Control Unknown Systems
31mProbabilistic Programming: The What, Why and How
14mSequential Monte Carlo Program Synthesis with Refinement Proposals
34mFast Algorithms for Multivariate ODEs arising in Sampling and Learning
20mProbabilistic Programming with Stochastic Probabilities
52mThe Simplex and Policy-Iteration Methods are Strongly Polynomial...
01h 01mRobustness, Stochastics, Uncertainty 2
15mMulti-Agent Reinforcement Learning In Stochastic Games: From Alphago To Robust Control