Для эпизодических 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, следует рассматривать соответствующую отдельную гарантию, а не переносить вывод основной таблицы. Препринт не устанавливает, какой алгоритм быстрее или удобнее в практическом применении.



