Адаптивное динамическое программирование

Для того чтобы можно было воспользоваться преимуществами наличия информации об ограничениях между состояниями, агент должен определить с помощью обучения, как связаны эти состояния. Агент, действующий по принципу адаптивного динамического программирования (или сокращенно ADP— Adaptive Dynamic Programming), функционирует путем определения с помощью обучения модели перехода в этой среде по мере выполнения своих действий и находит решение в соответствующем марковском процессе принятия решений, используя метод динамического программирования. Для пассивного обучающегося агента такой подход означает, что он должен подставлять полученную с помощью обучения модель перехода T(s,n(s), s* ) и наблюдаемые вознаграждения R(s) в уравнения Беллмана 21.2 для вычисления полезностей состояний. Как было отмечено при обсуждении в главе 17 принципа итерации по стратегиям, эти уравнения являются линейными (для них не требуется максимизация), поэтому они могут быть решены с помощью любого пакета линейной алгебры. Еще один вариант состоит в том, что может быть принят подход, основанный на принципе модифицированной итерации по стратегиям (см. с. 831), в котором используется упрощенный процесс итерации по значениям для обновления оценок полезностей после каждого изменения в модели, определяемой с помощью обучения. Поскольку эта модель после каждого наблюдения подвергается только незначительным изменениям, в процессе итерации по значениям в качестве начальных значений могут использоваться предыдущие оценки полезностей, а сами вычисления с помощью этого метода должны сходиться очень быстро.
Сам процесс определения модели с помощью обучения осуществляется просто, поскольку среда полностью наблюдаема. Это означает, что данная задача обучения представляет собой задачу контролируемого обучения, в которой входными данными являются пары "состояние—действие", а выходными — результирующие состояния. В простейшем случае модель перехода можно представить как таблицу вероятностей и следить за тем, насколько часто возникает каждый результат действия1, оценивая вероятность перехода T(s, a, s' ) по данным о частоте, с которой достигается состояние s' при выполнении действия а в состоянии s. Например, в трех трассировках попыток, приведенных на с. 1013, действие Right в состоянии (1,3) выполняется три раза, и двумя из трех результирующих состояний становится состояние (2,3), поэтому вероятность перехода Т( (1,3) , Right, (2,3) ) оценивается как 2/3.
Полная программа агента для пассивного агента ADP приведена в листинге 21.1. Производительность этой программы в мире 4x3 показана на рис. 21.2. Судя по тому, насколько быстро улучшаются полученные им оценки значений, агент ADP действует настолько успешно, насколько это возможно, учитывая его способность определять с помощью обучения модель перехода. В этом смысле данный проект агента может служить эталоном, с которым можно будет сравнивать производительность других алгоритмов обучения с подкреплением. Тем не менее в больших пространствах состояний такой подход становится не вполне осуществимым. Например, в нардах для его использования потребуется решить приблизительно 1050 уравнений с 1050 неизвестными.
Листинг 21.1. Алгоритм агента для пассивного обучения с подкреплением, основанный на адаптивном динамическом программировании. Для упрощения кода было принято предположение, что каждый результат восприятия можно разделить на информацию о состоянии и сигнал о вознаграждении
function Passive-ADP-Agent (percept) returns действие a
inputs: percept, результаты восприятия, обозначающие текущее
состояние s' и сигнал вознаграждения г' static: п, зафиксированная стратегия
mdp, марковский процесс принятия решений с моделью Т,
вознаграждениями R, коэффициентом обесценивания у U, таблица значений полезностей, первоначально пустая Nsa, таблица частот пар "состояние-действие", первоначально
содержащая нули ATsas', таблица частот троек "состояние-действие-состояние",
первоначально содержащая нули s, а, предыдущие состояние и действие, первоначально пустые
if состояние s' является новым then do
U[s' ] <- г' ; R[s' ] <- г* if состояние s не пусто then do
увеличить значения Nsa[s, а] и Nsas-[sf a, s1] for each t, такого что значение Nsas-[s, a, t] является ненулевым do T[s, a, t] <-Nsas>[s, a, t] / Nsa[s, a] U <— Value-Determination (я, U, mdp)
Обучение с учетом временной разницы
Существует также возможность взять (почти) самое лучшее из обоих описанных выше подходов; это означает, что можно аппроксимировать приведенные выше уравнения ограничений, не решая их для всех возможных состояний. Ключом к созданию этого метода становится то, что можно использовать наблюдаемые переходы для корректировки значений наблюдаемых состояний так, чтобы они согласовывались с уравнениями ограничений. Рассмотрим, например, переход из состояния (1,3) в состояние (2,3) во второй попытке, показанной на с. 1013. Предположим, что в результате первой попытки были получены оценки полезности if (1, 3) =0 . 84
if Terminal? [s' ] then s, a <— пустые значения else s, a <— s', 7i[s'] return a
и[/г(2,3)=0.92. Итак, если будет постоянно происходить этот переход, то следует учитывать, что указанные полезности будут подчиняться следующему уравнению:
l/l(l,3)=-0.04 + (2,3)
поэтому значение if (1,3) будет равно 0.88. Таким образом, текущая оценка этой полезности, равная 0 . 84, может оказаться немного заниженной и должна быть увеличена. Более общий вывод состоит в том, что если происходит переход из состояния s в состояние s', то к значению полезности if (s) применяется следующее обновление:
lf(s) <- lf(s) + a(R(s) + у if(s') - lf(s)) (21.3)
где a — параметр скорости обучения. Поскольку в этом правиле обновления используется разность между полезностями последовательных состояний, соответствующее уравнение часто называют уравнением временной разности, или сокращенно TD (Temporal Difference).
Основная идея всех методов временной разности состоит в том, что вначале определяются условия, выполняемые локально, когда оценки полезностей являются правильными, а затем составляется уравнение обновления, в котором оценки переносятся в это идеальное уравнение "равновесия". В случае пассивного обучения равновесие задается уравнением 21.2. Теперь уравнение 21.3 по сути вынуждает агента достичь равновесия, заданного в уравнении 21.2, но с учетом некоторых нюансов. Прежде всего следует отметить, что данное обновление касается только наблюдаемого преемника s', тогда как фактические условия равновесия касаются всех возможных следующих состояний. Можно было бы предположить, что это вызовет необоснованно большие изменения в значении lf(s) при возникновении очень редких переходов, но фактически, поскольку эти редкие переходы действительно случаются крайне редко, среднее значение if is) сходится к правильному значению.
Более того, если в качестве коэффициента а вместо фиксированного параметра будет применяться функция со значением, уменьшающимся по мере увеличения количества случаев посещения некоторого состояния, то само значение U(s) будет сходиться к правильному значению2. Эти рассуждения позволяют составить программу агента, приведенную в листинге 21.2. На рис. 21.3 показана производительность пассивного агента TD в мире 4x3. Обучение этого агента происходит менее быстро по сравнению с агентом ADP, и он показывает более значительную изменчивость, но сам алгоритм агента гораздо проще и требует меньше вычислений в расчете на каждое наблюдение. Обратите внимание на то, что алгоритм TD не требует применения модели для осуществления предусмотренных в нем обновлений. Информацию о связях между соседними состояниями поставляет сама среда в форме наблюдаемых переходов.
Листинг 21.2. Алгоритм агента для пассивного обучения с подкреплением, который позволяет определить с помощью обучения оценки полезностей на основе временнь/х разностей
function Passive-TD-Agent(percept) returns действие a
inputs: percept, результаты восприятия, обозначающие текущее
состояние s' и сигнал вознаграждения г' static: к, зафиксированная стратегия
U, таблица значений полезностей, первоначально пустая NSf таблица частот состояний, первоначально содержащая нули s, а, г, предыдущее состояние, действие и вознаграждение, первоначально пустые
if состояние s' является новым then U[sl] <— г' if состояние s не пусто then do увеличить значение iVs[s]
U[s] <- U[s] + a({Ns[s] }) (г + Y U[s' ] - U[s]) if Terminal? [s' ] then s, а, r <— пустые значения else s, a, r <— s', 7i[s'], r' return a
Подход на основе ADP и подход на основе TD фактически тесно связаны. В обоих этих алгоритмах предпринимаются попытки внести локальные корректировки в оценки полезностей, для того чтобы обеспечить "согласование" каждого состояния с его преемниками. Одно из различий между ними состоит в том, что в алгоритме TD состояние корректируется для согласования с его наблюдаемым преемником (уравнение 21.3), а в алгоритме ADP состояние корректируется для согласования со всеми преемниками, которые могут быть получены с учетом весов их вероятностей (уравнение 21.2). Это различие исчезает, когда результаты корректировок TD усредняются по большому количеству переходов, поскольку частота появления каждого преемника в множестве переходов приблизительно пропорциональна его вероятности. Более важное различие состоит в том, что в алгоритме TD выполняется отдельная корректировка в расчете на каждый наблюдаемый переход, а в алгоритме ADP выполняется столько корректировок, сколько требуется для восстановления согласованности между оценками полезностей и и моделью среды т. Хотя наблюдаемый переход вносит в т только локальное изменение, его результаты могут потребовать распространения по всем полезностям и. Таким образом, алгоритм TD может рассматриваться как грубое, но эффективное первое приближение алгоритма ADP.
Каждая корректировка, внесенная алгоритмом ADP, с точки зрения пользователя алгоритма TD может рассматриваться как результат "псевдоэксперимента", полученный путем моделирования в текущей модели среды. Подход, предусмотренный в алгоритме TD, можно дополнить в целях использования модели среды для выработки результатов нескольких псевдоэкспериментов, иначе говоря, переходов, возможность осуществления которых агент TD может допустить согласно его текущей модели. В ответ на каждый наблюдаемый переход агент TD может вырабатывать большое количество воображаемых переходов. Благодаря этому результирующие оценки полезностей TD будут все больше и больше аппроксимировать соответствующие оценки ADP, разумеется, за счет увеличения продолжительности времени вычислений.
Аналогичным образом могут создаваться все более эффективные версии алгоритма ADP путем непосредственной аппроксимации алгоритмов для итерации по значениям или итерации по стратегиям. Напомним, что полная итерация по значениям может быть трудновыполнимой, когда количество состояний велико. Однако многие этапы корректировки являются чрезвычайно малыми. Одним из возможных подходов, применимых для быстрой выработки достаточно качественных ответов, является ограничение количества корректировок, внесенных после каждого наблюдаемого перехода. Можно также использовать какую-то эвристику для ранжирования возможных корректировок, с тем чтобы в дальнейшем осуществлять только наиболее значимые из них. Эвристика, предусматривающая выметание с учетом приоритетов, позволяет предпочесть вариант с внесением корректировок в состояния, возможные преемники которых уже подвергались большим корректировкам в их собственных оценках полезностей. Приближенные алгоритмы ADP, в которых используются подобные эвристики, обычно обеспечивают обучение примерно с таким же быстродействием, как и полные алгоритмы ADP, с точки зрения количества обучающих последовательностей, но могут оказаться на несколько порядков величины более эффективными с точки зрения объема вычислений (см. упр. 21.3.) Это дает возможность применять такие алгоритмы для обработки пространств состояний, намного превышающих по размерам те, которые являются приемлемыми для полного алгоритма ADP. Приближенные алгоритмы ADP имеют еще одно дополнительное преимущество: на ранних этапах обучения в новой среде модель среды т часто далека от правильной, поэтому нет смысла слишком точно вычислять функцию полезности для согласования с ней. Приближенный алгоритм позволяет использовать минимальную величину корректировки, которая уменьшается по мере того, как модель среды становится все более точной. Это позволяет устранить очень продолжительные итерации по значениям, которые могут возникать на ранних этапах обучения из-за больших изменений в модели.







Материалы

Яндекс.Метрика