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

• Лазутченко, Алексей Николаевич
• кандидат наук
• 2016

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

Содержание

Введение

Глава 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. Моделирование двухпороговой стратегии в бинарной случайной среде

2.10. Двухпороговая стратегия управления в случайной среде с нормально распределенными доходами

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

Глава 3. Управление в случайной среде, использующее основную

теорему теории игр

3.1. Связь минимаксного и байесовского подходов и основная теорема теории игр

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

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

3.4. Моделирование методом Монте-Карло

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

3.6. Случай попарно различных дисперсий

3.7. Численная оптимизация байесовских рисков при различных попарно разных дисперсиях

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

Глава 4. Программный комплекс

4.1. Программа TwoArmed

4.2. Программ Bayes

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

Заключение

Литература

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

Введение

В различных областях человеческой деятельности с каждым годом всё большую актуальность получают задачи управления в условиях неопределенности. Это могут быть задачи целесообразного управления в случайных средах [3, 39, 40], адаптивного управления [29, 37, 61], о двуруком бандите [36, 48].

Управление в случайной среде — сравнительно молодое направление в науке. За рубежом оно возникло в 50-е годы в результате исследований американского статистика Г. Роббинса [59] и получило в дальнейшем название задачи о двуруком бандите [48]. Двурукий бандит — это игральный автомат с двумя ручками. Выбор любой из ручек сопровождается случайным доходом игрока, распределение которого зависит только от выбираемой в текущий момент времени ручки, фиксированы, но неизвестны игроку. Цель управления состоит в максимизации математического ожидания итогового дохода. В нашей стране это направление развивалось независимо в 60-х годах и прежде всего связано с именем советского кибернетика Цетлина, который рассматривал задачу целесообразного поведения биологических систем. Хорошим примером может являться поведение крысы в Т-образном лабиринте. При движении по лабиринту крыса может повернуть налево или направо. В конце лабиринта её в обоих случаях с некоторыми вероятностями ожидает слабый удар током. Эти вероятности фиксированы. Эксперименты показали, что крысы обучаются поворачивать туда, где вероятность удара меньше.

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

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

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

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

Актуальность темы исследования. Наиболее известным приложением задач управления в условиях неопределенности является задача о лечении пациентов, когда имеются два альтернативных лекарства с фиксированными, но неизвестными эффективностями. Требует организовать лечение таким образом, чтобы математическое ожидание выздоровевших в результате лечения пациентов было максимальным ([55, 62]). Другое известное приложение — оптимизация обработки данных двумя альтернативными методами с фикси-

рованными, но априори неизвестными эффективностями ([60]). Отметим, что при решении этих задач может использоваться параллельная обработка. В задачах лечения пациентов количество этапов параллельной обработки является небольшим, обычно два, редко три-четыре. В задачах же обработки данных допускается большое число этапов, например, 30-50. Так как данные при параллельной обработке суммируются, то в силу центральной предельной теоремы для управления используются нормально распределенные значения доходов. В зависимости от рассматриваемой постановки задачи дисперсии этих доходов могут иметь попарно одинаковые или различные значения.

Наиболее известными постановками цели управления являются минимаксная и байесовская. Достоинством байесовского подхода ([36, 48]) является то, что он позволяет для любого априорного распределения найти байесовские стратегии и риск численными методами. Недостатком подхода является отсутствие ясных критериев выбора априорного распределения. Достоинством минимаксного подхода является его робастность, а недостатком — сложность нахождения робастных алгоритмов, поскольку прямые методы нахождения их отсутствуют. Примерами робастных алгоритмов являются алгоритм на основе метода стохастической аппроксимации ([29]) и алгоритм зеркального спуска ([5, 43]). Отметим, что версии этих алгоритмов, допускающие параллельную обработку, насколько нам известно, не разрабатывались.

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

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

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

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

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

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

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

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

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

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

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

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

Связь работы с научными программами, темами. Основные результаты диссертации были получены в рамках выполнения исследований при финансовой поддержке Программы стратегического развития Новгородского государственного университета им. Ярослава Мудрого и Проектной части государственного задания в сфере научной активности Министерства образования и науки Российской Федерации, проект № 1.949.2014/К.

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

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

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

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

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

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

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

1. XVI, XVII, XVIII, XIX, XXIII научные конференции преподавателей, аспирантов и студентов НовГУ, 2009-2016 гг., Великий Новгород.

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

3. 57-я международная научная конференция МФТИ «Актуальные проблемы фундаментальных и прикладных наук в современном информационном обществе», 24 — 29 ноября 2014 г., Долгопрудный, Московская обл.

