Table of Contents
About the author
Acknowledgement
1 Introduction
1.1 Introduction
1.2 Mathematical Models for Decision Making
1.3 Examples of Practical Applications
1.4 Python and Computational Examples
1.5 Summary of Future Chapters
1.6 Concluding Remarks
1.7 Practice Exercises
2 Decision Trees
2.1 Decision Trees
2.2 Basic Probability Concepts
2.3 Quantifying Decisions: Payoffs and Decision-Maker Perspectives
2.3.1 Quality Adjusted Life Years
2.3.2 Probability of an Event
2.3.3 Utility
2.3.4 Time Value of Rewards
2.3.5 Regret
2.4 Multi-stage Decision Trees
2.5 Expected Value of Perfect Information
2.6 Concluding Remarks
2.7 Practice Exercises
3 Deterministic Dynamic Programs
3.1 Introduction
3.2 Mathematical Formulation of Dynamic Programs
3.3 Shortest Path Problems on Directed Acyclic Networks
3.4 Production Lot-sizing
3.5 Resource Allocation
3.6 Pattern Recognition
3.7 Generalization of Shortest Path Problems to Include Cycles
3.8 Counter Example: When DP Does Not Work
3.9 Concluding Remarks
3.10 Practice Exercises
4 Markov Decision Processes
4.1 Introduction
4.2 Markov Chains
4.3 Markov Decision Processes (MDPs)
4.3.1 Estimating Computational Complexity of Policy Evaluation
4.3.2 Finding Optimal Policies Efficiently
4.3.3 Analysis of the Backward Induction Algorithm
4.3.4 Shortest Path Problem Revisited
4.4 Optimal Stopping Time Problems
4.5 Production Planning with Uncertain Demand
4.6 MDP Parameter Estimation
4.7 Infinite-Horizon MDPs
4.7.1 Policy Evaluation Over an Infinite Horizon
4.7.2 Optimality Equations for Infinite-Horizon MDPs
4.7.3 Solving the Optimality Equations for Infinite-Horizon MDPs
Value Iteration
The Reasons Value Iteration Works
Policy Iteration
The Reason Policy Iteration Works
4.8 Concluding Remarks
4.9 Practice Exercises
5 Constrained Optimization Models
5.1 Introduction
5.2 A Visual Introduction to Linear Programming Models
5.3 The Shortest Path Problem Revisited
5.4 Relationship Between Dynamic Programs and Linear Programs
5.5 Two-Stage Stochastic Linear Programs
5.5.1 The Newsvendor Problem
5.5.2 Value of the Stochastic Solution
5.5.3 Scheduling Arrivals to a Stochastic Server
5.6 Expected Value of Perfect Information (EVPI)
5.7 Concluding Remarks
5.8 Practice Exercises
6 Monte Carlo Simulation
6.1 Introduction
6.2 Curse of Dimensionality
6.3 Monte Carlo Sampling
6.3.1 Pseudo Random Number Generators
6.4 Using Monte Carlo Simulation to Estimate Expectations
6.5 Sampling a Markov Chain
6.5.1 Using Monte Carlo Simulation to Analyze MDPs
6.6 Approximating Stochastic Programs with Monte Carlo Simulation
6.6.1 Monte Carlo Sampling for Multi-Stage Stochastic Programs
6.7 Monte Carlo Sampling for MDPs
6.8 Concluding Remarks
6.9 Practice Exercises
7 Partially Observable Markov Decision Processes (POMDPs)
7.1 Introduction
7.2 Hidden Markov Models (HMMs)
7.3 HMM Parameter Estimation
7.4 POMDP Model Formulation
7.5 Solution Methods for POMDPs
7.6 Approximation Methods for POMDPs
7.7 Concluding Remarks
7.8 Practice Exercises
8 Reinforcement Learning
8.1 Introduction
8.2 Contexts and Types of Learning
8.2.1 Off-line vs. On-line Learning
8.2.2 Stationary vs. Non-stationary Environments
8.2.3 Value Iteration vs. Policy Iteration Approaches
8.2.4 On-policy vs. Off-policy Learning
8.2.5 Exploitation vs. Exploration
8.3 Greedy Monte Carlo Policy Iteration
8.3.1 Greedy Policy for Bandit Problems
8.3.2 ϵ-Greedy Approach to the Multi-Armed Bandit
8.4 Monte-Carlo Policy Iteration
8.5 Q-Learning
8.6 Concluding Remarks
8.7 Practice Exercises
9 Multi-agent Markov Decision Processes
9.1 Introduction
9.2 A Two-Agent Model: Decision Maker vs. an Adversary
9.3 Cooperative Multi-Agent Markov Decision Processes (MAMDPs)
9.3.1 Independent Cooperative Agents with No Information Sharing
9.3.2 Fully Centralized MAMDPs
9.3.3 Fully Centralized MAMDPs with Partial Observability
9.3.4 Decentralized POMDPs
9.4 Concluding Remarks
9.5 Practice Exercises
10 Approximation Methods for Large-Scale Models
10.1 Introduction
10.2 Value Function Approximations
10.2.1 Basis Function Approximations
10.2.2 Kernel-Based Approximations
10.3 Policy Iteration Based Approximation
10.3.1 Policy Approximation Methods
10.4 Concluding Remarks
10.5 Practice Exercises
A Appendix A - Mathematical Notation
A.1 Appendix B - Derivation of Newsvendor Model Optimal Solution
A.2 Appendix C - Theorem Proofs
