論文の概要: Decentralized Asynchronous Multi-player Bandits

• arxiv url: http://arxiv.org/abs/2509.25824v1
• Date: Tue, 30 Sep 2025 05:57:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-01 17:09:04.44792
• Title: Decentralized Asynchronous Multi-player Bandits
• Title（参考訳）: 分散非同期マルチプレイヤーバンド
• Authors: Jingqi Fan, Canzhe Zhao, Shuai Li, Siwei Wang,
• Abstract要約: マルチプレイヤーマルチアームバンド (MP-MAB) は、認知無線ネットワークやモノのインターネットシステムに広く応用されているため、広く研究されている。 我々は,プレイヤーが探索と搾取の間で適応的に変化する新しいアルゴリズムを開発した。 我々のアルゴリズムは$mathcalO(sqrtT log T + log T/Delta2)$を後悔させる。
• 参考スコア（独自算出の注目度）: 14.867176164363501
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In recent years, multi-player multi-armed bandits (MP-MAB) have been extensively studied due to their wide applications in cognitive radio networks and Internet of Things systems. While most existing research on MP-MAB focuses on synchronized settings, real-world systems are often decentralized and asynchronous, where players may enter or leave the system at arbitrary times, and do not have a global clock. This decentralized asynchronous setting introduces two major challenges. First, without a global time, players cannot implicitly coordinate their actions through time, making it difficult to avoid collisions. Second, it is important to detect how many players are in the system, but doing so may cost a lot. In this paper, we address the challenges posed by such a fully asynchronous setting in a decentralized environment. We develop a novel algorithm in which players adaptively change between exploration and exploitation. During exploration, players uniformly pull their arms, reducing the probability of collisions and effectively mitigating the first challenge. Meanwhile, players continue pulling arms currently exploited by others with a small probability, enabling them to detect when a player has left, thereby addressing the second challenge. We prove that our algorithm achieves a regret of $\mathcal{O}(\sqrt{T \log T} + {\log T}/{\Delta^2})$, where $\Delta$ is the minimum expected reward gap between any two arms. To the best of our knowledge, this is the first efficient MP-MAB algorithm in the asynchronous and decentralized environment. Extensive experiments further validate the effectiveness and robustness of our algorithm, demonstrating its applicability to real-world scenarios.
• Abstract（参考訳）: 近年,認知無線ネットワークやモノのインターネットシステムに広く応用されているため,MP-MAB(Multi-player multi-armed bandits)が広く研究されている。 MP-MABに関する既存の研究は同期設定に重点を置いているが、現実世界のシステムはしばしば分散化され非同期であり、プレイヤーは任意のタイミングでシステムに入退し、グローバルクロックを持たない。 この分散非同期設定は2つの大きな課題をもたらす。 まず、グローバルな時間なしでは、プレイヤーは時間を通して暗黙的に行動を調整することができず、衝突を避けることは困難である。 第二に、システム内のプレイヤーの数を検出することが重要ですが、それを行うのに多くのコストがかかります。 本稿では、分散環境において、このような完全に非同期な設定によって引き起こされる課題に対処する。 我々は,プレイヤーが探索と搾取の間で適応的に変化する新しいアルゴリズムを開発した。 探索中、プレイヤーは腕を均一に引っ張り、衝突の確率を減らし、最初の挑戦を効果的に軽減する。 一方、プレイヤーは現在、小さな確率で他のプレイヤーが利用している腕を引っ張り続け、プレイヤーがいつ去ったかを検出し、第二の課題に対処する。 我々は,このアルゴリズムが$\mathcal{O}(\sqrt{T \log T} + {\log T}/{\Delta^2})$を後悔することを証明する。 我々の知る限り、これは非同期および分散環境における最初の効率的なMP-MABアルゴリズムである。 大規模な実験により、我々のアルゴリズムの有効性とロバスト性をさらに検証し、実世界のシナリオに適用可能であることを示す。

関連論文リスト

• Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
  我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。 課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。 我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-08-20T13:57:00Z)
• Multi-Player Approaches for Dueling Bandits [58.442742345319225]
  Follow Your Leaderのブラックボックスアプローチの直接的な使用は、この設定の低いバウンダリと一致することを示す。 また,Condorcet-Winnerレコメンデーションプロトコルを用いて,メッセージパッシングによる完全分散アプローチも分析する。
  論文  参考訳（メタデータ） (2024-05-25T10:25:48Z)
• Leading the Pack: N-player Opponent Shaping [52.682734939786464]
  我々は、複数のコプレーヤと複数のシェーピングエージェントを含む環境に、対向型シェーピング(OS)メソッドを拡張します。 多数のコプレーヤでプレイすると,OSメソッドの相対的な性能が低下し,OSメソッドが動作しない可能性が示唆された。
  論文  参考訳（メタデータ） (2023-12-19T20:01:42Z)
• Hardness of Independent Learning and Sparse Equilibrium Computation in Markov Games [70.19141208203227]
  マルコフゲームにおける分散型マルチエージェント強化学習の問題点を考察する。 我々は,全てのプレイヤーが独立に実行すると,一般のサムゲームにおいて,アルゴリズムが到達しないことを示す。 我々は,全てのエージェントが集中型アルゴリズムによって制御されるような,一見簡単な設定であっても,下位境界が保持されていることを示す。
  論文  参考訳（メタデータ） (2023-03-22T03:28:12Z)
• Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits [6.732901486505047]
  マルチプレイヤーのマルチアームバンディットは、認知無線システムへの応用を動機とした、ますます関連する意思決定問題である。 本稿では、前述のモデリング問題に対処することを目的とした、テキストマルチプレーヤのマルチアームウォーキングバンディットモデルを提案する。
  論文  参考訳（メタデータ） (2022-12-12T23:26:02Z)
• Multi-Player Multi-Armed Bandits with Finite Shareable Resources Arms: Learning Algorithms & Applications [32.313813562222066]
  本研究では,分散化されたプレイヤーが協調して同じマルチアームバンディットをプレイし,総累積報酬を最大化する方法について検討する。 既存のMMABモデルは、複数のプレイヤーが同じ腕を引っ張った場合、衝突を起こし、報酬がゼロになるか、衝突が無く、独立した報酬が得られると仮定する。 衝突と非衝突設定の拡張として,共有可能な資源を持つMMABを提案する。
  論文  参考訳（メタデータ） (2022-04-28T13:46:59Z)
• Selfish Robustness and Equilibria in Multi-Player Bandits [25.67398941667429]
  ゲームでは、複数のプレイヤーが同時に腕を引いて、同じ腕を同時に引っ張る場合、0の報酬で衝突する。 プレイヤーが集団報酬を最大化する協力的ケースは、主に考慮されてきたが、悪意のあるプレイヤーにとっては非常に重要かつ困難な問題である。 代わりに、社会的福祉を犠牲にして、個人の報酬を最大化するインセンティブを持つより自然な利己的なプレイヤーについて検討する。
  論文  参考訳（メタデータ） (2020-02-04T09:50:28Z)

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

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