ИССЛЕДОВАНИЕ СРЕДЫ И N-РУКИЕ БАНДИТЫ
В Лас-Вегасе одноруким бандитом называют игорный автомат определенного типа, в который игрок может вложить монету, потянуть за рукоятку и забрать выигрыш (если только таковой действительно появится). Существует также разновидность этого автомата с п рукоятками, называемая n-руким бандитом. Игрок должен выбрать, какую рукоятку следует потянуть на себя после вкладывания каждой следующей монеты, — ту, которая когда-то дала наибольший выигрыш, а может быть, ту, которую он еще не пытался использовать?
Задача с п-руким бандитом — это формальная модель реальных задач во многих жизненно важных областях, таких как принятие решения о выделении годового бюджета на исследования и разработки по искусственному интеллекту. Каждая рукоятка соответствует определенному действию (такому как выделение 20 миллионов долларов на подготовку новых учебников по искусственному интеллекту), а вознаграждение за подтягивание к себе такой рукоятки соответствует прибыли, полученной от выполнения соответствующего действия (в данном случае — просто колоссальной). Исследование среды, будь то исследование перспектив нового научного направления или зондирование нового товарного рынка, является рискованным, дорогостоящим и связано с неопределенными вознаграждениями; с другой стороны, полный отказ от проведения исследований означает, что не удастся обнаружить новые сферы деятельности, которые могут оказаться прибыльными.
Чтобы правильно сформулировать задачу с n-руким бандитом, необходимо точно определить, что подразумевается под оптимальным поведением. Большинство определений, приведенных в литературе, основано на предположении, что цель состоит в максимизации ожидаемого суммарного вознаграждения, полученного в течение всего срока существования агента. В этих определениях требуется, чтобы ожидаемое вознаграждение оценивалось по всем возможным мирам, в которых может оказаться агент, а также по возможным результатам каждой последовательности действий в любом конкретном мире. В данном случае "мир" определяется моделью перехода T(s,a, s' ). Таким образом, для того чтобы действовать оптимальным образом, агент должен знать распределение априорных вероятностей по всем возможным моделям. Возникающие в конечном итоге задачи оптимизации обычно являются крайне трудно разрешимыми.
В некоторых случаях (например, когда вознаграждение, получаемое от игры на каждом автомате, является независимым и используются обесцениваемые вознаграждения) существует возможность рассчитать индекс Гиттинса для каждого игорного автомата [561]. Этот индекс представляет собой функцию, параметрами которой являются только количество игр, проведенных на игорном автомате, и сумма полученного выигрыша. Индекс для каждого автомата показывает, насколько оправданы дополнительные затраты денег на продолжение игры с учетом комбинации ожидаемой прибыли и ожидаемой стоимости информации. Выбор автомата с наибольшим значением индекса позволяет найти оптимальную стратегию исследования среды. К сожалению, до сих пор не было обнаружено ни одного метода, позволяющего распространить понятие индексов Гиттинса на проблематику задач последовательного принятия решений.
Теорию n-руких бандитов можно использовать для обоснования приемлемости стратегии отбора в генетических алгоритмах (см. главу 4). Если в задаче с n-руким бандитом каждая рукоятка рассматривается как возможная строка генов, а вкладывание монеты для подтягивания одной рукоятки — как воспроизведение этих генов, то генетические алгоритмы должны обеспечить оптимальное вложение монет в игорный автомат с учетом соответствующего множества предположений о независимости.
Хотя задачи с n-рукими бандитами чрезвычайно трудно поддаются точному решению для получения оптимального метода исследования среды, тем не менее возможно предложить приемлемую схему, которая в конечном итоге приводит к оптимальному поведению со стороны агента. Формально любая такая схема должна быть жадной в пределе бесконечного исследования; это свойство сокращенно обозначается как GLIE (Greedy in the Limit of Infinite Exploration). Схема GLIE должна предусматривать опробование каждого действия в каждом состоянии путем осуществления неограниченного количества попыток такого действия для предотвращения появления конечной вероятности того, что будет пропущено какое-то оптимальное действие из-за крайне неудачного стечения обстоятельств. Агент ADP, в котором используется такая схема, должен в конечном итоге определить с помощью обучения истинную модель среды. Кроме того, схема GLIE должна в конечном итоге стать жадной, для того чтобы действия агента стали оптимальными по отношению к определенной с помощью обучения (и поэтому истинной) модели.
Предложено несколько схем GLIE; в одной из простейших из этих схем предусматривается, что агент должен в течение 1/t части времени выбирать случайное действие, а в течение остального времени придерживаться жадной стратегии. Хотя такая схема в конечном итоге сходится к оптимальной стратегии, весь этот процесс может оказаться чрезвычайно замедленным. Более обоснованный подход предусматривает присваивание определенных весов тем действиям, которые агент не опробовал очень часто, стараясь вместе с тем избегать действий, которые считаются имеющими низкую полезность. Такой подход может быть реализован путем модификации уравнения ограничения 21.4 таким образом, чтобы в нем присваивалась более высокая оценка полезности относительно мало исследованным парам "состояние—действие". По сути это сводится к определению оптимистического распределения априорных вероятностей по возможным вариантам среды и вынуждает агента на первых порах вести себя так, как если бы повсеместно были разбросаны замечательные вознаграждения. Допустим, что для обозначения оптимистической оценки полезности состояния s (т.е. ожидаемого будущего вознаграждения) используется запись if (s), и предположим, что N(a, s) — количество попыток опробования действия а в состоянии s. Предположим также, что в обучающемся агенте ADP используется метод итерации по значениям; в таком случае необходимо переписать уравнение обновления (т.е. уравнение 17.6), чтобы включить в него оптимистическую оценку. Именно такая цель достигается с помощью следующего уравнения:
где f(u,n) называется функцией исследования. Эта функция определяет компромисс между жадностью (предпочтениями, отданными высоким значениям и) и любопытством (предпочтениями, отданными низким значениям л, характеризующим действия, которые еще не были опробованы достаточно часто). Функция f(u,n) должна увеличиваться в зависимости от и и уменьшаться в зависимости от п. Безусловно, что существует много возможных функций, которые соответствуют этим условиям. Одним из особенно простых определений такой функции является следующее:
где R+ — оптимистическая оценка наилучшего возможного вознаграждения, которое может быть получено в любом состоянии; Ne — постоянный параметр. Результатом применения такой функции становится то, что агент пытается проверить каждую пару "состояние—действие" по меньшей мере Ne раз.
Тот факт, что в правой части уравнения 21.5 присутствует величина if, а не U, очень важен. Может вполне оказаться так, что по мере развития процесса исследования в большом количестве попыток будут опробованы состояния и действия, находящиеся недалеко от начального состояния. Если бы использовалась более пессимистическая оценка полезности, и, то агент вскоре стал бы не склонным проводить дальнейшее исследование среды. А применение оценки if означает, что выгоды от исследования среды распространяются в обратном направлении от границ неисследованных регионов, поэтому получают больший вес действия, ведущие к неисследованным регионам, а не просто действия, которые сами по себе остаются малоизученными. Эффект использования такой исследовательской стратегии наглядно показан на рис. 21.5, который демонстрирует более быструю сходимость к оптимальной производительности в отличие от жадного подхода. Способ действий, очень близкий к оптимальному, обнаруживается всего лишь после 18 попыток. Обратите внимание на то, что сами оценки полезности не сходятся так же быстро. Это связано с тем, что агент довольно рано прекращает исследование частей пространства состояний, не предоставляющих вознаграждения, и в дальнейшем посещает их только "по случаю". Но благодаря такому подходу агент приобретает идеальное понимание того, что не следует задумываться о точных значениях полезностей состояний, которые, как ему известно, являются нежелательными и которых можно избежать.
Определение функции "действие—стоимость" с помощью обучения
Теперь, после разработки алгоритма активного агента ADP, рассмотрим, как сконструировать активного агента, обучающегося по методу временной разности. Наиболее очевидным отличием от пассивного варианта является то, что агенту больше не предоставлена заданная стратегия, поэтому для определения с помощью обучения функции полезности и агенту потребуется определить с помощью обучения некоторую модель, чтобы иметь возможность выбрать с учетом значения и некоторое действие, выполнив прогнозирование на один шаг вперед. Задача приобретения модели для агента TD идентична такой же задаче для агента ADP. А что можно сказать о самом правиле обновления TD? Возможно, что следующее утверждение на первый взгляд покажется удивительным, но правило обновления 21.3 остается неизменным. Такая ситуация может показаться странной по следующей причине: предположим, что агент делает шаг, который обычно приводит в приемлемое место назначения, но из-за наличия недетерминированности в самой среде в конечном итоге агент оказывается в катастрофическом состоянии. Правило обновления TD позволяет отнестись к этой ситуации так же серьезно, как если бы полученным итогом был нормальный результат действия, тогда как можно было предположить, что агент не должен слишком сильно об этом беспокоиться, поскольку такой итог возник лишь из-за стечения обстоятельств. Безусловно, такой маловероятный результат в большом множестве обучающих последовательностей может возникать достаточно редко, поэтому можно надеяться, что в долговременной перспективе его последствия получат вес, пропорциональный их вероятности. Еще раз отметим следующее — можно доказать, что алгоритм TD сходится к тем же значениям, что и ADP, по мере того как количество обучающих последовательностей стремится к бесконечности.
Есть также альтернативный метод TD, называемый Q-обучением, в котором предусматривается определение с помощью обучения некоторого представления "действие-стоимость" вместо определения полезностей. Для обозначения стоимости выполнения действия а в состоянии s будет использоваться запись Q[a,s). Отметим, что Q-значения непосредственно связаны со значениями полезностей следующим образом:
На первый взгляд может показаться, что Q-функции представляют собой лишь еще один способ хранения информации о полезностях, но они обладают очень важным свойством: агенту TD, который определяет Q-функцию с помощью обучения, не требуется модель ни для обучения, ни для выбора действия. По этой причине Q-обучение называют безмодельным методом. Как и в случае полезностей, можно записать следующее уравнение для ограничений, которое должно соблюдаться в точке равновесия, когда Q-значения являются правильными:
Как и в случае обучающегося агента ADP, это уравнение может непосредственно использоваться в качестве уравнения обновления для процесса итерации, в котором вычисляются точные Q-значения при наличии оцениваемой модели. Но для этого требуется, чтобы с помощью обучения осуществлялось также определение модели, поскольку в уравнении используется вероятность T(s, a, s' ). С другой стороны, в подходе на основе временной разности модель не требуется. Уравнение обновления для Q-обучения по методу TD, которое вычисляется каждый раз, когда в состоянии s, ведущем к состоянию s1, выполняется действие а, является следующим:
Полный проект агента для исследующего среду Q-обучающегося агента, в котором используется метод TD, приведен в листинге 21.3. Обратите внимание на то, что в нем используется точно такая же функция исследования ?, которая была предусмотрена для исследующего среду агента ADP, поэтому возникает необходимость вести статистические данные о выполненных действиях (таблицу i\7). Если бы применялась более простая исследовательская стратегия (скажем, выбор действий случайным образом в некоторой части этапов, притом что эта часть уменьшается со временем), то можно было бы отказаться от ведения этих статистических данных.
Такой Q-обучающийся агент определяет с помощью обучения оптимальную стратегию для мира 4x3, но достигает этой цели с гораздо меньшей скоростью по сравнению с агентом ADP. Это связано с тем, что метод TD не вынуждает агента добиваться согласованности значений во всей модели. В связи с этим сравнением возникает общий вопрос: что лучше — определять с помощью обучения модель и функцию полезности или функцию "действие—значение" без модели? Иными словами, в чем состоит наилучший способ представления функции агента? Это —фундаментальный вопрос искусственного интеллекта. Как было указано в главе 1, традиционно одной из ключевых характерных особенностей многих исследований по искусственному интеллекту была (часто не выраженная явно) приверженность подходу, основанному на знаниях. Такой подход сводится к предположению, что наилучший способ задания функции агента состоит в формировании представления некоторых аспектов среды, в которой находится агент.
Листинг 21.3. Проводящий исследование среды Q-обучающийся агент. Это — активный ученик, который определяет с помощью обучения значение Q{a,s) каждого действия в каждой ситуации. В нем используется такая же исследовательская функция ?, как и в проводящем исследование среды агенте ADP, но исключается необходимость определять с помощью обучения модель перехода, поскольку Q-значение любого состояния может быть непосредственно связано с соответствующими значениями его соседних состояний
function Q-Learning-Agent{percept) returns действие a
inputs: percept, результаты восприятия, обозначающие текущее
состояние s' и сигнал вознаграждения г' static: Q, таблица значений действий, индексированная по состояниям и действиям Nsa, таблица частот пар "состояние-действие" s, а, г, предыдущие состояние, действие и вознаграждение, первоначально пустые
if состояние s не пусто then do увеличить значение Nsa[s, а]
Q[a, s]
if Terminal? [s1 ] then s, a, r <— пустое значение else s, a, r <— s' , argmax f (Q[a* , s' ] ,i\7sa[a' , s' ] ) , r1
a'
return a
Некоторые исследователи, и принадлежащие, и не принадлежащие к сообществу специалистов по искусственному интеллекту, выступили с заявлениями, что доступность методов, не требующих применения модели, таких как Q-обучение, означает, что подход, основанный на знаниях, не является необходимым. Тем не менее пока нет почти никаких оснований, позволяющих судить об обоснованности этих заявлений, кроме интуиции. А интуиция авторов в размышлениях о том, какой подход является наиболее перспективным, подсказывает, что по мере усложнения среды преимущества подхода, основанного на знаниях, становятся все более очевидными. Это обнаруживается даже в играх, таких как шахматы, шашки и нарды (см. следующий раздел), где усилия по определению с помощью обучения функции оценки на основе модели увенчались большим успехом, чем методы Q-обучения.