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

 

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

 

1. Автоматы с линейной тактикой, предложенные М.Л. Цетлиным [3].

 

Рассмотрим простейший пример автомата, обладающего целесообразным поведением. Рассмотрим автомат , имеющий два состояния памяти и и два действия и . Автомат сохраняет свои состояния (действия) при выигрыше и изменяет при проигрыше. Матрицы состояний имеют вид , . Графы переходов состояний имеют вид

 

 

Рисунок 1

 

Найдем математическое ожидание выигрыша этого автомата в стационарной случайной среде С( ). Обозначим через ( ) финальную вероятность действия . Тогда:

,

.

Учитывая условие нормировки - , имеем:

,

.

Тогда математическое ожидание выигрыша автомата А в среде С определяется как:

.

Если автомат выбирает свои действия независимо от реакций среды и равновероятно, то математическое ожидание его выигрыша

.

Очевидно, что при , т.е. автомат обладает целесообразным поведением в стационарной случайной среде С ( ).

 

Рассмотрим автомат (с линейной тактикой), являющийся естественным обобщением автомата . Он имеет 2m состояний и два различных действия и . Графы переходов состояний имеют вид (рисунок 2):

 

Рисунок 2

 

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

Имеем дискретную цепь Маркова, задающую поведение системы “автомат – среда”. Как и раньше, ( ) - финальная вероятность действия . Зададим ; . Найдем финальную вероятность каждого действия , а затем математическое ожидание выигрыша.

……..

……….

- Условие нормировки

=

=

….

, если

 

 

….

…

> , если

 

Мат. ожидание выигрыша возрастает, значит эти автоматы целесообразны.

Замечание: Если рассмотреть последовательность таких автоматов, у которых память , то такая последовательность автоматов называется асимптотически-оптимальной.

 

Автомат с линейной тактикой является обобщением конструкций М.Л. Цетлина, рассмотренных выше. Автомат имеет внутренних состояний и действий (параметр - глубина памяти). Состоянием автомата соответствует выходное действие . При = +1 (поощрении) автомат не меняет своего действия и из состояния переходит в состояние , а в состоянии остаётся. При = -1 (штрафе) из состояния переходит в состояние при и в состояние при , меняя своё действие на ( ) или на ( ). Граф смены состояний приведён на рисунке 3.

Рисунок 3

 

Автомат с линейной тактикой также является целесообразным в стационарной случайной среде С( ), и относится к асимптотически-оптимальной последовательности автоматов.

 

2. Автомат Крылова .

 

Рисунок 4

 

…

…

Добавляем условие нормировки:

Тогда из первого уравнения получаем:

…

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

Автоматы Крылова образуют асимптотически-оптимальную последовательность во всех стационарных случайных средах.

Аналогично, можно доказать целесообразность поведения автоматов, представленных ниже [2,3].

 

3. Автомат Роббинса

 

Рисунок 5

 

4. Автомат Кринского (“доверчивый” автомат)

 

Рисунок 6

 

5. Автомат Вайсборда

 

Рисунок 7

 

Запишем финальные вероятности состояний:

….

…

Автомат обладает целесообразностью поведения, т.к. , если .

 

6. Стохастический автомат с линейной тактикой . Данная конструкция представляет собой стохастический вариант автомата с линейной тактикой М.Л. Цетлина. При входном сигнале S автомат с вероятностью осуществляет те же переходы, что и автомат при таком же входном сигнале, а с вероятностью автомат осуществляет такие же переходы, которые осуществляет автомат при противоположном входном сигнале. При =1 стохастический автомат становится детерминированным автоматом с линейной тактикой. Автомат при является целесообразным в стационарной случайной среде С и относится к асимптотически-оптимальной последовательности автоматов.

 

 

Рисунок 8

 

 

7. Автомат Валаха (с избирательной тактикой)

 

S = +1

S = 1

 

Рисунок 9

 

Граф смены состояний автомата Валаха аналогичен графу стохастического автомата с линейной тактикой, только при S = +1 вместо , вместо : , а в случае S = -1 вместо , вместо :