Temporal difference и Q-learning

Снять требование модели

Динамическое программирование упиралось в $\sum_{s'}P(s'\mid s,a)$. Заменим математическое ожидание выборкой: агент сделал шаг, увидел награду и следующее состояние — этого достаточно.

$$V(s) \leftarrow V(s) + \alpha\,\underbrace{\big[\htmlData{k=target}{r + \gamma V(s')} - V(s)\big]}_{\htmlData{k=error}{\delta}}$$

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

Сравним с двумя соседями:

метод	цель	нужна модель	ждать конца эпизода
динамическое программирование	$\mathbb{E}[r + \gamma V(s')]$	да	нет
Монте-Карло	наблюдённый $G_t$ целиком	нет	да
TD(0)	$r + \gamma V(s')$	нет	нет

TD берёт лучшее из двух столбцов: выборку вместо ожидания у Монте-Карло, бутстрэппинг вместо полного возврата у динамического программирования.

Почему TD обычно лучше Монте-Карло

Ожидание такое: цель TD смещена (использует несовершенную оценку $V(s')$), зато у неё намного меньше дисперсия — она зависит от одного случайного перехода, а не от всей траектории. Монте-Карло несмещён, но собирает шум всего эпизода.

Проверим на классическом случайном блуждании из пяти состояний, где истинные значения известны точно и равны $\frac16, \frac26, \dots, \frac56$. Пятьдесят прогонов, $\alpha = 0.05$:

метод	средняя RMS-ошибка после 100 эпизодов	после 1000
TD(0)	$0.038$	$0.037$
Монте-Карло	$0.119$	$0.123$

TD втрое точнее, и разрыв не сокращается с числом эпизодов — при постоянном $\alpha$ обе оценки выходят на плато, определяемое дисперсией цели. Смещение TD при этом на результат почти не влияет: оно исчезает по мере того, как $V$ становится точнее, а дисперсия — не исчезает никогда.

Полезная формулировка: TD меняет несмещённость на дисперсию, и обмен обычно выгоден. Урок 080 покажет, что между этими двумя крайностями есть непрерывное семейство.

Q-learning

Чтобы выбирать действия без модели, нужна $Q$, а не $V$ (урок 020). Правило то же, с максимумом внутри:

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

Максимум делает алгоритм off-policy: цель говорит о жадной политике, а данные собираются какой угодно — например $\varepsilon$-жадной. Это разделение полезно: можно исследовать среду случайно и при этом выучивать оптимальную политику.

Сравните с SARSA, где вместо максимума стоит фактически выбранное действие:

$Q(s,a) \leftarrow Q(s,a) + \alpha\big[r + \gamma Q(s',a') - Q(s,a)\big]$

	Q-learning	SARSA
цель	по жадному действию	по фактическому
что выучивает	оптимальную политику	ценность своей политики
поведение у обрыва	идёт по краю	обходит с запасом

Третья строка — знаменитый пример «cliff walking», и он не курьёз. Если поведение остаётся $\varepsilon$-жадным, SARSA учитывает, что иногда сорвётся, и держится подальше; Q-learning выучивает путь, оптимальный для агента, который никогда не ошибается. Какой ответ правильный, зависит от того, будет ли исследование выключено при использовании.

терминал стена

дисконт γ

0.9

проходов

20

цена шага

-0.04

горизонт 1/(1−γ)

10

значение старта

0.344

изменение за проход

0.0e+0

проходов до сходимости

7

Точное решение. Именно к нему сходится табличный Q-learning при бесконечном исследовании и убывающем шаге.

Условия сходимости

Табличный Q-learning сходится к $Q^*$ при двух условиях:

1. каждая пара $(s,a)$ посещается бесконечно часто;
2. шаги удовлетворяют условиям Роббинса–Монро: $\sum\alpha_t = \infty$, $\sum\alpha_t^2 < \infty$.

Второе условие — то же самое, что в стохастической аппроксимации (блок 5, урок 060): шаги должны убывать, но не слишком быстро. Например $\alpha_t = 1/t$ подходит, $\alpha_t = 1/t^2$ — нет (сумма конечна, и алгоритм остановится, не дойдя).

Первое условие практически недостижимо и в этом вся трудность применения: чтобы гарантированно выучить, нужно бесконечно исследовать; чтобы получать награду, нужно использовать выученное. Компромисс называют exploration–exploitation, и универсального решения у него нет — $\varepsilon$-жадность, оптимистичная инициализация, UCB и энтропийные бонусы (урок 120) решают его по-разному.

Итог

• TD заменяет ожидание выборкой и полный возврат — бутстрэппингом.
• Обмен «смещение против дисперсии» обычно выгоден: втрое меньшая ошибка на классическом тесте.
• Q-learning off-policy благодаря максимуму в цели; SARSA on-policy и потому осторожнее.
• Сходимость требует бесконечного исследования и убывающих по Роббинсу–Монро шагов.
• Первое условие недостижимо, и отсюда вся проблематика исследования.