SDDP has polynomial iteration complexity in the horizon
Abstract
Stochastic dual dynamic programming (SDDP) and its variants are run in practice with forward passes that sample the noise at random. Recent iteration-complexity results favour another choice: when the trial points are selected deterministically, for instance along the scenario with the largest gap, the number of iterations is polynomial in the horizon T, whereas every bound we know of for randomly sampled forward passes is exponential in T. We show that this is not intrinsic to random sampling, for a broad class of trajectory-following dynamic programming algorithms, which includes SDDP, stochastic dual dynamic integer programming and stochastic Lipschitz dynamic programming. With random sampling, and with Lipschitz constants, diameters and per-stage loss ranges bounded independently of the stage and of the horizon, the expected number of iterations whose policy is not Tε-optimal is O(Tε−(d+1)), where d is the state dimension: linear in T, as for deterministic selection rules. The proof needs no particular scenario to be sampled: the gap between the expected cost of the current policy and the current lower bound equals the expected sum of one-step Bellman residuals along the sampled path, and Lipschitz cuts that are tight at the visited states turn the positive residuals into permanent increases of a bounded potential. The results extend to noise without finite support, to backward passes on a sample average approximation, and to stationary and periodic infinite-horizon SDDP with geometric pass lengths.
Related
- Global Sobolev Convergence of Howard Iteration for Finite-Horizon Controlled Diffusions
- Policy Iteration Is Not Strongly Polynomial for Deterministic Markov Decision Processes: The Price of Algorithmic Anarchy
- Simple Strategy-Iteration with Dantzig's Rule is not Strongly Polynomial on Turn-Based Deterministic Games
- Optimal Oracle Complexity of Dual Halpern Iteration in Normed Spaces
- Stochastic Inertial Krasnosel'skii-Mann Iteration Achieves Near-Optimal Sample Complexity
BibTeX
@misc{leclere2026sddp,
title = {{SDDP has polynomial iteration complexity in the horizon}},
author = {Vincent Leclere},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.12713},
eprint = {2610.12713},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.12713},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - SDDP has polynomial iteration complexity in the horizon
AU - Vincent Leclere
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.12713
UR - https://arxiv.org/abs/2610.12713
AB - Stochastic dual dynamic programming (SDDP) and its variants are run in practice with forward passes that sample the noise at random. Recent iteration-complexity results favour another choice: when the trial points are selected deterministically, for instance along the scenario with the largest gap, the number of iterations is polynomial in the horizon T, whereas every bound we know of for randomly sampled forward passes is exponential in T. We show that this is not intrinsic to random sampling, for a broad class of trajectory-following dynamic programming algorithms, which includes SDDP, stochastic dual dynamic integer programming and stochastic Lipschitz dynamic programming. With random sampling, and with Lipschitz constants, diameters and per-stage loss ranges bounded independently of the stage and of the horizon, the expected number of iterations whose policy is not Tε-optimal is O(Tε^−(d+1)), where d is the state dimension: linear in T, as for deterministic selection rules. The proof needs no particular scenario to be sampled: the gap between the expected cost of the current policy and the current lower bound equals the expected sum of one-step Bellman residuals along the sampled path, and Lipschitz cuts that are tight at the visited states turn the positive residuals into permanent increases of a bounded potential. The results extend to noise without finite support, to backward passes on a sample average approximation, and to stationary and periodic infinite-horizon SDDP with geometric pass lengths.
ER -