Нахождение оптимальных планов параллельного управления в случайной среде в приложении к обработке данных тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат наук Олейников, Андрей Олегович

• Олейников, Андрей Олегович
• кандидат наук
• 2014

Оглавление диссертации кандидат наук Олейников, Андрей Олегович

Оглавление

Введение

Глава 1. Теоретические основы

1.1. Краткий обзор литературы

1.2. Описание решаемой задачи

1.3. Поиск минимаксных стратегии и риска как байесовских

1.4. Выводы к первой главе

Глава 2. Стратегия параллельного управления

2.1. Нахождение минимаксного риска для параллельной обработки с группами переменного объема

2.2. Влияние размеров групп для параллельной обработки на минимаксный риск

2.3. Оптимизация размеров групп для параллельной обработки

2.4. Результаты численной оптимизации

2.5. Сравнение обработки с группами равного и различного размера

для одинакового числа этапов

2.6. Сложность алгоритма

2.7. Сравнение с другими алгоритмами

2.8. Возможные дальнейшие усовершенствования

2.9. Выводы ко второй главе

Глава 3. Упрощенные стратегии

3.1. О стратегиях

3.2. Способы получения упрощенных стратегий

3.3. Об оптимизации поиска рисков

3.4. Результаты численной оптимизации

3.5. Упрощенные стратегии для параллельной обработки с группами

различного размера

З.ф. Выводы к третьей главе

Заключение

Список литературы

Введение диссертации (часть автореферата) на тему «Нахождение оптимальных планов параллельного управления в случайной среде в приложении к обработке данных»

Введение

Целесообразное управление в случайной среде. В настоящее время все большую практическую значимость приобретают задачи принятия решений в условиях неопределенности. К таким задачам относятся задача о целесообразном поведении в стационарной случайной среде [2, 35], задача адаптивного управления [20, 32] и задача о двуруком бандите [31, 40, 44].

На практике часто встречаются задачи, требующие принятия решений

/

на основе неполных данных. При решении таких задач лицо, принимающее решения, (далее будем обозначать его ЛПР) пытается в процессе управления обеспечить достижение целей, не зная заранее, какие действия приведут к их достижению. Хорошо, если есть возможность предварительно изучить среду, в которой ведется управление, определить ее реакцию на различные действия ЛПР. В таком случае можно было бы заранее задать последовательность действий, ведущую к достижению целей управления. Но что делать, если предварительное изучение системы невозможно, например, по временным или экономическим соображениям? В таком случае оценка параметров системы перестает быть самостоятельной задачей и становится лишь вспомогательной процедурой в процессе достижения цели управления.

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

качестве дохода. На каждом этапе управления п (мы также будем употреблять термин «шаг») ЛПР может выбрать одно из двух возможных действий. Доход зависит только от выбранного па данном шаге действия. Доходы имеют нормальные распределения с математическими ожиданиями 1щ и Ш9 для первого и второго действия соответственно и единичными дисперсиями. Математические ожидания т\ и то заранее не известны ЛПР. Цель управления

состоит в максимизации дохода в некотором смысле [10, 13].

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

Среда, в которой ведется управление, может быть описана векторным параметром в = (?П1,?П2). При этом, если бы параметры среды были известны заранее, то оптимальная стратегия предписывала бы всегда выбирать действие, которому соответствует большее из значений т\, т^. Ожидаемый доход от применения такой стратегии составил бы Nтах.(т\,т<2). Если же параметр неизвестен, то функция

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

Над аналогичными задачами работало несколько групп исследователей, поэтому для них существует несколько различных названий и подходов. В западной литературе у задачи появилось название «задача о двуруком бандите» [68]. Суть задачи: есть некоторый игральный автомат с двумя ручками. За одну игру с автоматом игрок может дернуть одну из двух ручек. Автомат с какой-то вероятностью выдаст игроку единичный выигрыш. Вероятность выигрыша для каждой ручки постоянна, но не известна игроку. Цель — получить максимальный суммарный выигрыш за заданное количество игр. Такая постановка задачи часто называется «бернуллиевским двуруким бандитом» [10, 13, 39, 46, 52] из-за характера распределения доходов за применение ручек.

(1)

ром в [10].

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

