論文の概要: Competing Bandits in Matching Markets via Super Stability

• arxiv url: http://arxiv.org/abs/2506.15926v1
• Date: Thu, 19 Jun 2025 00:03:20 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-23 19:00:04.888613
• Title: Competing Bandits in Matching Markets via Super Stability
• Title（参考訳）: 超安定による市場競争の激化
• Authors: Soumya Basu,
• Abstract要約: 両面の報酬の不確実性を伴う市場における盗賊学習について検討する。 本研究は, 正規GSアルゴリズムよりも拡張Galle-Shapley (GS) アルゴリズムが真に安定なマッチングを実現することの利点を実証する。
• 参考スコア（独自算出の注目度）: 3.846293944458337
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study bandit learning in matching markets with two-sided reward uncertainty, extending prior research primarily focused on single-sided uncertainty. Leveraging the concept of `super-stability' from Irving (1994), we demonstrate the advantage of the Extended Gale-Shapley (GS) algorithm over the standard GS algorithm in achieving true stable matchings under incomplete information. By employing the Extended GS algorithm, our centralized algorithm attains a logarithmic pessimal stable regret dependent on an instance-dependent admissible gap parameter. This algorithm is further adapted to a decentralized setting with a constant regret increase. Finally, we establish a novel centralized instance-dependent lower bound for binary stable regret, elucidating the roles of the admissible gap and super-stable matching in characterizing the complexity of stable matching with bandit feedback.
• Abstract（参考訳）: 両面の報酬の不確実性を伴う市場における盗聴学習について検討し、従来の研究は主に片面の不確実性に焦点を当てていた。 Irving (1994) の 'super-stability' の概念を活用することで、不完全情報の下で真の安定マッチングを実現する上で、標準的な GS アルゴリズムよりも拡張された Gale-Shapley (GS) アルゴリズムの利点を実演する。 拡張GSアルゴリズムを用いることで、集中型アルゴリズムは、インスタンス依存の許容ギャップパラメータに依存する対数的悲観的な安定な後悔を実現する。 このアルゴリズムはさらに、絶え間なく増大する分散化された設定に適応する。 最後に、二元的安定な後悔に対する新しい集中型インスタンス依存の下位境界を確立し、許容ギャップと超安定マッチングの役割を解明し、バンドイットフィードバックと安定マッチングの複雑さを特徴づける。

関連論文リスト

• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  本稿では,誤差確率の指数的減衰を保証し,最適な腕識別のための新しいアルゴリズムを提案する。 我々は,複雑性のレベルが異なる様々な問題インスタンスに対する包括的経験的評価を通じて,アルゴリズムの有効性を検証する。
  論文  参考訳（メタデータ） (2025-06-03T02:56:26Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  我々は$f$-divergence-regularized offline policy learningを分析する。 逆Kullback-Leibler (KL) の発散に対して、単極集中性の下での最初の$tildeO(epsilon-1)$サンプル複雑性を与える。 これらの結果は,$f$-divergence-regularized policy learningの包括的理解に向けて大きな一歩を踏み出したものと考えられる。
  論文  参考訳（メタデータ） (2025-02-09T22:14:45Z)
• Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
  目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。 アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
  論文  参考訳（メタデータ） (2022-11-29T05:52:17Z)
• Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms [14.174806471635403]
  粒子ダイナミック(IPD)に対するグラディエント・ランゲヴィン・ダイナミクス(SGLD)やランダムバッチ法(RBM)などのサンプリングアルゴリズムの近似を考察する。 近似によって生じる雑音は中央極限定理(CLT)によりほぼガウス的であるが、ブラウン運動はまさにガウス的である。 この構造を利用して拡散過程内の近似誤差を吸収し、これらのアルゴリズムの収束保証を改善する。
  論文  参考訳（メタデータ） (2022-06-08T10:17:40Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• Asymptotic Randomised Control with applications to bandits [0.0]
  相関要素を持つ一般的なマルチアームバンディット問題を緩和制御問題として考察する。 エントロピー正規化を導入することにより、値関数への滑らかな近似が得られる。 これにより、最適決定過程の新たな半指数近似が得られる。
  論文  参考訳（メタデータ） (2020-10-14T17:17:48Z)
• On Lower Bounds for Standard and Robust Gaussian Process Bandit Optimization [55.937424268654645]
  有界ノルムを持つ関数のブラックボックス最適化問題に対するアルゴリズム非依存な下界を考える。 本稿では, 単純さ, 汎用性, エラー確率への依存性の向上など, 後悔の下位境界を導出するための新しい証明手法を提案する。
  論文  参考訳（メタデータ） (2020-08-20T03:48:14Z)
• Algorithmic Stability in Fair Allocation of Indivisible Goods Among Two Agents [8.66798555194688]
  正当性の概念や近似効率の弱さとともに、正確な安定性を達成することは不可能であることを示す。 本稿では,安定性,すなわち近似安定性と弱近似安定性の2つの緩和法を提案する。 本稿では、ペアワイズ最大値の割り当てに関する一般的な特徴付けを行い、それを用いてほぼ安定なアルゴリズムを設計する。
  論文  参考訳（メタデータ） (2020-07-30T03:09:02Z)

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

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