Обучение с подкреплением

Bellman Equations

Amazon управляет запасами на 185 складах по всему миру. Каждый день - миллионы решений: что заказать, сколько, когда. За всем этим стоит один математический принцип, сформулированный в 1953 году. Ричард Беллман работал в RAND Corporation над задачами военной логистики. Его уравнение оптимальности - рекурсивный принцип, из которого вырастают Dijkstra, Q-learning и AlphaGo.

**GPS-навигация** - алгоритм Дейкстры (частный случай Bellman equation) находит кратчайший путь в графе дорог за миллисекунды
**Управление запасами** - Dynamic Programming (основанный на Bellman equation) оптимизирует логистику Amazon и Walmart
**AlphaGo** - использует MCTS + нейросети для приближённого решения Bellman equation в пространстве 10^170 состояний

Ричард Беллман и проклятие размерности

В 1953 году Ричард Беллман работал в RAND Corporation и должен был обосновать свою работу перед Чарльзом Уилсоном - министром обороны, который распоряжался бюджетом ВВС, финансировавших RAND. Назвать «математическим программированием» было нельзя - Уилсон ненавидел слово «исследование». Беллман придумал «dynamic programming» - нейтральное название. Внутри скрывался принцип оптимальной подструктуры: оптимальное решение подзадач входит в оптимальное решение задачи целиком. Этот принцип позже лёг в основу всего RL.

Предварительные знания

Markov Decision Processes (MDP)

Value Function: ценность состояния

В лабиринте одни коридоры ведут к выходу, другие - в тупики. Если бы на каждом перекрёстке была табличка «до выхода осталось X шагов» - задача стала бы просто простой. **Value function** - именно такая табличка. Она говорит: **насколько хорошо находиться в данном состоянии**, если дальше действовать по политике π. GPS-навигатор тоже держит в памяти эту карту: для каждой точки дороги хранится «расстояние до цели».

**V^π(s) = E[G_t | s_t = s]** - ожидаемый cumulative discounted return, стартуя из состояния s и следуя политике π. Чем выше V(s), тем «ближе» состояние к большим наградам.

Посчитаем V(s) вручную для простого примера. Цепочка из 5 состояний, агент всегда идёт вправо:

Паттерн очевиден: ценность растёт по мере приближения к награде. Value function создаёт «градиент» - если агент всегда двигается в сторону бОльшей V(s), он придёт к цели. AlphaGo держал такую карту для 10^170 позиций го - не вручную, а через нейросеть.

Value function зависит от политики π. Одно и то же состояние может иметь высокую ценность при хорошей политике и низкую - при плохой. V^π(s) отвечает на вопрос: «насколько хорошо здесь, **если действовать по π**».

В цепочке S0->S1->S2->S3(goal, +1) с gamma=0.9, чему равна V(S1)?

Q-Function: ценность действия

Value function V(s) говорит, насколько хорошо **быть** в состоянии. Но агенту нужно **выбирать действия**. Для этого нужна другая функция: **Q(s, a)** - ценность **совершения действия a** в состоянии s. Именно на Q-function построены все современные model-free алгоритмы - от DQN до Atari-агентов DeepMind.

**Q^π(s, a) = E[G_t | s_t = s, a_t = a]** - ожидаемый return, если в состоянии s совершить действие a, а дальше следовать политике π. Q-function - «рейтинг» каждого действия в каждом состоянии.

Связь V и Q элегантна:

Зачем нужна Q-function, если есть V? **Q позволяет выбирать действия без знания модели среды.** Если есть V(s), чтобы выбрать лучшее действие, нужно знать переходы: «какое s' получится после действия a?» Но если есть Q(s,a) - просто берём argmax_a Q(s,a), и модель не нужна. Именно поэтому DQN от DeepMind научился играть в Atari без доступа к ROM-коду игры.

**Q-function - основа model-free RL.** Алгоритмы Q-learning и DQN обучают Q(s,a) из опыта, не зная модели среды. Именно поэтому Q-function так важна на практике.

Функция	Вход	Выход	Для чего нужна
V^pi(s)	Состояние s	Ценность состояния	Оценка «насколько хорошо здесь»
Q^pi(s,a)	Состояние s, действие a	Ценность действия	Выбор лучшего действия без модели
pi(a\|s)	Состояние s	Вероятность действия a	Стратегия агента

Почему Q(s,a) предпочтительнее V(s) для выбора действий в model-free RL?

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

В 1953 году математик Ричард Беллман сформулировал принцип, который стал основой всей теории RL: **оптимальная ценность состояния равна лучшему немедленному действию плюс дисконтированная ценность следующего состояния**. Алгоритм Дейкстры для shortest path - частный случай этого принципа. Управление запасами Amazon - прямое применение.