Рассмотрим причину выбора нормального распределения. Будем рассматривать описанный выше процесс управления в применении к обработке некоторых данных. Для обработки каждой единицы таких данных может быть выбран один из двух способов. Есть два возможных результата такой обработки: «успешная обработка» и «неуспешная обработка». Будем считать, что нам необходимо обработать очень большое количество данных. В этом случае стратегия последовательного управления требует для такой обработки достаточно много времени.

Изменим стратегию управления, а именно разобьем все данные на несколько групп, и ко всем данным в группе будем применять один и тот же способ обработки. Количество данных, обработанных успешно, в каждой группе в силу центральной предельной теоремы будет иметь распределение, близкое к нормальному. Поэтому для таких групп данных мы можем использовать описанную выше модель управления, используя количество успешно обработанных данных в качестве результата обработки группы. Разбиение данных на группы с одинаковым способом обработки может быть полезно в случае, если изменение способа обработки — дорогая операция, также оно позволяет ввести их параллельную обработку (что позволяет сократить время, необходимое для обработки). При этом важно, что при достаточно большом числе этапов управления (30 - 50) потери при параллельной обработке уже будут близки к потерям для обработки таких данных последовательно [10, 13].

Есть несколько подходов к данной задаче. Один из них — это минимаксный подход. При таком подходе находится стратегия управления, приводящая к наименьшим потерям для наихудшего значения параметра среды. Нас будет

интересовать множество допустимых параметров среды

0 = {(тът2) : \тгц - ш2| < 2с}, (2)

где с — некоторая константа (0 < с < оо). В таком случае минимаксный риск будет равен:

Я#(6) =т£вир Ьм{а,в). (3)

Е е

Главным достоинством минимаксного подхода является его робастность, то есть устойчивость при значительном отклонении входных параметров от ожидаемых значений. Действительно, в рассматриваемой постановке ожидаемые потери не превысят значения минимаксного риска для любых 9 из ©.

Актуальность темы исследования. Алгоритмы, решающие описанные выше задачи, могут быть использованы для получения стратегий управления в случае зашумления результатов экспериментов или недостоверной информации о среде. При этом главной целью управления является получение максимального «дохода», а не уточнение параметров среды.

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

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

Стратегии, получение которых описано в данной диссертации, имеют пороговый характер и для их хранения требуется некоторый объем памяти. Применение такой пороговой стратегии — простая задача, которая может быть реализована даже на устройствах с очень ограниченными ресурсами. Для

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

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

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

1. Создание модели параллельной обработки данных с использованием групп различного размера.

2. Создание численного метода нахождения оптимальных размеров групп для параллельной обработки данных.

3. Исследование способов упрощения стратегий и влияния упрощений на полученные доходы.

4. Разработка комплекса программ для исследования параллельной обработки.

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

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

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

Положения, выносимые на защиту. На защиту выносятся следующие положения:

1. Модель двухальтернативной параллельной обработки данных с группами различного размера.

2. Численный метод поиска оптимальных размеров групп для параллельной обработки данных.

3. Численные методы упрощения стратегий параллельной обработки данных.

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

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

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

Основные результаты диссертации докладывались на следующих конференциях:

1. XIX научная конференция преподавателей, аспирантов и студентов НовГУ, 2-7 апреля 2012 г., Великий Новгород.

2. 8-я международная Петрозаводская конференция «Вероятностные методы в дискретной математике», 2-9 июня 2012 г., Петрозаводск.

3. 55-я научная конференция МФТИ «Проблемы фундаментальных и прикладных естественных и технических наук в современном информационном обществе», 19 - 25 ноября 2012 г., Долгопрудный, Московская обл.

4. XX Всероссийская Школа-коллоквиум по стохастическим методам/ХГУ Всероссийский симпозиум по прикладной и промышленной математике, 12 - 18 мая 2013 г., Йошкар-Ола.

5. XIV Всероссийский симпозиум по прикладной и промышленной математике, 29 сентября - 5 октября 2013 г., Великий Новгород.

6. 56-я научная конференция МФТИ «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе», 25 - 30 ноября 2013 г., Долгопрудный, Московская обл.

А также на следующих семинарах:

1. Семинар кафедры прикладной математики и информатики Новгородского государственного университета им. Ярослава Мудрого, 19 ноября 2013 г., Великий Новгород.

Публикации. Материалы диссертации опубликованы в 9 печатных работах, из них 2 статьи в рецензируемых журналах, рекомендованных ВАК [16, 24],

1 статья в сборнике трудов конференций [21], 1 депонированная рукопись [15] и 5 тезисов докладов [17, 22, 23, 25, 26].

