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

Введение

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

Компоненты MDP

MDP обычно определяется следующими компонентами:

Состояния ((S))

Набор всех возможных состояний (S) представляет каждую мыслимую ситуацию, в которой может оказаться агент. Каждое состояние содержит всю информацию, необходимую для принятия решения. - Пример. В сфере торговли акциями состояние может быть представлено текущими ценами на различные акции, доступными средствами и существующими активами в портфеле.

Действия ((A))

Набор всех возможных действий (A) включает в себя все решения, которые агент может принять в любом состоянии. - Пример. В одной и той же среде торговли акциями действия могут включать покупку, продажу или удержание акций.

Вероятности перехода ((T) или (P))

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

Награды ((R))

Функция вознаграждения ( R(s,a,s’) ) определяет немедленное вознаграждение, полученное после перехода из состояния ( s ) в состояние ( s’ ) вследствие действия ( a ). Количественно это представляет собой выгоду от совершения определенного действия в данном состоянии. - Пример. В торговой среде вознаграждением может быть прибыль или убыток в результате покупки или продажи акций.

Формальное определение

MDP можно формально определить как кортеж ( (S, A, P, R, \gamma) ), где: - ( S ) - пространство состояний - ( A ) - пространство действий - ( P ) - функция вероятности перехода - ( R ) - функция вознаграждения - ( \gamma ) - коэффициент дисконтирования, определяющий текущую стоимость будущего вознаграждения

Политики

Политика ( \pi ) — это стратегия, используемая агентом, определяющая действие, которое необходимо предпринять в каждом состоянии. Политики могут быть детерминированными (( \pi(s) = a )) или стохастическими (( \pi(a|s) )), где последнее представляет собой распределение вероятностей по действиям в данном состоянии.

Оптимальная политика

Целью MDP является нахождение оптимальной политики ( \pi^* ), которая максимизирует ожидаемое совокупное вознаграждение с течением времени. Это часто формализуется с помощью функции значения или функции действия-ценности.

Функции значений

Функции значений используются для оценки долгосрочных выгод от состояний или пар «состояние-действие» в рамках заданной политики. Два основных типа функций значений:

Функция значения состояния (( V^\pi(s) ))

Функция значения состояния ( V^\pi(s) ) представляет собой ожидаемую совокупную награду за запуск в состоянии ( s ) и соблюдение политики ( \pi ).

[ V^\pi(s) = \mathbb{E}\pi \left[ \sum{t=0}^{\infty} \gamma^t R(s_t, a_t, s_{t+1}) \mid s_0 = s \right] ]

Функция-значение (( Q^\pi(s, a) ))

Функция значения действия ( Q^\pi(s, a) ) представляет собой ожидаемое совокупное вознаграждение за запуск в состоянии ( s ), выполнение действия ( a ) и последующее соблюдение политики ( \pi ).

[ Q^\pi(s, a) = \mathbb{E}\pi \left[ \sum{t=0}^{\infty} \gamma^t R(s_t, a_t, s_{t+1}) \mid s_0 = s, a_0 = a \right] ]

Уравнения Беллмана

Уравнения Беллмана обеспечивают рекурсивные соотношения для функций значения, необходимые для решения MDP.

Уравнение ожидания Беллмана для ( V^\pi )

[ V^\pi(s) = \sum_{a \in A} \pi(a s) \left[ R(s, a) + \gamma \sum_{s’ \in S} P(s’ s, a) V^\pi(s’) \right] ]

Уравнение ожидания Беллмана для ( Q^\pi )

[ Q^\pi(s, a) = R(s, a) + \gamma \sum_{s’ \in S} P(s’ s, a) \sum_{a’ \in A} \pi(a’ s’) Q^\pi(s’, a’) ]

Методы решения

Существует несколько методов поиска оптимальных политик в MDP, которые подразделяются на методы динамического программирования, Монте-Карло и методы временных разностей.

Динамическое программирование

Методы динамического программирования используют уравнения Беллмана для итеративного улучшения оценок стоимости и политики. Ключевые алгоритмы включают в себя:

Итерация значения

Итерация значения неоднократно обновляет функцию значения состояния до тех пор, пока она не сойдется к функции оптимального значения.

[ V_{k+1}(s) = \max_{a \in A} \left[ R(s, a) + \gamma \sum_{s’ \in S} P(s’ s, a) V_k(s’) \right] ]

Итерация политики

Итерация политики чередуется между оценкой политики (оценкой функции значения для данной политики) и улучшением политики (создание лучшей политики на основе функции текущей стоимости).

  1. Оценка политики: Определите ( V^\pi(s) ) для текущей политики ( \pi ). 2. Улучшение политики: обновите политику ( \pi ) с помощью функции обновленного значения.
[ \pi’(s) = \arg\max_{a \in A} \left[ R(s, a) + \gamma \sum_{s’ \in S} P(s’ s, a) V^\pi(s’) \right] ]

Методы Монте-Карло

Методы Монте-Карло оценивают функции значения на основе выборочных эпизодов из МДП. Эти методы не требуют знания вероятностей перехода и используются в контекстах, не связанных с моделями.

MC при первом посещении

При первом посещении Монте-Карло обновляет функцию значения на основе первого появления каждого состояния или пары состояние-действие в эпизоде.

MC при каждом посещении

При каждом посещении Монте-Карло обновляет функцию значения на основе каждого появления каждого состояния или пары состояние-действие в эпизоде.

Обучение временной разности (TD)

Методы временной разницы сочетают в себе идеи динамического программирования и методы Монте-Карло. Обучение TD обновляет оценки значений на основе разницы (временной разницы) между последовательными оценками значений.

TD(0)

TD(0) — это самая простая форма, обновляющая функцию значения с использованием одношагового просмотра вперед.

[ V(s_t) \leftarrow V(s_t) + \alpha \left[ R_{t+1} + \gamma V(s_{t+1}) - V(s_t) \right] ]

Q-Learning

Q-Learning — это алгоритм управления TD вне политики, который изучает оптимальную политику независимо от действий агента.

[ Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ R_{t+1} + \gamma \max_{a} Q(s_{t+1}, a) - Q(s_t, a_t) \right] ]

SARSA

SARSA - это алгоритм управления TD на основе политики, который обновляет функцию действия-значения на основе действий агента в соответствии с текущей политикой.

[ Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha \left[ R_{t+1} + \gamma Q(s_{t+1}, a_{t+1}) - Q(s_t, a_t) \right] ]

Приложения в алгоритмическом трейдинге

MDP имеют важное применение в алгоритмической торговле, где агенты должны принимать последовательные решения в условиях неопределенности, чтобы максимизировать прибыль.

Оптимальное исполнение

Одним из ключевых приложений является оптимальное исполнение сделок, при котором агент определяет лучшее время и объемы для торговли, чтобы минимизировать транзакционные издержки и влияние на рынок.

Управление портфелем

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

Создание рынка

Агенты могут использовать MDP для разработки оптимальных стратегий создания рынка, устанавливая спреды спроса и предложения на основе вероятных будущих движений цен, чтобы максимизировать прибыль от спреда, одновременно управляя риском запасов.

Обучение с подкреплением в трейдинге

Обучение с подкреплением, охватывающее множество методов решения MDP, используется для разработки сложных торговых алгоритмов. Такие платформы, как Alpaca и QuantConnect, предоставляют среду для тестирования и внедрения этих стратегий.

Заключение

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