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.

Autorentext

Eitan Altman (INRIA, Valbonne, Cedex, France)

Inhalt

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