Дистрибуционно-робастные марковские процессы принятия решений и их связь с мерами риска

Основная информация

• ID статьи: 2007.13103
• Название: Distributionally Robust Markov Decision Processes and their Connection to Risk Measures
• Авторы: Nicole Bäuerle, Alexander Glauner
• Классификация: math.OC (математическая оптимизация и управление), q-fin.RM (количественное управление финансовыми рисками)
• Дата публикации: 26 июля 2020 г.
• Ссылка на статью: https://arxiv.org/abs/2007.13103

Аннотация

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

Исследовательский контекст и мотивация

Постановка проблемы

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

Исследовательская мотивация

1. Проблема неопределённости модели: На практике вероятности переходов часто невозможно получить точно, существует неоднозначность модели
2. Требования к неприятию риска: Парадокс Эллсберга показывает, что лица, принимающие решения, склонны избегать неоднозначности
3. Теоретические ограничения: Существующие исследования робастных МППР в основном ограничены конечными пространствами состояний и действий
4. Практические потребности: Необходимо решать реальные задачи с непрерывными пространствами состояний и неограниченными функциями затрат

Ограничения существующих подходов

• Большинство исследований ограничены счётными или конечными пространствами состояний и действий
• Отсутствует обработка непрерывных пространств и неограниченных затрат
• Недостаточно глубокая связь с мерами риска
• Отсутствуют доказательства существования детерминированных оптимальных стратегий

Основные вклады

1. Расширение теоретической базы: Расширение существующей теории робастных МППР с счётных пространств на борелевы пространства с обработкой неограниченных функций затрат
2. Моделирование теорией игр: Моделирование задачи как игры Штакельберга, где природа является ведомым игроком, а лицо, принимающее решение, — лидером
3. Существование оптимальных стратегий: Доказательство существования детерминированных оптимальных стратегий для обеих сторон, что отличается от классических нулевых игр
4. Условия обмена экстремумов: При предположениях выпуклости использование теоремы Сиона о минимаксе позволяет обменять верхнюю и нижнюю грани
5. Связь с мерами риска: Установление эквивалентности между робастной оптимизацией и минимизацией когерентной меры риска при специальных неопределённых множествах
6. Практические приложения: Предоставление двух примеров приложений: робастная задача ЛК и управление возобновляемыми источниками энергии

Подробное описание методов

Определение задачи

Рассмотрим марковский процесс принятия решений с конечным временным горизонтом N:

• Пространство состояний: E (борелево пространство)
• Пространство действий: A (борелево пространство)
• Функция переходов: $T_n: D_n \times Z \to E$
• Функция затрат: $c_n: D_n \times E \to \mathbb{R}$
• Возмущения: $Z_1, \ldots, Z_N$ — независимые случайные элементы

Цель состоит в минимизации ожидаемых затрат в наихудшем случае: $V_0(x) = \inf_{\pi \in \Pi^R} \sup_{\gamma \in \Gamma} V_0^{\pi\gamma}(x)$

Архитектура модели

1. Моделирование неопределённых множеств

Определим неопределённое множество $\mathcal{Q}_n \subseteq M_q(\Omega_n, \mathcal{A}_n, P_n)$, где:

• $M_q(\Omega_n, \mathcal{A}_n, P_n)$ — множество вероятностных мер, абсолютно непрерывных относительно $P_n$
• Наделено слабой* топологией $\sigma(L^q, L^p)$, где $\frac{1}{p} + \frac{1}{q} = 1$

2. Структура игры Штакельберга

• Лицо, принимающее решение: выбирает стратегию $\pi = (\pi_0, \pi_1, \ldots, \pi_{N-1})$
• Природа: после наблюдения действий лица, принимающего решение, выбирает $\gamma = (\gamma_0, \ldots, \gamma_{N-1})$
• Информационная структура: природа является ведомым игроком и может наблюдать действия лица, принимающего решение

3. Рекурсивные соотношения функции значения

При предположениях условий функция значения удовлетворяет уравнению Беллмана: $J_n(x) = \inf_{a \in D_n(x)} \sup_{Q \in \mathcal{Q}_{n+1}} L_n J_{n+1}(x,a,Q)$

