EN KR JP CN RU IN
ICML

Враждебные атаки на комбинаторные многорукие бандиты

Authors Rishab Balasubramanian, Jiawei Li, Prasad Tadepalli, Huazheng Wang, Qingyun Wu, Haoyu Zhao ; Proceedings of the 41st International Conference on Machine Learning, PMLR 235:2505-2526
ISOM Posted 2026-03-19 18:49 UTC
Read Time 2M
Open PDF Open MICCAI page

Предыстория и академическая родословная

Истоки и академическая родословная

Проблема, рассматриваемая в данной статье, «Враждебные атаки на комбинаторные многорукие бандиты (CMAB)», возникает из слияния двух важных исследовательских областей: многоруких бандитов и изучения враждебной устойчивости в машинном обучении. Фундаментальная структура многоруких бандитов (MAB), впервые исследованная Ауэром (Auer, 2002), моделирует последовательное принятие решений, где агент должен стратегически балансировать между исследованием новых вариантов и использованием известных прибыльных для максимизации совокупного вознаграждения за период. Эта структура была широко исследована и применена в различных областях.

Более обобщенная версия MAB, известная как комбинаторные многорукие бандиты (CMAB), получила значительное распространение благодаря широкому спектру реальных приложений, включая онлайн-рекламу, рекомендательные системы и максимизацию влияния (Liu & Zhao, 2012; Kveton et al., 2015). В CMAB решение агента включает выбор комбинации базовых рук (называемых «супер-рукой») в каждом раунде, а не одной руки. Этот комбинаторный аспект делает компромисс между исследованием и использованием значительно более сложным, в основном потому, что количество возможных супер-рук может экспоненциально расти с количеством базовых рук.

Точное происхождение этой конкретной проблемы, которая включает переопределение и переоценку понятия «атакуемости» для CMAB, проистекает из недавних выводов о том, что алгоритмы MAB и их варианты подвержены враждебным атакам, в частности «атакам отравления вознаграждения» (Jun et al., 2018; Liu & Shroff, 2019). При таких атаках противник наблюдает выбранную руку и обратную связь по вознаграждению, затем тонко изменяет эту обратную связь, чтобы направить обучающий алгоритм к определенной целевой руке, которая служит интересам противника. Хотя концепция атакуемости ранее применялась к стандартным настройкам MAB (Wang et al., 2022), прямое распространение этого определения на CMAB оказалось проблематичным. Основным ограничением предыдущих подходов было то, что прямое применение определения атакуемости MAB к CMAB привело к граничной стоимости, которая была сублинейной по временному горизонту $T$, но экспоненциальной по количеству базовых рук $m$. Эта экспоненциальная зависимость от $m$ крайне нежелательна в практических сценариях, часто приводя к тривиальным результатам, когда стоимость атаки может даже превысить общий временной горизонт $T$. Эта неадекватность подчеркнула, что первоначальное понятие атакуемости было недостаточным, тем самым требуя нового, более подходящего определения для CMAB, которое данная статья стремится предоставить.

Интуитивные термины предметной области

  • Многорукий бандит (MAB): Представьте, что вы находитесь в казино перед рядом игровых автоматов, каждый из которых имеет неизвестную среднюю выплату. Ваша цель — максимизировать общий выигрыш за множество игр. В каждом ходу вы выбираете один автомат, дергаете за рычаг и получаете вознаграждение. Вы должны научиться, какие автоматы хороши (использовать), продолжая пробовать другие, чтобы обнаружить потенциально лучшие (исследовать).
  • Комбинаторный многорукий бандит (CMAB): Это похоже на сценарий MAB, но вместо выбора только одного игрового автомата за ход вы выбираете группу или комбинацию автоматов для одновременной игры. Например, вы можете решить играть автоматами 2, 5 и 8 вместе. Эта задача намного сложнее, потому что существует гораздо больше возможных комбинаций автоматов, чем отдельных.
  • Супер-рука: В контексте CMAB «супер-рука» — это конкретный набор или комбинация отдельных игровых автоматов, которые вы выбираете для игры в данном раунде. Она представляет собой ваше полное действие на этот ход.
  • Базовая рука: Это отдельные, фундаментальные игровые автоматы, из которых состоят комбинации. Если вы выбираете супер-руку, состоящую из автоматов 2, 5 и 8, то 2, 5 и 8 — это отдельные «базовые руки», которые были частью выбранной вами супер-руки.
  • Атака отравления вознаграждения: Это описывает ситуацию, когда злоумышленник тайно изменяет информацию о вознаграждении, которую вы получаете от игровых автоматов. Их цель — обмануть ваш процесс принятия решений, заставив вас неоднократно выбирать определенную, часто менее прибыльную, комбинацию (их «целевую супер-руку»), делая ее выплаты кажущимися лучше, чем они есть на самом деле, или делая действительно хорошие комбинации хуже.

Таблица обозначений

Обозначение Описание
$m$ Общее количество базовых рук.
$\mathcal{S}$ Множество всех возможных супер-рук (комбинаций базовых рук).
$S \in \mathcal{S}$ Конкретная супер-рука.
$T$ Общий временной горизонт (количество раундов) для задачи бандита.
$\mu = (\mu_1, \ldots, \mu_m)$ Вектор истинных средних вознаграждений для всех $m$ базовых рук.
$r_S(\mu)$ Ожидаемое вознаграждение супер-руки $S$ при заданном векторе истинных средних вознаграждений $\mu$.
$O_S$ Множество базовых рук, которые могут быть вероятностно задействованы при выборе супер-руки $S$.
$\mu \odot O_S$ Поэлементное произведение $\mu$ и бинарного вектора, представляющего $O_S$, эффективно обнуляющее средние вознаграждения для базовых рук, не входящих в $O_S$.
$\Delta_S$ «Разрыв» для супер-руки $S$, количественно определяющий ее атакуемость (Определение 3.5).
$M$ Множество целевых супер-рук, которые противник желает, чтобы алгоритм бандита выбрал.
$\Delta_M$ Общий «разрыв» для целевого множества $M$, определяемый как $\max_{S \in M} \Delta_S$.
$C(T)$ Общая стоимость атаки, понесенная противником за временной горизонт $T$.
$o(T)$ Функция, растущая медленнее, чем $T$, т.е. $\lim_{T \to \infty} o(T)/T = 0$.
$p^*$ Параметр, связанный с минимальной вероятностью задействования базовой руки (Определение 3.1).
$K$ Параметр, специфичный для задачи, часто связанный с количеством базовых рук в супер-руке или границами сожаления.
$\gamma, \gamma'$ Положительные константы, связанные с сублинейным ростом сожаления и стоимости атаки.
$\hat{\mu}_i^{(t)}$ Оценка эмпирического среднего вознаграждения для базовой руки $i$ в раунде $t$.
UCB Верхняя доверительная граница (Upper Confidence Bound), используемая алгоритмами бандитов для исследования-использования.

