Сравнение методов временного различия(0) и постоянного α Монте-Карло на задаче случайного блуждания

Сравнение методов временного различия и постоянного α Монте-Карло на задаче случайного блуждания

Изображение, сгенерированное Midjourney с платной подпиской, соответствующей общим коммерческим условиям [1].

Введение

Методы Монте-Карло (MC) и Temporal-Difference (TD) являются фундаментальными техниками в области обучения с подкреплением; они решают проблему предсказания на основе опыта взаимодействия с окружающей средой, а не на основе модели окружающей среды. Однако метод TD является комбинацией методов MC и динамического программирования (DP), что отличается от метода MC в аспектах правила обновления, бутстрэпинга и смещения/дисперсии. В большинстве случаев методы TD показывают лучшую производительность и более быструю сходимость по сравнению с методом MC.

В этой статье мы сравним методы TD и MC, а именно методы TD(0) и постоянно-α MC, на простой сетке и более полной среде случайного блуждания [2]. Надеемся, что эта статья поможет читателям, интересующимся обучением с подкреплением, лучше понять, как каждый метод обновляет функцию значения состояния и как их производительность отличается в одной и той же тестовой среде.

Мы реализуем алгоритмы и сравнения на языке Python, а используемые библиотеки в этой статье следующие:

python==3.9.16numpy==1.24.3matplotlib==3.7.1

Разница между TD и MC

Введение в метод TD(0) и постоянно-α MC

Метод постоянно-α MC является обычным методом MC с постоянным параметром α, и этот постоянный параметр помогает сделать оценку значения более чувствительной к последнему опыту. На практике выбор значения α зависит от компромисса между стабильностью и адаптируемостью. Ниже приведено уравнение метода MC для обновления функции значения состояния в момент времени t:

TD(0) является особым случаем TD(λ), который рассматривает только один шаг вперед и является самой простой формой обучения TD. Этот метод обновляет функцию значения состояния с помощью ошибки TD, разницы между оцененным значением состояния и наградой плюс оцененным значением следующего состояния. Постоянный параметр α работает так же, как в методе MC выше. Ниже приведено уравнение метода TD(0) для обновления функции значения состояния в момент времени t:

В общем случае разница между методами MC и TD заключается в трех аспектах:

  1. Правило обновления: Методы MC обновляют значения только после окончания эпизода; это может быть проблематично, если эпизод очень длинный, что замедляет программу, или в случае непрерывной задачи, у которой вообще нет эпизодов. Напротив, метод TD обновляет оценки значений на каждом шаге времени; это онлайн-обучение и может быть особенно полезным в непрерывных задачах.
  2. Бутстрэпинг: Термин “бутстрэпинг” в обучении с подкреплением означает обновление оценок значений на основе других оценок значений. Метод TD(0) основывается на значении следующего состояния, поэтому он является методом бутстрэпинга; наоборот, MC не использует бутстрэпинг, так как обновляет значение непосредственно из возвратов (G).
  3. Смещение/дисперсия: Методы MC являются несмещенными, поскольку они оценивают значение, взвешивая наблюдаемые фактические возвраты, не делая оценок во время эпизода; однако методы MC имеют высокую дисперсию, особенно при низком количестве выборок. Напротив, методы TD имеют смещение, так как они используют бутстрэпинг, и смещение может меняться в зависимости от конкретной реализации; методы TD имеют низкую дисперсию, так как используют мгновенную награду плюс оценку следующего состояния, что сглаживает флуктуации, возникающие из случайности в наградах и действиях.

Оценка методов TD(0) и постоянно-α MC на простой сетке

Чтобы сделать их различия более ясными, мы можем создать простую тестовую среду Gridworld с двумя фиксированными траекториями, запустить оба алгоритма в этой среде до сходимости и проверить, как они обновляют значения по-разному.

Сначала мы можем настроить тестовую среду с помощью следующего кода:

Рисунок 1 Слева: настройка среды. Справа: предустановленные пути. Источник: рисунок автора

