Constrained Markov Decision Processes
Stochastic Modeling
1st Edition
Published on 30. March 1999
Book
Hardback
256 pages
978-0-8493-0382-1 (ISBN)
Description
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.
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.
Reviews / Votes
"...an outstanding addition to the MDPs literature and it complements...".tstanding addition to the MDPs literature and it complements...".
More details
Series
Language
English
Place of publication
Oxford
United Kingdom
Publishing group
Taylor & Francis Ltd
Target group
College/higher education
Professional and scholarly
Dimensions
Height: 229 mm
Width: 152 mm
Weight
520 gr
ISBN-13
978-0-8493-0382-1 (9780849303821)
Copyright in bibliographic data and cover images is held by Nielsen Book Services Limited or by the publishers or by their respective licensors: all rights reserved.
Schweitzer Classification
Other editions
Additional editions
Eitan Altman
Constrained Markov Decision Processes
E-Book
12/2021
1st Edition
Routledge
€251.99
Available for download
Eitan Altman
Constrained Markov Decision Processes
E-Book
12/2021
1st Edition
Routledge
€251.99
Available for download
Person
Altman, Eitan
Content
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
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