The policy iteration method for the optimal stopping of a Markov chain and applications to a free boundary problem for random walks

In this paper we study the problem of the optimal stopping of a Markov chain with a countable state space. In each state i the controller receives a reward r(i) if he stops the process and he must pay the cost c(i) otherwise. We show that under some conditions, the policy iteration method, introduced by Howard, gives the optimal stopping rule in a finite number of iterations. For random walks with a special reward and cost structure the policy iteration method gives the solution of a free boundary problem. Using this property we shall derive a simple algorithm for the determination of the optimal stopping time of such random walks.