Controlled Markov Processes

This book is devoted to the systematic exposition of the contemporary theory of controlled Markov processes with discrete time parameter or in another termi­ nology multistage Markovian decision processes. We discuss the applications of this theory to various concrete problems. Particular attention is paid to mathe­ matical models of economic planning, taking account of stochastic factors. The authors strove to construct the exposition in such a way that a reader interested in the applications can get through the book with a minimal mathe­ matical apparatus. On the other hand, a mathematician will find, in the appropriate chapters, a rigorous theory of general control models, based on advanced measure theory, analytic set theory, measurable selection theorems, and so forth. We have abstained from the manner of presentation of many mathematical monographs, in which one presents immediately the most general situation and only then discusses simpler special cases and examples. Wishing to separate out difficulties, we introduce new concepts and ideas in the simplest setting, where they already begin to work. Thus, before considering control problems on an infinite time interval, we investigate in detail the case of the finite interval. Here we first study in detail models with finite state and action spaces-a case not requiring a departure from the realm of elementary mathematics, and at the same time illustrating the most important principles of the theory.

I: Control on a Finite Time Interval.- Chaper 1. Finite and Denumerable Models.- §1. Deterministic Controlled Processes.- §2. Controlled Markov Processes and Models.- §3. Strategies.- §4. Existence of a Uniformly Optimal Strategy. Combination of Strategies.- §5. The Derived Model. The Fundamental Equation.- §6. Reduction of the Problem of Optimal Control to the Analogous Problem for the Derived Model.- §7. The Optimality Equations. Construction of Simple Optimal Strategies.- §8. The Markov Property.- §9. The Dynamic Programming Principle.- §10. The Bus, Streetcar, or Walk Problem.- §11. The Replacement Problem.- §12. Countable Models: Optimality Equations and ?-Optimal Strategies.- §13. Countable Models: Sufficiency of Simple Strategies.- 2. Semicontinuous Models.- §1. On the Concept of Measurability.- §2. The General Definition of a Model.- §3. Is It Possible to Extend to General Models the Methods Applied in the Study of Finite and Countable Models?.- §4. Definition of a Semicontinuous Model.- §5. Optimality Equations and Simple Optimal Strategies.- §6. Theorems on Measurable Selection.- §7. The Model for Allocation of a Resource Between Production and Consumption.- §8. The Water Regulation Problem.- §9. The Problem of the Allocation of Stakes.- §10. The Problem of Allocation of a Resource Among Consumption and Several Productive Sectors.- §11. The Stabilization Problem.- 3. General (Borel) Models.- §1. Introduction. The Main Results.- §2. Proof of Main Results: Outline.- §3. The Space of Probability Measures.- §4. Measures on Product Spaces and Transition Functions.- §5. Strategic Measures.- §6. Universal Measurability of the Value of the Model and Almost-Surely (a.s.) ?-Optimal Strategies.- §7. The Optimality Equations.- §8. Sufficiency of the Simple Strategies.- §9. Simple a.s. ?-Optimal Strategies.- II: Control on an Infinite Time Interval.- 4. Discrete Models.- §1. Passage to an Infinite Interval of Control.- §2. Summable Models.- §3. The Fundamental Equation.- §4. Uniformly ?-Optimal Strategies.- §5. Optimality Equations.- §6. An Expression for the Value of a Model.- §7. Simple ?-Optimal Strategies.- §8. Sufficiency of Markov and Simple Strategies.- 5. Borel Models.- §1. The Main Results:.- §2. Extensions of the Results of Chapter 4 to Borel Models.- §3. Proofs of the Main Results.- §4. Measures on Infinite Products.- §5. Universal Measurability of the Value of a Model and the Existence of a.s. ?-Optimal Strategies.- §6. Semicontinuous Models.- 6. Homogeneous Models.- §1. Introduction.- §2. Application of the Results of Chapter 4.- §3. Stationary Optimal Strategies.- §4. The Bus, Streetcar, or Walk Problem.- §5. The Replacement Problem.- §6. Stationary ?-Optimal Strategies.- §7. Extensions of the Results to Borel Models.- §8. Stationary a.s. ?-Optimal Strategies.- §9. Allocation of a Resource Between Production and Consumption.- §10. The Problem of Allocation of Stakes.- §11. Allocation of a Resource Among Consumption and Several Productive Sectors.- §12. The Stabilization Problem.- 7. Maximization of the Average Reward Per Unit Time.- §1. Introduction. Canonical Strategies.- §2. Canonical Equations.- §3. Solution of the Howard Equations.- §4. Modification of the Canonical Equations.- §5. Howard’s Strategy Improvement Procedure.- §6. Asymptotics of the Discounted Reward.- §7. Increase of the Discounted Reward with the Howard Improvement.- §8. Extension to Infinite Models.- §9. Canonical and ?-Canonical Triples and Systems for General Models.- §10. Models with Minorants.- §11. The Replacement Problem.- §12. The Stabilization Problem.- §13. Models with Finitely Many States and Infinite Action Sets.- III: Some Applications.- 8. Models with Incomplete Information.- §1. Description of the Model.- §2. Reduction to a Model with Complete Information. The Finite Case.- §3. The Two-Armed Bandit Problem.- §4. Reduction to a Model with Complete Information. The General Case.- §5. The Stabilization Problem.- 9. Concave Models. Models of Economic Development.- §1. The Gale Model.- §2. Concave Models.- §3. The Spaces ?.- §4. Stimulating Prices.- §5. The Existence of Stimulating Prices.- Appendix 1: Borel Spaces.- §1. Introduction.- §2. Imbedding of a Borel Space into the Hilbert Cube.- §3. Imbedding of the Space of Dyadic Sequences into an Uncountable Borel Space.- §4. Imbedding of the Hilbert Cube into the Space of Dyadic Sequences.- Appendix 2: Analytic Sets.- §1. Introduction.- §2. The A-Operation.- §3. Universal Measurability of Analytic Sets.- §4. Separability of Analytic Sets.- §5. Example of a Nonmeasurable Analytic Set.- Appendix 3: Theorems on Measurable Selection.- §1. The Lemma of Yankov.- §2. The Theorem of Blackwell and Ryll-Nardzewski.- §3. Example of a Correspondence Not Admitting a Measurable Selection.- Appendix 4: Conditional Distributions.- §1. Introduction.- §2. Conditional Mathematical Expectations.- §3. Support Systems.- §4. Existence of Conditional Distributions.- Appendix 5: Some Lemmas on Measurability.- §1. The Lemma on Multiplicative Systems.- §2. Measurable Structure in the Space of Probability Measures.- Historical-Bibliographical Notes.