Deep RL Course, юнит 2: Q-learning

Это перевод теоретической части юнита 2 курса Hugging Face Deep RL Course. Практика — Q-learning с нуля на FrozenLake и Taxi — переведена на странице «Юнит 2, практика». Карта курса — в путеводителе.

Как читать вместе с курсом ChinaAI

Первая половина юнита (функции ценности, уравнение Беллмана) идёт параллельно уроку 6.0.1, вторая (Монте-Карло, TD, Q-learning, on-policy и off-policy) — уроку 6.0.2. Удобный порядок: урок 6.0.1 → разделы юнита до «Промежуточного теста» → урок 6.0.2 → остальная часть юнита и практика. В уроках ChinaAI те же понятия даны строже (уравнение Беллмана с вероятностями переходов, value iteration), здесь — нагляднее, на примере мышки и сыра.

О переводе

Перевод сделан по исходникам курса на GitHub (лицензия Apache-2.0). Формулы, которые в оригинале нарисованы на картинках, записаны формулами; рисунки описаны словами; тесты оформлены интерактивными квизами. Примечания переводчика вынесены в отдельные блоки. В курсе Hugging Face награда за действие $A_t$ обозначена $R_{t+1}$, в уроках ChinaAI — $r_t$: сдвинут только индекс.

Введение

В первом юните мы узнали, что такое обучение с подкреплением (RL), как устроен процесс RL и какие есть методы решения задач RL. Мы также обучили первых агентов и загрузили их на Hugging Face Hub.

В этом юните мы глубже разберём одну из групп методов RL — методы на основе ценности — и изучим первый алгоритм RL: Q-learningQ-learningEN Q-learningQ(s,a) ← Q(s,a) + α[r + γ max_a′ Q(s′,a′) − Q(s,a)]. Off-policy: учит Q* при любом поведении..

Мы также напишем первого агента RL с нуля — агента Q-learning — и обучим его в двух средах:

1. FrozenLake-v1 (нескользкая версия): агент должен дойти от старта (S) до цели (G), ступая только по льду (F) и обходя полыньи (H).
2. Автономное такси: агент должен научиться ездить по городу и возить пассажиров из точки A в точку B.

Конкретно мы:

• узнаем о методах на основе ценности;
• узнаем, чем отличаются Монте-Карло и обучение на временных разностях (TD);
• изучим и реализуем первый алгоритм RL: Q-learning.

Этот юнит обязателен, если вы хотите разобраться в Deep Q-learning — первом алгоритме Deep RL, который играл в игры Atari и на некоторых из них (Breakout, Space Invaders и других) превзошёл уровень человека.

Итак, начнём!

Что такое RL? Короткое повторение

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

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

Его цель — максимизировать ожидаемую накопленную награду (согласно гипотезе о награде).

Процесс принятия решений агента называется политикой $\pi$: по состоянию политика выдаёт действие или распределение вероятностей по действиям. То есть, получив наблюдение среды, политика говорит, какое действие выбрать агенту (или даёт вероятность каждого действия).

Наша цель — найти оптимальную политику $\pi^*$, то есть политику, которая даёт наибольшую ожидаемую накопленную награду.

Чтобы найти оптимальную политику (и тем самым решить задачу RL), есть два главных типа методов RL:

• Методы на основе политики: политику обучают напрямую, чтобы она знала, какое действие выбирать в данном состоянии.
• Методы на основе ценности: обучают функцию ценности, чтобы знать, какое состояние ценнее, и с её помощью выбирают действие, ведущее туда.

В этом юните мы углубимся в методы на основе ценности.

Два типа методов на основе ценности

В методах на основе ценности мы учим функцию ценности, которая сопоставляет состоянию ожидаемую ценность пребывания в нём.

Ценность состояния — это ожидаемая дисконтированная отдача, которую агент получит, если начнёт в этом состоянии и дальше будет действовать по нашей политике.

Заметка

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

Помните: цель агента RL — оптимальная политика $\pi^*$.

Чтобы найти её, мы изучили два разных подхода:

• Методы на основе политики: политику обучают напрямую выбирать действие в данном состоянии (или распределение вероятностей по действиям в нём). В этом случае функции ценности нет.

  Политика принимает состояние и выдаёт действие (детерминированная политика выдаёт одно действие; стохастическая, наоборот, — распределение вероятностей по действиям). Поэтому мы не задаём поведение политики вручную: его определяет обучение.

• Методы на основе ценности: косвенно, через обучение функции ценности, которая выдаёт ценность состояния или пары «состояние — действие». По этой функции ценности политика выбирает действие.

  Раз политику не обучают, её поведение нужно задать самим. Например, если мы хотим, чтобы политика по функции ценности всегда выбирала действия, ведущие к наибольшей награде, мы создаём жадную политику (greedy policy). В оригинале это показано схемой: по состоянию обучаемая функция ценности действий выдаёт ценность каждого действия, а заранее заданная жадная политика выбирает действие с наибольшей ценностью.

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