Определение проблемы и ограничения

Основная постановка задачи и дилемма

В статье рассматривается критический пробел в понимании уязвимости комбинаторных многоруких бандитов (CMAB) к враждебным атакам.

Входные данные/Текущее состояние:
Отправной точкой является стандартная задача CMAB, в которой обучающийся агент последовательно выбирает «супер-руки», состоящие из «базовых рук», в течение временного горизонта $T$. В каждом раунде агент наблюдает обратную связь (результаты задействованных базовых рук) и получает вознаграждение, стремясь максимизировать совокупное вознаграждение. Текущее состояние исследований признает, что многорукие бандиты (MAB) и их варианты подвержены «атакам отравления вознаграждения». При таких атаках противник наблюдает действия агента и обратную связь, затем тонко изменяет наблюдаемые вознаграждения. Цель противника — направить алгоритм бандита на последовательный выбор определенной «целевой руки» (той, которая служит интересам противника) почти во всех раундах ($T - o(T)$ раз), при этом понеся сублинейную стоимость атаки $o(T)$ за временной горизонт $T$.

Желаемый результат/Целевое состояние:
Основная цель статьи — установить «хорошее понятие для захвата уязвимости и устойчивости CMAB», которое имеет практический смысл. Это новое определение, названное «полиномиальной атакуемостью», призвано точно определить, когда экземпляр CMAB может быть эффективно атакован. В соответствии с этим уточненным определением успешная атака должна не только достичь своей цели (направление агента на выбор целевой руки в течение $T - o(T)$ раз), но и сделать это со стоимостью атаки, которая является сублинейной по временному горизонту $T$ И, что крайне важно, полиномиальной по количеству базовых рук $m$ и другим релевантным факторам задачи (например, $1/p^*$, $K$).

