Regular policies in abstract dynamic programming

DOI10.1137/16M1090946MaRDI QIDQ5348471zbMATH OpenFDO

Publication date 18 August 2017

Published in SIAM Journal on Optimization (Search for Journal in Brave)

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

abstract dynamic programming discrete-time optimal control policy iteration shortest path value iteration

Existence theories for optimal control problems involving relations other than differential equations (49J21) Dynamic programming in optimal control and differential games (49L20) Dynamic programming (90C39) Markov and semi-Markov decision processes (90C40)

Abstract: We consider challenging dynamic programming models where the associated Bellman equation, and the value and policy iteration algorithms commonly exhibit complex and even pathological behavior. Our analysis is based on the new notion of regular policies. These are policies that are well-behaved with respect to value and policy iteration, and are patterned after proper policies, which are central in the theory of stochastic shortest path problems. We show that the optimal cost function over regular policies may have favorable value and policy iteration properties, which the optimal cost function over all policies need not have. We accordingly develop a unifying methodology to address long standing analytical and algorithmic issues in broad classes of undiscounted models, including stochastic and minimax shortest path problems, as well as positive cost, negative cost, risk-sensitive, and multiplicative cost problems.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Regular policies in abstract dynamic programming

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