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

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

В этой и следующей главах мы будем рассматривать исключительно стационарные стратегии и обозначать их вместо

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

удовлетворяет рекуррентному соотношению

где

Лемма 2.4. Если стремится к при т. е. регулярна, то

где

Доказательство.

Полагая

получим (2.24).

Заметим, что если в данной лемме вместо вектора писать то равенство (2.24) остается справедливым и в общем случае, рассматриваемом в гл. 3.

Если достаточно велико, то, подставляя в соотношение (2.22) вместо значение получим

или

Равенство (2.27) определяет с точностью до постоянной, т. е. вектор вида постоянная) также удовлетворяет (2.27). Следовательно, полагая один элемент вектора равным нулю (например, ), можно разрешить (2.27) относительно Это соответствует процедуре определения весов для процесса с одним эргодическим классом.

Далее, определим процедуру улучшения решения. Применим для этого эвристический подход Ховарда [63]. При достаточно больших правая часть (2.22) асимптотически равна

Так как , то вектор (2.28) равен

Член в этом уравнении не зависит от новой улучшенной стратегии. Следовательно, можно максимизировать оставшуюся сумму

по всевозможным решениям, принимаемым в каждом состоянии, используя известные значения Строгое рассмотрение процедуры улучшения решения будет дано в разделе 2.5.

Если существует стратегия такая, что

то эта стратегия лучше Векторное неравенство (2.31) понимается в смысле определения, данного в разделе 1.2.

Теорема 2.2. Если при некотором выполнено неравенство то где -средний доход за единицу времени при стационарной стратегии

Доказательство. Пусть -мерный вектор такой, что

Для двух стратегий имеем

Вычитая (2.33) и (2.32) и полагая

получим

Умножая обе части этого равенства слева на предельный вектор получим

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

Представим итерационный алгоритм нахождения стратегий для процесса с одним эргодическим классом в следующем виде.

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

относительно (полагая где верхний индекс определяется выбранной стратегией ).

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

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

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

О причинах такого выбора будет сказано в разделе 2.5.