Разница в том, что:

• при обучении на основе политики оптимальную политику ($\pi^*$) находят, обучая саму политику;
• при обучении на основе ценности оптимальная функция ценности (обозначается $Q^*$ или $V^*$, разницу разберём ниже) даёт оптимальную политику.

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

$$\pi^*(s) = \arg\max_a Q^*(s, a)$$

На практике в методах на основе ценности чаще всего используют ε-жадную политику (epsilon-greedy), которая справляется с компромиссом между исследованием и использованием; о ней поговорим во второй части юнита, когда дойдём до Q-learning.

Как сказано выше, функции ценности бывают двух типов.

Функция ценности состояния

Функцию ценности состоянияфункция ценности состояния (V)EN state-value functionV^π(s) — средняя отдача, если стартовать из s и дальше действовать по политике π. при политике $\pi$ записывают так (в оригинале — на картинке):

$$V_\pi(s) = \mathbb{E}_\pi\left[G_t \mid S_t = s\right]$$

Для каждого состояния она выдаёт ожидаемую отдачу, если агент начнёт в этом состоянии и дальше всегда (на всех будущих шагах) будет следовать политике.

В оригинале нарисован лабиринт с ценностями клеток. Возьмём клетку с ценностью −7: это ожидаемая отдача, если начать в ней и действовать по нашей политике (жадной): вправо, вправо, вправо, вниз, вниз, вправо, вправо.

Функция ценности действия

Функция ценности действияфункция ценности действия (Q)EN action-value function (Q-function)Q^π(s, a) — средняя отдача, если в s выбрать действие a, а дальше действовать по π. для каждой пары «состояние — действие» выдаёт ожидаемую отдачу, если агент начнёт в этом состоянии, выполнит это действие и дальше всегда будет следовать политике.

Ценность выбора действия $a$ в состоянии $s$ при политике $\pi$:

$$Q_\pi(s, a) = \mathbb{E}_\pi\left[G_t \mid S_t = s, A_t = a\right]$$

Разница такая:

• функция ценности состояния считает ценность состояния $S_t$;
• функция ценности действия считает ценность пары «состояние — действие» ($S_t, A_t$), то есть ценность выбора этого действия в этом состоянии.

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

В обоих случаях, какую бы функцию ценности мы ни выбрали, возвращаемое значение — ожидаемая отдача.

Беда в том, что чтобы посчитать КАЖДУЮ ценность состояния или пары «состояние — действие», нужно сложить все награды, которые агент может получить, начав в этом состоянии.

Это может быть дорого, и здесь на помощь приходит уравнение Беллмана.

Уравнение Беллмана: упрощаем оценку ценности

Уравнение Беллманауравнение БеллманаEN Bellman equationЦенность состояния = средняя немедленная награда + γ · средняя ценность следующего состояния. упрощает вычисление ценности состояния или пары «состояние — действие».

Из того, что мы уже знаем: чтобы посчитать $V(S_t)$ (ценность состояния), нужно посчитать отдачу, начиная с этого состояния, а дальше всё время следовать политике. (В примере ниже политика жадная, и для простоты мы не дисконтируем награду.)

Значит, чтобы посчитать $V(S_t)$, нужно сложить ожидаемые награды. В оригинале это показано на лабиринте: ценность состояния 1 — это сумма наград, если агент начнёт в нём и дальше всё время будет следовать жадной политике (выбирать действия, ведущие в состояния с лучшей ценностью).

Затем, чтобы посчитать $V(S_{t+1})$, нужно посчитать отдачу, начиная с состояния $S_{t+1}$: сумму наград, если агент начнёт в этом состоянии и дальше будет всё время следовать политике.

Вы, наверное, заметили, что мы повторяем вычисления ценности разных состояний. Это утомительно, если делать так для каждой ценности состояния или пары «состояние — действие».

Вместо того чтобы считать ожидаемую отдачу для каждого состояния или каждой пары заново, можно воспользоваться уравнением Беллмана. (Подсказка: если вы знаете, что такое динамическое программированиединамическое программированиеEN dynamic programmingРешение задачи через ответы на подзадачи, которые хранятся и переиспользуются. В RL — методы для случая, когда модель среды известна., это очень похоже! Если не знаете — ничего страшного.)

Уравнение Беллмана рекурсивно и работает так: вместо того чтобы для каждого состояния считать отдачу с самого начала, ценность любого состояния можно представить как

немедленную награду $R_{t+1}$ + дисконтированную ценность следующего состояния ($\gamma \cdot V(S_{t+1})$).

$$V_\pi(s) = \mathbb{E}_\pi\left[R_{t+1} + \gamma\, V_\pi(S_{t+1}) \mid S_t = s\right]$$

Вернёмся к примеру: ценность состояния 1 равна ожидаемой накопленной отдаче, если начать в этом состоянии. Это сумма наград, если агент начнёт в состоянии 1 и дальше будет всё время следовать политике.

