Апостериорная выборка для непрерывных сред

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

• ID статьи: 2211.15931
• Название: Posterior Sampling for Continuing Environments
• Авторы: Wanqiao Xu (Stanford University), Shi Dong (Google DeepMind), Benjamin Van Roy (Stanford University)
• Классификация: cs.LG stat.ML
• Конференция публикации: RLJ | RLC 2024
• Ссылка на статью: https://arxiv.org/abs/2211.15931

Аннотация

В данной работе предлагается алгоритм апостериорной выборки для обучения с подкреплением в непрерывных средах (Continuing PSRL), который естественным образом интегрируется в масштабируемые конструкции агентов. Алгоритм поддерживает статистически обоснованную модель окружающей среды и следует политике, максимизирующей γ-дисконтированное вознаграждение в этой модели. На каждом временном шаге алгоритм с вероятностью 1-γ переизбирает модель из апостериорного распределения окружающей среды. Путём надлежащего выбора дисконтного коэффициента, зависящего от временного горизонта T, устанавливается байесовская граница сожаления Õ(τS√AT), где S — количество состояний окружающей среды, A — количество действий, τ — среднее время вознаграждения.

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

Основная проблема

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

Важность проблемы

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

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

1. TSDE (Ouyang et al., 2017): требует сложных критериев переизбора, включая условия удвоения счётчиков посещений, неприменимо в больших пространствах состояний
2. DS-PSRL (Theocharous et al., 2018): хотя избегает счётчиков посещений, анализ зависит от сильных технических предположений; без них граница сожаления растёт линейно
3. Традиционный PSRL: применим только к эпизодическим средам, не может быть прямо расширен на непрерывные настройки

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

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

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

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

1. Первый масштабируемый алгоритм PSRL для непрерывных сред: предложен Continuing PSRL, основанный на простой схеме рандомизации, избегающей сложных критериев переизбора
2. Строгий теоретический анализ: установлена байесовская граница сожаления Õ(τS√AT), соответствующая лучшим существующим результатам
3. Прорыв в масштабируемости: алгоритм естественно расширяется на высокомерные пространства состояний и настройки функциональной аппроксимации
4. Новая перспектива дисконтного коэффициента: дисконтный коэффициент рассматривается как инструмент проектирования алгоритма, а не как свойство окружающей среды, предоставляя новую перспективу понимания роли дисконтного коэффициента

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

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

Рассмотрим неизвестную окружающую среду E = (A,S,ρ), моделируемую марковским процессом принятия решений, где:

• A — конечное пространство действий, |A| = A
• S — конечное пространство состояний, |S| = S
• ρ — функция вероятности переходов состояний
• функция вознаграждения r : S × A → 0,1 является детерминированной и известной

Цель состоит в минимизации накопленного сожаления: $\text{Regret}(T,π) := \sum_{t=0}^{T-1}(λ_{*,E} - R_{t+1})$

где λ_{*,E} — оптимальное среднее вознаграждение.

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

Конструкция псевдоэпизодов

Алгоритм разлагает задачу обучения на бесконечном временном горизонте на псевдоэпизоды случайной длины:

• На каждом временном шаге t производится выборка бинарного индикатора X_t
• Когда X_t = 0, начинается новый псевдоэпизод и переизбирается модель окружающей среды
• Когда X_t = 1, продолжается текущий псевдоэпизод

Дисконтированная функция стоимости

Для окружающей среды E и политики π γ-дисконтированная функция стоимости определяется как: $V^γ_{π,E} := \mathbb{E}\left[\sum_{h=0}^{H-1} P^h_π r_π | E\right] = \mathbb{E}\left[\sum_{h=0}^{∞} γ^h P^h_π r_π | E\right]$

где H — длина псевдоэпизода, подчиняющаяся геометрическому распределению.

Среднее время вознаграждения

Ключевое понятие — среднее время вознаграждения τ_{π,E}, определяемое как минимальное значение τ такое, что: $\left|\mathbb{E}_π\left[\sum_{t=0}^{T-1} R_{t+1} | E, S_0 = s\right] - T \cdot λ_{π,E}(s)\right| \leq τ$

Процедура алгоритма

Алгоритм 1: Continuing PSRL

Вход: априорное распределение f, дисконтный коэффициент γ, общее время обучения T
1. Инициализация t=1, k=1, X₁=0
2. для t ≤ T:
3.   если Xₜ = 0:
4.     tₖ ← t
5.     выборка Eₖ ~ f(·|H_tₖ)
6.     вычисление πₖ = π^γ_Eₖ
7.     k ← k+1
8.   выборка и выполнение Aₜ ~ πₖ(·|Sₜ)
9.   наблюдение Rₜ₊₁ и Sₜ₊₁
10.  t ← t+1
11.  выборка Xₜ₊₁ ~ Bernoulli(γ)

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

1. Простой механизм переизбора: использует только генератор случайных чисел Бернулли, избегая сложных условий на счётчики посещений
2. Связь дисконтного коэффициента и вероятности переизбора: установка γ = 1-p, где p — вероятность переизбора
3. Независимый от политики критерий переизбора: стандарт переизбора не зависит от политики, упрощая анализ
4. Зависящий от времени дисконтный коэффициент: позволяет дисконтному коэффициенту расти со временем, достигая сублинейного сожаления

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

