Fugu-MT 論文翻訳(概要): Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions

論文の概要: Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions

arxiv url: http://arxiv.org/abs/2011.03896v1
Date: Sun, 8 Nov 2020 03:14:19 GMT
ステータス: 処理完了
システム内更新日: 2022-09-28 08:20:47.956631
Title: Cooperative and Stochastic Multi-Player Multi-Armed Bandit: Optimal Regret With Neither Communication Nor Collisions
Title（参考訳）: 協調的・確率的マルチプレイヤー・マルチアーム・バンディット:コミュニケーションも衝突も伴わない最適後悔
Authors: S\'ebastien Bubeck, Thomas Budzinski, Mark Sellke
Abstract要約: 我々は、多腕バンディット問題の協調型マルチプレイヤー版を考える。これらの特性は,任意の数の選手や腕に対して達成可能であることを示す。
参考スコア（独自算出の注目度）: 4.974932889340056
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We consider the cooperative multi-player version of the stochastic multi-armed bandit problem. We study the regime where the players cannot communicate but have access to shared randomness. In prior work by the first two authors, a strategy for this regime was constructed for two players and three arms, with regret $\tilde{O}(\sqrt{T})$, and with no collisions at all between the players (with very high probability). In this paper we show that these properties (near-optimal regret and no collisions at all) are achievable for any number of players and arms. At a high level, the previous strategy heavily relied on a $2$-dimensional geometric intuition that was difficult to generalize in higher dimensions, while here we take a more combinatorial route to build the new strategy.
Abstract（参考訳）: 確率的マルチアームバンディット問題の協調型マルチプレイヤー版を考える。プレーヤがコミュニケーションできないが共有ランダム性にアクセスできないような体制について検討する。最初の2人の著者による以前の研究で、この体制の戦略は2人のプレイヤーと3人の腕で構築され、後悔する$\tilde{O}(\sqrt{T})$で、プレイヤー間の衝突が全くなかった(非常に高い確率で)。本稿では,これらの特性(オプティマイズに近く,衝突も全くない)が,どの選手や腕でも達成可能であることを示す。高いレベルでは、以前の戦略は高次元での一般化が難しい2ドルの幾何学的直観に大きく依存していたが、ここでは新しい戦略を構築するためのより組合せ的なルートを取る。

関連論文リスト

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)
Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits [6.732901486505047]
マルチプレイヤーのマルチアームバンディットは、認知無線システムへの応用を動機とした、ますます関連する意思決定問題である。本稿では、前述のモデリング問題に対処することを目的とした、テキストマルチプレーヤのマルチアームウォーキングバンディットモデルを提案する。
論文参考訳（メタデータ） (2022-12-12T23:26:02Z)
The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player Multi-Armed Bandits with no Communication [10.446001329147112]
マルチプレイヤーのマルチアームバンディット問題について検討する。この問題では、$m$プレーヤーは、合計報酬を$K > m$アームから最大化するために協力する。ここで$Delta$は$m$-thと$m+1$-stのベストアームのギャップである。
論文参考訳（メタデータ） (2022-02-19T18:19:36Z)
An Instance-Dependent Analysis for the Cooperative Multi-Player Multi-Armed Bandit [93.97385339354318]
マルチプレイヤーマルチアーマッドバンドにおける情報共有と協調の課題について検討する。まず, プレイヤーの最適度差を推定するために, 逐次的除去戦略への簡単な修正が可能であることを示す。第2に,第1の結果を利用して,衝突の小さな報奨をプレイヤー間の協調に役立てる通信プロトコルを設計する。
論文参考訳（メタデータ） (2021-11-08T23:38:47Z)
Bandit Learning in Decentralized Matching Markets [82.39061186055775]
私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
論文参考訳（メタデータ） (2020-12-14T08:58:07Z)
Multitask Bandit Learning Through Heterogeneous Feedback Aggregation [35.923544685900055]
我々は,この問題を,一組のプレイヤーが一組のアームと同時に相互作用する,$epsilon$-multi-player multi-armed bandit問題として定式化する。我々は、異なるプレイヤーが収集した報酬を適応的に集約する高信頼な有界アルゴリズム、RobostAgg$(epsilon)$を開発する。
論文参考訳（メタデータ） (2020-10-29T07:13:28Z)
Faster Algorithms for Optimal Ex-Ante Coordinated Collusive Strategies in Extensive-Form Zero-Sum Games [123.76716667704625]
我々は,不完全情報ゼロサム拡張形式ゲームにおいて,対戦相手と対決する2人の選手のチームにとって最適な戦略を見つけることの課題に焦点をあてる。この設定では、チームができる最善のことは、ゲーム開始時の関節(つまり相関した)確率分布から潜在的にランダム化された戦略(プレイヤー1人)のプロファイルをサンプリングすることである。各プロファイルにランダム化されるのはチームメンバーの1人だけであるプロファイルのみを用いることで、そのような最適な分布を計算するアルゴリズムを提供する。
論文参考訳（メタデータ） (2020-09-21T17:51:57Z)
Coordination without communication: optimal regret in two players multi-armed bandits [1.6752182911522522]
同一の3本腕バンディットを同時に演奏するエージェントを2つ検討する。プレイヤー間の衝突が全くない戦略を提案する。また、この問題の完全な情報変種に対する下位境界を証明することによって、余剰対数項 $sqrtlog(T)$ は必要であると主張する。
論文参考訳（メタデータ） (2020-02-14T17:35:42Z)
Selfish Robustness and Equilibria in Multi-Player Bandits [25.67398941667429]
ゲームでは、複数のプレイヤーが同時に腕を引いて、同じ腕を同時に引っ張る場合、0の報酬で衝突する。プレイヤーが集団報酬を最大化する協力的ケースは、主に考慮されてきたが、悪意のあるプレイヤーにとっては非常に重要かつ困難な問題である。代わりに、社会的福祉を犠牲にして、個人の報酬を最大化するインセンティブを持つより自然な利己的なプレイヤーについて検討する。
論文参考訳（メタデータ） (2020-02-04T09:50:28Z)

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