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

• arxiv url: http://arxiv.org/abs/2405.18621v1
• Date: Tue, 28 May 2024 22:01:50 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-30 21:33:21.041711
• Title: Multi-Armed Bandits with Network Interference
• Title（参考訳）: ネットワーク干渉を用いたマルチアーマッドバンド
• Authors: Abhineet Agarwal, Anish Agarwal, Lorenzo Masoero, Justin Whitehouse,
• Abstract要約: 我々は,学習者が$mathcalA$アクション(カウント)を$T$ラウンド以上の$N$ユニット(グッド)に逐次割り当てて,後悔を最小限に抑えるマルチアームバンディット(MAB)問題について検討する。 従来のMAB問題とは異なり、各ユニットの報酬は他のユニットに割り当てられた処理に依存する。 後悔を最小限に抑えるため、単純で線形回帰に基づくアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 5.708360037632367
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Online experimentation with interference is a common challenge in modern applications such as e-commerce and adaptive clinical trials in medicine. For example, in online marketplaces, the revenue of a good depends on discounts applied to competing goods. Statistical inference with interference is widely studied in the offline setting, but far less is known about how to adaptively assign treatments to minimize regret. We address this gap by studying a multi-armed bandit (MAB) problem where a learner (e-commerce platform) sequentially assigns one of possible $\mathcal{A}$ actions (discounts) to $N$ units (goods) over $T$ rounds to minimize regret (maximize revenue). Unlike traditional MAB problems, the reward of each unit depends on the treatments assigned to other units, i.e., there is interference across the underlying network of units. With $\mathcal{A}$ actions and $N$ units, minimizing regret is combinatorially difficult since the action space grows as $\mathcal{A}^N$. To overcome this issue, we study a sparse network interference model, where the reward of a unit is only affected by the treatments assigned to $s$ neighboring units. We use tools from discrete Fourier analysis to develop a sparse linear representation of the unit-specific reward $r_n: [\mathcal{A}]^N \rightarrow \mathbb{R} $, and propose simple, linear regression-based algorithms to minimize regret. Importantly, our algorithms achieve provably low regret both when the learner observes the interference neighborhood for all units and when it is unknown. This significantly generalizes other works on this topic which impose strict conditions on the strength of interference on a known network, and also compare regret to a markedly weaker optimal action. Empirically, we corroborate our theoretical findings via numerical simulations.
• Abstract（参考訳）: 干渉によるオンライン実験は、電子商取引や医学における適応的臨床試験のような近代的な応用において共通の課題である。 例えば、オンラインマーケットプレースでは、商品の収益は競合商品に適用される割引に依存する。 干渉による統計的推測はオフライン環境で広く研究されているが、後悔を最小限に抑えるために適応的に治療を割り当てる方法についてはあまり知られていない。 我々は,学習者(eコマースプラットフォーム)が,可能な$\mathcal{A}$アクション(割引)の1つを,後悔(収益の最大化)を最小限に抑えるために,T$ラウンド以上の$N$ユニット(グッド)に順次割り当てる,マルチアームバンディット(MAB)問題を研究することで,このギャップに対処する。 従来のMAB問題とは異なり、各ユニットの報酬は他のユニットに割り当てられた処理に依存する。 $\mathcal{A}$アクションと$N$ユニットでは、アクション空間が$\mathcal{A}^N$として成長するので、後悔を最小化することは組合せ的に困難である。 この問題を克服するために、各ユニットの報酬は、近隣ユニットの$s$に割り当てられた処理によってのみ影響を受ける、スパースネットワーク干渉モデルについて検討する。 離散フーリエ解析のツールを用いて、単位固有報酬 $r_n: [\mathcal{A}]^N \rightarrow \mathbb{R} $ の疎線型表現を開発し、後悔を最小限に抑える単純な線形回帰アルゴリズムを提案する。 重要なことは、学習者がすべてのユニットの干渉地区を観察し、いつその領域が未知になるかの両方において、我々のアルゴリズムは確実に低い後悔を達成することである。 これは、既知のネットワーク上の干渉の強さに厳密な条件を課すこのトピックに関する他の研究を著しく一般化し、また、後悔を著しく弱い最適な行動と比較する。 数値シミュレーションにより理論的知見を裏付ける。

