[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

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

Published: 08 February 2021 Publication History

Abstract

Transforming Dynamic Optimization Problems for Enhanced Computational Efficiency

Abstract

Dynamic programming is one of the core algorithms for solving optimization problems in operations research, economics, finance, computer science, and numerous other fields. Although the theory itself is relatively straightforward, implementation can be computationally expensive, inhibiting application to interesting and realistic problems. This research considers a variety of transformations that can be applied to optimization problems and the key equations associated with the dynamic programming algorithm. It investigates the range of possible transformations, clarifies their links with optimality, and applies specific transformations to generate large speed gains in high-dimensional problems. Several economic applications are considered.

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.

References

[1]
Bagger J, Fontaine F, Postel-Vinay F, Robin JM (2014) Tenure, experience, human capital, and wages: A tractable equilibrium search model of wage dynamics. Amer. Econom. Rev. 104(6):1551–1596.
[2]
Bäuerle N, Jaśkiewicz A (2018) Stochastic optimal growth model with risk sensitive preferences. J. Econom. Theory 173:181–200.
[3]
Bellman R (1957) Dynamic Programming (Princeton University Press, New York).
[4]
Bertsekas DP (2012) Dynamic Programming and Optimal Control , vol. 2, 4th ed. (Athena Scientific, Massachusetts).
[5]
Bertsekas DP (2013) Abstract Dynamic Programming (Athena Scientific, Belmont, MA).
[6]
Bertsekas DP, Yu H (2012) Q-learning and enhanced policy iteration in discounted dynamic programming. Math. Oper. Res. 37(1):66–94.
[7]
Bidder RM, Smith ME (2012) Robust animal spirits. J. Monetary Econom. 59(8):738–750.
[8]
Bloise G, Vailakis Y (2018) Convex dynamic programming with (bounded) recursive utility. J. Econom. Theory 173:118–141.
[9]
Dixit AK, Pindyck RS (1994) Investment Under Uncertainty (Princeton University Press, Princeton, NJ).
[10]
Hansen LP, Sargent TJ (2008) Robustness (Princeton University Press, Princeton, NJ).
[11]
Iyengar GN (2005) Robust dynamic programming. Math. Oper. Res. 30(2):257–280.
[12]
Kellogg R (2014) The effect of uncertainty on investment: Evidence from Texas oil drilling. Amer. Econom. Rev. 104(6):1698–1734.
[13]
Kochenderfer MJ (2015) Decision Making Under Uncertainty: Theory and Application (MIT Press, Cambridge, MA).
[14]
Kristensen D, Mogensen P, Moon JM, Schjerning B (2018) Solving dynamic discrete choice models using smoothing and sieve methods. Technical report, University of Copenhagen, Copenhagen.
[15]
Livshits I, MacGee J, Tertilt M (2007) Consumer bankruptcy: A fresh start. Amer. Econom. Rev. 97(1):402–418.
[16]
Low H, Meghir C, Pistaferri L (2010) Wage risk and employment risk over the life cycle. Amer. Econom. Rev. 100(4):1432–1467.
[17]
Marinacci M, Montrucchio L (2010) Unique solutions for stochastic recursive utilities. J. Econom. Theory 145(5):1776–1804.
[18]
McCall JJ (1970) Economics of information and job search. Quart. J. Econom. 84(1):113–126.
[19]
Monahan GE (1980) Optimal stopping in a partially observable Markov process with costly information. Oper. Res. 28(6):1319–1334.
[20]
Munos R, Szepesvári C (2008) Finite-time bounds for fitted value iteration. J. Machine Learn. Res. 9(May):815–857.
[21]
Peskir G, Shiryaev A (2006) Optimal Stopping and Free-Boundary Problems (Springer, Berlin).
[22]
Powell WB (2007) Approximate Dynamic Programming: Solving the Curses of Dimensionality (John Wiley & Sons, Hoboken, NJ).
[23]
Puterman ML, Shin MC (1982) Action elimination procedures for modified policy iteration algorithms. Oper. Res. 30(2):301–318.
[24]
Rust J (1987) Optimal replacement of GMC bus engines: An empirical model of Harold Zurcher. Econometrica 55(5):999–1033.
[25]
Rust J (1994) Structural estimation of Markov decision processes. Engle RF, McFadden DL, eds. Handbook of Econometrics, vol. 4 (Elsevier, Amsterdam), 3081–3143.
[26]
Rust J (1996) Numerical dynamic programming in economics. Amman H, Kendrick D, Rust J. Handbook of Computational Economics, vol. 1 (Elsevier, North-Holland, Amsterdam), 619–729.
[27]
Ruszczyński A (2010) Risk-averse dynamic programming for Markov decision processes. Math. Programming 125(2):235–261.
[28]
Skiena SS (2008) The Algorithm Design Manual (Springer, London).
[29]
Tauchen G (1986) Finite state Markov-chain approximations to univariate and vector autoregressions. Econom. Lett. 20(2):177–181.

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Operations Research
Operations Research  Volume 69, Issue 5
September-October 2021
306 pages
ISSN:0030-364X
DOI:10.1287/opre.2021.69.issue-5
Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 08 February 2021
Accepted: 03 January 2020
Received: 24 January 2019

Author Tag

  1. dynamic programming: Markov

Author Tag

  1. Optimization

Author Tags

  1. dynamic programming
  2. optimality
  3. computational efficiency

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 0
    Total Downloads
  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 21 Dec 2024

Other Metrics

Citations

View Options

View options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media