Подкрепляющее обучение предлагает эффективные подходы к решению задач последовательного принятия решений. Методы обучения с временными разностями (TD-обучение) представляют собой востребованный класс алгоритмов подкрепляющего обучения. Эти методы интегрируют основные элементы методов Монте-Карло и динамического программирования, что позволяет ускорять процесс обучения без необходимости в идеальной модели динамики среды.
В этой публикации мы разберем различные варианты TD-алгоритмов на примере специально созданного мира сетки. Эксперимент подчеркивает значимость непрерывного исследования, а также отличительные особенности анализируемых алгоритмов: Q-обучение, Dyna-Q и Dyna-Q+.
Структура материала включает:
- Описание среды
- Обучение с временными разностями (TD-обучение)
- Бесмодельные TD-методы (Q-обучение) и модельные TD-методы (Dyna-Q и Dyna-Q+)
- Параметры
- Сравнение производительности
- Заключение
Среда эксперимента
Для проведения эксперимента выбрана среда в виде мира сетки со следующими характеристиками:
- Сетка состоит из 12 строк и 8 столбцов клеток.
- Агент начинает движение из левого нижнего угла, а цель — добраться до сокровища в правом верхнем углу (конечное состояние с наградой 1).
- Синие порталы связаны между собой: проход через портал в клетке (10, 6) переносит в клетку (11, 0). Агент не может использовать портал повторно после первого перехода.
- Фиолетовый портал возникает после 100 эпизодов и позволяет агенту быстрее достичь цели. Это стимулирует постоянное исследование среды.
- Красные порталы — это ловушки (конечные состояния с наградой 0), которые завершают эпизод.
- Столкновение со стеной оставляет агента в текущем состоянии.
Описание различных элементов мира сетки
Цель эксперимента — сопоставить поведение агентов Q-обучения, Dyna-Q и Dyna-Q+ в изменяющейся среде. После 100 эпизодов оптимальная политика меняется, и минимальное количество шагов в успешном эпизоде снижается с 17 до 12.
Изображение мира сетки, оптимальные траектории зависят от текущего эпизода
Введение в обучение с временными разностями
Обучение с временными разностями объединяет методы Монте-Карло (MC) и динамическое программирование (DP):
- Подобно методам MC, TD-методы обучаются на основе опыта без необходимости в модели динамики среды.
- Подобно методам DP, TD-методы корректируют оценки после каждого шага на основе других полученных оценок, не дожидаясь финального результата (это называется бутстрапингом).
Особенностью TD-методов является обновление оценки ценности на каждом временном шаге, в отличие от методов MC, которые ожидают завершения эпизода.
Оба подхода используют различные цели обновления. Методы MC корректируют возврат Gt, доступный только в конце эпизода. TD-методы же ориентированы на:
Цель обновления в TD-методах
Здесь V — это оценка истинной функции ценности Vπ.
Таким образом, TD-методы сочетают выборку из MC (используя оценку истинной ценности) и бутстрапинг из DP (обновляя V на основе дальнейших оценок).
Простейшая форма обучения с временными разностями — это TD(0) или одношаговое TD, реализация которого выглядит следующим образом:
Псевдокод алгоритма TD(0)
При переходе из состояния S в новое состояние S’ алгоритм TD(0) вычисляет подкрепленную ценность и корректирует V(S). Эта подкрепленная ценность известна как TD-ошибка — разница между наблюдаемой наградой R плюс дисконтированной ценностью нового состояния γV(St+1) и текущей оценкой V(S):
TD-ошибка
В итоге, TD-методы обладают рядом преимуществ:
- Они не требуют идеальной модели динамики среды p
- Они работают в онлайн-режиме, обновляя оценки после каждого шага
- TD(0) гарантированно сходится для любой фиксированной политики π, если α (скорость обучения или размер шага) удовлетворяет условиям стохастического приближения
Детали реализации
Дальнейшие разделы рассматривают ключевые свойства и результаты нескольких TD-алгоритмов в мире сетки.
Для всех моделей применены одинаковые параметры в целях упрощения:
- Эпсилон (ε) = 0.1: вероятность выбора случайного действия в ε-жадных политиках
- Гамма (γ) = 0.9: фактор дисконтирования для будущих наград или оценок ценности
- Альфа (α) = 0.25: скорость обучения, ограничивающая обновления Q-ценностей
- Шаги планирования = 100: для Dyna-Q и Dyna-Q+ количество шагов планирования на каждое прямое взаимодействие
- Каппа (κ) = 0.001: для Dyna-Q+ вес бонусных наград при шагах планирования
Производительность каждого алгоритма сначала показана для одного прогона из 400 эпизодов (разделы: Q-обучение, Dyna-Q и Dyna-Q+), а затем усреднена по 100 прогонам из 250 эпизодов в разделе «обзор и сравнение алгоритмов».
Q-обучение
Первый реализованный алгоритм — известное Q-обучение (Watkins, 1989):
Q-обучение относится к офф-полити алгоритмам, поскольку стремится напрямую аппроксимировать оптимальную функцию ценности, а не функцию ценности политики π, которой следует агент.
На практике Q-обучение использует политику, называемую поведенческой политикой, для выбора посещаемых пар состояние-действие и их обновления. Однако оно офф-полити, потому что обновляет Q-ценности на основе лучшей оценки будущих наград, независимо от того, соответствуют ли выбранные действия текущей политике π.
По сравнению с предыдущим псевдокодом TD-обучения, здесь три ключевых отличия:
- Необходимо инициализировать Q-функцию для всех состояний и действий, при этом Q(конечное) = 0
- Действия выбираются по политике на основе Q-ценностей (например, ε-жадная политика относительно Q-ценностей)
- Обновление направлено на функцию ценности действия Q, а не на функцию ценности состояния V
Псевдокод алгоритма Q-обучения
Теперь, когда алгоритм готов к тестированию, начинается фаза обучения. Агент перемещается по миру сетки с помощью ε-жадной политики относительно Q-ценностей. Эта политика выбирает действие с наивысшей Q-ценностью с вероятностью (1 – ε) и случайное действие с вероятностью ε. После каждого действия агент корректирует оценки Q-ценностей.
Эволюцию оценок максимальной ценности действия Q(S, a) для каждой клетки мира сетки можно визуализировать с помощью тепловой карты. Агент проходит 400 эпизодов. Поскольку обновление происходит только один раз за эпизод, изменения Q-ценностей медленные, и значительная часть состояний остается неисследованной:
Тепловая карта оценок Q-ценностей для каждого состояния во время обучения
После 400 эпизодов анализ общего количества посещений каждой клетки дает хорошую оценку средней траектории агента. Как видно на правом графике ниже, агент сошелся к субоптимальной траектории, избегая клетки (4,4) и постоянно следуя вдоль нижней стены.
Оценка максимальной ценности действия для состояний (слева), количество посещений состояний (справа)
Из-за этой субоптимальной стратегии агент достигает минимума в 21 шаг за эпизод, следуя пути, показанному на графике посещений. Колебания в количестве шагов объясняются ε-жадной политикой, вводящей 10% вероятность случайных действий. Такая политика делает следование вдоль нижней стены разумным способом минимизировать влияние случайностей.
Количество шагов для последних 100 эпизодов (300–400)
В итоге, агент Q-обучения сошелся к субоптимальной стратегии, как отмечалось ранее. Кроме того, часть среды остается неисследованной Q-функцией, что не позволяет агенту обнаружить новый оптимальный путь после появления фиолетового портала на 100-м эпизоде.
Эти ограничения производительности связаны с относительно малым числом шагов обучения (400), что ограничивает взаимодействия со средой и исследование, провоцируемое ε-жадной политикой.
Планирование, ключевой элемент модельных методов подкрепляющего обучения, особенно полезно для повышения эффективности выборки и оценки ценностей действий. Dyna-Q и Dyna-Q+ — удачные примеры TD-алгоритмов с шагами планирования.
Dyna-Q
Алгоритм Dyna-Q (динамическое Q-обучение) сочетает модельное подкрепляющее обучение и TD-обучение.
Модельные алгоритмы RL опираются на модель среды для планирования как основного механизма обновления оценок ценности. В отличие от них, бесмодельные алгоритмы полагаются на прямое обучение.
«Модель среды — это все, что агент может использовать для предсказания реакции среды на свои действия» — Подкрепляющее обучение: введение.
В контексте этой статьи модель можно рассматривать как аппроксимацию динамики переходов p(s’, r|s, a). Здесь p возвращает единственную пару следующего состояния и награды для текущей пары состояние-действие.
В стохастических средах различают распределительные модели и выборочные модели: первые дают распределение следующих состояний и наград, вторые — одну пару, выбранную из оцененного распределения.
Модели полезны для симуляции эпизодов, позволяя обучать агента, заменяя реальные взаимодействия шагами планирования, то есть взаимодействиями с симулированной средой.
Агенты с Dyna-Q относятся к классу агентов с планированием, которые комбинируют прямое подкрепляющее обучение и обучение модели. Они обновляют функцию ценности через прямые взаимодействия (как в Q-обучении) и учат модель среды. После каждого прямого взаимодействия выполняются шаги планирования для обновления функции ценности с помощью симулированных взаимодействий.
Простой пример с шахматами
Представьте хорошую партию в шахматы. После каждого хода реакция оппонента позволяет оценить качество хода. Это похоже на получение положительной или отрицательной награды, которая помогает «обновить» стратегию. Если ход приводит к ошибке, вы, вероятно, не повторите его в похожей позиции доски. Пока это аналогично прямому подкрепляющему обучению.
Теперь добавим планирование. Пока оппонент думает, вы мысленно возвращаетесь к каждому предыдущему ходу, чтобы переоценить его качество. Вы можете заметить упущенные слабости или понять, что некоторые ходы лучше, чем казалось. Эти размышления позволяют обновить стратегию. Именно это и есть планирование: обновление функции ценности без взаимодействия с реальной средой, а с ее моделью.
Планирование, действия, обучение модели и прямое RL: цикл агента с планированием
Dyna-Q включает дополнительные шаги по сравнению с Q-обучением:
После каждого прямого обновления Q-ценностей модель сохраняет пару состояние-действие, наблюдаемую награду и следующее состояние. Это называется обучением модели.
- После обучения модели Dyna-Q выполняет n шагов планирования:
- Случайная пара состояние-действие выбирается из буфера модели (эта пара была наблюдаема в прямых взаимодействиях)
- Модель генерирует симулированную награду и следующее состояние
- Функция ценности обновляется с использованием симулированных наблюдений (s, a, r, s’)
Псевдокод алгоритма Dyna-Q
Теперь воспроизведем процесс обучения с Dyna-Q, используя n=100. Это означает, что после каждого прямого взаимодействия с средой модель выполняет 100 шагов планирования (обновлений).
Следующая тепловая карта демонстрирует быструю сходимость модели Dyna-Q. Фактически, алгоритму требуется около 10 эпизодов, чтобы найти оптимальный путь. Это происходит потому, что каждый шаг приводит к 101 обновлению Q-ценностей (вместо 1 в Q-обучении).
Тепловая карта оценок Q-ценностей состояний во время обучения
Еще одно преимущество шагов планирования — лучшая оценка ценностей действий по всей сетке. Поскольку косвенные обновления касаются случайных переходов из модели, обновляются даже состояния, далекие от цели.
В Q-обучении ценности действий медленно распространяются от цели, что приводит к неполному картированию сетки.
Оценка максимальной ценности действия (слева), количество посещений (справа)
С Dyna-Q находится оптимальный путь, решающий задачу мира сетки за 17 шагов, как показано красными полосами на графике ниже. Оптимальные результаты достигаются регулярно, несмотря на периодическое вмешательство ε-жадных действий для исследования.
Наконец, хотя Dyna-Q кажется убедительнее Q-обучения благодаря планированию, важно помнить о компромиссе между вычислительными затратами и исследованием реального мира.
Количество шагов для последних 100 эпизодов (300–400)
Dyna-Q+
До сих пор ни один из протестированных алгоритмов не смог найти оптимальный путь, появляющийся после 100-го шага (фиолетовый портал). Оба алгоритма быстро сошлись к оптимальному решению, которое оставалось неизменным до конца обучения. Это подчеркивает необходимость непрерывного исследования на протяжении всего процесса.
Dyna-Q+ во многом похож на Dyna-Q, но включает небольшое изменение. Алгоритм постоянно отслеживает количество временных шагов, прошедших с момента последнего реального взаимодействия с каждой парой состояние-действие.
В частности, для перехода с наградой r, не пробованного в течение τ шагов, Dyna-Q+ планирует, как будто награда равна r + κ √τ, где κ достаточно мало (0.001 в эксперименте).
Это изменение в дизайне наград побуждает агента к постоянному исследованию среды. Оно предполагает, что чем дольше пара состояние-действие не пробовалась, тем выше вероятность изменения ее динамики или ошибки в модели.
Псевдокод алгоритма Dyna-Q+
Как видно на следующей тепловой карте, Dyna-Q+ гораздо активнее в обновлениях по сравнению с предыдущими алгоритмами. До 100-го эпизода агент исследует всю сетку, находит синий портал и первый оптимальный маршрут.
Ценности действий для остальной части сетки снижаются, прежде чем медленно расти снова, поскольку пары состояние-действие в левом верхнем углу некоторое время не исследуются.
Как только фиолетовый портал появляется на 100-м эпизоде, агент обнаруживает новую короткую дорогу, и ценности для всей области повышаются. До завершения 400 эпизодов агент непрерывно обновляет ценности действий для каждой пары, сохраняя периодическое исследование сетки.
Тепловая карта оценок Q-ценностей состояний во время обучения
Благодаря бонусу к наградам модели мы наконец получаем полное картирование Q-функции (каждое состояние или клетка имеет ценность действия).
В сочетании с непрерывным исследованием агент находит новый лучший маршрут (то есть оптимальную политику) по мере его появления, сохраняя предыдущее решение.
Оценка максимальной ценности действия (слева), количество посещений (справа)
Однако компромисс между исследованием и эксплуатацией в Dyna-Q+ имеет цену. Когда пары состояние-действие долго не посещаются, бонус исследования побуждает агента вернуться к ним, что может временно снижать немедленную производительность. Такое поведение исследования приоритизирует обновление модели для улучшения долгосрочных решений.
Это объясняет, почему некоторые эпизоды в Dyna-Q+ достигают до 70 шагов, в то время как в Q-обучении и Dyna-Q максимум 35 и 25 шагов соответственно. Более длинные эпизоды в Dyna-Q+ отражают готовность агента тратить дополнительные шаги на исследование для сбора информации о среде и уточнения модели, даже если это приводит к краткосрочному снижению производительности.
В отличие от этого, Dyna-Q+ регулярно достигает оптимальной производительности (показанной зелеными полосами на графике ниже), чего не добиваются предыдущие алгоритмы.
Количество шагов для последних 100 эпизодов (300–400)
Обзор и сравнение алгоритмов
Для выявления ключевых различий между алгоритмами используются две метрики (результаты зависят от входных параметров, которые были одинаковы для всех моделей в целях простоты):
- Количество шагов за эпизод: эта метрика характеризует скорость сходимости алгоритмов к оптимальному решению. Она также описывает поведение после сходимости, особенно в плане исследования.
- Средняя кумулятивная награда: процент эпизодов, приводящих к положительной награде
Анализ количества шагов за эпизод (см. график ниже) раскрывает несколько аспектов модельных и бесмодельных методов:
- Эффективность модельных методов: Модельные алгоритмы (Dyna-Q и Dyna-Q+) более эффективны по выборке в этом мире сетки (это свойство наблюдается в RL в целом). Они планируют заранее с помощью изученной модели среды, что приводит к более быстрой сходимости к почти оптимальным или оптимальным решениям.
- Сходимость Q-обучения: Q-обучение, хотя и сходится в итоге к почти оптимальному решению, требует больше эпизодов (125). Важно отметить, что Q-обучение выполняет только 1 обновление за шаг, в отличие от множественных обновлений в Dyna-Q и Dyna-Q+.
- Множественные обновления: Dyna-Q и Dyna-Q+ выполняют 101 обновление за шаг, что ускоряет сходимость. Однако цена за эту эффективность выборки — вычислительные затраты (см. раздел времени выполнения в таблице ниже).
- Сложные среды: В более сложных или стохастических средах преимущество модельных методов может уменьшиться. Модели могут вносить ошибки или неточности, приводя к субоптимальным политикам. Поэтому это сравнение следует воспринимать как обзор сильных и слабых сторон подходов, а не прямое сопоставление производительности.
Сравнение количества шагов за эпизод, усредненное по 100 прогонам
Теперь рассмотрим среднюю кумулятивную награду (ACR), которая отражает процент эпизодов, в которых агент достигает цели (поскольку награда 1 за цель и 0 за ловушку), ACR вычисляется как:
Формула ACR
Где N — число эпизодов (250), K — число независимых прогонов (100), а Rn,k — кумулятивная награда за эпизод n в прогоне k.
Вот разбор производительности всех алгоритмов:
- Dyna-Q быстро сходится и достигает наивысшей общей отдачи с ACR 87%. Это означает эффективное обучение и достижение цели в значительной доле эпизодов.
- Q-обучение также достигает похожего уровня производительности, но требует больше эпизодов для сходимости, что объясняет немного более низкий ACR в 70%.
- Dyna-Q+ быстро находит хорошую политику, достигая кумулятивной награды 0.8 уже после 15 эпизодов. Однако вариабельность и исследование, вызванное бонусной наградой, снижают производительность до 100-го шага. После 100 шагов улучшение начинается с обнаружением нового оптимального пути. Тем не менее, краткосрочное исследование ухудшает производительность, приводя к ACR 79%, что ниже, чем у Dyna-Q, но выше, чем у Q-обучения.
Сравнение кумулятивной награды за эпизод, усредненное по 100 прогонам
Заключение
В этой статье мы изложили базовые принципы обучения с временными разностями и применили Q-обучение, Dyna-Q и Dyna-Q+ к специально созданному миру сетки. Дизайн этого мира сетки помогает подчеркнуть важность непрерывного исследования как способа обнаружения и использования новых оптимальных политик в изменяющихся средах. Различия в производительности (оцененные по количеству шагов за эпизод и кумулятивной награде) иллюстрируют сильные и слабые стороны этих алгоритмов.
В обзоре модельные методы (Dyna-Q, Dyna-Q+) выигрывают в эффективности выборки по сравнению с бесмодельными (Q-обучение), но проигрывают в вычислительной эффективности. Однако в стохастических или более сложных средах неточности модели могут мешать производительности и приводить к субоптимальным политикам.
