Обучение с подкреплением и выравнивание

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

V, Q и преимущество — три способа сказать «насколько здесь хорошо»

Шаг 103 из 117 · ~24 мин

Три величины

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

Vπ(s)=Eπ[Gt∣st=s],Qπ(s,a)=Eπ[Gt∣st=s, at=a]\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]

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

Vπ(s)=∑aπ(a∣s) Qπ(s,a),Qπ(s,a)=E[r+γVπ(s′)]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π(s,a)=Qπ(s,a)−Vπ(s)A^\pi(s,a) = Q^\pi(s,a) - V^\pi(s)

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

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

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

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

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

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

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

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

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

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

0.62→0.73→0.86→10.52↑0.73↑0.86↑0.43↑0.52→0.62↑0.73↑0.34↑0.52↑0.62↑

цель стена

дисконт γ 0.9
проходов 12
цена шага -0.04
горизонт 1/(1−γ)
10
значение старта
0.344
изменение за проход
0.0e+0
проходов до сходимости
7
Стрелка показывает argmax по Q(s,·), посчитанному из текущих V. Обратите внимание, что политика становится оптимальной раньше, чем значения сходятся: направление перестаёт меняться, пока числа ещё уточняются. Это и есть причина, по которой policy iteration из урока 040 обычно требует меньше итераций.

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

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

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

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

−0.04+0.9⋅1=0.86-0.04 + 0.9 \cdot 1 = 0.86

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

расстояние до целизначение
110.8600.860
220.7340.734
330.6210.621
440.5190.519
550.4270.427

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

Итог

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

Источники

Проверки

0 из 2
  1. V, Q и преимущество

    Отметьте все верные утверждения о функциях ценности.

  2. От Q к V и преимуществу

    Реализуйте advantage_facts(policy, q_values) — два списка одинаковой длины: вероятности политики в некотором состоянии и ценности действий в нём. Верните [state_value, first_advantage, mean_advantage, greedy_index]:

    • state_value = ∑aπ(a) Q(a)\sum_a \pi(a)\,Q(a);
    • first_advantage = Q(0)−VQ(0) - V — преимущество нулевого действия;
    • mean_advantage = ∑aπ(a) A(a)\sum_a \pi(a)\,A(a) — обязано быть нулём;
    • greedy_index — индекс действия с наибольшим QQ (при равенстве берите наименьший индекс), возвращённый как число.

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

    функция advantage_facts

    Загрузка редактора…

    Ctrl/⌘ + Enter