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

ВВЕДЕНИЕ

ГЛАВА

§1.

§1.

§1.

§1.

§1.

§1.

ГЛАВА

§2.

§2.

§2.

§2.

§2.

§2.

§2.

ГЛАВА

§3.

§3.

§3.

§3.

§3.

§3.

§3.

§3.

§3.

О ПОСТАНОВКАХ ЦЕЛИ В ЗАДАЧЕ О ЦЕЛЕСООБРАЗНОМ ПОВЕДЕНИИ В СЛУЧАЙНОЙ СРЕДЕ, ПРИВОДЯЩИХ К МИНИМАКСНОМУ ПОДХОДУ

АВТОМАТНЫЙ ПОДХОД

Постановка задачи и основные результаты

Некоторые вспомогательные результаты

Оценки для отношения произведений вероятностей

Оценка снизу для минимаксного риска

Описание оптимизационных автоматов

Оценки минимаксного риска на классе всех стационарных

Оценки минимаксного риска для автоматов Хеллмана-Ковера

Обсуждение результатов

АПРИОРНЫЙ ВЫБОР ПРОДОЛЖИТЕЛЬНОСТИ ЭТАПОВ ОБУЧЕНИЯ И УПРАВЛЕНИЯ

Постановка задачи и основные результаты

Оценка минимаксного риска и оптимального априорного времени обучения

Пример. Бинарная стационарная среда Оценка квадратичного минимаксного риска и соответствующего оптимального времени обучения Пример. Бинарная стационарная среда Обобщение результатов на случай К>2 Обсуждение результатов

АЛГОРИТМ ОТЫСКАНИЯ МИНИМАКСНЫХ СТРАТЕГИИ И РИСКА ДЛЯ БИНАРНОЙ СТАЦИОНАРНОЙ СРЕДЫ

Постановка задачи и основные результаты

Эквивалентное определение стратегии

Смешанная стратегия и вариация стратегии

Свойства функции потерь и существование минимаксной стратегии

Критерий минимаксной стратегии Свойства минимаксной стратегии

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

§3.10 Байесовские риск и стратегия на конечном множестве параметров

§3.11 Определение минимаксных риска и стратегии на конечном множестве параметров

§3.12 Определение минимаксных риска и стратегии для некоторых значений Т на множестве всех бинарных стационарных сред

§3.13 Определение минимаксных риска и стратегии для некоторых 143 значений Т на множестве бинарных стационарных сред с известной максимальной вероятностью дохода

§3.14 Обсуждение результатов

ГЛАВА 4 АСИМПТОТИЧЕСКИЕ ОЦЕНКИ МИНИМАКСНОГО

И КВАДРАТИЧНОГО МИНИМАКСНОГО РИСКОВ

§4.1 Постановка задачи и основные результаты

§4.2 Неулучшаемые по порядку асимптотические оценки минимаксного риска

§4.3 Уточнение оценки сверху при К=2 на основе моделирования методом Монте-Карло

§4.4 Неулучшаемые по порядку асимптотические оценки квадратичного минимаксного риска

§4.5 О стратегиях поведения на бесконечном отрезке времени, сохраняющих порядок скорости роста функции потерь

§4.6 Обсуждение результатов

О ПОСТАНОВКАХ ЦЕЛИ В ЗАДАЧЕ О ЦЕЛЕСООБРАЗНОМ ПОВЕДЕНИИ В СЛУЧАЙНОЙ СРЕДЕ, ПРИВОДЯЩИХ К МИНИМАКСНОМУ ПОДХОДУ

В настоящее время все большее значение приобретает исследование задач управления с неполной априорной информацией. К их числу относится и задача о целесообразном и/или оптимальном поведении в случайной среде (см. монографии М.Л. Цетлина [65], и В.И. Варшавского [7]). Далее эта задача рассматривается в следующей постановке. Пусть имеются К вариантов (К > 2), называемых также управлениями, или действиями. Выбор любого из вариантов в дискретный момент времени t = 1, 2, 3,. приводит к получению случайного дохода распределение которого зависит только от выбранного варианта, но не зависит от предыстории процесса и момента времени t. Вид распределения дохода в зависимости от выбираемого варианта априори не известен или известен частично, например, содержит неизвестный параметр. Таким образом t = 1,2,3,. есть управляемый случайный процесс, или случайная среда, причем среда с указанной зависимостью распределений от выбираемых вариантов получила название стационарной. Временной интервал, на котором осуществляется управление, может быть как известным конечным, так и бесконечным. Таким образом рассматриваемая задача есть задача об оптимальном управлении с неполной априорной информацией. А сам процесс выбора вариантов, осуществляемый, как правило, на основе известной предыстории управления, обычно трактуют как поведение в случайной среде. Тот факт, что априорные распределения известны не полностью, означает, что алгоритмы управления должны быть применимы ко всем рассматриваемым средам, т.е. должны быть адаптивными, поэтому данную задачу рассматривают также как задачу адаптивного управления (см. монографии В.Г. Сраговича [55], [56], и A.B. Назина и A.C. Позняка [43]). Наконец, отметим, что иногда значения бывает удобнее интерпретировать как потери, а не как доходы.

Рассматриваемая задача широко известна также как задача о "двуруком бандите" (К = 2), или "многоруком бандите" (К > 2). Названия задач происходят от игрального автомата, снабженного двумя или более рукоятками, выбор каждой из которых влияет на величину текущего дохода игрока. В настоящее время эти названия стали общепринятыми (см., например, монографию Д. Берри и Б. Фристедта [68]), поэтому ниже они также будут использоваться, особенно при ссылках на результаты зарубежных авторов.

Приведем несколько примеров. В первом из них предположим, что некоторая система передачи данных может использовать несколько альтернативных методов кодирования передаваемых сообщений для защиты их от помех. Тогда априори неизвестная вероятность появления ошибки в сообщении зависит при заданном режиме работы канала связи только от выбираемого метода кодирования. Здесь методы кодирования информации соответствуют вариантам, текущий момент времени t соответствует номеру передаваемого сообщения, а доход определяется количеством безошибочно переданных сообщений, т.е. £г = 1, если сообщение передано без ошибки и ^ = 0 в противном случае.

Отметим, что в приведенном примере в случае возникновения ошибки при ' передаче данных, которая может быть обнаружена, например, в результате подсчета контрольной суммы, сообщение можно повторить. Это обстоятельство учитывается во втором примере. Предположим, что на кодирование и декодирование сообщений затрачивается некоторое время, зависящее от выбранного метода. Тогда полное время передачи сообщения т, включающее его кодирование, собственно передачу, декодирование и повторные передачи в случае обнаружения ошибки есть случайная величина, зависящая только от выбранного метода кодирования. В этом примере варианты - это методы кодирования, текущий момент времени £ соответствует номеру передаваемого сообщения, а потери определяются затратами времени на передачу, т.е. = тг, где тг - время, затраченное на передачу сообщения с номером На практике количество передаваемых сообщений, о которых идет речь в предыдущих примерах, велико. Поэтому при формальной постановке задачи в этом случае полное время функционирования системы следует считать или бесконечным, или конечным, но достаточно большим - так что можно получать асимптотические оценки. Однако возможны ситуации, когда полное время функционирования системы следует предполагать небольшим. В качестве примера рассмотрим испытание лекарств. Пусть имеется группа пациентов и два или более новых лекарств и пусть априори неизвестная вероятность излечения пациента зависит только от выбранного лекарства. Здесь варианты -это выбираемые лекарства, момент времени t соответствует порядковому номеру пациента, а доход определяется количеством излечившихся пациентов, т.е. = 1, если лечение было успешным и = 0 в противном случае. Можно рассмотреть и такую постановку задачи, когда при применении двух возможных лекарств неизвестной является вероятность успешного применения только одного из них - в этом случае требуется вводить некоторое дополнительное ограничение на класс стационарных сред. Кстати, такие ограничения могут потребоваться и в первых двух примерах, например, если известно, что для любого из методов кодирования вероятность безошибочной передачи сообщения не меньше чем 0.9.

