Optimization Online


Simplex Algorithm for Countable-state Discounted Markov Decision Processes

Ilbin Lee(ilbinlee***at***umich.edu)
Marina A. Epelman(mepelman***at***umich.edu)
H. Edwin Romeijn(romeijn***at***umich.edu)
Robert L. Smith(rlsmith***at***umich.edu)

Abstract: We consider discounted Markov Decision Processes (MDPs) with countably-infinite 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 countably-infinite linear programming (CILP) formulations of the MDPs (a CILP is defined as a linear program (LP) with countably-infinite numbers of variables and constraints). Under standard assumptions for analyzing MDPs with countably-infinite 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 simplex-type 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 simplex-type 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
Entry Accepted: 11/18/2014
Entry Last Modified: 11/18/2014

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society