4. 58-я научная конференция МФТИ с международным участием, 23 — 28 ноября 2015 г., Долгопрудный, Московская обл.

5. IX Международная Петрозаводская конференция «Вероятностные методы в дискретной математике», 30 мая — 3 июня 2016 г., Петрозаводск, Россия.

А также на семинарах кафедры прикладной математики и информатики Новгородского государственного университета имени Ярослава Мудрого.

Результаты исследований внедрены в учебный процесс Новгородского государственного университета имени Ярослава Мудрого в рамках дисциплины «Модели искусственного интеллекта».

Публикации. Материалы диссертации опубликованы в 11 печатных работах, из них 4 статьи в рецензируемых журналах, рекомендованных ВАК [17-20], 3 статьи в сборниках трудов конференций [21-23] и 4 тезиса докладов [24-27].

Комплексы программ:

Свидетельство о государственной регистрации программы для ЭВМ «Оптимизация параметров пороговой стратегии управления в случайной среде» № 2012614942, зарегистрирована в Реестре программ для ЭВМ 1 июня 2012 г.

Свидетельство о государственной регистрации программы для ЭВМ «Моделирование случайных сред с одно- и двухпороговой стратегиями управления в случайной среде» № 2013617255, зарегистрирована в Реестре программ для ЭВМ 06 августа 2013 г.

Свидетельство о государственной регистрации программ для ЭВМ «Расчет байесовских рисков, потерь и стратегий управления для случайных сред с нормально распределенными доходами с произвольными дисперсиями» № 2016619416, зарегистрирована в Реестре программ для ЭВМ 18 августа 2016 г.

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

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

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

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

Во второй главе рассматриваются пороговая и двухпороговая стратегии управления в случайных средах с бинарными и нормально распределенными доходами. Пороговая стратегия была предложена и исследована Фогелем [63]. В данной работе известная теоретическая верхняя оценка минимаксного риска улучшена численными методами для бинарной среды. Такая же оценка получена для сред с нормально распределенными доходами. Показано, что такие среды возникают при использовании параллельной обработки данных. Далее была предложена и исследована двухпороговая стратегия управления, которая минимизируют средние потери на заданном априорном множестве параметров сред с бинарными и нормально распределенными доходами. Обоснована целесообразность такой стратегии. Приводятся результаты численного моделирования. С помощью метода Монте-Карло установлено, что минимаксная пороговая стратегия, полученная для сред с единичными дисперсиями, остается таковой и для сред с дисперсиями, не превосходящих единичную. Кроме того, рассмотрены два метода оптимизации алгоритма, направленные на снижение времени расчетов без уменьшения точности результатов.

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

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

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

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

Общий объем диссертации 96 страниц, включая 24 рисунка и 3 таблицы. Список литературы включает 64 наименования.

13

Глава 1 Теоретические сведения

В данной главе приводится краткий обзор литературы, который приводит к постановке задачи о робастных параллельном управлении в случайной среде. После этого вводится общая постановка задачи по исследуемой в диссертации проблеме. Рассматриваются два подхода к решению этой задачи, минимаксный и байесовский. Также в этой главе рассмотрен важный вопрос, для каких сред достигаются наибольшие потери дохода. Показано, что для случайных сред с нормально распределенными доходами, математические ожидания которых значительно различаются, максимальные потери имеют порядок 1п Т, где Т — горизонт управления. Если же они различаются мало, то потери имеют порядок Т !/2.

1.1. Обзор литературы по теме

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

Инициатором автоматного подхода, прежде всего, был советский кибернетик М. Л. Целина, который опубликовал ряд работ о целесообразном поведении в случайных средах, например [39, 40], позднее была издана книга [41]. Этот подход позднее развивался, например, в работах [3, 4, 15, 16, 34].

Задача о целесообразном поведении возникла из попыток объяснить поведение некоторых живых организмов, например, крыс. Исследовалось поведение животного в Т-образном лабиринте. При движении по лабиринту крыса может свернуть налево или направо. В обоих направлениях её ожидает слабый удар током с некоторыми различными фиксированными вероятностями. Эксперименты показали, что крысы обучаются сворачивать в том направлении, где вероятность удара током меньше. Для описания такого поведения были

использованы автоматы.

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

(1.1)

/ (() = F (фЦ)),

где £ — дискретное время, й — входная переменная, принимающая значения 0 и 1, интерпретируемые как проигрыш и выигрыш, /(¿) — выходная переменная — действия автомата, ф(Ъ) — состояние автомата в момент времени

