Преимущество и GAE

Между двумя крайностями

Урок 050 показал два способа оценить возврат: полный наблюдённый (Монте-Карло, несмещён, шумен) и одношаговый с бутстрэппингом (TD, смещён, спокоен). Между ними есть непрерывное семейство:

$A_t^{(n)} = r_t + \gamma r_{t+1} + \dots + \gamma^{n-1} r_{t+n-1} + \gamma^n V(s_{t+n}) - V(s_t)$

При $n = 1$ это TD, при $n = \infty$ — Монте-Карло. Вопрос «какое $n$» не имеет хорошего ответа, и GAE решает его иначе: взять все сразу, с экспоненциальными весами.

$$\hat{A}_t = \sum_{l \ge 0} (\gamma\htmlData{k=lam}{\lambda})^l\, \htmlData{k=delta}{\delta_{t+l}}, \qquad \delta_t = r_t + \gamma V(s_{t+1}) - V(s_t)$$

Что приятно: считается это одним обратным проходом по эпизоду, рекуррентно.

$\hat{A}_t = \delta_t + \gamma\lambda\,\hat{A}_{t+1}$

Никаких сумм по $n$ — одна строка кода.

Крайние случаи и то, что между

Возьмём $\delta = [0.5, -0.2, 0.3, 0.1]$ и $\gamma = 0.99$:

$\lambda$	$\hat{A}_0$	что это
$0$	$0.500$	ровно $\delta_0$, то есть TD
$0.5$	$0.487$	почти TD
$0.95$	$0.660$	рабочее значение
$1$	$0.693$	сумма всех $\delta$, то есть Монте-Карло

Заметьте, что при $\lambda = 0$ ответ равен первой невязке, а при $\lambda = 1$ — их дисконтированной сумме $\sum_k \gamma^k\delta_k = 0.693$. Оба предела проверяются подстановкой в формулу.

Параметр $\lambda$ имеет наглядное прочтение: он задаёт эффективный горизонт оценки преимущества,

$\frac{1}{1-\gamma\lambda}$

$\lambda$ при $\gamma = 0.99$	горизонт
$0.90$	$9.2$ шага
$0.95$	$16.8$ шага
$0.99$	$50.3$ шага

То есть $\lambda$ — не абстрактный коэффициент, а ответ на вопрос «на сколько шагов вперёд мы доверяем наблюдениям, прежде чем положиться на $V$». Именно поэтому рабочие значения лежат около $0.95$: десятки шагов обычно достаточно, чтобы увидеть последствия действия, и мало, чтобы набрать шум всего эпизода.

Два дисконта, а не один

Тонкость, которую стоит различать. В GAE фактически два параметра дисконтирования:

	что делает
$\gamma$	задаёт задачу: какие последствия вообще важны
$\lambda$	задаёт оценку: как далеко доверять выборке

Смешивать их не стоит: $\gamma$ менять нельзя, не меняя того, что оптимизируется (урок 010), а $\lambda$ — можно свободно, это чисто статистический выбор. На практике обе ручки крутят вместе, и это источник путаницы: ухудшение при $\gamma = 0.9$ означает другую задачу, а при $\lambda = 0.9$ — другой компромисс смещения и дисперсии в той же задаче.

базовая линия

рука вероятность

скорость обучения

0.15

шагов

300

ожидаемая награда

1.985

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

0.0296

смещение оценки

3.6e-3

базовая линия

1.985

Вес равен награде минус ожидаемая награда — то есть ровно преимущество.

Что даёт преимущество вместо возврата

Собирая уроки 020, 070 и этот, получаем цепочку замен, каждая из которых снижает дисперсию:

вес в градиенте	недостаток
$R(\tau)$, весь эпизод	награды до момента $t$ не относятся к делу
$G_t$, reward-to-go	абсолютный уровень награды добавляет шум
$G_t - V(s_t)$	шум всей оставшейся траектории
$\hat{A}_t^{\text{GAE}}$	смещение из-за неточной $V$

Последняя строка честно называет цену. GAE смещён при $\lambda < 1$, и смещение тем больше, чем хуже $V$. Отсюда практическое следствие: качество критика определяет, какое $\lambda$ можно себе позволить. С плохо обученной $V$ малое $\lambda$ вредно, потому что вся оценка опирается на неё; с хорошей — выгодно.

Итог

• Между TD и Монте-Карло лежит семейство $n$-шаговых оценок; GAE усредняет их с весами $(\gamma\lambda)^l$.
• Считается одним обратным проходом: $\hat{A}_t = \delta_t + \gamma\lambda\hat{A}_{t+1}$.
• $\lambda = 0$ даёт TD, $\lambda = 1$ — Монте-Карло; проверяется подстановкой.
• Эффективный горизонт оценки равен $\frac{1}{1-\gamma\lambda}$ — это и есть смысл $\lambda$.
• $\gamma$ задаёт задачу, $\lambda$ — оценку; путать их нельзя.
• Смещение GAE зависит от качества критика, и это ограничивает выбор $\lambda$.