Dynamic programming deconstructed: transformations of the Bellman equation and computational efficiency

DOI10.1287/OPRE.2020.2006MaRDI QIDQ5031647zbMATH OpenOpenAlexFDO

Authors Qingyin Ma, John Stachurski

Publication date 16 February 2022

Published in Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1811.01940

zbMATH Keywords

computational efficiencydynamic programmingMarkovoptimalityoptimization

Mathematics Subject Classification ID

Dynamic programming (90C39)

Abstract: Some approaches to solving challenging dynamic programming problems, such as Q-learning, begin by transforming the Bellman equation into an alternative functional equation, in order 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, where 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.

Recommendations

• Unbounded dynamic programming via the Q-transform
• Dynamic programming with convexity, concavity and sparsity
• The work of Richard Bellman—I. optimization
• Approximate solution of the Hamilton-Jacobi-Bellman equation
• Shape-preserving dynamic programming

Cites work

• Abstract dynamic programming
• Action Elimination Procedures for Modified Policy Iteration Algorithms
• Approximate Dynamic Programming
• Convex dynamic programming with (bounded) recursive utility
• Decision making under uncertainty. Theory and application. With contributions from Christopher Amato, Girish Chowdhary, Jonathan P. How, Hayley J. Davison Reynolds, Jason R. Thornton, Pedro A. Torres-Carrasquillo, N. Kemal Üre and John Vian
• Dynamic programming and optimal control. Vol. 2
• Finite-time bounds for fitted value iteration
• scientific article; zbMATH DE number 3126094 (Why is no real title available?)
• scientific article; zbMATH DE number 5016447 (Why is no real title available?)
• scientific article; zbMATH DE number 1099381 (Why is no real title available?)
• Optimal Replacement of GMC Bus Engines: An Empirical Model of Harold Zurcher
• Optimal Stopping in a Partially Observable Markov Process with Costly Information
• Q-learning and enhanced policy iteration in discounted dynamic programming
• Risk-averse dynamic programming for Markov decision processes
• Robust Dynamic Programming
• Robustness
• Stochastic optimal growth model with risk sensitive preferences
• The algorithm design manual
• Unique solutions for stochastic recursive utilities

Cited in

(2)

• Unbounded dynamic programming via the Q-transform
• Beating a Benchmark: Dynamic Programming May Not Be the Right Numerical Approach

Describes a project that uses

Uses Software

• Stony Brook

This page was built for publication: Dynamic programming deconstructed: transformations of the Bellman equation and computational efficiency

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5031647)