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

Три величины

Политика $\pi$ — это правило выбора действия: $\pi(a\mid s)$. Ценность измеряет, насколько хорошо следовать ей из данного места.

$$\htmlData{k=v}{V^\pi(s)} = \mathbb{E}_\pi[G_t \mid s_t = s], \qquad \htmlData{k=q}{Q^\pi(s,a)} = \mathbb{E}_\pi[G_t \mid s_t = s,\ a_t = a]$$

Разница между $V$ и $Q$ одна: $Q$ фиксирует первое действие, а дальше следует политике. Отсюда связь в обе стороны:

$V^\pi(s) = \sum_a \pi(a\mid s)\, Q^\pi(s,a), \qquad Q^\pi(s,a) = \mathbb{E}\big[r + \gamma V^\pi(s')\big]$

И третья величина, которая понадобится начиная с урока 080:

$A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s)$

Преимущество отвечает на вопрос «насколько это действие лучше среднего по политике». У него есть свойство, которое стоит запомнить сразу: $\mathbb{E}_{a\sim\pi}[A^\pi(s,a)] = 0$ для любого состояния — по определению, потому что $V$ и есть это среднее.

Зачем три, если хватило бы одной

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

	что даёт	чего не хватает
$V(s)$	оценку состояния	чтобы выбрать действие, нужна модель $P$
$Q(s,a)$	оценку каждого действия	в $\vert A\vert$ раз больше чисел
$A(s,a)$	сравнение действий	не даёт абсолютной величины

Вторая строка объясняет, почему Q-learning работает без модели среды: жадное действие — это $\arg\max_a Q(s,a)$, и никакого знания переходов не требуется. С одной лишь $V$ выбрать действие нельзя, не зная, куда оно ведёт.

Третья строка объясняет, почему $A$ удобно для градиента политики: там важно сравнение действий между собой, а общий уровень $V(s)$ одинаково сдвигает все и потому не несёт информации о выборе. Урок 070 покажет, что вычитание этого уровня заметно снижает дисперсию.

Оптимальность

Политика $\pi^*$ оптимальна, если $V^{\pi^*}(s) \ge V^{\pi}(s)$ для всех $s$ и всех $\pi$. Утверждение, которое стоит осознать: такая политика существует, и она одна и та же для всех состояний. То есть не бывает так, что для одного состояния хороша одна политика, а для другого другая — оптимальность достигается везде сразу.

Больше того, оптимальная политика может быть детерминированной: случайность не нужна. Оба факта следуют из теории урока 030 и оба нетривиальны — в играх с несколькими агентами, например, ни то, ни другое не верно.

Посмотрите на сетку: стрелка в каждой клетке — жадное действие по текущим значениям, и после сходимости это и есть оптимальная политика.

цель стена

дисконт γ

0.9

проходов

12

цена шага

-0.04

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

10

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

0.344

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

0.0e+0

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

7

Значения сошлись. Жадная по ним политика оптимальна — и была таковой уже несколько проходов назад.

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

Что означают конкретные числа

Возьмите клетку слева от цели: её значение $0.86$. Проверим по определению — путь занимает один шаг, платится $-0.04$, затем награда $1$ с весом $\gamma$:

$-0.04 + 0.9 \cdot 1 = 0.86$

Следующая: $-0.04 + 0.9\cdot0.86 = 0.734$. И так далее. Каждое значение — это дисконтированная стоимость оптимального пути до цели, и его можно посчитать руками, зная длину пути:

расстояние до цели	значение
$1$	$0.860$
$2$	$0.734$
$3$	$0.621$
$4$	$0.519$
$5$	$0.427$

Полезное упражнение — сверить эту таблицу с картинкой и найти клетки, где расстояние по сетке больше манхэттенского из-за стен.

Итог

• $V$ оценивает состояние, $Q$ — пару, $A$ — превосходство действия над средним.
• $\mathbb{E}_{a\sim\pi}[A] = 0$ по определению.
• Без модели среды выбрать действие можно по $Q$, но не по $V$.
• Оптимальная политика существует, одна для всех состояний, и может быть детерминированной.
• Жадная политика стабилизируется раньше, чем сходятся значения.