Новый алгоритм SPSC для нестационарных low-rank бандитов превосходит существующие методы
Исследователи из международной команды опубликовали на arXiv препринт, в котором представлен новый алгоритм SPSC (Subspace Piecewise-Stationary Contextual) для задачи low-rank линейных контекстуальных бандитов с нестационарным поведением. Работа адресует проблему, когда награды зависят от низкоразмерного латентного подпространства, которое может дрейфовать со временем.
В реальных приложениях — рекомендательные системы, клиническое дозирование, таргетирование рекламы — часто возникают две особенности: награды живут в низкоразмерном подпространстве, и это подпространство меняется. Стационарные low-rank методы ломаются при изменении подпространства, а нестационарные линейные бандиты адаптируются, но платят размерностью признаков d.
Авторы рассматривают кусочно-стационарный low-rank линейный контекстуальный бандит со скалярной обратной связью. Они доказывают, что движущееся подпространство может быть восстановлено с помощью квадратичных функционалов наград при выполнении трёх условий: известная дисперсия шума, ограниченная связь состояния и шума, и полномерная поддержка пробников. Каждое условие необходимо, а вместе они достаточны.
Разработанный алгоритм SPSC чередует изотропные пробники с оконным проекционным гребневым UCB внутри изученного r-мерного подпространства; вариант с CUSUM-типом обнаруживает границы сегментов онлайн. Достигнутое динамическое сожаление составляет O?(r?T) + O?(T^{2/3}) + O(W V_in), что заменяет ambient rate d?T на внутренний ранг r.
Эксперименты на 11 наборах данных — синтетических, UCI, MovieLens, полусинтетических клинических и логах ZOZOTOWN — показали, что SPSC превосходит нестационарные и low-rank базовые методы во всех случаях, когда d?r превосходит T^{1/6}. Это первая работа, которая характеризует границу идентифицируемости и достигает intrinsic-rank динамической скорости сожаления в данной постановке.
