論文の概要: Probably Correct Optimal Stable Matching under Two-Sided Uncertainty
- arxiv url: http://arxiv.org/abs/2607.04824v1
- Date: Mon, 06 Jul 2026 08:57:30 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-07 22:26:30.092915
- Title: Probably Correct Optimal Stable Matching under Two-Sided Uncertainty
- Title（参考訳）: 2次元不確かさ下での最適安定マッチングの可能性
- Authors: Andreas Athanasopoulos, Anne-Marie George, Christos Dimitrakakis,
- Abstract要約: 両面の嗜好が不明な二面市場における安定マッチングの逐次学習問題について検討する。
我々は,最適な安定マッチングを高い確率で効率的に同定することを目的とした,純粋な探索的視点を採用する。
本稿では,学習した部分的嗜好の構造を利用した削除基準に基づくアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 10.205814220900981
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We study a sequential learning problem for stable matchings in two-sided markets where preferences on both sides are initially unknown. We focus on a centralized setting where an algorithm matches agents at each time step and receives noisy rewards that reflect the preferences of the matched agents, following a semi-bandit feedback structure. We adopt a pure exploration perspective, aiming to efficiently identify the optimal stable matching with high probability. Our work extends prior results by handling \emph{two-sided uncertainty} and by exploiting \emph{partial preference} information. A central ingredient is the notion of \textbf{pervasive stable matching}, which enables the identification of optimal stable matchings under partial preferences. We propose elimination-based algorithms whose stopping criteria exploit the structure of the learned partial preferences, and provide a refined sample-complexity analysis. Beyond pure exploration, we extend our approach to regret minimization and establish regret bounds with respect to the \emph{optimal} stable matching that avoid dependence on the minimum reward gap $Δ_{\min}$.
- Abstract（参考訳）: 両面の嗜好が不明な二面市場における安定マッチングの逐次学習問題について検討する。
我々は,アルゴリズムが各タイミングでエージェントと一致し,一致したエージェントの好みを反映したノイズの多い報酬を受け取る,半帯域フィードバック構造に基づく集中的な設定に焦点を当てる。
我々は,最適安定マッチングを高い確率で効率的に同定することを目的とした,純粋な探索的視点を採用する。
本研究は,<emph{two-sided uncertainty} を扱い,<emph{partial preference} 情報を活用することによって先行結果を拡張した。
中心となる要素は \textbf{pervasive stable matching} の概念であり、これは部分的選好の下での最適な安定マッチングの同定を可能にする。
本稿では,学習した部分的嗜好の構造を利用した除去基準に基づくアルゴリズムを提案する。
純粋探索の他に、最小報酬ギャップ$Δ_{\min}$への依存を避けるため、後悔の最小化へのアプローチを拡張し、最小報酬ギャップ$Δ_{\min}$への依存を避けるような 'emph{optimal} 安定マッチングに関して後悔の限界を確立する。
関連論文リスト
- 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) - Probably Correct Optimal Stable Matching for Two-Sided Markets Under Uncertainty [5.250288418639076]
市場左側の好ましくない条件下での安定婚姻モデルの学習課題について考察する。
我々の目的は、左サイド最適である安定したマッチングを素早く識別することであり、バンドイットフィードバックによる純粋な探索問題である。
論文 参考訳（メタデータ） (2025-01-06T13:59:57Z) - Stable Matching with Ties: Approximation Ratios and Learning [34.58046942241621]
我々は、市場の片側で働く労働者が、彼らのマッチングユーティリティーによって決定された、仕事よりも好みに結びついている可能性がある、マッチング市場と結びつきについて研究する。
厳格な嗜好を持つ古典的な二面市場とは異なり、すべての労働者に対して実用性を最大化する単一の安定なマッチングは存在しない。
論文 参考訳（メタデータ） (2024-11-05T17:14:46Z) - Putting Gale & Shapley to Work: Guaranteeing Stability Through Learning [14.448192914855674]
両面のマッチング市場は、市場の片側からの参加者が好みに応じて反対側からの参加者と一致しなければならない、一連の問題を記述している。
我々は安定解の構造を利用して、安定解を見つける可能性を改善するアルゴリズムを考案する。
論文 参考訳（メタデータ） (2024-10-06T06:47:53Z) - Fully Stochastic Trust-Region Sequential Quadratic Programming for
Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。
アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文 参考訳（メタデータ） (2022-11-29T05:52:17Z) - Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。
私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
論文 参考訳（メタデータ） (2021-08-19T17:59:28Z) - High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。
そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
論文 参考訳（メタデータ） (2021-06-10T17:54:21Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。