Dynamic Programming Deconstructed: Transformations of the Bellman Equation and Computational Efficiency

Qingyin Ma () and John Stachurski ()
Additional contact information
Qingyin Ma: International School of Economics and Management, Capital University of Economics and Business, Beijing 100070, China
John Stachurski: Research School of Economics, Australian National University, Acton, ACT 2601, Australia

Operations Research, 2021, vol. 69, issue 5, 1591-1607

Abstract: Some approaches to solving challenging dynamic programming problems, such as Q-learning, begin by transforming the Bellman equation into an alternative functional equation to open up a new line of attack. Our paper studies this idea systematically with a focus on boosting computational efficiency. We provide a characterization of the set of valid transformations of the Bellman equation, for which validity means that the transformed Bellman equation maintains the link to optimality held by the original Bellman equation. We then examine the solutions of the transformed Bellman equations and analyze correspondingly transformed versions of the algorithms used to solve for optimal policies. These investigations yield new approaches to a variety of discrete time dynamic programming problems, including those with features such as recursive preferences or desire for robustness. Increased computational efficiency is demonstrated via time complexity arguments and numerical experiments.

Keywords: dynamic programming: Markov; Optimization; dynamic programming; optimality; computational efficiency (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2020.2006 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:69:y:2021:i:5:p:1591-1607

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().