Метод итерации по стратегиям без дисконтирования

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

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

Это уравнение и служит основой метода итераций по стратегиям. Однако, чтобы сделать возможным изучение асимптотического поведения процесса, вид уравнения нужно немного изменить. В отличие от величины n, которая фигурирует в уравнении и соответствует i -му этапу, обозначим через η число оставшихся для анализа этапов. Тогда рекуррентное уравнение записывается в виде:

Здесь – суммарный ожидаемый доход при условии, что остались не рассмотренными η этапов. При таком определении η можно изучить асимптотическое поведение процесса, полагая при этом, что .

Обозначим через вектор установившихся вероятностей состояний с матрицей переходных вероятностей и пусть — ожидаемый доход за этап, тогда можно показать, что при достаточно большом η

где - постоянный член, описывающий асимптотическое поведение функции при заданном состоянии i.

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

Упростив это уравнение, получаем:

т.е. имеем m уравнений с неизвестными и E.

Конечной целью является определение оптимальной стратегии, приводящей к максимальному значению Е. Так как имеется m уравнений с неизвестными, оптимальное значение Е нельзя определить за один шаг. В связи с этим используется итеративная процедура, начинающаяся с произвольной стратегии, а затем определяется новая стратегия, дающая лучшее значение Е. Итеративный процесс заканчивается, если две последовательно получаемые стратегии совпадают.

Итеративный процесс состоит из двух основных шагов.

Шаг 1. Оценивание параметров.

Выбираем произвольную стратегию s. Используя соответствующие матрицы P^S и R^S произвольно полагая f(m) = 0, решаем уравнения

относительно неизвестных , .

Шаг 2. Улучшение стратегии.

Для каждого состояния определяем альтернативу k, обеспечивающую

Здесь используются значения , j = 1, 2, …, m, определенные на шаге оценивания параметров. Результирующие оптимальные решения для состояний 1, 2, …, m формируют новую стратегию t. Если s и t идентичны, то алгоритм заканчивается; в этом случае t – оптимальная стратегия. В противном случае полагаем s = t и возвращаемся к шагу оценивания параметров.

Оптимизационная задача на шаге улучшения стратегии нуждается в пояснении. Целью этого шага является получение максимального значения Е. Как показано выше,