Приведенные примеры характеризуют различные модели поведения в случайной среде. Эти модели различаются как значениями величины Т и классами стационарных сред, так и множествами применяемых стратегий. Действительно, естественно ожидать, что стратегии, применяемые в "быстрых" системах при обработке больших объемов данных, будут отличаться от стратегий, применяемых в "медленных" системах при обработке незначительных объемов информации. К первым можно отнести компьютерные системы и системы передачи информации, ко вторым - планирование эксперимента. В некоторых случаях ограничение на множество стратегий может накладываться возможностями управляющего устройства - классическим примером здесь является автоматная модель, широко применявшаяся при моделировании биологических систем [65].

Далее дается обзор некоторых известных результатов, который не претендует на полноту, а предназначен, скорее, для обоснования выбора минимаксного подхода, изучаемого в данной работе, и определения его места среди других подходов к решению задачи. Рассмотрим сначала случай бесконечного полного времени управления. Если значения интерпретируются как доходы, то цель управления состоит в том, чтобы максимизировать, в некотором смысле, ожидаемый средний доход. Если же значения интерпретируются как потери, то рассматривается цель минимизации ожидаемых средних потерь. Поскольку математически обе эти постановки эквивалентны (вторая постановка сводится к первой, если рассматривать последовательность — £ = 1,2,3,. вместо исходной), то далее будем придерживаться первой из них. Обозначим через гп\ = Е/& - математическое ожидание дохода за выбор варианта /, через и/'), I = 1, К обозначим их значения, расположенные в порядке возрастания. Если значения усц, / = 1 ,К известны, то оптимальное управление состоит в том, чтобы всегда выбирать вариант, которому соответствует наибольшее значение и>(к\ при этом будут выполнены предельные равенства 1

Иш Е£г=го(Л">, (2)

X—>оо ^ (3)

Т—»оо 1 где третье равенство является следствием усиленного закона больших чисел.

Если значения I = 1, А' априори неизвестны, то указать вариант, соответствующий наибольшему значению ги(к\ невозможно. Поэтому в процессе управления необходимо, так или иначе, оценивать параметры среды. Оказывается, что в этом случае выполнение предельных равенств (1) - (3) также может быть обеспечено. Простая стратегия поведения, для которой выполняются равенства (1), (3) при неизвестных 1111, I = 1, К предложена в работе Г. Роббинса [86], положившей начало широкому интересу к указанной задаче в зарубежной литературе (имеется перевод [51]). Таким образом, эта стратегия обеспечивала достижение целей управления, описываемых указанными равенствами, для любой среды из некоторого класса. Отметим, что далее термины стратегия и алгоритм (поведения, управления) будут употребляться как синонимы.

Выполнение предельных равенств (1) - (3) можно обеспечить не всегда. В монографиях М.Л. Цетлина [65], В.И. Варшавского [7] Л.А. Поспелова [48] и В.Г. Сраговича [55], [56] приведены результаты работ, посвященных изучению поведения конечных автоматов в случайных средах. Укажем здесь работы Н.П. Канделаки и Г.Н. Церцвадзе [20], В.И. Кринского [40], В.Ю. Крылова [41], В.А. Пономарева [45]. Все они были инициированы статьей М.Л. Цетлина [64], в которой была сделана попытка объяснения целесообразного поведения в биологических системах математическими методами. Этим, в частности, объяснялся тот факт, что в указанных работах рассматривались бинарные стационарные случайные среды, т.е. принимающие лишь два значения, интерпретируемые как неблагоприятные и благоприятные реакции среды [7] (или штраф и нештраф [65]). Для конечных автоматов вместо равенств (1) - (3) оказалось возможным обеспечить лишь выполнение неравенств для некоторого е > 0. Величина е могла быть сделана сколь угодно малой и обычно убывала с ростом числа N - количества состояний автомата, приходящегося на один вариант. Поскольку выполнение неравенств (4) - (6) требовалось обеспечить для любой среды из класса бинарных стационарных сред, то в качестве автоматов рассматривались симметрические автоматы, доход которых не меняется при изменении соответствия параметров среды вариантам. В зарубежных источниках управление на основе конечной памяти, или (что то же самое) конечнозначных статистик, также рассматривалось, причем исследования отечественных и зарубежных авторов в течение значительного времени выполнялись независимо. Отметим здесь работы Г. Роббинса [87]

4)

Нт Е£Т > ю{к) - е,

5) б) имеется перевод [52]), Дж. Исбелла [78], С. Смита и Р. Пайка [89], С. Самю-элса [88].

Тот факт, что для всех известных конечных автоматов не удавалось обеспечить выполнение предельных равенств (1) - (3), обусловил ряд исследований о максимально возможной величине финального среднего дохода конечного автомата. Первые точные оценки границ указанного среднего дохода при К = 2 в постановке, эквивалентной байесовской, были получены A.A. Милютиным [42]. В настоящее время наиболее известными являются результаты М. Хеллманаи Т. Ковера [71], [77], [63], также полученные в байесовской постановке при К — 2 для автоматов несколько иного типа, чем рассматривавшиеся A.A. Милютиным. Для случая К > 2 обобщение результатов М. Хеллмана и Т. Ковера для сред специального вида в минимаксной постановке было сделано К.Ш. Зигангировым [19].

То, что качество управления тем выше, чем больше состояний содержит автомат, было, по-видимому, достаточно ясно и до проведения упомянутых исследований. В работах В.И. Варшавского и И.П. Воронцовой [5], [6], результаты которых были затем изложены в монографии В.И. Варшавского [7], были рассмотрены автоматы, состояниями которых являлись сами вероятности выбора вариантов. Таким образом, указанные автоматы имели бесконечное множество состояний, и можно было ожидать, что они обеспечат выполнение равенств (1) - (3) по крайней мере для некоторого подкласса бинарных стационарных сред. Такие автоматы получили название автоматов с переменной структурой, в отличие от конечных автоматов, которые с тех пор иногда назывались автоматами с постоянной структурой. За рубежом автоматы с переменной структурой стали популярным объектом исследования; полученные там результаты изложены в монографии С. Лакшмиварахана [80], а на русском языке - в монографии A.B. Назина и А.С.Позняка [43]. Следует отметить (хотя это и выходит за рамки данной работы), что поведение автоматов в случайной среде M.JI. Цетлиным [65] В.И. Варшавским [7] рассматривалось как отправная точка для исследования более сложного и более интересного по крайней мере, с точки зрения возможных приложений - поведения коллективов автоматов. Там же поставлены и решены некоторые задачи о поведении автоматов в переключаемых случайных средах и об играх автоматов.

