論文の概要: Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms

• arxiv url: http://arxiv.org/abs/2201.12700v1
• Date: Sun, 30 Jan 2022 01:45:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-02-01 16:11:47.744106
• Title: Coordinated Attacks against Contextual Bandits: Fundamental Limits and Defense Mechanisms
• Title（参考訳）: コンテクスト・バンディットに対する協調攻撃:基本限界と防御機構
• Authors: Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, Shie Mannor
• Abstract要約: オンラインレコメンデーションシステムによってモチベーションされた我々は,文脈的包帯における最適政策の発見問題を提案する。 目標は、優れたユーザに対する報酬を可能な限り少ないユーザインタラクションで最大化するポリシーを、しっかりと学習することだ。 効率的なロバストな平均推定器を用いることで、$tildeO(min(S,A)cdot alpha/epsilon2)$ upper-boundを実現できることを示す。
• 参考スコア（独自算出の注目度）: 75.17357040707347
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by online recommendation systems, we propose the problem of finding the optimal policy in multitask contextual bandits when a small fraction $\alpha < 1/2$ of tasks (users) are arbitrary and adversarial. The remaining fraction of good users share the same instance of contextual bandits with $S$ contexts and $A$ actions (items). Naturally, whether a user is good or adversarial is not known in advance. The goal is to robustly learn the policy that maximizes rewards for good users with as few user interactions as possible. Without adversarial users, established results in collaborative filtering show that $O(1/\epsilon^2)$ per-user interactions suffice to learn a good policy, precisely because information can be shared across users. This parallelization gain is fundamentally altered by the presence of adversarial users: unless there are super-polynomial number of users, we show a lower bound of $\tilde{\Omega}(\min(S,A) \cdot \alpha^2 / \epsilon^2)$ {\it per-user} interactions to learn an $\epsilon$-optimal policy for the good users. We then show we can achieve an $\tilde{O}(\min(S,A)\cdot \alpha/\epsilon^2)$ upper-bound, by employing efficient robust mean estimators for both uni-variate and high-dimensional random variables. We also show that this can be improved depending on the distributions of contexts.
• Abstract（参考訳）: オンラインレコメンデーションシステムによってモチベーションされた本研究では,タスク(ユーザ)の小さな分数$\alpha < 1/2$が任意かつ敵対的である場合に,マルチタスクのコンテキスト的包帯における最適ポリシーを見つける問題を提案する。 残りの一部の良いユーザーは、$s$コンテキストと$a$アクション(items)で同じコンテキストのバンディットのインスタンスを共有している。 当然、ユーザーが良いか敵であるかは事前にはわからない。 目標は、優れたユーザに対する報酬を可能な限り少ないユーザインタラクションで最大化するポリシーを、しっかりと学習することだ。 対戦相手がいなければ, 協調フィルタリングの結果から, ユーザごとのO(1/\epsilon^2)$のインタラクションは, ユーザ間で情報を共有できるため, 適切なポリシを学習するのに十分であることがわかった。 超ポリノミカルなユーザ数でない限り、良いユーザに対して$\epsilon$-Optimal Policyを学ぶために、$\tilde{\Omega}(\min(S,A) \cdot \alpha^2 / \epsilon^2)$ {\it per-user}インタラクションの低い境界を示す。 次に、単変数および高次元の確率変数に対して効率的なロバスト平均推定器を用いることで、$\tilde{O}(\min(S,A)\cdot \alpha/\epsilon^2)$上界を達成できることを示す。 また、コンテキストの分布に応じて改善できることも示している。

関連論文リスト

• Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
  我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。 我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2024-06-18T08:54:04Z)
• Context-lumpable stochastic bandits [49.024050919419366]
  我々は、$S$コンテキストと$K$アクションによる文脈的盗賊問題を考える。 我々は,最大$widetilde O(r (S +K )/epsilon2)$サンプルを用いて,$epsilon$-optimal Policyを出力するアルゴリズムを提案する。 後悔の設定では、T$までの累積後悔を$widetilde O(sqrtr3(S+K)T)$で束縛するアルゴリズムを与える。
  論文  参考訳（メタデータ） (2023-06-22T17:20:30Z)
• Disincentivizing Polarization in Social Networks [10.758115514959593]
  本稿では,フィルタバブルを回避するコンテンツキュレーションとパーソナライゼーションのモデルを提案する。 推奨を最適化するためのアルゴリズム保証を提供する。 実世界の嗜好データを用いて、我々のモデルでは、利用者は小さなユーティリティ損失のみで多様化の重荷を共有していることを確認した。
  論文  参考訳（メタデータ） (2023-05-23T21:47:31Z)
• Optimal Algorithms for Latent Bandits with Cluster Structure [50.44722775727619]
  本稿では,複数のユーザが存在するクラスタ構造を持つ潜伏包帯問題と関連するマルチアーム包帯問題とを考察する。 本稿では,潜伏クラスタ構造を利用して$widetildeO(sqrt(mathsfM+mathsfN)mathsfTの最小限の後悔を提供するLATTICEを提案する。
  論文  参考訳（メタデータ） (2023-01-17T17:49:04Z)
• Tractable Optimality in Episodic Latent MABs [75.17357040707347]
  我々は、エージェントが時間ステップ$H$のエピソードのために環境と対話する、M$遅延コンテキストを持つマルチアームバンディット問題を考える。 エピソードの長さによっては、学習者は遅れた文脈を正確に見積もることができないかもしれない。 我々は、$O(textttpoly(A) + textttpoly(M,H)min(M,H))$インタラクションを用いて、ほぼ最適なポリシーを確実に学習する手順を設計する。
  論文  参考訳（メタデータ） (2022-10-05T22:53:46Z)
• Instance-optimal PAC Algorithms for Contextual Bandits [20.176752818200438]
  この作業では、$(epsilon,delta)$-$textitPAC$設定における帯域幅の問題に焦点を当てます。 最良腕識別のための最小限の後悔最小化とインスタンス依存のPACを同時に行うアルゴリズムは存在しないことを示す。
  論文  参考訳（メタデータ） (2022-07-05T23:19:43Z)
• Modeling Attrition in Recommender Systems with Departing Bandits [84.85560764274399]
  政策に依存した地平線を捉えた新しいマルチアームバンディット構成を提案する。 まず、全てのユーザが同じタイプを共有しているケースに対処し、最近の UCB ベースのアルゴリズムが最適であることを実証する。 次に、ユーザが2つのタイプに分けられる、より困難なケースを前進させます。
  論文  参考訳（メタデータ） (2022-03-25T02:30:54Z)
• Contextual Bandits with Side-Observations [10.248045133793287]
  ソーシャルネットワークを介して接続されたユーザの推薦アルゴリズムを設計するために,両腕にサイドオブザーブメントが存在する場合のコンテキスト帯について検討する。 既存の学習アルゴリズムの素直な応用は、$Oleft(Nlog Tright)$ regretとなり、そこでは$N$がユーザ数であることを示す。
  論文  参考訳（メタデータ） (2020-06-06T19:34:50Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。