Принцип оптимальности и уравнение Беллмана

Ричард Беллман в 1950-х предложил радикально иной взгляд на оптимизацию: не «найти всю траекторию сразу» (как в ПМП), а «решать задачу рекурсивно — справа налево». В основе лежит один глубокий принцип: оптимальный план «запоминает» только текущее состояние, а не как мы в него пришли. Это принцип оптимальности, и он порождает уравнение Беллмана — функциональное уравнение для оптимальной функции ценности. На этом принципе построена вся современная теория обучения с подкреплением, включая AlphaGo и ChatGPT (RLHF).

Принцип оптимальности Беллмана

Формулировка: «Оптимальная политика обладает тем свойством, что какие бы ни были начальное состояние и начальное решение, последующие решения должны составлять оптимальную политику относительно состояния, возникшего в результате первого решения.»

Проще: любая «хвостовая часть» оптимальной траектории сама оптимальна для соответствующей подзадачи.

Формально. Определим оптимальную функцию ценности: V*(x, t) = max_{u(·) на [t,T]} [∫_t^T L(x, u, s) ds + φ(x(T))], где x(t) = x.

Тогда для любого τ ∈ (t, T): V*(x, t) = max_{u(·) на [t, τ]} [∫_t^τ L(x, u, s) ds + V*(x(τ), τ)].

То есть: оптимизируем «короткое будущее» [t, τ], а дальше используем уже известную оптимальную ценность V*(·, τ).

Следствие. Оптимальное управление в момент s зависит только от текущего состояния x(s) и времени s, но не от истории — марковское свойство. Это огромное упрощение: мы ищем функцию u*(x, t), а не функционал u*(всей истории).

Уравнение Гамильтона-Якоби-Беллмана (HJB)

Возьмём принцип оптимальности с τ = t + Δt и устремим Δt → 0. Раскладывая в ряд Тейлора, получаем уравнение в частных производных:

−∂V/∂t = max_{u ∈ U} [L(x, u, t) + (∂V/∂x)ᵀ·f(x, u, t)].**

Терминальное условие: V*(x, T) = φ(x).

Это уравнение Гамильтона-Якоби-Беллмана (HJB). Расшифровка: левая часть — «темп изменения ценности по времени», правая — «оптимальная мгновенная скорость накопления полезности». Между ПМП и HJB есть глубокая связь: сопряжённая переменная ψ = ∂V*/∂x — теневая цена состояния.

Замечание. HJB — нелинейное уравнение в частных производных. Его решение, вообще говоря, не гладкое — допускает «изломы». Для строгого определения используют вязкостные решения (Crandall-Lions, 1980-е).

Верификационная теорема

Теорема: Если W(x, t) — гладкое решение HJB с W(x, T) = φ(x), и управление u*(x, t) = argmax [L + W_x·f] измеримо и допустимо, то W = V* (оптимальная функция ценности) и u* — оптимальная политика.

Это даёт практический рецепт: «угадай» функциональный вид V (например, квадратичный для LQR), подставь в HJB, получи ОДУ для коэффициентов, реши — и проверка готова.

Численный пример: LQR с конечным горизонтом

Задача: min ∫₀^T (x² + u²) dt + x(T)², ẋ = −x + u.

HJB: −V_t = min_u [x² + u² + V_x·(−x + u)]. Минимум по u: 2u + V_x = 0 → u* = −V_x/2.

Подставляя: −V_t = x² − V_x²/4 − x·V_x.

Пробный вид: V(x, t) = P(t)·x². Тогда V_x = 2P·x, V_t = Ṗ·x². Уравнение: −Ṗ·x² = x² − P²·x² − 2P·x² → Ṗ = P² + 2P − 1.

ОДУ для P с условием P(T) = 1 (из V(x, T) = x²). Уравнение Риккати в обратном времени!

Численное интегрирование (T = 1): P(0) ≈ 0.46. Оптимальное u*(x, t) = −P(t)·x — линейная обратная связь с переменным во времени коэффициентом.

При T → ∞: P(t) → P_∞ = (−2 + √8)/2 = √2 − 1 ≈ 0.414, что совпадает с решением алгебраического Риккати (бесконечный горизонт).

Связь с ПМП

При гладкой V*: ψ = ∂V*/∂x. Тогда HJB ↔ ПМП дают одинаковое оптимальное u*. Различие — в подходе:

• ПМП: краевая задача (forward для x, backward для ψ) — эффективно при малом числе состояний.
• HJB: PDE для V*(x, t) — эффективно при сложных ограничениях, но страдает от проклятия размерности при большом dim(x).

Реальные применения

• Финансы. Задача Мертона (оптимальное потребление и инвестиции) решена явно через HJB в 1969 г.: получена политика «инвестировать постоянную долю π* = (μ − r)/(σ²·γ) в рисковые активы».
• Управление запасами. Модели Скэрфа и Эрроу-Хэрриса используют HJB для нахождения оптимальной политики (s, S): «если запас < s, заказать до S».
• Реклама и маркетинг. Динамическое выделение бюджета между каналами рекламы — HJB-задача с эмпирически калиброванными моделями отклика.
• Reinforcement Learning. Уравнение Беллмана — основа Q-learning, DQN, AlphaGo. В каждом эпизоде агент обновляет V (или Q) согласно дискретной версии HJB.

Задание. Задача LQR с конечным горизонтом: min ∫₀^T (x² + u²) dt + x(T)², ẋ = −x + u, T = 2. (а) Запишите HJB. (б) Используйте пробный вид V(x, t) = P(t)·x²; найдите ОДУ для P(t) и численно решите назад во времени с шагом dt = 0.01. (в) Найдите оптимальное u*(x, t) = −P(t)·x. (г) Симулируйте x(t) при x(0) = 1 и сравните с разомкнутым решением u ≡ 0. (д) Подтвердите равенство ψ(t) = 2P(t)·x(t) с решением сопряжённой системы ПМП.