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

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

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 вместо , вместо :