Отсутствующее звено/Математический пробел:
Точным отсутствующим звеном является надежное и практичное определение «атакуемости» для CMAB. Предыдущие определения, напрямую заимствованные из более простых настроек MAB, оказываются неадекватными для CMAB. Это связано с тем, что комбинаторная природа CMAB означает, что количество возможных «супер-рук» может быть экспоненциально большим по $m$, количеству базовых рук. Применение старого определения подразумевало бы экспоненциальную стоимость атаки по $m$, делая ее «нежелательной» и «тривиальной» на практике, поскольку такая стоимость могла бы легко превысить общий временной горизонт $T$. Статья устраняет этот пробел, вводя «полиномиальную атакуемость», которая явно ограничивает стоимость атаки полиномиальной функцией от $m$, тем самым делая понятие атакуемости релевантным и практичным для CMAB. Математически это включает переход от общей стоимости $C(T) = o(T)$ к более специфической $C(T) = O(\text{poly}(m, 1/p^*, K) \cdot T^{1-\gamma'})$ для некоторого $\gamma' > 0$, где $m$ — количество базовых рук, $p^*$ связано с вероятностями задействования, а $K$ — параметр, специфичный для задачи. Статья также определяет «разрыв» $\Delta_S$ (Определение 3.5) для каждой супер-руки $S$, который количественно определяет разницу между ее ожидаемым вознаграждением и максимальным ожидаемым вознаграждением любой другой супер-руки, служа ключевым математическим индикатором атакуемости.

Дилемма:
Центральная дилемма, которая поставила в тупик предыдущих исследователей, — это компромисс между комбинаторной сложностью CMAB и практичностью стоимости атаки. Хотя заманчиво напрямую распространять концепции атаки MAB, это приводит к экспоненциальной стоимости по количеству базовых рук $m$, делая любое определение «успешной» атаки бессмысленным в реальных сценариях. Статья подчеркивает неожиданный и болезненный компромисс: атакуемость экземпляра CMAB является не только внутренним свойством, но и «также зависит от того, известен или неизвестен экземпляр бандита противнику». Это означает, что стратегия атаки, эффективная в условиях белого ящика (где параметры среды известны), может полностью провалиться в условиях черного ящика (где параметры неизвестны), делая универсальную стратегию атаки неуловимой, а проблему «безумно сложной» на практике.

Ограничения и режимы отказа

Проблема эффективной и осмысленной атаки на экземпляры CMAB ограничена несколькими суровыми, реалистичными барьерами:

  1. Комбинаторный взрыв супер-рук: Наиболее значительным ограничением является огромное количество возможных «супер-рук», которое может быть экспоненциальным по количеству базовых рук $m$. Эта комбинаторная сложность означает, что любая стратегия атаки, требующая исследования или манипулирования всеми супер-руками, повлечет за собой экспоненциальную стоимость, нарушая практическое требование полиномиальной атакуемости. Это делает прямое применение стратегий атаки MAB непрактичным и приводит к «тривиальным результатам».
  2. Знание противником среды: Критическим ограничением является доступ противника к основным параметрам экземпляра CMAB, таким как распределения вознаграждений ($\mu$) и распределения результатов базовых рук.
    • Известная среда (белый ящик): Если противник обладает полным знанием этих параметров, он может разрабатывать высокоцелевые и эффективные атаки.
    • Неизвестная среда (черный ящик): В более реалистичной среде черного ящика противник не обладает этим предварительным знанием. Это вынуждает противника проводить исследование для оценки параметров, что само по себе влечет за собой затраты и может сделать атаки намного сложнее или даже невозможными. Статья демонстрирует это на «сложном примере» (Теорема 4.1), где экземпляр полиномиально атакуем, если среда известна, но полиномиально неатакуем, если она неизвестна. Это подчеркивает серьезный практический барьер.
  3. Бюджет стоимости атаки: Противник действует в рамках строгого бюджетного ограничения: стоимость атаки должна быть сублинейной по временному горизонту $T$ и, согласно новому определению, полиномиальной по количеству базовых рук $m$ и другим факторам. Превышение этого бюджета считается режимом отказа, поскольку атака не будет считаться «эффективной» или «успешной».
  4. Полубандитская обратная связь: Обучающийся агент в CMAB получает «полубандитскую обратную связь», что означает, что он наблюдает результаты только от базовых рук, задействованных выбранной супер-рукой, а не от всех базовых рук. Эта частичная наблюдаемость ограничивает информацию, доступную противнику, затрудняя точную оценку вознаграждений или их эффективное манипулирование, особенно в неизвестных средах.
  5. Устойчивость алгоритма и границы сожаления: Атака должна быть успешной против обучающих алгоритмов (таких как CUCB), которые разработаны для минимизации сожаления, часто с теоретическими границами сожаления $O(\text{poly}(m, 1/p^*, K) \cdot T^{1-\gamma})$. Противник должен преодолеть присущие алгоритму механизмы обучения и исследования без чрезмерных затрат.
  6. Ограничения оракула: Задачи CMAB часто полагаются на вычислительные оракулы (например, для поиска оптимальных супер-рук). Если эти оракулы являются приближенными, а не точными (например, $(\alpha, \beta)$-приближенные оракулы), это может внести дополнительные сложности для противника, поскольку поведение алгоритма может отличаться от того, что произвел бы точный оракул, потенциально влияя на эффективность атаки.

Почему такой подход

Неизбежность выбора

Выбор авторов определить «полиномиальную атакуемость» для комбинаторных многоруких бандитов (CMAB) был не просто вариантом, а необходимостью, обусловленной присущими ограничениями применения традиционных понятий атакуемости к этой сложной области. Момент, когда авторы осознали, что передовые (SOTA) методы из стандартных многоруких бандитов (MAB) недостаточны, четко изложен во введении. Они отмечают, что «прямое применение концепции атакуемости MAB к CMAB заманчиво... Однако это приводит к сублинейной граничной стоимости по T, но экспоненциальной по количеству базовых рук m». Эта экспоненциальная зависимость от $m$ (количество базовых рук) явно названа «нежелательной» и способной превысить временной горизонт $T$, делая результаты «тривиальными» (стр. 1).

Это критическое наблюдение подчеркнуло, что комбинаторный взрыв, присущий CMAB, где количество супер-рук может быть экспоненциальным по $m$, фундаментально нарушил предположения предыдущих определений атакуемости MAB. Было необходимо решение, которое могло бы предоставить значимые гарантии в рамках практических вычислительных ограничений. Таким образом, предложенное определение полиномиальной атакуемости, которое требует, чтобы стоимость атаки была не только сублинейной по временному горизонту $T$, но и полиномиальной по количеству базовых рук $m$ и другим факторам, стало единственным жизнеспособным решением для предоставления управляемой и релевантной структуры для анализа враждебных атак на CMAB.

Сравнительное превосходство

Качественное превосходство этого подхода обусловлено его способностью решать комбинаторную сложность CMAB, проблему, которую предыдущие золотые стандарты атакуемости MAB не смогли преодолеть. Помимо простых метрик производительности, структурное преимущество заключается в преобразовании неразрешимой задачи с экспоненциальной стоимостью в разрешимую задачу с полиномиальной стоимостью.

В частности, «первоначальное понятие атакуемости» для MAB, примененное к CMAB, привело к «экспоненциальной стоимости по m» (стр. 1). Это означало, что по мере роста количества базовых рук стоимость атаки быстро становилась астрономически большой, делая любые теоретические гарантии практически бессмысленными. Новое определение «полиномиальной атакуемости» (Определение 3.1) фундаментально меняет это, требуя, чтобы стоимость атаки была ограничена полиномиальной функцией от $m$, $1/p^*$ и $K$ (где $p^*$ связано с вероятностями задействования, а $K$ — фактор из границ сожаления). Это качественный скачок, поскольку он позволяет проводить осмысленный анализ атакуемости в высокоразмерных настройках CMAB, где количество супер-рук экспоненциально.

Более того, статья предоставляет достаточное и необходимое условие для полиномиальной атакуемости (Теорема 3.6), основанное на «разрыве» $\Delta_M$ (Определение 3.5). Эта теоретическая характеристика предлагает глубокое структурное понимание того, почему определенные экземпляры CMAB атакуемы или неатакуемы, а не просто измеряет, насколько хорошо выполняется атака. Она обеспечивает четкую границу для внутренней устойчивости, что является значительным качественным преимуществом по сравнению с методами, которые могут предлагать только эмпирическую производительность на конкретных экземплярах. Этот метод эффективно снижает сложность памяти с неявной $O(2^m)$ (из-за экспоненциальных супер-рук) до полиномиальной зависимости от $m$, делая задачу анализируемой.

Соответствие ограничениям

Выбранный метод определения «полиномиальной атакуемости» идеально соответствует основным ограничениям задачи CMAB, особенно проблеме, создаваемой ее комбинаторной природой. Основное ограничение, как подчеркивается в определении проблемы, заключается в том, что количество возможных супер-рук в CMAB может быть «экспоненциальным по m» (стр. 1). Прямое применение определений атакуемости MAB, которые не учитывают этот экспоненциальный рост, приводит к «тривиальным результатам», поскольку стоимость атаки также будет расти экспоненциально с $m$.

«Слияние» суровых требований задачи и уникальных свойств решения очевидно в Определении 3.1. Это определение явно налагает ограничение, что успешная атака должна иметь стоимость, которая является полиномиальной по количеству базовых рук m (и другим факторам, таким как $1/p^*$ и $K$), в дополнение к тому, что она сублинейна по временному горизонту $T$. Это гарантирует, что понятие атакуемости остается осмысленным и практичным даже для больших экземпляров CMAB.

Кроме того, статья фокусируется на «атаках отравления вознаграждения» (Раздел 2.2), при которых противник изменяет наблюдаемые вознаграждения. Предлагаемый алгоритм атаки (Алгоритм 1) и условия атакуемости (Теорема 3.6) специально адаптированы к этой модели угрозы, гарантируя, что решение соответствует определенным возможностям и ограничениям противника. Метод также учитывает природу «полубандитской обратной связи» CMAB, где наблюдаются только результаты задействованных базовых рук, интегрируя эту структуру обратной связи в стратегию атаки.

Отклонение альтернатив

В статье четко изложены причины отклонения или модификации существующих подходов, в первую очередь сосредоточенные на прямом применении обычных определений атакуемости MAB. Основной аргумент их неадекватности заключается в том, что они приводят к «экспоненциальной стоимости по m» при применении к CMAB (стр. 1). Это не незначительная проблема производительности, а фундаментальный недостаток, который делает результаты «нежелательными» и «тривиальными» на практике. Комбинаторная природа CMAB с ее экспоненциально большим количеством супер-рук означает, что стоимость атаки, масштабирующаяся экспоненциально с количеством базовых рук, просто не является осуществимой или осмысленной. Следовательно, авторам пришлось ввести новое определение, которое требует полиномиальной стоимости по $m$.

Кроме того, статья косвенно отклоняет другие связанные направления исследований как не напрямую применимые или недостаточные для их конкретной постановки задачи:

  1. Существующие понятия атакуемости MAB: Как подробно описано выше, они были признаны недостаточными из-за экспоненциальной стоимости по $m$.
  2. Враждебные атаки на обучение с подкреплением (RL): Хотя и связанные, статья отмечает, что «ни одна из существующих работ не анализировала атакуемость данного экземпляра» (стр. 2, Раздел 1.2). Это указывает на то, что, хотя атаки RL являются широкой областью, они не предоставили характеристику атакуемости на уровне экземпляра, которую искала данная статья для CMAB.
  3. Устойчивые к искажениям бандиты: Это альтернативное направление исследований, которое изучает устойчивость к атакам отравления, упоминается, но косвенно отклоняется как прямое решение, поскольку оно часто рассматривает «более слабые модели угроз» (стр. 2, Раздел 1.2). Например, некоторые модели предполагают непредвзятого противника или ограничивают искажения только увеличением результатов. В отличие от этого, модель угрозы данной статьи позволяет противнику увеличивать или уменьшать результаты, делая проблему более общей и сложной, чем та, которую обычно решают алгоритмы устойчивых к искажениям бандитов. Эта более широкая способность противника требует более надежной структуры атакуемости.
Figure 3. An unattackable shortest path from s to t in the Flickr dataset. Optimal path: (s, a, b, e, t). Target path: (s, a, v, c, d, t). The cost on (b, c, d, t) is larger than the number of edges on (b, e, t), and the attacker cannot fool the algorithm to play the target path

Математический и логический механизм

Главное уравнение

Абсолютно ключевым уравнением, определяющим атакуемость экземпляра комбинаторного многорукого бандита (CMAB) в данной статье, является определение «разрыва» для супер-руки $S$, представленное в Определении 3.5. Этот разрыв количественно определяет внутреннюю уязвимость или устойчивость экземпляра CMAB к атакам отравления вознаграждения.

$$ \Delta_S := r_S(\mu) - \max_{S' \neq S} r_{S'}(\mu \odot O_S) $$

Для множества $M$ целевых супер-рук общий разрыв определяется как $\Delta_M = \max_{S \in M} \Delta_S$. Теорема 3.6 затем устанавливает, что если $\Delta_M > 0$, то экземпляр CMAB полиномиально атакуем, а если $\Delta_M < 0$, то он полиномиально неатакуем.

Поэлементный разбор

Давайте разберем главное уравнение по частям, чтобы понять его математическое определение, физическую/логическую роль и обоснование операторов.

  • $\Delta_S$:

    • Математическое определение: Это скалярное значение, представляющее разницу между ожидаемым вознаграждением конкретной целевой супер-руки $S$ и максимальным ожидаемым вознаграждением любой другой супер-руки $S'$, оцененным при модифицированном векторе средних вознаграждений.
    • Физическая/логическая роль: Он действует как «индикатор уязвимости» для конкретной целевой супер-руки $S$. Положительное $\Delta_S$ подразумевает, что целевая супер-рука $S$ внутренне «лучше», чем любая альтернатива $S'$, если эти альтернативы оцениваются только по базовым рукам, которые сама $S$ наблюдает. Это предполагает потенциальный путь для противника, чтобы направить алгоритм бандита к $S$. Если $\Delta_S$ отрицательно, это указывает на то, что $S$ не является лучшим выбором даже при такой конкретной оценке, что затрудняет атаку.
    • Почему вычитание и максимум: Вычитание используется для количественного определения «преимущества» $S$ над ее лучшей альтернативой. Оператор $\max$ идентифицирует сильнейшего конкурента для $S$ в контексте оценки противника, гарантируя, что разрыв действительно отражает самую сложную альтернативу для преодоления.

  • $r_S(\mu)$:

    • Математическое определение: Обозначает ожидаемое вознаграждение при выборе супер-руки $S$, когда истинный вектор средних вознаграждений всех базовых рук равен $\mu$.
    • Физическая/логическая роль: Это истинная, неискаженная ожидаемая производительность супер-руки $S$. Она представляет то, чего алгоритм бандита должен был бы достичь в идеале, если бы не было противника.
    • Почему такая форма: Это стандартный способ представления ожидаемой полезности действия (супер-руки) в задачах бандитов, зависящий от основных истинных распределений вознаграждений.

  • $\mu$:

    • Математическое определение: Это $m$-мерный вектор $(\mu_1, \mu_2, \ldots, \mu_m)$, где $\mu_i = E_{X \sim D}[X_i^{(t)}]$ — истинное среднее вознаграждение базовой руки $i$.
    • Физическая/логическая роль: Этот вектор представляет истинные, основные распределения вознаграждений всех отдельных базовых рук в среде CMAB. Это истина, которую алгоритм бандита пытается оценить, а противник пытается манипулировать.

  • $\max_{S' \neq S}$:

    • Математическое определение: Этот оператор находит максимальное значение среди ожидаемых вознаграждений всех супер-рук $S'$, которые не являются целевой супер-рукой $S$.
    • Физическая/логическая роль: Это идентифицирует «лучшую альтернативу» целевой супер-руке $S$ с точки зрения стратегии манипулирования противника. Противник хочет, чтобы $S$ казалась лучше всех других вариантов, поэтому он должен учитывать сильнейшего конкурента.

  • $S'$:

    • Математическое определение: Представляет любую супер-руку в пространстве действий $\mathcal{S}$, отличную от целевой супер-руки $S$.
    • Физическая/логическая роль: Это альтернативные действия, которые алгоритм бандита может выбрать вместо целевой супер-руки $S$. Цель противника — сделать эти альтернативы менее привлекательными.

  • $\mu \odot O_S$:

    • Математическое определение: Это поэлементное произведение (произведение Адамара) между вектором истинных средних вознаграждений $\mu$ и бинарным вектором $O_S$. Вектор $O_S$ имеет значения $1$ для базовых рук, которые могут быть задействованы супер-рукой $S$ (т.е. $i \in O_S$), и $0$ в противном случае.
    • Физическая/логическая роль: Этот модифицированный вектор средних представляет гипотетический сценарий, в котором вознаграждения базовых рук, не наблюдаемых целевой супер-рукой $S$, фактически «обнуляются» или игнорируются. Это важно, поскольку стратегия атаки противника (Алгоритм 1) часто включает установку наблюдаемых вознаграждений нецелевых базовых рук в 0. Оценивая $S'$ при $\mu \odot O_S$, статья моделирует эффект манипулирования противника на альтернативные супер-руки. Она спрашивает: «Если мы рассматриваем только базовые руки, которые $S$ может «видеть», насколько хороши другие супер-руки $S'$?»
    • Почему поэлементное произведение: Поэлементное произведение с $O_S$ эффективно фильтрует вектор $\mu$, сохраняя только средние вознаграждения для базовых рук, которые входят в $O_S$. Это математически отражает идею сосредоточения на подмножестве базовых рук, релевантных для целевой супер-руки $S$.

Пошаговый процесс

Давайте проследим, как определяется атакуемость экземпляра CMAB с использованием определения разрыва, чтобы это ощущалось как механическая сборочная линия:

  1. Входные данные характеристики экземпляра: В систему подается конкретный экземпляр CMAB. Этот экземпляр определяется его набором базовых рук $[m]$, пространством действий супер-рук $\mathcal{S}$, распределением задействования среды $D$, функцией вероятностного задействования $D_{trig}$ и функцией вознаграждения $R$. Важно, что истинный вектор средних вознаграждений $\mu$ для всех базовых рук предполагается известным для этой начальной оценки.

  2. Идентификация целевого множества: Противник указывает множество $M$ целевых супер-рук, которые он желает, чтобы алгоритм бандита выбрал.

  3. Оценка отдельной супер-руки (для каждого $S \in M$): Для каждой супер-руки $S$ из целевого множества $M$:

    • Расчет истинного вознаграждения: Ожидаемое вознаграждение $r_S(\mu)$ для этой супер-руки $S$ вычисляется на основе истинных средних вознаграждений $\mu$. Это ее базовая производительность.
    • Идентификация наблюдаемых базовых рук: Определяется множество $O_S$. Это совокупность базовых рук, которые могут быть вероятностно задействованы при выборе супер-руки $S$. Представьте это как «поле зрения» $S$ или ресурсы, на которые она может напрямую влиять.
    • Моделирование модифицированной среды: Создается гипотетическая среда, в которой истинные средние вознаграждения базовых рук, не входящих в $O_S$, фактически устанавливаются равными нулю. Это создает модифицированный вектор средних вознаграждений $\mu \odot O_S$. Это моделирует стратегию противника по подавлению вознаграждений от нерелевантных базовых рук.
    • Оценка конкурентов: Для каждой другой супер-руки $S' \neq S$ (т.е. любой супер-руки, которая в настоящее время не рассматривается как целевая), ее ожидаемое вознаграждение $r_{S'}(\mu \odot O_S)$ вычисляется с использованием этого модифицированного вектора средних вознаграждений. Этот шаг оценивает, насколько хорошо конкуренты будут работать, если им будет разрешено «видеть» только то, что видит $S$, или если противник манипулировал другими руками.
    • Идентификация сильнейшего конкурента: Определяется максимальное ожидаемое вознаграждение среди всех этих оцененных конкурентов, $\max_{S' \neq S} r_{S'}(\mu \odot O_S)$. Это самый высокий барьер, который $S$ должна преодолеть.
    • Расчет разрыва: Индивидуальный разрыв $\Delta_S$ вычисляется путем вычитания вознаграждения сильнейшего конкурента (в условиях модифицированной среды) из истинного вознаграждения $S$. Затем это значение сохраняется.

  4. Определение общей атакуемости: После расчета $\Delta_S$ для всех $S \in M$ находится максимум из этих индивидуальных разрывов, $\Delta_M = \max_{S \in M} \Delta_S$.

  5. Вывод атакуемости:

    • Если $\Delta_M > 0$, экземпляр CMAB объявляется «полиномиально атакуемым». Это означает, что существует по крайней мере одна целевая супер-рука $S$, которая имеет достаточный перевес, даже когда конкуренты оцениваются в условиях манипулирования противника.
    • Если $\Delta_M < 0$, экземпляр CMAB объявляется «полиномиально неатакуемым». Это подразумевает, что ни одна целевая супер-рука в $M$ не имеет явного перевеса в условиях предполагаемого манипулирования противника, что делает успешную атаку сложной или невозможной.

Динамика оптимизации

«Математический и логический механизм» в данной статье не включает традиционный процесс обучения или оптимизации для самого разрыва, поскольку $\Delta_S$ является статическим свойством экземпляра CMAB и целевого множества. Вместо этого динамика вращается вокруг того, как фиксированная стратегия противника (Алгоритм 1) использует динамику обучения алгоритма бандита для достижения своей цели, и как разрыв $\Delta_M$ действует как предиктор успеха.

  1. Цель противника: «Оптимизация» противника заключается в том, чтобы заставить алгоритм бандита выбрать целевую супер-руку $S \in M$ в течение $T - o(T)$ раз за временной горизонт $T$, при этом понеся сублинейную стоимость атаки $o(T)$. Это манипуляция, ориентированная на цель, а не итеративное обновление параметров.

  2. Обучение алгоритма бандита (например, CUCB): Алгоритм бандита-жертвы (например, CUCB) работает путем итеративной оценки ожидаемых вознаграждений базовых рук и построения верхних доверительных границ (UCB) для супер-рук. В каждом раунде $t$:

    • Он наблюдает выбранную супер-руку $S^{(t)}$ и результаты $X^{(t)}$ задействованных базовых рук.
    • Он обновляет свои эмпирические оценки средних вознаграждений базовых рук ($\hat{\mu}_i^{(t)}$) и их доверительные интервалы.
    • Он использует эти оценки для расчета UCB для всех супер-рук.
    • Затем он выбирает супер-руку с наивысшим UCB для следующего раунда. Этот процесс направлен на минимизацию сожаления путем балансировки исследования (пробы неопределенных рук) и использования (выбора рук с высокими оцененными вознаграждениями).

  3. Манипулирование противником (Алгоритм 1): Противник вмешивается в этот цикл обучения. Когда алгоритм бандита выбирает супер-руку $S^{(t)}$ и наблюдает результаты $X^{(t)}$, противник модифицирует эти результаты до $\tilde{X}^{(t)}$. В частности, для любой базовой руки $i$, которая задействована, но не входит в наблюдаемое множество $O_S$ целевой супер-руки $S$ (т.е. $i \in \mathcal{T}^{(t)} \setminus O_S$), противник устанавливает ее наблюдаемое вознаграждение $\tilde{X}_i^{(t)} = 0$. Другие результаты остаются без изменений.

  4. Влияние на UCB бандита: Это манипулирование напрямую влияет на обучение бандита:

    • Систематически устанавливая вознаграждения равными 0 для базовых рук, не входящих в $O_S$, противник систематически снижает эмпирические оценки средних вознаграждений ($\hat{\mu}_i^{(t)}$) для этих базовых рук.
    • Это, в свою очередь, снижает UCB для любых супер-рук $S'$, которые сильно зависят от этих «обнуленных» базовых рук.
    • Целевая супер-рука $S$, однако, оценивается на основе ее истинного ожидаемого вознаграждения $r_S(\mu)$ (или ее UCB, который противник хочет сохранить высоким).

  5. Сходимость к целевой руке: Если разрыв $\Delta_M > 0$, это означает, что существует по крайней мере одна целевая супер-рука $S$, чье истинное ожидаемое вознаграждение $r_S(\mu)$ достаточно выше, чем у любой альтернативы $S'$, когда эти альтернативы оцениваются в рамках манипулирования противника ($\mu \odot O_S$). Этот положительный разрыв указывает на то, что «ландшафт потерь» для алгоритма бандита может быть эффективно сформирован противником. Стратегия противника по подавлению вознаграждений рук, не входящих в $O_S$, приведет к тому, что UCB для нецелевых супер-рук упадут ниже UCB целевой супер-руки. Со временем итеративные обновления алгоритма бандита сойдутся к последовательному выбору целевой супер-руки из $M$, поскольку ее UCB будет казаться превосходящей из-за манипулируемой обратной связи. Атака «успешна», когда UCB бандита достаточно искажены.

  6. Неатакуемость ($\Delta_M < 0$): Если $\Delta_M < 0$, это означает, что даже при наиболее благоприятном манипулировании противника (обнуление рук, не входящих в $O_S$), нет целевой супер-руки $S \in M$, которая казалась бы превосходящей все другие альтернативы. В этом сценарии UCB алгоритма бандита не сойдутся к последовательному выбору целевой руки, поскольку какая-то нецелевая рука всегда будет иметь более высокий (или сопоставимый) UCB, делая экземпляр внутренне устойчивым к такому типу атаки. Усилия противника по манипулированию вознаграждениями будут тщетными или потребуют экспоненциальной стоимости, нарушая определение полиномиальной атакуемости. Естественное исследование и использование алгоритма бандита предотвратит его последовательное введение в заблуждение.

Результаты, ограничения и заключение

Дизайн эксперимента и базовые линии

Экспериментальная валидация была тщательно разработана для строгого тестирования теоретических утверждений относительно полиномиальной атакуемости различных экземпляров комбинаторных многоруких бандитов (CMAB). Исследователи использовали многогранный подход, применяя реальные наборы данных и ряд приложений CMAB, каждое со специфическими целевыми конфигурациями и базовыми алгоритмами.

Для задач Вероятностного максимального покрытия (PMC), Онлайн-минимального остовного дерева (MST) и Онлайн-кратчайшего пути использовался набор данных Flickr (McAuley & Leskovec, 2012). Подграф был уменьшен, сохранив самый большой слабосвязный компонент, что привело к 1892 узлам и 7052 направленным ребрам с их присущими весами активации ребер. Для Каскадных бандитов был использован набор данных MovieLens small (Harper & Konstan, 2015), состоящий из 9000 фильмов, с случайной выборкой 5000 фильмов для экспериментов. Для отображения рейтингов фильмов на вероятности кликов пользователей использовалось SVD-приближение ранга d. Все эксперименты повторялись минимум 10 раз для обеспечения статистической надежности, с отчетом о средних результатах и дисперсиях.

«Жертвами» (базовыми моделями) были стандартные алгоритмы обучения CMAB. Для PMC использовался алгоритм CUCB с жадным оракулом. Рассматривались два типа целевых объектов атаки: «фиксированная цель», состоящая из узлов с убывающими средними весами исходящих ребер, и «случайная цель» из K случайно выбранных узлов со средним весом исходящего ребра более 0.5.

Для задачи онлайн-MST набор данных Flickr был преобразован в неориентированный граф, а средние вероятности служили ожидаемыми стоимостями ребер. Атака использовала модифицированную версию Алгоритма 1, где цель была изменена на минимизацию стоимости путем установки модифицированного результата базовой руки $X_T = 1$. Базовыми линиями были стандартные алгоритмы CUCB. Целями были «фиксированная цель» (второе по величине минимальное остовное дерево) и «случайная цель» (минимальное остовное дерево со случайными весами ребер).

В задаче онлайн-кратчайшего пути против CUCB были оценены два различных типа целей: «неатакуемая цель» (тщательно сконструированный путь, где стоимость на целевом пути была изначально выше, чем у оптимального пути, что затрудняло введение алгоритма в заблуждение) и «случайная цель» (кратчайший путь между случайно выбранными исходным и конечным узлами со случайными весами ребер). Эта настройка была критически важна для демонстрации экземпляров, которые внутренне устойчивы к атакам.

Для каскадных бандитов исследование противопоставило атаку алгоритмам CascadeKL-UCB, CascadeUCB1 и CascadeUCB-V. Целевая супер-рука выбиралась из подмножества базовых рук со средней вероятностью клика более 0.1.

Дополнительно, эксперименты по онлайн-максимизации влияния (IM), подробно описанные в Приложении A.2, использовали $(\alpha, \beta)$-приближенный оракул (оракул IMM) из-за NP-трудности задачи. Стратегия атаки включала эвристику, которая модифицировала наблюдаемые реализации ребер до 0 для ребер вне «расширенного целевого множества» $S_{ex}$, которое включало целевые узлы и узлы в пределах определенного расстояния $l$. Эти эксперименты повторялись не менее 5 раз. Этот всесторонний дизайн эксперимента, охватывающий разнообразные приложения CMAB и целевые конфигурации, позволил провести тщательную эмпирическую проверку теоретических условий атакуемости.

Что доказывают свидетельства

Экспериментальные данные предоставляют убедительную и окончательную валидацию основных математических утверждений статьи относительно атакуемости CMAB, в частности условий, изложенных в Теореме 3.6 и Следствии 3.8.

Для Вероятностного максимального покрытия (PMC), как показано на рисунках 2(a) и 2(b), атака успешно заставила алгоритм CUCB выбирать целевую руку линейно с течением времени, в то время как общая стоимость атаки росла сублинейно. Эта сублинейная стоимость, несмотря на большое количество узлов и ребер, была явно полиномиальной по количеству базовых рук, напрямую подтверждая Теорему 3.9, которая гласит, что PMC полиномиально атакуем, когда $\Delta_M > 0$. Линейное увеличение выборов целевой руки при сублинейной стоимости является неоспоримым доказательством того, что механизм атаки эффективно вводит в заблуждение базовый алгоритм CUCB. Атаки на случайные цели демонстрировали более высокую дисперсию, предполагая присущую непредсказуемость таких сценариев.

Аналогично, для задачи Онлайн-минимального остовного дерева (MST) (Рисунки 2(c) и 2(d)) общая стоимость атаки оставалась сублинейной, а целевая рука выбиралась линейно. Этот результат идеально соответствует Следствию 3.8, которое предполагает, что онлайн-задачи MST всегда атакуемы, поскольку их разрыв $\Delta_M \ge 0$. Последовательная сублинейная стоимость и линейный выбор целевой руки в экспериментах против базовых алгоритмов CUCB обеспечивают сильную эмпирическую поддержку теоретическому прогнозу атакуемости в этой области.

Эксперименты по Онлайн-кратчайшему пути (Рисунки 2(e) и 2(f)) предоставили решающую демонстрацию как атакуемых, так и неатакуемых экземпляров. Для «случайных целей» атака достигла сублинейной стоимости и линейного выбора целевой руки, аналогично PMC и MST. Однако для «неатакуемых целей» (тщательно сконструированных путей, разработанных для устойчивости) общая стоимость росла линейно, и, что критически важно, выбор целевой руки оставался почти постоянным. Этот резкий контраст окончательно доказывает существование внутренне неатакуемых экземпляров CMAB, подтверждая теоретическое различие между атакуемыми и неатакуемыми сценариями на основе условия $\Delta_M$. Алгоритм CUCB в данном случае не был обманут, предоставляя веские доказательства пределов атакуемости.

В Каскадных бандитах (Рисунки 2(g) и 2(h)) атака успешно вызвала линейные выборы целевой руки при сублинейной стоимости атаки против CascadeKL-UCB, CascadeUCB1 и CascadeUCB-V. Этот результат далее укрепляет Следствие 3.8, подтверждая, что каскадные бандиты полиномиально атакуемы. Последовательное линейное увеличение выборов целевой руки при минимальной стоимости в различных базовых алгоритмах обеспечивает надежное доказательство эффективности атаки.

Результаты Онлайн-максимизации влияния (IM) (Рисунки 4(a) и 4(b)) представили более нюансированную картину. Хотя стоимость атаки снизилась, процент выбранных целевых узлов оставался постоянным на уровне 0, без явной тенденции к увеличению выбора целевых узлов. Этот результат, вместо опровержения атакуемости, подчеркивает сложность атаки на онлайн-IM и подчеркивает утверждение статьи о том, что для экземпляров CMAB с неточными (α-приближенными) оракулами атакуемость должна анализироваться на основе каждого экземпляра. Это предполагает, что текущая эвристика атаки недостаточна для IM, но не исключает ее внутреннюю атакуемость, что побуждает к дальнейшим исследованиям.

Таким образом, эксперименты безжалостно доказали математические утверждения, показав, что для экземпляров, где $\Delta_M > 0$ (PMC, MST, Каскадные бандиты), алгоритм атаки успешно вводит в заблуждение различные базовые алгоритмы на основе CUCB при сублинейной стоимости и линейном выборе целевой руки. Напротив, для экземпляров, где $\Delta_M < 0$ (определенные конфигурации кратчайшего пути), атака терпит неудачу, приводя к линейной стоимости и постоянному выбору целевой руки, тем самым предоставляя окончательные, неоспоримые доказательства того, что основной механизм атакуемости (или неатакуемости) работает на практике.

Ограничения и будущие направления

Хотя эта статья представляет собой новаторскую характеристику атакуемости CMAB, она также открыто признает несколько ограничений и предлагает захватывающие направления для будущих исследований.

Одним из значительных ограничений является то, что предлагаемый алгоритм атаки (Алгоритм 1) может быть не оптимальным с точки зрения стоимости атаки. Текущие выводы устанавливают достаточность для атакуемости, но не гарантируют минимально возможную стоимость. Важным будущим направлением является разработка более сложных алгоритмов атаки, которые могут достигать более низкой стоимости атаки. Это также потребует установления теоретических нижних границ для стоимости атаки в экземплярах CMAB, что является интригующей и сложной областью.

Другая ключевая область для обсуждения касается различия между известными и неизвестными средами бандитов. Статья раскрывает удивительный факт: полиномиальная атакуемость может различаться для одного и того же экземпляра CMAB в зависимости от того, обладает ли противник предварительным знанием параметров среды (например, распределений вознаграждений). Построенный «сложный пример» (Теорема 4.1) демонстрирует экземпляр, который полиномиально атакуем в известной среде, но неатакуем, когда среда неизвестна. Это предполагает, что общая стратегия атаки для любого экземпляра CMAB в условиях черного ящика может не существовать. Будущие исследования должны быть сосредоточены на характеристике гарантий устойчивости для экземпляров CMAB в неизвестных средах, особенно для таких задач, как кратчайший путь, где разрыв $\Delta_M$ может быть положительным или отрицательным. Разработка общей структуры для сведения неатакуемых задач CMAB к этим сложным примерам была бы очень ценной.

Кроме того, текущая характеристика атакуемости строго ограничена атаками отравления вознаграждения. Авторы явно заявляют, что их выводы не могут быть напрямую обобщены на другие, потенциально более мощные, модели угроз, такие как атаки отравления среды (где противник может напрямую изменять функцию вознаграждения среды) или атаки отравления действий. Будущие исследования должны расширить анализ на эти альтернативные модели угроз, чтобы обеспечить более полное понимание уязвимостей CMAB. Это потребует изучения того, как различные типы враждебных пертурбаций влияют на условия и стоимость атакуемости.

Наконец, заключение статьи подчеркивает необходимость дальнейшего изучения влияния вероятностно задействованных рук на атакуемость. Этот механизм, при котором базовые руки задействуются вероятностно, добавляет еще один уровень сложности к CMAB. Понимание его влияния на атакуемость, особенно в таких приложениях, как онлайн-максимизация влияния с различными моделями диффузии, может привести к новым идеям и более надежным алгоритмам. Первоначальные результаты для онлайн-максимизации влияния, где стратегия атаки не была явно успешной, подчеркивают важность этого конкретного направления исследований, особенно при работе с приближенными оракулами.

Эти перспективные обсуждения, охватывающие оптимизацию стоимости атаки и исследование различных моделей угроз и знаний среды, предоставляют богатую повестку дня для исследователей, стремящихся разработать более надежные алгоритмы CMAB и лучше понять их последствия для безопасности в реальных приложениях.

Изоморфизмы с другими областями

Структурный каркас

По сути, данная статья представляет механизм, который количественно определяет уязвимость системы последовательного принятия решений к целенаправленному манипулированию путем выявления критического «разрыва» в ожидаемых результатах и последующей его эксплуатации посредством модификации вознаграждения.

Дальние родственники

Фундаментальная логика выявления и использования «разрыва» для введения в заблуждение агента, принимающего решения, резонирует в областях, далеких от комбинаторных многоруких бандитов.

  1. Целевая область: Обнаружение манипулирования финансовым рынком

    • Связь: На финансовых рынках сложные алгоритмы и трейдеры постоянно принимают последовательные инвестиционные решения на основе наблюдаемых ценовых сигналов и рыночных данных. Давней проблемой является обнаружение и предотвращение манипулирования рынком, когда противник (например, крупный институциональный трейдер) может «отравить» рыночные сигналы (например, посредством фиктивной торговли, спуфинга или распространения ложных слухов), чтобы ввести в заблуждение других участников рынка к покупке или продаже определенного актива по искусственной цене. Это зеркальное отражение проблемы статьи: противник изменяет «вознаграждения» (воспринимаемые стоимости активов или доходность), чтобы заставить «обучающегося агента» (инвесторов/алгоритмы) выбрать «целевую руку» (инвестировать в определенный актив) в интересах противника. «Разрыв» статьи ($\Delta_S$) может напрямую трансформироваться в меру того, насколько манипулятор должен исказить воспринимаемую стоимость актива, чтобы он казался более привлекательным, чем его истинная фундаментальная стоимость, по сравнению с другими активами.

  2. Целевая область: Кибербезопасность (системы обнаружения/предотвращения вторжений)

    • Связь: Системы обнаружения вторжений (IDS) и системы предотвращения вторжений (IPS) работают в непрерывном цикле последовательного принятия решений, отслеживая сетевой трафик и системные события для обнаружения угроз и реагирования на них. Противники в области кибербезопасности стремятся «отравить» наблюдаемые данные (например, путем внедрения безобидного трафика, маскировки вредоносных полезных нагрузок или генерации ложных срабатываний), чтобы ввести в заблуждение IDS/IPS. Цель состоит в том, чтобы либо избежать обнаружения, либо заставить систему предпринять «целевое действие», которое выгодно злоумышленнику, например, игнорировать реальную угрозу или блокировать легитимных пользователей. Это отражает атаку CMAB, где противник манипулирует наблюдаемыми «вознаграждениями» (системными журналами, сетевыми пакетами), чтобы направить «обучающегося агента» (IDS/IPS) к желаемому, часто пагубному, результату. Условие «атакуемости» может отражать внутреннюю устойчивость логики обнаружения системы против определенных стратегий отравления данных.

Сценарий «Что если»

Представьте себе финансового исследователя, возможно, количественного аналитика из регулирующего органа, который «украдет» эту статью с ее точным уравнением завтра. В частности, он адаптирует определение «разрыва» из Определения 3.5: $\Delta_S := r_S(\mu) - \max_{S' \neq S} r_{S'}(\mu \odot O_S)$.

В этом радикальном сценарии «Что если» $r_S(\mu)$ будет представлять истинную, фундаментальную ожидаемую доходность акции $S$ (возможно, полученную из глубоких, неискаженных финансовых моделей), в то время как $O_S$ будет набором наблюдаемых рыночных сигналов для этой акции. Термин $\mu \odot O_S$ будет означать воспринимаемую ожидаемую доходность, основанную на этих наблюдаемых, потенциально искаженных, сигналах. Затем «разрыв» $\Delta_S$ будет количественно определять разницу между истинной внутренней стоимостью акции и ее наиболее привлекательной воспринимаемой альтернативой.

Прорыв произойдет в форме Индекса уязвимости рынка к манипуляциям в реальном времени. Вместо реактивного расследования подозрительных торговых паттернов, регуляторы смогут использовать этот индекс для выявления акций или целых сегментов рынка, которые внутренне уязвимы к манипулированию. Если акция последовательно показывает небольшой положительный $\Delta_S$ (что означает, что ее истинная стоимость лишь незначительно лучше других вариантов, делая ее «атакуемой» при минимальном отравлении вознаграждения), она будет помечена. Это позволит проактивно развернуть целевой надзор, более строгие торговые правила или даже временные автоматические выключатели на таких активах, предотвращая манипулирование до его начала. Это смещает парадигму с форензического анализа на предиктивную оценку уязвимости, фундаментально изменяя способ поддержания целостности рынка.

Универсальная библиотека структур

Элегантная структура данной статьи для характеристики атакуемости и устойчивости в системах последовательного принятия решений, основанная на концепции количественно определяемого «разрыва», иллюстрирует, как фундаментальные математические структуры, подобные тем, что управляют стратегическим взаимодействием и асимметрией информации, выходят за рамки конкретных областей, предлагая универсальные линзы для понимания уязвимости и устойчивости в разнообразных научных и инженерных задачах.