Further Topics on Discrete-Time Markov Control Processes

This book presents the second part of a two-volume series devoted to a sys­ tematic exposition of some recent developments in the theory of discrete­ time Markov control processes (MCPs). As in the first part, hereafter re­ ferred to as "Volume I" (see Hernandez-Lerma and Lasserre [1]), interest is mainly confined to MCPs with Borel state and control spaces, and possibly unbounded costs. However, an important feature of the present volume is that it is essentially self-contained and can be read independently of Volume I. The reason for this independence is that even though both volumes deal with similar classes of MCPs, the assumptions on the control models are usually different. For instance, Volume I deals only with nonnegative cost­ per-stage functions, whereas in the present volume we allow cost functions to take positive or negative values, as needed in some applications. Thus, many results in Volume Ion, say, discounted or average cost problems are not applicable to the models considered here. On the other hand, we now consider control models that typically re­ quire more restrictive classes of control-constraint sets and/or transition laws. This loss of generality is, of course, deliberate because it allows us to obtain more "precise" results. For example, in a very general context, in §4.

7 Ergodicity and Poisson’s Equation.- 7.1 Introduction.- 7.2 Weighted norms and signed kernels.- A. Weighted-norm spaces.- B. Signed kernels.- C. Contraction maps.- 7.3 Recurrence concepts.- A. Irreducibility and recurrence.- B. Invariant measures.- C. Conditions for irreducibility and recurrence.- D. w-Geometric ergodicity.- 7.4 Examples on w-geometric ergodicity.- 7.5 Poisson’s equation.- A. The multichain case.- B. The unichain P.E.- C. Examples.- 8 Discounted Dynamic Programming with Weighted Norms.- 8.1 Introduction.- 8.2 The control model and control policies.- 8.3 The optimality equation.- A. Assumptions.- B. The discounted-cost optimality equation.- C. The dynamic programming operator.- D. Proof of Theorem 8.3.6.- 8.4 Further analysis of value iteration.- A. Asymptotic discount optimality.- B. Estimates of VI convergence.- C. Rolling horizon procedures.- D. Forecast horizons and elimination of non-optimal actions.- 8.5 The weakly continuous case.- 8.6 Examples.- 8.7 Further remarks.- 9 The Expected Total Cost Criterion.- 9.1 Introduction.- 9.2 Preliminaries.- A. Extended real numbers.- B. Integrability.- 9.3 The expected total cost.- 9.4 Occupation measures.- A. Expected occupation measures.- B. The sufficiency problem.- 9.5 The optimality equation.- A. The optimality equation.- B. Optimality criteria.- C. Deterministic stationary policies.- 9.6 The transient case.- A. Transient models.- B. Optimality conditions.- C. Reduction to deterministic policies.- D. The policy iteration algorithm.- 10 Undiscounted Cost Criteria.- 10.1 Introduction.- A. Undiscounted criteria.- B. AC criteria.- C. Outline of the chapter.- 10.2 Preliminaries.- A. Assumptions.- B. Corollaries.- C. Discussion.- 10.3 From AC-optimality to undiscounted criteria.- A. The AC optimality inequality.- B. The AC optimality equation.- C. Uniqueness of the ACOE.- D. Bias-optimal policies.- E. Undiscounted criteria.- 10.4 Proof of Theorem 10.3.1.- A. Preliminary lemmas.- B. Completion of the proof.- 10.5 Proof of Theorem 10.3.6.- A. Proof of part (a).- B. Proof of part (b).- C. Policy iteration.- 10.6 Proof of Theorem 10.3.7.- 10.7 Proof of Theorem 10.3.10.- 10.8 Proof of Theorem 10.3.11.- 10.9 Examples.- 11 Sample Path Average Cost.- 11.1 Introduction.- A. Definitions.- B. Outline of the chapter.- 11.2 Preliminaries.- A. Positive Harris recurrence.- B. Limiting average variance.- 11.3 The w-geometrically ergodic case.- A. Optimality in IIDS.- B. Optimality in II.- C. Variance minimization.- D. Proof of Theorem 11.3.5.- E. Proof of Theorem 11.3.8.- 11.4 Strictly unbounded costs.- 11.5 Examples.- 12 The Linear Programming Approach.- 12.1 Introduction.- A. Outline of the chapter.- 12.2 Preliminaries.- A. Dual pairs of vector spaces.- B. Infinite linear programming.- C. Approximation of linear programs.- D. Tightness and invariant measures.- 12.3 Linear programs for the AC problem.- A. The linear programs.- B. Solvability of (P).- C. Absence of duality gap.- D. The Farkas alternative.- 12.4 Approximating sequences and strong duality.- A. Minimizing sequences for (P).- B. Maximizing sequences for (P*).- 12.5 Finite LP approximations.- A. Aggregation.- B. Aggregation-relaxation.- C. Aggregation-relaxion-inner approximations.- 12.6 Proof of Theorems 12.5.3, 12.5.5, 12.5.7.- References.- Abbreviations.- Glossary of notation.