2025-11-15T23:58:12.055440

An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs

Liu, Wei, Zimmert
We study decision making with structured observation (DMSO). Previous work (Foster et al., 2021b, 2023a) has characterized the complexity of DMSO via the decision-estimation coefficient (DEC), but left a gap between the regret upper and lower bounds that scales with the size of the model class. To tighten this gap, Foster et al. (2023b) introduced optimistic DEC, achieving a bound that scales only with the size of the value-function class. However, their optimism-based exploration is only known to handle the stochastic setting, and it remains unclear whether it extends to the adversarial setting. We introduce Dig-DEC, a model-free DEC that removes optimism and drives exploration purely by information gain. Dig-DEC is always no larger than optimistic DEC and can be much smaller in special cases. Importantly, the removal of optimism allows it to handle adversarial environments without explicit reward estimators. By applying Dig-DEC to hybrid MDPs with stochastic transitions and adversarial rewards, we obtain the first model-free regret bounds for hybrid MDPs with bandit feedback under several general transition structures, resolving the main open problem left by Liu et al. (2025). We also improve the online function-estimation procedure in model-free learning: For average estimation error minimization, we refine the estimator in Foster et al. (2023b) to achieve sharper concentration, improving their regret bounds from $T^{3/4}$ to $T^{2/3}$ (on-policy) and from $T^{5/6}$ to $T^{7/9}$ (off-policy). For squared error minimization in Bellman-complete MDPs, we redesign their two-timescale procedure, improving the regret bound from $T^{2/3}$ to $\sqrt{T}$. This is the first time a DEC-based method achieves performance matching that of optimism-based approaches (Jin et al., 2021; Xie et al., 2023) in Bellman-complete MDPs.
academic

Улучшенный коэффициент решения-оценки без модели с приложениями в противодействующих MDP

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

  • ID статьи: 2510.08882
  • Название: An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs
  • Авторы: Haolin Liu (Университет Вирджинии), Chen-Yu Wei (Университет Вирджинии), Julian Zimmert (Google Research)
  • Классификация: cs.LG (Машинное обучение)
  • Время публикации: Октябрь 2025
  • Ссылка на статью: https://arxiv.org/abs/2510.08882v1

Аннотация

В данной работе исследуется проблема структурированного принятия решений с наблюдениями (DMSO). Предыдущие работы характеризовали сложность DMSO через коэффициент решения-оценки (DEC), однако оставили разрыв между верхней и нижней границами сожаления, связанный с размером класса модели. Foster и др. (2023b) ввели оптимистичный DEC для сокращения этого разрыва, достигнув границ, зависящих только от размера класса функций стоимости. Однако исследование, основанное на оптимизме, может обрабатывать только стохастические среды, и остается неясным, может ли оно быть расширено на противодействующие среды.

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

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

  1. Проблема, которую необходимо решить: Существующая структура коэффициента решения-оценки (DEC) оставляет разрыв между размером класса модели и размером класса функций стоимости, а методы, основанные на оптимизме, не могут эффективно обрабатывать противодействующие среды.
  2. Важность проблемы:
    • Принятие решений в режиме онлайн является центральной проблемой обучения с подкреплением
    • В практических приложениях часто встречаются смешанные среды, частично стохастические и частично противодействующие
    • Существует разрыв между теоретическими гарантиями и практической производительностью существующих методов
  3. Ограничения существующих методов:
    • Модель Foster и др. на основе DEC/E2D требует затрат на оценку модели log|M|
    • Хотя оптимистичный DEC улучшает сложность, он зависит от принципа оптимизма и не может обрабатывать противодействующие параметры
    • Метод смешанного MDP Liu и др. (2025) может обрабатывать только полную обратную связь, случай с бандитами остается открытой проблемой
  4. Исследовательская мотивация: Разработать унифицированную структуру, которая может как улучшить существующие результаты в стохастических средах, так и впервые обработать случай с бандитами для смешанных MDP.

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

  1. Предложение меры сложности Dig-DEC: Введение двойного информационного прироста коэффициента решения-оценки, устранение оптимизма, управление исследованием исключительно через информационный прирост
  2. Унифицированная теоретическая структура: Построение универсальной структуры алгоритма, способной одновременно обрабатывать стохастические и смешанные среды
  3. Улучшенная онлайн-оценка функций:
    • Средняя ошибка оценки: улучшение с T^{3/4}/T^{5/6} до T^{2/3}/T^{7/9}
    • Квадратичная ошибка: улучшение с T^{2/3} до √T, впервые достигнута производительность, эквивалентная оптимистичным методам в Bellman-полных MDP
  4. Решение открытой проблемы: Впервые получены границы сожаления без модели для смешанных MDP с обратной связью по бандитам

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

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

Структура DMSO: Дано пространство моделей M, пространство политик Π, пространство наблюдений O и класс функций стоимости V. На каждом раунде t:

  • Окружение выбирает модель Mt ∈ M
  • Обучающийся выбирает политику πt ∈ Π
  • Наблюдение ot ~ Mt(·|πt)
  • Цель: минимизировать сожаление Reg(π*) = Σt(VMt(π*) - VMt(πt))

Φ-ограниченная среда: Разбиение M×Π через информационные множества Φ, каждое информационное множество ϕ содержит единственную политику πϕ.

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

1. Универсальная структура (Алгоритм 1)

Основная идея заключается в решении следующей задачи о седловой точке:

min_{p∈Δ(Π)} max_{ν∈Δ(Ψ)} AIR^{Φ,D}_η(p,ν;ρt)

