技術的概要：偽データ注入による確率的バンディットへの実用的敵対的攻撃

1. 問題定義

多腕バンディット（MAB）アルゴリズムは、パーソナライズされた推薦、オンライン広告、臨床試験などのアプリケーションにおいて、探索と利用のバランスを取るオンライン意思決定システムの基盤です。先行研究は MAB アルゴリズムが敵対的攻撃に脆弱であることを確立していますが、既存の脅威モデルは現実のシステムへの関連性を制限する非現実的な仮定に依存しています。

具体的には、先行研究（例：Jun et al., 2018; Liu and Shroff, 2019; Zuo, 2024）は主にフィードバック改ざんモデルを採用しています。このモデルでは、攻撃者は各ラウンドで学習者が選択した腕とその報酬を観察し、学習者に提示される前に報酬を恣意的に改ざんします。このモデルは、攻撃者に各時間ステップにおけるフィードバックチャネルの完全な制御権を与え、無制限の改ざん能力を仮定しています。

実際には、そのような能力はしばしば非現実的です。例えば、レストラン推薦プラットフォームにおいて、敵対者は何千もの実在する顧客からの真のユーザー評価を継続的に上書きすることはできません。代わりに、現実的な攻撃には、偽のアカウントを作成して捏造されたレビューや合成された相互作用（例：クリック詐欺）を注入することが含まれます。これらの攻撃は既存のデータを変更するのではなく偽のデータを追加するものであり、システムレベルの検出やリソース制限の対象となり、かつ有効なフィードバック範囲（例：1〜5 星の評価）に準拠する必要があります。

本論文は、理論的な攻撃モデルと実用的な制約の間のギャップに対処するため、新しい脅威モデル：偽データ注入を提案します。核心的な課題は、以下の制約の下で、学習者をほぼすべてのラウンドにおいて特定の非最適（ターゲット）腕を選択させるように誘導しつつ、部分線形コストのみを発生させる攻撃戦略を設計することです。

1. 真のフィードバックの改ざん不可：攻撃者は実在するユーザーデータを上書きできません。
2. 有界な報酬：注入された偽の報酬は、有効なフィードバック範囲 $[r_l, r_u]$ 内に存在しなければなりません。
3. 時間的制約：攻撃者は、1 ラウンドあたりに注入できる偽サンプルの数（バッチサイズ）や注入の頻度が制限される可能性があります。

2. 手法と核心概念

2.1 偽データ注入脅威モデル

著者は、攻撃者が $N_F$ 個の偽データサンプル $\{(a^F_s, r^F_s)\}$ を学習者の履歴に注入する設定を形式化しました。学習者は、これらの注入されたサンプルを正当な相互作用と区別なく扱い、経験平均、引き回数、内部ラウンドカウンターをそれに応じて更新します。

• 攻撃コスト：$C_F(T) = \sum |r^F_s - \mu_{a^F_s}|$ と定義されます。
• 成功基準：攻撃が成功するとは、学習者が $T - o(T)$ ラウンドにおいてターゲット腕を選択し、かつ $C_F(T) = o(T)$ であることを保証する場合です。

2.2 抑制の原理

中心的な技術的洞察は抑制の原理です。報酬を継続的に改ざんする代わりに、攻撃者は、非ターゲット腕の経験推定値をターゲット腕の安定した下限基準以下に抑えるために、十分な量の有界な偽フィードバックを注入することを目指します。一度非ターゲット腕が十分に抑制されると、学習者自身の探索メカニズムが、相当期間その腕が再び選択されることを防ぎます。

指数抑制補題（UCB 向け）

Upper Confidence Bound (UCB) アルゴリズムにおいて、著者は、非ターゲット腕 $i$ が十分に引き ($N_i(t) \geq \log T/\delta_0^2$)、その経験平均がターゲット腕 $K$ の特定の下限 $\hat{\ell}_K(t)$ 以下に駆り立てられた場合、腕 $i$ は少なくともラウンド $\exp(N_i(t)\delta_0^2)$ まで高い確率で再び選択されないことを証明しました。この「指数抑制」により、攻撃者は腕ごとに単一の注入イベントで長期的な操作を達成できます。

2.3 攻撃戦略

A. 同時注入 (SI)

攻撃者が厳密な 1 ラウンドあたりの制限なしに必要なときにデータを注入できる設定向けに設計されています。

• メカニズム：各非ターゲット腕 $i$ について、攻撃者はそれが $\lceil \log T/\delta_0^2 \rceil$ 回引きられるまで待ちます。その後、攻撃者は有効な最小報酬 $r_l$ を持つ偽サンプルのバッチを注入し、その腕の経験平均をターゲット腕の下限信頼区間以下に低下させます。
• 結果：これにより UCB アルゴリズムは、累積コスト $\tilde{O}(K\sigma\sqrt{\log T})$ で $T - o(T)$ ラウンドにわたりターゲット腕を選択することを強制され、既知の下限と一致します。

B. 周期的有界注入 (PBI)

攻撃者がバッチサイズ制限（1 ラウンドあたり $f$ サンプル）に直面し、異常検知を回避しなければならない現実的な制約向けに設計されています。

