論文の概要: Competitive Multi-armed Bandit Games for Resource Sharing
- arxiv url: http://arxiv.org/abs/2503.20975v1
- Date: Wed, 26 Mar 2025 20:35:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-03-28 12:51:34.716765
- Title: Competitive Multi-armed Bandit Games for Resource Sharing
- Title（参考訳）: 資源共有のための競争型マルチアームバンドゲーム
- Authors: Hongbo Li, Lingjie Duan,
- Abstract要約: 現代の資源共有システムでは、複数のエージェントが未知の状態の限られたリソースにアクセスしてタスクを実行する。
本稿では,N-player K-arm competitive MAB gameについて検討し,N-myopic player(エージェント)が互いに競い合い,未知の腕の多様な個人推定を行う。
- 参考スコア（独自算出の注目度）: 17.986928810925686
- License:
- Abstract: In modern resource-sharing systems, multiple agents access limited resources with unknown stochastic conditions to perform tasks. When multiple agents access the same resource (arm) simultaneously, they compete for successful usage, leading to contention and reduced rewards. This motivates our study of competitive multi-armed bandit (CMAB) games. In this paper, we study a new N-player K-arm competitive MAB game, where non-myopic players (agents) compete with each other to form diverse private estimations of unknown arms over time. Their possible collisions on same arms and time-varying nature of arm rewards make the policy analysis more involved than existing studies for myopic players. We explicitly analyze the threshold-based structures of social optimum and existing selfish policy, showing that the latter causes prolonged convergence time $\Omega(\frac{K}{\eta^2}\ln({\frac{KN}{\delta}}))$, while socially optimal policy with coordinated communication reduces it to $\mathcal{O}(\frac{K}{N\eta^2}\ln{(\frac{K}{\delta})})$. Based on the comparison, we prove that the competition among selfish players for the best arm can result in an infinite price of anarchy (PoA), indicating an arbitrarily large efficiency loss compared to social optimum. We further prove that no informational (non-monetary) mechanism (including Bayesian persuasion) can reduce the infinite PoA, as the strategic misreporting by non-myopic players undermines such approaches. To address this, we propose a Combined Informational and Side-Payment (CISP) mechanism, which provides socially optimal arm recommendations with proper informational and monetary incentives to players according to their time-varying private beliefs. Our CISP mechanism keeps ex-post budget balanced for social planner and ensures truthful reporting from players, achieving the minimum PoA=1 and same convergence time as social optimum.
- Abstract（参考訳）: 現代の資源共有システムでは、複数のエージェントが未知の確率条件で限られた資源にアクセスしてタスクを実行する。
複数のエージェントが同じリソース(アーム)を同時にアクセスすると、彼らはうまく使用するために競争し、競合と報酬の削減につながる。
このことは、競争力のあるマルチアーム・バンディット(CMAB)ゲームの研究を動機付けている。
本稿では,N-player K-arm competitive MAB gameについて検討し,N-myopic player(エージェント)が互いに競い合い,時間とともに未知の腕の様々な個人推定を行う。
同じ腕に衝突する可能性があり、腕の報酬の時間的変化は、既存のミオピックプレイヤーの研究よりも政策分析に関係している。
社会最適化と既存の自己資本政策のしきい値に基づく構造を明示的に分析し、後者が長い収束時間$\Omega(\frac{K}{\eta^2}\ln({\frac{KN}{\delta}}))$であるのに対し、協調通信による社会的に最適な政策は$\mathcal{O}(\frac{K}{N\eta^2}\ln{(\frac{K}{\delta})})$であることを示す。
比較により,ベストアームに対する利己的な選手同士の競争が無限の価格のアナーキ(PoA)をもたらすことを証明し,社会的最適性と比較して任意の効率損失を示す。
さらに、非筋電図プレーヤーによる戦略的誤報がそのようなアプローチを損なうため、情報的(非金銭的)メカニズム(ベイズ的説得を含む)が無限のPoAを減少させることはないことを証明した。
そこで本稿では,CISP(Combined Informational and Side-Payment)機構を提案する。
当社のCISP機構は,ソーシャルプランナーに対するポスト予算のバランスを保ち,プレイヤーからの真正な報告を確実にし,最小のPoA=1とソーシャル最適の収束時間を達成する。
関連論文リスト
- Strategic Multi-Armed Bandit Problems Under Debt-Free Reporting [21.14355421498382]
我々は、古典的なマルチアームバンディット問題を考えるが、戦略的な武器で考える。
両腕が真に振る舞う平衡を確立するための新しいメカニズムを導入し、その報酬をできるだけ多く開示する。
この機構により、エージェントは腕の中で2番目に高い(真の)報酬を得ることができ、累積的後悔は$O(log(T)/Delta)$(problem-dependent)または$O(sqrtTlog(T))$(worst-case)で束縛される。
論文 参考訳（メタデータ） (2025-01-27T13:01:34Z) - Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。
課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。
我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
論文 参考訳（メタデータ） (2024-08-20T13:57:00Z) - Optimistic Policy Gradient in Multi-Player Markov Games with a Single
Controller: Convergence Beyond the Minty Property [89.96815099996132]
単一コントローラを用いたマルチプレイヤーゲームにおいて,楽観的なポリシー勾配手法を特徴付ける新しいフレームワークを開発した。
我々のアプローチは、我々が導入する古典的なミニティの自然一般化に依存しており、マルコフゲームを超えてさらなる応用が期待できる。
論文 参考訳（メタデータ） (2023-12-19T11:34:10Z) - Bandits Meet Mechanism Design to Combat Clickbait in Online
Recommendation [50.469872635246176]
我々は,マルチアームバンディット問題の戦略的変種について検討し,これを戦略的クリックバンディット(Click-bandit)と呼ぶ。
このモデルは、推奨項目の選択がクリックスルー率とクリック後の報酬の両方に依存するオンラインレコメンデーションのアプリケーションによって動機付けられている。
論文 参考訳（メタデータ） (2023-11-27T09:19:01Z) - Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals [0.9831489366502302]
予算的マルチアーマッド・バンドイット(MAB)問題について検討し、プレイヤーが期待できない報酬とコストでK$アームから選択する。
非対称な信頼区間を用いた新しいアッパー信頼境界(UCB)サンプリングポリシーである$omega$-UCBを提案する。
これらの間隔は、サンプル平均とランダム変数の境界との間の距離でスケールし、報酬コスト比をより正確かつ厳密に推定する。
論文 参考訳（メタデータ） (2023-06-12T12:35:16Z) - Competing for Shareable Arms in Multi-Player Multi-Armed Bandits [29.08799537067425]
本稿では,プレイヤーが自尊心を持ち,自己報酬を最大化することを目的とした,新しいマルチプレイヤーマルチアームバンディット(MPMAB)について検討する。
本稿では, 平均アロケーション (SMAA) を用いた新たな自己中心型MPMABを提案する。
我々は,一人の利己的なプレイヤーが,逸脱によって報酬を著しく増加させることはできず,また,他のプレイヤーの報酬に有害な影響も与えないことを確認した。
論文 参考訳（メタデータ） (2023-05-30T15:59:56Z) - How Bad is Selfish Driving? Bounding the Inefficiency of Equilibria in
Urban Driving Games [64.71476526716668]
我々は,任意の平衡選手がプレーに同意するであろう効率について検討する。
我々は、アナーキーの価格に関する既存の境界を洗練させる保証を得る。
提案手法はオープンループ軌道に対する懸念を保証しているが,エージェントがクローズドループポリシーを採用する場合においても,効率的な平衡を観測する。
論文 参考訳（メタデータ） (2022-10-24T09:32:40Z) - 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) - Multi-Player Multi-Armed Bandits with Finite Shareable Resources Arms:
Learning Algorithms & Applications [32.313813562222066]
本研究では,分散化されたプレイヤーが協調して同じマルチアームバンディットをプレイし,総累積報酬を最大化する方法について検討する。
既存のMMABモデルは、複数のプレイヤーが同じ腕を引っ張った場合、衝突を起こし、報酬がゼロになるか、衝突が無く、独立した報酬が得られると仮定する。
衝突と非衝突設定の拡張として,共有可能な資源を持つMMABを提案する。
論文 参考訳（メタデータ） (2022-04-28T13:46:59Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。