Динамическое программирование

Два способа решить одно уравнение

Уравнение Беллмана можно решать двумя способами, и они устроены принципиально по-разному.

$$\htmlData{k=vi}{V \leftarrow \max_a\big[R + \gamma P V\big]} \qquad\text{против}\qquad \htmlData{k=pi}{\begin{cases} V^{\pi} \text{ решить точно} \\ \pi \leftarrow \text{greedy}(V^\pi)\end{cases}}$$

Value iteration делает один шаг оператора и идёт дальше. Policy iteration вместо этого решает уравнение для фиксированной политики — без максимума оно линейно, — а затем делает один жадный шаг.

Измерение

Разница на случайном MDP с восемью состояниями и четырьмя действиями, $\gamma = 0.9$, точность $10^{-10}$:

алгоритм	итераций
value iteration	$215$
policy iteration	$3$

Обе дают одно и то же $V^*$ (совпадение до $10^{-8}$). Разница в семьдесят раз — не аномалия, а типичная картина, и объясняется она одним наблюдением из урока 020: политике нужен порядок величин, а не сами величины. Value iteration уточняет числа до десятого знака, хотя порядок установился давно; policy iteration переспрашивает только про порядок.

Но итерации у них разной цены:

	стоимость одной итерации
проход value iteration	$O(\vert S\vert^2\vert A\vert)$
точная оценка политики	$O(\vert S\vert^3)$ решением системы
приближённая оценка	$O(k\vert S\vert^2)$ за $k$ проходов

При $|S| = 8$, $|A| = 4$ это $256$ против $512$ — то есть policy iteration дороже вдвое за итерацию и всё равно выигрывает в семьдесят раз по общей работе. При больших $|S|$ кубический член становится неприемлемым, и его заменяют несколькими проходами вместо точного решения. Так получается обобщённое policy iteration, частными случаями которого оказываются оба алгоритма:

$k$ проходов оценки	что получается
$1$	value iteration
до сходимости	policy iteration
$3{-}10$	то, что используют на практике

Гарантия завершения

У policy iteration есть свойство, которого нет у value iteration: она заканчивается точно, за конечное число шагов. Причина комбинаторная — политик конечное число ($|A|^{|S|}$), каждая итерация строго улучшает политику (теорема из урока 030), а значит ни одна не повторяется.

Value iteration в общем случае сходится лишь в пределе: значения приближаются к $V^*$ геометрически и достигают её точно только в вырожденных случаях вроде детерминированной сетки из урока 010.

Практический вывод обратен интуиции: алгоритм, который «делает больше работы за итерацию», завершается за меньшее их число и с точным ответом.

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

дисконт γ

0.9

проходов

5

цена шага

-0.04

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

10

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

-0.164

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

5.6e-1

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

7

Три оговорки

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

Нужен перебор всех состояний. Проход по $|S|$ состояниям невозможен, когда $|S|$ велико. Отсюда асинхронные варианты, где обновляются не все состояния подряд, а те, что чаще встречаются или где ошибка больше. Сходимость сохраняется, если каждое состояние обновляется бесконечно часто.

Нужна табличная форма. Значения хранятся как массив, по числу на состояние. Как только $V$ становится нейросетью, теория из урока 030 перестаёт применяться: оператор Беллмана в композиции с проекцией на пространство функций сети не обязан быть сжимающим, и расходимость становится возможной. Это известная «смертельная триада» — аппроксимация, бутстрэппинг и off-policy обучение вместе, — и урок 090 к ней вернётся.

Третья оговорка — самая важная и чаще всего пропускаемая. Аккуратные гарантии этого блока относятся к таблицам; всё, что работает в больших задачах, работает без них.

Итог

• Value iteration и policy iteration решают одно уравнение с разной стратегией.
• Измерено: $215$ проходов против $3$ итераций на одной задаче, при цене итерации вдвое выше.
• Причина — политике нужен порядок величин, а не их точность.
• Policy iteration завершается точно за конечное число шагов; value iteration — в пределе.
• Обобщённая схема с несколькими проходами оценки покрывает оба алгоритма и используется на практике.
• Всё это требует модели, перебора состояний и табличного представления.