Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 276
Текст из файла (страница 276)
Теперь уравнение 21.3 по сути вынуждает агента достичь равновесия, заданного в уравнении 2!.2, но с учетом некоторых нюансов. Прежде всего следует отметить, что данное обновление касается только наблюдаемого преемника э ', тогда как фактические условия равновесия касаются всех возможных следующих состояний. Можно было бы предположить, что это вызовет необоснованно большие изменения в значении (Г'(э) при возникновении очень редких переходов, но фактически, поскольку эти редкие переходы действительно случаются крайне редко, среднее значение О ( э) сходится к правильному значению.
и О"( 2, 3 ) =О . 92. Итак, если будет постоянно происходить этот переход, то следует учитывать, что указанные полезности будут подчиняться следуюшему уравнению; ГР(2,3)=-0.04 т па(2,3) 10!8 Часть Ч]. Обучение Более того, если в качестве коэффициента а вместо фиксированного параметра будет применяться функция со значением, уменьшающимся по мере увеличения количества случаев посещения некоторого состояния, то само значение [)(з) будет сходиться к правильному значению'. Эти рассуждения позволяют составить программу агента, приведенную в листинге 21.2. На рис.
21.3 показана производительность пассивного агента ТР в мире ех3. Обучение этого агента происходит менее быстро по сравнению с агентом АРР, и он показывает более значительную изменчивость, но сам алгоритм агента гораздо проще и требует меньше вычислений в расчете на каждое наблюдение. Обратите внимание на то, что бв алгоритм ТВ не требует применения модели для осуществления предусмотренных в нем об((овлений. Информацию о связях между соседними состояниями поставляет сама среда в форме наблюдаемых переходов.
Листинг 21.2. Ачгорнтм агента для пассивного обучения с подкреплением, который позволяет оп- ределять с помон(ью обучения оценки полезностей на основе временных разностей Еппсеаоп Резваче-тп-Лдепс(регсерс) геепгпв действие а апрцев: регсерс, результаты восприятия, обозначающие текущее состояние з' и сигнал вознаграждения г' ввавас: я, зафиксированная стратегия У, таблица значений полезностей, первоначально пустая №, таблица частот состояний, первоначально содержащая нули з, а, г, предыдущее состояние, действие н вознаграждение, первоначально пустые зг состояние з' является новым е)зеп [([з'] л- г' ая состояние з не пусто ЕЬеп бо увеличить значение № [з] о[в] +- и[з) + а((№[я] ) ) (г + у о[в') — ц[з] ) аг тегщапа12[я'] еЬеп з, в, г л- пустые значения е1ве з, а, г л- я', я[з'1, г' геецгп е Подход на основе АРР и подход на основе ТР фактически тесно связаны. В обоих этих алгоритмах предпринимаются попытки внести локальные корректировки в оценки полезностей, для того чтобы обеспечить "согласование" каждого состояния с его преемниками.
Одно из различий между ними состоит в том, что в алгоритме ТР состояние корректируется для согласования с его наблюдаемым преемником (уравнение 21.3), а в алгоритме АРР состояние корректируется для согласования со всеми преемниками, которые могут быть получены с учетом весов их вероятностей [уравнение 21.2). Это различие исчезает, когда результаты корректировок ТР усредняются по большому количеству переходов, поскольку частота появления каждого преемника в множестве переходов приблизительно пропорциональна его вероятности. Более важное различие состоит в том, что в алгоритме ТР выполняется отдельная корректировка в расчете на каждый наблюдаемый переход, а в алгоритме АРР выполняется столько корректировок, сколько требуется для восстановления согла- з Формально требуется, пабы соблюдались условия ~~> а(п) = н ~~~ а'(л) < .
Зтнм условиям уловлепюряет функция затухания а(л)=туп, а на рнс 2).3 использовалась функция а(п)ево~(зэ - ). Глава 2 !. Обучение с подкреплением !О!9 выполняется столько корректировок, сколько требуется для восстановления согласованности между оценками полезностей г) и моделью среды щ Хотя наблюдаемый переход вносит в 2' только локальное изменение, его результаты могут потребовать распространения по всем полезностям щ Таким образом, алгоритм ТР может рассматриваться как грубое, но эффективное первое приближение алгоритма АРР.
0,6 и 0,5 й= ' о о й й 0,4 ь. И „=0,3 й пы О в о в Х. 0,1 ы к 0,8 И я 0,6 о ц 0,4 ез 0,2 0 0 0 100 200 300 400 500 0 20 40 60 80 100 Количество попыток Ковичеетво попыток а) б) рис. 21.3. Кривые обучения с помощью алгоритма 222 для мира акзт оценки полезности для избранного подмножества состояниб, полученные как дгункции от количества попыток (а); среднеквадратичная ошибка в оценке для П щ, 21, усредненная по 20 прогонам, состоящим из 500 попыток каждыи (бй Показаны результаты только для первых 100 попыток, чтобы можно было провести сравнение с рис.
2!.2 Каждая корректировка, внесенная алгоритмом АРР, с точки зрения пользователя алгоритма ТР может рассматриваться как результат "псевдоэксперимента", полученный путем моделирования в текущей модели среды. Подход, предусмотренный в алгоритме ТР, можно дополнить в целях использования модели среды для выработки результатов нескольких псевдоэкспериментов, иначе говоря, переходов, возможность осуществления которых агент ТР может допустить согласно его текущей модели.
В ответ на каждый наблюлаемый переход агент ТР может вырабатывать большое количество воображаемых переходов. Благодаря этому результирующие оценки полезностей ТР будут все больше и больше аппроксимировать соответствующие оценки АРР, разумеется, за счет увеличения продолжительности времени вычислений. Аналогичным образом могут создаваться все более эффективные версии алгоритма АРР путем непосредственной аппроксимации алгоритмов для итерации по значениям или итерации по стратегиям. Напомним, что полная итерация по значениям может быть трудновыполнимой, когда количество состояний велико.
Олнако многие этапы корректировки являются чрезвычайно малыми. Одним из возможных подходов, применимых для быстрой выработки достаточно качественных ответов, является ограничение количества корректировок, внесенных после каждого наблюдаемого перехода. Можно также использовать какую-то эвристику для ранжирования возможных корректировок, с тем чтобы в дальнейшем осуществлять только наиболее значимые из них. Эвристика, предусматривающая 'оь выметание с учетом приоритетов, позволяет предпочесть вариант с внесением корректировок в состояния, возможные преемники которых уже подвергались большим корректировкам 1020 Часть У1. Обучение в их собственных оценках полезностей.
Приближенные алгоритмы АРР, в которых используются подобные эвристики, обычно обеспечивают обучение примерно с таким же быстродействием, как и полные алгоритмы АРР, с точки зрения количества обучающих последовательностей,но могут оказаться на несколько порядков величины более эффективными с точки зрения объема вычислений (см. упр. 21.3.) Это дает возможность применять такие алгоритмы для обработки пространств состояний, намного превышающих по размерам те, которые являются приемлемыми для полного алгоритма АРР. Приближенные алгоритмы АОР имеют еще одно дополнительное преимущество: на ранних этапах обучения в новой среде молель среды т часто далека от правильной, поэтому нет смысла слишком точно вычислять функцию полезности для согласования с ней. Приближенный алгоритм позволяет использовать минимальную величину корректировки, которая уменьшается по мере того, как модель срелы становится все более точной.
Это позволяет устранить очень продолжительные итерации по значениям, которые могут возникать на ранних этапах обучения из-за больших изменений в модели. 21.3. АКТИВНОЕ ОБУЧЕНИЕ С ПОДКРЕПЛЕНИЕМ Пассивный обучающийся агент руководствуется постоянно заданной стратегией, которая определяет его поведение, а активный агент должен сам принимать решение о том, какие действия следует предпринять. Начнем с описания агента, действующего с помощью адаптивного динамического программирования, и рассмотрим, какие изменения необходимо внести в его проект, чтобы он мог функционировать с учетом этой новой степени свободы. Прежде всего агенту потребуется определить с помощью обучения полную модель с вероятностями результатов для всех действий, а не просто модель для заданной стратегии.
Для этой цели превосходно подходит простой механизм обучения, используемый в алгоритме Раявуче-Рлр-Адепг. Затем необходимо принять в расчет тот факт, что агент должен осуществлять выбор из целого ряда действий, Полезности, которые ему потребуются для обучения, определяются оптимальной стратегией; они подчиняются уравнениям Беллмана, приведенным на с.
824, которые мы еше раз приведем ниже для удобства. Эти уравнения могут быть решены для получения функции полезности () с помощью алгоритмов итерации по значениям или итерации по стратегиям, приведенных в главе 17. Последняя задача состоит в определении того, что делать на каждом этапе. Получив функцию полезности и, оптимальную для модели, определяемой с помощью обучения, агент может извлечь информацию об оптимальном действии, составляя одношаговый прогноз для максимизации ожидаемой полезности; еще один вариант состоит в том, что если используется итерация по стратегиям, то оптимальная стратегия уже известна, поэтому агент должен просто выполнить действие, рекомендуемое согласно оптимальной стратегии.
Но действительно ли он должен выполнять именно это действие? 1021 Глава 21. Обучение с подкреплением Исследование среды На рис. 21.4 показаны результаты одной последовательности попыток для агента АПР, который следует рекомендациям по выбору оптимальной стратегии для модели, определяемой с помощью обучения, на каждом этапе. Как оказалось, агент не находит с помощью обучения истинные полезности или истинную оптимальную стратегию! Вместо этого происходит то, что после 39-й попытки агент находит стратегию, позволяющую достичь вознаграждения +1 вдоль нижнего маршрута, проходящего через квадраты (2, 1), (3, 1), (3, 2) и (3, 3) (рис. 21 4). После проведения экспериментов с небольшими вариантами, начиная от 276-й попытки и дальше, агент постоянно придерживается этой стратегии, так и не определив с помощью обучения полезности других состояний и не найдя оптимальный маршрут через квадраты (1,2), (1,3) и (2,3).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
