Сравнения

Границы сожаления в adversarial MDP: сравнение трёх оценок

Сравнение ведущих оценок сожаления для adversarial MDP с неизвестной динамикой: два прежних результата, новая граница и оставшийся разрыв до нижнего масштаба.

Наш вывод

Для эпизодических adversarial MDP с неизвестной динамикой и полной информацией новая работа заявляет Õ(√(H³SAK)), меньший ведущий член, чем у двух приведённых предшественников. До масштаба нижней границы остаётся √H; это теоретическое сравнение, не практический тест.

Rosenberg и Mansour (2019)Открыть
Tiapkin et al. (2024)Открыть
Новая оценка на основе VOPOОткрыть

Сравнение

По критериям
КритерийRosenberg и Mansour (2019)Tiapkin et al. (2024)
Ведущий член, неизвестная динамика и полная информацияÕ(HS√(AK))Õ(√(H⁶SAK))
Ведущий член, неизвестная динамика и полная информацияÕ(HS√(AK))Õ(√(H³SAK))
Разрыв новой оценки до масштаба нижней границы—√H

Что выбрать под вашу задачу

Нужны гарантии для неизвестной динамики и полной информации о наградах
Новая оценка имеет меньший ведущий член, чем две приведённые прежние оценки
Нужен теоретический ориентир возможного масштаба
Нижняя граница Ω(H√(SAK)); это не алгоритм
Известная динамика или траекторная bandit feedback
Рассматривать отдельную гарантию для этого режима

Для эпизодических adversarial MDP с неизвестной динамикой и полной информацией о наградах новая работа приводит ведущий член оценки сожаления Õ(√(H³SAK)). Он меньше ведущих членов двух предшествующих оценок в этой постановке. Однако до масштаба стандартной нижней границы остаётся множитель √H: это сравнение теоретических гарантий, а не практических испытаний алгоритмов.

Источник сравнения — препринт Schlisselberg, Cohen и Mansour “Improved Regret via Variance-Aware Policy Optimization in Adversarial MDPs”, версия arXiv:2611.17469v1 от 12 ноября 2026 года.

Постановка: что именно сравнивается

H обозначает горизонт эпизода, S — общее число состояний по слоям, A — число действий, K — число эпизодов. Сравнение относится к неизвестной динамике и полной информации о наградах. В таблице приведены ведущие члены по K: логарифмические множители и аддитивные слагаемые опущены, поэтому это не полные гарантии с константами.

Нижняя граница служит теоретическим ориентиром, а не алгоритмом-конкурентом. Все строки сравнивают математические оценки для указанной постановки; они не сообщают о скорости или качестве практических реализаций.

Три верхние оценки и нижняя граница

Для Rosenberg и Mansour (2019) препринт приводит Õ(HS√(AK)), а для Tiapkin et al. (2024) — Õ(√(H⁶SAK)). Авторы называют эти две прежние оценки несопоставимыми: при разных соотношениях H и S одна не обязана быть лучше другой. Новая работа заявляет Õ(√(H³SAK)); стандартный масштаб нижней границы — Ω(H√(SAK)).

Сравнение по одинаковым критериям

Результат Динамика и обратная связь Ведущий член по K Роль в сравнении
Rosenberg и Mansour (2019) Неизвестная динамика, полная информация о наградах Õ(HS√(AK)) Предшествующая верхняя оценка
Tiapkin et al. (2024) Неизвестная динамика, полная информация о наградах Õ(√(H⁶SAK)) Предшествующая верхняя оценка
Новая оценка на основе VOPO Неизвестная динамика, полная информация о наградах Õ(√(H³SAK)) Новая верхняя оценка
Стандартная нижняя граница Теоретический ориентир для постановки Ω(H√(SAK)) Не алгоритм

При loop-free convention каждый слой решений непустой, поэтому S ≥ H. Авторы указывают улучшение новой оценки относительно Rosenberg и Mansour в √(S/H) раз, а относительно Tiapkin et al. — в H√H раз. До масштаба нижней границы для новой оценки остаётся множитель √H. Следовательно, из таблицы можно заключить, что ведущий член новой гарантии меньше обоих прежних в заявленном смысле, но не что достигнут нижний предел.

Как VOPO меняет оценку

Механизм состоит из variance-aware анализа и нового Stability-Matching Bonus (SMB), применённых в алгоритме оптимизации политики VOPO. Далее авторы используют редукцию от неизвестной динамики к известной. Она применима к алгоритмам, у которых политика на шаге h вычисляется только по информации с шагов h+1 и далее.

Для VOPO при известной динамике и полной информации авторы заявляют Õ(√(H³K)). До целевого масштаба Õ(H√K) здесь также остаётся √H; этот разрыв наследуется оценкой для неизвестной динамики. Именно анализ с учётом дисперсии, бонус SMB и подходящая редукция объясняют полученную гарантию — не сравнительные замеры времени выполнения.

Границы применимости

Основное сравнение относится только к эпизодическим adversarial MDP с неизвестной динамикой и полной информацией о наградах. Работа отдельно рассматривает известную динамику с траекторной bandit feedback и приводит для VOPO оценку Õ(√(H²SAK)). Это другой режим обратной связи, поэтому его нельзя напрямую поставить в таблицу вместо оценки для полной информации и неизвестной динамики.

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

Что означают оценки для заданной постановки

Для читателя, которому нужны гарантии именно при неизвестной динамике и полной информации о наградах, таблица показывает, как новая верхняя оценка соотносится с двумя прежними и с нижним ориентиром. По заявленным ведущим членам новая оценка лучше обеих прежних, но разрыв √H до нижней границы сохраняется.

Если интересуют известная динамика или траекторная bandit feedback, следует рассматривать соответствующую отдельную гарантию, а не переносить вывод основной таблицы. Препринт не устанавливает, какой алгоритм быстрее или удобнее в практическом применении.

Вопросы и ответы

Что означают H, S, A и K?

H — горизонт эпизода, S — общее число состояний по слоям, A — число действий, K — число эпизодов.

Является ли новая оценка практическим бенчмарком?

Нет. Это теоретическая гарантия, а не независимое практическое сравнение.

Достигает ли новая оценка масштаба нижней границы?

Нет. По оценке авторов, остаётся разрыв √H.