Центральные предельные теоремы для асинхронного усредненного Q-обучения

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

• ID статьи: 2509.18964
• Название: Central Limit Theorems for Asynchronous Averaged Q-Learning
• Автор: Xingtu Liu (Simon Fraser University)
• Классификация: cs.LG math.OC stat.ML
• Конференция: OPT2025: 17th Annual Workshop on Optimization for Machine Learning
• Ссылка на статью: https://arxiv.org/abs/2509.18964

Аннотация

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

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

Проблемный фон

1. Значимость Q-обучения: Q-обучение является одним из наиболее широко используемых алгоритмов в обучении с подкреплением, непосредственно обучаясь оптимальной функции стоимости действия из эмпирических траекторий. Алгоритм достиг значительных успехов в играх Atari, го, робототехнике и выравнивании больших языковых моделей.
2. Вызовы теоретического анализа:
   • Q-обучение можно интерпретировать как частный случай стохастической аппроксимации (SA), однако асинхронное Q-обучение представляет собой нелинейную задачу SA с марковским шумом
   • По сравнению с линейной SA и обучением временным разностям (TD), анализ Q-обучения более сложен из-за его нелинейности, негладких операторов и нестационарных процессов
   • Асинхронные обновления дополнительно вводят марковский шум, увеличивая сложность анализа
3. Ограничения существующих работ:
   • Предыдущие работы устанавливали функциональную ЦПТ для синхронного Q-обучения, но синхронное Q-обучение рассматривает только мартингальный шум
   • Zhang и Xie (2024) установили функциональную ЦПТ для асинхронного Q-обучения с постоянным размером шага, однако постоянный размер шага не удовлетворяет необходимым условиям для установления неасимптотической ЦПТ
   • На данный момент не существует неасимптотической ЦПТ для Q-обучения, даже в синхронном случае

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

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

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

1. Первая неасимптотическая ЦПТ для Q-обучения: Доказана неасимптотическая центральная предельная теорема для асинхронного усредненного Q-обучения со скоростью сходимости $\tilde{O}((|S||A|)^{1/2}K^{-1/6}\rho^{-2}(1-\gamma)^{-3})$
2. Функциональная центральная предельная теорема: Установлена функциональная ЦПТ для асинхронного Q-обучения с убывающим размером шага, показывающая слабую сходимость частичных сумм процессов к броуновскому движению
3. Явные зависимости: Скорость сходимости явно отражает зависимость от количества итераций K, размера пространства состояний-действий |S||A|, коэффициента дисконтирования γ и качества исследования ρ
4. Технические инновации: Преодолены аналитические вызовы, вызванные нелинейностью, марковским шумом и негладкими операторами

Детальное описание методологии

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

Рассматривается бесконечный горизонт дисконтированного марковского процесса принятия решений (MDP) $M = \langle S, A, P, r, \gamma \rangle$, где:

• $S$: множество состояний
• $A$: множество действий
• $P: S \times A \rightarrow \Delta_S$: функция переходных вероятностей
• $\gamma \in [0,1)$: коэффициент дисконтирования

Целью является обучение оптимальной Q-функции $Q^* = \max_\pi Q^\pi$.

Алгоритм асинхронного Q-обучения

Асинхронное Q-обучение поддерживает оценку Q-функции $Q_k$ с правилом обновления: $Q_{k+1} = Q_k + \alpha_k(F_k - Q_k)$

где:

• $F_k = F(Q_k, y_k)$, $y_k = (s_k, a_k, s_{k+1})$
• $[F(Q_k, s_k, a_k, s_{k+1})](s,a) = \mathbf{1}_{\{(s_k,a_k)=(s,a)\}}\Gamma(Q_k, s_k, a_k, s_{k+1}) + Q_k(s,a)$
• $\Gamma(Q_k, s_k, a_k, s_{k+1}) = r_k(s_k, a_k) + \gamma\max_a Q_k(s_{k+1}, a) - Q_k(s_k, a_k)$

Ключевые предположения

Предположение 1: Существует оптимальная политика $\pi^*$ такая, что для $Q \in \mathbb{R}^{|S|\times|A|}$: $\|(P^\pi - P^{\pi^*})(Q-Q^*)\|_\infty \leq L\|Q-Q^*\|_2^\infty$

Предположение 2: $\{y_k\}_{k \geq 0}$ является неприводимой и апериодической конечной цепью Маркова.

Выбор размера шага

Выбирается полиномиальный размер шага $\alpha_k = \alpha(k+b)^{-\beta}$, где $\alpha, b > 0$, $\beta \in (0.5, 1)$.

Причины такого выбора:

1. Удовлетворяет ключевым условиям схемы усреднения Поляка-Юдицкого
2. Постоянный размер шага нарушает условия (i) и (iii), линейный размер шага нарушает условие (ii)
3. Полиномиальный размер шага удовлетворяет всем необходимым условиям

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

Неасимптотическая центральная предельная теорема

Теорема 4: При предположениях 1 и 2 имеет место: $W_1\left(K^{-1/2}\sum_{k=1}^K \Delta_k, \tilde{N}\right) \leq \frac{(|S||A|)^{1/2}}{\rho(1-\gamma)^2K^{1/2}} \cdot \tilde{O}\left((\rho(1-\gamma))^{\frac{\beta-2}{1-\beta}} + K^{\beta/2}\rho^{-1}(1-\gamma)^{-1} + K^{1-\beta} + K^{\frac{1-\beta}{2}}\rho^{-1-\beta}(1-\gamma)^{-\beta}\right)$