Это то же самое, что $V(S_t)$ = немедленная награда $R_{t+1}$ + дисконтированная ценность следующего состояния $\gamma \cdot V(S_{t+1})$.

Для простоты здесь мы не дисконтируем, то есть $\gamma = 1$. Пример с $\gamma = 0{,}99$ вы увидите в разделе о Q-learning.

• Ценность $V(S_{t+1})$ = немедленная награда $R_{t+2}$ + дисконтированная ценность следующего состояния ($\gamma \cdot V(S_{t+2})$).
• И так далее.

Примечание переводчика: пример с числами

Пусть, как в лабиринте из юнита 1, каждый шаг даёт награду −1, $\gamma = 1$, а ценность следующей клетки на пути жадной политики равна −6. Тогда по уравнению Беллмана $V(S_t) = -1 + 1 \cdot (-6) = -7$: не нужно заново складывать семь наград −1, достаточно одной награды и уже известной ценности соседа. Ту же рекурсию $G_t = r_t + \gamma G_{t+1}$ урок 6.0.1 решает в коде на «коридоре».

Итак, идея уравнения Беллмана: вместо того чтобы считать каждую ценность как сумму ожидаемой отдачи (а это долго), мы считаем ценность как сумму немедленной награды и дисконтированной ценности следующего состояния.

Прежде чем идти дальше, подумайте о роли гаммы в уравнении Беллмана. Что будет, если гамма очень маленькая (например, 0,1 или даже 0)? Что будет, если она равна 1? А если она огромная, например миллион?

Монте-Карло против обучения на временных разностях

Последнее, что нужно обсудить перед Q-learning, — две стратегии обучения.

Помните: агент RL учится, взаимодействуя со средой. Идея в том, что по полученному опыту и награде агент обновляет свою функцию ценности или политику.

Монте-Карлометод Монте-Карло (в RL)EN Monte Carlo methodОценка ценности усреднением фактических отдач законченных эпизодов. Без смещения, но с большим разбросом. и обучение на временных разностяхобучение на временных разностях (TD)EN temporal-difference learningОбновление оценки после каждого шага: V(s) ← V(s) + α[r + γV(s′) − V(s)]. (Temporal Difference, TD) — две разные стратегии обучения функции ценности или функции-политики. Обе используют опыт для решения задачи RL.

Монте-Карло перед обучением использует целый эпизод опыта. TD же учится по одному шагу ($S_t, A_t, R_{t+1}, S_{t+1}$).

Объясним обе стратегии на примере метода на основе ценности.

Монте-Карло: учимся в конце эпизода

Монте-Карло ждёт конца эпизода, вычисляет $G_t$ (отдачу) и использует её как цель для обновления $V(S_t)$.

Поэтому перед обновлением функции ценности нужен полный эпизод взаимодействия. Формула (в оригинале — на картинке):

$$V(S_t) \leftarrow V(S_t) + \alpha\left[G_t - V(S_t)\right]$$

Здесь $V(S_t)$ слева — новая оценка ценности состояния $t$, справа — прежняя оценка, $\alpha$ — скорость обучения (learning rate), $G_t$ — отдача с шага $t$.

Пример. Мышка в лабиринте с котом и сыром:

• Каждый эпизод мы начинаем в одной и той же точке.
• Агент выбирает действия по политике. Например, по ε-жадной стратегии — политике, которая чередует исследование (случайные действия) и использование.
• Мы получаем награду и следующее состояние.
• Эпизод заканчивается, если кот съел мышку или мышка сделала больше 10 шагов.
• В конце эпизода у нас есть список кортежей «состояние, действие, награда, следующее состояние». Например: [[клетка 3 внизу, влево, +1, клетка 2 внизу], [клетка 2 внизу, влево, +0, клетка 1 внизу]…].
• Агент складывает все награды в $G_t$ (чтобы понять, насколько хорошо он сыграл).
• Затем обновляет $V(s_t)$ по формуле выше.
• И начинает новую игру с новыми знаниями.

Чем больше эпизодов, тем лучше агент играет.

Например, если обучать функцию ценности состояния методом Монте-Карло:

• Инициализируем функцию ценности так, чтобы для каждого состояния она возвращала 0.
• Скорость обучения (lr) — 0,1, коэффициент дисконтирования — 1 (= без дисконтирования).
• Мышка исследует среду, выбирая случайные действия.
• Мышка сделала больше 10 шагов — эпизод окончен.
• У нас есть список «состояние, действие, награда, следующее состояние», и нужно посчитать отдачу $G_{t=0}$:

$$G_t = R_{t+1} + R_{t+2} + R_{t+3} + \dots \quad \text{(для простоты не дисконтируем)}$$ $$G_0 = R_1 + R_2 + R_3 + \dots = 1 + 0 + 0 + 0 + 0 + 0 + 1 + 1 + 0 + 0 = 3$$

• Теперь можно посчитать новое $V(S_0)$:

