Сходимость и сложность выборки методов естественного градиента политики типа прямо-двойственных для ограниченных МДП

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

• ID статьи: 2206.02346
• Название: Convergence and sample complexity of natural policy gradient primal-dual methods for constrained MDPs
• Авторы: Dongsheng Ding, Kaiqing Zhang, Jiali Duan, Tamer Başar, Mihailo R. Jovanović
• Классификация: math.OC cs.AI cs.LG cs.SY eess.SY
• Журнал публикации: Journal of Machine Learning Research 26 (2025) 1-76
• Ссылка на статью: https://arxiv.org/abs/2206.02346

Аннотация

В данной работе исследуется задача последовательного принятия решений по максимизации ожидаемого совокупного вознаграждения при условии удовлетворения ограничений на ожидаемую совокупную полезность. Авторы применяют метод естественного градиента политики для решения задачи оптимального управления с дисконтированием на бесконечном горизонте для ограниченных марковских процессов принятия решений (constrained MDPs). Конкретно предложен новый метод естественного градиента политики типа прямо-двойственный (NPG-PD), который обновляет прямые переменные посредством восхождения по естественному градиенту политики, а двойственные переменные — посредством проецируемого субградиентного спуска. Несмотря на то, что базовая задача максимизации включает невогнутую целевую функцию и невыпуклое множество ограничений, при параметризации политики softmax метод достигает сублинейной скорости глобальной сходимости как для зазора оптимальности, так и для нарушения ограничений. Эта сходимость не зависит от размера пространства состояний-действий, то есть является безразмерной. Кроме того, для логарифмически-линейной и общей гладкой параметризации политики установлена сублинейная скорость сходимости вплоть до ошибки функциональной аппроксимации, вызванной ограниченной параметризацией политики.

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

Определение проблемы

Основная проблема, решаемая в данной работе, — это задача обучения оптимальной политике в ограниченных марковских процессах принятия решений (Constrained MDPs):

• Цель: максимизировать ожидаемое совокупное вознаграждение $V^π_r(ρ)$
• Ограничение: удовлетворять ограничению на ожидаемую совокупную полезность $V^π_g(ρ) ≥ b$
• Вызовы: целевая функция невогнута, множество ограничений невыпукло

Значимость

Ограниченные МДП имеют важное значение в критичных по безопасности приложениях:

1. Автономные транспортные средства: необходимо максимизировать производительность при соблюдении ограничений безопасности
2. Робототехника: при выполнении задач должны соблюдаться физические и безопасностные ограничения
3. Кибербезопасность: оптимизация производительности системы при сохранении политик безопасности
4. Финансовое управление: достижение доходов при контроле рисков

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

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

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

1. Предложение алгоритма NPG-PD: разработана новая архитектура алгоритма, объединяющая естественный градиент политики и методы типа прямо-двойственные
2. Гарантии глобальной сходимости: доказана безразмерная глобальная сходимость при параметризации softmax
3. Теория функциональной аппроксимации: установлена теория сходимости для логарифмически-линейной и общей гладкой параметризации политики
4. Анализ сложности выборки: предоставлены гарантии конечной сложности выборки для двух вариантов алгоритма NPG-PD на основе выборок
5. Экспериментальная проверка: подтверждена эффективность метода на задачах робототехнического моделирования

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

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

Ограниченный МДП определяется как кортеж из семи элементов $(\mathcal{S}, \mathcal{A}, P, r, g, b, γ, ρ)$:

• $\mathcal{S}$: конечное пространство состояний
• $\mathcal{A}$: конечное пространство действий
• $P$: вероятность переходов
• $r, g$: функции вознаграждения и полезности
• $b$: пороговое значение ограничения
• $γ$: коэффициент дисконтирования
• $ρ$: начальное распределение состояний

Задача оптимизации: $\max_{π ∈ Π} V^π_r(ρ) \quad \text{при условии} \quad V^π_g(ρ) ≥ b$

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

