Delphi.science

Bidirectional SDDP with dimension-free complexity for solving strongly convex stochastic dynamic programming equations

Pablo Barros, Vincent Guigues

arXivarxiv/2606.10161Jun 8, 2026math.OCscore 0

We analyze the complexity of Bidirectional Stochastic Dual Dynamic Programming (BSDDP) algorithm applied to multistage stochastic optimization problems with strongly convex cost functions. Under standard regularity assumptions and without discount factor, we establish an explicit complexity bound on the expected number of iterations needed to obtain an epsilon-optimal policy. Our bound depends on the strong convexity constants and Lipschitz constants of the stagewise cost functions but is independent of the dimensionality of the state space. This improves upon the complexity of SDDP for…

SourceJSON

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2606.10161
curl -X POST /api/v1/records/arxiv/2606.10161/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.10161/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'