$$V(S_0) = V(S_0) + \mathrm{lr} \cdot \left[G_0 - V(S_0)\right] = 0 + 0{,}1 \cdot [3 - 0] = 0{,}3$$

Обучение на временных разностях: учимся на каждом шаге

TD, наоборот, ждёт только одного взаимодействия (одного шага) $S_{t+1}$, чтобы построить TD-цель и обновить $V(S_t)$ с помощью $R_{t+1}$ и $\gamma \cdot V(S_{t+1})$.

Идея TD — обновлять $V(S_t)$ на каждом шаге.

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

Это называется бутстрэпомбутстрэп (в RL)EN bootstrappingОбновление оценки с опорой на другую собственную оценку (V(s′) или max Q(s′, ·)), а не на полную фактическую отдачу. Не путать с бутстрэп-выборкой из статистики. (bootstrapping): TD отчасти опирается на уже имеющуюся оценку $V(S_{t+1})$, а не на полный сэмпл $G_t$.

$$V(S_t) \leftarrow V(S_t) + \alpha\left[\underbrace{R_{t+1} + \gamma\, V(S_{t+1})}_{\text{TD-цель}} - V(S_t)\right]$$

Этот метод называют TD(0), или одношаговым TD (функция ценности обновляется после каждого отдельного шага). Разность в квадратных скобках называют TD-ошибкойTD-ошибкаEN TD errorδ = r + γV(s′) − V(s): насколько после шага дела оказались лучше (или хуже), чем ожидалось..

Тот же пример:

• Инициализируем функцию ценности так, чтобы для каждого состояния она возвращала 0.
• Скорость обучения (lr) — 0,1, коэффициент дисконтирования — 1 (без дисконтирования).
• Мышка начинает исследовать среду и выбирает случайное действие: идёт влево.
• Она получает награду $R_{t+1} = 1$, потому что съела кусочек сыра.

Теперь можно обновить $V(S_0)$:

$$V(S_0)_{\text{новое}} = V(S_0) + \mathrm{lr} \cdot \left[R_1 + \gamma \cdot V(S_1) - V(S_0)\right] = 0 + 0{,}1 \cdot [1 + 1 \cdot 0 - 0] = 0{,}1$$

Мы только что обновили функцию ценности для состояния 0.

Теперь продолжаем взаимодействовать со средой, уже с обновлённой функцией ценности.

Итог:

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

flowchart LR
subgraph MC["Монте-Карло"]
  A1["Сыграть эпизод целиком"] --> A2["Посчитать отдачу G_t"] --> A3["V(S_t) += α·(G_t − V(S_t))"]
end
subgraph TD["TD(0)"]
  B1["Сделать один шаг"] --> B2["TD-цель: R_t+1 + γ·V(S_t+1)"] --> B3["V(S_t) += α·(TD-цель − V(S_t))"]
end

Две стратегии обновления функции ценности

Промежуточные итоги

Прежде чем перейти к Q-learning, подытожим.

Функции ценности бывают двух типов:

• Функция ценности состояния: выдаёт ожидаемую отдачу, если агент начнёт в данном состоянии и дальше всё время будет действовать по политике.
• Функция ценности действия: выдаёт ожидаемую отдачу, если агент начнёт в данном состоянии, выполнит в нём данное действие, а дальше всё время будет действовать по политике.
• В методах на основе ценности мы не учим политику, а задаём её вручную и учим функцию ценности. Если у нас есть оптимальная функция ценности, будет и оптимальная политика.

Обновлять функцию ценности можно двумя способами:

• Методом Монте-Карло: обновляем по целому эпизоду и используем настоящую дисконтированную отдачу этого эпизода.
• Методом TD: обновляем по одному шагу, заменяя неизвестную $G_t$ оценкой отдачи — TD-целью.

Промежуточный тест

Лучший способ учиться и не попасть в ловушку иллюзии компетентности — проверять себя.

Промежуточный тест к юниту 22 вопроса·

1 Вопрос 1. Какие два главных подхода к поиску оптимальной политики?Можно выбрать несколько ответов

Методы на основе политикиМетоды на основе случайностиМетоды на основе ценностиЭволюционные стратегии

2 Вопрос 4. Чем отличаются Монте-Карло и TD? Выберите все верные утверждения.Можно выбрать несколько ответов

В Монте-Карло функцию ценности обновляют по целому эпизодуВ Монте-Карло функцию ценности обновляют по одному шагуВ TD функцию ценности обновляют по целому эпизодуВ TD функцию ценности обновляют по одному шагу

Проверить ответы

Вопрос 2. Что такое уравнение Беллмана?

Ответ

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

Вопрос 3. Назовите каждую часть уравнения Беллмана $V_\pi(s) = \mathbb{E}_\pi[R_{t+1} + \gamma V_\pi(S_{t+1}) \mid S_t = s]$.

Ответ