«Программа поиска оптимальных размеров групп данных для параллельной обработки» из представленного комплекса программ зарегистрирована в Реестре программ для ЭВМ №2013614359 от 29.04.2013.

Структура и объем диссертации. Диссертация состоит из введения, 3 глав, заключения и списка литературы. Во введении отражена актуальность работы, приведено краткое описание задачи о целесообразном поведении в случайной среде, обоснована новизна работы, показана практическая значимость результатов.

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

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

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

В заключении представлен общий обзор результатов работы.

Общий объем диссертации — 111 страниц, включая 18 рисунков. Список литературы содержит 69 наименований.

12

Глава 1

Теоретические основы

1.1. Краткий обзор литературы

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

1.1.1. Автоматный подход

В 60-е годы инициатором развития автоматного подхода в Советском Союзе был М. Л. Цетлин, который написал ряд статей о целесообразном поведении в случайной среде, например [33, 34].

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

Под случайной внешней средой в данном случае понимается модель внешнего мира, в котором есть несколько возможных действий организма и все возможные реакции среды делятся на два класса: благоприятные («не штраф») и неблагоприятные («штраф»). Каждый из исходов (реакций среды) может случиться с какой-то вероятностью, априорно не известной организму.

Таким образом, рассматривается автомат, заданный каноническими уравнениями:

где £ = 1,2,... имеет смысл времени и принимает целочисленные значения

т =

(1.1)

(1.2)

(дискретное время), й(£) — входная переменная, которая может принимать только значения «выигрыш» и «проигрыш», /(ж) — выходная переменная, может принимать к различных значении, при этом различные значения данной переменной обычно называют действиями, ф(¿) характеризует состояние автомата в момент времени Количество различных состояний называют объемом памяти автомата.

Целесообразным поведением обладает автомат, для которого математическое ожидание выигрыша выше, чем для автомата, который совершает свои действия равновероятно, независимо от реакции среды [2, 35]. Для такого автомата математическое ожидание доходов равно

где к — количество выходных сигналов автомата, называемых действиями, агп

— вероятность благоприятного исхода при выборе ш-го действия.

К автоматному подходу относится термин «симметрический автомат»

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

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

Различными исследователями было предложено несколько различных вариантов автоматов. Один из них — автомат с линейной тактикой. В простейшем случае он имеет два состояния: «выбирать первое действие» и «выбирать второе действие». Если после выбора действия результат благоприятный — автомат остается в текущем состоянии, если нет — переходит в другое. В [35] показано, что даже такой автомат обладает целесообразным поведением.

Автоматы с линейной тактикой имеют как правило более сложную структуру: вместо двух состояний у таких автоматов две ветви состояний. При

(1.3)

благоприятной реакции автомат переходит в более глубокое состояние текущей ветви, в противном случае — в менее глубокое (в случае, если автомат уже находится в первом состоянии данной ветви, он переходит в первое состояние противоположной).

Исследование зависимости целесообразности поведения таких автоматов от объема внутренней памяти показало, что при увеличении размера памяти простого линейного автомата математическое ожидание выбора лучшего варианта также увеличивается. В [35] такая последовательность называется асимптотически-оптимальной последовательностью конечных автоматов.

Похожей структурой обладает автомат Роббинса-Кринекого [19] («доверчивый» автомат). Отличительной особенностью такого автомата является поведение в случае благоприятного исхода. В этом случае он переходит в самое глубокое состояние па ветви состояний, в которых выбирается опробованное действие.

Как показали предыдущие исследования, увеличение размера памяти линейного и «доверчивого» автомата увеличивает вероятность благоприятной реакции. Однако такие автоматы нельзя просто наделить бесконечным количеством состояний — в таком случае их поведение перестает быть целесообразным. Например, автомат Роббпнса-Кринского при благоприятной реакции должен будет сразу уйти в бесконечное состояние.

Одним пз способов решения этой проблемы являются автоматы с растущей памятью [9]. Емкость памяти таких автоматов растет вместе с увеличением номера этапа управления.

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

«Автомат с переменной структурой» Варшавского и Воронцовой описывается при помощи системы стохастических матриц переходов Р(3) = Цтг^-Ц- При этом значения подстраиваются в зависимости от воздействий среды для того, чтобы обеспечивать большую частоту выбора благоприятного варианта.

