26.02.2024

Q-Обучение

26.02.2024

607

Введение
Обучение с подкреплением
Два метода на основе ценности (value-based methods)
Функция ценности состояния (value function)
Функция ценности действия (action value function)
Уравнение Беллмана
Методы вычисления функций ценности
Метод Монте-Карло
Обучение на временных разностях
Q-обучение
Что такое Q-обучение?
Q-Learning алгоритм
Домашнее задание
Дополнительные ресурсы

Введение

В этой статье мы подробно рассмотрим один из методов обучения с подкреплением — метод, в основе которого лежит функция ценности. А еще познакомимся с нашим первым алгоритмом Q-обучения.

Для лучшего понимания статьи рекомендуем посмотреть нашу предыдущую публикацию на тему обучения с подкреплением по этой ссылке.

Обучение с подкреплением

Давайте вспомним, что такое обучение с подкреплением. Наша задача здесь — создать агента, который способен принимать умные решения. Это может быть, например, агент для игры в видеоигры или агент для торговли на бирже. Второй должен учиться максимизировать выгоды и выбирать, когда и какие акции стоит купить или продать.

Рисунок 1. Парадигма обучения с подкреплением. Агент получает состояние среды и вознаграждение. На их основе он предпринимает действие, которое, в свою очередь, меняет состояние среды

Наш агент будет учиться принимать решения, взаимодействуя с окружающей средой методом проб и ошибок и получая награды в качестве обратной связи. Его цель — максимизация ожидаемой совокупной награды. Процесс, по которому агент принимает решения, называется политикой \( \pi \), которая возвращает действие \( a_t \), исходя из текущего состояния среды \( s_t \).

Два метода на основе ценности (value-based methods)

В подходах на основе ценности мы обучаем функцию ценности \( v_\pi \), которая определяет ожидаемое вознаграждение определенного состояния \( s \):

\( v_\pi(s) = \mathbb{E}_\pi\big[R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots\ |\ S_t = s\big] \).

Ценность состояния — это ожидаемое дисконтированное вознаграждение \( R \), которое может получить агент, если начнет действовать из состояния \( S_t=s \) и будет следовать установленной стратегии \( \pi \).

Но что значит действовать в соответствии с установленной стратегией? В конце концов, в методах, основанных на значении, у нас нет стратегии, поскольку мы обучаем функцию ценности, а не стратегию.

Вспомним следующее: цель агента обучения с подкреплением — найти оптимальную стратегию \( π^* \). Для этого есть два ключевых типа методов:

Методы, основанные на стратегии: напрямую обучаем стратегию выбирать, какое действие предпринять в данном состоянии (или распределение вероятностей действий в этом состоянии). В этом случае у нас нет функции ценности.
Методы, основанные на ценности: косвенно обучаем стратегию через обучение функции ценности, которая выдает ценность состояния или пары “состояние-действие”. Исходя из этой функции ценности, наша стратегия будет предпринимать действие.

Поскольку в методах, основанных на ценности, стратегия не тренируется, нам нужно определить ее. Например, если мы хотим стратегию, которая, исходя из функции ценности, всегда будет выбирать действия, приводящие к наибольшему вознаграждению, мы получим жадную стратегию.

Следовательно, независимо от метода, который мы будем использовать для решения нашей проблемы, у нас будет стратегия. В случае методов, основанных на ценности, стратегия не обучается: ваша стратегия — это просто заранее определенная функция (например, жадная стратегия). Она использует ценности, предоставленные функцией ценности для выбора своих действий.

Функция ценности состояния (value function)

Функция ценности состояния при стратегии \( π \) записывается так:

\( \begin{align} V_\pi(s) = \mathbb{E}_\pi\big[ G_t \ |\ S_t=s]. \end{align} \)

Для каждого состояния эта функция возвращает ожидаемое вознаграждение \( G_t = R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots \), если агент начинает с этого состояния и затем следует стратегии бесконечно долго или до конца эпизода.

Функция ценности действия (action value function)

Функция ценности действия для каждой пары “состояние-действие” возвращает ожидаемое вознаграждение, если агент начинает в данном состоянии, совершает данное действие и затем бесконечно долго следует стратегии. Ценность совершения действия \( a \) в состоянии \( s \) при стратегии \( π \) определяется как:

\( \begin{align} Q_\pi(s,a) = \mathbb E_\pi\big[ G_t\ |\ S_t=s, A_t=a] . \end{align} \)

Отличие между \( V_\pi(s) \) и \( Q_\pi(s,a) \) заключается в следующем:

для функции ценности состояния мы вычисляем ценность конкретного состояния \( S_t \);
для функции ценности действия мы вычисляем ценность пары “состояние-действие” (\( S_t, A_t \)), то есть значение совершения данного действия в данном состоянии.

