Хаос и обучение поощрением
На первый взгляд, проблема эквивалентна управлению перевёрнутым маятником. Однако, если применить тот же самый алгоритм управления, окажется, что тележка довольно скоро уедет за допустимые пределы (Р.
Хехт-Нильсен очень интересно описывает эксперименты с тележкой, которые проводились в его фирме [46]. Задача кажется простой, но при небольших размерах тележки требует характерного времени реакции около 0.1с,
Рис. 2: Задача о балансировании стержня на тележке. Система управления должна после каждого интервала т выбрать правильное направление / так чтобы угол отклонения стержня ? оставался в пределах [(9тах, (9тах], а тележка не уходила бы за границы дорожки, жтах х жтах.
В начальный момент тележка устанавливается в середину дорожки х = 0 а стержень под некоторым углом ?0 в допустимых пределах.
что превышает возможности человека; все с энтузиазмом берутся за дело, считая что уж у него-то получится, но...). А дело в том, что в этой задаче к одномерному неустойчивому многообразию стержня добавляется двумерное центральное многообразие тележки, так что траектория может свободно перемещаться уже в трёхмерном пространстве.
Но в трёхмерном пространстве интуитивно угадать правильную стратегию уже не получается, нужно учиться. (Следует заметить, что с точки зрения теории управления эта задача довольно элементарная, но мы хотим, чтобы управляла тележкой обучающаяся нейросеть, которая теорию управления не изучала, а может действовать только путём проб и ошибок.) Детали возможного процесса обучения мы рассмотрим в следующем разделе. Здесь мы только отметим, что нейросетевой контроллер можно построить и обучить [77], а управление протекает в хаотическом режиме с одним положительным ляпуновским показателем.
Мы записали активность нескольких нейронов управляющей сети и построили для них автокорреляционную функцию, Рис. 3. Их вид характерен для хаотических систем, хотя собственно архитектура использованной нейросети типа Кохонена никакой собственной хаотической динамики не допускает.
Похожие результаты были получены и для другой модельной задачи стабилизации неустойчивой химической реакции [77].
Таким образом, хаос может возникать в сложных петлях обратных связей, где нейронная сеть играет роль обучающейся системы управления. Можно, однако, спросить, а может ли хаос быть полезен для обработки информации или для обучения?
Как показывают наши результаты, ответ утвердительный, но прежде чем его объяснить, необходимо описать основные идеи поощряемое обучения.
Рис. 3: "Энцефалограмма" для нейронной сети, управляющей тележкой со стержнем.
Графики а и b демонстрируют временную активность двух нейронов (1 когда нейрон активен и О в противном случае). На графиках с и d показана соответствующая автокорреляционная функция.
Видны следы как детерминизма, так и хаотичности.
Хаос и обучение поощрением (reinforcement learning)
Что такое обучение поощрением?
В большинстве книг по нейронным сетям рассматривается два типа обучения, "с учителем" (supervised) и ’’без учителя" (unsupervised). Если для каждого обучающего входного сигнала X известен правильный ответ Y, и этот ответ используется для подстройки связей сети, то говорят, что обучение идёт с учителем.
Оно типично для большинства нейронных сетей. Если же обучение идёт совсем без корректирующего сигнала, то говорят, что обучение идёт без учителя. Примерами могут служить рассмотрение сети Кохонена и Гроссберга (ART), когда для входных сигналов заранее неизвестно, какому кластеру они должны принадлежать. Однако возможна и промежуточная ситуация, когда правильный отклик неизвестен, однако некоторая оценка работы сети может быть дана.
Такая оценка обычно имеет вид скалярного ’’поощряющего" сигнала г: в случае успеха г О, при неудаче г 0, а в нейтральных случаях г = 0. Соответствующий тип обучения был назван обучение поощрением (reinforcement learning) или ’’обучение с критиком". В традиционных нейронных сетях он практически не используется.
Однако он оказывается весьма полезен в ситуациях, где известна конечная цель, но неизвестен правильный способ её достижения (можно поощрять приближение к цели или наказывать за удаление от неё или за медлительность как, цель ещё не достигнута?!). Примером может служить задача о стержне на тележке, когда трудно сказать, в какую сторону сейчас надо было толкать тележку, в то время как заметить выход параметров за допустимые пределы несложно.
В этой связи следует заметить, что поощрение может быть запаздывающим. Примером может служить партия в шахматы: поощрение в виде выигрыша, проигрыша или ничьей получается лишь в результате большого числа ходов, и сказать, какой из них был правильным, а какой нет, зачастую очень сложно.
Проблема определения ответственности каждого действия за конечный результат широко обсуждалась еще в начале 60-х годов и получила название "credit assignment problem".
Весьма вероятно, что высокоорганизованные живые организмы используют какой-либо тип обучения поощрением. У них есть довольно сложный источник поощряющего сигнала, такой как чувство боли или удовлетворения. Видимо, существование этой системы даёт этим организмам преимущество.
Похожие источники поощряющего сигнала использовались и для мобильных роботов [73], они были названы оценочной подсистемой (value system).
Ввиду бурного развития систем искусственного интеллекта и автономных роботов, следует ожидать и всё возрастающего использования методов обучения поощрением. Проблема, однако, заключается в том, что в настоящее время нет достаточно общей теории таких методов.
Сама концепция обучения поощрением недостаточно конкретна и может относиться к слишком разным системам и ситуациям. Однако весьма большой прогресс был достигнут в одном из классов задач, известных как марковский процесс принятия решений (Markov decision process, MDP) или динамическое программирование (Dynamical Programming, DP).
Формальное описание MDP включает (і) окружение (environment), характеризуемое состоянием s, (например, система, которой необходимо управлять, для тележки со стержнем s = {ж, ж, (9, (9}), и (іі) агент (управляющая система), который может выполнять действие а (в примере с тележкой действием было приложение силы if). Для простоты будем считать, что s и а могут принимать только дискретные значения.
Агент получает информацию о состоянии st в момент t, и предпринимает действие at, которое влияет на состояние окружения. После каждого действия окружение меняет своё состояние и агент получает информацию о следующем состоянии и скалярный поощряющий сигнал rt+1. Правило 7г(., а), по которому агент выбирает свои действия, называется политикой (policy).
Обычно 7г(., а) это вероятность выбрать действие а в состоянии s. Детерминированный выбор означает, что только для одного из действий вероятность ненулевая.
Задача агента состоит в том, чтобы выробать оптимальную пол,и,тик,у, которая даёт максимальное интегральное поощрение за большое или бесконечное число действий. В последнем случае сумма Yfj?=i гк может оказаться бесконечной и используют взвешенное (discounted) интегральное поощрение 1к~1гк, 0 7 1 (обычно величина |г*.| огра
ничена).
Вплоть до настоящего момента ситуация выглядела весьма общей. Ограничивающим предположением, сильно облегчающим теоретическое исследование, является то, что динамика окружения предполагается марковской. Обозначим через Р = Р(а,s,.') вероятность перехода окружения из s в s' после действия а, а соответствующее поощрение Я = і?.(а,.,.') (г% всегда равно одному из Я с соответствующими аргументами). Предполагается, что вероятности Р и поощрения Я не зависят от времени, от предыдущих состояний окружения и предшествующих действий агента.
Следовательно, динамику окружения можно описать в терминах управляемой цепи Маркова. Далее мы будем полагать её эргодической.
Если все Р и Я известны, можно вычислить среднее взвешенное поощрение для состояния s, действия а и избранной политики ж путём усреднения по всем возможным будущим траекториям вдоль марковской цепи,
Р(а', s', s) (R(a', s', s) + .. .)^ .
Величины Qir(s,a) были названы ценность действия (action values). Поскольку мы предположили, что 7Г, Р и Я не зависят от времени, в правой части возникают те же ценности действий Qv, поэтому
Это линейная система уравнений для Qv, которую можно решить стандартными методами.
Почему ценности действий Qv так важны? Дело в том, что с их помощью можно улучшать существующую политику, до тех пор пока не будет найдена оптимальная политика, приносящая максимальный выигрыш. После того как все Qv найдены, естественно изменить текущую политику тг так, чтобы в каждом состоянии выбирать наиболее ценное действие а = arg шаха/ Q’n'(,s,o/).
В результате получается новая политика 717. Как показал более 40 лет назад Р. Веллман [14], для новой политики QVl (a,s) Qv(a,s).
Затем можно проделать то же самое с новыми ценностями действий QVl (a, s) и получить следующую политику 7г2 и так далее. Этот процесс итерирования политики сходится к оптимальной
политике 7Г*, которой соответствуют Q*(s,a). Оптимальных политик может быть и несколько, но ценности действий у всех одни и те же.
Существует весьма эффективный численный алгоритм для итерирования политики [14, 83].
Существующие методы обучения поощрением (Reinforcement Learning, RL) [83, 57] развиты для случая, когда все предположения динамического программирования справедливы, но переходные вероятности Р и поощрения R неизвестны. Это означает, что нет возможности найти оптимальную политику при помощи уравнений (13). Проблема напоминает управление тележкой со стержнем, можно действовать только методом проб и ошибок.
Как же нам научиться удерживать стержень?
Идея методов обучения поощрением состоит в том, чтобы оценить те же самые ценности действий Q, но путём усреднения по времени, а не по ансамблю (13), поэтому нам нужна эргодичность. Когда агент в момент t выбирает действие at в состоянии st и на следующем шаге получает поощрение rt+1, последнее может быть использовано для коррекции оценки Q(st,at).
Если сделать достаточно много попыток, оценки могут стать достаточно точными и быть использованы для улучшения политики. Хотя как правило улучшение текущей политики не требует точного знания всех Q, необходимо только знать, для какого действия а величина Q(s,a) является наибольшей.
А эта информация часто может быть получена за разумное время.
Существующие методы обучения поощрением обычно подразделяют на два больших класса [83, 57]: Методы Монте-Карло, когда Q оценивают путём непосредственного усреднения поощрений, полученных после данной комбинации состояние-действие, и методы временных разностей (Temporal Differences, TD), когда оценки получают при помощи итерационных схем. Методы Монте-Карло требуют очень много повторений и сходятся медленно.
Мы не будем их здесь рассматривать. Согласно [83, 57], TD-методы более популярны и обычно сходятся гораздо быстрее.
TD методы основаны на следующем несложном соотношении: когда мы пытаемся оценивать Q экспериментально, оценки связаны как Q(st, at) = 1krk+t+i = rt+1+7Q(.st+1, at+1),
а потому At = rt+i +7Q(t+i, G't+i) Q{st,, a-t) = 0. Если At ф 0, это означает, что текущая оценка нуждается в коррекции. Методика выглядит следующим образом. Используются оценки ценностей действия, зависящие от времени, Q(s, a, t).
Начальные значения Q(s, а, 0) можно выбирать достаточно произвольно. Затем следует выбрать некоторую политику тг и после каждого шага итерационно корректировать уенности действий:
Q{s, a, t + 1) = Q{s,a, t) + ate(s, a, t) At. (14)
Это соотношение содержит два дополнительных фактора скорость обучения at и так называемые коэффициенты пластичности (eligibility traces) e(s,a,t), о которых мы поговорим чуть позже. Для расчёта корректирующего члена А чаще всего используют две основные методики.
a) ’’Sarsa" (в качестве имени используется последовательность st, at, rt+1, ,st+1, at+1, применяемая для расчёта А)
At = rt+г + 73(.*+1, t+і, t) Q(st,at,t).
Метод даёт оценки Q для текущей политики. Тем не менее, если в свою очередь текущие значения Q используются для формирования политики, например, каждый раз выбирается
действие с наибольшей Q(st, a, t) (обычно выбор сложнее, но об этом тоже позднее), то оказывается, что методика допускает одновременно и улучшение политики.
Ъ) " Q-learning",
At = П+і + 7 max Q(.t+i,, t) - Q(st, at, t).
Метод сходится к значениям Q* для оптимальной политки тт* почти независимо от текущей политики л. Зная Q*, нетрудно получить и саму оптимальную политику тг*.
В отношении выбора скорости обучения а серьёзных теоретических ограничений нет. Доказательство сходимости методов RL [83, 57] требует, чтобы at убывали со временм так чтобы J2tat = оо, J2tat 00 (требования методов стохастической аппроксимации), например, at = a0/t.
Иногда описанные методы хорошо работают и для неубывающих at, которые к тому же могут даже не быть очень маленькими. Для некоторых задач известно, что наилучший выбор а = 1 [57].
Теперь обратимся к коэффициентам пластичности. Изначально они появились в моделях обучения нейронов для того чтобы воспроизвести эффекты сходные с условными рефлексами [84]. Такие рефлексы связывают два события, " нейтральное" и " существенное" , разделённые временным промежутком.
Идея состояла в том, что нейроны и связи, ответственные за обработку нейтральных событий, в течение некоторого времени после них сохраняют возможность изменяться (пластичны), поскольку сохраняют память о недавнем событии. Если в течение этого промежутка произойдёт существенное событие, оно может изменить связи, сохранившие пластичность. В результате после нескольких повторений нейтральное событие получает способность вызывать такой же эффект, как и существенное.
Соответствующая математичекая модель нейронов, помимо обычных связей Wijt между ними, включала также величины е^4, названные " eligibility traces", по-видимому, наиболее адекватный перевод коэффициенты пластичности. Правило изменения весов имело вид AWijt ~ (’-ijtgt, где gt сигнал, порождённый "существенным" событием. Первоначально все е^0 = 0. Когда происходит нейтральное событие и связи обретают пластичность, соответствующей коэффициент е становится равным 1 (или увеличивается на 1).
Затем он экспоненциально затухает, et+1 = Aet, А 1. Таким образом, в течение некоторого времени после установки е, соответствующая связь может меняться, однако в дальнейшем эта способность пропадает до новой установки.
В обучении поощрением эта идея была использована как попытка решить упоминавшуюся проблему credit assignment. Когда корректирующий член А вычислен, было бы желательно скорректировать Q не только для последнего состояния st, но и для предшествующих состояний, поскольку последний сигнал поощрения частично характеризует и предыдущие действия. Чтобы это сделать, следует присвоить этим состояниям коэффициент ответственности.
Рецепта, как этого добиться в общем случае, нет, но для эргодических цепей Маркова эффект каждого действия или пребывания в некотором состоянии должен экспоненциально убывать. Следовательно, по крайней мере для некоторых задач, экспоненциально убывающие коэффициенты пластичности могли бы частично решить проблему credit assignment. Соответствующий класс алгоритмов RL был назван TD(A), где А обозначает скорость затухания коэффициентов пластичности. Для каждой пары состояние-действие вводится переменная е(., а, t), е(., а, 0) = 0. Как только окружение оказывается в состоянии st и выбирается действие at, соответствующая Q(st, at) получает способность меняться и мы присваиваем e(.
t, at, t) = 1 (в некоторых версиях e(.t, at, t) = e(.
t, at, t) + 1). Обучение может быть разбито на эпизоды. Например, для стержня на тележке после падения стержня или ухода тележки за допустимые пределы тележка возвращается в центр дорожки, а стержень снова устанавливается почти вертикально.
В таких случаях коэффициенты пластичности также следует установить в ноль.
Согласно [83, 57], коэффициенты пластичности могут существенно ускорить сходимость алгоритмов RL, особенно в ситуациях с запаздывающим поощрением, когда ненулевое ? появляется лишь в результате многих действий. В отношении скорости затухания Л, так же как и весового множителя 7, единственным теоретическим ограничением является 0А1, 071. Некоторые практические рекомендации по выбору а, А и 7 можно найти в статье Дж.
Тесауро [90] (автора получившей известность программы TD-garrirrion, играющей в нарды backgammon на уровне мировых мастеров; в основе программы лежат методы обучения поощрением, а для аппроксимации ценности состояний применяется трёхслойный персептрон с несколькими десятками скрытых нейронов). Однако качество работы методов RL может существенно зависеть от значений параметров, поэтому в каждом конкретном случае может оказаться необходимым проведение специальных тестов.
Приложения обучения поощрением в настоящее время довольно многочисленны, помимо упомянутой игры в нарды это управление сложными механическими системами, роботами, лифтами в многоэтажных зданиях, контроль хаоса и др., см., например, [83, 57, 92, 36, 97].
Какое отношение всё вышеизложенное имеет к нейросетям? Связи с нейросетями многочисленны.
Во-первых, методы обучения поощрением используют функции, аппроксимация которых необходима в некоторых вариантах методов [57, 83]: л : s a, Q : s X а і?1, R, Р : s X s X а і?1, иногда и некоторые другие. Подобные аппроксимации могут быть получены с помощью какой-либо из аппроксимирующих сетей, например, многослойного персептрона. Во-вторых, состояние s часто изменяется непрерывно.
Версии динамического программирования и обучения поощрением для непрерывного случая также существуют, но они гораздо сложнее, чем в дискретном случае. Поэтому часто пространство возможных состояний разбивается на множество областей, каждая из которых рассматривается как одно дискретное состояние. Эту процедуру квантования состояний естественно поручить нейросети для векторного квантования, такой как сеть Кохонена или ART [18, 59].
Например, нейросетевой контроллер может иметь вид двухступенчатой сети Кохонена. В качестве входного сигнала сеть получает причём каждый нейрон отвечает одному дискретному состоянию.
После выбора победителя, нейрон, отвечающий текущему состоянию, включается и посылает сигнал следующей сети через ряд выходных связей с весами, равными Q. Во второй конкурентной сети каждый нейрон соответствует одному действию. После соревнования выбирается действие с наибольшим Q. Таким образом, нейронные сети удобный инструмент методов RL, иногда даже используется термин " нейродинамическое программирование" [15] (не путать с нейролингвистическим программированием из области психологии).
Существует и связь со сложной динамикой и хаосом. Во-первых, как говорилось в предыдущем разделе, нейросетевой контроллер с поощрительным обучением объединённый с
Рис. 4: Примеры обучения поощрением (Q-learning) для тележки со стержнем. Обучение разбивается на эпизоды, эпизод заканчивается когда х или ? выходят за допустимые пределы (контроллер в этом случае получает отрицательный поощряющий сигнал) или управление успешно протекает вплоть до момента Т = 6000. Последнее означает, что контроллер способен удерживать стержень очень долго, скорее всего, бесконечно долго.
Продолжительность каждого эпизода показана точками. Иногда использовалась е-жадная политика (графики а и с), и стержень иногда падал только из-за случайного действия.
После каждого эпизода тестировалась получающаяся жадная политика, продолжительность удержания стержня для которой показана сплошной линией. Г рафики соответствуют различны параметрам Q-learning. При хорошем выборе (Ь) обучение весьма эффективно.
Из графиков а и с видно, что при некоторых параметрах возможны колебания между различными политиками: контроллер находит хорошую политику, потом забывает, потом находит снова.
неустойчивой динамической системой, может научиться поддерживать её в хаотическом состоянии. На Рис. 4 показан пример такого обучения для системы тележка-стержень. Во-вторых, хаос может быть необходим контроллеру для получения хорошей политики при помощи методов RL с освоением новых действий (exploration).
Рассмотрим этот вопрос более детально.
Обучение поощрением, освоение действий и хаос
Обсудим теперь вопросы формирования политики, т.е. согласно каким же критериям следует выбирать действия в каждом заданном состоянии. В задачах динамического программирования, когда информация о свойствах окружения полна, ценности действия Q* для оптимальной политики могут быть рассчитаны, оптимальным является способ выбора действий с наибольшим Q*.
Однако при обучении методом проб и ошибок такая политика часто оказывается далеко не лучшей, поскольку известны не точные значения Q'. а лишь их оценки. Даже если часть значений Q известна точно, всегда есть вероятность того, что лучшее действие ещё не было испробовано.
Это в свою очередь значит, что истинные Q* ещё неизвестны. Если агент использует только наилучшие из известных действий, он может никогда не найти оптимальной политики. Следовательно, иногда необходимо пробовать неоптимальные действия.
Агент должен осваивать новые возможности путём проб и ошибок. С другой стороны, если агент предпринимает слишком много плохих действий, его эффективность снижается. Поэтому возникает дилемма освоения и эксплуатации [83, 91].
Когда мы рассказывали про метод Q-learning, мы говорили, что он даёт значения Q* для оптимальной политики почти независимо от текущей политики тг: текущая политика должна давать возможность осваивать лучшие действия.
Когда агент всегда выбирает действие с максимальной оценкой Q, такая политика называется жадной (greedy). Было показано, что следование чисто жадной политике без освоения может привести в результате к неоптимальной политике [83].
С другой стороны, иногда следование жадной политике вполне оправдано. Необходимый элемент освоения часто может возникнуть сам собой благодаря блужданию в пространстве политик во время сходимости оценок Q. Можно дополнительно стимулировать освоение, устанавливая высокие начальные приближения для Q ("оптимистичные" начальные данные) и побуждая агента попробовать большинство действий во время обучения.
Для того, чтобы гарантировать освоение новых действий, часто используют политику, называемую е-жадной. Допустим, что в состоянии s есть п возможных действий. Тогда мы выбираем лучшее действие с вероятностью 1 е, а любое иное действие с вероятностью е./(п 1). Когда оценки Q почти сойдутся, освоение уже будет только портить результаты из-за не лучших действий.
Поэтому рекомендуется постепенно уменьшать е с течением времени [83].
Предположим теперь, что окружение нестационарно, хотя изменения редки или невелики, так что модель марковской цепи по-прежнему можно использовать на временах, достаточных для сходимости Q. Благодаря нестационарное™, оптимальная политика со временм может измениться. В этом случае жадная политика может оказаться опасной: освоение благодаря переходным процессам и начальным данным теперь отсутствует, и новую оптимальную политику можно никогда не найти. В таких обстоятельствах важность могут приобретать специальные меры по освоению новых действий, например, в
Рис. 5: Тестовая задача для хаотической политики движение по решётке, (а) В каждом состоянии агент может выполнять 4 действия: вверх, вниз, вправо, влево, если в выбранном неправлении нет пустой клетки, агент остаётся на месте. (Ь) Начальное окружение, агент стартует с клетки "S" и должен достичь цели "G". Заштрихованные клетки агенту недоступны и кратчайший путь занимает 15 шагов.
На каждом шаге агент получает поощрение г = 1, пока не достигнет цели; тогда он получает г = +1 и возвращается на стартовую клетку, (с) В момент t = 2010 одна из блокированных клеток открывается и появляется короткий путь из 5 шагов. Чтобы открыть этот новый путь, агент должен использовать политику с освоением действий.
