論文の概要: Optimal Analysis for Bandit Learning in Matching Markets with Serial Dictatorship

• arxiv url: http://arxiv.org/abs/2512.06758v1
• Date: Sun, 07 Dec 2025 09:45:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-09 22:03:54.511834
• Title: Optimal Analysis for Bandit Learning in Matching Markets with Serial Dictatorship
• Title（参考訳）: 実時間ディクタシップを考慮した市場における帯域学習の最適分析
• Authors: Zilong Wang, Shuai Li,
• Abstract要約: 本稿では,市場がシリアル独裁を満足する場合に,$Oleft( fracNlog(T)2 + fracKlog(T) right)$ regret bound を求めるマルチレベル連続選択アルゴリズムを提案する。 我々の知る限りでは、市場と盗賊をマッチングする問題の下位境界に一致するアルゴリズムを最初に提案する。
• 参考スコア（独自算出の注目度）: 11.735287543240688
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The problem of two-sided matching markets is well-studied in computer science and economics, owing to its diverse applications across numerous domains. Since market participants are usually uncertain about their preferences in various online matching platforms, an emerging line of research is dedicated to the online setting where one-side participants (players) learn their unknown preferences through multiple rounds of interactions with the other side (arms). Sankararaman et al. provide an $Ω\left( \frac{N\log(T)}{Δ^2} + \frac{K\log(T)}Δ \right)$ regret lower bound for this problem under serial dictatorship assumption, where $N$ is the number of players, $K (\geq N)$ is the number of arms, $Δ$ is the minimum reward gap across players and arms, and $T$ is the time horizon. Serial dictatorship assumes arms have the same preferences, which is common in reality when one side participants have a unified evaluation standard. Recently, the work of Kong and Li proposes the ET-GS algorithm and achieves an $O\left( \frac{K\log(T)}{Δ^2} \right)$ regret upper bound, which is the best upper bound attained so far. Nonetheless, a gap between the lower and upper bounds, ranging from $N$ to $K$, persists. It remains unclear whether the lower bound or the upper bound needs to be improved. In this paper, we propose a multi-level successive selection algorithm that obtains an $O\left( \frac{N\log(T)}{Δ^2} + \frac{K\log(T)}Δ \right)$ regret bound when the market satisfies serial dictatorship. To the best of our knowledge, we are the first to propose an algorithm that matches the lower bound in the problem of matching markets with bandits.
• Abstract（参考訳）: 両面マッチング市場の問題は、様々な分野にまたがる多様な応用のために、コンピュータ科学と経済学においてよく研究されている。 市場参加者は通常、様々なオンラインマッチングプラットフォームでの好みについて不透明であるため、一方の参加者(プレイヤー)が他方(アーム)との複数ラウンドの相互作用を通じて未知の好みを学習するオンライン環境に、新たな研究ラインが設けられている。 Sankararaman et al は$Ω\left( \frac{N\log(T)}{Δ^2} + \frac{K\log(T)}Δ \right)$ regret lower bound for this problem for this problem under serial dictatorship assumption, where $N$ is the number of player, $K (\geq N)$ is the number of arms, $Δ$ is the least reward gap between player and arms, $T$ is the time horizon。 現実的な独裁は、腕が同じ好みを持っていると仮定し、一方の参加者が統一された評価基準を持つのが現実である。 最近、KongとLiの研究はET-GSアルゴリズムを提案し、これまでに達成された最高の上限である$O\left( \frac{K\log(T)}{Δ^2} \right)$ regret upper boundを達成する。 それでも、下限と上限の間のギャップは、$N$から$K$まで持続する。 下限と上限を改良する必要があるかは、まだ不明である。 本稿では,市場がシリアル独裁を満足する場合に,$O\left( \frac{N\log(T)}{Δ^2} + \frac{K\log(T)}Δ \right)$ regret boundを求める多段階連続選択アルゴリズムを提案する。 我々の知る限りでは、市場と盗賊をマッチングする問題の下位境界に一致するアルゴリズムを最初に提案する。

関連論文リスト

• 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)
• Near-Optimal Reinforcement Learning with Self-Play under Adaptivity Constraints [21.412085244757336]
  適応性制約を伴うマルチエージェント強化学習(MARL)の問題について検討する。 2つのプレイヤーゼロサムマルコフゲームに対して、$widetildeO(sqrtH3 S2 ABK)$を後悔する(政治)排除に基づくアルゴリズムを設計する。 バッチ複雑性の低い$Omega(fracHlog_AK+loglog K)$を$widetildeO(sqrtK)$で証明する。
  論文  参考訳（メタデータ） (2024-02-02T03:00:40Z)
• Improved Bandits in Many-to-one Matching Markets with Incentive Compatibility [12.05174711411919]
  両面のマッチング市場は、そのリッチな応用のために、文献で広く研究されている。 まず,1対1設定のための既存のアルゴリズムをこのより一般的な設定に拡張し,プレイヤー最適後悔に対するほぼ最適境界を実現することを示す。 本稿では,アダプティブ・サーベイ・then-deferred (AETDA) アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-01-03T03:45:35Z)
• Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
  本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。 本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。 我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
  論文  参考訳（メタデータ） (2023-10-02T08:15:52Z)
• Horizon-Free and Variance-Dependent Reinforcement Learning for Latent Markov Decision Processes [62.90204655228324]
  我々は,後期マルコフ決定過程(LMDP)における強化学習(RL)の文脈を考慮した後悔の最小化について検討した。 我々は,モデル最適化と値最適化の両手法でインスタンス化できる,新しいモデルベースアルゴリズムフレームワークを設計する。
  論文  参考訳（メタデータ） (2022-10-20T21:32:01Z)
• Variance-Aware Sparse Linear Bandits [64.70681598741417]
  余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。 ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。 我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
  論文  参考訳（メタデータ） (2022-05-26T15:55:44Z)
• Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits with Linear Payoff Functions [53.77572276969548]
  我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。 一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-20T04:29:18Z)
• Contextual Blocking Bandits [35.235375147227124]
  我々は,多腕バンディット問題の新たな変種について検討し,各ステップごとに,腕の平均報酬を決定する独立したサンプルコンテキストをプレイヤーが観察する。 アームを再生することで(すべてのコンテキストにわたって)将来の時間ステップの固定および既知の回数をブロックする。 我々は、$mathcalO(log T)$-regret w.r.t.$alpha$regret戦略を$Tタイムステップで保証し、$Omega(log(T)$low boundと一致する UCB ベースのフル情報アルゴリズムの変種を提案する。
  論文  参考訳（メタデータ） (2020-03-06T20:34:42Z)

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

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