ÍNDICE

List of Figures ......................................................... ix
List of Tables ......................................................... xi
Preface ................................................................. xiii
Acknowledgments ......................................................... xv

1. INTRODUCTION ............................................................. 1

1.1 A Brief Description of Markov Decision Processes ......................... 1
1.2 Overview of the Book ..................................................... 4
1.3 Organization of the Book ................................................. 6

2. DISCRETE TIME MARKOV DECISION PROCESSES: TOTAL REWARD ............... 11

2.1 Model and Preliminaries .................................................. 11
  2.1.1 System Model ........................................................ 11
  2.1.2 Some Concepts ....................................................... 12
  2.1.3 Finiteness of the Reward ............................................ 14
2.2 Optimality Equation ...................................................... 17
  2.2.1 Validity of the Optimality Equation .................................. 17
  2.2.2 Properties of the Optimality Equation ................................ 21
2.3 Properties of Optimal Policies ............................................ 25
2.4 Successive Approximation .................................................. 30
2.5 Sufficient Conditions ..................................................... 32
2.6 Notes and References ...................................................... 34

3. DISCRETE TIME MARKOV DECISION PROCESSES: AVERAGE CRITERION .......... 39

3.1 Model and Preliminaries ................................................... 39
3.2 Optimality Equation ....................................................... 43
  3.2.1 Properties of ACOE and Optimal Policies ............................. 44
  3.2.2 Sufficient Conditions ................................................ 48
  3.2.3 Recurrent Conditions ................................................ 50
3.3 Optimality Inequalities .................................................... 53
  3.3.1 Conditions .......................................................... 54
  3.3.2 Properties of ACOI and Optimal Policies ............................. 57
3.4 Notes and References ...................................................... 60

4. CONTINUOUS TIME MARKOV DECISION PROCESSES ............................ 63

4.1 A Stationary Model: Total Reward .......................................... 63
  4.1.1 Model and Conditions ................................................. 63
  4.1.2 Model Decomposition .................................................. 67
  4.1.3 Some Properties ...................................................... 71
  4.1.4 Optimality Equation and Optimal Policies ............................. 77
4.2 A Nonstationary Model: Total Reward ....................................... 85
  4.2.1 Model and Conditions ................................................. 85
  4.2.2 Optimality Equation .................................................. 87
4.3 A Stationary Model: Average Criterion ..................................... 95
4.4 Notes and References ...................................................... 101

5. SEMI-MARKOV DECISION PROCESSES ........................................ 105

5.1 Model and Conditions ...................................................... 105
  5.1.1 Model ............................................................... 105
  5.1.2 Regular Conditions ................................................... 107
  5.1.3 Criteria ............................................................ 110
5.2 Transformation ............................................................ 111
  5.2.1 Total Reward ........................................................ 112
  5.2.2 Average Criterion ................................................... 115
5.3 Notes and References ...................................................... 119

6. MARKOV DECISION PROCESSES IN SEMI-MARKOV ENVIRONMENTS ............... 121

6.1 Continuous Time MDP in Semi-Markov Environments .......................... 121
  6.1.1 Model ............................................................... 121
  6.1.2 Optimality Equation .................................................. 127
  6.1.3 Approximation by Weak Convergence .................................... 137
  6.1.4 Markov Environment .................................................. 140
  6.1.5 Phase Type Environment ............................................... 143
6.2 SMDP in Semi-Markov Environments .......................................... 148
  6.2.1 Model ............................................................... 148
  6.2.2 Optimality Equation .................................................. 152
  6.2.3 Markov Environment .................................................. 158
6.3 Mixed MDP in Semi-Markov Environments ..................................... 160
  6.3.1 Model ............................................................... 160
  6.3.2 Optimality Equation .................................................. 163
  6.3.3 Markov Environment .................................................. 170
6.4 Notes and References ...................................................... 174

7. OPTIMAL CONTROL OF DISCRETE EVENT SYSTEMS: I ........................ 177

7.1 System Model .............................................................. 177
7.2 Optimality ............................................................... 180
  7.2.1 Maximum Discounted Total Reward ...................................... 182
  7.2.2 Minimum Discounted Total Reward ...................................... 186
7.3 Optimality in Event Feedback Control ...................................... 186
7.4 Link to Logic Level ....................................................... 189
7.5 Resource Allocation System ................................................ 194
7.6 Notes and References ...................................................... 201

8. OPTIMAL CONTROL OF DISCRETE EVENT SYSTEMS: II ......................... 203

8.1 System Model .............................................................. 203
8.2 Optimality Equation and Optimal Supervisors ............................... 207
8.3 Language Properties ....................................................... 213
8.4 System Based on Automaton ................................................. 215
8.5 Supervisory Control Problems .............................................. 218
  8.5.1 Event Feedback Control ............................................... 218
  8.5.2 State Feedback Control ............................................... 222
8.6 Job-Matching Problem ...................................................... 223
8.7 Notes and References ...................................................... 230

9. OPTIMAL REPLACEMENT UNDER STOCHASTIC ENVIRONMENTS .................... 233

9.1 Optimal Replacement: Discrete Time ........................................ 234
  9.1.1 Problem and Model .................................................... 234
  9.1.2 Total Cost Criterion ................................................. 238
  9.1.3 Average Criterion .................................................... 241
9.2 Optimal Replacement: Semi-Markov Processes ................................. 244
  9.2.1 Problem ............................................................. 244
  9.2.2 Optimal Control Limit Policies ....................................... 247
  9.2.3 Markov Environment ................................................... 250
  9.2.4 Numerical Example .................................................... 258
9.3 Notes and References ....................................................... 260

10. OPTIMAL ALLOCATION IN SEQUENTIAL ONLINE AUCTIONS ..................... 265

10.1 Problem and Model ......................................................... 265
10.2 Analysis for Private Reserve Price ........................................ 267
10.3 Analysis for Announced Reserve Price ...................................... 271
10.4 Monotone Properties ....................................................... 273
10.5 Numerical Results ......................................................... 282
10.6 Notes and References ...................................................... 284

References ................................................................. 287
Index ..................................................................... 295