1. Лагранжева двойственность

Преобразование задачи ограниченной оптимизации в задачу поиска седловой точки: $\max_{π ∈ Π} \min_{λ ≥ 0} V^π_r(ρ) + λ(V^π_g(ρ) - b)$

2. Основные обновления алгоритма NPG-PD

Обновление прямых переменных (естественный градиент политики): $θ^{(t+1)} = θ^{(t)} + η_1 F^†_ρ(θ^{(t)})∇_θ V^{θ^{(t)},λ^{(t)}}_L(ρ)$

Обновление двойственных переменных (проецируемый субградиентный спуск): $λ^{(t+1)} = P_Λ\left(λ^{(t)} - η_2(V^{θ^{(t)}}_g(ρ) - b)\right)$

где:

• $F^†_ρ(θ)$: псевдообратная матрица информации Фишера
• $P_Λ$: проекция на интервал $[0, 2/((1-γ)ξ)]$

3. Упрощенная форма при параметризации softmax

При параметризации softmax $π_θ(a|s) = \frac{\exp(θ_{s,a})}{\sum_{a'} \exp(θ_{s,a'})}$ обновление упрощается до:

$θ^{(t+1)}_{s,a} = θ^{(t)}_{s,a} + \frac{η_1}{1-γ}A^{(t)}_L(s,a)$

что эквивалентно обновлению мультипликативных весов: $π^{(t+1)}(a|s) = \frac{π^{(t)}(a|s)\exp\left(\frac{η_1}{1-γ}A^{(t)}_L(s,a)\right)}{Z^{(t)}(s)}$

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

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

Теоретические результаты

Основная теорема сходимости

Теорема 10 (глобальная сходимость при параметризации softmax): При условии Слейтера, выборе $η_1 = 2\log|A|$, $η_2 = 2(1-γ)/\sqrt{T}$ алгоритм NPG-PD удовлетворяет:

Зазор оптимальности: $\frac{1}{T}\sum_{t=0}^{T-1}(V^*_r(ρ) - V^{(t)}_r(ρ)) ≤ \frac{7}{(1-γ)^2}\frac{1}{\sqrt{T}}$

Нарушение ограничений: $\left[\frac{1}{T}\sum_{t=0}^{T-1}(b - V^{(t)}_g(ρ))\right]_+ ≤ \frac{2}{ξ} + \frac{4ξ}{(1-γ)^2}\frac{1}{\sqrt{T}}$

Случай функциональной аппроксимации

Теорема 16 (логарифмически-линейная параметризация): При функциональной аппроксимации скорость сходимости составляет: $E\left[\frac{1}{T}\sum_{t=0}^{T-1}(V^*_r(ρ) - V^{(t)}_r(ρ))\right] ≤ \frac{C_3}{(1-γ)^5}\frac{1}{\sqrt{T}} + \text{ошибка функциональной аппроксимации}$

Сложность выборки

Теоремы 28/29 (сложность выборки):

• Сложность итераций: $O(1/ε^2)$
• Сложность выборки: $O(1/ε^4)$

Это представляет значительное улучшение по сравнению с предыдущим результатом $O(1/ε^8)$.

Экспериментальная установка

Задачи робототехнического моделирования

Использованы 6 задач ходьбы робота в среде MuJoCo:

• Ant-v1, Humanoid-v1, HalfCheetah-v1, Walker2d-v1, Hopper-v1, Swimmer-v1
• Ограничение: скорость движения не превышает заданный порог (ограничение безопасности)

Методы сравнения

1. Классические методы типа прямо-двойственные: TRPOLag, PPOLag
2. Новейшие методы оптимизации политики: CUP, FOCOPS

Метрики оценки

• Среднее вознаграждение: производительность задачи
• Средняя стоимость: степень нарушения ограничений (средняя скорость)