В форме равенств (1) - (3) и неравенств (4) - (6) указанные цели управления были впервые классифицированы в работах В.Г. Сраговича; эти результаты были впоследствии представлены в его монографиях [55], [56]. Цели (2), (5) названы там соответственно асимптотической и е—оптимальностью в слабом смысле, а цели (3), (6) - асимптотической и ^-оптимальностью в сильном смысле. Цели (1), (4) также рассмотрены как слабейшие из возможных, но специального названия не получили. С формальной точки зрения представляется, однако, что в соответствии с классической постановкой задачи о "многоруком бандите", в которой целью управления является максимизация именно среднего дохода, в качестве асимптотической и е-оптимальности в слабом смысле следовало бы выделить цели (1), (4), а выполнение условий (2), (5) рассматривать при этом как свойства отдельных (например, автоматных) стратегий. Некоторым подтверждением сказанного служит то, что цель (2), в отличие от (1), (3), не была рассмотрена в упоминавшейся выше работе Г. Роббинса [86], хотя предложенная там стратегия может быть легко модифицирована так, чтобы достигалась и цель (2). С другой стороны, аргументом в пользу выбранной в [55], [56] классификации может служить тот факт, что в случае бесконечного полного времени управления для большинства известных адаптивных стратегий хотя бы одно из условий (2), (5) оказывается выполнено, и это автоматически влечет выполнение соответствующего более слабого условия (1) или (4).

В монографиях [55], [56] формулировка целей управления (1) - (3) и (4) - (6) дана в несколько более общем виде, пригодном для постановки в случайных средах отличных от стационарных. В.Г. Сраговичем, его коллегами и учениками установлена е-оптимальность и асимптотическая оптимальность (т.е. выполнение условий (5), (6), (2), (3)) в различных случайных средах для ряда алгоритмов на бесконечном отрезке времени. Укажем здесь некоторые результаты, при этом удобно, следуя используемой авторами приводимых работ терминологии, говорить не о поведении в случайной среде, а об управлении случайными процессами. В частности, стационарные среды именуются при этом однородными процессами с независимыми значениями (ОПНЗ). В.Г. Сраговичем и Ю.А. Флеровым [58], [59] построена серия е-оптимальных автоматов для бинарных ОПНЗ. Дальнейшее развитие этих результатов было сделано в работах В.Г. Сраговича [53], [54] и Ю.А. Флерова [62], где предложены конструкции, обладающие свойствами асимптотической оптимальности и е-оптимальности при управлении ОПНЗ общего вида (а не только бинарными). Отметим, что все эти конструкции функционировали на основе текущих статистических оценок параметров среды. М. Гесселем, Ю.В. Поповым и В.Г. Сраговичем [10] и Ю.В. Поповым [46] рассмотрены адаптивные алгоритмы управления неоднородными (во времени) процессами с независимыми значениями. М.Г. Коноваловым [38] предложено семейство е-оптимальных автоматов для периодических процессов с независимыми значениями. Алгоритмы асимптотически оптимального и е-оптимального управления марковскими процессами и марковскими цепями с доходами изучались в статьях В.Г. Сраговича [57], М. Гесселя и В.Г. Сраговича [9], М. Гесселя, Ю.В. Попова и В.Г. Сраговича [И], Е.И. Гордиенко [12], [13], В.С.Засухина[18], М.Г. Коновалова [37], [39], Ю.В. Попова [47]. Г.А. Агасандяном [1], [2] предложены алгоритмы для управления стационарными процессами и однородными процессами с непрерывными множествами состояний и управлений. Игры автоматов изучались Е.Т. Гурвичем [14], [15] и Б.Г.Сушковым [60]. При этом наряду с конструкциями на основе текущих статистических оценок параметров среды для указанных выше алгоритмов широко использовались конечные автоматы с постоянной структурой, а также некоторые другие оригинальные идеи.

В основе еще одного подхода к рассматриваемой задаче лежит использование метода стохастической аппроксимации для формирования и исследования адаптивных алгоритмов, предложенное в монографии Я.З. Цыпки-на [66]. Возможность использования этого подхода для рекуррентных алгоритмов поведения в стационарной среде была первоначально установлена в работе Я.З. Цыпкина и A.C. Позняка [67]. Рекуррентным является в данном случае алгоритм пересчета текущего вектора вероятностей выбора вариантов, который осуществляется на основе его предыдущего значения и текущих значений выбранного варианта и реакции среды. Например, упомянутые выше автоматы с переменной структурой являются рекуррентными алгоритмами. Результаты анализа ранее известных рекуррентных алгоритмов, а также собственные исследования в этой области A.B. Назина и A.C. Позняка, опубликованные в ряде журнальных статей, были затем изложены в их монографии [43]. При этом наряду с целями управления (1) - (3) в [43] систематически исследуется гарантированное на классе случайных сред значение величины т.е. гарантированной скорости сходимости в среднем квадратическом. Для ряда рекуррентных алгоритмов, асимптотически оптимальных на классе всех стационарных сред, установлено, что гарантированная скорость сходимости смотрено обобщение указанных алгоритмов для задач условной минимизации, управления конечными однородными марковскими цепями, а также игровые алгоритмы.

Здесь уместно отметить, что авторы многих отмеченных выше работ зачастую либо формулировали цели управления не в форме условий (1) - (6), либо наряду с ними рассматривали некоторые другие характеристики. Например, для конечных автоматов, автоматов с переменной структурой и рекуррентных алгоритмов обычным являлось изучение динамики поведения вектора вероятностей выбора вариантов и его финальное распределение. Но, во-первых, выполнение (или невыполнение) условий (1) - (6) для указанных алгоритмов было впоследствии проверено (например, в монографиях [56], [43]), а, во-вторых, данный обзор, как уже отмечалось, имел целью обоснование рассматриваемого ниже минимаксного подхода к задаче.

7) имеет порядок Т 2а, где 0 < 2а < 1, например, а = 1/3. Кроме того, в [43] рас

Можно выделить две основные причины неудовлетворенности описанными выше результатами. Первая состоит в том, что было предложено много различных не только £-оптимальных, но и асимптотически оптимальных стратегий и, следовательно, встал вопрос о некотором дополнительном критерии их качества, а также об отыскании оптимальной стратегии относительно этого критерия. Например, в монографии [43] в качестве такого критерия для рекуррентных алгоритмов рассматривалась гарантированная скорость сходимости в среднем квадратическом и была поставлена задача об отыскании алгоритма с наилучшей скоростью сходимостью.

Вторая причина состоит в том, что почти все описанные выше стратегии носили в большей или меньшей степени эвристический характер (исключение составляют работы [19], [42], [63], [71]). В основном использовалась идея обеспечить за счет выбора подходящей конструкции управляющей системы преимущественное (по доле времени применения или по вероятности выбора) использование лучшего варианта. Но математическое решение задачи предполагает, что оптимальная стратегия должна не изобретаться, а отыски-ваться'исходя из некоторого критерия оптимальности - примерно так же, как отыскивается точка экстремума функции или функционала.

