Атакующие воздействия на линейные контекстные бандиты

Алгоритмы контекстных бандитов применяются в самых разных областях — от рекламы и рекомендательных систем до клинических испытаний и образования. Во многих из этих областей злоумышленники могут быть заинтересованы в атаке на алгоритм бандита, чтобы заставить его действовать желаемым образом. Например, недобросовестный издатель рекламы может попытаться увеличить собственный доход за счёт рекламодателей; продавец может стремиться повысить видимость своих товаров или сорвать рекламную кампанию конкурента. В этой статье мы рассматриваем несколько сценариев атак и показываем, что злоумышленник может заставить линейный алгоритм контекстного бандита выбирать любую заданную ручку T - o(T) раз на горизонте из T шагов, внося при этом атакующие изменения в вознаграждения или контексты, величина которых возрастает лишь логарифмически, как O(log T). Мы также исследуем случай, когда злоумышленник заинтересован в изменении поведения алгоритма бандита только в одном контексте (например, для конкретного пользователя). Сначала мы устанавливаем достаточные условия осуществимости атаки, а затем предлагаем эффективный алгоритм её реализации. Теоретические результаты подтверждены экспериментами на синтетических наборах данных и наборах данных из реального мира.