где $\Delta_k = Q_k - Q^*$, $\tilde{N} = (A^{-1}\Sigma A^{-\top})^{1/2}N(0,I)$.

Следствие 5: При $\beta = 2/3$ скорость сходимости упрощается до: $W_1\left(K^{-1/2}\sum_{k=1}^K \Delta_k, (A^{-1}\Sigma A^{-\top})^{1/2}N(0,I)\right) \leq \tilde{O}\left(\frac{(|S||A|)^{1/2}}{K^{1/6}\rho^2(1-\gamma)^3}\right)$

Функциональная центральная предельная теорема

Теорема 6: В условиях теоремы 4 процесс частичных сумм $\Phi_K(\zeta) = K^{-1/2}\sum_{k=1}^{\lfloor\zeta K\rfloor}\Delta_k$ слабо сходится в $D[0,1]$ к $(A^{-1}\Sigma A^{-\top})^{1/2}B(\cdot)$, где $B(\cdot)$ — стандартное броуновское движение.

Технические инновации и стратегия доказательства

Основные технические вызовы

1. Нелинейность: Q-обучение является нелинейной SA, более сложной, чем линейная SA
2. Марковский шум: Асинхронные обновления вводят неидентично распределенный марковский шум
3. Негладкие операторы: Эмпирический оператор Беллмана в асинхронном Q-обучении негладкий

Стратегия доказательства

1. Техника верхних и нижних границ: Введение верхней последовательности $\Delta_k^{\uparrow}$ и нижней последовательности $\Delta_k^{\downarrow}$, применение теоремы о сжатии
2. Разложение членов: Разложение $\sum_{k=1}^K \Delta_k$ на 6 членов:
   • Член (1): Ошибка инициализации
   • Член (2): Нелинейная ошибка
   • Член (3): Марковский шум
   • Члены (4-5): Поправки высшего порядка
   • Член (6): Мартингальные разности
3. Техника уравнения Пуассона: Преобразование марковского шума в мартингальные разности
4. Мартингальная центральная предельная теорема: Применение неасимптотической мартингальной ЦПТ Srikant (2024)

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

Теория стохастической аппроксимации

• Polyak, B. T. и Juditsky, A. B. (1992): Классическая техника ускорения и усреднения для снижения дисперсии
• Anastasiou и др. (2019): Неасимптотическая ЦПТ для усредненного SGD Поляка-Рупперта
• Mou и др. (2020): Неасимптотическая ЦПТ для линейной SA

ЦПТ в обучении с подкреплением

• Xie и Zhang (2022), Li и др. (2023): Функциональная ЦПТ для синхронного Q-обучения
• Zhang и Xie (2024): Функциональная ЦПТ для асинхронного Q-обучения с постоянным размером шага
• Srikant (2024), Samsonov и др. (2024): Неасимптотическая ЦПТ для обучения TD

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

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

1. Установлена первая неасимптотическая ЦПТ для Q-обучения со скоростью сходимости, явно зависящей от параметров задачи
2. Доказана слабая сходимость процесса частичных сумм асинхронного Q-обучения
3. Обеспечена теоретическая основа для количественной оценки неопределенности в обучении с подкреплением

Ограничения

1. Требуются сильные предположения Липшица (Предположение 1)
2. Рассматривается только конечное пространство состояний-действий
3. Скорость сходимости может быть неоптимальной

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

1. Улучшение скорости сходимости
2. Расширение на другие метрики помимо 1-расстояния Вассерштейна
3. Рассмотрение случаев функциональной аппроксимации

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

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

1. Значительный теоретический вклад: Впервые установлена неасимптотическая ЦПТ для Q-обучения, заполняя важный теоретический пробел
2. Технические инновации: Умелое сочетание техники верхних и нижних границ, уравнения Пуассона и мартингальной ЦПТ для решения технических проблем
3. Полнота результатов: Одновременное предоставление неасимптотической и функциональной ЦПТ
4. Явные зависимости: Скорость сходимости явно отражает влияние каждого параметра

Недостатки

1. Сильные предположения: Предположение Липшица может быть сложным для проверки на практике
2. Скорость сходимости: Скорость сходимости $K^{-1/6}$ относительно медленная
3. Конечные состояния: Не рассматриваются непрерывные пространства состояний или функциональная аппроксимация

Влияние

1. Теоретическая ценность: Предоставляет новые инструменты и перспективы для теоретического анализа Q-обучения
2. Практическое значение: Закладывает теоретическую основу для количественной оценки неопределенности в алгоритмах обучения с подкреплением
3. Методология: Техники доказательства могут быть обобщены на другие нелинейные задачи SA

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

1. Теоретический анализ табличных задач обучения с подкреплением
2. Исследование сходимости алгоритмов с асинхронными обновлениями
3. Статистический вывод и построение доверительных интервалов в обучении с подкреплением

Библиография

• Polyak, B. T. and Juditsky, A. B. (1992). Acceleration of stochastic approximation by averaging.
• Xie, C. and Zhang, Z. (2022). A statistical online inference approach in averaged stochastic approximation.
• Zhang, Y. and Xie, Q. (2024). Constant stepsize q-learning: Distributional convergence, bias and extrapolation.