Отметим, что найти такую стратегию путем синтеза оптимальных стратегий, вычисленных при различных фиксированных известных значениях параметра среды, в данном случае невозможно, поскольку все они предписывают применять каждый раз свой, лучший для данной среды вариант. Поэтому можно попробовать максимизировать математическое ожидание среднего дохода при некотором ограничении на множество стратегий, вытекающем из существа рассматриваемой задачи. В [65], [7] отмечено, что для конечных автоматов таким ограничением является их симметричность, поскольку автомат должен одинаково хорошо функционировать во всех средах, которые получаются из исходной в результате всевозможных перестановок составляющих ее параметра, соответствующих различным вариантам. Ясно, что идея симметричности стратегии может рассматриваться как универсальная для данной задачи, а не ограничивается только классом конечных автоматов. Что касается последних, то управляющие системы на их основе всегда конструировались симметрическими или легко могли быть модифицированы в таковые. Идея симметричности оптимального автомата была положена в основу отыскания его структуры в [22]; оказалось, что структура такого автомата не за» висит от рассматриваемой среды. При попытке обобщить этот результат на случай стратегий общего вида, зависящих от всей предыстории, выяснилось, что такая стратегия может требовать априорного знания параметра среды, хотя и сохраняется при любых перестановках его составляющих [23]. Таким образом попытка свести задачу поиска оптимальной стратегии на классе всех стационарных сред к ее определению для какой-то конкретной среды путем ввода ограничений на множество стратегий не удалась.

Другой подход состоит в том, чтобы модифицировать подходящим образом цели (1) - (6). Причем, поскольку на бесконечном отрезке времени существует много различных асимптотически оптимальных стратегий, то соответствующая цель - критерий оптимальности стратегии - должна быть сформулирована на конечном априори известном отрезке'времени Т.

Ясно, что при переходе к конечному полному времени управления цели (1) - (3) рассматриваться не могут. Невозможна постановка на конечном отрезке времени цели (6), и не отражает сути задачи цель (5), если не сделать каких-то дополнительных оговорок. Действительно, стратегия, применяющая варианты по очереди в течение первых Т — 1 шагов для набора статистики и выбирающая на последнем шаге тот из них, которому соответствует больший начальный средний доход, обеспечивает достижение цели (5) для конечного времени управления, но не дает решения задачи по существу. А вот цель управления (4) при подходящем выборе значения е сохраняется. Если же дополнительно к требованию выполнения неравенства (4) потребовать минимизации величины е, то получаем минимаксную постановку задачи.

При формулировке минимаксной цели управления удобно явным образом ввести в рассмотрение параметр 0, описывающий случайную среду (далее речь идет только о стационарных средах). Выбор параметра определяется распределениями среды; в общем случае можно считать, что в = (^(О, • • •, где -Р}(.) - функция распределения дохода при условии выбора /-ого варианта. Отметим, что параметр, описывающий среду, остается неизменным в процессе управления. Таким образом, априорная неопределенность состоит в том, что известен не сам параметр, а множество его допустимых значений О, описывающее класс случайных сред. Если стратегию управления обозначить через а, то можно определить минимаксный риск характеризующий минимальную величину гарантированной разности макси

Здесь в обозначении ~Еа>в явно указано, что математическое ожидание дохода вычисляется по мере, порожденной стратегией а и параметром среды в. Предполагается, что а принадлежит некоторому классу стратегий {<т}, который характеризует тем свмым модель поведения; три таких класса рассмотрены в основной части работы. Если минимаксный риск (8) достигается для некоторой стратегии <7° на классе стационарных сред Э, то для любой среды из указанного класса, очевидно, выполнено неравенство являющееся аналогом цели (4), а величина 211/?т(Э) характеризует минимально возможное значение е. Отметим, что для конечных автоматов, с учетом сделанного ранее замечания о максимальной величине их финального среднего дохода, оказывается удобнее рассматривать минимаксный риск на бесконечном отрезке времени управления; при этом его следует вычислять не по суммарному, а по среднему доходу. Существенным является также вопрос о существовании стратегии сг°; например, для автоматов зачастую можно указать только е-оптимальные стратегии. Существование всех остальных изучаемых в данной работе оптимальных стратегий устанавливается в ее основной части.

8) т мально возможного (Тю^к\9)) и реального ожидаемого (ЕСТ)0 ^ доходов. t=l

9)

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

Задача об отыскании минимаксного риска для "двурукого бандита", т.е. при К = 2, в формулировке эквивалентной (8), предложена в отмеченной выше работе Г. Роббинса [86] (в этой работе минимаксный риск определен не по суммарному, а по среднему доходу). Однако никакого решения поставленной задачи в [86] не дается. Основная причина здесь состоит в том, что вычисление минимаксного риска для конкретных классов случайных сред и конкретных значений Т оказывается трудной задачей (исключениями являются Т = 1,2 и, может быть, Т = 3). Зато удается получить асимптотические оценки минимаксного риска. Такие неулучшаемые по 'порядку оценки были получены при К = 2 в работах В. Вогела [90], [91]. В используемых здесь обозначениях эти результаты соответствуют тому, что Лт(0) имеет как функция Т порядок Т1/2 при Т —► оо. Предполагается, что Э содержит все возможные распределения. К сожалению, результаты В. Вогела не получили достаточного отражения в отечественной библиографии. Фактически их изложение имеется только в монографии Э.Л. Пресмана и И.М. Сонина [49]. А в монографии М. Де Гроота [72], широко известной у нас в переводе [17], статьи [90], [91] включены в библиографический список, однако комментарии к ним отсутствуют. В качестве другой работы, в которой установлено существование минимаксной стратегии для бернуллиевского "двурукого бандита" и рассмотрены некоторые ее свойства, например, симметричность, а также вычислены минимаксные стратегии для значений Т = 1, 2,3,4, отметим работу Дж. Фаби-уса и В. ван Цвета [73]. Минимаксный подход использовался и в отмеченной выше работе [19] по определению оптимальной структуры управляющего конечного автомата.

Как видно из (9), величина Т-1 Дг(0) характеризует гарантированную скорость сходимости среднего дохода к его предельному значению. Соответственно, гарантированная скорость сходимости в среднем квадратическом описывается гарантированным на классе стационарных сред значением величины (7). Введение этой характеристики в [43] было оправдано использованием метода стохастической аппроксимации при обосновании сходимости рассматриваемых там рекуррентных алгоритмов. Однако ее рассмотрение представляется интересным и для других алгоритмов, поскольку она гарантирует отсутствие больших отклонений среднего дохода от его ожидаемого значения. Кроме того, применяя неравенство Коши-Буняковского, именно можно видеть, что гарантированная сходимость в среднем квадратическом влечет обычную гарантированную сходимость. Таким образом, если для несходимости в среднем квадратическом имеет порядок Т~2а, где 0 < 2а < 1, то из приведенного неравенства следует, что порядок обычной гарантированной скорости сходимости есть Т~а. Формально в этом случае удобно, аналогично (8), определить квадратичный минимаксный риск а гарантированная скорость сходимости в среднем квадратическом будет то

Для решения задачи о "двуруком бандите" применялся и байесовский подход, причем количество публикаций, посвященных его использованию, намного больше числа публикаций, посвященных минимаксному подходу; в качестве одной из первых отметим статью Р. Брэдта, С. Джонсона и С. Карлина [70]. В уже упоминавшихся работах [42], [63], [71] по определению оптимальной струккоторого алгоритма оказывается установлено, что гарантированная скорость

