論文の概要: Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits
- arxiv url: http://arxiv.org/abs/2212.06279v1
- Date: Mon, 12 Dec 2022 23:26:02 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-14 13:16:26.210880
- Title: Decentralized Stochastic Multi-Player Multi-Armed Walking Bandits
- Title（参考訳）: 分散確率的マルチプレイヤーマルチアーム歩行バンディット
- Authors: Guojun Xiong, Jian Li
- Abstract要約: マルチプレイヤーのマルチアームバンディットは、認知無線システムへの応用を動機とした、ますます関連する意思決定問題である。
本稿では、前述のモデリング問題に対処することを目的とした、テキストマルチプレーヤのマルチアームウォーキングバンディットモデルを提案する。
- 参考スコア（独自算出の注目度）: 6.732901486505047
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Multi-player multi-armed bandit is an increasingly relevant decision-making
problem, motivated by applications to cognitive radio systems. Most research
for this problem focuses exclusively on the settings that players have
\textit{full access} to all arms and receive no reward when pulling the same
arm. Hence all players solve the same bandit problem with the goal of
maximizing their cumulative reward. However, these settings neglect several
important factors in many real-world applications, where players have
\textit{limited access} to \textit{a dynamic local subset of arms} (i.e., an
arm could sometimes be ``walking'' and not accessible to the player). To this
end, this paper proposes a \textit{multi-player multi-armed walking bandits}
model, aiming to address aforementioned modeling issues. The goal now is to
maximize the reward, however, players can only pull arms from the local subset
and only collect a full reward if no other players pull the same arm. We adopt
Upper Confidence Bound (UCB) to deal with the exploration-exploitation tradeoff
and employ distributed optimization techniques to properly handle collisions.
By carefully integrating these two techniques, we propose a decentralized
algorithm with near-optimal guarantee on the regret, and can be easily
implemented to obtain competitive empirical performance.
- Abstract（参考訳）: マルチプレイヤーのマルチアームバンディットは、認知無線システムへの応用による、ますます関連する意思決定問題である。
この問題のほとんどの研究は、プレイヤーがすべての腕に \textit{full access} を持ち、同じ腕を引っ張るときに報酬を受け取らない設定にのみ焦点をあてている。
したがって、すべてのプレイヤーは累積報酬の最大化を目標として同じバンディット問題を解決する。
しかし、これらの設定は多くの現実世界のアプリケーションにおいて重要な要素を無視しており、プレイヤーは \textit{a dynamic local subset of arms} に \textit{limited access} を持つ(つまり、腕は 'walking' で、プレイヤーにはアクセスできないことがある)。
そこで本稿では,上記のモデリング問題に対処するために,多人数マルチプレイヤー歩行バンディットモデルを提案する。
現在の目標は、報酬を最大化することだが、プレイヤーはローカルのサブセットからのみ腕を引くことができ、他のプレイヤーが同じ腕を引かなければ完全な報酬を得られる。
我々は,探索・爆発のトレードオフに対処するためにuper confidence bound(ucb)を採用し,衝突を適切に処理するために分散最適化技術を採用する。
そこで本研究では,これら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) - Provably Efficient Generalized Lagrangian Policy Optimization for Safe
Multi-Agent Reinforcement Learning [105.7510838453122]
制約付きマルコフゲームを用いたオンライン安全なマルチエージェント強化学習について検討する。
我々は,このラグランジアン問題を解くための高信頼強化学習アルゴリズムを開発した。
提案アルゴリズムは,オンラインミラー降下によるミニマックス決定主元変数と,投影勾配ステップによる双対変数を更新する。
論文 参考訳（メタデータ） (2023-05-31T22:09:24Z) - Competing for Shareable Arms in Multi-Player Multi-Armed Bandits [29.08799537067425]
本稿では,プレイヤーが自尊心を持ち,自己報酬を最大化することを目的とした,新しいマルチプレイヤーマルチアームバンディット(MPMAB)について検討する。
本稿では, 平均アロケーション (SMAA) を用いた新たな自己中心型MPMABを提案する。
我々は,一人の利己的なプレイヤーが,逸脱によって報酬を著しく増加させることはできず,また,他のプレイヤーの報酬に有害な影響も与えないことを確認した。
論文 参考訳（メタデータ） (2023-05-30T15:59:56Z) - Multi-Player Multi-Armed Bandits with Finite Shareable Resources Arms:
Learning Algorithms & Applications [32.313813562222066]
本研究では,分散化されたプレイヤーが協調して同じマルチアームバンディットをプレイし,総累積報酬を最大化する方法について検討する。
既存のMMABモデルは、複数のプレイヤーが同じ腕を引っ張った場合、衝突を起こし、報酬がゼロになるか、衝突が無く、独立した報酬が得られると仮定する。
衝突と非衝突設定の拡張として,共有可能な資源を持つMMABを提案する。
論文 参考訳（メタデータ） (2022-04-28T13:46:59Z) - 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) - Efficient Pure Exploration for Combinatorial Bandits with Semi-Bandit
Feedback [51.21673420940346]
コンビナーシャルバンディットはマルチアームバンディットを一般化し、エージェントが腕のセットを選択し、選択したセットに含まれる各腕の騒々しい報酬を観察します。
我々は, 最善の腕を一定の信頼度で識別する純粋爆発問題と, 応答集合の構造が動作集合の1つと異なるような, より一般的な設定に注目する。
有限多面体に対するプロジェクションフリーオンライン学習アルゴリズムに基づいて、凸的に最適であり、競争力のある経験的性能を持つ最初の計算効率の良いアルゴリズムである。
論文 参考訳（メタデータ） (2021-01-21T10:35:09Z) - Bandit Learning in Decentralized Matching Markets [82.39061186055775]
私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。
このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。
アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
論文 参考訳（メタデータ） (2020-12-14T08:58:07Z) - Selfish Robustness and Equilibria in Multi-Player Bandits [25.67398941667429]
ゲームでは、複数のプレイヤーが同時に腕を引いて、同じ腕を同時に引っ張る場合、0の報酬で衝突する。
プレイヤーが集団報酬を最大化する協力的ケースは、主に考慮されてきたが、悪意のあるプレイヤーにとっては非常に重要かつ困難な問題である。
代わりに、社会的福祉を犠牲にして、個人の報酬を最大化するインセンティブを持つより自然な利己的なプレイヤーについて検討する。
論文 参考訳（メタデータ） (2020-02-04T09:50:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。