Strategies for alleviating/postponing curse of dimensionality in SDP

Stochastic Dynamic Programming (SDP) is a powerful tool for modelling sequential decision making under uncertainty. However, solving an SDP by a naïve backward recursion is not practical in many close-to-real world instances for many of the decision making problems because the curse of dimensionality emerges after a small increment in the stage index. Curse of dimensionality refers to explosion of either of (i) available decisions to be checked, (ii) available initial states to be checked), and (iii) computational volume for a given decision at a specific initial state (maybe because of growth in the number of possible random transitions to neighboring states of the next stage). This is a computational obstacle for a fast exact solution to an SDP. There are different exact and inexact approaches for battling with the curse of dimensionality. Parallelization of computations is an example for exact approaches and random sampling among available decisions/states to be checked is an example for inexact approaches. However, none of them is a stand-alone panacea for this computational obstacle and some of the times a mixture of them provides better solutions in even a shorter CPU time.

Keywords:

Stochastic dynamic programming , Curse of dimensionality , Sequential decision making , Uncertainty