Наборы данных

1. Табличная среда RiverSwim:
   • цепочечная структура из 6 состояний
   • вознаграждение 0.005 в левом конце, 1.0 в правом конце
   • оптимальная политика — всегда плыть вправо
2. Среда RiverSwim с непрерывными признаками:
   • аналогичная структура, но с наблюдениями в виде пиксельных признаков
   • отображение признаков: φ(s_t) = 1{x ≤ s_t} ∈ 0,1^N
   • тестирование производительности алгоритма в условиях функциональной аппроксимации

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

• Накопленное сожаление (Cumulative Regret)
• Изменение среднего сожаления во времени

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

1. TSDE (Ouyang et al., 2017): выборка Томпсона на основе счётчиков посещений
2. DS-PSRL (Theocharous et al., 2018): схема переизбора с фиксированными временными интервалами
3. Случайный агент: в качестве базовой линии
4. DQN с ε-жадной стратегией: сравнение в среде с непрерывными признаками

Детали реализации

• Априорное распределение: распределение Дирихле (переходы) и нормально-гамма распределение (вознаграждения)
• Гиперпараметры: псевдосчёт n=1, α=1/S, μ=σ²=1
• В среде с непрерывными признаками используется Bootstrapped DQN, γ=0.99

Результаты экспериментов

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

1. Табличная среда:
   • Continuing PSRL показывает производительность, сравнимую с TSDE, несмотря на то, что последний непосредственно оптимизирует среднее вознаграждение
   • значительно превосходит DS-PSRL
   • подтверждает теоретически предсказанный рост сублинейного сожаления
2. Среда с непрерывными признаками:
   • Bootstrapped DQN со случайным переизбором достигает сублинейного сожаления
   • явно превосходит vanilla DQN с ε-жадным исследованием
   • доказывает масштабируемость метода в сложных средах

Экспериментальные находки

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

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

Выборка Томпсона и апостериорная выборка

• Классическая выборка Томпсона: первоначально применялась к задаче многорукого бандита
• Расширение PSRL: Osband и др. расширили её на обучение с подкреплением, но в основном для эпизодических сред
• Bootstrapped DQN: использует ансамблевые методы для аппроксимации апостериорного распределения

Исследование в непрерывных средах

• TSDE: первый метод выборки Томпсона для непрерывных сред, но зависит от сложного критерия переизбора
• DS-PSRL: упрощает переизбор, но требует сильных технических предположений
• Данная работа: впервые предоставляет простой и строгий метод стохастического переизбора

Теоретический анализ

• Существующие работы в основном рассматривают γ-дисконтированное сожаление; данная работа сосредоточена на недисконтированном сожалении
• использование среднего времени вознаграждения τ заменяет традиционное понятие span
• предположение о слабой связности MDP — наиболее общая настройка для границ сожаления на конечном временном горизонте

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

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

1. Теоретический вклад: установлена граница сожаления Õ(τS√AT), соответствующая лучшим существующим результатам
2. Простота алгоритма: для реализации эффективного исследования требуется только генератор случайных чисел Бернулли
3. Практическая ценность: алгоритм может быть прямо интегрирован в существующие методы глубокого обучения с подкреплением
4. Новая перспектива дисконтного коэффициента: дисконтный коэффициент рассматривается как инструмент проектирования алгоритма, а не как свойство окружающей среды

Ограничения

1. Теоретические предположения: требуется предположение о слабой связности MDP и ограниченном среднем времени вознаграждения
2. Зависимость от априорного распределения: производительность зависит от надлежащей установки априорного распределения
3. Настройка параметров: выбор дисконтного коэффициента γ требует знания временного горизонта T
4. Объём экспериментов: эксперименты проводились в основном в относительно простых средах

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

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

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

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

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

Недостатки

1. Недостаточная глубина экспериментов: эксперименты проводились в основном в простых средах, отсутствует проверка в крупных сложных средах
2. Чувствительность к параметрам: выбор дисконтного коэффициента γ зависит от параметров задачи, может требовать тщательной настройки при практическом применении
3. Неполное сравнение: отсутствует сравнение с некоторыми связанными методами исследования (например, методами типа UCB)
4. Отсутствие практических примеров применения: в основном теория и простые симуляции, отсутствует проверка в реальных сценариях применения

Влияние

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

Сценарии применения

1. Обучение с подкреплением в непрерывных средах: среды, требующие длительного взаимодействия без естественной структуры эпизодов
2. Высокомерные пространства состояний: сложные среды, где традиционные методы на основе счётчиков неприменимы
3. Онлайн-обучение: сценарии, требующие непрерывного обучения и адаптации в процессе взаимодействия
4. Глубокое обучение с подкреплением: может быть интегрирован в существующие фреймворки глубокого RL

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

Статья ссылается на важные работы в области обучения с подкреплением, включая:

• Классические работы по выборке Томпсона (Thompson, 1933)
• Основополагающие работы по PSRL (Osband et al., 2013)
• Связанные исследования в непрерывных средах (Ouyang et al., 2017; Theocharous et al., 2018)
• Важные достижения в глубоком обучении с подкреплением (Mnih et al., 2015)

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