Dynamic programming deconstructed: Transformations of the bellman equation and computational efficiency

Qingyin Ma, John Stachurski

    Research output: Contribution to journalArticlepeer-review

    4 Citations (Scopus)

    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.

    Original languageEnglish
    Pages (from-to)1591-1607
    Number of pages17
    JournalOperations Research
    Volume69
    Issue number5
    DOIs
    Publication statusPublished - 1 Sept 2021

    Fingerprint

    Dive into the research topics of 'Dynamic programming deconstructed: Transformations of the bellman equation and computational efficiency'. Together they form a unique fingerprint.

    Cite this