Ebook: Handbook of Markov Decision Processes: Methods and Applications

Eugene A. Feinberg Adam Shwartz This volume deals with the theory of Markov Decision Processes (MDPs) and their applications. Each chapter was written by a leading expert in the re­ spective area. The papers cover major research areas and methodologies, and discuss open questions and future research directions. The papers can be read independently, with the basic notation and concepts ofSection 1.2. Most chap­ ters should be accessible by graduate or advanced undergraduate students in fields of operations research, electrical engineering, and computer science. 1.1 AN OVERVIEW OF MARKOV DECISION PROCESSES The theory of Markov Decision Processes-also known under several other names including sequential stochastic optimization, discrete-time stochastic control, and stochastic dynamic programming-studiessequential optimization ofdiscrete time stochastic systems. The basic object is a discrete-time stochas­ tic system whose transition mechanism can be controlled over time. Each control policy defines the stochastic process and values of objective functions associated with this process. The goal is to select a "good" control policy. In real life, decisions that humans and computers make on all levels usually have two types ofimpacts: (i) they cost orsavetime, money, or other resources, or they bring revenues, as well as (ii) they have an impact on the future, by influencing the dynamics. In many situations, decisions with the largest immediate profit may not be good in view offuture events. MDPs model this paradigm and provide results on the structure and existence of good policies and on methods for their calculation.

---

The theory of Markov Decision Processes - also known under several other names including sequential stochastic optimization, discrete-time stochastic control, and stochastic dynamic programming - studies sequential optimization of discrete time stochastic systems. Fundamentally, this is a methodology that examines and analyzes a discrete-time stochastic system whose transition mechanism can be controlled over time. Each control policy defines the stochastic process and values of objective functions associated with this process. Its objective is to select a "good" control policy. In real life, decisions that humans and computers make on all levels usually have two types of impacts: (i) they cost or save time, money, or other resources, or they bring revenues, as well as (ii) they have an impact on the future, by influencing the dynamics. In many situations, decisions with the largest immediate profit may not be good in view of future events. Markov Decision Processes (MDPs) model this paradigm and provide results on the structure and existence of good policies and on methods for their calculations.
MDPs are attractive to many researchers because they are important both from the practical and the intellectual points of view. MDPs provide tools for the solution of important real-life problems. In particular, many business and engineering applications use MDP models. Analysis of various problems arising in MDPs leads to a large variety of interesting mathematical and computational problems. Accordingly, the Handbook of Markov Decision Processes is split into three parts: Part I deals with models with finite state and action spaces and Part II deals with infinite state problems, and Part III examines specific applications. Individual chapters are written by leading experts on the subject.

---

