Affordable Access

Publisher Website

An exact iterative search algorithm for constrained Markov decision processes

Authors
Journal
Automatica
0005-1098
Publisher
Elsevier
Volume
50
Issue
5
Identifiers
DOI: 10.1016/j.automatica.2014.03.020
Keywords
  • Markov Decision Processes
  • Policy Iteration
  • Dynamic Programming
  • Constrained Optimization
Disciplines
  • Computer Science

Abstract

Abstract This communique provides an exact iterative search algorithm for the NP-hard problem of obtaining an optimal feasible stationary Markovian pure policy that achieves the maximum value averaged over an initial state distribution in finite constrained Markov decision processes. It is based on a novel characterization of the entire feasible policy space and takes the spirit of policy iteration (PI) in that a sequence of monotonically improving feasible policies is generated and converges to an optimal policy in iterations of the size of the policy space at the worst case. Unlike PI, an unconstrained MDP needs to be solved at iterations involved with feasible policies and the current best policy improves all feasible policies included in the union of the policy spaces associated with the unconstrained MDPs.

There are no comments yet on this publication. Be the first to share your thoughts.