Экспериментальные результаты

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

1. Преимущество производительности: NPG-PD достигает более высокого вознаграждения в большинстве задач при сохранении аналогичной степени удовлетворения ограничений
2. Скорость сходимости: сходится быстрее, чем классические методы Лагранжа
3. Конкурентная производительность: производительность сравнима или превосходит новейшие методы (FOCOPS, CUP)

Анализ конкретных результатов

• Ant-v1 и Humanoid-v1: NPG-PD единообразно превосходит все четыре других метода
• HalfCheetah-v1 и Walker2d-v1: производительность NPG-PD сравнима с PPOLag, оба превосходят другие методы
• Hopper-v1 и Swimmer-v1: NPG-PD конкурирует с FOCOPS и CUP, несмотря на ранние колебания, в конечном итоге достигает более высокого вознаграждения

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

Развитие алгоритмов для ограниченных МДП

1. Ранние работы: методы на основе Лагранжа (Altman 1999, Borkar 2005)
2. Методы локальной сходимости: CPG, accelerated PDPO, CPO и др.
3. Исследования глобальной сходимости: данная работа — первая, предоставляющая гарантии конечной глобальной сходимости

Методы градиента политики

1. Теория сходимости без ограничений: Agarwal et al. (2021) и др.
2. Вызовы ограниченной оптимизации: дополнительные трудности при обработке невыпуклых множеств ограничений

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

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

1. Теоретический прорыв: впервые предоставлены безразмерные гарантии глобальной сходимости для методов градиента политики в ограниченных МДП
2. Практический алгоритм: алгоритм NPG-PD прост и эффективен, применим к крупномасштабным задачам
3. Теория функциональной аппроксимации: установлена полная структура анализа ошибок функциональной аппроксимации

Ограничения

1. Колебательное поведение: ранние колебания, характерные для методов типа прямо-двойственные
2. Условие Слейтера: требуется предположение о строгой допустимости
3. Параметризация softmax: наиболее сильные результаты применимы только к конкретной параметризации

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

1. Сходимость итерации политики: исследование сходимости итерации политики для одношкальных алгоритмов
2. Техники регуляризации: введение регуляризации для устранения колебаний
3. Расширение на непрерывные пространства: расширение на непрерывные пространства состояний-действий
4. Анализ робастности: учет влияния неопределенности модели

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

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

1. Теоретическая инновация: впервые установлена безразмерная теория глобальной сходимости для ограниченных МДП
2. Техническая глубина: умелое объединение техник онлайн-обучения и ограниченной оптимизации
3. Полный анализ: полная теоретическая структура от табличного случая до функциональной аппроксимации
4. Экспериментальная проверка: проверка теоретических предсказаний на практических задачах робототехники

Недостатки

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

Влияние

1. Теоретический вклад: предоставляет важную теоретическую основу для ограниченного обучения с подкреплением
2. Методологическая ценность: структура NPG-PD может быть расширена на другие задачи ограниченной оптимизации
3. Практическая ценность: алгоритм прост в реализации и подходит для инженерных приложений
4. Основание для будущих исследований: закладывает теоретическую основу для последующих исследований в этой области

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

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

Дополнительные технические детали

Ключевые леммы

Лемма 11 (немонотонное улучшение): каждое обновление прямых переменных улучшает лагранжев член, но сами функции вознаграждения и полезности могут быть немонотонными.

Лемма 12 (ограниченная средняя производительность): через анализ ожидаемого сожаления устанавливаются границы средней производительности.

Техники доказательства

1. Связь с обновлением мультипликативных весов: интерпретация обновления NPG как MWU в онлайн-обучении
2. Обратная матрица информации Фишера: использование структуры softmax для упрощения вычислений NPG
3. Сильная двойственность: установление сильной двойственности при условии Слейтера
4. Граница нарушения ограничений: использование техник выпуклого анализа для ограничения нарушения ограничений

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