About the Author xi
Acknowledgments xiii
About the Companion Website xv
1 Introduction to Decision Analytics 1
1.1 Introduction 1
1.2 Mathematical Models for Decision-making 1
1.3 Examples of Practical Applications 3
1.4 Python and Computational Examples 5
1.5 Summary of Future Chapters 6
1.6 Concluding Remarks 7
1.7 Practice Exercises 7
2 Decision Trees 11
2.1 Introduction 11
2.2 Basic Probability Concepts 12
2.3 Quantifying Decisions: Payoffs and Decision-maker Perspectives 14
2.4 Multi-stage Decision Trees 17
2.5 Expected Value of Perfect Information 19
2.6 Concluding Remarks 21
2.7 Practice Exercises 21
3 Deterministic Dynamic Programs 25
3.1 Introduction 25
3.2 Mathematical Formulation of Dynamic Programs 25
3.3 Shortest Path Problems on Directed Acyclic Networks 26
3.4 Production Lot-sizing 28
3.5 Resource Allocation 31
3.6 Pattern Recognition 34
3.7 Generalization of Shortest Path Problems to Include Cycles 36
3.8 Counter Example: When DP Does Not Work 41
3.9 Concluding Remarks 42
3.10 Practice Exercises 42
4 Markov Decision Processes 47
4.1 Introduction 47
4.2 Markov Chains 47
4.3 Markov Decision Processes 49
4.4 Optimal Stopping Time Problems 56
4.5 Production Planning with Uncertain Demand 60
4.6 MDP Parameter Estimation 64
4.7 Infinite-horizon MDPs 65
4.8 Concluding Remarks 78
4.9 Practice Exercises 79
5 Constrained Optimization Models 83
5.1 Introduction 83
5.2 A Visual Introduction to Linear Programming Models 85
5.3 The Shortest Path Problem Revisited 87
5.4 Relationship Between Dynamic Programs and Linear Programs 90
5.5 Two-stage Stochastic Linear Programs 92
5.6 Expected Value of Perfect Information (EVPI) 102
5.7 Concluding Remarks 106
5.8 Practice Exercises 106
6 Monte Carlo Simulation 109
6.1 Introduction 109
6.2 Curse of Dimensionality 109
6.3 Monte Carlo Sampling 110
6.4 Using Monte Carlo Simulation to Estimate Expectations 112
6.5 Sampling a Markov Chain 114
6.6 Approximating Stochastic Programs with Monte Carlo Simulation 120
6.7 Monte Carlo Sampling for MDPs 123
6.8 Concluding Remarks 124
6.9 Practice Exercises 125
7 Partially Observable Markov Decision Processes 127
7.1 Introduction 127
7.2 Hidden Markov Models 127
7.3 HMM Parameter Estimation 129
7.4 POMDP Model Formulation 130
7.5 Solution Methods for POMDPs 131
7.6 Approximation Methods for POMDPs 135
7.7 Concluding Remarks 141
7.8 Practice Exercises 142
8 Reinforcement Learning 145
8.1 Introduction 145
8.2 Contexts and Types of Learning 146
8.3 Greedy Monte Carlo Policy Iteration 148
8.4 Monte Carlo Policy Iteration 153
8.5 Q-learning 157
8.6 Concluding Remarks 162
8.7 Practice Exercises 163
9 Multi-agent Markov Decision Processes 165
9.1 Introduction 165
9.2 A Two-agent Model: Decision-maker vs. an Adversary 165
9.3 Cooperative Multi-agent Markov Decision Processes (MAMDPs) 170
9.4 Concluding Remarks 187
9.5 Practice Exercises 187
10 Approximation Methods for Large-scale Models 191
10.1 Introduction 191
10.2 Value Function Approximations 192
10.3 Policy Iteration-based Approximation 204
10.3.1 Policy Approximation Methods 210
10.4 Concluding Remarks 212
10.5 Practice Exercises 213
References 213
Appendix 215
Index 221
