Decision Theory: An Introduction to Dynamic Programming and Sequential Decisions Book

	Preface	xi
1	Introduction	1
1.1	Mathematical Induction	1
1.2	Historical Background	2
1.3	Dynamic Programming	5
1.4	The Executioner's Tale	8
1.5	Summary	8
	Exercises	10
I	Deterministic Models	11
2	Multi-Stage Decision Problems	13
2.1	Maximizing Utilities	13
2.2	A General Model	17
2.3	Applications	19
	Exercises	25
3	Networks	27
3.1	Shortest Paths	27
3.2	Directed Networks	29
3.3	Critical Path Analysis	30
	Exercises	37
4	Further Applications	39
4.1	Discrete Actions	39
4.2	The Knapsack Problem	39
4.3	A Simple Replacement Model	42
4.4	Scheduling Problems	44
4.5	Johnson's Algorithm	45
	Exercises	49
5	Convexity	51
5.1	Convex and Concave Functions	51
5.2	Allocation Problems	56
5.3	Concave Utility Functions	60
	Exercises	64
II	Stochastic Models	67
6	Markov Systems	69
6.1	Introduction	69
6.2	Stochastic Dynamic Programming	70
6.3	Applications	72
	Exercises	78
7	Optimal Stopping	79
7.1	Introduction	79
7.2	Stopping Times and Stopping Sets	82
7.3	Applications	90
	Exercises	94
8	Special Problems	97
8.1	Introduction	97
8.2	Selling an Asset	97
8.3	The Marriage Problem	104
8.4	Prophet Inequalities	109
	Exercises	116
III	Markov Decision Processes	119
9	General Theory	121
9.1	Introduction	121
9.2	Minimizing Discounted Expectations	122
9.3	Policy Improvements	130
9.4	A Machine Replacement Model	137
10	Minimizing Average Costs	145
10.1	Introduction	145
10.2	Long-Term Average Costs	148
10.3	Extension to Infinitely Many States	153
10.4	Optimal Inventory Policies	158
11	Statistical Decisions	165
11.1	Introduction	165
11.2	Testing Statistical Hypotheses	166
11.3	The Sequential Probability Ratio Test	170
	Notes on the Exercises	177
	References	185
	Index	187