Q-обучение: алгоритм обучения с подкреплением по шагам

Обучение с подкреплением - это раздел машинного обучения, где агент учится не на готовых примерах с ответами, а на собственном опыте: пробует действия, получает награды и постепенно понимает, как вести себя выгоднее. Q-обучение (Q-learning) - самый известный табличный алгоритм этого семейства. Он хранит оценку «полезности» каждого действия в каждом состоянии и обновляет её по одному простому правилу. Ниже разберём это правило по частям, посмотрим, как ценность сходится к оптимуму, и чем Q-обучение отличается от родственного SARSA. Прежде чем читать формулы, можно покрутить параметры обучения в калькуляторе и увидеть сходимость своими глазами.

Что такое обучение с подкреплением

В задаче обучения с подкреплением есть агент и среда. На каждом шаге агент видит текущее состояние $s$, выбирает действие $a$, среда переводит его в новое состояние $s'$ и выдаёт скалярную награду $r$. Цель агента - выбрать стратегию (политику) действий так, чтобы суммарная награда за всё взаимодействие была максимальной.

Формально среда описывается марковским процессом принятия решений: будущее зависит только от текущего состояния и действия, а не от всей истории. Награда обычно дисконтируется: близкая ценнее далёкой. Это та же идея, что в методе дисконтированных денежных потоков - рубль сегодня дороже рубля завтра, поэтому будущие награды умножают на коэффициент $\gamma < 1$.

Ключевая величина - ценность действия $Q(s, a)$: ожидаемая суммарная дисконтированная награда, если из состояния $s$ сделать действие $a$, а дальше действовать оптимально. Если бы мы знали все $Q$ точно, оптимальная стратегия была бы тривиальной: в каждом состоянии выбирай действие с наибольшим $Q$. Q-обучение как раз и оценивает эту функцию из опыта.

Q-таблица: память агента

В табличном Q-обучении функция $Q(s, a)$ хранится буквально как таблица: строки - состояния, столбцы - действия, в клетках - текущие оценки ценности. В начале все клетки заполнены нулями (агент ничего не знает), и по мере накопления опыта числа в таблице уточняются.

Представим агента в сетке-лабиринте $3 \times 3$, который ищет выход. Состояние - клетка, где он стоит; действия - «вверх», «вниз», «влево», «вправо». Q-таблица здесь - это 9 строк (клеток) на 4 столбца (направления). Когда агент случайно доходит до выхода и получает награду, эта награда «протекает» назад по таблице: сначала повышается ценность последнего шага, потом предпоследнего, и так до старта.

Правило обновления Q

Сердце алгоритма - одна формула. После того как агент из состояния $s$ сделал действие $a$, получил награду $r$ и оказался в $s'$, он обновляет клетку таблицы:

