Introduction to Stochastic Dynamic Programming

PrefaceI. Finite-Stage Models 1. Introduction 2. A Gambling Model 3. A Stock-Option Model 4. Modular Functions and Monotone Policies 5. Accepting the Best Offer 6. A Sequential Allocation Model 7. The Interchange Argument in Sequencing Problems Notes and ReferencesII. Discounted Dynamic Programming 1. Introduction 2. The Optimality Equation and Optimal Policy 3. Method of Successive Approximations 4. Policy Improvement 5. Solution by Linear Programming 6. Extension to Unbounded Rewards Problems ReferencesIII. Minimizing Costs—Negative Dynamic Programming 1. Introduction and Some Theoretical Results 2. Optimal Stopping Problems 3. Bayesian Sequential Analysis 4. Computational Approaches 5. Optimal Search Problems ReferencesIV. Maximizing Rewards—Positive Dynamic Programming 1. Introduction and Main Theoretical Results 2. Applications to Gambling Theory 3. Computational Approaches to Obtaining V Problems Notes and ReferencesV. Average Reward Criterion 1. Introduction and Counterexamples 2. Existence of an Optimal Stationary Policy 3. Computational Approaches Problems Notes and ReferencesVI. Stochastic Scheduling 1. Introduction 2. Maximizing Finite-Time Returns—Single Processor 3. Minimizing Expected Makespan—Processors in Parallel 4. Minimizing Expected Makespan—Processors in Series 5. Maximizing Total Field Life 6. A Stochastic Knapsack Model 7. A Sequential-Assignment Problem Problems Notes and ReferencesVII. Bandit Processes 1. Introduction 2. Single-Project Bandit Processes 3. Multiproject Bandit Processes 4. An Extension and a Nonextension 5. Generalizations of the Classical Bandit Problem Problems Notes and ReferencesAppendix: Stochastic Order Relations 1. Stochastically Larger 2. Coupling 3. Hazard-Rate Ordering 4. Likelihood-Ratio Ordering Problems ReferenceIndex