10) гда равна Т 2Ят(&). туры управляющего автомата также использовался байесовский подход. Отметим, что во многих публикациях речь идет не о минимизации байесовского риска, а об эквивалентной ей задаче максимизации байесовского дохода. Популярность байесовского подхода во многом объяснялась тем, что при удачном выборе априорного распределения параметра среды можно было точно найти байесовскую стратегию, причем стратегия именно вычислялась исходя из сформулированной цели, а не изобреталась из некоторых эвристических соображений. Так, практически во все монографии, посвященные байесовскому подходу, вошел результат Д. Фельдмана [74], состоящий в том, что если априорное распределение сосредоточено на двух противоположных средах, то при выборе вариантов следует руководствоваться только текущим апостериорным распределением параметра. Более того, хорошо известна простая численная процедура, описанная, например, в монографии М. Де Гроота [17], которая позволяет методом динамического программирования определить байесовскую стратегию для любого априорного распределения. В случае бесконечного полного времени управления получил распространение подход, развитый в работе Дж. Гиттинса [76]. В ней в'байесовской постановке рассмотрена задача о "многоруком бандите" с дисконтируемыми доходами, оо т.е. максимизируется ожидаемая величина бесконечной суммы ^ гДе Р - дисконтирующий множитель, удовлетворяющий ограничениям 0 < (3 < 1. В этом случае используется "индекс Гиттинса", значения которого в каждый момент времени определяются для всех вариантов на основе текущего апостериорного распределения параметра, а оптимальная стратегия состоит в выборе того варианта, которому соответствует большая величина индекса.

Среди работ, посвященных байесовскому подходу к задаче о "многоруком бандите", выделим статью Т. Лэя [81], в которой даны асимптотические оценки байесовского риска для стационарных сред из экспоненциального семейства при широких предположениях об априорном распределении параметра. В используемых здесь обозначениях этот результат состоит в том, что при фиксированном априорном распределении байесовский риск как функция полного времени управления Т имеет порядок (1пТ)2. Таким образом, этот результат описывает порядок ожидаемых потерь, если время управления неограниченно растет.

В России байесовский подход к задаче применительно к экономическим проблемам развивался в работах Э.Л. Пресмана и И.М. Сонина, результаты которых были затем обобщены в монографии [49] и работе [84] (см. также [85]). При этом результаты были получены как для дискретного, так и для непрерывного времени. Следует отметить, что пуассоновская модель, рассмотренная в [84], явилась одной из моделей процессов с непрерывным временем, которая легла в основу популярной в настоящее время за рубежом общей концепции "непрерывного многорукого бандита", предложенной А. Мандель-баумом [82].

Таким образом, байесовский подход дает как будто бы другой метод решения рассматриваемой задачи, когда оптимальная стратегия вычисляется на основе некоторого критерия; в данном случае целью является минимизация байесовской функции потерь. Однако он обладает одним существенным недостатком, состоящим в необходимости выбирать априорное распределение параметра. Непонятно, как обосновать такой выбор в каждом конкретном случае. Ясно также, что такое обоснование будет скорее всего не более убедительным, чем, например, обоснование требования симметричности управляющих стратегий. Исключением могут быть, как указано в [49] (где имеются ссылки и на другие источники, в которых обсуждается применимость байесовского подхода), задачи, в которых априорное распределение определяется на основе экспертных оценок, например, экономические модели. В общем случае случае опять возможно использование минимаксного подхода, при этом ограничимся случаем бинарной стационарной среды, или, что то же самое, бернуллиевского "многорукого бандита".

Пусть О - замкнутое множество, а \{М) - априорное распределение параметра на нем. Байесовский риск определяется равенством

Д?(А,в) = ЫI Е„,е ¡Ти,(к\9) - £ Л А (¿0), е а стратегия ав(А,0), обеспечивающая его достижение, называется байесовской. Минимаксный подход состоит в этом случае в определении гарантированной величины байесовского риска

Д?(9) = зир / \Тг»(к\в) -ТЬ) А(«Ю),

