Introduction to Stochastic Dynamic Programming (eBook)

Sheldon M. Ross (Autor)

Z. W. Birnbaum, E. Lukacs (Herausgeber)

eBook Download: PDF

2014 | 1. Auflage
178 Seiten
Elsevier Science (Verlag)
978-1-4832-6909-2 (ISBN)

Infos

Introduction to Stochastic Dynamic Programming presents the basic theory and examines the scope of applications of stochastic dynamic programming. The book begins with a chapter on various finite-stage models, illustrating the wide range of applications of stochastic dynamic programming. Subsequent chapters study infinite-stage models: discounting future returns, minimizing nonnegative costs, maximizing nonnegative returns, and maximizing the long-run average return. Each of these chapters first considers whether an optimal policy need exist-providing counterexamples where appropriate-and then presents methods for obtaining such policies when they do. In addition, general areas of application are presented. The final two chapters are concerned with more specialized models. These include stochastic scheduling models and a type of process known as a multiproject bandit. The mathematical prerequisites for this text are relatively few. No prior knowledge of dynamic programming is assumed and only a moderate familiarity with probability- including the use of conditional expectation-is necessary.

Dr. Sheldon M. Ross is a professor in the Department of Industrial and Systems Engineering at the University of Southern California. He received his PhD in statistics at Stanford University in 1968. He has published many technical articles and textbooks in the areas of statistics and applied probability. Among his texts are A First Course in Probability, Introduction to Probability Models, Stochastic Processes, and Introductory Statistics. Professor Ross is the founding and continuing editor of the journal Probability in the Engineering and Informational Sciences. He is a Fellow of the Institute of Mathematical Statistics, a Fellow of INFORMS, and a recipient of the Humboldt US Senior Scientist Award.

Inhalt

Front Cover 1
Introduction to Stochastic Dynamic Programming 4
Copyright Page 5
Table of Contents 8
Dedication 6
Preface 12
Chapter I. Finite-Stage Models 14
1. Introduction 14
2. A Gambling Model 15
3. A Stock-Option Model 17
4. Modular Functions and Monotone Policies 18
5. Accepting the Best Offer 24
6. A Sequential Allocation Model 27
7. The Interchange Argument in Sequencing 30
Problems 34
Notes and References 40
Chapter II. Discounted Dynamic Programming 42
1. Introduction 42
2. The Optimality Equation and Optimal Policy 43
3. Method of Successive Approximations 48
4. Policy Improvement 51
5. Solution by Linear Programming 53
6. Extension to Unbounded Rewards 55
Problems 57
References 61
Chapter III. Minimizing Costs—Negative Dynamic Programming 62
1. Introduction and Some Theoretical Results 62
2. Optimal Stopping Problems 64
3. Bayesian Sequential Analysis 71
4. Computational Approaches 73
5. Optimal Search 76
Problems 81
References 84
Chapter IV. Maximizing Rewards—Positive Dynamic Programming 86
1. Introduction and Main Theoretical Results 86
2. Applications to Gambling Theory 89
3. Computational Approaches to Obtaining V 96
Problems 98
Notes and References 101
Chapter V. Average Reward Criterion 102
1. Introduction and Counterexamples 102
2. Existence of an Optimal Stationary Policy 106
3. Computational Approaches 111
Problems 116
Notes and References 118
Chapter VI. Stochastic Scheduling 120
1. Introduction 120
2. Maximizing Finite-Time Returns—Single Processor 121
3. Minimizing Expected Makespan—Processors in Parallel 122
4. Minimizing Expected Makespan—Processors in Series 127
5. Maximizing Total Field Life 131
6. A Stochastic Knapsack Model 135
7. A Sequential-Assignment Problem 137
Problems 140
Notes and References 142
Chapter VII. Bandit Processes 144
1. Introduction 144
2. Single-Project Bandit Processes 144
3. Multiproject Bandit Processes 146
4. An Extension and a Nonextension 156
5. Generalizations of the Classical Bandit Problem 158
Problems 163
Notes and References 164
Appendix: Stochastic Order Relations 166
1. Stochastically Larger 166
2. Coupling 167
3. Hazard-Rate Ordering 169
4. Likelihood-Ratio Ordering 170
Problems 173
Reference 174
Index 176

Produkt-Details

• Erscheint lt. Verlag: 10.7.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik ► Algebra
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Technik
• ISBN-10: 1-4832-6909-4 / 1483269094
• ISBN-13: 978-1-4832-6909-2 / 9781483269092