Почему одной стратегии мало: адаптивные портфели политик для устойчивых MDP
Классические марковские процессы принятия решений (MDP) предполагают, что динамика среды известна точно. На практике это почти никогда не так: мы можем лишь очертить множество правдоподобных сценариев. Устойчивые MDP (robust MDP) подходят к этому радикально — ищут одну политику, которая будет работать достаточно хорошо при самом плохом из возможных переходов. Но у такого подхода есть скрытая цена: он настроен на худший случай и потому часто оказывается чрезмерно консервативным.
Особенно заметно это в ситуациях, когда неизвестность со временем уменьшается. Среда разворачивается перед агентом, и часть её динамики становится наблюдаемой и частично идентифицируемой. Оптимальная политика, вычисленная до развёртывания, не использует эту новую информацию. По сути, мы продолжаем играть в худший случай даже там, где уже знаем, что он не реализовался. Исследователи из Университета Твенте и Антверпена — Kasper Engelen, Sebastian Junges, Guillermo A. Pérez и Marnix Suilen — в своей работе «Adaptive Policy Portfolios for Robust Markov Decision Processes» (arXiv:2608.17929, cs.AI/cs.LO) предлагают более гибкий подход.
Адаптивные портфели: набор политик вместо одной
Вместо одной устойчивой политики авторы рассматривают портфель политик — конечный набор рандомизированных политик без памяти, которые синтезируются заранее, офлайн. В дополнение к ним используется лёгкий онлайн-селектор, который в процессе работы выбирает наиболее подходящую политику из портфеля. Это напоминает ансамбль моделей в машинном обучении, но с чёткой теоретической постановкой.
Ключевой метрикой качества такого портфеля становится устойчивый регрет (robust regret). Для каждой конкретной среды из множества правдоподобных он измеряет, насколько политика, выбранная онлайн-селектором, уступает той идеальной политике, которую мы бы построили, если бы знали эту среду заранее. Иными словами, портфель считается хорошим, если его лучший участник достаточно близок к оптимуму для любой среды. Такой взгляд переносит акцент с гарантий в худшем случае на цену адаптации.
Похожие идеи ранее разрабатывались Ghavamzadeh et al. (2016), но с фокусом на приближённые методы и релаксации для безопасного улучшения политик. Новая работа существенно продвигает теоретические основы этой области.
Сложность сертификации и синтеза
Портфель — это не просто инженерная эвристика. Авторы дают аккуратный теоретико-сложностный анализ задач, которые возникают при работе с портфелями.
Первая задача — сертификация заданного портфеля: можно ли гарантировать, что для всех правдоподобных сред найдётся политика с приемлемым регретом? Оказывается, эта задача является ∀R-полной уже для детерминированных портфелей в ациклических (s,a)-прямоугольных RMDP. Это означает, что проверка качества даже небольшого набора политик — вычислительно тяжёлая задача, сравнимая по сложности с решением систем вещественных неравенств.
Ещё жёстче задача синтеза портфеля ограниченного размера (unary-bounded). Для общих рациональных политопов она оказывается ∃∀R-полной — даже при фиксированном коэффициенте дисконтирования и ациклической динамике. Такая сложность указывает, что простых комбинаторных алгоритмов здесь не существует: проблема сочетает в себе и дискретный перебор, и алгебраическую сложность. Примечательно, что даже случай одной политики нетривиален и «дорог» по обеим осям.
Как это приблизить к практике?
Полученные результаты о сложности могут отпугнуть, но авторы не останавливаются на негативных выводах. Они предлагают конкретную офлайн-конструкцию портфеля, которая допускает специализацию во время выполнения (runtime specialization). Смысл в том, чтобы заранее подготовить набор политик, а уже в процессе взаимодействия со средой быстро настраивать выбор под текущее наблюдение. Такой подход позволяет совместить строгие гарантии с практической гибкостью.
Вывод прост: в задачах, где неизвестность частично раскрывается со временем, одна зафиксированная стратегия заведомо слабее адаптивного набора. Портфель политик платит более высокой вычислительной сложностью, но зато даёт право на ошибку и способность переключаться по мере поступления данных. Это важный шаг на пути от чисто консервативных методов к интеллектуальным системам принятия решений в условиях неопределённости.
