Abstract

We study the consistency of stochastic dynamic programs under converging probability distributions and other approximations. Utilizing results on the epi-convergence of expectation functions with varying measures and integrands, and the Attouch-Wets distance, we show that appropriate equi-semicontinuity assumptions assure epi-consistency. A number of examples illustrate the approach. In particular, we permit both unbounded and simultaneously approximated stage-cost functions, and treat an example with approximated constraints.

Author information

Contact details are reproduced from the original publication and may be historical.

Johannes O. Royset

University of Southern California, Los Angeles, U.S.A.

royset@usc.edu

Keywords

  • Stochastic optimal control
  • stochastic dynamic programming
  • epi-convergence
  • Attouch-Wets distance

Mathematics Subject Classification

90C15; 90C39

References

  1. Z. Artstein, R. J-B Wets: Consistency of minimizers and the SLLN for stochastic programs, J. Convex Analysis 2 (1995) 1–17.https://doi.org/10.68381/jca02001Google Scholar
  2. H. Attouch, R. Lucchetti, R. J-B Wets: The topology of the ρ-Hausdorff distance, Ann. Mat. Pura Appl. 160 (1991) 303–320.https://doi.org/10.1007/BF01764131Google Scholar
  3. H. Attouch, R. J-B Wets: Isometries for the Legendre-Fenchel transform, Trans. Amer. Math. Soc. 296 (1986) 33–60.https://doi.org/10.1090/S0002-9947-1986-0837797-XGoogle Scholar
  4. H. Attouch, R. J-B Wets: Quantitative stability of variational systems. I: The epigraphical distance, Trans. Amer. Math. Soc. 328/2 (1991) 695–729.https://doi.org/10.1090/S0002-9947-1991-1018570-0Google Scholar
  5. D. P. Bertsekas, S. E. Shreve: Stochastic Optimal Control: The Discrete-Time Case, Athena Scientific, Belmont (1996).Google Scholar
  6. P. Billingsley: Probability and Measure, 3rd ed., Wiley, New York (1995).Google Scholar
  7. P. Billingsley: Convergence of Probability Measures, 2nd ed., Wiley, New York (1999).https://doi.org/10.1002/9780470316962Google Scholar
  8. R. Davidson, J. G. MacKinnon: Econometric Theory and Methods, Oxford University Press, New York (2004).Google Scholar
  9. O. Dowson: The policy graph decomposition of multistage stochastic programming problems, Networks 76/1 (2020) 3–23.https://doi.org/10.1002/net.21932Google Scholar
  10. O. Dowson, L. Kapelevich: SDDP.jl: A Julia package for stochastic dual dynamic programming, INFORMS J. Computing 33 (2021) 27–33.https://doi.org/10.1287/ijoc.2020.0987Google Scholar
  11. E. A. Feinberg, P. O. Kasyanov, J. O. Royset: Epi-convergence of expectation functions under varying measures and integrands, J. Convex Analysis 30/3 (2023) 917–936.https://doi.org/10.68381/jca30043Google Scholar
  12. E. A. Feinberg, P. O. Kasyanov, N. V. Zadoianchuk: Average cost Markov decision processes with weakly continuous transition probabilities, Math. Oper. Res. 37/4 (2012) 591–607.https://doi.org/10.1287/moor.1120.0555Google Scholar
  13. E. A. Feinberg, P. O. Kasyanov, M. Z. Zgurovsky: Partially observable total-cost Markov decision processes with weakly continuous transition probabilities, Math. Oper. Res. 41/2 (2016) 656–681.https://doi.org/10.1287/moor.2015.0746Google Scholar
  14. A. D. Ioffe: On lower semicontinuity of integral functionals I, SIAM J. Control Optim. 15/4 (1977) 521–538.https://doi.org/10.1137/0315035Google Scholar
  15. D. S. T. Keehan, A. B. Philpott, E. J. Anderson: On the out-of-sample performance of stochastic dynamic programming and model predictive control, INFORMS J. Optim. (2025), to appear.https://doi.org/10.1287/ijoo.2024.0060Google Scholar
  16. A. J. King, R. J-B Wets: Epi‐consistency of convex stochastic programs, Stochastics Stochastic Rep. 34/1-2 (1991) 83–92.https://doi.org/10.1080/17442509108833676Google Scholar
  17. A. Klenke: Probability Theory: A Comprehensive Course, 3rd ed., Springer, Cham (2020).https://doi.org/10.1007/978-3-030-56402-5Google Scholar
  18. L. A. Korf: Approximating infinite horizon stochastic optimal control in discrete time with constraints, Ann. Oper. Res. 142 (2006) 165–186.https://doi.org/10.1007/s10479-006-6167-xGoogle Scholar
  19. B. Light: The principle of optimality in dynamic programming: A pedagogical note, Oper. Res. Letters 57 (2024), art.no. 107164.https://doi.org/10.1016/j.orl.2024.107164Google Scholar
  20. G. Nannicini, E. Traversi, R. W. Calvo: A Benders squared (B2) framework for infinite-horizon stochastic linear programs, Math. Programming Comput. 13 (2020) 645–681.https://doi.org/10.1007/s12532-020-00195-2Google Scholar
  21. T. Pennanen: Epi-convergent discretizations of multistage stochastic programs, Math. Oper. Res. 30/1 (2005) 245–256.https://doi.org/10.1287/moor.1040.0114Google Scholar
  22. T. Pennanen: Epi-convergent discretizations of multistage stochastic programs via integration quadratures, Math. Programming 116 (2009) 461–479.https://doi.org/10.1007/s10107-007-0113-9Google Scholar
  23. M. V. F. Pereira, L. M. V. G. Pinto: Multi-stage stochastic optimization applied to energy planning, Math. Programming 52 (1991) 359–375.https://doi.org/10.1007/BF01582895Google Scholar
  24. R. T. Rockafellar, R. J-B Wets: Variational Analysis, Grundlehren der Mathematischen Wissenschaften 317, Springer, Berlin (1998).https://doi.org/10.1007/978-3-642-02431-3Google Scholar
  25. J. O. Royset: Approximations and solution estimates in optimization, Math. Programming 170 (2018) 479–506.https://doi.org/10.1007/s10107-017-1165-0Google Scholar
  26. J. O. Royset, R. J-B Wets: Variational analysis of constrained M-estimators, Ann. Statistics 48/5 (2020) 2759–2790.https://doi.org/10.1214/19-AOS1905Google Scholar
  27. J. O. Royset, R. J-B Wets: An Optimization Primer, Springer, Cham (2021).https://doi.org/10.1007/978-3-030-76275-9Google Scholar
  28. A. Shapiro: Inference of statistical bounds for multistage stochastic programming problems, Math. Methods Oper. Res. 58 (2003) 57–68.https://doi.org/10.1007/s001860300280Google Scholar
  29. A. Shapiro, Y. Cheng: Central limit theorem and sample complexity of stationary stochastic programs, Oper. Res. Letters 49/5 (2021) 676–681.https://doi.org/10.1016/j.orl.2021.06.019Google Scholar
  30. A. Shapiro, Y. Cheng: Dual bounds for periodical stochastic programs, Oper. Res. 71/1 (2023) 120–128.https://doi.org/10.1287/opre.2021.2245Google Scholar
  31. A. Shapiro, L. Ding: Periodical multistage stochastic programs, SIAM J. Optim. 30/3 (2020) 2083–2102.https://doi.org/10.1137/19M129406XGoogle Scholar
  32. N. L. Stokey, R. E. Lucas Jr., E. C. Prescott: Recursive Methods in Economic Dynamics, Harvard University Press, Cambridge (1989).https://doi.org/10.2307/j.ctvjnrt76Google Scholar

Suggested citation

D. S. T. Keehan, J. O. Royset. “Epi-Consistent Approximation of Stochastic Dynamic Programs.” Journal of Convex Analysis 33 (2026), No. 1&2, 393–413. https://doi.org/10.68381/jca33024

Download BibTeXPublished by Heldermann Verlag.

Published by Heldermann Verlag, 2026. Rights now held by Banach Press LLC.