Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 275
Текст из файла (страница 275)
72 для состояния (1, 1), две выборки со значениями О. 76 и О. 84 для состояния (1, 2), две выборки со значениями О. 80 и О. 88 для состояния (1, 3) и т.д. Таким образом, в конце каждой последовательности алгоритм вычисляет наблюлаемое будущее вознаграждение для каждого состояния и обновляет соответствующим образом оценку полезности для этого состояния путем ведения текущего среднего значения для каждого состояния в таблице. В пределе, после выполнения бесконечного количества попыток, среднее по выборкам сходится к значению истинного ожидания, приведенному в уравнении 2!.!. Очевидно, что непосредственная оценка полезности представляет собой один из видов контролируемого обучения, в котором каждый пример задает состояние в качестве входных данных, а наблюдаемое будущее вознаграждение — в качестве выходных. Это означает, что данный метод позволяет свести обучение с подкреплением к стандартной задаче индуктивного обучения, которая рассматривалась в главе 18.
В разделе 21.4 описано использование более мощных видов представлений для функции полезности, таких как нейронные сети. Методы обучения для этих представлений могут применяться непосредственно к наблюдаемым данным. Метод непосредственной оценки полезности позволяет успешно свести задачу обучения с подкреплением к задаче индуктивного обучения, о которой уже многое известно. Но, к сожалению, этот метод не позволяет воспользоваться очень важным источником информации — в нем не учитывается тот факт, что полезности состояний не являются независимыми! Дело в том, что оу- палезпасть каждого состояния равна сумме ега сайственнага вознаграждения и ожидаемой полезности ега састаянийпрегмникав. Это означает, что значения полезности подчиняются уравнениям Беллмана для данной конкретной стратегии (см.
также уравнение 17.10): !015 Глава 21. Обучение с подкреплением лезность, поскольку оно ведет к состоянию (3,3), но метод непосредственной оценки полезности не позволяет ничего определить с помощью обучения до конца этой попытки. В более широком контексте метод непосредственной оценки полезности можно рассматривать как поиск в пространстве гипотез для (), которое имеет размеры намного большие, чем необходимо, поскольку включает также много функций, которые нарушают уравнения Беллмана. По этой причине данный алгоритм часто сходится очень медленно.
Адаптивное динамическое программирование Для того чтобы можно было воспользоваться преимуществами наличия информации об ограничениях между состояниями, агент должен определить с помощью обучения, как связаны эти состояния. ск Агент, действующий по принципу адаптивного динамического программирования (или сокращенно А1)Р— Ат)арг!уе 0упаш!с Ргоагатгп!пд), функционирует путем определения с помощью обучения модели перехода в этой среде по мере выполнения своих действий и находит решение в соответствующем марковском процессе принятия решений, используя метод динамического программирования. Для пассивного обучаюгцегося агента такой подход означает, что он должен подставлять полученную с помощью обучения модель перехода т(п, п(э), д' ) и наблюдаемые вознаграждения л(д) в уравнения Беллмана 21.2 для вычисления полезностей состояний.
Как было отмечено при обсуждении в главе 17 принципа итерации по стратегиям, эти уравнения являются линейными (для них не требуется максимизация), поэтому они могут быть решены с помощью любого пакета линейной алгебры. Еше один вариант состоит в том, что может быть принят подход, основанный на принципе молифицированной итерации по стратегиям (см. с. 831), в котором используется упрощенный процесс итерации по значениям для обновления оценок полезностей после каждого изменения в модели, определяемой с помощью обучения.
Поскольку эта модель после каждого наблюдения подвергается только незначительным изменениям, в процессе итерации по значениям в качестве начальных значений могут использоваться предыдущие оценки полезностей, а сами вычисления с помощью этого метода должны сходиться очень быстро. Сам процесс определения модели с помощью обучения осуществляется просто, поскольку среда полностью наблюдаема. Это означает, что данная задача обучения представляет собой задачу контролируемого обучения, в которой входными данными являются пары "состояние — действие", а выходными — результирующие состояния.
В простейшем случае модель перехода можно представить как таблицу вероятностей и следить за тем, насколько часто возникает каждый результат действия', оценивая вероятность перехода т ( п, а, э ' ) по данным о частоте, с которой достигается состояние э' при выполнении лействия а в состоянии сь Например, в трех трассировках попыток, приведенных на с.
10!3, действие дздйс в состоянии (1, 3) выполняется три раза, и двумя из трех результирующих состояний становится со- СТОЯНИЕ (2, 3), ПОЭТОМУ ВЕРОЯтНОСтЬ ПЕРЕХОДа Т( (1, 3), Лабгйг, (2, 3) ) ОЦЕНИВается как 2! 3. ' Это — опенка максимального правдоподобия, которая рассматривается в главе 20 Способ байесовского обновления с использованием распределения априорных вероятностей Дирихле может оказаться лучше.
101б Часть 1[[. Обучение Полная программа агента для пассивного агента АРР приведена в листинге 21.1. Производительность этой программы в мире 4х3 показана на рис. 21.2. Судя по тому, насколько быстро улучшаются полученные им оценки значений, агент АРР действует настолько успешно, насколько это возможно, учитывая его способность определять с помощью обучения модель перехода. В этом смысле данный проект агента может служить эталоном, с которым можно будет сравнивать производительность других алгоритмов обучения с подкреплением.
Тем не менее в больших пространствах состояний такой подход становится не вполне осуществимым. Например, в нардах для его использования потребуется решить приблизительно 10" уравнений с 10" неизвестными. Листинг 21.1. Ачгорнтм агента лля пассивного обучения с подкреплением, основанный на адаптивном динамическом просраммнрованнн. Для упрощения кода было принято предположение, что каждый результат восприятия можно разделить на ннформанню о состоянии н сигнал о вознаграждении Еппсеьоп Раззьуе-А?)Р-Адепт(регсере) кесцгпв действие а ьпрпсвь регсерг, результаты восприятия, обозначающие текущее состояние з' и сигнал вознаграждения г' всаеьс: л, зафиксированная стратегия щс[р, марковский процесс принятия решений с моделью Т, вознаграждениями К, коэффициентом обесценивания у У, таблица значений полезностей, первоначально пустая АЬ, таблица частот пар "состояние-действие", первоначально содержащая нули И„,, таблица частот троек "состояние-действие-состояние", первоначально содержащая нули з, а, предыдущие состояние и действие, первоначально пустые ьЕ состояние з' является новым Еиеп Оо У[я'] < — г'; К[з'] с в г' ЕЕ состояние з не пусто Еиеп сто увеличить значения Ггю[з, а] и Х4, [з, а, з') Еок енса С, такого что значение А,, [з, а, С] является ненулевым сто Т[З, а, С] С вЂ” Аю, [З, а, С! / г)„[З, а] У с в уа1це-песегщьпасьоп[л, У, щс)р) 1Е тегш1па1т[з'] еЬеп з, а с- пустые значения е1ве з, а +- з', л[в'1 теситп а Обучение с учетом временной разницы Существует также возможность взять (почти) самое лучшее из обоих описанных выше подходов; это означает, что можно аппроксимировать приведенные выше уравнения ограничений, не решая их для всех возможных состояний.
ср Ключом к созданию этого метода становится то, что можно использовать наблюдаемые переходы для корректировки значений ниблюдаемых состояний тик, чтобы они согласовывались с уравнениями ограничений. Рассмотрим, например, переход из состояния [1, 3) в состояние [2, 3) во второй попытке, показанной на с. 1013. Предположим, что в результате первой попытки были получены оценки полезности [Г'[1, 3) =О. 84 Глава 21. Обучение с подкреплением 1017 0,6 Я~ 05 й в е й а 0,1 ы д 0,8 э Д 0,6 й 0,4 сз 02 0 0 0 0 20 40 60 80 100 Катичеетао попыток 20 40 60 80 !00 Количество попыток а) б) )ттс 21 2 Кривые писсивного обучения А РР для мира езсз, полученные при отпимальной стратегии, которая показана на рис. 21.
12 оценки полезности для избраннот подмножестпва состояний, полученные как функции от количества попыток (а), Обратите внимание на то, что примерно при 78-й попытке происходят значительные изменения; именно тогда агент впервые попадает в терминальное состояние с полезностью -2, пютветствующее квадрату (4,2); среднеквадратичная ошибка в оценке для ц (2, 2 ), усредненная по 20 прогонам, состоящим из 100попыток каждьш (б) поэтому значение (Г'(1, 3) будет равно О. 88.
Таким образом, текушая оценка этой полезности, равная О . 84, может оказаться немного заниженной и должна быть увеличена. Более обший вывод состоит в том, что если происходит переход из состояния э в состояние э', то к значению полезности (р( э) применяется следуюшее обновление; (р(в) т — о" (в) + а(д(п) т у Г/'(в') — ьп(в) ) (21.3) где а — параметр скорости обучения. Поскольку в этом правиле обновления используется разность между полезностями последовательных состояний, соответствуюшее уравнение часто называют уравнением 'ж временной разности, или сокрашенно Т)3 (Тешрога1 П!йегепсе).
Основная идея всех методов временной разности состоит в том, что вначале определяются условия, выполняемые локально, когда оценки полезностей являются правильными, а затем составляется уравнение обновления, в котором оценки переносятся в это идеальное уравнение "равновесия". В случае пассивного обучения равновесие задается уравнением 21.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