$V_\pi(s)$ — ценность состояния $s$; $R_{t+1}$ — немедленная награда; $\gamma$ — коэффициент дисконтирования; $V_\pi(S_{t+1})$ — ценность следующего состояния. Всё вместе: ценность состояния = немедленная награда + дисконтированная ценность следующего состояния.

Вопрос 5. Назовите каждую часть формулы TD-обучения $V(S_t) \leftarrow V(S_t) + \alpha[R_{t+1} + \gamma V(S_{t+1}) - V(S_t)]$.

Ответ

Слева — новая оценка ценности состояния $S_t$; справа $V(S_t)$ — прежняя оценка; $\alpha$ — скорость обучения; $R_{t+1}$ — награда; $\gamma V(S_{t+1})$ — дисконтированная оценка ценности следующего состояния; вместе $R_{t+1} + \gamma V(S_{t+1})$ — TD-цель.

Вопрос 6. Назовите каждую часть формулы Монте-Карло $V(S_t) \leftarrow V(S_t) + \alpha[G_t - V(S_t)]$.

Ответ

Слева — новая оценка ценности состояния $S_t$; справа $V(S_t)$ — прежняя оценка; $\alpha$ — скорость обучения; $G_t$ — отдача с шага $t$, посчитанная по завершённому эпизоду.

Поздравляем с окончанием теста! Если что-то упустили, перечитайте предыдущие разделы и подкрепите (😏) знания.

Знакомимся с Q-learning

Что такое Q-learning

Q-learning — это off-policy метод на основе ценности, который обучает функцию ценности действия TD-подходом:

• Off-policy: об этом поговорим в конце юнита.
• Метод на основе ценности: находит оптимальную политику косвенно, обучая функцию ценности (состояния или действия), которая говорит ценность каждого состояния или каждой пары «состояние — действие».
• TD-подход: обновляет функцию ценности действия на каждом шаге, а не в конце эпизода.

Q-learning — это алгоритм, которым мы обучаем Q-функцию, то есть функцию ценности действия: она определяет ценность пребывания в данном состоянии и выбора в нём данного действия.

По состоянию и действию Q-функция выдаёт ценность пары «состояние — действие» (её ещё называют Q-значением).

Буква Q — от слова Quality («качество»), то есть ценности этого действия в этом состоянии.

Ещё раз о разнице между ценностью и наградой:

• Ценность состояния или пары «состояние — действие» — это ожидаемая накопленная награда, которую агент получит, если начнёт в этом состоянии (или с этой пары) и дальше будет действовать по своей политике.
• Награда — это обратная связь от среды после выполнения действия в состоянии.

Внутри Q-функция хранится в Q-таблице — таблице, где каждая клетка соответствует ценности пары «состояние — действие». Считайте Q-таблицу памятью или шпаргалкой Q-функции.

Разберём пример с лабиринтом. В оригинале нарисован лабиринт из 2×3 клеток, мышка в начальной клетке и пустая Q-таблица.

Q-таблица инициализирована, поэтому все значения равны 0. Эта таблица хранит для каждого состояния и действия соответствующую ценность пары «состояние — действие». В этом простом примере состояние определяется только положением мышки. Поэтому в Q-таблице 2×3 строк — по одной на каждое возможное положение мышки. В более сложных задачах состояние может содержать больше информации, чем положение действующего лица.

Здесь видно, что ценность пары «начальное состояние, вверх» равна 0.

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

flowchart LR
S["Состояние"] --> Q["Q-функция: поиск в Q-таблице"]
A["Действие"] --> Q
Q --> V["Q-значение пары «состояние — действие»"]

Q-функция табличного Q-learning

Подытожим: Q-learning — алгоритм RL, который:

• обучает Q-функцию (функцию ценности действия), внутри которой — Q-таблица со всеми ценностями пар «состояние — действие»;
• по состоянию и действию находит в Q-таблице соответствующее значение;
• когда обучение закончено, у нас есть оптимальная Q-функция, а значит, и оптимальная Q-таблица;
• а если есть оптимальная Q-функция, то есть и оптимальная политика, потому что мы знаем лучшее действие в каждом состоянии.

В начале Q-таблица бесполезна: в ней произвольные значения для каждой пары «состояние — действие» (чаще всего её инициализируют нулями). По мере того как агент исследует среду, а мы обновляем Q-таблицу, она всё лучше и лучше приближает оптимальную политику. В оригинале это показано тремя Q-таблицами: в начале — нули, потом — заполненные числами, по которым видно ценность каждой пары.

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

Алгоритм Q-learning

Ниже — псевдокод Q-learning (в оригинале — картинка). Разберём каждую часть и посмотрим на простом примере, как она работает, прежде чем писать код. Не пугайтесь — всё проще, чем кажется! Пройдём по шагам.