Математическое ожидание выигрыша W для автомата А, совершающего действия равновероятно, независимо от реакции двухваринатной среды, можно выразить как W(А) = (рх + р2)/2, где рх, р2 — вероятности благоприятного исхода при выборе действия с номерами 1, 2. Автомат обладает целесообразным поведением, если его величина математического ожидания выше, чем W(Л). В дальнейших работах предлагались различные модификации автомата с целесообразным поведением в случайной среде: автомат с линейной тактикой [41], автомат Роббинса-Кринского [15] (стоит отметить, что постановка была получена авторами независимо друг от друга), автомат Крылова [16], автомат Пономарева [34], «автомат с переменной структурой» Варшавского и Воронцовой [3].

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

фи + 1) = ФШ),«(* + 1))

1.1.2. Идентификационный подход

Идентификационный подход к управления в адаптивных системах был предложен в книгах В. Г. Сраговича [37, 38, 61], в которых обобщены его результаты и результаты его учеников.

Идея идентификационного подхода состоит в том, что вероятности выигрыша на действиях среды рх и р2 в каждый момент времени оцениваются по формулам

Л / \ Л Х2

Pi[t) = —, <p2{t) = —, £1 12

где ti, t2 — количество применений действий к моменту времени t = tx + t2 (t1 +12 = t), Xi, X2 — текущие доходы за применение действий.

Стратегией управления может являться следующая. Для получения начальной статистики каждое из действий применяется одинаковое количество п раз. При всех t > 2п с вероятностью 1 — Ö применяется то действие, которому соответствует большая из текущих оценок вероятностей f>1(t), p2(t), а с вероятностью Ö — меньшая из оценок. Здесь Ö > 0 — некоторое малое число.

Чем меньше Ö > 0, тем предельный средний доход выше. Если вместо постоянного Ö > 0 рассмотреть последовательность öt, такую что lim öt = 0,

то

а öt = то, то такая стратегия обеспечит максимально возможное значение t=1

предельного среднего дохода.

В работе [13] рассмотрены адаптивные стратегии, позволяющие достигать цели в условиях информационной неопределенности, основываясь на «обучении» в процессе взаимодействия с некоторым объектом. Работа посвящена теоретическим аспектам адаптивного подхода.

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

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

Из недостатков идентификационного подхода можно отметить отсутствие методов для применения в параллельном управлении.

1.1.3. Алгоритм зеркального спуска

Алгоритм зеркального спуска представляет собой обобщение стандартного метода градиента для задач выпуклой оптимизации в условиях априорной неопределенности. В ряде случаев он имеет преимущество перед другими алгоритмами поиска экстремума при высокой размерности: его гарантируемая скорость сходимости значительно выше. Алгоритм находит применение в прикладных задачах, например: томография [47], классификация [43] и ранжирование [31].

Алгоритм зеркального спуска применяется для решения задач о двуруком бандите для неизвестного горизонта управления. Цели управления в целом те же, что и в других подходах, — уменьшение средних потерь полного дохода.

В работе [53] получена оценка верхней границы потерь, равная:

где Ф(Т) — средние потери доход, Е(Фу) — математическое ожидание средних потерь, ат[п — математическое ожидание потерь за применение лучшего возможного действия, К — количество действий случайной среды, Т — горизонт управления.

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

В работе [30] представлен алгоритм зеркального спуска, направленный на минимизацию средних потерь стохастической системы, функционирующей в непрерывном времени, c потерями, возникающими в случайные моменты скачков пуассоновского процесса с известной интенсивностью. Для алгоритма доказана явная верхняя граница превышения средних интегральных потерь над минимумом. Граница имеет вид С\[Т, где Т — горизонт управления, С — конкретная константа.

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

1.1.4. Алгоритм UCB1

С развитием интернет-технологий появилась необходимость в новых эффективных методах управления в случайной среде. Например, популярные порталы Mail.ru и Yahoo! содержат на своих домашних страницах множество ссылок. Цель состоит в определении ссылок, дающих максимальный CTR (click-through ratio, отношение кликов). Здесь каждый показ ссылки пользователю соответствует применению ручки; каждый клик — успех, положительная реакция среды; не-клик — неудача. Задача алгоритма в том, чтобы как можно быстрее понять, что та или иная ссылка является наиболее посещаемой, и выводить её в заголовок страницы.

Одним из современных методов решения подобных задач является достаточно простой в реализации UCB1 [44, 45] (акроним Upper Confidence Bound, верхний доверительный предел).

Алгоритм следующий:

• Применить каждую ручку один раз;

• Пока продолжается работа, применить ручку ], для которой максимальна

где х^ — средний доход за применение ручки ], п^ — количество применений ручки ], п — общее количество применений всех ручек.