$$Q(s, a) \leftarrow Q(s, a) + \alpha\,\bigl[\,r + \gamma \max_{a'} Q(s', a') - Q(s, a)\,\bigr]$$

Разберём по частям. Выражение в скобках называют ошибкой временной разности (TD-ошибка): это разница между тем, чего мы ожидали ($Q(s, a)$), и более точной оценкой $r + \gamma \max_{a'} Q(s', a')$ - мгновенной наградой плюс дисконтированной лучшей ценностью в следующем состоянии. Агент сдвигает старую оценку в сторону новой на долю $\alpha$.

Рассчитать для своей задачи

Параметры:

• Скорость обучения $\alpha \in (0, 1]$ - насколько сильно новый опыт перетягивает старую оценку. При $\alpha = 1$ старое значение полностью забывается и заменяется новым; при малом $\alpha$ таблица меняется медленно и плавно.
• Коэффициент дисконтирования $\gamma \in [0, 1)$ - насколько агент ценит будущее. При $\gamma$ около нуля он жадничает на мгновенную награду; при $\gamma$ около единицы планирует на много шагов вперёд.
• $\max_{a'} Q(s', a')$ - лучшая ценность в новом состоянии. Именно этот максимум делает Q-обучение «жадным» в оценке будущего.

Уравнение Беллмана: куда всё сходится

Правило обновления не случайно. Оно приближает решение уравнения оптимальности Беллмана, которое описывает, какой должна быть истинная функция ценности:

$$Q^*(s, a) = r(s, a) + \gamma \max_{a'} Q^*(s', a')$$

Это уравнение говорит: оптимальная ценность действия равна немедленной награде плюс дисконтированной оптимальной ценности следующего состояния. TD-ошибка в правиле обновления - это в точности невязка уравнения Беллмана: насколько текущая оценка не выполняет это равенство. Каждое обновление чуть-чуть уменьшает невязку.

Для простого детерминированного коридора из $N$ клеток, где награда $R$ ждёт только в конце, оптимальная ценность старта равна

$$Q^*(\text{старт}) = \gamma^{\,N-1} R$$

• награда, дисконтированная на число шагов до неё. Именно к этому значению сходится синяя кривая в калькуляторе выше: повышайте число эпизодов - и оценка стартовой клетки подползает к пунктирному оптимуму.

Исследование и эксплуатация

Если агент всегда выбирает действие с максимальным $Q$, он застрянет на первом найденном неплохом пути и не узнает о лучших. Это дилемма исследование против эксплуатации: пробовать новое или использовать уже известное хорошее.

Рассчитать для своей задачи

Стандартное решение - $\varepsilon$-жадная стратегия. С вероятностью $\varepsilon$ агент выбирает действие случайно (исследует), а с вероятностью $1 - \varepsilon$ - действие с максимальным $Q$ (эксплуатирует):

$$a = \begin{cases} \text{случайное действие}, & \text{с вероятностью } \varepsilon \\ \arg\max_a Q(s, a), & \text{с вероятностью } 1 - \varepsilon \end{cases}$$

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

Q-обучение и SARSA: off-policy против on-policy

У Q-обучения есть близкий родственник - алгоритм SARSA. Правило обновления почти такое же, отличается только оценка будущего:

$$\text{SARSA:}\quad Q(s, a) \leftarrow Q(s, a) + \alpha\,\bigl[\,r + \gamma\,Q(s', a') - Q(s, a)\,\bigr]$$

Вместо $\max_{a'} Q(s', a')$ здесь стоит $Q(s', a')$ - ценность того действия $a'$, которое агент реально выберет в следующем состоянии (включая случайные исследовательские шаги).

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

Классический пример расхождения - задача «обрыв»: SARSA выбирает более безопасный обходной путь подальше от края, потому что учитывает риск случайно упасть, а Q-обучение находит кратчайший путь вдоль самого обрыва.

Частые ошибки

• Не уменьшать $\varepsilon$ со временем. Если оставить высокий $\varepsilon$ до конца, агент так и будет постоянно ходить случайно и не закрепит найденную стратегию.
• Слишком большая скорость обучения $\alpha$. При $\alpha$ близком к единице каждое обновление резко перезаписывает таблицу, и оценки скачут вместо плавной сходимости - особенно вредно в стохастической среде.
• Путать награду $r$ и ценность $Q$. Награда - это мгновенный сигнал от среды за один шаг; $Q$ - накопленная дисконтированная сумма наград за всё будущее. Это разные величины.
• Брать $\gamma = 1$ в бесконечной задаче. Без дисконта сумма наград может расходиться, и $\max Q$ перестаёт быть ограниченным - алгоритм не сойдётся.
• Считать, что нули в таблице - это «плохие» действия. В начале нули означают «неизвестно», а не «плохо»; пока действие не опробовано, его ценность просто не оценена.

FAQ

Гарантированно ли Q-обучение находит оптимум? Да, при теоретических условиях: каждое действие в каждом состоянии пробуется бесконечно часто, а скорость обучения $\alpha$ убывает по специальному правилу (сумма $\alpha$ расходится, сумма $\alpha^2$ сходится). На практике с постоянным небольшим $\alpha$ оно сходится к хорошему приближению.

Чем Q-обучение отличается от обучения с учителем? В обучении с учителем есть пары «вход - правильный ответ». В обучении с подкреплением правильного действия никто не подсказывает: агент получает только награду и сам выясняет, какая последовательность действий ведёт к большей суммарной награде.

Что делать, если состояний слишком много для таблицы? Переходят к Deep Q-Network: вместо таблицы функцию $Q(s, a)$ приближает нейросеть, которая принимает на вход признаки состояния и выдаёт ценности действий. Правило обновления на основе TD-ошибки сохраняется, но обучается уже сеть.

Коротко

Q-обучение - табличный алгоритм обучения с подкреплением, который хранит ценности действий $Q(s, a)$ и уточняет их по одному правилу: сдвигает старую оценку на долю $\alpha$ в сторону суммы немедленной награды и дисконтированной лучшей ценности следующего состояния. Это приближает уравнение оптимальности Беллмана, поэтому оценки сходятся к оптимальной политике. Баланс исследования и эксплуатации задаёт $\varepsilon$-жадная стратегия, а главное отличие от SARSA - жадный $\max$ в оценке будущего, делающий Q-обучение off-policy.