論文の概要: Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits

• arxiv url: http://arxiv.org/abs/2610.18514v1
• Date: Tue, 13 Oct 2026 15:07:03 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-16 21:01:01.339769
• Title: Approximating Optimal Policies in Heterogeneous Asynchronous Multi-player Bandits
• Title（参考訳）: 不均一な非同期マルチプレイヤーバンドにおける最適ポリシーの近似
• Abstract要約: MMAB(Multi-player multi-armed bandits)は、認知無線ネットワークへの応用が動機である。 実際の関連性にもかかわらず、この設定は比較的検討されていない。 グリーディアルゴリズムは最適なアロケーションの$frac1e$-approximationを実現できることを示す。
• 参考スコア（独自算出の注目度）: 33.540490103058396
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by applications to cognitive radio networks, multi-player multi-armed bandits (MMAB) have attracted considerable attention in recent years. The asynchronous variant, in which players are active only at a fraction of timesteps, better reflects real-world decentralized networks, where devices are not permanently active. Despite its practical relevance, this setting remains relatively understudied. Existing work on asynchronous MMAB has focused on homogeneous players, who share the same activation probability, a setting in which the optimal centralized allocation can be easily characterized. In contrast, efficiently computing the optimal allocation in the heterogeneous setting, where players have different activation probabilities, has remained an open problem. In this work, we investigate this problem and first establish its NP-hardness. We then turn to the greedy algorithm, which runs in polynomial time, and prove that it achieves a $\frac{1}{e}$-approximation of the optimal allocation. Furthermore, when players are processed in decreasing order of their activation probabilities, the approximation guarantee improves to $\frac{1}{\sqrt{e}}$. Overall, our results establish the greedy algorithm as an efficient approximation to the optimal allocation, providing a practical oracle baseline for the design of online algorithms for heterogeneous asynchronous multi-player bandits.
• Abstract（参考訳）: 近年,認知無線ネットワークへの応用により,マルチプレイヤーマルチアームバンド (MMAB) が注目されている。 プレイヤーが少数のタイムステップでのみアクティブになる非同期型は、デバイスが永久にアクティブでない現実世界の分散ネットワークをよりよく反映する。 実際の関連性にもかかわらず、この設定は比較的検討されていない。 非同期MMABにおける既存の作業は、同じアクティベーション確率を共有する均質なプレイヤーに焦点を当てている。 対照的に、プレイヤーが異なるアクティベーション確率を持つヘテロジニアス環境での最適割り当てを効率的に計算することは、未解決の問題のままである。 本研究では,この問題を考察し,まずNP硬度を確立する。 次に、多項式時間で実行されるgreedyアルゴリズムに目を向け、最適な割り当ての $\frac{1}{e}$-approximation を達成することを証明します。 さらに、プレイヤーがアクティベーション確率の順に処理されると、近似保証は$\frac{1}{\sqrt{e}}$に改善される。 全体として,提案アルゴリズムは最適アロケーションの効率的な近似法として確立され,ヘテロジニアス非同期マルチプレイヤーバンディットのためのオンラインアルゴリズム設計のための実用的なオラクルベースラインを提供する。

関連論文リスト

• Breaking $\textit{Winner-Takes-All}$: Cooperative Policy Optimization Improves Diverse LLM Reasoning [53.42577591449649]
  グループ協力政策最適化は、トレーニングパラダイムをロールアウト競争からチーム協力へとシフトさせる。 GCPOは独立したロールアウトスコアをチームレベルのクレジット割り当てに置き換える。 チームへの平均的な限界貢献に従って、各ロールアウトに対して、グループチームの報酬を再分配する。
  論文  参考訳（メタデータ） (2026-05-12T03:20:24Z)
• Similarity-based Portfolio Construction for Black-box Optimization [0.13764085113103217]
  自然な対策は、評価予算を、潜在的に異なるアルゴリズムの複数の実行に分割することである。 完全なトレーニングセット上に構築されたナイーブなポートフォリオが,これまでで最強のベースラインをすでに上回っていることを示す。 次に、単純なk-nearest-neighbor-based finetuningアプローチを提案し、未確認インスタンスに適したポートフォリオを構築する。
  論文  参考訳（メタデータ） (2026-04-20T12:48:28Z)
• Distributed Algorithms for Multi-Agent Multi-Armed Bandits with Collision [16.136111977594087]
  マルチプレイヤーマルチアーマッド・バンドイット(MMAB)問題について検討し、複数のプレイヤーが腕を選択して累積報酬を最大化する。 我々は,各プレイヤーが自身の行動と衝突フィードバックのみを観察できるような,中央調整のない分散環境を考える。 本稿では,適応的かつ効率的な通信プロトコルを用いた分散アルゴリズムを提案する。このアルゴリズムは,通信コストが$mathcalO(loglog T)$で,ほぼ最適なグループと個人の後悔を実現する。
  論文  参考訳（メタデータ） (2025-10-08T06:12:59Z)
• QuACK: A Multipurpose Queuing Algorithm for Cooperative $k$-Armed Bandits [5.530212768657544]
  我々は、$m$エージェントのネットワークが協調して最適な行動を見つける、協調的な$k$武器の盗賊問題を研究する。 単一エージェントのバンディットアルゴリズムをマルチエージェント設定に拡張できるブラックボックスリダクションを提供する。
  論文  参考訳（メタデータ） (2024-10-31T12:20:36Z)
• Decentralized Multi-Task Online Convex Optimization Under Random Link Failures [5.513958040574729]
  我々は不均一な確率を持つランダムリンク障害に対する頑健な分散型サドルポイントアルゴリズムを開発した。 我々はアルゴリズムと分析を2点の帯域フィードバックシナリオに拡張する。
  論文  参考訳（メタデータ） (2024-01-04T00:57:33Z)
• Provably Efficient Fictitious Play Policy Optimization for Zero-Sum Markov Games with Structured Transitions [145.54544979467872]
  本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。 我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。 提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
  論文  参考訳（メタデータ） (2022-07-25T18:29:16Z)
• Optimal Algorithms for Decentralized Stochastic Variational Inequalities [113.43047601775453]
  この作業は、ますます重要になるが十分に理解されていない分散的な設定に集中する。 通信と局所的な繰り返しの両方の下位境界を示し、これらの下位境界に一致する最適なアルゴリズムを構築する。 我々のアルゴリズムは、分散化されたケースだけでなく、決定論的で非分散的な文献でも利用できる。
  論文  参考訳（メタデータ） (2022-02-06T13:14:02Z)
• Optimal and Efficient Algorithms for General Mixable Losses against Switching Oracles [0.0]
  動的環境における混合損失関数のオンライン最適化について検討する。 我々の結果は、個々のシーケンス方式で強い決定論的意味を持つことが保証されている。
  論文  参考訳（メタデータ） (2021-08-13T21:48:55Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)

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

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