Growth Optimality for Branching Markov Decision Chains

Abstract

This paper considers a (multiplicative) process called branching Markov decision chains in which the output at the end of the Nth period equals the product of N nonnegative matrices chosen at the beginning of periods 1, …, N, respectively, times a positive (fixed) terminal reward vector. It is assumed that the above transition matrices are drawn out of a finite set of matrices given in product form (i.e., the rows of the matrices can be selected independently out of finite sets of nonnegative row vectors). For each coordinate s we define the geometric and algebraic growth rates, respectively, of the sth coordinate of the stream of output. These growth rates are defined so that the magnitude of the corresponding sequence is of the order α N N k where α is the geometric growth rate and k is the algebraic growth rate. The main result of this paper is the constructive establishment of the existence of a transition matrix whose repeated use will guarantee, for each coordinate, the achievement of the best geometric growth rate and the best algebraic growth rate subject to the geometric growth rate at maximum, among all potential sequences of transition matrices.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 47 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.