Next-Generation Dynamic Programming Algorithms: A Survey of Modern Techniques, Applications, and Future Directions

Author

Gorasiya Archit Jayeshbhai

Abstract

 Dynamic programming (DP) has anchored sequential optimization since Bellman’s work in the 1950s, but its tabular form breaks down once the state space becomes large, continuous or irregular. This survey follows how the field has answered. We sort recent work into five paradigms, each of which relaxes a different assumption of classical DP: abstract DP, which studies the Bellman operator instead of a particular problem; graph-aware DP, which prunes the state space with problem structure, as in join-order optimization; neuro-dynamic and approximate DP, which replace tables with parametric value functions; parallel DP on multicore and GPU hardware; and quantum DP for exponential-time recurrences. Beyond cataloguing methods, we compare their guarantees and failure modes and back the discussion with four small computational studies of our own: measured contraction rates of value iteration, exhaustive counts of the join pairs examined by DPsub and DPccp (915 times fewer on a twelve-relation chain), a reproduction of Baird’s divergence example, and a wavefront model with a measured CPU baseline. A closed-form comparison of reported quantum speed-ups completes the picture. Applications in query optimization, robot control, energy-storage dispatch and sequence analysis are reviewed, and we close with open problems: convergence under nonlinear approximation, sample efficiency, QRAM limits and the absence of shared benchmarks.

Keywords

Dynamic programming, curse of dimensionality, abstract dynamic programming, neuro-dynamic programming, join-order optimization, GPU acceleration, quantum algorithms, value iteration.

Full Text:

Download Paper PDF

References

