Dynamic Programming в RL

1957. Беллман в RAND Corporation решает как оптимально управлять ракетами. Никакого AI, никаких нейросетей - чистая математика оптимизации. Policy Iteration и Value Iteration, разработанные тогда для ракет, лежат в основе AlphaGo, ChatGPT RLHF и Tesla Autopilot сегодня. Понять Dynamic Programming - значит понять математику, на которой стоит современный RL.

• **AlphaGo**: Policy Iteration через MCTS + нейросетевая оценка. Известная модель среды (правила Го) делает возможным model-based планирование
• **Навигационные алгоритмы GPS**: Value Iteration на графе дорог. Кратчайший путь - частный случай оптимальной политики в MDP без стохастики
• **Управление энергосистемами**: Policy Iteration для оптимизации распределения нагрузки с известной моделью сети

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

В 1957 году Ричард Беллман опубликовал 'Dynamic Programming' в RAND Corporation. Принцип оптимальности Беллмана: оптимальная политика имеет то свойство, что каково бы ни было начальное состояние и начальное решение, последующие решения должны составлять оптимальную политику по отношению к состоянию, которое является результатом первого решения. В том же году Беллман формализовал value iteration и уравнение Беллмана. Беллман также ввёл термин 'curse of dimensionality' - проклятие размерности - описывая экспоненциальный рост сложности с числом переменных. В 1960 году Рональд Ховард ввёл policy iteration в книге 'Dynamic Programming and Markov Processes' - второй столп DP для RL. Это ограничение DP остаётся актуальным и сегодня.

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

• Уравнение Беллмана и value function V(s), Q(s,a)
• Марковский процесс принятия решений: состояния, действия, переходы P, награда R, gamma
• Итеративные алгоритмы и интуиция сходимости

• Bellman Equations
• Марковские процессы (MDP)

Policy Iteration: оцени и улучши

**1957. RAND Corporation.** Ричард Беллман решает задачу оптимального управления ракетами для ВВС США. Ключевое наблюдение: оптимальная политика может быть найдена через чередование двух шагов - оценки текущей политики и её улучшения. Это Policy Iteration - первый точный алгоритм для MDP, гарантированно сходящийся к оптимуму.

**Policy Iteration - два чередующихся шага:** 1. **Policy Evaluation** - вычислить V^pi(s) для текущей политики pi. Решаем систему линейных уравнений итеративно: пока |V_new - V_old| > theta. 2. **Policy Improvement** - улучшить политику: для каждого состояния выбрать действие, максимизирующее Q^pi(s,a). Алгоритм сходится за конечное число итераций (число возможных политик = |A|^|S| конечно). Обычно нужно 5-20 итераций даже для больших MDP.

**Policy Evaluation - дорогая операция.** Полное вычисление V^pi требует многих проходов по всем состояниям до сходимости. Modified Policy Iteration делает только k шагов evaluation (k=1 - это Value Iteration). На практике Modified Policy Iteration с k=3-10 часто быстрее обоих крайних вариантов.

Value Iteration: прямая оптимизация

Policy Iteration чередует два шага. Value Iteration предлагает: а зачем вообще отдельно оценивать политику? Давайте сразу применять оператор оптимальности Беллмана к value function, не заботясь о текущей политике. Математически это одна итерация Policy Evaluation + Policy Improvement, повторяемая до сходимости.

**Когда Value Iteration лучше Policy Iteration?** Когда пространство состояний большое: Policy Evaluation решает систему |S| уравнений - это O(|S|^3) для точного решения. Value Iteration делает один sweep за O(|S| * |A|). При |S| = 10^6 Policy Evaluation просто невозможна, Value Iteration - стандартный выбор.

Сходимость: математические гарантии

Почему мы вообще знаем, что эти алгоритмы работают? Математика за сходимостью DP в RL - это теорема Банаха о неподвижной точке для оператора Беллмана. Понимание этой теоремы объясняет не только почему DP работает, но и почему Q-Learning и TD-методы работают в model-free контексте.

**Оператор Беллмана T:** (TV)(s) = max_a SUM_s' P(s'|s,a) [R(s,a,s') + gamma * V(s')] **Свойство 1: монотонность.** Если V(s) <= U(s) для всех s, то TV(s) <= TU(s). **Свойство 2: сжатие.** ||TV - TU||_inf <= gamma * ||V - U||_inf **Следствие:** T имеет единственную неподвижную точку V*, и итерации V_{k+1} = TV_k сходятся к V* со скоростью gamma^k * ||V_0 - V*||.

**Критерий остановки theta:** Value Iteration останавливается когда max_s |V_new(s) - V_old(s)| < theta. Это гарантирует что **текущая ошибка в политике** (не в V!) ограничена 2*gamma*theta/(1-gamma). При theta=1e-6 и gamma=0.9 - ошибка политики <= 1.8e-5. Слишком малый theta = лишние итерации. Слишком большой - неоптимальная политика.

Model-based RL: когда нужна модель

**DP-методы (Policy Iteration, Value Iteration) - model-based: требуют знания P(s'|s,a) и R(s,a,s').** В реальных задачах модель редко известна заранее. Но model-based подход остаётся важным по двум причинам: 1) иногда модель можно построить (Dyna-Q), 2) он служит теоретической базой для model-free методов.

**AlphaGo использует model-based RL.** Модель среды (игра в Го) известна полностью - правила детерминированы. Policy Iteration (Monte Carlo Tree Search) в каждой позиции планирует наперёд, используя нейросети для оценки позиции (value network) и выбора ходов (policy network). Это комбинация model-based планирования и model-free обучения из самоигры.

Dynamic Programming в экосистеме RL

DP - это точное ядро на основе модели. Каждый последующий model-free метод - приближение к тем же обновлениям Беллмана:

• Bellman Equations — Алгоритмы DP - это итеративные процедуры, решающие уравнение оптимальности Беллмана
• Policy Gradient — Контраст: policy gradient оптимизирует политику напрямую без модели P, тогда как DP она нужна
• TD Learning и Q-Learning — TD-методы заменяют полные проходы DP по известной модели на sampled bootstrapped обновления
• Марковские процессы — DP предполагает, что весь MDP (P, R) известен - именно эту модель используют алгоритмы

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

• **Policy Iteration** чередует Policy Evaluation (вычислить V^pi для текущей pi) и Policy Improvement (выбрать лучшее действие по Q). Сходится за конечное число итераций. Медленная evaluation - узкое место
• **Value Iteration** применяет оператор Беллмана напрямую к V без явной политики. Один дешёвый sweep вместо дорогой evaluation. Сходится асимптотически - нужен порог theta
• **Скорость сходимости** = gamma^k: высокий gamma -> медленная сходимость. Критерий остановки theta определяет ошибку политики через 2*gamma*theta/(1-gamma)
• **Model-based RL** требует P и R, но даёт точные ответы. Dyna-Q строит модель из опыта и планирует n_planning симулированных шагов - ускорение без дополнительных реальных взаимодействий

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

• Policy Iteration сходится за конечное число итераций, Value Iteration - асимптотически. Почему тогда на практике Value Iteration часто предпочтительнее?
• Dyna-Q строит модель среды из накопленного опыта. Что произойдёт если среда изменится (concept drift)? Как алгоритм должен адаптироваться?
• AlphaGo знает модель среды (правила Го) и использует MCTS как Policy Iteration. Почему в большинстве реальных RL задач (управление роботом, торговля) model-based подход неприменим?

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

• rl-03
• rl-05
• aut-04-mdp
• rl-06
• ml-49-q-learning
• alg-21-dp