REINFORCE и дисперсия

Алгоритм

REINFORCE — прямая реализация теоремы прошлого урока: сыграть эпизод, посчитать возвраты, сделать шаг.

$\theta \leftarrow \theta + \alpha \sum_t G_t \,\nabla_\theta \log\pi_\theta(a_t \mid s_t)$

Работает, несмещён — и почти неприменим в чистом виде из-за дисперсии. Урок про то, откуда она берётся и что с ней делают.

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

Вычтем из веса произвольную величину $b(s)$, не зависящую от действия:

$$\nabla_\theta J = \mathbb{E}\Big[\big(G_t - \htmlData{k=base}{b(s_t)}\big)\nabla_\theta\log\pi_\theta(a_t\mid s_t)\Big]$$

Оценка остаётся несмещённой, потому что

$\mathbb{E}_{a\sim\pi}\big[b(s)\nabla_\theta\log\pi_\theta(a\mid s)\big] = b(s)\sum_a \pi_\theta(a\mid s)\frac{\nabla_\theta\pi_\theta(a\mid s)}{\pi_\theta(a\mid s)} = b(s)\,\nabla_\theta\!\!\sum_a \pi_\theta(a\mid s) = b(s)\,\nabla_\theta 1 = 0$

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

Насколько это важно

Возьмём трёхрукий бандит с наградами $1$, $0$, $2$ и равномерную политику. Точная дисперсия оценки градиента (не выборочная — посчитанная по определению):

базовая линия $b$	дисперсия
$0$	$0.889$
$0.5$	$0.389$
$1.0$	$0.222$
$1.5$	$0.389$
$2.0$	$0.889$

Градиент при этом во всех строках одинаков — $(0, -1/3, +1/3)$. Оптимум приходится на $b = 1.0$, то есть на среднюю награду, и даёт четырёхкратное снижение.

Но настоящий эффект виден, если сдвинуть все награды на константу. Возьмём $101$, $100$, $102$ — задача та же, предпочтения те же:

	дисперсия	градиент
без базовой линии	$6800.9$	$(0, -1/3, +1/3)$
с базовой линией $101$	$0.222$	$(0, -1/3, +1/3)$

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

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

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

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

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

0.1

шагов

200

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

1.956

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

0.0919

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

2.5e-3

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

1.956

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

Какая базовая линия лучшая

Естественный выбор — $b(s) = V(s)$, ожидаемый возврат из состояния. Тогда вес превращается в $G_t - V(s_t)$ — оценку преимущества из урока 020, и градиент читается как «сделать вероятнее то, что оказалось лучше ожидаемого».

Строго говоря, $V$ не минимизирует дисперсию: оптимум — взвешенное по квадрату градиента среднее возврата. Разница обычно мала, а $V$ нужна и по другим причинам, поэтому на практике берут её.

Заметьте, что как только $V$ обучается вместе с политикой, получается actor–critic: одна сеть выбирает действия, другая оценивает состояния и служит базовой линией. Ничего нового в схему при этом не добавилось — только конкретный выбор $b$.

Другие источники дисперсии

Базовая линия убирает один вклад, но не все:

источник	лечение
абсолютный уровень награды	базовая линия
награды из прошлого в весе $G_t$	причинность: суммировать только с $t$
длинный горизонт	бутстрэппинг, $n$-шаговые возвраты (урок 080)
стохастичность политики	понижение энтропии по ходу обучения
стохастичность среды	не лечится, только усреднением

Вторая строка стоит пояснения. В исходной формуле веса $G_t$ включают награды до момента $t$, хотя действие $a_t$ на них повлиять не могло. Их вклад в среднем нулевой (по тому же доводу, что и для базовой линии), но дисперсию они добавляют. Отсюда версия «reward-to-go», которую и используют всегда.

Итог

• REINFORCE несмещён и почти неприменим без снижения дисперсии.
• Базовая линия не вносит смещения, потому что градиент единицы равен нулю.
• Измерено: сдвиг наград на константу меняет дисперсию в тридцать тысяч раз, не меняя градиента.
• Выбор $b = V(s)$ превращает вес в преимущество и даёт actor–critic.
• Причинность, $n$-шаговые возвраты и контроль энтропии убирают другие вклады.