2.7. Процессы с поглощением

Рассмотрим марковский процесс принятия решений специального вида. Именно, мы предположим, что система имеет одно поглощающее состояние при любом решении. Примем его за состояние 1. Предположим затем, что состояние 1 достижимо из любого другого состояния. Строго это предположение выглядит так.

Предположение о поглощении. Общее поглощающее состояние может быть достигнуто с вероятностью 1 за конечное число шагов из каждого состояния при любом принимаемом решении.

Другими словами, это предположение утверждает, что состояние -поглощающее, а состояния невозвратные при любом принимаемом решении.

Найдем стратегию, которая максимизирует суммарный средний доход до поглощения. Эта задача возникла в работе Шэпли [105], рассматривающей стохастическую игру, в которой второй игрок является пассивным (см. Приложение); в общем случае задача является стохастической игрой с поглощением. Предположение о поглощении, сделанное Шэпли, сводится к неравенству для всех . Наше предположение заключается в том, что для некоторого и всех соответствующих решений . Система не обязательно переходит в состояние 1 за один шаг из всех невозвратных состояний. Но состояние 1 достижимо из любого невозвратного состояния за конечное число шагов с вероятностью 1.

Целевая функция в данном случае конечна, поскольку с вероятностью 1 за конечное число шагов система попадает в поглощающее состояние. Это пример

системы, в которой суммарный средний доход конечен без введения переоценки.

Вектор суммарных средних доходов, получаемых системой при различных начальных состояниях и стратегии , равен

где Химерные векторы, а -матрица размера получающаяся путем вычеркивания первых строки и столбца. Для этой задачи справедливы следующие теоремы. Доказательства их почти аналогичны приведенным в разделе 1.2. Поэтому они опускаются.

Лемма 2.5. Если те для всех то те оптимальна, где те — стратегия, в которой первой принимается политика а затем все политики, входящие в .

Теорема 2.4. Для каждого справедливо одно и только одно из следующих утверждений.

а) Если для всех то оптимальна.

б) Если для некоторого то

Теорема 2.5. Существует оптимальная стратегия, являющаяся стационарной.

Теорема 2.4 порождает следующий итерационный алгоритм нахождения стратегий.

Процедура определения весов. Выбрать любое Решить уравнения

относительно где верхний индекс соответствует выбранной стратегии

Процедура улучшения решения. Используя полученные значения найти для

каждого элемент множества такой, что

для всех Если пусто для всех то оптимальна, а вектор суммарных средних доходов. Если при некотором множество непусто, то рассмотреть улучшенную стратегию которая строится так: если непусто, и если пусто. Перейти к процедуре определения весов.

Для процесса с поглощением имеем следующую задачу линейного программирования:

при ограничениях

где -начальное распределение процесса.

Вывод этой задачи линейного программирования во многом аналогичен выводу, приведенному в разделе 1.3.

Аналогия между процессом с переоценкой и процессом с поглощением будет рассмотрена в гл. 7 с помощью принципа сжатых отображений.

Ссылки и комментарии

Мы рассматриваем только конечные цепи Маркова, при классификации состояний и изучении свойств которых следуем книге Кемени и Снелла [70]. Свойство суммируемости рассмотрено в работе Кемени и др. [71].

Итерационный алгоритм для процесса с одним эргодическим классом был предложен Ховардом [63]. Оптимальность стационарных стратегий доказана Дерманом [36], Блекуэллом [14] и Мартин-Лефом [87]. Формулировка в виде задачи линейного программирования дана Де Хелинком [27], Манне [85], Дерманом [36] и Вольфом и Данцигом [120]. Сравнение трех алгоритмов было сделано Осаки.

Процесс с поглощением рассматривался Ховардом [63, Приложение], Итоном и Заде [53] и Осаки и Майном [95].

Для случая процесса с одним эргодическим классом важной задачей является выбор начальной стратегии. Изучались последовательные приближения, отличные от рассмотренных здесь. Уайт [116] предложил метод последовательных приближений, использующий приближения в пространстве политик для динамического программирования. Норман и Уайт [92] дали метод приближения оптимальной стратегии с помощью средних

Вопрос о сходимости -оптимальных стратегий к -оптимальной при и оптимальности стационарных стратегий при максимизации среднего дохода рассматривался также Висковым и Ширяевым [126]. Юшкевичем [146] введено понятие канонической стратегии, которая оказывается асимптотически оптимальной при оптимизации стационарного среднего дохода.

Вопросам ускорения сходимости итерационного алгоритма и методам его реализации на ЦВМ посвящены работы Мортона [152], Одони [153], Швейцера [157], [1581, Уайта [159], Янга [160]. Примеры реализации алгоритма Ховарда можно найти в дополнении Рыкова к русскому переводу книги Ховарда [63], в работах Неймарка и Преображенской [133], Федоткина [141] и др.