Markov Decision Process (MDP)

Марковский процесс принятия решений (MDP) — это математическая модель последовательной задачи принятия решений: агент наблюдает состояние, выбирает действие, получает вознаграждение и переходит в следующее состояние, зависящее отчасти от его выбора, а отчасти от случайности. Формально MDP состоит из множества состояний, множества действий, вероятностей перехода P(s′ | s, a), функции вознаграждения R(s, a) и, как правило, коэффициента дисконтирования γ от 0 до 1. Решить MDP — значит найти политику, то есть правило выбора действия в каждом состоянии, которая максимизирует ожидаемую дисконтированную сумму будущих вознаграждений. MDP возникли в исследовании операций в 1950-х годах; методы их решения обеспечило динамическое программирование Ричарда Беллмана. Сегодня MDP — это стандартная постановка задачи для обучения с подкреплением (RL).

Свойство Маркова#

Определяющее допущение — свойство Маркова: следующее состояние и вознаграждение зависят только от текущего состояния и действия, а не от пути, который привёл к ним. Поэтому состояние полностью описывает всё, что имеет значение для агента. Один кадр камеры нарушает это допущение для движущегося объекта: на нём видна позиция, но не скорость. Поэтому DQN от DeepMind, игравшая в Atari, подавала на вход сети последние четыре кадра вместе, чтобы сеть могла видеть движение.

Если агент не может наблюдать полное состояние, например робот из-за шумных или закрытых датчиков, задача становится частично наблюдаемым MDP (POMDP). Тогда агент действует на основе оценки состояния, которую поддерживает с помощью фильтра или рекуррентной сети, а не самого состояния.

Компоненты MDP#

• Состояния: ситуации, в которых может оказаться агент, например углы суставов робота и положение объекта, к которому он тянется.
• Действия: варианты выбора в каждом состоянии. Пространство действий может быть дискретным (повернуть налево, повернуть направо) или непрерывным (угол поворота руля в градусах).
• Вероятности перехода: вероятность каждого следующего состояния после действия, учитывающая пробуксовку колёс, поведение других водителей и любые другие источники случайности.
• Вознаграждения: непосредственная числовая оценка перехода. Постановка задачи зависит от выбранных разработчиком вознаграждений; неудачно заданные вознаграждения могут привести к взлому системы вознаграждений.
• Коэффициент дисконтирования: показывает, насколько будущие вознаграждения важны по сравнению с немедленными. При γ = 0.9 вознаграждение через десять шагов стоит 0.9¹⁰ ≈ 0.35 от такого же вознаграждения сейчас.

На каждом временном шаге это взаимодействие повторяется до завершения эпизода:

Решение MDP#

Ценность состояния — это ожидаемая суммарная награда при следовании политике, а оптимальные значения удовлетворяют уравнению Беллмана: ценность каждого состояния равна непосредственному вознаграждению за лучшее действие плюс дисконтированная сумма ценностей состояний, в которые оно ведёт, взвешенная по вероятностям. Если вероятности перехода и вознаграждения известны, это уравнение решается напрямую с помощью динамического программирования. Итерация по значениям (Беллман, 1957) многократно применяет это уравнение, пока значения не перестанут меняться; итерация по политикам (Ховард, 1960) чередует оценку политики и её улучшение.

В этом примере NumPy выполняет итерацию по значениям для робота-сборщика вторсырья из книги Саттона и Барто Обучение с подкреплением: введение: робот должен выбирать между поиском банок, ожиданием и подзарядкой при высоком или низком заряде батареи.

import numpy as np

# MDP робота-сборщика вторсырья: состояния 0 = высокий заряд, 1 = низкий заряд; действия 0 = искать, 1 = ждать, 2 = подзарядить
gamma = 0.9  # коэффициент дисконтирования
P = np.zeros((2, 3, 2))  # P[s, a, s'] = вероятность попасть в s' после выполнения a в состоянии s
P[0, 0] = [0.7, 0.3]  # поиск при высоком заряде может разрядить батарею до низкого уровня
P[1, 0] = [0.4, 0.6]  # поиск при низком заряде может полностью разрядить батарею (робота спасают и подзаряжают)
P[:, 1] = np.eye(2)  # ожидание сохраняет уровень заряда батареи
P[:, 2] = [1.0, 0.0]  # подзарядка всегда восстанавливает высокий заряд батареи
R = np.array([[2.0, 1.0, 0.0], [0.0, 1.0, 0.0]])  # ожидаемое R[s, a]; поиск при низком заряде: 0.6 * 2 + 0.4 * -3 = 0

# Итерация по значениям: применяй обновление оптимальности Беллмана, пока значения не перестанут меняться
V = np.zeros(2)
for _ in range(500):
    Q = R + gamma * P @ V  # ценность каждого действия в каждом состоянии
    V = Q.max(axis=1)

actions = ["search", "wait", "recharge"]
print("Optimal values:", V.round(2))
print("Optimal policy:", {s: actions[a] for s, a in zip(["high", "low"], Q.argmax(axis=1))})

Результат — ценности 15.75 для высокого заряда и 14.17 для низкого, а также политика, согласно которой при высоком заряде нужно искать, а при низком — подзаряжаться. Риск в 40% получить штраф −3 за спасение делает поиск при низком заряде менее выгодным, чем подзарядку.

Если вероятности перехода неизвестны, обучение с подкреплением оценивает те же значения на основе опыта. Q-learning обновляет ценности действий на основе выборочных переходов, методы градиента политики напрямую корректируют политику, а глубокое обучение с подкреплением использует нейронные сети, когда пространство состояний слишком велико для перечисления. Алгоритмы планирования, например поиск по дереву Монте-Карло, решают огромные MDP во время работы, моделируя только те будущие состояния, в которые можно попасть из текущего.

MDP и родственные модели#

• Марковская цепь: последовательность случайных состояний без действий и вознаграждений. MDP добавляет варианты выбора и цель.
• Скрытая марковская модель (HMM): марковская цепь, состояния которой наблюдаются только через зашумлённые сигналы. POMDP соотносится с MDP таким же образом.
• Многорукий бандит: MDP с одним состоянием, где результат каждого действия не зависит от предыдущих.
• Обучение с подкреплением: семейство методов, которые учатся эффективно действовать в MDP в результате взаимодействия, не получая заданных вероятностей перехода.

Применение#

• Робототехника и управление: захват объектов, ходьбу и навигацию формулируют как MDP; политики для них часто обучают в симуляции. При управлении на основе камеры детектор, например Ultralytics YOLO26, может предоставлять состояние, преобразуя каждый кадр в короткий список классов объектов и координат рамок. Такой вход для политики намного компактнее исходных пикселей.
• Обучение языковых моделей: RLHF и RLVR рассматривают генерацию текста как MDP, где состояние — это запрос и уже сгенерированные токены, действие — следующий токен, а вознаграждение поступает после завершения ответа.
• Исследование операций: пополнение запасов, техническое обслуживание оборудования и динамическое ценообразование — классические задачи MDP. Рональд Ховард разработал итерацию по политикам, оптимизируя рассылку каталогов Sears.