Марковские процессы принятия решений (MDP) в оптимизации

Математическая модель MDP задается кортежем $(S, A, P, R, \gamma)$, где $S$ — множество состояний системы, $A$ — множество возможных действий, $P$ — матрица вероятностей переходов (вероятность оказаться в новом состоянии зависит только от текущего состояния и действия, что определяет Марковское свойство системы), $R$ — функция мгновенного вознаграждения, и $\gamma$ — дисконтирующий множитель. Цель оптимизации — найти стратегию (политику) $\pi(s)$, представляющую собой правило выбора действия в каждом состоянии, которая максимизирует математическое ожидание дисконтированной суммы всех будущих вознаграждений.

Ядром теории MDP является уравнение Беллмана. Оно рекурсивно связывает ценность нахождения в определенном состоянии (Value Function) с ценностью состояний, в которые система может перейти на следующем шаге. Для нахождения оптимальной стратегии используются два классических алгоритма: итерация по ценности (Value Iteration) и итерация по политике (Policy Iteration). Оба алгоритма опираются на принцип сжимающих отображений в банаховом пространстве, что гарантирует строгую математическую сходимость к единственной глобально оптимальной функции ценности за полиномиальное время от числа состояний и действий.

Альтернативным и крайне элегантным методом решения MDP является сведение задачи к классическому линейному программированию. Переменными в такой задаче выступают "частоты посещения" пар (состояние, действие). Любая стационарная стратегия может быть найдена с помощью симплекс-метода или методов внутренней точки. Этот подход особенно ценен в задачах оптимизации с ограничениями (Constrained MDP), где, например, максимизируя прибыль, робот обязан удерживать риск повреждения оборудования ниже строго заданного порога вероятности.

Основной проблемой применения MDP на практике является "проклятие размерности": количество состояний растет экспоненциально с ростом числа параметров системы. В логистике, финансах (алготрейдинг) или играх (го, шахматы) точное решение уравнения Беллмана физически невозможно. На помощь приходят методы глубокого обучения с подкреплением (Deep RL), где нейронные сети используются для непрерывной аппроксимации функции ценности, перенося мощь теории марковских процессов на задачи оптимизации с бесконечным и непрерывным пространством состояний.

Список литературы:
1. Беллман Р. Динамическое программирование. — М.: ИЛ, 1960.
2. Саттон Р.С., Барто Э.Дж. Обучение с подкреплением: Введение. — М.: БИНОМ, 2011.
3. Путерман М.Л. Markov Decision Processes: Discrete Stochastic Dynamic Programming. — Wiley, 1994.