7.5. Примеры

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

где — коэффициент переоценки,

Поскольку

то выполняется условие сжатия. Далее, если то

что равносильно выполнению условия монотонности.

Таким образом, применяя результаты раздела 7.3, получаем два оптимизационных алгоритма нахождения оптимальной стратегии. Один из них — алгоритм линейного программирования, сформулированный в разделе 1.3 в виде двойственной задачи. Второй — итерационный алгоритм нахождения стратегий, приведенный в разделе 1.2.

2. Процесс с поглощением (см. раздел 2.7). Для этой модели при каждом и политика определяется как функция любое значение которой есть решение, принимаемое в состоянии Тогда

Хотя отображение не является сжатым, тем не менее Ну — сжатое отображение, т. е. модель удовлетворяет условию -сжатия. Здесь число состояний процесса. Кроме того, очевидно, что выполняется условие монотонности. Таким образом, можно применить теорему 7.6 и воспользоваться алгоритмами оптимизации, аналогичными приведенным в разделе 2.7.

3. Обобщенный марковский процесс принятия решений (см. гл. 6). В этой модели пространство состояний и пространство политик суть непустые борелевские множества, элементы которых будем обозначать и а

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

где а) при каждой фиксированной паре

является распределением на Положим

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

Из этого включения вытекает, что

Тогда или Из определения не следует, что . Однако . А тогда имеют место следующие неравенства:

показывающие, что выполняется условие сжатия. Условие монотонности проверяется стандартным путем. Отметим, что определение функции одно и то же как для задачи максимизации, так и для задачи минимизации.

4. Полумарковский процесс принятия решений с переоценкой (см. раздел 5.4). Этот пример отличается от трех предыдущих тем, что рассматривается процесс с непрерывным временем. В остальном он аналогичен примеру 1. Чтобы избежать некоторых трудностей, связанных с интегрируемостью, опять воспользуемся функцией и покажем, что задача примера 1, для которой нет проблемы интегрируемости, вложена в рассматриваемую задачу.

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

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

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

Написанное выражение имеет смысл только тогда, когда функция интегрируема. Пусть

и предположим, что 1 при всех

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

Легко проверить, что в рассматриваемую задачу вложена задача примера 1, описываемая объектами

А тогда теорема 7.7 позволяет свести задачу оптимизации к более простой: с конечными пространствами состояний и решений, обходя трудности, связанные с интегрируемостью. Существование стационарной оптимальной стратегии гарантируется следствием 2 теоремы 7.4, что попутно доказывает теорему 5.1.

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

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

Заметим, что при фиксированных написанная выше формула задает платежную матрицу некоторой прямоугольной игры, -элемент которой равен выражению, стоящему в фигурных скобках. Следовательно, на основании теоремы о минимаксе для прямоугольных игр можно определить оператор В, действующий в пространстве У, следующим образом:

Пусть совокупности всевозможных вероятностных распределений на множествах соответственно. И пусть элементы этих множеств будем обозначать и (Таким образом, любые 8 и те представляют собой йаборы из вероятностных распределений, заданных на соответствующих множествах.) При любых фиксированных отображение удовлетворяет условию сжатия (см. Приложение), т. е. является сжатым отображением. Пусть неподвижная точка

этого отображения. Определим оператор с помощью следующего равенства:

Теорема 7.4 остается справедливой и в случае минимизации (вместо максимизации), а значит, она обеспечивает выполнение условия сжатия при каждом 8. Тогда, замечая, что

и применяя снова теорему 7.4, убеждаемся, что удовлетворяет условию монотонности. Отсюда следует, что единственное решение следующих уравнений:

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

Основные понятия математического анализа, использованные в этой главе, можно найти, например, в книгах Колмогорова и Фомина [76] или Эльсгольца [54].

Результаты этой главы были получены Денардо [31], а также Денардо и Миттеном [35]. Условие монотонности было впервые введено Миттеном [91].

Некоторые результаты для процессов с конечным пространством состояний получили Карп и Хелд [69].