Инициализировать Q(s, a) = 0 для всех s и a (для терминального состояния Q = 0)
Для каждого эпизода:
    уменьшить ε
    наблюдать начальное состояние S_0;  t ← 0
    повторять:
        выбрать действие A_t по ε-жадной политике из Q
        выполнить A_t, получить R_{t+1} и S_{t+1}
        Q(S_t, A_t) ← Q(S_t, A_t) + α·[R_{t+1} + γ·max_a Q(S_{t+1}, a) − Q(S_t, A_t)]
        t ← t + 1
    пока S_t не терминальное
Вернуть Q

Шаг 1. Инициализируем Q-таблицу

Q-таблицу нужно инициализировать для каждой пары «состояние — действие». Чаще всего её заполняют нулями.

Шаг 2. Выбираем действие по ε-жадной стратегии

ε-жадная стратегияε-жадная стратегияEN ε-greedy policyС вероятностью ε — случайное действие, иначе — действие с наибольшей оценкой Q. — политика, которая справляется с компромиссом между исследованием и использованием.

Идея в том, что при начальном значении ε = 1,0:

• с вероятностью 1 − ε мы используем знания (агент выбирает действие с наибольшей ценностью пары «состояние — действие»);
• с вероятностью ε мы исследуем (пробуем случайное действие).

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

Шаг 3. Выполняем действие $A_t$, получаем награду $R_{t+1}$ и следующее состояние $S_{t+1}$

Шаг 4. Обновляем $Q(S_t, A_t)$

Помните: в TD-обучении мы обновляем политику или функцию ценности (смотря какой метод RL выбран) после одного шага взаимодействия.

Чтобы построить TD-цель, мы берём немедленную награду $R_{t+1}$ плюс дисконтированную ценность следующего состояния, которую находим, выбирая действие, максимизирующее текущую Q-функцию в следующем состоянии. (Это и называется бутстрэпом.)

$$\text{TD-цель} = R_{t+1} + \gamma \max_a Q(S_{t+1}, a)$$

Поэтому формула обновления $Q(S_t, A_t)$ выглядит так:

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha\left[R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)\right]$$

Это значит, что для обновления $Q(S_t, A_t)$:

• нам нужны $S_t, A_t, R_{t+1}, S_{t+1}$;
• чтобы обновить Q-значение пары «состояние — действие», мы используем TD-цель.

Как строится TD-цель?

1. Получаем награду $R_{t+1}$ после действия $A_t$.
2. Чтобы получить лучшую ценность пары «состояние — действие» для следующего состояния, выбираем следующее лучшее действие жадной политикой. Обратите внимание: это не ε-жадная политика — она всегда выбирает действие с наибольшей ценностью.

Когда это Q-значение обновлено, мы оказываемся в новом состоянии и снова выбираем действие ε-жадной политикой.

Вот почему говорят, что Q-learning — off-policy алгоритм.

Off-policy и on-policy

Разница тонкая:

• Off-policyoff-policy (обучение на данных другой политики)EN off-policyПолитика, которую учим, отличается от той, что собирала данные. Пример — Q-learning; в PPO и GRPO — поправка π/π_old.: для действий (инференса) и для обновления (обучения) используются разные политики.

  Например, в Q-learning ε-жадная политика (политика действий) отличается от жадной политики, которой выбирают ценность лучшего действия в следующем состоянии при обновлении Q-значения (политика обновления).

  Политика действий — ε-жадная: $A_t$ выбирается ε-жадно из $Q$. Политика обновления — жадная: $\gamma \max_a Q(S_{t+1}, a)$.

• On-policyon-policy (обучение на данных текущей политики)EN on-policyПротивоположность — off-policy, обучение на данных другой политики.: для действий и для обновления используется одна и та же политика.

  Например, в SARSASARSAEN SARSA (state–action–reward–state–action)Как Q-learning, но в цели Q(s′, a′) действия, которое агент действительно выбрал. On-policy., другом алгоритме на основе ценности, следующую пару «состояние — действие» выбирает ε-жадная политика, а не жадная:

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha\left[R_{t+1} + \gamma\, Q(S_{t+1}, A_{t+1}) - Q(S_t, A_t)\right]$$

Примечание переводчика: зачем это LLM

Различие on-policy и off-policy всплывёт в PPO и GRPO: после первого шага оптимизации данные, собранные «старой» политикой, уже чужие, и их перевзвешивают отношением вероятностей. Это разобрано в уроках 6.0.2 и 6.0.3, а в этом курсе — в юните 8 (перевод).

Пример Q-learning

Чтобы лучше понять Q-learning, возьмём простой пример:

• Вы — мышка в крошечном лабиринте. Вы всегда начинаете в одной и той же точке.
• Цель — съесть большую кучу сыра в правом нижнем углу и не съесть яд. Ну кто же не любит сыр?
• Эпизод заканчивается, если мы съели яд, съели большую кучу сыра или сделали больше пяти шагов.
• Скорость обучения — 0,1.
• Коэффициент дисконтирования (гамма) — 0,99.

Функция награды:

