Материал подготовлен автоматически по первоисточникам: ссылки на них — в конце статьи.
Исторические наблюдения можно использовать в стохастическом многоруком бандите, даже если их собрал неизвестный адаптивный алгоритм. Команда Inria и партнёрских лабораторий показала, что KL-UCB-Transfer сохраняет логарифмическое сожаление и при подходящих данных опережает обычный KL-UCB, хотя работа не рецензирована и числа в ней получили сами авторы. Это позволяет переносить логи прежней рекомендательной или экспериментальной системы без восстановления её стратегии.
Как перенести данные от неизвестной стратегии
В задаче многорукого бандита система последовательно выбирает один из вариантов и получает награду. Сожаление показывает накопленную потерю относительно стратегии, которая всегда выбирала бы лучший вариант. Обычный KL-UCB исследует варианты онлайн и оценивает их верхнюю границу с помощью расхождения Кульбака — Лейблера, то есть меры различия распределений.
KL-UCB-Transfer начинает с исторических наград по каждому варианту. Стратегия их сбора может быть неизвестной, а количество наблюдений — случайным и зависимым от предыдущих результатов. Это соответствует логам старого алгоритма, который чаще показывал перспективные варианты и почти переставал проверять слабые.
Алгоритму не нужно знать, почему старый процесс распределил показы именно так. Однако для каждого варианта требуется граница L: средняя награда в новой среде должна отличаться от исторической меньше чем на эту величину. Исторические наблюдения при этом независимы, относятся к тем же вариантам, а награда лежит в диапазоне [0, 1].
Алгоритм объединяет старые и новые наблюдения в индексе варианта. Прошлые данные сокращают необходимое онлайн-исследование, если историческая средняя награда слабого варианта вместе с допустимым сдвигом всё ещё ниже средней награды лучшего текущего варианта. Если это условие не выполняется, вариант приходится проверять почти так же, как в обычном KL-UCB.
Анализ также охватывает несколько независимых источников. Каждый получает собственную границу различия, поэтому полезные источники могут сокращать исследование, не заставляя систему считать все прошлые среды одинаковыми.
Когда перенос сокращает сожаление, а когда ломает гарантию
При корректных границах KL-UCB-Transfer сохраняет логарифмический рост сожаления. Для информативных исторических данных уменьшается коэффициент перед логарифмом: системе реже приходится выбирать заведомо слабые варианты. Если источник не помогает, асимптотическая гарантия возвращается к уровню классического KL-UCB.
При ошибочной границе возникают три режима. Если историческая оценка лучшего варианта с допустимым сдвигом остаётся выше его текущей средней награды, перенос даёт лучший коэффициент. Если эта оценка опускается ниже текущего лидера, но остаётся выше конкурента, сожаление всё ещё растёт логарифмически, однако быстрее. Если оценка падает ниже конкурента, теоретическая гарантия исчезает: алгоритм может принять слабый вариант за лучший и выбирать его почти постоянно.
В симуляциях использовали среду с четырьмя вариантами. Когда каждому варианту заранее давали по 500 наблюдений из хорошо согласованного источника, сожаление оставалось почти нулевым на горизонте 100 000 шагов. Когда те же данные собирал KL-UCB за 2000 шагов, выигрыш уменьшался: старая стратегия редко проверяла слабые варианты, хотя именно их наблюдения лучше всего помогли бы исключить лишнее исследование.
Тяжёлая ошибка в границе приводила к линейному росту сожаления при равном числе исторических наблюдений. Адаптивный источник иногда смягчал этот эффект, потому что ошибочно оценённый вариант получал мало старых данных, но это результат конкретной симуляции, а не защитный механизм алгоритма.
Меняет ли работа планы продуктовой команды
Работа меняет архитектурный выбор, если у команды уже есть логи действий и наград, но нет кода или точного описания старой стратегии. Такие данные не обязательно отбрасывать: достаточно сохранить привязку наблюдений к вариантам и обосновать границы сдвига средних наград между средами.
Главная инженерная зависимость переносится с восстановления старого алгоритма на оценку L. Для стабильных сред это может быть проще. Если продукт, аудитория или определение награды заметно изменились, слишком узкая граница превращает ускорение в систематическую ошибку и способна дать линейное сожаление.
Гарантии асимптотические и предполагают единственный лучший вариант. Верхняя и нижняя теоретические границы также не полностью совпадают для произвольного случайного числа исторических наблюдений; разрыв исчезает, когда это число достаточно хорошо концентрируется около среднего. Поэтому работа даёт основу для алгоритма, но не заменяет проверку на реальном горизонте продукта.
Практический план меняется умеренно: KL-UCB-Transfer стоит рассматривать как замену запуску с нуля там, где границу сдвига можно защитить данными или устройством процесса. Если такой границы нет, обычный KL-UCB остаётся более предсказуемой отправной точкой.
Источники
Похоже на вашу задачу?
Расскажите, что собираете. За полчаса разложим на этапы и назовём сроки — это бесплатно и ни к чему не обязывает.