**Bellman Optimality Equation для V*:** V*(s) = max_a [ R(s,a) + gamma * sum_{s'} P(s'|s,a) * V*(s') ]. Словами: ценность лучшей стратегии из s = max по действиям (немедленная награда + gamma * средняя ценность следующего состояния).

Разберём каждый компонент:

Ключевая идея: уравнение **рекурсивно**. V*(s) определяется через V*(s'). Рекурсия позволяет декомпозировать сложную задачу оптимизации на серию простых «один шаг вперёд» решений. Это принцип оптимальной подструктуры - тот же, что в Dynamic Programming.

Уравнение Беллмана - это **система уравнений** (по одному на каждое состояние), а не одно уравнение. Для |S| состояний - |S| уравнений с |S| неизвестными. Для маленьких MDP можно решить аналитически. Для больших - нужны итерационные методы.

В детерминированной среде с gamma=0.9: из состояния S действие a=0 даёт reward=2 и ведёт в S' с V*(S')=5, действие a=1 даёт reward=4 и ведёт в S'' с V*(S'')=1. Чему равно V*(S)?

Value Iteration: решаем Bellman итеративно

Уравнение Беллмана рекурсивно - V*(s) зависит от V*(s'). Как решить систему, где всё зависит от всего? **Итеративно.** Начинаем с произвольных значений V(s) и многократно применяем уравнение Беллмана, пока значения не стабилизируются. Та же логика, что в Bellman-Ford для shortest paths: повторяй обновления, пока граф не успокоится.

**Value Iteration:** 1) Инициализируем V(s) = 0 для всех s. 2) Для каждого s обновляем: V(s) <- max_a [R(s,a) + gamma * sum P(s'|s,a) * V(s')]. 3) Повторяем, пока max|V_new(s) - V_old(s)| < threshold. Гарантированно сходится к V*!

Применим к конкретному gridworld 4x4. Цель - в правом нижнем углу (состояние 15), reward = +1. За каждый шаг - штраф -0.04 (мотивация двигаться).

Value iteration гарантированно сходится для gamma < 1 благодаря **теореме о сжимающем отображении** (contraction mapping theorem). Каждая итерация уменьшает максимальную ошибку как минимум в gamma раз. Для gamma=0.9 нужно ~50 итераций, для gamma=0.99 - ~500.

Метод	Знание модели	Гарантия оптимальности	Масштабируемость
Value Iteration	Нужна P(s'\|s,a)	Да (сходится к V*)	O(\|S\|^2 * \|A\|) на итерацию
Policy Iteration	Нужна P(s'\|s,a)	Да	Меньше итераций, дороже каждая
Q-Learning	НЕ нужна	Да (при бесконечном обучении)	Работает с опытом

Уравнение Беллмана - это алгоритм обучения, который агент использует для улучшения политики

Уравнение Беллмана - это математическое соотношение, описывающее свойства оптимальной value function. Value Iteration, Policy Iteration, Q-Learning - это алгоритмы, которые решают это уравнение разными способами.

Уравнение Беллмана не говорит, КАК найти V* - оно говорит, ЧЕМУ V* должна удовлетворять. Это как 'x^2 = 4' - уравнение задаёт условие, а x=2 - это решение. Value iteration - один способ решить. Q-learning (обучение из опыта) - другой. TD-learning - третий.

Что гарантирует сходимость Value Iteration?

Ключевые идеи

**V(s)** отвечает «насколько хорошо здесь быть», **Q(s,a)** - «насколько хорошо сделать это действие». Q позволяет выбирать действия без модели среды - отсюда model-free RL
**Bellman Optimality Equation** V*(s) = max_a [R(s,a) + gamma * sum P(s'|s,a) V*(s')] - рекурсивное определение оптимальной стратегии. Ценность позиции определяется ценностями соседей
**Value Iteration** - итеративный алгоритм решения Bellman equation. Начинаем с нулей, повторяем обновления, сходимся к V*. Гарантия - теорема о сжимающем отображении
**Уравнение - не алгоритм.** Bellman equation задаёт условие оптимальности. Value Iteration, Q-Learning, Policy Gradient - разные алгоритмы решения одного уравнения

Связанные темы

Bellman equations - мост между теорией MDP и практическими алгоритмами:

MDP: Марковские процессы — Bellman equation определён на MDP - использует S, A, P, R, gamma
Q-Learning и TD-методы — Model-free алгоритмы, решающие Bellman equation из опыта, без знания P(s'|s,a)
Dynamic Programming (алгоритмы) — Value Iteration - это dynamic programming. Принцип оптимальной подструктуры Беллмана лежит в основе DP

Вопросы для размышления

Почему Value Iteration требует знания модели (P(s'|s,a)), а Q-Learning - нет? Какой компонент Bellman equation «снимает» потребность в модели при использовании Q?
Value Iteration сходится к V* для ЛЮБОЙ инициализации. Интуитивно - почему? Подсказка: подумайте о том, что происходит с ошибкой на каждой итерации.
Если проектировать RL-агента для игры в шахматы (~10^47 состояний), можно ли применить Value Iteration напрямую? Какие подходы обходят проблему размера?

Связанные уроки

rl-02 — Bellman equation определён на MDP - использует S, A, P, R, gamma
rl-04 — Q-Learning и TD-методы решают Bellman equation из опыта без знания P(s'|s,a)
alg-21-dp — Value Iteration - это dynamic programming с принципом оптимальной подструктуры
alg-14-dijkstra — Dijkstra - частный случай Bellman equation для детерминированных графов
alg-15-bellman-ford — Bellman-Ford буквально реализует уравнение Беллмана на графе с отрицательными рёбрами
opt-01 — Выпуклая оптимизация даёт теоретические гарантии сходимости Value Iteration
calc-19-gradient