Глава 311: Поиск по дереву Монте-Карло для трейдинга

Введение

Поиск по дереву Монте-Карло (MCTS) — это мощный алгоритм принятия решений, который сочетает поиск по дереву со случайной выборкой для навигации в огромных пространствах решений. Первоначально ставший популярным благодаря успехам в игре Го — в частности, в AlphaGo и AlphaZero от DeepMind — MCTS зарекомендовал себя как универсальный алгоритм планирования, способный решать задачи с огромной комбинаторной сложностью.

Трейдинг является естественной областью применения MCTS. В каждый момент времени трейдер сталкивается с деревом решений: купить, продать, удержать, изменить размер позиции, установить стоп-лоссы или выбрать среди нескольких активов. Каждое действие ведёт к новому состоянию рынка, которое, в свою очередь, представляет новый набор решений. Глубина этого дерева растёт экспоненциально с горизонтом торговли, что делает полный перебор невозможным. MCTS решает эту проблему, интеллектуально выбирая наиболее перспективные ветви, сохраняя при этом исследование альтернатив.

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

Многоэтапного исполнения ордеров: Планирование последовательности сделок для минимизации влияния на рынок
Ребалансировки портфеля: Решения о том, какими активами торговать и в каком порядке
Выбора опционных стратегий: Оценка сложных многоуровневых стратегий
Принятия решений с учётом рисков: Баланс между ожидаемой доходностью и нисходящим риском

Ключевое преимущество MCTS перед более простыми подходами — это способность заглядывать на несколько шагов вперёд, учитывать последовательную природу торговых решений и адаптировать поиск, фокусируясь на наиболее релевантных частях пространства решений.

Математические основы

Алгоритм UCT

Ядром современного MCTS является алгоритм UCT (Upper Confidence bounds applied to Trees). UCT использует формулу UCB1 для балансировки эксплуатации (выбора действий с высокой оценочной ценностью) и исследования (проб менее посещённых действий):

$$UCT(s, a) = \bar{Q}(s, a) + c \cdot \sqrt{\frac{\ln N(s)}{N(s, a)}}$$

Где:

$\bar{Q}(s, a)$ — средняя награда от выполнения действия $a$ в состоянии $s$
$N(s)$ — количество посещений состояния $s$
$N(s, a)$ — количество раз, когда действие $a$ было выполнено из состояния $s$
$c$ — константа исследования (обычно $\sqrt{2}$ для теоретической оптимальности, настраивается эмпирически на практике)

Первый член обеспечивает эксплуатацию — предпочтение действий с исторически высокими наградами. Второй член обеспечивает исследование — предпочтение действий, которые были опробованы меньше раз, при этом логарифмический счётчик родителя гарантирует, что исследование уменьшается, но никогда не прекращается.

Четыре фазы MCTS

MCTS работает через четыре итеративные фазы:

1. Выбор (Selection)

Начиная с корневого узла, алгоритм проходит по дереву, выбирая потомков согласно формуле UCT, пока не достигнет листового узла (узла, имеющего нераскрытые действия или не посещавшегося):

$$a^* = \arg\max_{a \in A(s)} \left[ \bar{Q}(s, a) + c \cdot \sqrt{\frac{\ln N(s)}{N(s, a)}} \right]$$

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

2. Расширение (Expansion)

В листовом узле к дереву добавляются один или несколько дочерних узлов, соответствующих неопробованным действиям. В контексте трейдинга это означает рассмотрение новых действий (например, «купить 10 единиц», «продать 5 единиц», «удержать»), которые не были исследованы из текущего состояния.

3. Моделирование (Simulation / Rollout)

Из только что расширенного узла запускается моделирование до терминального состояния или фиксированного горизонта с использованием политики развёртки (часто случайной или основанной на простых эвристиках). Моделирование даёт сигнал награды:

$$R = \sum_{t=0}^{T} \gamma^t r_t$$

Где $\gamma$ — коэффициент дисконтирования, а $r_t$ — награда на шаге $t$. В трейдинге это может быть кумулятивный PnL за горизонт моделирования, доходность с поправкой на риск (коэффициент Шарпа) или пользовательская целевая функция.

4. Обратное распространение (Backpropagation)

Результат моделирования распространяется обратно по дереву, обновляя счётчики посещений и оценки ценности для каждого узла на пути:

$$N(s, a) \leftarrow N(s, a) + 1$$ $$Q(s, a) \leftarrow Q(s, a) + R$$ $$\bar{Q}(s, a) = \frac{Q(s, a)}{N(s, a)}$$

После многих итераций счётчики посещений сходятся, и наиболее посещаемое действие из корня выбирается как лучшее решение.

Свойства сходимости

Доказано, что MCTS с UCT сходится к оптимальной политике при стремлении числа итераций к бесконечности. На практике даже умеренное количество итераций (1 000–10 000) часто даёт хорошие результаты. Член исследования гарантирует, что ни одна часть дерева не будет навсегда проигнорирована, в то время как эксплуатация фокусирует вычислительные ресурсы на наиболее перспективных ветвях.

Применение в трейдинге

Многоэтапное исполнение ордеров

При исполнении крупного ордера трейдер должен решить, как разделить его по временным шагам для минимизации влияния на рынок. MCTS может планировать оптимальное исполнение, моделируя:

Состояние: Текущая позиция, оставшийся объём ордера, недавняя траектория цены, глубина книги ордеров
Действия: Размеры исполняемых частей (например, 10%, 20%, 50% от оставшегося) или ожидание
Награда: Отрицательная стоимость проскальзывания с штрафами за неисполненные части

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

Решения по ребалансировке портфеля

Ребалансировка портфеля включает множество коррелированных решений: какими активами торговать, в каком порядке и в каком объёме. MCTS естественно справляется с этим:

