論文の概要: Bandit Learning in Decentralized Matching Markets

• arxiv url: http://arxiv.org/abs/2012.07348v3
• Date: Mon, 15 Feb 2021 03:55:05 GMT
• ステータス: 処理完了
• システム内更新日: 2021-05-08 14:36:38.046437
• Title: Bandit Learning in Decentralized Matching Markets
• Title（参考訳）: 分散マッチング市場におけるバンディット学習
• Authors: Lydia T. Liu, Feng Ruan, Horia Mania, Michael I. Jordan
• Abstract要約: 私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。 このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。 アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
• 参考スコア（独自算出の注目度）: 82.39061186055775
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study two-sided matching markets in which one side of the market (the players) does not have a priori knowledge about its preferences for the other side (the arms) and is required to learn its preferences from experience. Also, we assume the players have no direct means of communication. This model extends the standard stochastic multi-armed bandit framework to a decentralized multiple player setting with competition. We introduce a new algorithm for this setting that, over a time horizon $T$, attains $\mathcal{O}(\log(T))$ stable regret when preferences of the arms over players are shared, and $\mathcal{O}(\log(T)^2)$ regret when there are no assumptions on the preferences on either side. Moreover, in the setting where a single player may deviate, we show that the algorithm is incentive compatible whenever the arms' preferences are shared, but not necessarily so when preferences are fully general.
• Abstract（参考訳）: 本研究では、一方の市場(プレイヤー)が他方の市場(腕)に対する嗜好について事前知識を持っておらず、その嗜好を経験から学ぶ必要がある二面マッチング市場について検討する。 また、プレイヤーは直接のコミュニケーション手段を持たないと仮定する。 このモデルは、標準的な確率的マルチアームバンディットフレームワークを、競争を伴う分散マルチプレイヤー設定に拡張する。 この設定に新たなアルゴリズムを導入し、ある時間帯に$T$が$\mathcal{O}(\log(T))$ プレイヤーよりも腕の好みを共有した場合に$\mathcal{O}(\log(T))$ と $\mathcal{O}(\log(T)^2)$ のどちらにも好みの仮定がない場合に$ である。 さらに、一つのプレイヤーが逸脱する可能性のある設定では、腕の好みが共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合は必ずしもそうではない。

関連論文リスト

• Multi-agent Multi-armed Bandits with Stochastic Sharable Arm Capacities [69.34646544774161]
  我々は、各アームへのリクエストの到着とプレイヤーへのリクエストの割り当てポリシーをキャプチャするマルチプレイヤーマルチアーム・バンディット(MAB)モデルの新しいバリエーションを定式化する。 課題は、プレイヤーが最適な腕引きプロファイルに従って腕を選択するように分散学習アルゴリズムを設計する方法である。 我々は,Mラウンドのみの最適腕引きプロファイルにおいて,プレイヤーがコンセンサスに達することを保証した反復分散アルゴリズムを設計する。
  論文  参考訳（メタデータ） (2024-08-20T13:57:00Z)
• Explore-then-Commit Algorithms for Decentralized Two-Sided Matching Markets [7.512199306943756]
  我々は、需要側(プレイヤー)が供給側(アーム)と競合する分散化された二面マッチング市場を研究する。 この問題に対して,エポック型CA-ETC (Collision avoidance explore then commit) (textttCA-ETC,略してtextttCA-ETC) という多相探索型アルゴリズムを提案する。 初期エポック長が$T_circ$で、その後のエポック長が$2l/gamma T_circ$の場合、textttCA-ETC がプレイヤーとなることを示す。
  論文  参考訳（メタデータ） (2024-08-16T12:06:09Z)
• Improved Bandits in Many-to-one Matching Markets with Incentive Compatibility [12.05174711411919]
  両面のマッチング市場は、そのリッチな応用のために、文献で広く研究されている。 まず,1対1設定のための既存のアルゴリズムをこのより一般的な設定に拡張し,プレイヤー最適後悔に対するほぼ最適境界を実現することを示す。 本稿では,アダプティブ・サーベイ・then-deferred (AETDA) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-03T03:45:35Z)
• Player-optimal Stable Regret for Bandit Learning in Matching Markets [12.54215178882448]
  ここでは、各プレイヤーの最適な安定な後悔は、$O(Klog T/Delta2)$、$K$は腕の数、$T$は地平線、$Delta$は、最初の$N+1$の腕の中でプレイヤーの最小の好みの差であることを示す。 我々の研究は、プレイヤー・ペシミカルの安定したマッチング目標がより弱かったり、特別な仮定を持った市場のみに適用されたりした以前の作品を大幅に改善する。
  論文  参考訳（メタデータ） (2023-07-20T14:10:33Z)
• Competing Bandits in Time Varying Matching Markets [1.1470070927586014]
  両面の非定常マッチング市場におけるオンライン学習の課題について検討し,安定したマッチングに収束することが目的である。 非定常性を扱うための単純な再起動戦略を組み合わせたRCB(Restart Competing Bandits)アルゴリズムを提案する。 提案アルゴリズムにより,各プレイヤーは,エージェントの嗜好の変動数に対して,$widetildemathcalO(L1/2_TT1/2)$の均一なサブ線形後悔を受けることを示す。
  論文  参考訳（メタデータ） (2022-10-21T02:36:57Z)
• Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
  我々は平均場相関と粗相関平衡の概念を発展させる。 ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
  論文  参考訳（メタデータ） (2022-08-22T08:31:46Z)
• 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)
• Decentralized Competing Bandits in Non-Stationary Matching Markets [46.13741000158631]
  非定常(動的)環境下での分散化二面マッチング市場の枠組みを紹介する。 分散非定常競合帯域(textttDNCB)を用いた分散非同期学習アルゴリズムの提案と解析を行う。 我々はこの強調探索を特徴付け、texttDNCBのサブ線形(対数的)後悔を得る。
  論文  参考訳（メタデータ） (2022-05-31T21:05:30Z)
• Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
  不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。 私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
  論文  参考訳（メタデータ） (2021-08-19T17:59:28Z)

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

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