Proper Policies in Infinite-State Stochastic Shortest Path Problems

DOI10.1109/TAC.2018.2811781MaRDI QIDQ4559523zbMATH OpenOpenAlexWikidataFDO

Authors Dimitri P. Bertsekas

Publication date 4 December 2018

Published in IEEE Transactions on Automatic Control (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Markov and semi-Markov decision processes (90C40) Optimal stochastic control (93E20)

Abstract: We consider stochastic shortest path problems with infinite state and control spaces, a nonnegative cost per stage, and a termination state. We extend the notion of a proper policy, a policy that terminates within a finite expected number of steps, from the context of finite state space to the context of infinite state space. We consider the optimal cost function $J^{\ast }$, and the optimal cost function $hatJ$ over just the proper policies. We show that $J^{\ast }$ and $hatJ$ are the smallest and largest solutions of Bellman's equation, respectively, within a suitable class of Lyapounov-like functions. If the cost per stage is bounded, these functions are those that are bounded over the effective domain of $hatJ$. The standard value iteration algorithm may be attracted to either $J^{\ast }$ or $hatJ$, depending on the initial condition.

Cited in

(2)

• Extreme Occupation Measures in Markov Decision Processes with an Absorbing State
• Improved value iteration for neural-network-based stochastic optimal control design

This page was built for publication: Proper Policies in Infinite-State Stochastic Shortest Path Problems

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