6.3. Теоремы существования

Теорема 6.1. Для любых существует -оптимальный план.

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

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

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

Итак, мы доказали существование -оптимального плана . Приведем теперь примеры процессов, для которых не существует -оптимального или -оптимального плана.

Пример. 1 (не существует -оптимального плана). Множество состоит из одного элемента, который обозначим счетное множество, элементы которого Положим

Для такого процесса но не существует плана для которого

Пример 2 (не существует -оптимального плана). Пусть Система остается в одном и том же состоянии, т. е. , а доход равен 1 или О в зависимости от того, принадлежит ли пара некоторому заданному борелевскому множеству или нет. Для любого множество борелевское подмножество множества являющегося проекцией В на Если В выбрать таким образом, чтобы множество не было борелевским, то найдется точка для которой и следовательно, Для построим функцию такую, что и положим Тогда Для любого выполняется неравенство показывающее, что план не является -оптимальным ни при каком

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

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

где для любой функции Докажем теперь, что если план

является марковским при то для любого числа существует отображение переводящее при котором где Повторяя эту процедуру раз при получаем марковский план являющийся -мажорирующим по отношению к плану

Чтобы найти напишем следующее соотношение:

где

Найдем из условия

где

Рассмотрим распределение на Соответствующие случайные величины (и их значения) будем обозначать При любой функции функция совпадает с условным математическим ожиданием Если выбрать так, чтобы с вероятностью 1 выполнялось неравенство , то с вероятностью 1 будет выполняться также и неравенство что эквивалентно условию (6.8). Существование такой функции сразу следует из леммы 6.1, если положить в качестве взять условное распределение величины относительно

Следствие. Для любых существует -оптимальный нерандомизированный марковский план .

Доказательство. В силу теоремы 6.1 существует -оптимальный план , а из теоремы 6.2 следует существование нерандомизированного марковского плана , являющегося -мажорирующим по отношению к . Следовательно, -оптимальный план.

Следствие теоремы 6.2 устанавливает существование -оптимального нерандомизированного марковского

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

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

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

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

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

Теорема 6.3, а) Оператор монотонный, т. е. если то Для произвольной постоянной с

б) Для любого марковского плана выполняется равенство где

Определение 6.10. Пусть произвольный марковский план. Функцию отображающую назовем -вырожденной, если существует такое разбиение множества на борелевские подмножества при котором для всех (Множества называются разбиением , если при )

Определение 6.11. Марковский план назовем -вырожденным, если все являются -вырожденными.

Каждому марковскому плану поставим в соответствие оператор отображающий множество в себя, с помощью следующего равенства:

Теорема 6.4. а) Оператор монотонный.

б) Для произвольной постоянной с

в) Для любого оператора связанного с -вырожденной функцией выполняется неравенство

г) Для любых существует -вырож-денная функция такая, что связанный с ней оператор удовлетворяет неравенству

Доказательство. Утверждения а) и в) очевидны. Чтобы доказать б), воспользуемся неравенством

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

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

для любого марковского плана Если план является -вырожденным, то для всех так что Чтобы найти план удовлетворяющий неравенству

выберем произвольные положительные числа и такие -вырожденные функции чтобы

Последовательно применяя последнее неравенство при убывающих значениях начиная с получаем

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

Теорема 6.5. Если — оператор, удовлетворяющий условиям а) и б) теоремы 6.4, то сжатое отображение, модуль которого равен т. е.

Доказательство. В силу утверждений а) и б) теоремы 6.4 из неравенства следует неравенство

Заменяя и на на и, получаем аналогичное неравенство

Из теоремы (6.5) следует, что отображение имеет единственную неподвижную точку и неравенство

выполняется при всех

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

б) Для любых существует стационарный -оптимальный план.

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

г) Для каждого обозначим оператор, соответствующий функции Тогда любая функция и, удовлетворяющая неравенству при всех а,

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

д) Если для любого существует -оптимальный план, то оптимальный доход и является бэровской функцией, удовлетворяющей уравнению оптимальности

е) План является оптимальным тогда и только тогда, когда доход удовлетворяет уравнению оптимальности.

Доказательство, а) Для любого -вырожденного плана имеем где Так как каждое является сжатым отображением с модулем, равным то

Следовательно, при поэтому . В силу утверждения г) теоремы 6.4 существует -вырожденная функция такая, что выполняется неравенство в, где Индукцией по легко доказать, что неравенство

выполняется при всех . А так как то из (6.16) получаем, что

б) В силу следствия теоремы 6.2 существует -оптимальный марковский план Из только что доказанного утверждения а) вытекает существование стационарного плана для которого выполняется неравенство

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

в) Для любого плана имеем , где

Если -оптимальный план, то при всех и поэтому

где

В силу леммы 6.1 существует функция такая, что неравенство выполняется при всех а тогда оператор отвечающий этой функции удовлетворяет неравенству Индукцией по получаем

Переходя в этом неравенстве к пределу при получаем . А так как -оптимальный план, то стационарный план является -оптимальным.

г) Для любых существует стационарный план при котором неравенство

выполняется при всех . В самом деле, в качестве такого плана возьмем стационарный -оптимальный план, где распределение сосредоточено в точке Из выполнения неравенства при всех а следует его справедливость для выбранной выше функции т. е. Таким образом, монотонно убывая, стремится к причем Тогда Переход к пределу при завершает доказательство.

д) Из утверждения в) следует, что для любого целого существует стационарный -оптимальный план; обозначим его . В силу а), неподвижная точка отображения отвечающего плану является оптимальным доходом в классе -вырожденных планов. В частности, поэтому при всех и является оптимальным доходом. Нетрудно заметить,

что . С другой стороны, для любого справедливы соотношения

где Переходя в (6.20) к пределу при получаем Таким образом, а удовлетворяет уравнению оптимальности.

е) Если удовлетворяет уравнению оптимальности, то, полагая в утверждении г) получаем, что — оптимальный план. Обратно, если план оптимален, то выполнено условие утверждения д), а тогда в силу этого утверждения оптимальный доход а удовлетворяет уравнению оптимальности.

Отметим, что пункт г) теоремы 6.6 можно использовать при доказательстве оптимальности плана. В самом деле, если известно, что и — доход от процесса при плане удовлетворяет неравенству при всех а, то в силу утверждения г) план оптимален.