Данный подход используется, например, в [33], где разработан поисковой робот (краулер), предназначенный для сбора исходящих гиперссылок с заданного целевого множества веб-сайтов. Адаптивное поведение краулера, заключающееся в том, что за ограниченное время он должен находить максимально возможное суммарное количество гиперссылок, моделируется как задача о многоруком бандите. Такая постановка задачи позволила применить для её решения известные алгоритмы, эксперименты с которыми показали их зависимость от тематики целевого множества. В работе показано, что для научных сайтов алгоритм ИСБ1 показывает лучшие результаты по сравнению с «тривиальным правилом» и правилом, построенном с использованием индексов Гиттинса.

Список литературы диссертационного исследования кандидат наук Лазутченко, Алексей Николаевич, 2016 год

Литература

1. Афанасьев В. Н. Динамические системы управления с неполной информацией. Алгоритмическое конструирование: // М.: КомКнига. 2006. 170 с.

2. Бусленко Н. П., Шрейдер Ю. А. Метод статистических испытаний и его реализация на цифровых вычислительных машинах // М.: ИФМЛ. 1961. 226 с.

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

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

5. Гасников А. В., Нестеров Ю. Е., Спокойный В. Г. Об эффективности одного метода рандомизации зеркального спуска в задачах online оптимизации // Журнал вычислительной математики и математической физики. 2015. 55:4. С. 582-598.

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

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

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

9. Колногоров А. В., Шелонина Т. Н. Об инвариантности функции потерь для пороговой стратегии поведения в случайной среде // Вестн. Новг. гос. ун-та. 2006. № 39. С. 18-21.

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

11. Колногоров А. В. О стратегии поведения в стационарной среде с неулучша-емой гарантированной оценкой сходимости среднего дохода // АиТ. 1991. выпуск 5. С. 183-186.

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

13. Коновалов М. Г. Об адаптивных стратегиях и условиях их существования // Информ. и ее примен., 2012, том 6, выпуск 4, 18-26

14. Коновалов М. Г. Об одной задаче оптимального управления нагрузкой на сервер // Информ. и ее примен., 2013, том 7, выпуск 4, 34-43

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

16. Крылов В. Ю. Об одном стохастическом автомате, асимптотически-оптимальном в случайной среде // Автоматика и телемеханика 24. 1963. № 9.

17. Лазутченко А. Н. Использование двухпороговой стратегии управления в бинарной случайной среде // Современные проблемы науки и образования. 2013. № 3; URL: www.science-education.ru/109-9552 (дата обращения: 15.09.2015).

18. Лазутченко А. Н. Использование двухпороговой стратегии управления в случайной среде с нормально распределенными доходами // Современные проблемы науки и образования. 2014. № 2; URL: www.science-education.ru/116-12590 (дата обращения: 15.09.2015).

19. Лазутченко А. Н. Минимаксная стратегия управления для класса гауссов-

ских случайных сред с различными дисперсиями // Вестн. Новг. гос. ун-та. Сер.: Физико-математические науки. 2015. № 3(86). часть 2. С. 25-28.

20. Лазутченко А. Н. О робастном управлении в случайной среде, характеризуемой доходами с различными дисперсиями // КарНЦ. Сер.: Математическое моделирование и информационные технологии. 2015. № 10. С. 107-113.

21. Лазутченко А. Н., Колногоров А. В. О робастном управлении в случайной среде, характеризуемой нормальным распределением доходов с различными дисперсиями // Труды 57-й научной конференции МФТИ. Управление и прикладная математика. Т. 1. С. 114-116.

22. Лазутченко А. Н., Колногоров А. В. Минимаксный подход к решению одной из задач о двуруком бандите в случайной среде с нормально распределенными доходами // Труды 58-й научной конференции МФТИ; URL: http://conf58.mipt.ru/static/reports_pdf/214.pdf (дата обращения: 14.12.2015.

23. Лазутченко А. Н. Использование двухпороговой стратегии управления в бинарной случайной среде // Обозрение прикладной и промышленной математики. 2013. Т. 20. вып. 4. с. 557.

