Theoretical Foundations of Sequential Dynamic Programming
Abstract
Many economic problems have several controls per period, whose joint choice is subject to the curse of dimensionality. Solving them in stages is computationally cheaper, but no general result says when staging is exact. I develop a separability theory, discrete choices and non-concave objectives included: staging is exact if utility, transitions, and constraints depend on earlier decisions only through a state passed forward. For each ordering the smallest such state exists and is unique up to relabeling. Any state that keeps staging exact for all preferences over later decisions and the future must carry everything the smallest one carries for the transition. For affine primitives, the smallest state consists of the linear combinations, such as cash-on-hand, on which later outcomes depend. Its dimensions pick the order whose largest stage is smallest. In a six-choice household model, each stage chooses one variable on a three-dimensional state, the joint problem all six.
Related
- Theoretical Foundations of Computational Islamic Jurisprudence (Fiqh)
- Theoretical Foundations of Ordinal Spherical Multidimensional Scaling
- Theoretical Foundations and Effective Algorithms for Policy-Aware Simulator Learning
- Distributed Intraday Energy Management for 16.7-Hz Railway Power Systems---Part I: Theoretical Foundations
- Learning to Solve Mixed-Integer Nonlinear Programming with Neural Networks and Sequential Quadratic Programming Refinement
BibTeX
@misc{lujan2026theoretical,
title = {{Theoretical Foundations of Sequential Dynamic Programming}},
author = {Alan Lujan},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.27449},
eprint = {2610.27449},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.27449},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Theoretical Foundations of Sequential Dynamic Programming
AU - Alan Lujan
PY - 2026
DA - 2026/10/20
PB - arXiv
DO - 10.48550/arxiv.2610.27449
UR - https://arxiv.org/abs/2610.27449
AB - Many economic problems have several controls per period, whose joint choice is subject to the curse of dimensionality. Solving them in stages is computationally cheaper, but no general result says when staging is exact. I develop a separability theory, discrete choices and non-concave objectives included: staging is exact if utility, transitions, and constraints depend on earlier decisions only through a state passed forward. For each ordering the smallest such state exists and is unique up to relabeling. Any state that keeps staging exact for all preferences over later decisions and the future must carry everything the smallest one carries for the transition. For affine primitives, the smallest state consists of the linear combinations, such as cash-on-hand, on which later outcomes depend. Its dimensions pick the order whose largest stage is smallest. In a six-choice household model, each stage chooses one variable on a three-dimensional state, the joint problem all six.
ER -