В любом случае независимо от выбранной функции ценности (ценности состояния или ценности действия) возвращаемая ценность является ожидаемым суммарным вознаграждением. Однако проблема заключается в том, что для вычисления \( V_\pi(s) \) или \( Q_\pi(s,a) \) необходимо суммировать все награды, которые агент может получить, начиная с этого состояния. Это может быть вычислительно затратным процессом, и именно здесь на помощь приходит уравнение Беллмана.

Уравнение Беллмана

Уравнение Беллмана позволяет упростить вычисление нашей функции ценности состояния или ценности пары “состояние-действие”. В качестве иллюстрации рассмотрим табличную задачу на Рис. 2, где агенту необходимо найти алмаз (выполнить задачу) как можно скорее. Для этого он получает вознаграждение \( R_t = -1 \) в любом состоянии, кроме конечного, где находится алмаз.

Рисунок 2. Пример табличной задачи с частично заполненными значениями ценности состояний

Опираясь на наши знания до этого момента, мы отмечаем следующее: для вычисления \( V(S_t) \) (ценности состояния) нам нужно вычислить суммарное вознаграждение, начиная из этого состояния, и затем всегда следовать стратегии. В приведенном примере мы определили стратегию как жадную. Для упрощения мы не дисконтировали вознаграждение. Следовательно, для состояния \( S_t \) ценность будет вычисляться, как на Рис. 3.

Рисунок 3. Вычисление функции ценности состояния для состояния \( S_t \)

Рисунок 4. Вычисление функции ценности состояния для состояния \( S_{t+1} \)

Затем для вычисления \( V(S_{t+1}) \) нам необходимо сложить вознаграждения, начиная из состояния \( S_{t+1} \), как это показано на Рис. 4.

Вы могли заметить, как мы повторяем вычисление ценности различных состояний, что может быть утомительным, если нужно сделать это для каждого состояния или пары “состояние-действие”. Чтобы не вычислять ожидаемое вознаграждение для каждого состояния или каждой пары “состояние-действие”, мы можем использовать уравнение Беллмана (привет, динамическое программирование).

Уравнение Беллмана — это рекурсивное уравнение. Оно работает следующим образом: вместо того, чтобы вычислять ценность каждого состояния как суммарное вознаграждение, мы можем рассматривать ценность любого состояния как непосредственную награду \( R_{t+1} \) + дисконтированную ценность последующего состояния, \( \gamma\cdot V_\pi(S_{t+1}) \) (см. на Рис. 5).

\( \begin{align} V_\pi(s)=\mathbb E_\pi\big[R_{t+1} + \gamma\cdot V_\pi(S_{t+1})\ |\ S_t =s \big] \end{align} \)

Рисунок 5. Визуализация уравнения Беллмана для нашей задачи поиска алмаза

Резюмируем: суть уравнения Беллмана — вместо длительного вычисления каждой ценности как суммы ожидаемого вознаграждения мы вычисляем ценность как сумму непосредственного вознаграждения плюс дисконтированную ценность последующего состояния.

Методы вычисления функций ценности

Вспомним, что агент в обучении с подкреплением учится при взаимодействии со средой. Идея здесь следующая: на основе полученного опыта и награды агент будет обновлять свою функцию ценности или стратегию. Метод Монте-Карло и обучение на временных разностях — это два разных подхода тренировки нашей функции ценности или стратегии. Оба метода используют опыт для решения задачи обучения с подкреплением.

С одной стороны, метод Монте-Карло применяет целый эпизод опыта перед обучением. С другой — обучение на временных разностях использует только один шаг (\( S_t \), \( A_t \),\( R_{t+1} \), \( S_{t+1} \)) для обучения. Мы подробнее рассмотрим эти два подхода на примере из Рис. 6, где агенту необходимо собрать как можно больше алмазов. За каждый алмаз он получает вознаграждение \( R_t=1 \), в противном случае принимает \( R_t=0 \).

Рисунок 6. Пример задачи обучения с подкреплением, где агенту надо собрать как можно больше алмазов

Метод Монте-Карло

Этот метод ждет конца эпизода, вычисляет \( G_t \) (суммарное вознаграждение) и использует его в качестве цели для обновления \( V(S_t) \). Таким образом, он требует полного эпизода взаимодействия перед обновлением нашей функции ценности.

Рисунок 7. Один эпизод для обновления функции ценности

Рисунок 8. Один шаг для обновления функции
ценности при обучении на временных разностях

Алгоритм метода Монте-Карло можно описать так:

Мы всегда начинаем эпизод с одного и того же начального состояния.
Агент совершает действия, используя стратегию. Например, используя \( \epsilon \)-жадную стратегию, которая чередует исследование (случайные действия) и эксплуатацию.
Мы получаем награду и следующее состояние.
Эпизод завершается, если робот сгорает или совершает > 10 шагов.
В конце эпизода у нас есть список кортежей [Состояние, Действие, Вознаграждение и Следующее Состояние].
Агент будет суммировать вознаграждения, чтобы получить \( G_t \) (то есть оценить, насколько хорошо он справился).
Затем он обновит \( V(S_t) \) на основе формулы:

