論文の概要: Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference
- arxiv url: http://arxiv.org/abs/2503.07555v1
- Date: Mon, 10 Mar 2025 17:25:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-11 18:54:08.452445
- Title: Graph-Dependent Regret Bounds in Multi-Armed Bandits with Interference
- Title（参考訳）: 干渉を考慮した多関節帯域におけるグラフ依存レグレスト境界
- Authors: Fateme Jamshidi, Mohammad Shahverdikondori, Negar Kiyavash,
- Abstract要約: マルチアーム・バンディット(MAB)は、パーソナライズされたコンテンツの推薦から患者への治療の割り当てに至るまで、オンラインのシーケンシャルな意思決定に頻繁に使用される。
ネットワーク干渉下でのMAB問題について検討し、各ユニットの報酬はそれぞれの処理と近隣の処理に依存する。
本稿では, 干渉グラフの局所構造を用いて, 後悔を最小限に抑えるアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 18.101059380671582
- License:
- Abstract: Multi-armed bandits (MABs) are frequently used for online sequential decision-making in applications ranging from recommending personalized content to assigning treatments to patients. A recurring challenge in the applicability of the classic MAB framework to real-world settings is ignoring \textit{interference}, where a unit's outcome depends on treatment assigned to others. This leads to an exponentially growing action space, rendering standard approaches computationally impractical. We study the MAB problem under network interference, where each unit's reward depends on its own treatment and those of its neighbors in a given interference graph. We propose a novel algorithm that uses the local structure of the interference graph to minimize regret. We derive a graph-dependent upper bound on cumulative regret showing that it improves over prior work. Additionally, we provide the first lower bounds for bandits with arbitrary network interference, where each bound involves a distinct structural property of the interference graph. These bounds demonstrate that when the graph is either dense or sparse, our algorithm is nearly optimal, with upper and lower bounds that match up to logarithmic factors. We complement our theoretical results with numerical experiments, which show that our approach outperforms baseline methods.
- Abstract（参考訳）: マルチアーム・バンディット(MAB)は、パーソナライズされたコンテンツの推薦から患者への治療の割り当てに至るまで、オンラインのシーケンシャルな意思決定に頻繁に使用される。
古典的MABフレームワークを現実世界の設定に適用する際の繰り返しの課題は、ユニットの結果が他のユニットに割り当てられた処理に依存するような \textit{interference} を無視しることである。
これは指数関数的に増加する作用空間をもたらし、標準的アプローチを計算的に非現実的にレンダリングする。
ネットワーク干渉下でのMAB問題について検討し、各ユニットの報酬はそれぞれの処理と近隣の処理に依存する。
本稿では, 干渉グラフの局所構造を用いて, 後悔を最小限に抑えるアルゴリズムを提案する。
累積的後悔に基づくグラフ依存上界を導出し、前処理よりも改善することを示す。
さらに、任意のネットワーク干渉を持つバンディットに対して、各境界が干渉グラフの異なる構造特性を含む最初の下界を与える。
これらの境界は、グラフが密度または疎度であるとき、我々のアルゴリズムはほぼ最適であり、上下境界は対数的因子に一致することを示した。
理論的結果と数値実験を補完し,本手法がベースライン法より優れていることを示す。
関連論文リスト
- Causal bandits with backdoor adjustment on unknown Gaussian DAGs [5.807183284468881]
グラフ構造が不明な場合の因果帯域問題について検討する。
連続的に生成された実験データと観測データを用いて各アームのバックドア調整セットを同定する。
最適介入を逐次決定するために,修正された上位信頼境界に基づく新しい帯域幅アルゴリズムを開発した。
論文 参考訳（メタデータ） (2025-02-04T05:18:35Z) - Influence Maximization via Graph Neural Bandits [54.45552721334886]
IM問題を多ラウンド拡散キャンペーンに設定し,影響を受けやすいユーザ数を最大化することを目的とした。
IM-GNB(Influence Maximization with Graph Neural Bandits)を提案する。
論文 参考訳（メタデータ） (2024-06-18T17:54:33Z) - Multi-Armed Bandits with Network Interference [5.708360037632367]
我々は,学習者が$mathcalA$アクション(カウント)を$T$ラウンド以上の$N$ユニット(グッド)に逐次割り当てて,後悔を最小限に抑えるマルチアームバンディット(MAB)問題について検討する。
従来のMAB問題とは異なり、各ユニットの報酬は他のユニットに割り当てられた処理に依存する。
後悔を最小限に抑えるため、単純で線形回帰に基づくアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-05-28T22:01:50Z) - An Effective Branch-and-Bound Algorithm with New Bounding Methods for
the Maximum $s$-Bundle Problem [9.400610985728441]
最大s束問題(英: Maximum s-Bundle Problem、MBP)は、与えられたグラフ内の最大s束を特定するタスクに対処する問題である。
本稿では,グラフ分割技術を利用した分割型アッパーバウンド(PUB)を導入し,より厳密なアッパーバウンドを実現する。
また,グラフ削減のための前処理において,初期下界とPUBを利用する新しいBnBアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-02-06T06:05:11Z) - Graph Signal Sampling for Inductive One-Bit Matrix Completion: a
Closed-form Solution [112.3443939502313]
グラフ信号解析と処理の利点を享受する統合グラフ信号サンプリングフレームワークを提案する。
キーとなる考え方は、各ユーザのアイテムのレーティングをアイテムイットグラフの頂点上の関数(信号)に変換することである。
オンライン設定では、グラフフーリエ領域における連続ランダムガウス雑音を考慮したベイズ拡張(BGS-IMC)を開発する。
論文 参考訳（メタデータ） (2023-02-08T08:17:43Z) - Local Graph-homomorphic Processing for Privatized Distributed Systems [57.14673504239551]
付加雑音は学習モデルの性能に影響を与えないことを示す。
これは、分散アルゴリズムの差分プライバシーに関する以前の研究に対して、大きな改善である。
論文 参考訳（メタデータ） (2022-10-26T10:00:14Z) - Inverse Boundary Value and Optimal Control Problems on Graphs: A Neural
and Numerical Synthesis [0.0]
現在のアーキテクチャにおける重要な要素は、境界を注入したメッセージパッシングニューラルネットワークです。
境界から離れたノードでの予測を安定化するのに役立つグラフィカル距離に基づく正規化手法が導入された。
論文 参考訳（メタデータ） (2022-06-06T21:26:23Z) - Optimal Clustering with Bandit Feedback [57.672609011609886]
本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。
これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。
合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
論文 参考訳（メタデータ） (2022-02-09T06:05:05Z) - Efficient Algorithms for Finite Horizon and Streaming Restless
Multi-Armed Bandit Problems [30.759279275710078]
インデックスベースのソリューションを計算するための新しいスケーラブルなアプローチを提案します。
コストのかかる有限地平線問題を解くことなく,指数減衰をキャプチャするアルゴリズムを提供する。
当社のアルゴリズムは、これらのタスクにおける既存の方法よりも150倍以上のスピードアップを実現し、パフォーマンスを損ないません。
論文 参考訳（メタデータ） (2021-03-08T13:10:31Z) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。
非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
論文 参考訳（メタデータ） (2020-10-23T09:12:47Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
データから制約をマイニングするための一般的なフレームワークを提案する。
特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。
提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
論文 参考訳（メタデータ） (2020-06-18T20:09:53Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。