где: $L_n v(x,a,Q) = \int c_n(x,a,T_n(x,a,z)) + v(T_n(x,a,z)) \, Q(dz)$

Технические инновации

1. Применение теоремы об измеримом выборе

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

2. Обработка слабой* топологии

Применение слабой* топологии $\sigma(L^q, L^p)$ вместо топологии слабой сходимости для облегчения установления связи с рекурсивными мерами риска.

3. Техника граничных функций

Введение верхней и нижней граничных функций $\bar{b}$ и $\underline{b}$ для обработки неограниченных затрат, обеспечивая корректную определённость функции значения.

4. Анализ выпуклости

При предположениях выпуклости модели использование теоремы Сиона о минимаксе для реализации: $\inf_{a \in D_n(x)} \sup_{Q \in \mathcal{Q}_{n+1}} L_n J_{n+1}(x,a,Q) = \sup_{Q \in \mathcal{Q}_{n+1}} \inf_{a \in D_n(x)} L_n J_{n+1}(x,a,Q)$

Основные теоретические результаты

Теорема 3.6: Итерация значений робастной стратегии

При предположениях 2.1 и 3.1:

1. Робастное значение стратегии $V_n^\pi(h_n)$ является измеримым и удовлетворяет рекурсивному соотношению
2. Если неопределённое множество слабо* замкнуто, то существует оптимальное правило решения для природы

Теорема 3.10: Существование оптимальной стратегии

1. Достаточно рассмотреть детерминированные марковские стратегии: $V_n(h_n) = J_n(x_n)$
2. $J_n \in B$ и удовлетворяет уравнению Беллмана
3. Существует марковская оптимальная стратегия для лица, принимающего решение

Теорема 5.2: Обмен экстремумов

В выпуклой модели: $J_n(x) = \inf_{a \in D_n(x)} \sup_{Q \in \mathcal{Q}_{n+1}} L_n J_{n+1}(x,a,Q) = \sup_{Q \in \mathcal{Q}_{n+1}} \inf_{a \in D_n(x)} L_n J_{n+1}(x,a,Q)$

Теорема 5.5: Существование равновесия Нэша

При предположениях выпуклости модели и слабой* замкнутости неопределённого множества существует пара стратегий равновесия Нэша.

Связь с мерами риска

Представление спектральной меры риска

Когда неопределённое множество имеет специальную структуру, робастная оптимизация эквивалентна оптимизации спектральной меры риска: $\rho_\phi(X) = \sup_{Y \in \mathcal{Q}_d} E[XY]$

где $\phi$ — спектральная функция.

Когерентная мера риска

При инвариантных относительно закона неопределённых множествах задача может быть переписана как: $\inf_{\pi \in \Pi^M} \rho\left(\sum_{n=0}^{N-1} c_n(X_n, d_n(X_n), X_{n+1}) + c_N(X_N)\right)$

Экспериментальные приложения

Приложение 1: Робастная задача ЛК

Рассмотрим линейно-квадратичную задачу:

• Пространство состояний: $E = \mathbb{R}$, пространство действий: $A = \mathbb{R}^d$
• Функция переходов: $T_n(x,a,Z_{n+1}) = U_{n+1}x + V_{n+1}^T a + W_{n+1}$
• Функция затрат: $c_n(x,a) = x^2 Q_n + a^T R_n a$

Ключевые результаты

1. При предположении независимости оптимальная стратегия природы не зависит от состояния
2. Возможно обменять экстремумы с использованием теоремы Сиона, упрощая решение
3. Когда возможно выбрать $E^Q[U_n V_n] = 0$, оптимальное управление равно $d_n^*(x) = 0$

Приложение 2: Управление возобновляемыми источниками энергии

Совместное управление ветроэнергетической установкой и накопителем энергии:

• Состояние: объём накопленной энергии в батарее $x \in [0,K]$
• Действие: объявленный объём производства $a \in [0,B]$
• Вознаграждение: $Pa$ (где $P > 0$ — цена электроэнергии)
• Штраф: пропорциональный штраф $c > 0$ при дефиците

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