На левом рисунке выше показана простая настройка среды Gridworld. Все цветные ячейки представляют собой терминальные состояния; агент получает награду +1, когда попадает на красную ячейку, но получает награду -1, когда попадает на синие ячейки. Все остальные шаги на сетке возвращают награду ноль. На правом рисунке выше обозначены две предустановленные траектории: одна достигает синей ячейки, а другая останавливается на красной ячейке; пересечение траекторий помогает максимизировать разницу значений между двумя методами.

Затем мы можем использовать уравнения из предыдущего раздела для оценки среды. Мы не учитываем дисконтирование дохода или оценки и устанавливаем α на небольшое значение 1e-3. Когда абсолютная сумма приращений значения меньше порога 1e-3, мы считаем, что значения сходятся.

Результат оценки выглядит следующим образом:

Рисунок 2 Результаты оценки TD(0) и постоянного α MC. Источник: рисунок автора

Различия в способах оценки значений двух алгоритмов становятся довольно очевидными на изображении выше. Метод MC верен относительно возвратов пути, поэтому значения на каждом пути напрямую отображают его завершение. Тем не менее, метод TD дает лучшее предсказание, особенно на синем пути — значения на синем пути до пересечения также указывают на возможность попадания в красную ячейку.

Имея в виду этот минимальный случай, мы готовы перейти к намного более сложному примеру и попытаться выяснить разницу в производительности между двумя методами.

Задача случайного блуждания

Задача случайного блуждания — это простой марковский процесс вознаграждения, предложенный Саттоном и др. для целей прогнозирования TD и MC[2], как показано на изображениях ниже. В этой задаче агент начинает с центрального узла C. Агент делает шаг вправо или влево с равной вероятностью на каждом узле. На обоих концах цепи есть два терминальных состояния. Награда за попадание в левый конец равна 0, а за попадание в правый конец равна +1. Все шаги до завершения дают награду 0.

Рисунок 3 Случайное блуждание. Источник: рисунок автора

И мы можем использовать следующий код для создания среды случайного блуждания:

=====Тест: проверка настройки среды=====Связи:        None ← Узел A → Узел BВознаграждение:   0 ← Узел A → 0Связи:    Узел A ← Узел B → Узел CВознаграждение:   0 ← Узел B → 0Связи:    Узел B ← Узел C → Узел DВознаграждение:   0 ← Узел C → 0Связи:    Узел C ← Узел D → Узел EВознаграждение:   0 ← Узел D → 0Связи:    Узел D ← Узел E → NoneВознаграждение:   0 ← Узел E → 1

Истинное значение для каждого узла среды при случайной стратегии составляет [1/6, 2/6, 3/6, 4/6, 5/6]. Значение было рассчитано с помощью оценки стратегии с помощью уравнения Беллмана:

Наша задача здесь – найти, насколько близки значения, оцененные обоими алгоритмами, к истинному значению; мы можем произвольно предположить, что алгоритм производит более близкую функцию значения к истинной функции значения, измеренной усредненной среднеквадратичной ошибкой (RMS), что указывает на лучшую производительность.

Производительность TD(0) и постоянной а MC на случайном ходе

Алгоритмы

С готовой средой мы можем начать запускать оба метода на среде случайного хода и сравнивать их производительность. Сначала давайте рассмотрим оба алгоритма:

Источник: алгоритм написан на latex автором
Источник: алгоритм написан на latex автором

Как уже упоминалось ранее, метод MC должен ждать, пока эпизод закончится, чтобы обновить значения с хвоста траектории, в то время как метод TD обновляет значения постепенно. Это различие приводит к хитрости при инициализации функции значения состояния: в MC функция значения состояния не включает терминальные состояния, в то время как в TD(0) функция должна включать терминальное состояние со значением 0, потому что метод TD(0) всегда смотрит на один шаг вперед, прежде чем эпизод закончится.

Реализация

