Марковский процесс принятия решений

Цели урока

• Понимать отличие MDP от цепей Маркова: агент влияет на переходы через действия
• Знать компоненты MDP: S, A, P, R, gamma и роль дисконт-фактора
• Понимать уравнение оптимальности Беллмана и почему оно решается итеративно
• Различать Value Iteration, Policy Iteration и Q-Learning по применимости

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

• Цепи Маркова (aut-02): матрицы переходов, стационарные распределения
• HMM (aut-03): скрытые состояния, алгоритм Витерби
• Базовое понимание вероятности и математического ожидания

2016. AlphaGo сыграл 40 миллионов партий и победил чемпиона мира 4:1. Каждый ход - MDP. Каждое решение ChatGPT - MDP. Этот урок - теоретическая база всего современного RL.

• **AlphaGo (DeepMind, 2016)** - победил чемпиона мира Ли Седоля 4:1, сыграв 40 млн партий через self-play и MDP
• **DQN (DeepMind, 2013)** - Q-Learning + нейросеть, прошёл 49 игр Atari на уровне человека без знания правил
• **ChatGPT RLHF** - обучение через reward model это MDP: модель как агент, контекст как состояние, токены как действия
• **Tesla Autopilot** - управление автомобилем в реальном времени через policy learned from MDP
• **Рекомендательные системы (YouTube, Netflix)** - какой контент показать следующим: MDP где состояние = история пользователя

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

В 1957 году Ричард Беллман, работая в RAND Corporation над задачами оптимизации для ВВС США, опубликовал книгу 'Dynamic Programming'. Он описал рекурсивное разложение задачи оптимизации - принцип оптимальности Беллмана - и сам же назвал главную проблему 'curse of dimensionality': если у системы 10 параметров с 10 значениями каждый, пространство состояний 10^10. Эта проблема актуальна и сегодня - именно против неё работают нейросетевые аппроксиматоры в Deep RL.

От наблюдателя к агенту

**2016. DeepMind AlphaGo сыграл 40 миллионов партий в го против самого себя и победил чемпиона мира Ли Седоля 4:1.** Ли Седоль сказал после матча: «Я думал, что всегда смогу выиграть хотя бы одну партию». Не смог. Цепи Маркова и HMM описывали мир и угадывали скрытые состояния. AlphaGo делал другое - в каждой позиции он выбирал ход. Это суть MDP: не наблюдение, а принятие решений.

**MDP (Markov Decision Process)** - пятёрка (S, A, P, R, gamma): S - множество состояний, A - множество действий, P(s'|s,a) - функция перехода (зависит от действия!), R(s,a,s') - функция награды, gamma - дисконт-фактор. В цепи Маркова переход P(s'|s) зависит только от состояния. В MDP - от состояния и выбранного действия.

В каждом шаге: агент наблюдает состояние s, выбирает действие a, среда переходит в s' с вероятностью P(s'|s,a) и выдаёт награду R(s,a,s'). Задача - найти стратегию выбора действий, максимизирующую суммарную накопленную награду.

Политика и ценность состояний

**Политика (policy) pi** - функция, определяющая какое действие выбирать в каждом состоянии. Детерминированная политика: pi(s) = a. Стохастическая политика: pi(a|s) = P(A=a|S=s). Цель MDP - найти оптимальную политику pi*, максимизирующую ожидаемую суммарную награду.

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

**Value Function V^pi(s)** - ожидаемая суммарная дисконтированная награда при старте из состояния s и следовании политике pi. Дисконт-фактор gamma задаёт горизонт планирования: при gamma близком к 0 агент жадный (берёт немедленную награду), при gamma близком к 1 - дальновидный (оптимизирует долгосрочный результат).

При gamma = 0.99 награда через 100 шагов весит 0.99^100 = 0.37 от немедленной. Через 500 шагов - 0.006. Gamma контролирует насколько агент планирует вперёд.

Уравнение Беллмана и Q-функция

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

**Уравнение оптимальности Беллмана для V**: V*(s) = max_a SUM_{s'} P(s'|s,a) * [R(s,a,s') + gamma * V*(s')]. Расшифровка: выбрать лучшее действие (max_a), усреднить по возможным переходам (SUM), получить немедленную награду плюс дисконтированную ценность следующего состояния.

**Q-функция Q^pi(s,a)** - ценность выбора конкретного действия a в состоянии s при следовании политике pi далее. Связь с V: V^pi(s) = SUM_a pi(a|s) * Q^pi(s,a). Оптимальная политика проста, если известна Q*: pi*(s) = argmax_a Q*(s,a). Именно поэтому Q-Learning стал основой современного RL.

Уравнение Беллмана - это система из |S| уравнений с |S| неизвестными. V*(s) зависит от V*(s'), которое зависит от V*(s''). Прямого решения нет - нужна итерация. Беллман сам назвал эту проблему 'проклятием размерности': при 10 состояниях и 10 признаках пространство состояний 10^10.

Алгоритмы решения MDP

**Три классических подхода к решению MDP - каждый применяется в современных системах.** Value Iteration - основа планирования в робототехнике. Policy Iteration - используется в AlphaGo. Q-Learning без модели мира - сердце DQN от DeepMind (2013), который впервые прошёл 49 игр Atari на уровне человека.

**Exploration vs Exploitation:** Q-Learning использует epsilon-greedy стратегию: с вероятностью epsilon выбирается случайное действие (exploration), с вероятностью 1-epsilon - лучшее известное (exploitation). Без exploration агент застревает в локальном оптимуме. DQN от DeepMind начинал с epsilon=1.0 и постепенно снижал до 0.1.

**Ограничения MDP:** 1. полная наблюдаемость - агент точно знает состояние. Когда агент не уверен в состоянии - нужен POMDP. 2. марковское свойство - будущее зависит только от текущего состояния. 3. дискретные пространства состояний и действий. Для непрерывных (управление роботом) - нейросети аппроксимируют V и Q (Deep RL).

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

• Задача управления роботом-курьером в городе: состояние - позиция + заряд батареи + текущий заказ, действия - движение в 4 направлениях + зарядка + принятие заказа. Как сформулировать функцию награды R, чтобы робот не жертвовал безопасностью ради скорости доставки?

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

• aut-03-hmm
• rl-01
• rl-04
• aut-05-pomdp
• ml-48-rl-intro
• alg-21-dp