$J_n(x) = \inf_{a \in D(x)} \sup_{Q \in \mathcal{Q}} \left\{-aP + \int_a^B J_{n+1}((x+z-a) \wedge K) Q(dz) + \int_0^a [(P+c)(x+z-a)^- + J_{n+1}((x+z-a)^+)] Q(dz)\right\}$

Связанные работы

Развитие робастных МППР

1. Iyengar (2005): Первое введение робастных МППР при условии прямоугольности
2. Nilim & El Ghaoui (2005): Одновременная работа для конечных пространств состояний
3. Wiesemann et al. (2013): Метод доверительных областей
4. Xu & Mannor (2010): Вложенные неопределённые множества

Преимущества данной работы

1. Расширение пространств: Расширение от конечных/счётных к общим борелевым пространствам
2. Обработка затрат: Допущение неограниченных функций затрат
3. Свойства стратегий: Доказательство существования детерминированных оптимальных стратегий
4. Теоретическая глубина: Установление глубокой связи с мерами риска

Заключение и обсуждение

Основные выводы

1. Успешное расширение теории робастных МППР на непрерывные пространства и неограниченные затраты
2. Установление полной теории итерации значений и существования оптимальных стратегий
3. Раскрытие глубокой связи между робастной оптимизацией и мерами риска
4. Предоставление практических методов решения и примеров приложений

Ограничения

1. Условия предположений: Требуются достаточно сильные предположения интегрируемости, непрерывности и компактности
2. Требования выпуклости: Обмен экстремумов требует выпуклости структуры модели
3. Вычислительная сложность: Вычисление supremum в непрерывных пространствах остаётся сложной задачей
4. Выбор неопределённого множества: Разумное построение неопределённого множества в практических приложениях требует знаний предметной области

Направления будущих исследований

1. Разработка алгоритмов: Проектирование эффективных численных алгоритмов решения
2. Ослабление предположений: Исследование теоретических результатов при более общих условиях
3. Расширение приложений: Конкретные приложения в финансах, исследовании операций и других областях
4. Интеграция с обучением: Комбинирование с методами онлайн-обучения и адаптивными подходами

Глубокая оценка

Преимущества

1. Значительный теоретический вклад: Фундаментальное расширение применимости робастных МППР
2. Строгая методология: Применение глубоких теорий теории меры и функционального анализа
3. Ясная структура: Логичное изложение от базовых предположений к основным теоремам
4. Глубокие связи: Установление моста между теорией оптимизации и управлением рисками
5. Практическая ценность: Предоставление применимой на практике базы моделирования

Недостатки

1. Высокий технический уровень: Требуется сильный математический фундамент для полного понимания
2. Вычислительные вызовы: Расстояние между теоретическими результатами и практическими вычислениями
3. Ограничения предположений: Некоторые предположения могут быть сложны для удовлетворения в практических приложениях
4. Недостаточная численная верификация: Отсутствие крупномасштабных численных экспериментов для верификации

Влияние

1. Академическая ценность: Предоставление важной теоретической базы для робастной оптимизации и управления рисками
2. Перспективы приложений: Широкие возможности приложений в управлении финансовыми рисками, энергетических системах и других областях
3. Методологический вклад: Моделирование игры Штакельберга предоставляет новый подход к связанным задачам
4. Основа для будущих исследований: Создание основы для дальнейшего теоретического развития и разработки алгоритмов

Применимые сценарии

1. Финансовая инженерия: Оптимизация портфеля, управление рисками
2. Энергетические системы: Планирование возобновляемых источников энергии, управление накопителями
3. Управление цепочками поставок: Контроль запасов при неопределённом спросе
4. Исследование операций: Распределение ресурсов, планирование производства

Список литературы

Статья ссылается на 75 связанных работ, включая:

• Iyengar (2005): Основополагающая работа по робастному динамическому программированию
• Sion (1958): Классический результат теоремы о минимаксе
• Bäuerle & Rieder (2011): Монография по марковским процессам принятия решений
• Epstein & Schneider (2003): Теория рекурсивных множественных приоров
• Ruszczyński (2010): Динамическое программирование с неприятием риска

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