Technical Note—Undiscounted Markov Renewal Programming Via Modified Successive Approximations

This note describes an efficient class of procedures for finding a solution to the functional equations \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland,xspace}\usepackage{amsmath,amsxtra}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}$$v^{*}_{i}=\max_{k} \biggl[q^{k}_{i}-g^{*}T^{k}_{i}+ \sum^{j=n}_{j=1}P^{k}_{ij}v_{j}^{*}\biggr],\quad 1\leq i \leq N,$$\end{document} of undiscounted Markov renewal programming. First, for the special case of a single possible policy, the problem is proved equivalent to solving two related ordinary Markov chain problems, which leads to an algorithm for the general problem whose exact form depends on the specification of a decision rule for alternation of two types of iterations. At one extreme, the technique is exactly “policy iteration,” with iterative techniques replacing solution of N equations for each improved policy; at the other extreme, the algorithm becomes essentially “value iteration,” generalizing the method of successive approximations proposed by D. J. White for Markovian decision processes. The latter version of the technique is related to another generalization being currently proposed by Paul J. Schweitzer; the methods being proposed here, however, do not deteriorate when the minimum transition time between states becomes very small.