БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ
Подход, основанный на обучении с подкреплением, предложил Тьюринг [1519], [1520], но он не был убежден в его общей эффективности и писал, что "использование наказаний и вознаграждений в лучшем случае может составлять лишь часть процесса обучения". По-видимому, одним из первых успешных исследований по машинному обучению была работа Артура Самюэла [1349]. Хотя эта работа не была основана на теоретическом фундаменте и имела целый ряд недостатков, она содержала большинство современных идей в области обучения с подкреплением, включая применение временной разности и функциональной аппроксимации. Примерно в то же время исследователи в области теории адаптивного управления Видроу и Хофф [1587], опираясь на работу Хебба [638], занимались обучением простых сетей с помощью дельта-правила. (Долго существовавшие неправильные представления о том, что обучение с подкреплением является частью проблематики нейронных сетей, могло быть вызвано тем, что связь между этими научными областями установилась так рано.) Как метод обучения с подкреплением на основе аппрокси-матора функции может также рассматриваться работа Мичи и Чамберса [1046], посвященная системе "тележка-шест". Психологические исследования в области обучения с подкреплением начались гораздо раньше; хороший обзор по этой теме приведен в [653]. Непосредственные свидетельства того, как осуществляется обучение с подкреплением у животных, были получены в исследованиях поведения пчел, связанного с добычей пищи; достоверно обнаружен нейронный аналог структуры передачи сигнала вознаграждения в виде крупного нейронного образования, связывающего рецепторы органов взятия нектара непосредственно с двигательной корой [1070]. Исследования, в которых используется регистрация активности отдельной клетки, показали, что допаминовая система в мозгу приматов реализует нечто напоминающее обучение на основе стоимостной функции [1369].
Связь между обучением с подкреплением и марковскими процессами принятия решений была впервые отмечена в [1580], но разработка методов обучения с подкреплением в рамках искусственного интеллекта началась с исследований, проводимых в Массачусетсском университете в начале 1980-х годов [76]. Хороший исторический обзор подготовлен Саттоном [1477]. Уравнение 21.3, приведенное в этой главе, представляет собой частный случай общего алгоритма TD(A) Саттона при Х=0. В алгоритме TD(A) обновляются значения всех состояний в последовательности, ведущей вплоть до каждого перехода, на величину, которая уменьшается в зависимости от Xt для состояний, отстоящих на t шагов в прошлое. Алгоритм TD(1) идентичен правилу Видроу-Хоффа, или дельта-правилу. Бойян [162], опираясь на [170], доказал, что в алгоритме TD(A) и связанных с ним алгоритмах результаты, полученные опытным путем, используются неэффективно; по сути они представляют собой алгоритмы оперативной регрессии, которые сходятся гораздо медленнее, чем алгоритмы автономной регрессии. Предложенный Бойяном алгоритм LSTD(A) представляет собой оперативный алгоритм, позволяющий достичь таких же результатов, как и алгоритм автономной регрессии.
Применение сочетания метода обучения на основе временной разности с методом формирования моделируемых результатов опытов с помощью модели было предложено в архитектуре Саттона Dyna [1479]. Идея выметания с учетом приоритетов была предложена независимо Муром и Аткесоном [1077], а также Пенгом и Уильямсом [1203]. Метод Q-обучения был разработан в докторской диссертации Уоткинса [1558].
Задачи с n-рукими бандитами, которые моделируют задачу исследования непоследовательных решений, были глубоко проанализированы в [116]. Оптимальные стратегии исследования для нескольких постановок задач могут быть получены с помощью метода, называемого индексами Гиттинса [561]. Целый ряд методов исследования, применимых для решения задач последовательного принятия решений, обсуждается в [74]. В [171] и [785] описаны алгоритмы, позволяющие исследовать неизвестные варианты среды и гарантирующие сходимость к стратегиям, близким к оптимальным, за полиномиальное время.
Истоки идей по применению функциональной аппроксимации в обучении с подкреплением можно найти в работах Самюэла, который использовал линейные и нелинейные функции оценки, а также методы выбора характеристик для уменьшения пространства характеристик. В дальнейшем были разработаны такие методы, как СМАС (Cerebellar Model Articulation Controller) [12], который по сути сводится к использованию суммы перекрывающихся локальных ядерных функций, и ассоциативные нейронные сети [75]. В настоящее время в качестве аппроксиматоров функций наиболее широко используются нейронные сети. Наиболее известным приложением является программа TD-Gammon [1499], [1500], которая описывалась в данной главе. Одной из существенных проблем, возникающих при использовании обучающихся по методу TD агентов, основанных на нейронной сети, является то, что они, как правило, забывают полученные раньше результаты опытов, особенно касающиеся тех частей пространства состояний, которых они стали избегать после приобретения достаточной компетентности. Этот недостаток может приводить к катастрофическому отказу, если снова возникают подобные обстоятельства. Такую проблему позволяет устранить функциональная аппроксимация с помощью обучения на основе экземпляра (instance-based learning) [477], [1159].
Тема, касающаяся сходимости алгоритмов обучения с подкреплением, в которых применяется функциональная аппроксимация, требует чрезвычайно формального освещения. В случае использования аппроксиматоров линейных функций результаты обучения по методу TD неизменно улучшались [338], [1477], [1515], но было показано, что при использовании нелинейных функций обнаруживаются некоторые примеры отсутствия сходимости (для ознакомления с этой темой см. [1515]). В [1172] описан новый тип алгоритма обучения с подкреплением, который сходится при использовании любой формы аппроксиматора функции, при условии, что для наблюдаемых данных может быть найдена аппроксимация с наилучшим соответствием.
Методы поиска стратегии вышли на передний план под влиянием исследований Уильямса [1597], который разработал семейство алгоритмов Reinforce. Дальнейшие исследования, описанные в [86], [981] и [1478], позволили усилить и обобщить результаты достижения сходимости в методе поиска стратегии. Алгоритм Pegasus был предложен Энджи и Джорданом [1134], но аналогичные методы изложены в докторской диссертации Ван Роя [1535]. Как упоминалось в этой главе, производительность стохастической стратегии представляет собой непрерывную функцию от ее параметров, что способствует применению методов поиска с учетом градиента. Это — не единственное преимущество указанных методов; в [721] доказано, что стохастические стратегии обычно функционируют в частично наблюдаемых вариантах среды лучше, чем детерминированные стратегии, если те и другие ограничиваются действиями, основанными на текущих результатах восприятия. (Одна из причин этого состоит в том, что стохастическая стратегия с меньшей вероятностью "заходит в тупик1', встретив какое-то невидимое препятствие.) Кроме того, в главе 17 было указано, что оптимальные стратегии в частично наблюдаемых задачах MDP представляют собой детерминированные функции от доверительного состояния, а не от текущих результатов восприятия, поэтому можно рассчитывать на получение еще лучших результатов с помощью слежения за доверительным состоянием с использованием методов фильтрации, приведенных в главе 15. К сожалению, пространство доверительных состояний является многомерным и непрерывным, и еще не разработаны эффективные алгоритмы обучения с подкреплением на основе доверительных состояний.
Реальные варианты среды также характеризуются невероятной сложностью с точки зрения количества примитивных действий, требуемых для достижения значимых вознаграждений. Например, роботу, играющему в футбол, могут потребоваться сотни тысяч отдельных движений ног для того, чтобы забить мяч. Одним из широко применяемых методов, который первоначально использовался при обучении животных, является так называемый метод формирования вознаграждения (reward shaping). Он предусматривает предоставление агенту дополнительных вознаграждений за то, что он "добивается успехов". Что касается футбола, то такие вознаграждения могут предоставляться за удар по мячу или за отправку мяча в сторону ворот. Подобные вознаграждения позволяют существенно повысить скорость обучения, асам способ их предоставления является очень простым, но существует опасность того, что агент обучится максимизации таких псевдовознаграждений и не будет стремиться к истинным вознаграждениям; например, многочисленных контактов с мячом можно добиться, стоя рядом с мячом и "совершая колебательные движения". В [1133] показано, что агент все равно будет искать с помощью обучения оптимальную стратегию, при условии, что псевдовознаграждение F{s, a, s' ) удовлетворяет соотношению F(s, a, s' ) =уФ (s' ) -Ф (s), где Ф — произвольная функция от состояния. Функцию Ф можно составить таким образом, чтобы она отражала все желательные аспекты состояния, такие как достижение подцелей или уменьшение расстояния до целевого состояния.
Выработку сложных вариантов поведения можно также обеспечить с помощью методов иерархического обучения с подкреплением, которые представляют собой попытку решать задачи на нескольких уровнях абстракции, во многом аналогично методам планирования HTN, описанным в главе 12. Например, цель "забить мяч" можно разделить на подцели "овладеть мячом", "приближаясь к воротам, обвести противников" и "ударить по воротам", а каждая из этих подцелей может быть дополнительно разделена на двигательные варианты поведения еще более низкого уровня. Фундаментальный результат в этой области получен Форестьером и Варайя [481], которые доказали, что варианты поведения низкого уровня с произвольной сложностью можно рассматривать как примитивные действия (хотя и учитывая при этом то, что они могут потребовать разного количества времени) с точки зрения вариантов поведения более высокого уровня, в которых они вызываются. В современных подходах [32], [397], [1177], [1478] эти результаты используются для создания методов, позволяющих предоставить агенту частичную программу, которая ограничивает поведение агента так, чтобы оно имело конкретную иерархическую структуру. После этого применяется обучение с подкреплением, чтобы агент определил наилучший вариант поведения, совместимый с этой частичной программой. Сочетание методов функциональной аппроксимации, формирования вознаграждения и иерархического обучения с подкреплением может стать основой успешного подхода к решению крупномасштабных задач.
Хорошим исходным пунктом для дальнейшего изучения литературы по этой теме может служить обзор [759]. В книге Саттона и Барто [1480], двух основоположников этой области, изложение сосредоточено на архитектурах и алгоритмах, а также показано, как методы обучения с подкреплением подпитываются идеями в области обучения, планирования и осуществления действий. В немного более формальной работе [121] приведено строгое изложение основ теории динамического программирования и стохастической сходимости. Статьи по обучению с подкреплением часто публикуются в журналах Machine Learning и Journal of Machine Learning Research, а также в материалах конференций International Conferences on Machine Learning и семинаров Neural Information Processing Systems.