The stochastic shortest-path problem for Markov chains with infinite state space with applications to nearest-neighbor lattice chains (Q2392790)

The authors consider the basic version of the stochastic shortest-path problem (SSPP), where the objective is to control a discrete-time Markov chain (MC), by suppressing certain moves, so as to minimize the expected time to reach a certain given target state. The authors solve the basic SSPP for an MC on a countable state space and then use the results to deal with a large class of nearest-neighbor Markov lattices. They characterize the optimal policies for SSPPs for general MCs with countably infinite state space, the main tool being a verification theorem for the value function, and give an algorithmic construction. Then they apply the results to a large class of examples: nearest-neighbor MCs for which the state space \(\mathbb{ Z\times Z}\) is split by a vertical line into two regions inside which the transition probabilities are the same for every state. The authors give a necessary and sufficient condition for the so-called distance-diminishing policy to be optimal. Finally, for the general case in which this condition does not hold, they develop an explicit finite construction of an optimal policy.