М{А {¿в))1 { е гВ(С1 и нахождении соответствующей стратегии а (0), для которой, таким образом, оказывается выполненным неравенство Е^Дт-1 ^Л А(<Ю)> / 7-^(0) при любом априорном распределении параметра А{¿9). Из основной теоремы теории игр [44] следует, что при широких предположениях величина описывающая минимаксный риск "усредненной игры" с "многоруким бандитом", является ценой этой игры, и, следовательно, численно равна обычному минимаксному риску Отсюда следует, что /?т(0) характеризует максимально возможное значение байесовского риска Д^(А,0), и задача об определении гарантированной величины байесовского риска сводится к задаче об определении минимаксного риска. Что касается предположений, при выполнении которых возможно применение основной теоремы теории игр (см., например, [3]), то одним из них является требование к множеству стратегий содержать смешанные стратегии; выполнение его может быть легко проверено для стратегий общего вида, зависящих от всей предыстории управления и делается в основной части работы. Другими предположениями являются непрерывность подинтегрального выражения Е^ — как функции переменных а и 9 и компактность множеств {сг} и 0, что в данном случае также имеет место.

Перейдем к краткому изложению результатов данной работы. В главе 1 рассмотрен минимаксный подход в модели поведения с конечной памятью, если для управления используются конечные автоматы типа рассмотренных в [65], [7]. В предположении, что автомат имеет одинаковое количество состояний, соответствующих каждому варианту, установлены точные границы предельного среднего дохода автомата для фиксированной бинарной среды, а также на множестве всех бинарных случайных сред. Для фиксированной среды минимаксный риск имеет отрицательную экспоненциальную зависимость от N - количества состояний, приходящихся на один вариант, а ка классе всех сред - порядок тУ-1. Можно ожидать, что эти оценки останутся справедливыми, если допустить, что разным вариантам может соответствовать разное количество состояний. Так, оценки снизу и сверху для отношений произведений финальных вероятностей в этом случае сохраняются. Однако соответствующие оценки для финального среднего дохода автомата пока получены при некоторых ограничениях, обусловленных техникой доказательства. Отметим также, что оптимальные автоматы несколько различаются, если значения среды интерпретируются как потери, для которых в качестве цели рассматривается их минимизация, или же как доходы, для которых целью является максимизация. В работе оба функционала рассмотрены с единых позиций за счет введения соответствующих весовых векторов. При построении оптимальных автоматов дано определение симметрического автомата, которое обобщает определение [7]. Оптимальные автоматы оказались симметрическими и аналогичны рассмотренным в [42], [19]. Для автоматов Хеллмана-Ковера, несколько отличных от рассмотренных в [65], [7], получены оценки минимаксного риска на классе всех стационарных сред при К = 2; эти оценки не допускают обобщения на случай К > 2. Отметим, что при К = 2 асимптотические оценки минимаксного риска для автоматов типа [65], [7] и автоматов Хеллмана-Ковера оказались одинаковыми, если они имеют одинаковое полное число состояний. Основные результаты этой главы опубликованы в [29], [31], [33].

В главе 2 рассмотрена модель поведения с априори определяемой продолжительностью времени обучения в стационарной среде общего вида при условии существования равномерно ограниченных сверху первых четырех моментов для всех распределений доходов (при рассмотрении минимаксного риска достаточно существования первых трех моментов). Стратегия состоит в том, что на начальном отрезке времени варианты применяются по очереди для набора статистики о среде, а затем на заключительном отрезке времени применяется всегда один и тот же вариант, которому соответствует больший начальный доход. Таким образом весь процесс управления делится на два этапа: начальный, который можно назвать этапом обучения, и заключительный, на котором осуществляется собственно управление. При этом максимальные ожидаемые потери на начальном этапе возрастают с ростом его продолжительности, а максимальные ожидаемые потери на заключительном этапе падают с ростом продолжительности начального. Задача состоит в том, чтобы выбрать оптимальную продолжительность начального этапа. Она выбирается из уравнения баланса максимальных ожидаемых потерь на начальном и заключительном этапах и имеет порядок Г2/3, где Т - полное время управления. Кроме того на длину начального отрезка времени управления влияют максимальная дисперсия дохода и максимальная разность математических ожиданий доходов на классе стационарных сред, которые могут быть вычислены на основе известной априорной информации. Минимаксный и квадратичный минимаксный риски имеют порядки Т2/3 и Г4/3 соответственно, а гарантированная скорость сходимости и гарантированная скорость сходимости в среднем квадратическом - порядки Г-1/3 и Т~2/3. Основные результаты этой главы опубликованы в [30], [34], [35], [36].

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

Оценка для числа параметров может быть понижена. Для этого устанавливается, что для любой стратегии указанного вида найдется стратегия, зависящая только от достаточных статистик предыстории, обеспечивающая то же значение математического ожидания дохода, что и исходная. Поэтому требуемое число параметров может быть понижено до величины 2№(К,Т), где Лг'°(/1, Т) - количество вероятностей, необходимых для задания стратегии, зависящей только от достаточных статистик. Отметим, что при фиксированном К справедлива оценка №(К,Т) ~ Т2К(К - 1)/(2К)\, т.е. №(К,Т) имеет степенную зависимость от полного времени управления. Если множество 0 -симметрическое, то можно ограничиться только симметрическими стратегиями, и, следовательно, оценка для числа параметров может быть еще снижена по крайней мере в К раз. Отметим, что некоторые свойства стратегий для бернуллиевского "двурукого бандита" были ранее установлены в [73].

На конечном множестве параметров минимаксная стратегия определяется как байесовская для наихудшего априорного распределения на этом множестве параметров. Это следует из основной теоремы теории игр. В работе приведены приближенные значения минимаксных рисков при Т = 1,2,.,10и описаны соответствующие стратегии для класса всех бинарных стационарных сред, т.е. $цля 0 = {9 : в = (р!,р2), 0 < р/ < 1, / = 1,2}. При этом оказывается удобным описывать стратегию соответствующим ей конечным множеством параметров и наихудшим априорным распределением на нем (в рассмотренных случаях такая байесовская стратегия оказалась единственной, если дополнительно потребовать ее симметричности). Для каждого из перечисленных выше значений Т оказалось достаточным указать не более четырех параметров из множества О. Отметим, что отсюда не следует, что четырех значений параметра достаточно для определения минимаксной стратегии в указанном диапазоне Т; речь идет только об ее приближенном вычислении. Основные результаты этой главы опубликованы в [24], [25], [28], [31].

В главе 4 устанавливаются асимптотические неулучшаемые по порядку оценки минимаксного (8) и квадратичного минимаксного (10) рисков. Они имеют порядки Т1/2 и Т соответственно, где Т - полное время управления. Соответственно гарантированная скорость сходимости и гарантированная скорость сходимости в среднем квадратическом имеют порядки Т-1/2 и Т-1. Оценки для минимаксного риска, хотя и получены независимо, не являются новыми; ранее они были установлены в уже упоминавшихся работах [90], [91]. Однако новыми являются, во-первых, постановка задачи, в которой при широких предположениях рассматриваются произвольные классы стационарных сред, во-вторых, представление оценок, в котором наряду с полным временем функционирования присутствует и максимальная дисперсия дохода на классе случайных сред (в работах [90], [91] указана зависимость только от времени управления), в-третьих, предложенные доказательства. Также новыми являются оценки квадратичного риска и обобщения оценок минимаксного и квадратичного минимаксного рисков на случай К > 2. При получении оценок сверху использована пороговая стратегия, впервые предложенная в [90], [91], поэтому можно говорить о том, что в этой главе рассмотрена модель поведения на основе пороговой стратегии. Наконец, в этой главе рассмотрена простая процедура синтеза стратегии, действующей на бесконечном промежутке времени, на основе некоторой стратегии, действующей на конечном промежутке. При этом синтезированная стратегия имеет тот же порядок гарантированной скорости сходимости, что и исходная. Результаты этой главы опубликованы в [26], [27], [79].

ЗАКЛЮЧЕНИЕ

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

Для конечных автоматов с постоянной структурой минимаксный риск вычислялся по финальному распределению вероятностей. Его оценки основывались на алгебраических свойствах финальных вероятностей и некоторых свойствах отношений пропорций. При широких предположениях установлено, что минимаксный риск, который совпадает в данном случае с гарантированной скоростью сходимости, не может быть равен нулю для автоматов с конечной памятью даже при бесконечном времени управления. Минимаксный риск для конечного набора сред, получающихся перестановками компонент параметра некоторой исходной среды, имеет показательную зависимость от числа состояний ТУ, приходящихся на один вариант, и порядок ТУ-1 на классе всех стационарных сред. Для автоматов Хеллмана-Ковера асимптотические оценки минимаксного риска совпадают с сооответствующими оценками для автоматов с детерминированной функцией выхода, если они имеют одинаковое общее число состояний.

Для стратегий, в которых процессы сбора статистики (обучения) и собственно управления разделены на два этапа на основе известной априорной информации, рассматривается задача об оптимальной продолжительности этих этапов. Поскольку потери на начальном этапе растут, а на заключительном - падают с ростом продолжительности начального этапа, то оптимальная продолжительность находится из уравнения баланса для максимальных ожидаемых потерь на начальном и заключительном этапах. Если полное время управления есть Т, то минимаксный риск и гарантированная скорость сходимости имеют порядки Т2!3 и Г-1/3, а квадратичный минимаксный риск и скорость сходимости в среднем квадратическом - порядки Т4^3 и Т~2/'3. Оптимальная продолжительность начального этапа в обоих случаях имеет порядок г2/3.

Для бинарной стационарной среды рассмотрены стратегии, наиболее полно учитывающие предысторию управления. Для них методом вариации оптимальной стратегии исходное множество параметров было сужено до конечного, минимаксный риск на котором равен минимаксному риску на исходном множестве. Число параметров в конечном множестве оценивается сверху количеством независимых допустимых вариаций оптимальной стратегии, но в конкретных случаях может быть совсем небольшим. Установлен ряд свойств минимаксной стратегии: зависимость только от достаточных статистик предыстории и симметричность в случае симметричности исходного множества параметров. Эти свойства интересны как сами по себе, так и с точки зрения возможности уменьшения числа независимых вариаций. Для конечного множества параметров минимаксная стратегия определяется с использованием основной теоремы теории игр, т.е. она совпадает с некоторой байесовской стратегией для "наихудшего" априорного распределения. Алгоритм был применен для приближенного отыскания минимаксных стратегии и риска при К = 2 и Т = ТДО.

Для больших значений Т получены асимптотические оценки минимаксного и квадратичного минимаксного рисков, которые имеют порядки Г1/2 и Т. Соответственно гарантированная скорость сходимости и гарантированная скорость сходимости в среднем квадратическом имеют порядки Г-1/2 и Г-1. Оценки снизу получены как оценки минимаксного и квадратичного минимаксного рисков на некоторых подмножествах исходного множества параметров. Оценки сверху получены как гарантированные оценки сверху для функции потерь и квадратичной функции потерь для простой последовательной стратегии, основанной на отбрасывании худшего варианта. Эта стратегия в силу своей простоты и эффективности может иметь практическое применение, если время Т достаточно велико и заранее известно. Если же время Т неизвестно, то можно использовать модифицированную стратегию, сохраняющую порядок гарантированной скорости сходимости на бесконечном отрезке времени.

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

Некоторые дальнейшие возможные направления работы рассматривались при обсуждении результатов отдельных глав. Здесь, как наиболее важные, отметим еще раз следующие. Представляет интерес изучение асимптотического поведения "наихудшего" априорного распределения, что дало бы возможность получения точных асимптотических оценок минимаксного риска и асимптотического вида минимаксной стратегии. Причем порядок минимаксного риска, равный Т1/2, уже установлен; вопрос стоит об определении точного коэффициента в этой оценке. Представляет также интерес изучение различных модификаций стратегии, рассмотренной в главе 4: переменный во времени порог, использование накопленной статистики после применения процедуры отбрасывания худшего варианта и т.д.

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

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

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

1. Агасандян Г.А. Адаптивная система для класса однородных последовательностей// ДАН СССР. Т. 228. 1976. № 2. С. 329-331.

2. Агасандян Г.А. Адаптивные системы для однородных процессов с непрерывными множествами состояний и управлений// Теория вероятностей и ее применения. 1979. № 3. С. 515-528.

3. Боровков A.A. Математическая статистика. Дополнительные главы. М.: Наука, 1984.

4. Боровков A.A. Теория вероятностей. М.: Наука, 1986.

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

6. Варшавский В.И., Воронцова И.П. Стохастические автоматы с переменной структурой// В кн:. Теория конечных и вероятностных автоматов. Труды ИФАК. М.: Наука, 1965. С. 301-309.

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

8. Гантмахер Ф.Р. Теория матриц. М.: Наука, 1988.

9. Гесселъ М., Срагович В.Г. Адаптивное управление марковскими цепями с доходами// ДАН СССР. 1980. Т. 254. № 3. С. 523-527.

10. Гессель М., Попов Ю.В., Срагович В.Г. Адаптивное управление обобщенными процессами с независимыми значениями// Изв. АН СССР. Техн. кибернет. 1978. № 6. С. 186-192.

11. Гессель М., Попов Ю.В., Срагович В.Г. Адаптивное управление частично наблюдаемыми марковскими цепями с доходами// ДАН СССР. 1977. Т. 237. № 4. С. 767-769.

12. Гордиенко Е.И. Адаптивное оптимальное управление некоторыми марковскими процессами// ДАН СССР. 1981. Т. 261. № 2. С. 271-275.

13. Гурвич Е. Т. Метод асимптотического исследования игр автоматов// АиТ. 1975. № 2. С. 80-94.

14. Гурвич Е.Т. Адаптивное управление векторными случайными процессами// В сб.: Исследования по теории адаптивных систем. М.: ВЦ АН СССР, 1976, С. 67-118.

15. Данцер Л., Грюнбаум В., Кли В. Теорема Хелли. М.: Мир, 1968.

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

17. Засухин В.С. Достаточное условие асимптотической оптимальности одного класса вероятностных автоматов// Изв. АН СССР. Техн. кибернет. 1975. № 5. С. 142-147.

18. Зигангиров К.Ш. О многоальтернативном различении гипотез с помощью автоматов с конечным числом состояний// Пробл. передачи информ. 1977. Т. 13. № 3. С. 45-55.

19. Канделаки H.H., Церцвадзе Г.Н. О поведении некоторых классов стохастических автоматов в случайных средах// АиТ. 1966. Т. 27. № 6. С. 115-119.

20. Карманов В.Г. Математическое программирование. М.: Наука, 1980.

21. Колногоров A.B. Границы предельного среднего выигрыша симметрического конечного автомата. Деп. в ВИНИТИ. Ш 2892-80 от 10.07.80. 23 С.

22. Колногоров A.B. Некоторые задачи оптимального адаптивного управления. Деп. в ВИНИТИ. № 2891-80 от 10.07.80. 14 С.

23. Колногоров A.B. О минмаксном подходе к задаче о "двуруком бандите"// Деп. в ВИНИТИ. № 4406-85 от 20.06.85. 46 С.

24. Колногоров A.B. О минимаксном подходе к оптимальному целесообразному поведению в стационарных средах на конечном времени// Изв. АН СССР. Сер. Техн. кибернет. 1988. № 6. С. 143-146.

25. Колногоров A.B. Об оценках минимаксного риска в стационарных средах// Изв. АН СССР. Сер. Техн. кибернет. 1990. № 2. С. 153-155.

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

27. Колногоров A.B. К обоснованию двух эвристических приемов в задаче о целесообразном поведении в стационарной среде// АиТ. 1992. № 8. С. 8385.

28. Колногоров A.B. Об автоматах в случайной среде// В сб.: Материалы международной конференции и Чебышевских чтений, посвященных 175-летию со дня рождения П.Л. Чебышева. М.: Изд-во МГУ, 1996, С. 211-214.

29. Колногоров A.B. Об одной простой стратегии в задаче о "двуруком бандите"// Обозрение прикл. и промышл. матем. Сер. Вероятн. и статист. 1997. Т. 4. В. 3. С. 355.

30. Колногоров A.B. Об оптимальном поведении конечных автоматов в случайной среде// Пробл. передачи информ. 1998. Т. 34. № 1. С. 77-86.

31. Колногоров A.B. Алгоритм отыскания минимаксной стратегии для бер-нуллиевского "многорукого бандита"// Обозрение прикл. ипромышл. ма-тем. Сер. Вероятн. и статист. 1998. Т. 5. В. 2. С. 230.

32. Колногоров A.B. Об автомате с неулучшаемым гарантированным доходом в случайной среде// Вестн. Новг. гос. ун-та. Сер. Естеств. и техн. науки. 1998, № 10, С. 99-101.

33. Колногоров A.B. Простая стратегия поведения в стационарной среде со степенной гарантированной скоростью сходимостью // АиТ. 1999. № 8. С. 95-101.

34. Колногоров A.B. Об оптимальном априорном балансе обучения и управления в задаче о "двуруком бандите"// Обозрение прикл. и промышл. матем. Сер. Вероятн. и статист. 1999. Т. 6. В. 1. С. 158-159.

35. Колногоров A.B. Об оптимальном априорном времени обучения в задаче о "двуруком бандите"// Пробл. передачи информ. 2000. Т. 36. № 4. С. 117127.

36. Коновалов М.Г. Об адаптивном управлении некоторыми классами марковских цепей// ДАН СССР. 1977. Т. 233. № 5. С. 780-783.

37. Коновалов М.Г. Адаптивное управление периодическими процессами с независимыми значениями// Изв. АН СССР. Техн. кибернет. 1979. № 1. С. 138-144.

38. Коновалов М.Г. Адаптивное управление конечными автоматами с ненаблюдаемыми состояниями// ДАН СССР. 1986. Т. 291. № 15. С. 59-62.

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

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

41. Милютин A.A. Об автоматах с оптимальным целесообразным поведением в стационарной среде// АиТ. 1965. Т.26. № 1. С. 117-131.

42. Назин A.B., Позняк A.C. Адаптивный выбор вариантов. М.: Наука, 1986.

43. Фон Нейман Дж., Моргенштерн О. Теория игр и экономическое поведение. М.: Наука, 1970.

44. Пономарев В.А. Об одной конструкции конечного автомата, асимптотически оптимального в стационарной среде// Биофизика. 1964. Т. 9. Вып 1. С. 104-110.

45. Попов Ю.В. Адаптивное управление некоторыми классами случайных процессов общего вида// В сб.: Исследования по теории адаптивных систем. М.: ВН АН СССР, 1976, С. 119-142.

46. Попов Ю.В. Адаптивное управление эргодическими марковскими цепями// В сб.: Исследования по теории адаптивных систем. М.: ВЦ АН СССР, 1976, С. 143-149.

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

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

49. Прохоров Ю.В., Розанов Ю.А. Теория вероятностей. М.: Наука, 1987.

50. Роббинс Г. Некоторые аспекты последовательностного построения экспериментов// Кибернетический сб. 1970. Вып. 7. С. 71-80.

51. Роббинс Г. Построение последовательностных экспериментов с конечной памятью// Кибернетический сб. 1970. Вып. 7. С. 81-84.

52. Срагович В.Г. Автоматы с многозначным входом и их поведение в случайных средах// В сб.: Исследования по теории самонастраивающихся систем. М.: ВЦ АН СССР, 1971, С. 19-65.

53. Срагович В.Г. Оптимальные свойства одного класса управляющих автоматов// Изв. АН СССР. Техн. кибернет. № 1, 1973, С. 110-116.

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

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

56. Срагович В.Г. Оптимизация с ограничениями на конечных управляемых марковских цепях// ДАН СССР, Т. 275, № 3, 1984, С. 572-575.

57. Срагович В.Г., Флеров ЮЛ. Построение класса оптимальных автоматов// ДАН СССР, Т. 159, № 6, 1964, С. 1236-1237.

58. Срагович В.Г., Флеров ЮЛ. Об одном классе стохастических автоматов// Изв. АН СССР. Техн. кибернет. № 2, 1965, С. 66-73.

59. Сушков Б.Г. О симметрических играх больших коллективов вероятностных автоматов// Пробл. передачи информ. 1973. Т. 9. № 3. С. 95-99.

60. Феллер В. Введение в теорию вероятностей и ее приложения. Т.1. М.: Мир, 1984.

61. Флеров Ю.А. О некоторых классах многовходовых автоматов// В сб.: Исследования по теории самонастраивающихся систем. М.: ВЦ АН СССР, 1971, С. 96-110.

62. Хеллман М.Е., Ковер Т.М. По поводу автоматов в случайной среде// Пробл. передачи информ. 1970. Т. 6. № 2. С. 21-30.

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

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

65. Цыпкин Я.З. Адаптация и обучение в автоматических системах// М.: Наука, 1968.

66. Цыпкин Я.З., Лозняк A.C. Обучающиеся конечные автоматы// Изв. АН СССР. Техн. кибернет. № 3, 1972, С.127-140.

67. Berry D.A., Fristedt В. Bandit Problems. London.: Chapman and Hall, 1985.

68. Blumental L.M. Metrie methods in linear inequalities// Duke Math. J. 1948. V. 15. P. 955-966.

69. Bradt R.N., Johnson S.M., Karlin, S. On sequential designs for maximazing the sum of n observations// Ann. Math. Statist. 1956. V. 27. P. 1060-1074.

70. Cover T.M., Hellman M.E. The Two-Armed Bandit Problem with Time-Invariant Finite Memory// IEEE Trans. Inform. Theory. 1970. V. 16. № 2. P. 185-195.

71. DeGroot M.H. Optimal statistics decisions. McGraw-Hill Company, 1970.

72. Fabius J., van Zwet W.R. Some remarks on the two-armed bandit// Ann. Math. Statist. 1970. V. 41 P. 1906-1916.

73. Feldman D. Contributions to the "two-armed bandit" problem// Ann. Math. Statist. 1962. V. 33. P. 847-856.

74. Feller W. An introduction to probability theory and its applications. V. 1. John Willey & Sons, 1970.

75. Gittins J.C. Bandit processes and dinamic allocation indices// J. Roy. Statist. Soc. B. 1979. V. 41. P. 148-177.

76. Hellman M.E., Cover T.M. Learning with Finite Memory // Ann. Math. Statist. 1970. V. 41. №3. P. 765-782.

77. Isbell J.R. On a problem of Robbins// Ann. Math. Statist. 1959. V. 30. P. 606-610.

78. Kolnogorov A. V. The strategies of the play against "the two-armed bandit" with unimproved in order guaranteed speed of convergency of the mean expected income// Advances in Modelling & Analysis, B, AMSE Press, V. 28. № 2. 1993. P. 1-10.

79. Lakshmivarahan S. Learning algorithms theory and applications. N.Y.; Heidelberg; Berlin; Springer Verlag, 1981.

80. Lai T.L. Adaptive treatment allocation and the multi-armed bandit problem// The Annals of Statist. 1987. V. 15. № 3. P. 1091-1114.

81. Mandelbaum A. Continious multi-armed bandits and multiparameter processes// The Annals of Prob. 1987. V. 15. № 4. P. 1527-1556.

82. Fon Neumann J., Morgenstern 0. Game theory and economical behaviour. 1947.

83. Presman E.L., Sonm I.M. Two and many-armed bandit problems with infinite horizon// Lecture Notes in Math. 1983. V. 1021. P. 526-540. Springer. New York.

84. Presman E.L., Sonin I.M. Sequential Control with Incomplete Information. Academic Press. 1990.

85. Robbins H. Some aspects of the sequential design of experiments// Bulletin of Amer. Math. Soc. 1952. V. 58. № 5. P. 527-535.

86. Robbins H. A sequential decision problem with finite memory// Proc. National Academy of Sciences. 1956. V. 42. № 3. P. 920-923.

87. Samuels S.M. Randomized rules for one two-armed bandit problem with finite memory// Ann. Math. Statist. 1968. V. 39. P. 2103-2107.

88. Smith C. V. Pyke R. The Robbins-Isbell two-armed bandit problem with finite memory// Ann. Math. Statist. 1965. V. 36. P. 1375-1386.

89. Vogel W. A sequential design for the two-armed bandit problem// Ann. Math. Statist. 1960. V. 31, P. 430-443.

90. Vogel W. An asimptotic minimax theorem for the two-armed bandit problem// Ann. Math. Statist. 1960. V. 31, P. 444-451.