TY - GEN

T1 - The policy iteration method for the optimal stopping of a Markov chain with an application

AU - Hee, van, K.M.

PY - 1976

Y1 - 1976

N2 - 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 or he must pay the cost c(i) otherwise. We show that, under the condition that there exists an optimal stopping rule, the policy iteration method, introduced by Howard, produces a sequence of stopping rules for which the expected return converges to the value function. For random walks on the integers with a special reward and cost structure, we show that the policy iteration method gives the solution of a discrete two point boundary value problem with a free boundary. We give a simple algorithm for the computation of the optimal stopping rule.

AB - 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 or he must pay the cost c(i) otherwise. We show that, under the condition that there exists an optimal stopping rule, the policy iteration method, introduced by Howard, produces a sequence of stopping rules for which the expected return converges to the value function. For random walks on the integers with a special reward and cost structure, we show that the policy iteration method gives the solution of a discrete two point boundary value problem with a free boundary. We give a simple algorithm for the computation of the optimal stopping rule.

U2 - 10.1007/3-540-07623-9_277

DO - 10.1007/3-540-07623-9_277

M3 - Conference contribution

SN - 3-540-07623-9

T3 - Lecture Notes in Computer Science

SP - 22

EP - 36

BT - Optimization techiques : modeling and optimization in the service of man part 2 (Proceedings 7th IFIP Conference, Nice, France, September 8-12, 1975), Part 2

A2 - Cea, J.

PB - Springer

CY - Berlin

ER -