論文の概要: Multi-Armed Bandits with Interference

• arxiv url: http://arxiv.org/abs/2402.01845v1
• Date: Fri, 2 Feb 2024 19:02:47 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-06 23:50:06.666395
• Title: Multi-Armed Bandits with Interference
• Title（参考訳）: 干渉を考慮したマルチアーマッドバンド
• Authors: Su Jia, Peter Frazier, Nathan Kallus
• Abstract要約: スイッチバックポリシは,最高の固定アームポリシに対して,最適に期待された後悔のO(sqrt T)$を達成できることが示される。 提案するクラスタランダム化ポリシは,期待値に最適である。
• 参考スコア（独自算出の注目度）: 44.48234870516134
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Experimentation with interference poses a significant challenge in contemporary online platforms. Prior research on experimentation with interference has concentrated on the final output of a policy. The cumulative performance, while equally crucial, is less well understood. To address this gap, we introduce the problem of {\em Multi-armed Bandits with Interference} (MABI), where the learner assigns an arm to each of $N$ experimental units over a time horizon of $T$ rounds. The reward of each unit in each round depends on the treatments of {\em all} units, where the influence of a unit decays in the spatial distance between units. Furthermore, we employ a general setup wherein the reward functions are chosen by an adversary and may vary arbitrarily across rounds and units. We first show that switchback policies achieve an optimal {\em expected} regret $\tilde O(\sqrt T)$ against the best fixed-arm policy. Nonetheless, the regret (as a random variable) for any switchback policy suffers a high variance, as it does not account for $N$. We propose a cluster randomization policy whose regret (i) is optimal in {\em expectation} and (ii) admits a high probability bound that vanishes in $N$.
• Abstract（参考訳）: 干渉による実験は、現代のオンラインプラットフォームにおいて大きな課題となる。 干渉による実験に関する以前の研究は、政策の最終出力に集中している。 累積的なパフォーマンスは、等しく重要なものの、あまり理解されていない。 このギャップに対処するために、学習者がT$ラウンドの時間的地平線上でN$の実験ユニットにアームを割り当てるMABI ( {\em Multi-armed Bandits with Interference) を導入する。 各ラウンドにおける各ユニットの報酬は、単位間の空間距離で単位の影響が減衰するような、全ての単位の処理に依存する。 さらに,報奨機能が敵によって選択され,ラウンドやユニット間で任意に変化するような一般的な設定も採用する。 まず、スイッチバックポリシーが最適に期待された後悔の$\tilde O(\sqrt T)$を最良の固定アームポリシーに対して達成することを示す。 それでも、あらゆるswitchbackポリシーに対する後悔(ランダム変数として)は、n$を考慮しないため、高いばらつきを被る。 我々は,クラスタランダム化政策を提案する。 i)は予想において最適であり、かつ (ii) は、$n$ で消滅する高い確率境界を認めている。

関連論文リスト

• Multi-Armed Bandits with Network Interference [5.708360037632367]
  我々は,学習者が$mathcalA$アクション(カウント)を$T$ラウンド以上の$N$ユニット(グッド)に逐次割り当てて,後悔を最小限に抑えるマルチアームバンディット(MAB)問題について検討する。 従来のMAB問題とは異なり、各ユニットの報酬は他のユニットに割り当てられた処理に依存する。 後悔を最小限に抑えるため、単純で線形回帰に基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-05-28T22:01:50Z)
• Short-lived High-volume Multi-A(rmed)/B(andits) Testing [6.707544598445059]
  短命の腕を多量に持つベイズ的マルチプレイバンディット問題について検討した。 我々は、ある定数$rho>0$に対して$k = O(nrho)$が与えられたとき、我々の提案したポリシーは、事前分布の十分大きなクラスに対して$tilde O(n-min rho, frac 12 (1+frac 1w)-1)$損失を持つことを示した。
  論文  参考訳（メタデータ） (2023-12-23T21:38:35Z)
• Allocating Divisible Resources on Arms with Unknown and Random Rewards [25.93048671326331]
  我々は、各期間に複数の武器で再生可能資源の1単位を割り当てる意思決定者について検討する。 アームは未知でランダムな報酬であり、その手段は割り当てられたリソースに比例し、分散は割り当てられたリソースのオーダー$b$に比例する。
  論文  参考訳（メタデータ） (2023-06-28T21:59:11Z)
• Communication-Constrained Bandits under Additive Gaussian Noise [111.06688156723018]
  クライアントが学習者にコミュニケーション制約のあるフィードバックを提供する分散マルチアームバンディットについて検討する。 我々は、この下限を小さな加法係数にマッチさせるマルチフェーズ帯域幅アルゴリズム、$mathtUEtext-UCB++$を提案する。
  論文  参考訳（メタデータ） (2023-04-25T09:31:20Z)
• Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
  本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。 提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
  論文  参考訳（メタデータ） (2023-01-31T03:49:00Z)
• Top $K$ Ranking for Multi-Armed Bandit with Noisy Evaluations [102.32996053572144]
  我々は,各ラウンドの開始時に,学習者が各アームの真の報酬について,ノイズのない独立した評価を受けるマルチアームバンディット・セッティングを考える。 評価の方法によって異なるアルゴリズムアプローチと理論的保証を導出する。
  論文  参考訳（メタデータ） (2021-12-13T09:48:54Z)
• Linear Contextual Bandits with Adversarial Corruptions [91.38793800392108]
  本稿では,敵対的腐敗の存在下での線形文脈的包帯問題について検討する。 逆汚染レベルに適応する分散認識アルゴリズムをC$で提案する。
  論文  参考訳（メタデータ） (2021-10-25T02:53:24Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Learning and Optimization with Seasonal Patterns [3.7578900993400626]
  平均報酬が周期的に変化するK$アームを持つ非定常MABモデルを考える。 本稿では,信頼関係分析と学習手順を組み合わせて未知の期間を学習する2段階ポリシーを提案する。 我々の学習ポリシーは、後悔の上限である $tildeO(sqrtTsum_k=1K T_k)$ ここで、$T_k$はarm $k$の期間であることを示す。
  論文  参考訳（メタデータ） (2020-05-16T20:19:25Z)

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

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