Аннотация:
Рассматривается задача оптимальной остановки цепи Маркова на бесконечном интервале времени с платой за остановку $g(z)$. И. М. Сонин для случая цепи с конечным числом состояний предложил алгоритм, который позволяет найти функцию выигрыша и множество остановки за конечное число шагов (не более чем в два раза превосходящее число состояний). Алгоритм основан на рассмотрении на каждом этапе новой цепи с новым пространством состояний, когда исключаются состояния, в которых заведомо не нужно останавливаться. Оказалось, что при рассмотрении задачи с произвольным пространством состояний удобно несколько видоизменить алгоритм.
Рассмотрим, как и И. М. Сонин, множество $C_1$, на котором выигрыш от мгновенной остановки меньше выигрыша от остановки на первом шаге. На этом множестве заведомо не нужно останавливаться. Пусть $g_1 (z)$ – выигрыш от остановки в момент первого попадания в дополнительное к $C_1 $ множество. Тогда при естественных предположениях $g_1 (z)$ больше, чем $g(z)$ для $z$, принадлежащих $C_1$, и совпадет с $g(z)$ на дополнительном множестве. Рассмотрим для той же цепи задачу с новой платой за остановку, равной $g_1 (z)$. Очевидно, что эта задача эквивалентна исходной. Добавим теперь к множеству $C_1$ те точки, в которых выигрыш от мгновенной остановки меньше выигрыша от остановки на первом шаге для платы $g_1 (z)$. Получим множество $C_2$ и соответствующую функцию $g_2 (z)$. Последовательное применение этой процедуры приводит к последовательности функций $g_n(z)$ и множеств $C_n$, которые не убывают и сходятся соответственно к функции выигрыша исходной задачи и к множеству продолжения исходной задачи.
Иллюстрируется эффективность этой процедуры и возможности обобщения на случай непрерывного времени.
|