24. Лазутченко А. Н. Задача о целесообразном управлении в случайной среде // Тезисы докладов аспирантов, соискателей, студентов. Часть 3. Великий Новгород. 2009. с. 38.

25. Лазутченко А. Н. Задача о целесообразном управлении в случайной среде // Тезисы докладов аспирантов, соискателей, студентов. Часть 3. Великий Новгород. 2010. С. 39-40.

26. Лазутченко А. Н. Задача о целесообразном поведении в случайной среде // Материалы докладов аспирантов, соискателей, студентов. Часть 3. Великий Новгород. 2011. С. 59-62.

27. Лазутченко А. Н. Оптимизация параллельного управления в случайной среде с нормально распределенными доходами и различными дисперсиями // IX Международная Петрозаводская конференция «Вероятностные методы в дискретной математике», 30 мая — 3 июня 2016 г., Петрозаводск, Россия

28. Мазалов В. В. Математическая теория игр и приложения // СПб.: «Лань». 2010. 448 с.

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

30. Назин А. В., Анулова С. В., Тремба А. А. Алгоритм зеркального спуска для минимизации средних потерь, поступающих пуассоновским потоком // Автоматика и телемеханика. 2014. № 6. С. 30-38.

31. Назин А. В., Поляк Б. Т. Рандомизированный алгоритм нахождения собственного вектора стохастической матрицы с применением к задаче Ра§еИ,апк // АиТ. 2011. № 2. С. 131-141.

32. Олейников А. О. Нахождение оптимальных планов параллельного управления в случайной среде в приложении к обработке данных: Дис. ... канд. технич. наук. Петрозаводск. 2014. - 111 с.

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

34. Пономарев В. А. Об одной конструкции конечного автомата, асимптотически-оптимального в стационарной случайной среде // Биофизика 6. 1963. № 6.

35. Прохоров Ю. В., Розанов Ю. А. Теория вероятностей. Основные понятия. Предельные теоремы. Случайные процессы // М.: Наука. 1967. 496 с.

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

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

38. Срагович В. Г. Теория адаптивных систем // М.: Наука. 1976. 320 с.

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

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

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

42. Тихомиров А. С. Введение в Maple: учеб. пособие // сост. А. С. Тихомиров, И. С. Пашков; НовГУ им. Ярослава Мудрого. Великий Новгород. 2007. 121 с.

43. Юдицкий А. Б., Назин А. В., Цыбаков А. Б. и др. Рекуррентное агрегирование оценок методом зеркального спуска с усреднением // Проблемы передачи информации. 2005. Т. 41. № 4. С. 78-96.

44. Auer P. Using Confidence Bounds for Exploitation-Exploration Trade-off's // The Journal of Machine Learning Research. 2003. Vol. 3. P. 397-422.

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

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

47. Ben-Tal A., Margalit T., Nemirovski A. The Ordered Subsets Mirror Descent Optimization Method with Applications to Tomography // SIAM J. Optim. 2001. V. 12. No. 1. P. 79-108.

48. Berry D. A., Fristedt B. Bandit problems. Sequential Allocation of Experiments // London, New York: Chapman and Hall. 1985. P. 275.

49. G. E. P. Box, M. E. Muller. A Note on the Generation of Random Normal Deviates // Ann. Math. Stat. 1958. Vol. 29. № 2. P. 610-611.

50. Brochu E., Hoffman M., Freitas N. Portfolio Allocation for Bayesian Optimization // Uncertainty in Artificial Intelligence. 2011. P. 327-336.

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

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

53. Juditsky A. B., Nazin A. V., Tsybakov A. B., 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. P. 11560-11563.

54. Kuleshov V., Precup D. Algorithms for multi-armed bandit problems // CoRR, arXiv:1402.6028, 2014.

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

56. 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. № 6. P. 3135-3138.

57. 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.

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. Robbins H. Some aspects of the sequential design of experiments // Bulletin AMS. 1952. Vol. 58(5). P. 527-535.

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

61. Sragovich V. G. Mathematical Theory of Adaptive Control // World Scientific. Interdisciplinary Mathematical Sciences. New Jersey. London. v. 4. P. 473

62. Villar S. S. et al. Multi-armed bandit models for the optimal design of clinical trials: benefits and challenges // Statistical Science. 2015. V. 30. №. 2. C. 199-215.

63. Vogel W. An asymptotic minimax theorem for the two-armed bandit problem. // Ann. Math. Stat. 1960. V. 31. P. 444-451.

64. Vogel W. A sequential design for the two armed bandit. // Ann. Math. Stat. 1960. V.31. P. 430-443.