Уравнение Беллмана: принцип оптимальности простыми словами

Уравнение Беллмана - это рекуррентное соотношение, которое связывает ценность текущего состояния с ценностью состояний, в которые можно перейти. Его сформулировал Ричард Беллман в 1950-х как ядро динамического программирования: вместо того чтобы перебирать все возможные траектории целиком, мы разбиваем задачу на шаги и решаем её «с конца». Сегодня уравнение Беллмана - фундамент обучения с подкреплением, оптимального управления и многих алгоритмов на графах. Ниже разберём, откуда берётся рекуррентность, чем функция ценности $V$ отличается от $Q$, и как из уравнения получаются рабочие алгоритмы. Если хотите сразу примерить идею на свою задачу - соберите запрос в форме ниже.

Принцип оптимальности - откуда берётся рекуррентность

В основе лежит принцип оптимальности Беллмана: оптимальная траектория обладает тем свойством, что какова бы ни была первая принятая мысль, оставшийся хвост траектории тоже оптимален относительно состояния, в которое мы попали. Иными словами, оптимальное решение целого складывается из оптимальных решений его частей.

Это и позволяет записать рекуррентность. Пусть $V^*(s)$ - максимальная суммарная награда, которую можно набрать, стартуя из состояния $s$ и действуя оптимально. Тогда ценность $s$ равна лучшему из вариантов «получить немедленную награду за действие плюс ценность того состояния, куда мы перейдём». Длинную задачу про всю траекторию мы свернули в локальное соотношение между соседними состояниями.

Рассчитать для своей задачи

Уравнение Беллмана для функции ценности V

Для марковского процесса принятия решений уравнение Беллмана оптимальности записывается так:

$$V^*(s) = \max_{a} \left[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^*(s') \right]$$

Разберём по частям. $R(s, a)$ - немедленная награда за действие $a$ в состоянии $s$. $P(s' \mid s, a)$ - вероятность оказаться в состоянии $s'$. $\gamma \in [0, 1)$ - коэффициент дисконтирования: он показывает, насколько мы цените будущее по сравнению с настоящим. При $\gamma$ близком к нулю агент жаден и смотрит на шаг вперёд; при $\gamma$ близком к единице он терпелив и учитывает далёкую перспективу. Сумма по $s'$ усредняет ценность следующего состояния по всем исходам.

Если среда детерминированная (действие однозначно ведёт в одно состояние), сумма исчезает и уравнение упрощается:

$$V^*(s) = \max_{a} \left[ R(s, a) + \gamma\, V^*(s'_{s,a}) \right]$$

V против Q - две функции ценности

Рядом с $V$ почти всегда встречается функция ценности действия $Q^*(s, a)$ - ожидаемая награда, если в состоянии $s$ выбрать действие $a$, а дальше действовать оптимально:

$$Q^*(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, \max_{a'} Q^*(s', a')$$

Связь простая: $V^*(s) = \max_a Q^*(s, a)$. Разница в удобстве. $V$ отвечает на вопрос «насколько хорошо это состояние», но чтобы выбрать действие, нужно знать модель среды $P$ и $R$. $Q$ сразу хранит ценность по парам «состояние-действие», поэтому оптимальная политика читается без модели: $\pi^*(s) = \arg\max_a Q^*(s, a)$. Именно поэтому Q-обучение так популярно в безмодельном обучении с подкреплением.

Полезно держать в голове, что обе функции описывают одно и то же оптимальное поведение, просто с разной «гранулярностью». $V$ компактнее: на $n$ состояний приходится $n$ чисел. $Q$ хранит $n \times m$ чисел для $m$ действий, но взамен снимает необходимость заглядывать в модель при выборе хода. На практике выбор между ними диктуется тем, известна ли среда: если модель $P$ и $R$ под рукой - работают с $V$ и планируют; если агент учится из взаимодействия - удобнее $Q$.

Рассчитать для своей задачи

Уравнение Беллмана для фиксированной политики

Уравнение со знаком $\max$ описывает оптимальное поведение. Но иногда нужно оценить уже заданную политику $\pi$ - например, чтобы потом её улучшить. Тогда максимум заменяется усреднением по действиям, которые выбирает $\pi$:

$$V^\pi(s) = \sum_{a} \pi(a \mid s) \left[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V^\pi(s') \right]$$

Это уравнение Беллмана для оценки политики (Bellman expectation equation). Для конечного числа состояний оно превращается в систему линейных уравнений и решается напрямую. А чередуя оценку политики с её жадным улучшением, получаем классический алгоритм итерации по политике (policy iteration).

Как из уравнения получаются алгоритмы

Уравнение Беллмана - не только формула, но и рецепт вычисления. Поскольку $V^*$ является неподвижной точкой оператора Беллмана, к ней можно сходиться итерациями. Метод итерации по ценности (value iteration) делает это прямолинейно: начинаем с произвольных $V_0$ и многократно применяем правую часть уравнения как оператор обновления:

$$V_{k+1}(s) = \max_{a} \left[ R(s, a) + \gamma \sum_{s'} P(s' \mid s, a)\, V_k(s') \right]$$

Оператор Беллмана является сжимающим отображением с коэффициентом $\gamma$, поэтому последовательность $V_k$ гарантированно сходится к единственной $V^*$. На практике итерации обрывают, когда максимальное изменение ценности по всем состояниям становится меньше малого порога. Та же идея «разбить на подзадачи и собрать с конца» лежит и в основе алгоритмов на графах - например, в алгоритме Беллмана-Форда для кратчайших путей или в задаче о рюкзаке, где функция ценности - это максимальная стоимость при заданной вместимости.

Рассчитать для своей задачи

Маленький пример на пальцах

Возьмём детерминированную среду из трёх состояний в линию: $A \to B \to C$, где $C$ - терминальное с наградой за вход $+10$, а переходы $A \to B$ и $B \to C$ дают награду $0$. Пусть $\gamma = 0{,}9$. Тогда:

$$\begin{aligned} V^*(C) &= 0 \\ V^*(B) &= 0 + 0{,}9 \cdot V^*(C) + 10 = 10 \\ V^*(A) &= 0 + 0{,}9 \cdot V^*(B) = 9 \end{aligned}$$

Ценность $A$ получилась меньше ценности $B$ именно из-за дисконтирования: до награды из $A$ идти на шаг дольше, поэтому будущие $+10$ обесцениваются множителем $\gamma$. Поменяйте $\gamma$ - и расклад ценностей сместится: чем терпеливее агент, тем ближе ценности дальних состояний к награде в конце.

Обратите внимание на порядок вычисления: мы посчитали ценности с конца - сначала терминальное $C$, затем $B$, затем $A$. Это и есть динамическое программирование в чистом виде: рекуррентность Беллмана позволяет получить ответ за один проход в обратном порядке, не перебирая траектории. Когда среда содержит циклы и однозначного «конца» нет, прямой проход с конца невозможен - там и выручает итеративный метод: мы применяем оператор Беллмана многократно, пока ценности не перестанут меняться, и сходимость гарантирует сжимаемость оператора.

Частые ошибки

• Путают $V$ и $Q$. $V(s)$ оценивает состояние, $Q(s, a)$ - пару состояние-действие. Чтобы выбрать действие по $V$, нужна модель среды; по $Q$ - нет.
• Берут $\gamma = 1$ в бесконечном горизонте. Без дисконта (или терминальных состояний) сумма наград расходится, и уравнение теряет единственное решение. Для эпизодических задач $\gamma = 1$ допустимо.
• Путают уравнение оптимальности и уравнение оценки политики. Со знаком $\max$ - про оптимальное поведение, с усреднением по $\pi$ - про оценку конкретной политики.
• Считают, что одной итерации хватит. Value iteration сходится в пределе; нужно повторять обновление до стабилизации ценностей, а не применять формулу один раз.
• Забывают про дисконт в немедленной награде. Множитель $\gamma$ стоит только перед будущей ценностью $V(s')$, а не перед $R(s, a)$ текущего шага.

FAQ

Чем уравнение Беллмана отличается от принципа оптимальности? Принцип оптимальности - это словесная идея: хвост оптимальной траектории сам оптимален. Уравнение Беллмана - её математическая запись в виде рекуррентного соотношения между ценностями соседних состояний.

Почему в уравнении стоит коэффициент дисконтирования $\gamma$? Он задаёт, насколько агент ценит будущие награды относительно текущих, и одновременно гарантирует сходимость суммы наград в задачах с бесконечным горизонтом. При $\gamma < 1$ оператор Беллмана становится сжимающим, что обеспечивает единственное решение.

Как уравнение Беллмана связано с обучением с подкреплением? Q-обучение и SARSA - это способы приближённо решать уравнение Беллмана для $Q$ по выборкам опыта, без явной модели среды. Обновление Q-значения буквально подтягивает оценку к правой части уравнения Беллмана.

Коротко

Уравнение Беллмана сворачивает задачу про оптимальную траекторию в локальную рекуррентность: ценность состояния равна лучшей немедленной награде плюс дисконтированная ценность следующего состояния. Через функцию $V$ оно оценивает состояния, через $Q$ - пары состояние-действие, а как сжимающий оператор задаёт сходящиеся алгоритмы итерации по ценности и по политике. Это общий мостик между динамическим программированием, оптимальным управлением и обучением с подкреплением.