• メカニズム：単一の大きな注入の代わりに、攻撃者は必要な偽サンプルを時間的に分散させます。非ターゲット腕が引き閾値に達すると、攻撃者は必要なサンプルの総数と「クールダウン期間」$R_i$ を計算します。攻撃者は、注入の間隔を $R_i$ ラウンド空けながら、サイズ $f$ のバッチを周期的に注入し、注入の間に腕が抑制された状態を維持します。
• 結果：PBI は、厳格な時間的および大きさの制約下でも、ステルス性と有効性のバランスを取りながら、部分線形コストで成功する攻撃を達成します。

C. 一般抑制有界フレームワーク

著者はこれらの知見を UCB を超えて、抑制有界と呼ばれるアルゴリズムのクラスに拡張しました。あるアルゴリズムが、非最適腕がターゲット腕によって経験的に支配された後、その腕をさらに有界な回数しか引きません。

• このフレームワークはThompson Samplingおよび$\epsilon$-greedyアルゴリズムに適用されます。
• 攻撃戦略は、非ターゲット腕の経験平均がターゲットの基準以下に留まる条件を満たすために、最小限の偽サンプルを注入することを含み、アルゴリズムが持つ抑制後の引き回数に関する固有の制約を利用します。

3. 主要な貢献

1. 新しい脅威モデル：先行するフィードバック改ざんモデルが見落としていた現実的な制約（有界な報酬、制限された注入頻度、真のデータの上書き不可）を反映する偽データ注入の導入。
2. 抑制の原理：有界な偽注入が非ターゲット腕を永続的に抑制できるメカニズムの形式化。これにより、攻撃は継続的な改ざんではなく、抑制の確立と維持という問題へと転換されます。
3. アルゴリズム的戦略：
   • 同時注入 (SI)：最小の制約下での UCB に対する最適戦略。
   • 周期的有界注入 (PBI)：バッチサイズおよび時間的制約下での UCB に対する堅牢な戦略。
   • 一般フレームワーク：抑制分析の Thompson Sampling および $\epsilon$-greedy への拡張。
4. 理論的保証：有界な報酬値であっても、これらの攻撃が部分線形攻撃コスト ($o(T)$) で学習者を $T - o(T)$ ラウンドにおいてターゲット腕を選択させるように誘導できることの証明。
5. 実証的検証：合成データおよびMovieLens 25Mデータセットを用いた実験により、疎で有界な偽データが実際にはバンディット学習者を大幅に偏らせることができることを実証。

4. 実験結果

著者は以下のデータセットで戦略を評価しました。

• 合成データ：$K=10$ 腕のガウス分布報酬。
• 実世界データ：10 腕（映画）とユーザー相互作用を持つ推薦システムをシミュレートした MovieLens 25M データセット。

主要な発見：

• 有効性：SI と PBI の両方とも、初期抑制フェーズの後、UCB および Thompson Sampling 学習者を 95% 以上のラウンドでターゲット腕を選択させることに成功しました。
• コスト効率：PBI は SI と同等のパフォーマンスを達成しつつ、注入を時間的に分散させることで、長期的なシナリオにおいてより低い攻撃コストを実現しました。
• ベースラインとの比較：残存時間に比例してランダムにサンプルを注入するヒューリスティックなベースラインは、学習者をターゲット腕に収束させることができませんでした。これは、注入スケジュールと抑制の原理の決定的な重要性を浮き彫りにしました。
• 制約への頑健性：PBI は、バッチサイズに厳格な制限 ($f=5$ または $f=10$) があっても攻撃が有効であることを示しました。一方、無制限の戦略（Least Injection など）は理論的に最低のコストを伴いますが、検出が厳しい環境では実用的でない可能性があります。

5. 意義と限界

意義：
本論文は、オンライン学習における理論的敵対的堅牢性と実用的セキュリティの間のギャップを埋めます。それは、「無制限の、1 ラウンドごとの報酬改ざん」という仮定が、現実のシステムを攻撃する難しさを過大評価していることを示しています。疎で有界かつ時間的に分散した偽データが標準的なバンディットアルゴリズムを乗っ取ることができることを示すことで、この研究は高リスク分野で使用される逐次意思決定システムにおける重大な脆弱性を明らかにしました。提案された抑制補題は、経験平均と探索ボーナスに依存するアルゴリズムの脆弱性を分析するための汎用的なツールを提供します。

限界（著者による記載）：

• 受動的学習者：分析は、防御メカニズム（フィルタリングや監査など）なしにすべてのフィードバックを処理する受動的学習者を仮定しています。
• 確率的設定：このフレームワークは現在、確率的バンディットに限定されており、文脈バンディットや強化学習への拡張は未解決の問題です。
• 検知リスク：現在のモデルは、異常検知や腕レベルの監査を採用する適応的学習者との攻撃者間の動的相互作用を明示的に捉えていません。

著者は、結果が古典的な堅牢性保証と実用的セキュリティの間のギャップを露呈させている一方で、将来の研究は異常検知や、攻撃者と適応的・防御的学習者間の動的な相互作用に対する防御策の調査を行う必要があると結論付けています。