Целесообразность такого автомата была изначально проверена только при помощи моделирования на ЭВМ (хотя в статье [5] можно найти аналитические соображения по поводу целесообразности данного автомата в стационарной случайной среде). В более поздней работе [20] показано, что стохастический автомат Варшавского и Воронцовой (а также ряд других стохастических автоматов) не гарантирует с вероятностью 1 оптимального поведения в произвольной среде.

Автоматному подходу посвящено большое количество работ. Этот подход развит в различных направлениях, например [2, 35]:

1. Коллективное поведение автоматов (игры автоматов). В общем виде рассматриваются вопросы коллективного поведения автоматов, теория игр же используется как удобный аппарат для описания взаимодействия нескольких субъектов. Однако рассмотрение игр автоматов отличается от принятого в теории игр. Обычно в теории игр игроки заранее знают систему платежных функций игры и выбирают стратегию, пользуясь этой информацией и различными вычислительными методами. В описываемой же постановке рассматриваются игры, о которых у игроков нет априорной информации. Вследствие этого игроки вынуждены выбирать свою стратегию не заранее, а прямо во время игры. При этом предполагается, что игра состоит из многократно повторяющихся партий, таким образом автоматы могут получать данные о возможных результатах применения стратегий на основе предыдущих игр (игры автоматов также рассматриваются, например, в [4, 6]).

2. Поведение автоматов в средах, не являющихся стационарными. Например,

поведение автоматов в составной случайной среде (среда, в которой

значения параметров описываются ценыо Маркова).

3. Задачи с непрерывным временем.

Инженерному применению автоматного подхода к прикладным задачам посвящена книга Д. А. Поспелова [30]. В ней рассмотрены вопросы синтеза автоматов с нужными свойствами и исследование поведения вероятностных автоматов в различных средах. Главная цель книги — описание применения вероятностных автоматов на практике.

В [30] также собраны некоторые возможные приложения автоматов. К ним отнесены: регулирование движения через автомобильный перекресток, распределение потока задач в мультипрограммной системе, система управления обслуживанием в периодическом режиме, система управления многокаскадной схемой коммуникации.

Работы, посвященные автоматному подходу, не ограничиваются только бинарным распределением реакции среды, например в [27] рассмотрен вариант с тремя различными реакциями («поощрением», «наказанием» и «безразличием»). Кроме того, можно преобразовать небинарные среды в бинарные при помощи генератора случайных чисел и использовать для получившихся сред автоматы, описанные выше. Подробнее такое преобразование описано, например, в [20].

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

поведение автоматов или игры автоматов). Данный подход проигрывает другим направлениям, также не в его пользу говорит тот факт, что автоматный подход не нашел широкого применения на практике, несмотря на полувековую историю.

1.1.2. Адаптивное управление

После автоматного подхода следует более общая теория, а именно теория адаптивного управления.

Направление адаптивного управления в нашей стране активно развивалось В. Г. Сраговичем [32, 64]. В [32] предлагается использовать идентификационный подход, основанный на идее оценки математических ожиданий доходов т1 и 7П2 за применение первого и второго действия соответственно. Далее предложенная стратегия предписывает преимущественный выбор того действия, которому соответствует большая оценка. Оценка математических ожиданий производится по следующим правилам:

ггц{п) = —, тп2(п) - —, (1.4)

Щ П2

где 77-1 и Щ ~~ количество шагов (этапов управления), на которых было выбрано первое или второе действие соответственно, п — общее число этапов управления (очевидно, что п — щ 712). Х\ и Х2 — суммарные доходы за применение первого и второго действия соответственно.

При получении таких оценок появляется желание сразу же воспользоваться стратегией «Р1ау-Ше-1еас1ег». Данная стратегия предлагает сначала провести исследование действий, выбрав каждое по к раз, а затем всегда выбирать то действие, которому соответствует большая оценка. Однако можно заметить, что такой вариант является неоптимальным если полное время управления неограничено.

Действительно, допустим что т\ > т2, однако на первых 2к шагах в силу случайности доходов среднее значение для первого действия оказалось

меньше, чем т2 {т\ < тг). В таком случае стратегия будет предписывать выбирать второе действие и оценка для него будет приближаться к действительному значению Ш2- Если т\ «С гаг, может получиться, что оценка для второго действия никогда не станет меньше оценки для первого и будет всегда выбираться субоптимальное действие.