Состояние: Текущие веса портфеля, целевые веса, транзакционные издержки, рыночные условия
Действия: Торговать конкретным активом в направлении цели, пропустить или скорректировать цель
Награда: Снижение ошибки отслеживания минус транзакционные издержки

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

Планирование с учётом рисков

Модифицируя оценку развёртки, MCTS может учитывать соображения риска:

$$R_{risk} = \mathbb{E}[R] - \lambda \cdot \text{CVaR}_\alpha(R)$$

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

MCTS в стиле AlphaZero с обученными сетями

Подход AlphaZero усиливает MCTS двумя нейронными сетями:

Сеть политики $p_\theta(a|s)$: Предоставляет априорные вероятности для действий, заменяя равномерное априорное распределение в стандартном MCTS. Это направляет поиск к перспективным действиям с самого начала.
Сеть ценности $v_\theta(s)$: Оценивает ожидаемый результат из состояния $s$, заменяя или дополняя случайные развёртки. Это значительно повышает качество моделирования.

Модифицированная формула UCT становится:

$$UCT_{AZ}(s, a) = \bar{Q}(s, a) + c \cdot p_\theta(a|s) \cdot \frac{\sqrt{N(s)}}{1 + N(s, a)}$$

Для трейдинга сеть политики может быть обучена на исторических данных для отражения распространённых торговых паттернов, в то время как сеть ценности учится предсказывать будущую доходность с поправкой на риск. Сети обучаются итеративно: MCTS генерирует обучающие данные через самоигру, сети обновляются, а улучшенные сети направляют лучший поиск MCTS.

Этот подход особенно мощен, потому что:

Сеть политики уменьшает коэффициент ветвления, фокусируясь на правдоподобных действиях
Сеть ценности устраняет необходимость в случайных развёртках, которые зашумлены на финансовых рынках
Вся система улучшается через самоигру без необходимости размеченных данных

Реализация на Rust

Реализация в rust/src/lib.rs предоставляет полный фреймворк MCTS для трейдинга:

Основные компоненты

TradingState: Представляет текущее состояние рынка, включая историю цен, позицию, баланс и счётчик шагов
TradingAction: Перечисление возможных действий (Buy, Sell, Hold) с настраиваемыми размерами позиций
MCTSNode: Узел дерева, хранящий счётчики посещений, накопленную ценность, потомков, выполненное действие и ссылку на родителя
MCTS: Основной поисковый движок с настраиваемой константой исследования и числом итераций

Ключевые возможности

Выбор UCT: Реализует формулу UCB1 для обхода дерева с настраиваемым параметром исследования
Расширение на основе состояний: Генерирует дочерние узлы для всех допустимых действий из текущего торгового состояния
Случайная развёртка: Моделирует вперёд от листовых узлов с использованием случайного выбора действий
Обратное распространение: Обновляет оценки ценности вдоль всего пути от листа к корню
Интеграция с Bybit: Получает реальные данные BTCUSDT kline через публичный API Bybit

Использование

use monte_carlo_tree_search::{MCTS, TradingState};

let prices = vec![50000.0, 50100.0, 49900.0, 50200.0, 50050.0];
let state = TradingState::new(prices, 10000.0);
let mut mcts = MCTS::new(1.414, 1000);
let best_action = mcts.search(&state);

Пример в rust/examples/trading_example.rs демонстрирует получение реальных данных с Bybit и запуск MCTS для определения оптимальных торговых действий.

Интеграция данных Bybit

Реализация подключается к публичному REST API Bybit для получения исторических данных свечей (kline):

GET https://api.bybit.com/v5/market/kline?category=spot&symbol=BTCUSDT&interval=60&limit=100

Это предоставляет часовые данные OHLCV, которые подаются в торговое моделирование MCTS. Интеграция:

Получает последние ценовые данные для указанной торговой пары
Извлекает цены закрытия как представление состояния
Инициализирует дерево поиска MCTS текущим состоянием рынка
Запускает поиск для определения оптимального действия

Ключ API не требуется для публичных эндпоинтов рыночных данных.

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

MCTS превосходен в последовательных решениях: Трейдинг включает цепочки зависимых решений, где каждое действие влияет на будущие возможности. MCTS естественно отражает эту последовательную структуру через своё древовидное представление.
UCT балансирует исследование и эксплуатацию: Математическая основа UCT гарантирует, что MCTS эффективно распределяет вычислительный бюджет, фокусируясь на перспективных стратегиях, сохраняя осведомлённость об альтернативах.
Онлайн-планирование адаптируется к изменяющимся условиям: В отличие от политик, обученных офлайн, MCTS планирует в момент принятия решения, используя текущее состояние рынка. Это делает его изначально адаптивным к смене режимов и новым рыночным условиям.
Улучшения в стиле AlphaZero трансформируют подход: Замена случайных развёрток обученными сетями ценности и направление поиска сетями политики значительно повышают производительность MCTS в сложных областях, таких как трейдинг.
Вычислительная стоимость — основное ограничение: MCTS требует выполнения многих моделирований в момент принятия решения. Для высокочастотной торговли это может быть непрактично, но для среднечастотных стратегий (часовых, дневных) это вполне применимо.
Интеграция риска естественна: Оценка развёртки может включать любую меру риска (VaR, CVaR, максимальная просадка), что делает MCTS подходящим для торговых стратегий с учётом риска.
Масштабируемость через параллелизм: Моделирования MCTS в значительной степени независимы и могут быть распараллелены по ядрам CPU или даже распределены между машинами, что обеспечивает масштабируемость к большим пространствам решений.
Доменные знания улучшают производительность: Пользовательские политики развёртки, специфичные для домена представления состояний и обученные априорные распределения значительно улучшают производительность MCTS по сравнению с базовыми реализациями.