関連論文リスト

• Rising Rested Bandits: Lower Bounds and Efficient Algorithms [15.390680055166769]
  本論文は、連続マルチアーマッドバンド(MAB)の分野である。 我々は,腕の期待される報酬が単調に非減少性であり,結束する残留包帯の特定の症例について検討した。 我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
  論文  参考訳（メタデータ） (2024-11-06T22:00:46Z)
• Multi-Armed Bandits with Interference [39.578572123342944]
  スイッチバックポリシは,最高の固定アームポリシに対して,最適に期待された後悔のO(sqrt T)$を達成できることが示される。 提案するクラスタランダム化ポリシは,期待値に最適である。
  論文  参考訳（メタデータ） (2024-02-02T19:02:47Z)
• On the Convergence of Federated Averaging under Partial Participation for Over-parameterized Neural Networks [13.2844023993979]
  フェデレートラーニング(FL)は、ローカルデータを共有せずに複数のクライアントから機械学習モデルを協調的に作成するための分散パラダイムである。 本稿では,FedAvgが世界規模で世界規模で収束していることを示す。
  論文  参考訳（メタデータ） (2023-10-09T07:56:56Z)
• Distributed Extra-gradient with Optimal Complexity and Communication Guarantees [60.571030754252824]
  複数のプロセッサ/ワーカー/クライアントがローカルなデュアルベクトルにアクセス可能なマルチGPU設定において、モノトン変分不等式(VI)問題を考察する。 モノトーンVI問題に対するデファクトアルゴリズムであるExtra-gradientは、通信効率が良くないように設計されている。 そこで本稿では,VI の解法に適した非バイアスで適応的な圧縮手法である量子化一般化外部勾配 (Q-GenX) を提案する。
  論文  参考訳（メタデータ） (2023-08-17T21:15:04Z)
• Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
  本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。 疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。 後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
  論文  参考訳（メタデータ） (2023-05-30T16:05:44Z)
• Federated Empirical Risk Minimization via Second-Order Method [18.548661105227488]
  連合学習環境下での一般的な経験的リスク最小化問題を解決するためのインテリアポイント法(IPM)を提案する。 IPMの各イテレーションの通信複雑性は$tildeO(d3/2)$であり、$d$はデータセットの次元(つまり、多くの機能)である。
  論文  参考訳（メタデータ） (2023-05-27T14:23:14Z)
• Energy Regularized RNNs for Solving Non-Stationary Bandit Problems [97.72614340294547]
  我々は、ニューラルネットワークが特定の行動を支持するのに自信過剰になるのを防ぐエネルギー用語を提案する。 提案手法は,ロッティングバンドのサブプロブレムを解く方法と同じくらい有効であることを示す。
  論文  参考訳（メタデータ） (2023-03-12T03:32:43Z)
• The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret and Policy Switches [84.54669549718075]
  漸進的強化学習(RL)における後悔の最小化問題について検討する。 一般関数クラスと一般モデルクラスで学ぶことに集中する。 対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
  論文  参考訳（メタデータ） (2022-03-03T02:55:55Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。 楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。 我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
  論文  参考訳（メタデータ） (2021-10-21T15:25:15Z)
• Towards an Understanding of Benign Overfitting in Neural Networks [104.2956323934544]
  現代の機械学習モデルは、しばしば膨大な数のパラメータを使用し、通常、トレーニング損失がゼロになるように最適化されている。 ニューラルネットワークの2層構成において、これらの良質な過適合現象がどのように起こるかを検討する。 本稿では,2層型ReLUネットワーク補間器を極小最適学習率で実現可能であることを示す。
  論文  参考訳（メタデータ） (2021-06-06T19:08:53Z)
• Toward Adversarial Robustness via Semi-supervised Robust Training [93.36310070269643]
  アドリラルな例は、ディープニューラルネットワーク(DNN)に対する深刻な脅威であることが示されている。 R_stand$ と $R_rob$ の2つの異なるリスクを共同で最小化することで、新しい防御手法であるロバストトレーニング(RT)を提案する。
  論文  参考訳（メタデータ） (2020-03-16T02:14:08Z)

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

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