{"id":"arxiv/2610.12713","url":"https://arxiv.org/abs/2610.12713","tags":["math.OC"],"score":0,"title":"SDDP has polynomial iteration complexity in the horizon","domain":"math.OC","source":"arxiv","authors":["Vincent Leclere"],"reviews":0,"subject":"math.OC","summary":"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,…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-10-08","reactions":{}}