В [32] предложен а-автомат. Упрощенно реализуемую им стратегию можно описать так: на первом этапе каждое действие выбирается по к раз, затем управление ведется в соответствии с полученными оценками. При этом с вероятностью 5 будет выбираться действие, которому соответствует меньшая оценка. Действие, которому соответствует ббльшая оценка, будет выбрано, соответственно, с вероятностью (1 — 6). После каждого шага оценка для выбранного действия корректируется.

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

В качестве усовершенствования предложен также ¿»(^-автомат. Он отличается применением действий с вероятностями 5п и (1 — 6п), где п — номер шага. 5п выбирается экспертом, при этом для того, чтобы ¿си-автомат был асимптотически оптимальным, необходимо, чтобы она соответствовала следующим условиям:

Важным преимуществом ¿¿¿-автомата является возможность подстраиваться под горизонт управления.

Список литературы диссертационного исследования кандидат наук Олейников, Андрей Олегович, 2014 год

Список литературы

1. Беллман Р. Динамическое программирование. Москва: Иностранной литературы, 1960. С. 400.

2. Варшавский В. И. Коллективное поведение автоматов. Москва: Наука, 1973. С. 408.

3. Варшавский В. И., Воронцова И. П. Поведение стохастических автоматов с переменной структурой // Автоматика и телемеханика. 1963. Т. 24, № 3. С. 353-360.

4. Варшавский В. И., Поспелов Д. А. Оркестр играет без дирижера: размышления об эволюции некоторых технических систем и управления ими. Москва: Наука, 1984. С. 208.

5. Воронцова И. П. Алгоритмы изменения переходных вероятностей стохастических алгоритмов // Проблемы передачи информации. 1965. Т. 1, № 3. С. 122-126.

6. Гинзбург С. Л., Цетлин М. Л. О некоторых примерах моделирования коллективного поведения автоматов // Проблемы передачи информации. 1965. Т. 1 Вып. 2. С. 54-62.

7. Де Гроот М. Оптимальные статистические решения. Москва: Мир, 1974. С. 491.

8. Дынкин Е. В., Юшкевич А. А. Управляемые марковские процессы и их приложения. Москва: Наука, 1975. С. 340.

9. Колногоров А. В. Асимптотически оптимальные в стационарной среде автоматы с растущей памятью // Автоматика и телемеханика. 1984. № 9. С. 129-137.

10. Колногоров А. В. Нахождение минимаксных стратегии и риска в случайной среде (задаче о двуруком бандите) // Автоматика и телемеханика. 2011. Т. 5. С. 127-138.

11. Колногоров А. В. Нахождение минимаксных стратегий и риска в трехаль-

тернативной случайной среде // Вестник НовГУ. 2011. № 65. С. 76-79.

12. Колногоров А. В. Задача о двуруком бандите для систем с параллельной обработкой данных // Проблемы передачи информации. 2012. Т. 48 Вып.

1. С. 83-95.

13. Колногоров А. В. Робастное параллельное управление в случайной среде (задаче о двуруком бандите) // Автоматика и телемеханика. 2012. Т. 4. С. 114-130.

14. Колногоров А. В. Управление в случайной среде. Великий Новгород: ФГБОУ «Новгородский государственный университет им. Ярослава Мудрого», 2013. С. 87.

15. Колногоров А. В., Олейников А. О. О робастном управлении в случайной среде. Деп. в ВИНИТИ № 317-В2011 от 01.07.2011. С. 17.

16. Колногоров А. В., Олейников А. О. Оптимизация параллельной многоэтапной обработки в случайной среде // Вестник НовГУ. 2012. К5 68. С. 67-69.

17. Колногоров А. В., Олейников А. О. Оптимизация параллельной многоэтапной обработки в случайной среде // Обозрение прикладной и промышленной математики. 2012. Т. 19, вып. 2. С. 210-211.

18. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. Второе издание. Москва, Санкт-Питербург, Киев: Вильяме, 2005. С. 1296.

19. Кринский В. И. Асимптотичеси оптимальный автомат с экспоненциальной скоростью сходимости // Биофизика. 1964. Т. 9 Вып. 4. С. 484 487.

20. Назин А. В., Позняк А. С. Адаптивный выбор вариантов. Москва: Наука, 1986. С. 288.

21. Олейников А. О. О робастном управлении в случайной среде // Материалы докладов аспирантов, соискателей, студентов: XIX научная конференция преподавателей, аспирантов и студентов НовГУ 2-7 апреля 2012 года. Часть

2. 2012. С. 78-80.

22. Олейников А. О. Получение упрощенных стратегий для параллельной обра-

ботки в случайной среде численными методами // Обозрение прикладной и промышленной математики. 2013. Т. 20, вып. 4. С. 565.

23. Олейников А. О. Способы получения упрощенных стратегий для параллельной обработки в случайной среде // Обозрение прикладной и промышленной математики. 2013. Т. 20, вып. 2. С. 149.

24. Олейников А. О. Численная оптимизация параллельной обработки в стационарной случайной среде // Труды КарНЦ РАН. 2013. Т. 1. С. 73-78.

25. Олейников А. О., Колногоров А. В. Численная оптимизация групп данных для параллельной обработки в стационарной случайной среде // Труды 55-й научной конференции МФТИ. Управление и прикладная математика. 2012. Т. 1. С. 92-93.

26. Олейников А. О., Колногоров А. В. Получение упрощенных стратегий для параллельной обработки в случайной среде с различными размерами групп // Труды 56-й научной конференции МФТИ. Управление и прикладная математика. 2013. Т. 1. С. 84-85.

27. Пальцев Е. И. Поведение конечных автоматов при трех типах реакции стационарной случайной среды // Проблемы передачи информации. 1975. Т. 9 Вып. 3. С. 61-69.

28. Печников А. А., Чернобровкин Д. И. Адаптивный краулер для поиска и сбора внешних гиперссылок // Управление большими системами: сборник трудов. 2012. № 36. С. 301-315.

29. Полак Э. Численные методы оптимизации. Единый подход. Москва: Мир, 1974. С. 376.

30. Поспелов Д. А. Вероятностные автоматы. Москва: Энергия, 1970. С. 88.

31. Пресман Э. Л., Сонин И. Э. Последовательное управление по неполным данным. Москва: Наука, 1982. С. 256.

32. Срагович В. Г. Адаптивное управление. Москва: Наука, 1981. С. 384.

33. Цетлин М. Л. О поведении конечных автоматов в случайных средах // Автоматика и телемеханика. 1961. Т. 22, № 10. С. 1345-1354.

34. Цетлин М. JI. Конечные автоматы и моделирование простейших форм поведения // Успехи математических наук. 1963. Т. 18, №4(112). С. 3-28.

35. Цетлин М. JI. Исследования по теории автоматов и моделированию биологических систем. Москва: Наука, 1969. С. 316.

36. Agrawal R. Sample mean based index policies with О log n regret for the multiarmed bandit problem // Advances in applied probability. 1995. Vol. 27, no. 4. P. 1054-1078.

37. Auer P., Cesa-Bianchi N., Fischer P. Finite-time Analysis of the Multiarmed Bandit Problem // Machine Learning. 2002. Vol. 47. P. 235-256.

38. Bather J. A. The Minimax Risk for the Two-Armed Bandit Problem // Mathematical Learning Models Theory and Algorithms. 1983. Vol. 20. P. 1-11.

39. Berry D. A. A Bernoulli two-armed bandit // The Annals of Mathematical Statistics. 1972. Vol. 43, no. 3. P. 871-897.

40. Berry D. A., Fristedt B. Bandit problems. London, New York: Chapman and Hall, 1985. P. 275.

41. Cesa-Bianchi N., Lugosi G. Prediction, Learning, and Games. New York: Cambridge University Press, 2006. P. 394.

42. Cheng Y. Multistage decision problems // Sequential analysis. 1994. Vol. 13(4). P. 329-349.

43. DeGroot M. H. Optimal statistical decisions. McGraw-Hill Company, 1970. P. 489.

44. Fabius J., van Zwet W. R. Some remarks on the two-armed bandit // The Annals of Mathematical Statistics. 1970. Vol. 41, no. 6. P. 1906 1916.

45. Feldman D. Contributions to the "two-armed bandit "problem / / The Annals of Mathematical Statistics. 1962. Vol. 33. P. 847-856.

46. Ginebra J., Clayton M. K. Small-sample performance of Bernoulli two-armed bandit Bayesian strategies // Journal of Statistical Planning and Inference. 1999. Vol. 79, no. 1. P. 107-122.

47. Gittins J., Glazebrook K., Weber R. Multi-armed Bandit Allocation Indices, 2nd Edition. Wiley, 2011. R 410..

48. Gittins J. C. Bandit Processes and Dynamic Allocation Indices // Journal of the Royal Statistical Socicty. Series B. 1979. Vol. 41, no. 2. P. 148-177.

49. Glazebrook K., Kirkbride C., Hodge D., Minty J. Stochastic scheduling: A short history of index policies and new approaches to index generation for dynamic resource allocation // Journal of Scheduling. 2013. P. 19.

50. Juditsky A., Nazin A. V., Tsybakov A., Vayatis N. Gap-free Bounds for Stochastic Multi-Armed Bandit // Proceedings of the 17th World Congress The International Federation of Automatic Control Seoul, Korea, July 6-11, 2008. 2008. P. 4.

51. Kaelbling L. P., Littman M. L., Moore A. W. Reinforcement learning: a survey // Journal of Artificial Intelligence Research. 1996. Vol. 4. P. 237-285.

52. Kolnogorov A. V. Determination of the Minimax Risk for the Normal Two-Armed Bandit // Proc. of the IFAC Workshop "Adaptation and Learning in Control and Signal Processing ALCOSP 2010", Antalya, Turkey, August 26-28, 2010. DOI10.3182/20100826-3-TR-4015.00044. 2010.

53. Lai T. L. Adaptive Treatment Allocation and the Multi-Armed Bandit Problem // The Annals of Statistics. 1987. Vol. 25. P. 1091-1114.

54. Lai T. L., Levin B., Robbins H., Siegmund D. Sequential medical trails (stopping rules/asymptotic optimality) // Proceedings of the National Academy of Sciences of the USA. 1980. Vol. 77, no. 6. P. 3135-3138.

55. Lai T. L., Robbins H. Asymptotically Efficient Adaptive Allocation Rules // Advances in Applied Mathematics. 1985. Vol. 6. P. 4-22.

56. Li L., Chu W., Langford J., Schapire R. E. A contextual-bandit approach to personalized news article recommendation // Proceedings of the 19th international conference on World wide web. WWW '10. New York, NY, USA: ACM, 2010. P. 661-670. URL: http://doi.acm.org/10.1145/1772690.1772758.

57. Nazin A., Miller B. Mirror Decent Algorithm for a Multi-Armed Bandit

Governed by a Stationary Finite State Markov Chain // Proceedings of the 2013 European Control Conference (ECC) July 17-19, 2013, Zurich, Switzerland. 2013. P. 5.

58. Nazin A. V., Miller B. The Mirror Descent Control Algorithm for Weakly Regular Homogeneous Finite Markov Chains with Unknown Mean Losses // Proceedings of 50th IEEE CDC ECC, Orlando, Florida, USA, 2011, December 12-15. 2011. P. 5.

59. Polak E. Computational Methods in Optimization: A Unified Approach. New York, London: Academic Press, 1971. P. 329.

60. Robbins H. Some aspects of the sequential design of experiments // Bulletin AMS. 1952. Vol. 58(5). P. 527-535.

61. Schraudolph N. N. A Fast, Compact Approximation of the Exponential Function // Neural computation. 1999. Vol. 11, no. 4. P. 853-862.

62. Scott S. L. A modern Bayesian look at the multi-armed bandit // Applied Stochastic Models in Business and Industry. 2010. Vol. 26, no. 6. P. 639-658.

63. Sonin I. M. A generalized Gittins index for a Markov chain and its recursive calculation // Statistics and Probability Letters. 2008. Vol. 78. P. 1526-1533.

64. Sragovich V. G. Mathematical Theory of Adaptive Control. Singapore: World Scientific, 2006. P. 473.

65. Sutton R. S., Barto A. G. Reinforcement Learning: An Introduction. Cambridge: MIT Press, 1998. P. 322.

66. Thompson W. R. On the likelihood that one unknown probability exceeds another in view of the evidence of two samples // Biometrika. 1933. Vol. 25, no. 3/4. P. 285-294.

67. Vogel W. An asymptotic minimax theorem for the two armed bandit problem // The Annals of Mathematical Statistics. 1960. Vol. 31, no. 2. P. 444-451.

68. Vogel W. A sequential design for the two armed bandit // The Annals of Mathematical Statistics. 1960. Vol. 31, no. 2. P. 430-443.

69. Witmer J. A. Bayesian multistage decision problems // The Annals of Statistics.

1986. Vol. 14, no. 1. P. 283-297.