Constrained Markov Decision Processes / Edition 1

by Eitan Altman

Overview

This book provides a unified approach for the study of constrained Markov decision processes with a finite state space and unbounded costs. Unlike the single controller case considered in many other books, the author considers a single controller with several objectives, such as minimizing delays and loss, probabilities, and maximization of throughputs. It is desirable to design a controller that minimizes one cost objective, subject to inequality constraints on other cost objectives. This framework describes dynamic decision problems arising frequently in many engineering fields. A thorough overview of these applications is presented in the introduction.
The book is then divided into three sections that build upon each other.
The first part explains the theory for the finite state space. The author characterizes the set of achievable expected occupation measures as well as performance vectors, and identifies simple classes of policies among which optimal policies exist. This allows the reduction of the original dynamic into a linear program. A Lagranian approach is then used to derive the dual linear program using dynamic programming techniques.
In the second part, these results are extended to the infinite state space and action spaces. The author provides two frameworks: the case where costs are bounded below and the contracting framework.
The third part builds upon the results of the first two parts and examines asymptotical results of the convergence of both the value and the policies in the time horizon and in the discount factor. Finally, several state truncation algorithms that enable the approximation of the solution of the original control problem via finite linear programs are given.

Product Details

ISBN-13:	9780849303821
Publisher:	Taylor & Francis
Publication date:	03/30/1999
Series:	Stochastic Modeling Series , #7
Pages:	256
Product dimensions:	6.00(w) x 9.00(h) x 0.80(d)

About the Author

Altman, Eitan

Table of Contents

INTRODUCTION
Examples of Constrained Dynamic Control Problems
On Solution Approaches for CMDPs with Expected Costs
Other Types of CMDPs
Cost Criteria and Assumptions
The Convex Analytical Approach and Occupation Measures
Linear Programming and Lagrangian Approach for CMDPs
About the Methodology
The Structure of the Book
PART ONE: FINITE MDPS
MARKOV DECISION PROCESSES
The Model
Cost Criteria and the Constrained Problem
Some Notation
The Dominance of Markov Policies
THE DISCOUNTED COST
Occupation Measure and the Primal LP
Dynamic Programming and Dual LP: the Unconstrained Case
Constrained Control: Lagrangian Approach
The Dual LP
Number of Randomizations
THE EXPECTED AVERAGE COST
Occupation Measure and the Primal LP
Equivalent Linear Program
The Dual Program
Number of Randomizations
FLOW AND SERVICE CONTROL IN A SINGLE-SERVER QUEUE
The Model
The Lagrangian
The Original Constrained Problem
Structure of Randomization and Implementation Issues
On Coordination Between Controllers
Open Questions
PART TWO: INFINITE MDPS
MDPS WITH INFINITE STATE AND ACTION SPACES
The Model
Cost Criteria
Mixed Policies, and Topologic Structures
The Dominance of Markov Policies
Aggregation of States
Extra Randomization in the Policies
Equivalent Quasi-Markov Model and Quasi-Markov Policies
THE TOTAL COST: CLASSIFICATION OF MDPS
Transient and Absorbing MDPs
MDPs With Uniform Lyapunov Functions
Equivalence of MDP With Unbounded and bounded costs
Properties of MDPs With Uniform Lyapunov Functions
Properties for Fixed Initial Distribution
Examples of Uniform Lyapunov Functions
Contracting MDPs
THE TOTAL COST: OCCUPATION MEASURES AND THE PRIMAL LP
Occupation Measure
Continuity of Occupation Measures
More Properties of MDPs
Characterization of Achievable Sets of Occupation Measure
Relation Between Cost and Occupation Measure
Dominating

Editorial Reviews

"…an outstanding addition to the MDPs literature and it complements…".

tstanding addition to the MDPs literature and it complements…".

From the Publisher

Presents a unified approach to the study of constrained Markov decision processes. The author considers a controller with several objectives, which results in the design of a controller that minimizes one cost objective, subject to inequality constraints on others. Following an overview, 16 chapters discuss finite and infinite MDPs as well as asymptotic methods and approximations. They feature a thorough analysis of all standard cost criteria, consideration of unbounded cost, an explanation of numerical solution methods for infinite state problems, and previously unpublished results. Annotation c. by Book News, Inc., Portland, Or.

Booknews