• +0 — переход в клетку без сыра;
• +1 — переход в клетку с маленьким кусочком сыра;
• +10 — переход в клетку с большой кучей сыра;
• −10 — переход в клетку с ядом и, значит, гибель;
• +0 — если сделали больше пяти шагов.

Чтобы обучить агента оптимальной политике (то есть политике «вправо, вправо, вниз»), используем алгоритм Q-learning.

Шаг 1. Инициализируем Q-таблицу

Все значения — нули. Пока Q-таблица бесполезна: Q-функцию нужно обучить алгоритмом Q-learning.

Проделаем это для двух шагов обучения.

Шаг обучения 1.

Шаг 2. Выбираем действие по ε-жадной стратегии. Поскольку ε велико (= 1,0), выбираю случайное действие. В этот раз иду вправо.

Шаг 3. Выполняем действие $A_t$, получаем $R_{t+1}$ и $S_{t+1}$. Пойдя вправо, я получаю маленький кусочек сыра, так что $R_{t+1} = 1$, и оказываюсь в новом состоянии.

Шаг 4. Обновляем $Q(S_t, A_t)$ по нашей формуле (в оригинале — расчёт на картинке). Все значения в таблице пока нули, поэтому $\max_a Q(S_{t+1}, a) = 0$:

$$Q(S_t, A_t) = 0 + 0{,}1 \cdot \left[1 + 0{,}99 \cdot 0 - 0\right] = 0{,}1$$

Шаг обучения 2.

Шаг 2. Выбираем действие по ε-жадной стратегии. Снова выбираю случайное действие: ε = 0,99 всё ещё велико. (Обратите внимание: мы немного уменьшаем ε, потому что по ходу обучения исследование нужно всё реже.)

Я выбрал действие «вниз». Это плохое действие: оно ведёт к яду.

Шаг 3. Выполняем действие $A_t$, получаем $R_{t+1}$ и $S_{t+1}$. Я съел яд, поэтому получаю $R_{t+1} = -10$ и погибаю.

Шаг 4. Обновляем $Q(S_t, A_t)$. Клетка с ядом терминальная, её Q-значения нулевые:

$$Q(S_t, A_t) = 0 + 0{,}1 \cdot \left[-10 + 0{,}99 \cdot 0 - 0\right] = -1$$

Мы погибли, поэтому начинаем новый эпизод. Но видно, что за два шага исследования агент поумнел.

Продолжая исследовать и использовать среду и обновляя Q-значения по TD-цели, мы получаем Q-таблицу, которая всё лучше приближает оптимальную. В конце обучения у нас будет оценка оптимальной Q-функции.

Примечание переводчика: проверьте себя кодом

Те же два обновления в Python (значения совпадают с расчётом выше):

alpha, gamma = 0.1, 0.99
q = 0.0
q = q + alpha * (1 + gamma * 0.0 - q)     # шаг 1: «вправо», маленький сыр
print(q)                                   # 0.1
q2 = 0.0
q2 = q2 + alpha * (-10 + gamma * 0.0 - q2) # шаг 2: «вниз», яд, конец эпизода
print(q2)                                  # -1.0

Итоги по Q-learning

Q-learning — алгоритм RL, который:

• обучает Q-функцию, то есть функцию ценности действия, которая хранится во внутренней памяти — Q-таблице со всеми ценностями пар «состояние — действие»;
• по состоянию и действию находит в Q-таблице соответствующее значение;
• когда обучение закончено, у нас есть оптимальная Q-функция или, что то же самое, оптимальная Q-таблица;
• а если есть оптимальная Q-функция, то есть и оптимальная политика: мы знаем лучшее действие в каждом состоянии.

В начале Q-таблица бесполезна: в ней произвольные значения для каждой пары (чаще всего — нули). Но по мере исследования среды и обновления Q-таблицы она приближает оптимальную всё лучше.

Глоссарий

Глоссарий составлен участниками сообщества курса.

Стратегии поиска оптимальной политики

• Методы на основе политики. Политику обычно обучают нейросетью: по состоянию она выбирает действие. Здесь действие выдаёт сама нейросеть, а не функция ценности. По опыту, полученному от среды, нейросеть подстраивается и выдаёт всё лучшие действия.
• Методы на основе ценности. Здесь обучают функцию ценности, которая выдаёт ценность состояния или пары «состояние — действие», представляющую нашу политику. Но сама по себе ценность не говорит, какое действие выбрать. Поведение агента по выходу функции ценности нужно задать отдельно. Например, можно выбрать политику, которая всегда выбирает действие, ведущее к наибольшей награде (жадная политика). Итак, политика — жадная (или любое другое правило, которое выберет пользователь) и выбирает действия по значениям функции ценности.

Среди методов на основе ценности есть две главные стратегии

• Функция ценности состояния. Для каждого состояния — ожидаемая отдача, если агент начнёт в нём и будет следовать политике до конца.
• Функция ценности действия. В отличие от функции ценности состояния, считает для каждой пары «состояние — действие» ожидаемую отдачу, если агент начнёт в этом состоянии, выполнит это действие и дальше всегда будет следовать политике.

