Fast Approximate Dynamic Programming for Infinite-Horizon Markov Decision Processes

In this study, we consider the infinite-horizon, discounted cost, optimal control of stochastic nonlinear systems with separable cost and constraints in the state and input variables. Using the linear-time Legendre transform, we propose a novel numerical scheme for implementation of the correspondin...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2022-03
Main Authors: Kolarijani, M A S, Max, G F, Esfahani, P Mohajerin
Format: Article
Language:English
Subjects:
Algorithms
Complexity
Conjugates
Discrete time systems
Domains
Dynamic programming
Dynamical systems
Iterative methods
Markov processes
Nonlinear dynamics
Numerical analysis
Optimal control
Optimization
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this study, we consider the infinite-horizon, discounted cost, optimal control of stochastic nonlinear systems with separable cost and constraints in the state and input variables. Using the linear-time Legendre transform, we propose a novel numerical scheme for implementation of the corresponding value iteration (VI) algorithm in the conjugate domain. Detailed analyses of the convergence, time complexity, and error of the proposed algorithm are provided. In particular, with a discretization of size \(X\) and \(U\) for the state and input spaces, respectively, the proposed approach reduces the time complexity of each iteration in the VI algorithm from \(O(XU)\) to \(O(X+U)\), by replacing the minimization operation in the primal domain with a simple addition in the conjugate domain.
ISSN:2331-8422