1.2. Итерационный алгоритм нахождения стратегий

Ниже мы приведем итерационный алгоритм нахождения стратегий для марковских процессов принятия решений с переоценкой, который был впервые предложен Ховардом [63] и поэтому иногда называется итерационным алгоритмом Ховарда.

Он тесно связан с линейным программированием, и эта связь будет позднее обсуждена. Материал этого параграфа является основой для рассмотрения общих процессов принятия решений в гл. 7.

Пусть множество всевозможных векторов со значениями в пространстве политик и -элементы из Тогда стратегия определяется, как последовательность т. е.

вектор, элемент которого, обозначаемый является решением, принимаемым в состоянии в момент

Стратегия обозначается где Стратегия обозначается где и называется стационарной.

Стационарная стратегия состоит из политик, не зависящих от времени. Стратегия вида

обозначается где

При любой стратегии изучаемый процесс является, вообще говоря, неоднородной цепью Маркова, для которой матрица вероятностей перехода за шагов имеет вид

где является матрицей перехода размера элемент которой равен При положим (единичная матрица размера При любом можно определить -мерный вектор доходов его элемент обозначается . В этих обозначениях -мерный вектор суммарных средних доходов элемент которого отвечает начальному состоянию процесса имеет вид

Чтобы показать ограниченность этого вектора, положим Имеем

где -мерный вектор с компонентами, равными 1.

Справедливы следующие равенства:

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

Определим векторные неравенства следующим образом. Для любых векторов будем писать если каждый элемент вектора не меньше, чем соответствующий элемент вектора и будем писать если

Определение 1.1. Стратегия называется -опти-калъной, если для всех при фиксированной величине

Это определение означает, что оптимальная стратегия оптимальна одновременно для всех начальных состояний — факт, не являющийся тривиальным, как будет показано далее.

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

Лемма 1.1. Оператор является монотонным, т. е. если то

Доказательство. Пусть Тогда

Отсюда получаем следующие теоремы.

Теорема 1.1. Если при всех , то -оптимальна.

Доказательство. По предположению теоремы при всех Для любой стратегии полагая имеем Применяя монотонный оператор получаем

Неоднократное применение этого соотношения приводит к неравенству

справедливому при всех Полагая находим, что всех Теорема то

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

Следующая теорема является основной.

Теорема 1.3. Пусть и для каждого обозначим множество всех таких, что

где элемент Тогда

1) Если пусто при всех , то - оптимальна.

2) Если непусто, то для любого такого, кто некотором

и б) если имеет место неравенство

Доказательство, элемент вектора равен где Он больше тогда и только тогда, когда и равен если Таким образом, если пусто при всех то при всех откуда следует, что является -оптимальной стратегией (по теореме 1.1). В то же время для любой удовлетворяющей условиям а) и б), имеем откуда (по теореме 1.2).

Следствие. Существует стационарная -оптимальная стратегия.

Доказательство. По теореме 1.3 любая стационарная стратегия либо является -оптимальной (случай, когда пусто при всех ), либо имеет стационарное улучшение (случай, когда не пусто при некотором S). Поскольку существует лишь конечное число стационарных стратегий, то за конечное число итераций найдется такая, которая не имеет стационарных улучшений. Следовательно, она должна быть -оптимальной.

Доказанные теоремы содержат описание метода нахождения оптимальной стационарной стратегии. Этот метод, называемый итерационным алгоритмом Ховарда, состоит из следующих двух процедур.

Процедура определения весов.

Выбирая произвольную политику решим уравнения

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

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

Если множества пусты при всех то -оптимальна и вектор является вектором суммарных средних доходов с учетом переоценки. Пусть теперь существует хотя бы одно состояние для которого множество непусто. И пусть множество всех таких состояний. Тогда образуем улучшенную стратегию по следующему правилу: произвольный элемент множества при каждом а при полагаем После этого возвращаемся к процедуре определения весов.

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

В разделе 1.6 будут даны численные примеры применения итерационного алгоритма.