\( \begin{align} V(S_t) \leftarrow V(S_t) + \alpha \big [G_t — V(S_t)\big], \end{align} \)

где \( \alpha \) — размер шага обучения.

После мы начинаем новую игру с этими новыми знаниями.

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

Обучение на временных разностях

Метод обучения на временных разностях (Temporal Difference Learning, TD) ждет только одного взаимодействия со средой (одного шага) \( S_{t+1} \), чтобы сформировать TD цель и обновить \( V(S_t) \), используя непосредственное вознаграждение \( R_{t+1} \) и дисконтированную ценность следующего состояния, \( γ⋅V(S_{t+1}) \). Идея метода TD заключается в обновлении \( V(S_t) \) на каждом шаге.

Но поскольку мы не завершили весь эпизод, у нас нет \( G_t \). Вместо этого мы оцениваем \( G_t \), добавляя \( R_{t+1} \) и дисконтированную ценность следующего состояния:

\( \begin{align} V(S_t) \leftarrow V(S_t) + \alpha \big [\underbrace{R_{t+1} + \gamma V(S_{t+1})}_{\mathrm{TD\ target}} — V(S_t)\big] \end{align} \)

Это называется бутстрэппингом. Название связано с тем, TD базирует свое обновление частично на существующей оценке \( V(S_{t+1}) \) и не на полной выборке \( G_t \).

Подведем итоги:

В Методе Монте-Карло мы обновляем функцию ценности на основе полного эпизода, поэтому используем фактический точный дисконтированный возврат этого эпизода.
в TD Обучении мы обновляем функцию ценности на каждом шаге и заменяем неизвестный нам \( G_t \) на оценочный возврат, называемый целью TD.

Q-обучение

Что такое Q-обучение?

Q-обучение — это алгоритм, используемый для тренировки нашей Q-функции, функции ценности действия, которая определяет ценность нахождения в определенном состоянии и совершения конкретного действия в этом состоянии (см. Рис. 9).

Рисунок 9. Для данного состояния и действия Q-функция возвращает ценность пары “состояние-действие” (Q-value)

Изнутри наша Q-функция представлена Q-таблицей — таблицей, где каждая ячейка соответствует значению пары “состояние-действие”. Эту Q-таблицу можно представлять как память или шпаргалку нашей Q-функции. Давайте рассмотрим пример с лабиринтом на Рис. 10.

Рисунок 10. Простой пример для визуализации Q-обучения

Q-таблица содержит для каждого состояния и действия соответствующую ценность пар “состояние-действие”. В этом простом примере состояние определяется только позицией мыши. Следовательно, в нашей Q-таблице 2*3 строки, по одной строке для каждой возможной позиции мыши. В более сложных сценариях состояние может содержать больше информации, чем позиция действующего лица.

Рисунок 11. Q-таблица для нашего простого примера

Сначала наша Q-таблица бесполезна, поскольку она дает произвольные значения для каждой пары “состояние-действие” (чаще всего мы инициализируем Q-таблицу нулями). По мере того, как агент исследует среду, а мы обновляем Q-таблицу по формуле (5), она будет давать нам постепенно наилучшее приближение к оптимальной стратегии.

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

Q-Learning алгоритм

Псевдокод Q-обучения выглядит следующим образом:

Давайте пройдемся по основным шагам алгоритма.

Инициализируем Q-таблицу для каждой пары “состояние-действие”. В большинстве случаев мы инициализируем значениями 0.
Выбираем действие при помощи \( \epsilon \)-жадного алгоритма, который позволяет найти компромисс между исследованием и эксплуатацией. Он с вероятностью \( \epsilon \) исследует среду и с вероятностью \( 1-\epsilon \) эксплуатирует (использует текущее знание для принятия решения, которое приведет к наибольшему вознаграждению). Обычно в начале обучения мы используем большое значение \( \epsilon \), а по мере обучения уменьшаем ее.
Выполняем действие \( A_t \), получаем награду \( R_{t+1} \) и следующее состояние \( S_{t+1} \).
Обновляем Q-таблицу, используя обучение на временных разностях:

\( Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha \big [\underbrace{R_{t+1} + \gamma\cdot \underset{a}{\max}\ Q(S_{t+1}, a)}_{\mathrm{TD\ target}} — Q(S_t, A_t)\big] \)

Обратите внимание: для TD target мы используем жадную стратегию, а при выборе действия на втором шаге — \( \epsilon \)-жадную стратегию. Поэтому говорят, что Q-обучение является off-policy алгоритмом. К концу обучения алгоритм сходится к оптимальной Q-таблице: значения в ней перестают меняться. Используя эту таблицу и жадный алгоритм, наш агент сможет максимизировать суммарное вознаграждение для данной среды.

Домашнее задание

Итак, мы рассмотрели наш первый алгоритм обучения с подкреплением на основе ценности — Q-обучение.

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

Для более глубокого Q-обучения я советую вам реализовать этот алгоритм и решить Frozen Lake среду 🙂