[1] R. Bellman, Dynamic Programming. Princeton, NJ, USA: Princeton Univ. Press, 1957.
[2] S. B. Needleman and C. D. Wunsch, “A general method applicable to the search for similarities in the amino acid sequence of two proteins,” J. Mol. Biol., vol. 48, no. 3, pp. 443–453, 1970.
[3] T. F. Smith and M. S. Waterman, “Identification of common molecular subsequences,” J. Mol. Biol., vol. 147, no. 1, pp. 195–197, 1981.
[4] M. Zuker and P. Stiegler, “Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information,” Nucleic Acids Res., vol. 9, no. 1, pp. 133–148, 1981.
[5] P. G. Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price, “Access path selection in a relational database management system,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 1979, pp. 23–34.
[6] M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming. Hoboken, NJ, USA: Wiley, 2005.
[7] G. Moerkotte and T. Neumann, “Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products,” in Proc. 32nd Int. Conf. Very Large Data Bases (VLDB), Seoul, South Korea, 2006, pp. 930–941.
[8] A. Ambainis, K. Balodis, J. Iraids, M. Kokainis, K. Prūsis, and J. Vihrovs, “Quantum speedups for exponential-time dynamic programming algorithms,” in Proc. 30th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA), 2019, pp. 1783–1793.
[9] R. S. Sutton and A. G. Barto, Reinforcement Learning: An Introduction, 2nd ed. Cambridge, MA, USA: MIT Press, 2018.
[10] M. Held and R. M. Karp, “A dynamic programming approach to sequencing problems,” J. Soc. Ind. Appl. Math., vol. 10, no. 1, pp. 196–210, 1962.
[11] R. Bellman, “Dynamic programming treatment of the travelling salesman problem,” J. ACM, vol. 9, no. 1, pp. 61–63, 1962.
[12] R. Mancini, S. Karthik, B. Chandra, V. Mageirakos, and A. Ailamaki, “Efficient massively parallel join optimization for large queries,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2022.
[13] K. Lowrey, A. Rajeswaran, S. Kakade, E. Todorov, and I. Mordatch, “Plan online, learn offline: Efficient learning and exploration via model-based control,” in Proc. Int. Conf. Learn. Represent. (ICLR), 2019.
[14] E. V. Denardo, “Contraction mappings in the theory underlying dynamic programming,” SIAM Rev., vol. 9, no. 2, pp. 165–177, 1967.
[15] D. P. Bertsekas and J. N. Tsitsiklis, Neuro-Dynamic Programming. Belmont, MA, USA: Athena Scientific, 1996.
[16] J. N. Tsitsiklis and B. Van Roy, “An analysis of temporal-difference learning with function approximation,” IEEE Trans. Autom. Control, vol. 42, no. 5, pp. 674–690, May 1997.
[17] G. Moerkotte and T. Neumann, “Dynamic programming strikes back,” in Proc. ACM SIGMOD Int. Conf. Manage. Data, 2008, pp. 539–552.
[18] D. P. Bertsekas, Abstract Dynamic Programming, 3rd ed. Belmont, MA, USA: Athena Scientific, 2022.
[19] V. Mnih et al., “Human-level control through deep reinforcement learning,” Nature, vol. 518, no. 7540, pp. 529–533, 2015.
[20] M. Schönberger, S. Scherzinger, and W. Mauerer, “Ready to leap (by co-design)? Join order optimisation on quantum hardware,” Proc. ACM Manage. Data, vol. 1, no. 1, Art. 92, May 2023.
[21] M. Stoian and A. Kipf, “DPconv: Super-polynomially faster join ordering,” arXiv:2409.08013, Sep. 2024 (to appear at SIGMOD 2025).
[22] S. Caroppo, J. Vihrovs, D. Zajakina, and A. Zajakins, “Quantum time-space tradeoffs for exponential dynamic programming,” arXiv:2604.02233, Apr. 2026.
[23] D. P. Bertsekas, “Regular policies in abstract dynamic programming,” SIAM J. Optim., vol. 27, no. 3, pp. 1694–1727, 2017.
[24] A. Meister, G. Moerkotte, and G. Saake, “Errata for ‘Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products’,” Proc. VLDB Endow., vol. 11, no. 10, pp. 1069–1070, 2018.
[25] W. B. Powell, Approximate Dynamic Programming: Solving the Curses of Dimensionality, 2nd ed. Hoboken, NJ, USA: Wiley, 2011.
[26] L. Baird, “Residual algorithms: Reinforcement learning with function approximation,” in Proc. 12th Int. Conf. Mach. Learn. (ICML), 1995, pp. 30–37.
[27] H. van Hasselt, Y. Doron, F. Strub, M. Hessel, N. Sonnerat, and J. Modayil, “Deep reinforcement learning and the deadly triad,” arXiv:1812.02648, Dec. 2018.
[28] T. P. Lillicrap et al., “Continuous control with deep reinforcement learning,” in Proc. Int. Conf. Learn. Represent. (ICLR), 2016.
[29] D. Silver et al., “A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play,” Science, vol. 362, no. 6419, pp. 1140–1144, 2018.
[30] D. P. Bertsekas, Rollout, Policy Iteration, and Distributed Reinforcement Learning. Belmont, MA, USA: Athena Scientific, 2020.
[31] S. Krishnan, Z. Yang, K. Goldberg, J. Hellerstein, and I. Stoica, “Learning to optimize join queries with deep reinforcement learning,” arXiv:1808.03196, 2018.
[32] R. Marcus et al., “Neo: A learned query optimizer,” Proc. VLDB Endow., vol. 12, no. 11, pp. 1705–1718, 2019.
[33] M. Korpar and M. Šikić, “SW#–GPU-enabled exact alignments on genome scale,” Bioinformatics, vol. 29, no. 19, pp. 2494–2495, 2013.
[34] Y. S. Lee, Y. S. Kim, and R. L. Uy, “Serial and parallel implementation of Needleman-Wunsch algorithm,” Int. J. Adv. Intell. Informat., vol. 6, no. 1, pp. 97–108, Mar. 2020.
[35] R. Barnes, “A review of the Smith-Waterman GPU landscape,” Dept. EECS, Univ. California, Berkeley, CA, USA, Tech. Rep. UCB/EECS-2020-152, Aug. 2020.
[36] A. Lucas, “Ising formulations of many NP problems,” Front. Phys., vol. 2, Art. no. 5, 2014.
[37] T. Kadowaki and H. Nishimori, “Quantum annealing in the transverse Ising model,” Phys. Rev. E, vol. 58, no. 5, pp. 5355–5363, 1998.
[38] M. Schönberger, I. Trummer, and W. Mauerer, “Quantum-inspired digital annealing for join ordering,” Proc. VLDB Endow., 2024.
[39] J. Preskill, “Quantum computing in the NISQ era and beyond,” Quantum, vol. 2, p. 79, 2018.
[40] W. B. Powell and S. Meisel, “Tutorial on stochastic optimization in energy—Part I: Modeling and policies,” IEEE Trans. Power Syst., vol. 31, no. 2, pp. 1459–1467, Mar. 2016.
[41] W. B. Powell and S. Meisel, “Tutorial on stochastic optimization in energy—Part II: An energy storage illustration,” IEEE Trans. Power Syst., vol. 31, no. 2, pp. 1468–1475, Mar. 2016.
[42] D. R. Jiang, T. V. Pham, W. B. Powell, D. F. Salas, and W. R. Scott, “A comparison of approximate dynamic programming techniques on benchmark energy storage problems: Does anything work?,” in Proc. IEEE Symp. Adapt. Dyn. Program. Reinforcement Learn. (ADPRL), 2014, pp. 1–8.
[43] J. Nascimento and W. B. Powell, “An optimal approximate dynamic programming algorithm for concave, scalar storage problems with vector-valued controls,” IEEE Trans. Autom. Control, vol. 58, no. 12, pp. 2995–3010, Dec. 2013.

Share your valuable work from Social Media Buttons