論文の概要: Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach
- arxiv url: http://arxiv.org/abs/2602.06404v1
- Date: Fri, 06 Feb 2026 05:53:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-09 22:18:26.248744
- Title: Near-Optimal Regret for Distributed Adversarial Bandits: A Black-Box Approach
- Title（参考訳）: 分散反転帯域に対する準最適レグレット:ブラックボックスアプローチ
- Authors: Hao Qiu, Mengxiao Zhang, Nicolò Cesa-Bianchi,
- Abstract要約: そこでは,N$エージェントが協力してグローバルな平均損失を最小限に抑えつつ,ローカルな損失のみを観察する。
この問題のミニマックス後悔は$tilde(sqrt(-1/2+K/N)T)$であり、$T$は地平線、$K$は行動の数、$は通信行列のスペクトルギャップである。
- 参考スコア（独自算出の注目度）: 26.085126064745378
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study distributed adversarial bandits, where $N$ agents cooperate to minimize the global average loss while observing only their own local losses. We show that the minimax regret for this problem is $\tildeΘ(\sqrt{(ρ^{-1/2}+K/N)T})$, where $T$ is the horizon, $K$ is the number of actions, and $ρ$ is the spectral gap of the communication matrix. Our algorithm, based on a novel black-box reduction to bandits with delayed feedback, requires agents to communicate only through gossip. It achieves an upper bound that significantly improves over the previous best bound $\tilde{O}(ρ^{-1/3}(KT)^{2/3})$ of Yi and Vojnovic (2023). We complement this result with a matching lower bound, showing that the problem's difficulty decomposes into a communication cost $ρ^{-1/4}\sqrt{T}$ and a bandit cost $\sqrt{KT/N}$. We further demonstrate the versatility of our approach by deriving first-order and best-of-both-worlds bounds in the distributed adversarial setting. Finally, we extend our framework to distributed linear bandits in $R^d$, obtaining a regret bound of $\tilde{O}(\sqrt{(ρ^{-1/2}+1/N)dT})$, achieved with only $O(d)$ communication cost per agent and per round via a volumetric spanner.
- Abstract（参考訳）: そこでは,N$エージェントが協力してグローバルな平均損失を最小限に抑えつつ,ローカルな損失のみを観察する。
この問題のミニマックス後悔は$\tilde'(\sqrt{(ρ^{-1/2}+K/N)T})$であり、$T$は地平線、$K$は行動の数、$ρ$は通信行列のスペクトルギャップである。
提案アルゴリズムは,フィードバックが遅れたバンディットに対する新たなブラックボックス削減に基づいて,ゴシップを介してのみ通信する必要がある。
これは、Yi と Vojnovic (2023) の$\tilde{O}(ρ^{-1/3}(KT)^{2/3})$よりも大幅に改善される上限を達成する。
この問題の難易度は通信コスト$ρ^{-1/4}\sqrt{T}$と帯域コスト$\sqrt{KT/N}$に分解されることを示す。
さらに、分散対向的な設定において、一階と一階と一階の境界を導出することで、我々のアプローチの汎用性をさらに実証する。
最後に、我々のフレームワークを$R^d$で分散線形バンドレットに拡張し、$\tilde{O}(\sqrt{(ρ^{-1/2}+1/N)dT})$の後悔境界を得る。
関連論文リスト
- Distributed Online Convex Optimization with Efficient Communication: Improved Algorithm and Lower bounds [27.851263935083736]
圧縮通信を用いた分散オンライン凸最適化について検討する。
本稿では,凸関数と強凸関数に対して,$tildeO(-1/2-1nsqrtT)$と$tildeO(-1-2nlnT)$の改善された後悔境界を実現するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2026-01-08T13:05:36Z) - Bandit Max-Min Fair Allocation [30.8580020414087]
本稿では,BMMFA問題と呼ばれる新たな意思決定問題について検討する。
この問題の目標は、加法的評価を持つエージェント間での最小効用を最大化することである。
この問題の1つの重要な特徴は、各アイテムに対する各エージェントのバリュエーションが半帯域フィードバックによってのみ観察できることである。
論文 参考訳（メタデータ） (2025-05-08T12:09:20Z) - Low-rank Matrix Bandits with Heavy-tailed Rewards [55.03293214439741]
アンダーライン重み付きアンダーラインリワード(LowHTR)を用いたアンダーラインローランク行列バンディットの問題点について検討する。
観測されたペイオフに対するトランケーションと動的探索を利用して,LOTUSと呼ばれる新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-04-26T21:54:31Z) - Adversarial Combinatorial Bandits with Switching Costs [55.2480439325792]
本稿では,各ラウンドで選択したアームのスイッチに対して,切替コストが$lambda$の逆帯域問題について検討する。
ミニマックスの後悔とそれにアプローチするための設計アルゴリズムの限界を低くする。
論文 参考訳（メタデータ） (2024-04-02T12:15:37Z) - Federated Linear Bandits with Finite Adversarial Actions [20.1041278044797]
我々は、M$のクライアントが中央サーバと通信し、線形文脈の帯域幅問題を解決するための連合線形帯域幅モデルについて検討する。
逆有限作用集合のユニークな問題に対処するため、FedSupLinUCBアルゴリズムを提案する。
我々は、FedSupLinUCBが$tildeO(sqrtd T)$の完全後悔を達成したことを証明している。
論文 参考訳（メタデータ） (2023-11-02T03:41:58Z) - 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) - Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。