Decision Processes in Dynamic Probabilistic Systems

'Et moi •...• si j'avait su comment en revenir. One service mathematics has rendered the je n'y serais point aile: human race. It has put common sense back where it belongs. on the topmost shelf next Jules Verne (0 the dusty canister labelled 'discarded non­ sense'. The series is divergent; therefore we may be able to do something with it. Eric T. Bell O. Heaviside Mathematics is a tool for thought. A highly necessary tool in a world where both feedback and non­ linearities abound. Similarly, all kinds of parts of mathematics serve as tools for other parts and for other sciences. Applying a simple rewriting rule to the quote on the right above one finds such statements as: 'One service topology has rendered mathematical physics .. .'; 'One service logic has rendered com­ puter science .. .'; 'One service category theory has rendered mathematics .. .'. All arguably true. And all statements obtainable this way form part of the raison d'etre of this series.

1 Semi-Markov and Markov Chains.- 1.1 Definitions and basic properties.- 1.1.1 Discrete time semi-Markov and Markov behaviour of systems.- 1.1.2 Multi-step transition probability.- 1.1.3 Semi-Markov processes.- 1.1.4 State occupancy and waiting-time statistics.- 1.1.5 Non-homogeneous Markov processes.- 1.1.6 The limit theorem.- 1.1.7 Effect of small deviations in the transition probability matrix.- 1.1.7.1 Limits of some important characteristics for Markov chains.- 1.2 Algebraic and analytical methods in the study of Markovian systems.- 1.2.1 Eigenvalues and eigenvectors.- 1.2.2 Stochastic matrices.- 1.2.3 Perron-Frobenius theorem.- 1.2.4 The Geometric transformation (the z-transform).- 1.2.5 Exponential transformation (Laplace transform).- 1.3 Transient and recurrent processes.- 1.3.1 Transient processes.- 1.3.2 The study of recurrent state occupancy in Markov processes.- 1.4 Markovian populations.- 1.4.1 Vectorial processes with a Markovian structure.- 1.4.2 General branching processes.- 1.5 Partially observable Markov chains.- 1.5.1 The core process.- 1.5.2 The observation process.- 1.5.3 The state of knowledge and its dynamics.- 1.5.4 Examples.- 1.6 Rewards and discounting.- 1.6.1 Rewards for sequential decision processes.- 1.6.2 Rewards in decision processes with Markov structure.- 1.6.3 Markovian decision processes with and without discounting.- 1.7 Models and applications.- 1.7.1 Real systems with a Markovian structure.- 1.7.2 Model formulation and practical results.- 1.7.2.1 A semi-Markov model for hospital planning.- 1.7.2.2 System reliability.- 1.7.2.3 A Markovian interpretation for PERT networks.- 1.8 Dynamic-decision models for clinical diagnosis.- 1.8.1 Pattern recognition.- 1.8.2 Model optimization.- 2 Dynamic and Linear Programming.- 2.1 Discrete dynamic programming.- 2.2 A linear programming formulation and an algorithm for computation.- 2.2.1 A general formulation for the LP problem and the Simplex method.- 2.2.2 Linear programming - a matrix formulation.- 3 Utility Functions and Decisions under Risk.- 3.1 Informational lotteries and axioms for utility functions.- 3.2 Exponential utility functions.- 3.3 Decisions under risk and uncertainty; event trees.- 3.4 Probability encoding.- 4 Markovian Decision Processes (Semi-Markov and Markov) with Complete Information (Completely Observable).- 4.1 Value iteration algorithm (the finite horizon case).- 4.1.1. Semi-Markov decision processes.- 4.1.2 Markov decision processes.- 4.2 Policy iteration algorithm (the finite horizon optimization).- 4.2.1 Semi-Markov decision processes.- 4.2.2 Markov decision processes.- 4.3 Policy iteration with discounting.- 4.3.1 Semi-Markov decision processes.- 4.3.2 Markov decision processes.- 4.4 Optimization algorithm using linear programming.- 4.4.1 Semi-Markov decision process.- 4.4.2 Markov decision processes.- 4.5 Risk-sensitive decision processes.- 4.5.1 Risk-sensitive finite horizon Markov decision processes.- 4.5.2 Risk-sensitive infinite horizon Markov decision processes.- 4.5.3 Risk-sensitive finite horizon semi-Markov decision processes.- 4.5.4 Risk-sensitive infinite horizon semi-Markov decision processes.- 4.6 On eliminating sub-optimal decision alternatives in Markov and semi-Markov decision processes.- 4.6.1 Markov decision processes.- 4.6.2 Semi-Markov decision processes with finite horizon.- 5 Partially Observable Markovian Decision Processes.- 5.1 Finite horizon partially observable Markov decision processes.- 5.2 The infinite horizon with discounting for partially observable Markov decision processes.- 5.2.1 Model formulation.- 5.2.2 The concept of finitely transient policies.- 5.2.3 The function C(?|?) approximated as a Markov process with a finite number of states.- 5.3 A useful policy iteration algorithm, for discounted (? < 1) partially observable Markov decision processes.- 5.3.1 The case v for N = 2.- 5.3.2 The case v for N > 2.- 5.4 The infinite horizon without discounting for partially observable Markov processes.- 5.4.1 Model formulations.- 5.4.2 Cost of a stationary policy.- 5.4.3 Policy improvement phase.- 5.4.4 Policy iteration algorithm.- 5.5 Partially observable semi-Markov decision processes.- 5.5.1 Model formulation.- 5.5.2 State dynamics.- 5.5.3 The observation space.- 5.5.4 Overall system dynamics.- 5.5.5 Decision alternatives in clinical disorders.- 5.6 Risk-sensitive partially observable Markov decision processes.- 5.6.1 Model formulation and practical examples.- 5.6.1.1 Maintenance policies for a nuclear reactor pressure vessel.- 5.6.1.2 Medical diagnosis and treatment as applied to physiological systems.- 5.6.2 The stationary Markov decision process with probabilistic observations of states.- 5.6.3 A branch and bound algorithm.- 5.6.4 A Fibonacci search method for a branch and bound algorithm for a partially observable Markov decision process.- 5.6.5 A numerical example.- 6 Policy Constraints in Markov Decision Processes.- 6.1 Methods of investigating policy costraints in Markov decision processes.- 6.2 Markov decision processes with policy constraints.- 6.2.1 A Lagrange multiplier formulation.- 6.2.2 Development and convergence of the algorithm.- 6.2.3 The case of transient states and periodic processes.- 6.3 Risk-sensitive Markov decision process with policy constraints.- 6.3.1 A Lagrange multiplier formulation.- 6.3.2 Development and convergence of the algorithm.- 7 Applications.- 7.1 The emergency repair control for electrical power systems.- 7.1.1 Reliability and system effectiveness.- 7.1.2 Reward structure.- 7.1.3 The Markovian decision process for emergency repair.- 7.1.4 Linear programming formulation for repair optimization.- 7.1.5 The investment problem.- 7.2 Stochastic models for evaluation of inspection and repair schedules [2].- 7.2.1 Inspection actions.- 7.2.1.1 Complete inspection.- 7.2.1.2 Control limit inspection.- 7.2.1.3 Inspection.- 7.2.2 Markov chain models.- 7.2.3 Cost structures and operating requirements.- 7.2.3.1Inspection costs.- 7.2.3.2 Repair costs.- 7.2.3.3 Operating costs and requirements.- 7.2.3.4 Inspection and repair policies.- 7.2.3.5 Closed loop policies.- 7.2.3.6 Updating state probabilities after an inspection.- 7.2.3.7 Obtaining next-time state probabilities using transition matrix.- 7.2.3.8Open loop policies.- 7.3 A Markovian dicision model for clinical diagnosis and treatment applied to the respiratory system.- 7.3.1 Concept of state in the respiratory system.- 7.3.2 The clinical observation space.- 7.3.3. Computing probabilities in cause-effect models and overall system dynamics.- 7.3.4 Decision alternatives in respiratory disorders.- 7.3.4.1 Branch and bound algorithm.- 7.3.4.2 Steps in the branch and bound algorithm.- 7.3.5 A numerical example for the respiratory system.- 7.3.6 Concllusions.