Article ID Journal Published Year Pages File Type
1142455 Operations Research Letters 2014 8 Pages PDF
Abstract

We study infinite-horizon nonstationary Markov decision processes with discounted cost criterion, finite state space, and side constraints. This problem can equivalently be formulated as a countably infinite linear program (CILP), a linear program with countably infinite number of variables and constraints. We provide a complete algebraic characterization of extreme points of the CILP formulation and illustrate the characterization for special cases. The existence of a KK-randomized optimal policy for a problem with KK side constraints also follows from this characterization.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , , ,