Generalized Dual Dynamic Programming for Infinite Horizon Problems in Continuous State and Action Spaces
METADATA ONLY
Loading...
Author / Producer
Date
2019-12
Publication Type
Journal Article
ETH Bibliography
yes
Citations
Altmetric
METADATA ONLY
Data
Rights / License
Abstract
We describe a nonlinear generalization of dual dynamic programming (DP) theory and its application to value function estimation for deterministic control problems over continuous state and action spaces, in a discrete-time infinite horizon setting. We prove, using a Benders-type argument leveraging the monotonicity of the Bellman operator, that the result of a one-stage policy evaluation can be used to produce nonlinear lower bounds on the optimal value function that are valid over the entire state space. These bounds contain terms reflecting the functional form of the system's costs, dynamics, and constraints. We provide an iterative algorithm that produces successively better approximations of the optimal value function, and prove under certain assumptions that it achieves an arbitrarily low desired Bellman optimality tolerance at preselected points in the state space, in a finite number of iterations. We also describe means of certifying the quality of the approximate value function generated. We demonstrate the efficacy of the approach on systems whose dimensions are too large for conventional DP approaches to be practical.
Permanent link
Publication status
published
External links
Editor
Book title
Journal / series
Volume
64 (12)
Pages / Article No.
5012 - 5023
Publisher
IEEE
Event
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
Aerospace electronics; Approximation algorithms; Cost function; Trajectory; Dynamic programming; Optimal control
Organisational unit
03751 - Lygeros, John / Lygeros, John