Asymptotic expansions for dynamic programming recursions with general nonnegative matrices (Q1078098)

This paper is concerned with the study of the asymptotic behavior of dynamic programming recursions of the form \(x(n+1)=\max_{P\in {\mathcal K}}Px(n)\) \((n=0,1,2,...)\) where \({\mathcal K}\) denotes a set of matrices, generated by all possible interchanges of corresponding rows, taken from a fixed finite set of nonnegative square matrices. These recursions arise in a number of well-known and frequently studied problems, e.g. in the theory of controlled Markov chains, Leontief substitution systems, controlled branching processes, etc. Results concerning the asymptotic behavior of x(n), for \(n\to \infty\), are established in terms of the maximal spectral radius, the maximal index, and a set of generalized eigenvectors. A key role in the analysis is played by a geometric convergence result for value iteration in undiscounted multichain Markov decision processes. A new proof of this result is also presented.