論文の概要: Explore-then-Commit Algorithms for Decentralized Two-Sided Matching Markets

• arxiv url: http://arxiv.org/abs/2408.08690v1
• Date: Fri, 16 Aug 2024 12:06:09 GMT
• ステータス: 処理完了
• システム内更新日: 2024-08-19 15:35:21.437582
• Title: Explore-then-Commit Algorithms for Decentralized Two-Sided Matching Markets
• Title（参考訳）: 分散化された二面マッチング市場のための探索的アルゴリズム
• Authors: Tejas Pagare, Avishek Ghosh,
• Abstract要約: 我々は、需要側(プレイヤー)が供給側(アーム)と競合する分散化された二面マッチング市場を研究する。 この問題に対して,エポック型CA-ETC (Collision avoidance explore then commit) (textttCA-ETC,略してtextttCA-ETC) という多相探索型アルゴリズムを提案する。 初期エポック長が$T_circ$で、その後のエポック長が$2l/gamma T_circ$の場合、textttCA-ETC がプレイヤーとなることを示す。
• 参考スコア（独自算出の注目度）: 7.512199306943756
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online learning in a decentralized two-sided matching markets, where the demand-side (players) compete to match with the supply-side (arms), has received substantial interest because it abstracts out the complex interactions in matching platforms (e.g. UpWork, TaskRabbit). However, past works assume that each arm knows their preference ranking over the players (one-sided learning), and each player aim to learn the preference over arms through successive interactions. Moreover, several (impractical) assumptions on the problem are usually made for theoretical tractability such as broadcast player-arm match Liu et al. (2020; 2021); Kong & Li (2023) or serial dictatorship Sankararaman et al. (2021); Basu et al. (2021); Ghosh et al. (2022). In this paper, we study a decentralized two-sided matching market, where we do not assume that the preference ranking over players are known to the arms apriori. Furthermore, we do not have any structural assumptions on the problem. We propose a multi-phase explore-then-commit type algorithm namely epoch-based CA-ETC (collision avoidance explore then commit) (\texttt{CA-ETC} in short) for this problem that does not require any communication across agents (players and arms) and hence decentralized. We show that for the initial epoch length of $T_{\circ}$ and subsequent epoch-lengths of $2^{l/\gamma} T_{\circ}$ (for the $l-$th epoch with $\gamma \in (0,1)$ as an input parameter to the algorithm), \texttt{CA-ETC} yields a player optimal expected regret of $\mathcal{O}\left(T_{\circ} (\frac{K \log T}{T_{\circ} \Delta^2})^{1/\gamma} + T_{\circ} (\frac{T}{T_{\circ}})^\gamma\right)$ for the $i$-th player, where $T$ is the learning horizon, $K$ is the number of arms and $\Delta$ is an appropriately defined problem gap. Furthermore, we propose a blackboard communication based baseline achieving logarithmic regret in $T$.
• Abstract（参考訳）: オンライン学習は、需要側(プレイヤー)がサプライ側(アーム)と競合する分散化された二面マッチング市場において、マッチングプラットフォーム(UpWork、TaskRabbitなど)における複雑なインタラクションを抽象化するため、かなりの関心を集めている。 しかし、過去の研究は、各腕がプレイヤーよりも好みのランク(一方的な学習)を知っていると仮定しており、各プレイヤーは連続した相互作用を通じて武器よりも好みを学習することを目指している。 さらに、この問題に関するいくつかの(実践的でない)仮定は、通常、放送プレーヤーアームマッチのLiu et al (2020; 2021)、Kong & Li (2023)、シリアルディクテーターシップのSankararaman et al (2021)、Basu et al (2021)、Ghosh et al (2022)といった理論的なトラクタビリティに対してなされる。 本稿では,分散化された二面マッチング市場について検討し,プレイヤーに対する選好のランキングが腕のアプリオリ(apriori)で知られていると仮定する。 さらに、この問題に関する構造的な仮定は一切ない。 本稿では,エージェント(プレイヤとアーム)間の通信を必要としない問題に対して,エポックベースのCA-ETC(コリエーション回避探索,コミット)を提案する。 T_{\circ} の初期エポック長が$T_{\circ}$およびそれに続くエポック長が$2^{l/\gamma} T_{\circ}$ ($l-$th epoch with $\gamma \in (0,1)$) の場合、 \texttt{CA-ETC} は$\mathcal{O}\left(T_{\circ} (\frac{K \log T}{T_{\circ} \Delta^2})^{1/\gamma} + T_{\circ} (\frac{T}{T_{\circ}})^\gamma\right)$ ($T は$i$のプレイヤーで、$K は$1のアームの数であり、$K は$$$$$$$$のギャップを適切に定義する。 さらに,対数後悔を実現するブラックボード通信ベースラインを$T$で提案する。

関連論文リスト

• Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
  オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。 我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。 我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
  論文  参考訳（メタデータ） (2024-06-15T13:26:17Z)
• $\widetilde{O}(T^{-1})$ Convergence to (Coarse) Correlated Equilibria in Full-Information General-Sum Markov Games [8.215874655947335]
  楽観的フォロー・ザ・レギュラライズド・リーダー・アルゴリズムは,フル情報汎用マルコフゲームにおいて,$widetildeO(T-1)$-approximate iterationsを$T$内で見つけることができることを示す。
  論文  参考訳（メタデータ） (2024-02-02T20:40:27Z)
• Constant or logarithmic regret in asynchronous multiplayer bandits [22.376992460581594]
  マルチプレイヤーのバンディット問題は、まず探索-then-commit (ETC)アルゴリズムで取り組んだ。 最適ポリシーが各アームに少なくとも1人のプレイヤーを割り当てる場合、常にインスタンス依存の後悔をもたらすアルゴリズムであるCautious Greedyを導入する。
  論文  参考訳（メタデータ） (2023-05-31T09:35:03Z)
• Uncoupled and Convergent Learning in Two-Player Zero-Sum Markov Games with Bandit Feedback [49.1061436241109]
  非漸近収束率の非結合、収束、合理的なアルゴリズムの開発に注力する。 我々のアルゴリズムは[Chen et al., 2021, Cen et al., 2021]と関係があり、エントロピー正規化技術に基づいている。
  論文  参考訳（メタデータ） (2023-03-05T18:08:54Z)
• Minimax-Optimal Multi-Agent RL in Zero-Sum Markov Games With a Generative Model [50.38446482252857]
  2人プレイのゼロサムマルコフゲームは多エージェント強化学習においておそらく最も基本的な設定である。 我々は,$$ widetildeObiggを用いて,$varepsilon$-approximate Markov NEポリシーを学習する学習アルゴリズムを開発した。 我々は、分散型量の役割を明確にするFTRLに対する洗練された後悔境界を導出する。
  論文  参考訳（メタデータ） (2022-08-22T17:24:55Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Bandit Learning in Decentralized Matching Markets [82.39061186055775]
  私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。 このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。 アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
  論文  参考訳（メタデータ） (2020-12-14T08:58:07Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)

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

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