Краткое содержание

arXiv:2510.17067v2 Announce Type: replace-cross Аннотация: Регрет-матчинг (RM) и его современные варианты являются фундаментальным онлайн-алгоритмом, который лежал в основе многих прорывных результатов в области ИИ по решению эталонных игр с нулевой суммой, таких как покер. Однако, что удивительно, до сих пор о его сходимости за пределами двухагентных игр с нулевой суммой известно довольно мало. Например, проблема сходимости регрет-матчинга к равновесиям Нэша в потенциальных играх оставалась открытой на протяжении двух десятилетий. Даже за пределами игр, варианты RM можно попытаться использовать для общих задач условной оптимизации. Недавние эмпирические данные свидетельствуют о том, что они — в частности, регрет-матчинг$^+$ (RM$^+$) — демонстрируют высокую производительность на эталонных задачах условной оптимизации, превосходя традиционные алгоритмы типа градиентного спуска. Мы показываем, что RM$^+$ сходится к $\epsilon$-точке Куна-Таккера за $O_\epsilon(1/\epsilon^4)$ итераций, впервые устанавливая, что это корректный и быстрый оптимизатор первого порядка.