где мера расхождения определяется как:

D^π(ν||ρ) = E_{M~ν}E_{o~M(·|π)}[KL(ν_{ϕ}(·|π,o), ρ) + E_{ϕ~ρ}[D^π(ϕ||M)]]

2. Определение Dig-DEC

dig-dec^{Φ,D}_η = max_{ρ∈Δ(Φ)} min_{p∈Δ(Π)} max_{ν∈Δ(Ψ)} 
E_{π~p}E_{(M,π*)~ν}[V_M(π*) - V_M(π) - (1/η)E_{o~M(·|π)}[KL(ν_{ϕ}(·|π,o), ρ)] - (1/η)E_{ϕ~ρ}[D^π(ϕ||M)]]

3. Механизм апостериорного обновления

В зависимости от выбора D:

  • Средняя ошибка оценки: использование пакетного алгоритма (Алгоритм 2)
  • Квадратичная ошибка оценки: использование двухуровневого алгоритма обучения (Алгоритм 3)

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

  1. Проектирование двойного информационного прироста:
    • KL-член используется для регуляризации, избегая оптимистичного механизма
    • Член D^π захватывает различие распределений, обеспечивая строгое улучшение
  2. Устранение оптимизма: Замена члена V_ϕ(π_ϕ) в оптимистичном DEC на регуляризационный член KL(ν_{ϕ}, ρ)
  3. Улучшенные процедуры оценки:
    • Средняя ошибка: использование несмещенного оценивателя вместо смещенного
    • Квадратичная ошибка: переработка двухвременной процедуры, улучшение границы Est с T^{1/3} до константы

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

Среды для теоретической проверки

  1. Стохастическая установка:
    • Билинейный класс MDP
    • MDP с ограниченной размерностью Bellman-eluder
    • MDP с ограниченной покрываемостью
  2. Смешанная установка:
    • Смешанный билинейный класс
    • Смешанный MDP с покрываемостью
    • Известные линейные признаки вознаграждения

Показатели оценки

  • Границы сожаления: верхние границы EReg(π*)
  • Сравнение сложности: dig-dec vs o-dec vs классический DEC
  • Скорость сходимости: зависимость от степени T

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

  • Оптимистичный DEC Foster и др. (2023b)
  • Структура AIR Liu и др. (2025)
  • Классические оптимистичные методы (Jin и др. 2021, Xie и др. 2023)

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

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

Улучшения в стохастической среде (Таблица 1):

Категория установкиFoster и др. (2023b)Предложенный метод
Билинейный/BE (средняя ошибка)T^{3/4}/T^{5/6}T^{2/3}/T^{7/9}
Bellman-полный (квадратичная ошибка)T^{2/3}√T

Прорыв в смешанной среде (Таблица 2):

Категория установкиLiu и др. (2025)Предложенный метод
Билинейный (средняя ошибка)Только полная информацияT^{5/6}/T^{13/15}
Bellman-полный (квадратичная ошибка)НеприменимоT^{3/4}

Проверка теоретических преимуществ

Теорема 13: В стохастической установке dig-dec^{Φ,D}_η ≤ o-dec^{Φ,D}_η + η

Теорема 14: Построение трехрукого примера бандита, доказывающее, что в некоторых случаях:

  • Метод Foster и др.: EReg(a) ≥ Ω(√T)
  • Предложенный метод: EReg(a) ≤ 1

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

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

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

Основные направления исследований

  1. Развитие структуры DEC:
    • Foster и др. (2021b, 2023a): установление базовой теории DEC
    • Foster и др. (2023b): введение оптимистичного DEC
    • Chen и др. (2025): расширение на другие установки
  2. Исследование противодействующих MDP:
    • Neu и др. (2013): табличные противодействующие MDP
    • Luo и др. (2021): линейные противодействующие MDP
    • Liu и др. (2025): теория смешанных MDP
  3. Обучение с подкреплением без модели:
    • Jin и др. (2021): размерность Bellman-eluder
    • Xie и др. (2023): теория покрываемости

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

  1. Теоретическое единство: Первая структура DEC, одновременно обрабатывающая стохастические и смешанные среды
  2. Технические инновации: Проектирование двойного информационного прироста, устранение зависимости от оптимизма
  3. Решение проблем: Решение открытой проблемы, оставленной Liu и др. (2025)

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

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

  1. Dig-DEC обеспечивает более точную характеристику сложности, позволяя получить произвольно большие улучшения в особых случаях
  2. Устранение оптимизма позволяет алгоритму естественно обрабатывать противодействующие среды
  3. Улучшенные процедуры оценки имеют важное значение как в теории, так и на практике

Ограничения

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

Будущие направления

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

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

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

  1. Значительный теоретический вклад:
    • Предложение новой меры сложности dig-dec
    • Унифицированная обработка стохастических и противодействующих сред
    • Решение важной открытой проблемы
  2. Сильная техническая инновационность:
    • Умное проектирование двойного информационного прироста
    • Эффективное улучшение процедуры оценки
    • Передовые методы анализа
  3. Убедительные результаты:
    • Теоретические границы tight и практичны
    • Построенные примеры доказывают строгое улучшение
    • Охват множества классических типов MDP

Недостатки

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

Влияние

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

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

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

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

Ключевые ссылки включают:

  • Foster и др. (2021b, 2023a, 2023b): основы теории DEC
  • Liu и др. (2025): исследование смешанных MDP
  • Jin и др. (2021): размерность Bellman-eluder
  • Xie и др. (2023): теория покрываемости
  • Xu и Zeevi (2023): структура AIR

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