A survey is given of the present state of the art of value-iteration and related successive approximation methods, as well as of resulting turnpike properties, in both the discounted and undiscounted version of finite state and action Markov Decision Problems.
In this paper we consider a set of denumerable stochastic matrices where the paramter set is a compact metric space. We give a number of simultaneous recurrence conditions on the stochastic matrices and establish equivalences between these conditions. The results obtained generalize corresponding results in Markov chain theory to a considerable extent and have applications in stochastic control problems.
This paper investigates the solutions to the functional equations that arise inter alia in Undiscounted Markov Renewal Programming. We show that the solution set is a connected, though possibly nonconvex set whose members are unique up to the n* constants, characterize n* and show that some of these n* degrees of freedom are locally rather than globally independent.
This paper is concerned with the properties of the value-iteration operator which arises in undiscounted Markov decision problems. We give both necessary and sufficient conditions for this operator to reduce to a contraction operator, in which case it is easy to show that the value-iteration method exhibits a uniform geometric convergence rate.
An example for undiscounted multichain Markov Renewal Programming shows that policies may exist such that the Policy Iteration Algorithm (PIA) can converge to these policies for some (but not all) choices of the additive constants in the relative values, and as a consequence that the PIA may cycle if the relative values are improperly determined.
This paper is concerned with the optimality equation for the average costs in a denumerable state semi-Markov decision model. It will be shown that under each of a number of recurrency conditions on the transition probability matrices associated with the stationary policies, the optimality equation has a bounded solution. This solution indeed yields a stationary policy which is optimal for a strong version of the average cost optimality criterion.
This paper considers non-cooperative N-person stochastic games with a countable state space and compact metric action spaces. We concentrate upon the average return per unit time criterion for which the existence of an equilibrium policy is established under a number of recurrency conditions with respect to the transition probability matrices associated with the stationary policies.
This paper considers an undiscounted semi-Markov decision problem with denumerable state space and compact metric action spaces. Recurrence conditions on the transition probability matrices associated with the stationary policies are considered and relations between these conditions are established. Also it is shown that under each of these conditions the optimality equation for the average costs has a bounded solution.
This paper considers undiscounted Markov Decision Problems. For the general multichain case, we obtain necessary and sufficient conditions which guarantee that the maximal total expected reward for a planning horizon of n epochs minus n times the long run average expected reward has a finite limit as n approaches infinity for each initial state and each final reward vector. In addition, we obtain a characterization of the chain and periodicity structure of the set of one-step and J-step maximal gain policies.