Dynamic programming — это один принцип, который прячется за поиском кратчайшего пути в графе, подсчётом градиентов при обучении нейросети и разбором контекстно-свободных грамматик. Ричард Беллман, создатель метода, сформулировал его так: оптимальная политика устроена так, что каковы бы ни были начальное состояние и первое решение, все последующие решения должны быть оптимальны относительно состояния, получившегося после первого шага.
Чтобы понять это, автор строит формальную модель. Есть автомат: множество состояний, в каждом состоянии доступны действия. Действие переводит систему в новое состояние и приносит стоимость. Последовательность действий образует траекторию. Политика — правило, которое для каждого состояния выбирает действие. Стоимость политики — сумма дисконтированных затрат, где дисконт γ ∈ [0,1] показывает, что будущие расходы важны меньше. Такую постановку можно применить к задаче о кратчайшем пути: города — состояния, рёбра — действия, веса рёбер — стоимости.
Беллман заметил: чтобы найти оптимальную политику, задачу нужно решать рекурсивно. Если после первого действия мы попали в новое состояние, дальше нужно решать ту же задачу из этого состояния. Это даёт уравнение Беллмана: v(s) = min_a [c(s,a) + γ v(T(s,a))]. Всё dynamic programming — это методы решения этого уравнения. Уравнение можно переписать как неподвижную точку оператора Беллмана. Применив теорему Банаха о неподвижной точке, получаем: если дисконт меньше единицы, решение существует и единственно, и его можно найти итерациями оператора.
Отсюда два классических алгоритма. Value iteration повторяет v ← Bv, пока изменение не станет меньше допуска. Каждая итерация требует O(|S|·|A|) операций, а минимизацию для каждого состояния можно считать параллельно. Есть вариант с обновлением in-place, который быстрее на одном процессоре, но теряет параллельность. Policy iteration работает иначе: он поочерёдно оценивает текущую политику и улучшает её, выбирая лучшие действия относительно найденной ценности. Такой подход находит оптимальную политику за конечное число шагов.
Автор подчёркивает: memoization, которую обычно ассоциируют с dynamic programming, — это лишь деталь представления функций, а не суть метода. Принцип работает от планирования траектории ракеты до переноса строк в TeX. А обобщения на бесконечные пространства дают Reinforcement Learning и Stochastic Dual Dynamic Programming, но это уже другая история.