The theory of Markov Decision Processes - also known under several other names including sequential stochastic optimization, discrete-time stochastic control, and stochastic dynamic programming - studies sequential optimization of discrete time stochastic systems. Fundamentally, this is a methodology that examines and analyzes a discrete-time stochastic system whose transition mechanism can be controlled over time. Each control policy defines the stochastic process and values of objective functions associated with this process. Its objective is to select a "good" control policy. In real life, decisions that humans and computers make on all levels usually have two types of impacts: (i) they cost or save time, money, or other resources, or they bring revenues, as well as (ii) they have an impact on the future, by influencing the dynamics. In many situations, decisions with the largest immediate profit may not be good in view of future events. Markov Decision Processes (MDPs) model this paradigm and provide results on the structure and existence of good policies and on methods for their calculations.
MDPs are attractive to many researchers because they are important both from the practical and the intellectual points of view. MDPs provide tools for the solution of important real-life problems. In particular, many business and engineering applications use MDP models. Analysis of various problems arising in MDPs leads to a large variety of interesting mathematical and computational problems. Accordingly, the Handbook of Markov Decision Processes is split into three parts: Part I deals with models with finite state and action spaces and Part II deals with infinite state problems, and Part III examines specific applications. Individual chapters are written by leading experts on the subject.
Content:
Front Matter....Pages i-viii
Introduction....Pages 1-17
Front Matter....Pages 19-19
Finite State and Action MDPS....Pages 21-87
Bias Optimality....Pages 89-111
Singular Perturbations of Markov Chains and Decision Processes....Pages 113-150
Front Matter....Pages 151-151
Average Reward Optimization Theory for Denumerable State Spaces....Pages 153-171
Total Reward Criteria....Pages 173-207
Mixed Criteria....Pages 209-229
Blackwell Optimality....Pages 231-267
The Poisson Equation for Countable Markov Chains: Probabilistic Methods and Interpretations....Pages 269-303
Stability, Performance Evaluation, and Optimization....Pages 305-346
Convex Analytic Methods in Markov Decision Processes....Pages 347-375
The Linear Programming Approach....Pages 377-407
Invariant Gambling Problems and Markov Decision Processes....Pages 409-428
Front Matter....Pages 429-429
Neuro-Dynamic Programming: Overview and Recent Trends....Pages 431-459
Markov Decision Processes in Finance and Dynamic Options....Pages 461-487
Applications of Markov Decision Processes in Communication Networks....Pages 489-536
Water Reservoir Applications of Markov Decision Processes....Pages 537-558
Back Matter....Pages 559-565

---

The theory of Markov Decision Processes - also known under several other names including sequential stochastic optimization, discrete-time stochastic control, and stochastic dynamic programming - studies sequential optimization of discrete time stochastic systems. Fundamentally, this is a methodology that examines and analyzes a discrete-time stochastic system whose transition mechanism can be controlled over time. Each control policy defines the stochastic process and values of objective functions associated with this process. Its objective is to select a "good" control policy. In real life, decisions that humans and computers make on all levels usually have two types of impacts: (i) they cost or save time, money, or other resources, or they bring revenues, as well as (ii) they have an impact on the future, by influencing the dynamics. In many situations, decisions with the largest immediate profit may not be good in view of future events. Markov Decision Processes (MDPs) model this paradigm and provide results on the structure and existence of good policies and on methods for their calculations.
MDPs are attractive to many researchers because they are important both from the practical and the intellectual points of view. MDPs provide tools for the solution of important real-life problems. In particular, many business and engineering applications use MDP models. Analysis of various problems arising in MDPs leads to a large variety of interesting mathematical and computational problems. Accordingly, the Handbook of Markov Decision Processes is split into three parts: Part I deals with models with finite state and action spaces and Part II deals with infinite state problems, and Part III examines specific applications. Individual chapters are written by leading experts on the subject.
Content:
Front Matter....Pages i-viii
Introduction....Pages 1-17
Front Matter....Pages 19-19
Finite State and Action MDPS....Pages 21-87
Bias Optimality....Pages 89-111
Singular Perturbations of Markov Chains and Decision Processes....Pages 113-150
Front Matter....Pages 151-151
Average Reward Optimization Theory for Denumerable State Spaces....Pages 153-171
Total Reward Criteria....Pages 173-207
Mixed Criteria....Pages 209-229
Blackwell Optimality....Pages 231-267
The Poisson Equation for Countable Markov Chains: Probabilistic Methods and Interpretations....Pages 269-303
Stability, Performance Evaluation, and Optimization....Pages 305-346
Convex Analytic Methods in Markov Decision Processes....Pages 347-375
The Linear Programming Approach....Pages 377-407
Invariant Gambling Problems and Markov Decision Processes....Pages 409-428
Front Matter....Pages 429-429
Neuro-Dynamic Programming: Overview and Recent Trends....Pages 431-459
Markov Decision Processes in Finance and Dynamic Options....Pages 461-487
Applications of Markov Decision Processes in Communication Networks....Pages 489-536
Water Reservoir Applications of Markov Decision Processes....Pages 537-558
Back Matter....Pages 559-565
....