Глава 2. Марковские процессы принятия решений без переоценки I

2.1. Введение

В этой и следующей главах будут рассмотрены марковские процессы принятия решений без переоценки в случае бесконечного времени планирования. Для таких процессов суммарный средний доход обычно неограничен (случай ограниченного суммарного среднего дохода рассматривается в разделе 2.7).

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

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

2.2. Вспомогательные результаты

Сначала приведем некоторые хорошо известные факты из теории матриц.

Лемма 2.1. Пусть А — матрица размера Тогда, если (нулевая матрица), невырождена и

Доказательство этой леммы приводится во многих источниках (см., например, [70], стр. 37).

Лемма 2.2. Если стохастическая матрица размера стремится при к то стремится к

Доказательство. По предположению последовательность суммируема по Чезаро к Но из суммируемости по Чезаро последовательности к следует суммируемость по Абелю последовательности т. е.

Следующая лемма в дальнейшем играет важную роль.

Лемма 2.3. Пусть стохастическая матрица размера Тогда

а) последовательность сходится при к стохастической матрице такой, что

б) матрица невырождена и

при

и

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

имеет единственное решение

Доказательство. Утверждение а) доказывается в теории цепей Маркова (см., например, [70]).

б) Используя (2.3), имеем при Из леммы 2.1

при или Следовательно,

Из леммы 2.2 получаем, что

при Таким образом, матрица в правой части (2.9) стремится к при невырождена. Умножая обе части равенства (2.9) справа на и устремляя получим, что Из этого соотношения следует (2.4). Для доказательства (2.5) воспользуемся равенствами

полученными из (2.3). Аналогично можно показать, что

Для доказательства (2.6) воспользуемся равенствами

полученными из (2.3) и (2.5). Можно также показать, что

в) Утверждение следует из соотношений

г) Доказательство следует из утверждения в).

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

Таким образом, нижний предел среднего дохода, получаемого за единицу времени при равен

Найдем стратегию максимизирующую т. е. удовлетворяющую неравенству

при всех . Такую стратегию назовем оптимальной.

Дерман [36] показал, что существует стационарная оптимальная стратегия, максимизирующая средний доход за единицу времени. Такой же результат был получен Блекуэллом [14] и другими. Здесь мы приведем результат Дермана.

Теорема 2.1. Существует оптимальная стратегия, являющаяся стационарной.

Доказательство. Для марковского процесса принятия решений с переоценкой существует -оптимальная стационарная стратегия (следствие теоремы 1.3). Поскольку число стационарных стратегий конечно, то можно выбрать последовательность такую, что где является стационарной стратегией. Из леммы 2.2 имеем

Для любой стратегии справедливо (см. [119], стр. 181):

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

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

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

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

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

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

Для любой стационарной стратегии и процесса с одним эргодическим классом имеем

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

где -мерный вектор, все элементы которого

равны 1. Тогда -мерный вектор является единственным решением системы

Таким образом, вектор средних доходов за единицу времени для стационарной стратегии равен

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

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