3.3. Итерационный алгоритм нахождения 1-оптимальных стратегий

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

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

Лемма 3.4. Пусть для любых функция является единственным решением уравнений

Тогда

Доказательство. Единственность следует из теоремы 3.1. Поскольку то

Прибавляя это уравнение к первому уравнению в (3.34) и переписывая второе уравнение, получим

Но из теоремы 3.2 вытекает, что единственным решением этой системы является Таким образом, равенство (3.35) выполнено.

Отметим, что из (3.3), (3.14) и леммы 3.4 следует, что задача максимизации по всем имеет тот же вид, что и задача максимизации и по где заменено на на на при и всех Таким образом, итерационный алгоритм теоремы 3.2 можно использовать для нахождения максимизирующей а следовательно, и (в силу (3.35)) по всем

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

ли, что Алгоритм этого типа дается в следующей лемме.

Лемма 3.5. Если пусто и если при всех то

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

Следовательно, переобозначая -оптимальную стратегию через из (3.2) имеем

Поэтому при Таким образом, -оптимальна и в силу теоремы

Докажем следствие, которое обобщает теорему 3.3.

Следствие. Если пусто и если при всех то

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

Пусть при каждом является единственным (по теореме 3.1) решением уравнений

Аналогично множеству определим при любом множество решений

где и элементы векторов соответственно. Определим также

Будем считать, что пусто, если при каждом

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

Сформулируем теперь основной результат — итерационный алгоритм нахождения -оптимальной стратегии.

Теорема 3.5. Выберем произвольное Тогда

а) Если пусто, то

Доказательство. Утверждения а) и в) следуют из теоремы 3.2 и ее следствия.

б) Заметим сначала, что из (3.35) следует равенство Поскольку пусто, то из теоремы 3.2 и леммы 3.4 находим, что

для всех Таким образом,

г) Очевидно, поэтому из леммы 3.1 получаем, что и Из теоремы 3.2 (если ). Для всех достаточно близких к 1), из леммы 3.4 и из пункта данной теоремы следует, что или или

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

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

1. Выбрать произвольное

2. Найти Если пусто, то перейти к шагу 3. В противном случае выбрать улучшенную стратегию и повторить первую часть этого шага.

3. Найти и вычислить Если пусто, то . В противном случае выбрать улучшенную стратегию и повторить первую часть этого шага.

Продемонстрируем теперь итерационный алгоритм нахождения -оптимальной стратегии на примере из раздела 3.2 (стр. 71).

В качестве исходной стратегии выберем Тогда

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

при этом

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

Вновь вычисляя получаем, что множество пусто, откуда следует, что

Так как в рассматриваемом примере у цепи Маркова с матрицей при всех нет невозвратных состояний и так как множество пусто, то из следствия леммы 3.2 вытекает, что