Уравнения Беллмана

Рекурсия

Ценность состояния — это немедленная награда плюс дисконтированная ценность того, куда попадёшь. Записанное формально, это уравнение, а не определение:

$$V^*(s) = \htmlData{k=max}{\max_a} \Big[\htmlData{k=now}{R(s,a)} + \gamma \htmlData{k=later}{\textstyle\sum_{s'} P(s'\mid s,a) V^*(s')}\Big]$$

Заметьте: слева и справа стоит одна и та же неизвестная функция. Это система уравнений, а не формула для вычисления. Без максимума она линейна и решается обращением матрицы; с максимумом — нет, и вот тут появляется весь аппарат.

Оператор и сжатие

Обозначим правую часть как оператор $T$, действующий на функции: $(TV)(s) = \max_a[\dots]$. Тогда уравнение Беллмана — это $V = TV$, то есть поиск неподвижной точки.

Ключевое свойство:

$\|TU - TW\|_\infty \le \gamma\, \|U - W\|_\infty$

Оператор сближает любые две функции в $\gamma$ раз. Проверено численно на случайном MDP с шестью состояниями и тремя действиями — во всех пробах неравенство выполняется с большим запасом (например, $1.25$ против границы $5.86$).

Отсюда по теореме Банаха о неподвижной точке получается сразу всё:

следствие	что означает
неподвижная точка существует	оптимальная ценность определена
она единственна	«оптимально» — не двусмысленно
итерации $V_{k+1} = TV_k$ сходятся к ней	value iteration работает
из любого начального $V_0$	инициализация не важна для сходимости
со скоростью $\gamma^k$	сходимость геометрическая

Всё это — не пять теорем про обучение с подкреплением, а одна теорема из функционального анализа плюс проверка одного неравенства. Стоит это осознать: содержательная часть здесь — что оператор сжимает, и она держится на дисконте.

Практическая оценка ошибки

Теоретическая оценка $\gamma^k\|V_0 - V^*\|$ бесполезна: $V^*$ неизвестна. Работает другая, где всё измеримо:

$\|V_k - V^*\|_\infty \le \frac{\gamma}{1-\gamma}\,\|V_k - V_{k-1}\|_\infty$

Справа — изменение за последний проход, то есть ровно то, что показывает виджет. Измерено на том же случайном MDP при $\gamma = 0.9$:

проход	реальная ошибка	изменение	граница
$2$	$3.420$	$0.406$	$3.658$
$5$	$2.488$	$0.276$	$2.488$
$10$	$1.469$	$0.163$	$1.469$

Начиная с пятого прохода граница становится точной до шестого знака. Причина в том, что итерация выходит на геометрический режим и ошибка убывает ровно как $\gamma$ за проход; тогда $\sum_{j\ge1}\gamma^j\cdot(\text{изменение})$ и есть остаток. То есть на практике эта оценка не консервативна, а почти точна, и по ней можно останавливаться осознанно.

цель стена

дисконт γ

0.9

проходов

3

цена шага

-0.04

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

10

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

-0.108

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

7.0e-1

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

7

Улучшение политики

Второй кирпич, из которого собран следующий урок. Пусть есть политика $\pi$ и её ценность $V^\pi$. Построим жадную:

$\pi'(s) = \arg\max_a \Big[R(s,a) + \gamma \textstyle\sum_{s'} P(s'\mid s,a)V^\pi(s')\Big]$

Теорема об улучшении политики: $V^{\pi'}(s) \ge V^{\pi}(s)$ для всех $s$, причём равенство достигается только если $\pi$ уже оптимальна.

Утверждение сильнее, чем кажется. Жадность строилась по старой ценности $V^\pi$, а гарантия даётся для новой политики целиком, во всех состояниях и на всём будущем. Не «стало не хуже в среднем», а «не хуже в каждом состоянии». Именно поэтому чередование «оценить — улучшить» не может зациклиться и обязано остановиться на оптимуме.

Ограничение, которое стоит помнить

Всё сказанное требует знания $P$ и $R$ — модели среды. Оба уравнения содержат сумму по $s'$ с вероятностями перехода. Урок 040 показывает, что с этим знанием делать, а урок 050 — как обойтись без него.

Второе ограничение — размер. Проход по всем состояниям стоит $O(|S|^2|A|)$, а $|S|$ в интересных задачах астрономично: у шахмат порядка $10^{44}$ позиций. Точное динамическое программирование — инструмент для малых задач и источник теории для больших, а не метод решения последних.

Итог

• Уравнение Беллмана — это $V = TV$, поиск неподвижной точки, а не формула.
• $T$ сжимает с коэффициентом $\gamma$; отсюда существование, единственность и сходимость.
• Практическая оценка ошибки через изменение за проход почти точна, а не консервативна.
• Жадное улучшение по $V^\pi$ не ухудшает политику ни в одном состоянии.
• Всё это требует модели среды и перебора всех состояний — отсюда следующие два урока.