  


Simplex Algorithm for Countablestate Discounted Markov Decision Processes
Ilbin Lee(ilbinleeumich.edu) Abstract: We consider discounted Markov Decision Processes (MDPs) with countablyinfinite state spaces, finite action spaces, and unbounded rewards. Typical examples of such MDPs are inventory management and queueing control problems in which there is no specific limit on the size of inventory or queue. Existing solution methods obtain a sequence of policies that converges to optimality in value but may not improve monotonically, i.e., a policy in the sequence may be worse than preceding policies. Our proposed approach considers countablyinfinite linear programming (CILP) formulations of the MDPs (a CILP is defined as a linear program (LP) with countablyinfinite numbers of variables and constraints). Under standard assumptions for analyzing MDPs with countablyinfinite state spaces and unbounded rewards, we extend the major theoretical extreme point and duality results to the resulting CILPs. Under an additional technical assumption which is satisfied by several applications of interest, we present a simplextype algorithm that is implementable in the sense that each of its iterations requires only a finite amount of data and computation. We show that the algorithm finds a sequence of policies which improves monotonically and converges to optimality in value. Unlike existing simplextype algorithms for CILPs, our proposed algorithm solves a class of CILPs in which each constraint may contain an infinite number of variables and each variable may appear in an infinite number of constraints. A numerical illustration for inventory management problems is also presented. Keywords: simplex algorithm, infinite linear programs, dynamic programming Category 1: Other Topics (Dynamic Programming ) Category 2: Linear, Cone and Semidefinite Programming (Linear Programming ) Category 3: Infinite Dimensional Optimization Citation: 11/2014 Download: [PDF] Entry Submitted: 11/18/2014 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  