ε-жадная стратегия

• Распространённая в RL стратегия, которая соблюдает баланс между исследованием и использованием.
• С вероятностью 1 − ε выбирает действие с наибольшей ожидаемой наградой.
• С вероятностью ε выбирает случайное действие.
• ε обычно уменьшают со временем, чтобы сместить акцент на использование.

Жадная стратегия

• Всегда выбирает действие, которое, по текущим знаниям о среде, ведёт к наибольшей награде (только использование).
• Не исследует вовсе.
• Может проигрывать в средах с неопределённостью или неизвестными оптимальными действиями.

Off-policy и on-policy алгоритмы

• Off-policy: при обучении и при инференсе используются разные политики.
• On-policy: при обучении и при инференсе используется одна и та же политика.

Стратегии обучения Монте-Карло и TD

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

Тест по Q-learning

Тест по Q-learning2 вопроса·

1 Вопрос 1. Что такое Q-learning?

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

2 Вопрос 2. Что такое Q-таблица?

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

Проверить ответы

Вопрос 3. Почему, если у нас есть оптимальная Q-функция $Q^*$, у нас есть и оптимальная политика?

Ответ

Потому что, зная оптимальную Q-функцию, мы знаем лучшее действие в каждом состоянии: $\pi^*(s) = \arg\max_a Q^*(s, a)$.

Вопрос 4. Объясните, что такое ε-жадная стратегия.

Ответ

ε-жадная стратегия — политика, которая справляется с компромиссом между исследованием и использованием. Задаём ε = 1,0:

• с вероятностью 1 − ε — использование (агент выбирает действие с наибольшей ценностью пары «состояние — действие»);
• с вероятностью ε — исследование (пробуем случайное действие).

Вопрос 5. Как обновить Q-значение пары «состояние — действие»?

Ответ

$$Q(S_t, A_t) \leftarrow Q(S_t, A_t) + \alpha\left[R_{t+1} + \gamma \max_a Q(S_{t+1}, a) - Q(S_t, A_t)\right]$$

Новое Q-значение = прежнее Q-значение + скорость обучения × (TD-цель − прежнее Q-значение), где TD-цель — награда плюс дисконтированная наибольшая ценность следующего состояния.

Вопрос 6. Чем отличаются on-policy и off-policy?

Ответ

В Q-learning (off-policy) действия выбирает ε-жадная политика, а при обновлении берётся жадный $\max_a Q(S_{t+1}, a)$ — политики разные. В SARSA (on-policy) и действие, и следующая пара для обновления выбираются одной и той же ε-жадной политикой: в TD-цели стоит $Q(S_{t+1}, A_{t+1})$.

Поздравляем с окончанием теста! Если что-то упустили, перечитайте главу и подкрепите (😏) знания.

Заключение

Поздравляем с окончанием главы! Информации было много. И поздравляем с окончанием практических занятий: вы только что реализовали своего первого агента RL с нуля и поделились им на Hub.

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

Нормально, если что-то пока путается. Так было и у автора курса, и у всех, кто изучает RL.

Не спешите и как следует разберитесь в материале, прежде чем идти дальше.

В следующей главе мы углубимся в первый алгоритм глубокого обучения с подкреплением, основанный на Q-learning, — Deep Q-learning. Вы обучите агента DQN с помощью RL-Baselines3 Zoo играть в игры Atari (перевод юнита 3).

Продолжайте учиться и оставайтесь крутыми 🤗

Дополнительное чтение

Это необязательные материалы для тех, кто хочет копнуть глубже.

Монте-Карло и TD-обучение

• Почему у методов TD дисперсия меньше, чем у Монте-Карло? (Cross Validated).
• Когда методы Монте-Карло предпочтительнее TD? (Cross Validated).

Q-learning

• Reinforcement Learning: An Introduction, Саттон и Барто, главы 5, 6 и 7.
• Foundations of Deep RL Series, L2: Deep Q-Learning — Питер Аббил (видео).

Примечание переводчика: что читать по-русски

Смещение и разброс Монте-Карло против TD с числами разобраны в уроке 6.0.2; там же браузерное задание «Q-learning и SARSA на скользком озере».

Словарик

English	Русский
value-based method	метод на основе ценности
state-value function $V$	функция ценности состояния
action-value function $Q$, Q-value	функция ценности действия, Q-значение
greedy / epsilon-greedy policy	жадная / ε-жадная политика
Bellman equation	уравнение Беллмана
Monte Carlo (MC)	метод Монте-Карло
Temporal Difference (TD), TD target, TD error	временные разности, TD-цель, TD-ошибка
bootstrapping	бутстрэп
learning rate	скорость обучения
Q-table	Q-таблица
off-policy / on-policy	off-policy / on-policy
acting policy / updating policy	политика действий / политика обновления
tabular method	табличный метод