4.3. Свойства оптимальной стратегии

В отличие от бесконечного времени планирования, в рассматриваемом случае оптимальная стратегия не обязательно стационарна. Рассмотрим следующий пример.

Пример. Пусть имеется система, которая в каждый момент времени может находиться в одном из двух состояний 1 или 2. В состоянии 1 существуют два решения. При первом система получает доход, равный 1, и с вероятностью остается в том же состоянии; при втором — система получает доход, равный и с вероятностью остается в состоянии 1. Если же система находится в состоянии 2, то она получает нулевой доход и остается в состоянии 2 с вероятностью . В этом случае где Соответствующие матрицы переходов и векторы

одношаговых доходов имеют вид

Таким образом,

и стационарная оптимальная стратегия (она также и -оптимальна, см. теорему 3.4).

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

Для произвольного -мерного вектора определим величину .

Обозначим любое из трех отношений Легко видеть, что тогда и только тогда, когда Кроме того, и Следовательно, оптимальная стратегия имеет вид т. е. является последовательностью чередующихся элементов заканчивающейся элементом Таким образом, оптимальная стратегия — периодическая.

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

Лемма 4.4 а) Если матрица непериодическая, то

б) Если периодическая матрица с периодом а то

где

Доказательство. Будем для краткости вместо писать соответственно.

а) Так как непериодическая матрица, то . Поэтому в силу леммы 2.4 имеем

б) Так как то можно написать следующую цепочку равенств:

Кроме того, при поскольку непериодическая матрица. Тогда

т.е Следовательно,

Полагая

получаем утверждение б).

Применим теперь лемму 4,4 к рассмотренному выше примеру. Заметим, что

Тогда в силу леммы 4.4 имеем

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

Лемма 4.5. Пусть стационарная оптимальная стратегия для бесконечного времени планирования. Тогда стратегия является -оптимальной при некотором значении

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

Из леммы 4.3 получаем, что при всех достаточно больших и любом справедливо неравенство

Но из леммы 4.2 следует, что

Таким образом, для любой стратегии

для всех значений

Теорема 4.1. Пусть — оптимальная стратегия, а — стационарная оптимальная стратегия. Тогда разность является равномерно ограниченной по

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

а последний член в правой части равномерно ограничен по Полагая в силу леммы 4.5 получаем, что Это противоречит

сделанному предположению о неограниченности данной разности сверху.

Следствие 1. Разность равномерно ограничена по

Доказательство. Заметим, что

Но в силу лемм 2.4 и 4.4 выражения, стоящие в скобках, равномерно ограничены по

Следствие 2. Если элемент встречается в бесконечное число раз, то где оптимальная стратегия.

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

Переходя к пределу в (4.27) по подпоследовательности такой, что и используя следствие 1 теоремы 4.1, получаем

Покажем, что асимптотически периодическая функция, т. е. найдется такое натуральное число что предел

существует при каждом

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

Заменим повсюду на Докажем, что существует, если

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

Лемма 4.6. Пусть некоторое семейство действительных функций таких, что

для всех Тогда

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

что противоречит сделанному предположению. Таким образом,

Меняя местами получаем

Обозначим норму вектора определяемую равенством где координата вектора

Приведем теперь две леммы, которые будут существенно использованы при доказательстве теоремы 4.2.

Лемма 4.7. Если ли и соответственно -оптимальная и -оптимальная стратегии, то имеет место неравенство

Доказательство. Для любой стратегии имеем

где Используя лемму 4.6, из неравенства (4.32) получаем

откуда следует утверждение леммы.

Лемма 4.8. Пусть предельная точка последовательности где -оптимальная стратегия. Тогда для некоторого выполняется равенство

Доказательство. Так как предельная точка последовательности то существует подпоследовательность такая, что при Следовательно, для всех достаточно больших

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

Заметим, что в силу лемм 4.5 и 4.2. (Кроме того, и ). Пусть предельная точка для такая, что где минимум берется по всем предельным для точкам множества В. Этот минимум достигается, потому что множество точек, предельных для является компактом. На основании леммы 4.7 получаем

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

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

Пусть имеется бесконечно много точек таких, что при некотором

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

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

Докажем теперь теорему об асимптотической периодичности

Теорема 4.2. Если — оптимальная стратегия, то найдется такое натуральное число что предел

существует при каждом I, где оптимальная стратегия.

Доказательство. Предположим, что в оптимальной стратегии элемент встречается лишь

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

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

Применяя лемму 4.7, получаем

И, наконец, из леммы 4.8 следует, что для некоторого

Следствие. Для всякого существует стратегия , у которой при всех достаточно больших и такая, что для оптимальной стратегии и всех выполняется неравенство

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

где периодическая -оптимальная стратегия. Таким образом, мы показали, что

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

Все результаты этой главы принадлежат Брауну [19], который рассмотрел также специальный случай, когда все элементы матрицы строго положительны, т. е. регулярная матрица. Для этого случая им доказана более сильная теорема,

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

Общая теория динамического программирования содержится в книгах Беллмана [7], [8], Беллмана и Дрейфуса [9].

Формулировка задачи линейного программирования применительно к марковским процессам принятия решений с конечным временем планирования была дана Дерманом и Клейном [43], но мы ее здесь не рассматриваем.

Представляет также интерес магистральная теорема, доказанная для процессов, изучавшихся в этой главе (см. Шапиро [1041).

Аналогичные задачи рассматривал Юшкевич [146] в связи с понятием канонических стратегий.