Выбор параметра α в этой реализации отсылает к предложенному в книге [2]; параметры для метода MC: [0.01, 0.02, 0.03, 0.04], а для метода TD: [0.05, 0.10, 0.15]. Мне было интересно, почему автор не выбрал одинаковый набор параметров для обоих алгоритмов, пока я не запустил метод MC с параметрами для TD: параметры TD слишком высоки для метода MC и поэтому не могут показать лучшую производительность MC. Поэтому мы будем придерживаться настройки из книги при переборе параметров. Теперь давайте запустим оба алгоритма, чтобы узнать их производительность на настройке случайного хода.

Результат

Рисунок 4 Результат сравнения алгоритмов. Источник: рисунок автора

Результат после 100 запусков сравнения показан на изображении выше. Метод TD в целом дает лучшие оценки значений, чем методы MC, и метод TD с α = 0.05 может очень близко подойти к истинному значению. График также показывает, что метод MC имеет большую дисперсию по сравнению с методами TD, поскольку орхидейные линии колеблются больше, чем стально-синие линии.

Стоит отметить, что для обоих алгоритмов, когда α (относительно) высокое, потеря RMS сначала уменьшается, а затем снова увеличивается. Такое явление связано с совместным эффектом инициализации значения и значения α. Мы инициализировали относительно высокое значение 0.5, что больше, чем истинное значение узлов A и B. Поскольку случайная стратегия дает 50% шанс выбрать «неправильный» шаг, который уводит агента от правильного терминального состояния, более высокое значение α также подчеркивает неправильные шаги и отдаляет результат от истинного значения.

Теперь попробуем уменьшить начальное значение до 0.1 и снова запустим сравнение, посмотрим, смогла ли проблема уменьшиться:

Рисунок 5 Результат сравнения алгоритмов с начальным значением 0.1. Источник: рисунок автора

Более низкое начальное значение, очевидно, помогает смягчить проблему; нет заметных эффектов «пойти вниз, а затем вверх». Однако, побочный эффект более низкого начального значения заключается в том, что обучение менее эффективно, поскольку потеря RMS никогда не опускается ниже 0.05 после 150 эпизодов. Таким образом, есть компромисс между начальным значением, параметром и производительностью алгоритма.

Пакетное обучение

Один последний момент, который я хочу упомянуть в этом посте, – это сравнение пакетного обучения на обоих алгоритмах.

Предположим, что мы сталкиваемся с такой ситуацией: мы накопили только ограниченное количество опыта на задаче случайного блуждания или мы можем запустить только определенное количество эпизодов из-за ограничений времени и вычислительных ресурсов. Идея пакетного обновления [2] была предложена для решения такой ситуации путем полного использования существующих траекторий.

Идея пакетного обучения заключается в обновлении значений на пакете траекторий до тех пор, пока значения не сойдутся к ответу. Значения будут обновляться только после полной обработки всех пакетных опытов. Давайте реализуем пакетное обучение для обоих алгоритмов на среде случайного блуждания, чтобы увидеть, продолжает ли метод TD показывать лучшие результаты, чем метод MC.

Результат

Рисунок 6 Результат пакетного обучения. Источник: рисунок автора

Результаты пакетного обучения показывают, что метод TD по-прежнему показывает лучшие результаты, чем метод MC при ограниченном опыте, и разница в производительности двух алгоритмов явно заметна.

Вывод

В этом посте мы обсудили разницу между методом постоянного α MC и методами TD(0) и сравнили их производительность на задаче случайного блуждания. Метод TD превосходит методы MC во всех тестах в этом посте, поэтому рассмотрение TD как метода для задач обучения с подкреплением является предпочтительным выбором. Однако это не означает, что TD всегда лучше MC, поскольку у последнего есть наиболее очевидное преимущество: отсутствие смещения. Если мы сталкиваемся с задачей, которая не терпит смещений, то MC может быть лучшим выбором; в противном случае TD лучше справляется с общими случаями.

Ссылки

[1] Условия использования Midjourney: https://docs.midjourney.com/docs/terms-of-service

[2] Саттон, Ричард С., и Эндрю Г. Барто. Reinforcement learning: An introduction. Издательство MIT, 2018.

Мой репозиторий на GitHub для этого поста: [Ссылка].