- Зеркальный спуск с относительной гладкостью в пространствах с мерой, с применением к Sinkhorn и EM(arXiv)
Автор:Пьер-Сирил Обен-Франковски, Анна Корба, Флавьен Леже
Аннотация: многие задачи машинного обучения можно сформулировать как оптимизацию выпуклого функционала в пространстве мер. В этой статье изучается сходимость алгоритма зеркального спуска в этой бесконечномерной обстановке. Определяя дивергенции Брегмана через производные по направлениям, получаем сходимость схемы для относительно гладких и сильно выпуклых пар функционалов. Применяя наш результат к совместным распределениям и дивергенции Кульбака — Лейблера (КЛ), мы показываем, что первичные итерации Синкхорна для энтропийного оптимального транспорта в непрерывном режиме соответствуют зеркальному спуску, и получаем новое доказательство его (суб)линейной сходимости. Мы также показываем, что максимизацию ожидания (EM) всегда можно формально записать как зеркальный спуск, и при оптимизации скрытого распределения при фиксации смесей мы получаем сублинейные скорости сходимости
2. Альтернативный зеркальный спуск для ограниченных игр Min-Max (arXiv)
Автор: Андре Вибисоно, Молей Тао, Георгиос Пилиурас
Аннотация: В этой статье мы изучаем билинейные игры с нулевой суммой для двух игроков с ограниченными пространствами стратегий. Примером естественного появления таких ограничений является использование смешанных стратегий, которые соответствуют вероятностному симплексному ограничению. Мы предлагаем и анализируем алгоритм альтернативного зеркального спуска, в котором каждый игрок по очереди выполняет действия, следуя алгоритму зеркального спуска для оптимизации с ограничениями. Мы интерпретируем чередующийся зеркальный спуск как переменную дискретизацию косоградиентного потока в дуальном пространстве и используем инструменты выпуклой оптимизации и модифицированной функции энергии, чтобы установить ограничение O (K−2/3) на его среднее сожаление после K итераций. Это количественно подтверждает лучшее поведение алгоритма, чем одновременная версия алгоритма зеркального спуска, который, как известно, расходится и дает среднюю границу сожаления O (K−1/2). В частном случае неограниченной настройки наши результаты восстанавливают поведение алгоритма переменного градиентного спуска для игр с нулевой суммой, которое было изучено в (Bailey et al., COLT 2020).
3. Децентрализованный оптимистичный гиперполитический зеркальный спуск: беспроигрышное обучение в марковских играх (arXiv)
Автор:Вэньхао Чжань, Джейсон Д. Ли, Чжуоран Ян
Аннотация: мы изучаем децентрализованное политическое обучение в марковских играх, в которых мы управляем одним агентом, чтобы играть с нестационарными и, возможно, враждебными противниками. Наша цель — разработать безотказный алгоритм онлайн-обучения, который (i) предпринимает действия на основе локальной информации, наблюдаемой агентом, и (ii) способен найти наилучшую политику задним числом. Для такой задачи нестационарные переходы состояний из-за меняющегося противника представляют серьезную проблему. В свете недавнего результата \citep{liu2022learning}, мы сосредоточились на настройке, в которой предыдущая политика оппонента раскрывается агенту для принятия решения. С такой информационной структурой мы предлагаем новый алгоритм, \underline{D}децентрализованную \underline{O}оптимистическую рекламу\underline{R}политику m\underline{I}ошибку de\underline{S}cent (DORIS), которая достигает K−−√-сожаления в контексте аппроксимации общей функции, где K — количество эпизодов. Более того, когда все агенты принимают DORIS, мы доказываем, что их смешанная политика представляет собой приближенное грубо коррелированное равновесие. В частности, DORIS поддерживает \textit{гиперполитику}, которая представляет собой распределение по пространству политик. Гиперполитика обновляется посредством зеркального спуска, где направление обновления определяется оптимистичным вариантом оценки политики методом наименьших квадратов. Кроме того, чтобы проиллюстрировать силу нашего метода, мы применяем DORIS к MDP с ограничениями и векторными значениями, которые можно сформулировать как марковские игры с нулевой суммой с фиктивным противником.
