論文の概要: Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints
- arxiv url: http://arxiv.org/abs/2301.10230v3
- Date: Wed, 29 May 2024 00:13:05 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-31 02:41:05.674569
- Title: Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints
- Title（参考訳）: Quota と Complementary Preferences Constraint による両面競合型マッチング推奨市場
- Authors: Yuantong Li, Guang Cheng, Xiaowu Dai,
- Abstract要約: 本稿では,両面のオンラインマッチング市場において,補完的な嗜好とクォータ制約を伴う問題に対処する新しい推奨アルゴリズムを提案する。
混合クォータと相補的な選好制約の存在は、マッチングプロセスの不安定性を引き起こす。
バンドレート学習の枠組みとしてこの問題を定式化し,マルチエージェント多型トンプソンサンプリングアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 13.069703665055084
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a new recommendation algorithm for addressing the problem of two-sided online matching markets with complementary preferences and quota constraints, where agents' preferences are unknown a priori and must be learned from data. The presence of mixed quota and complementary preferences constraints can lead to instability in the matching process, making this problem challenging to solve. To overcome this challenge, we formulate the problem as a bandit learning framework and propose the Multi-agent Multi-type Thompson Sampling (MMTS) algorithm. The algorithm combines the strengths of Thompson Sampling for exploration with a new double matching technique to provide a stable matching outcome. Our theoretical analysis demonstrates the effectiveness of MMTS as it can achieve stability and has a total $\widetilde{\mathcal{O}}(Q{\sqrt{K_{\max}T}})$-Bayesian regret with high probability, which exhibits linearity with respect to the total firm's quota $Q$, the square root of the maximum size of available type workers $\sqrt{K_{\max}}$ and time horizon $T$. In addition, simulation studies also demonstrate MMTS's effectiveness in various settings. We provide code used in our experiments \url{https://github.com/Likelyt/Double-Matching}.
- Abstract（参考訳）: 本稿では,エージェントの嗜好が未知であり,データから学習しなければならないような,相補的な嗜好とクォータ制約を伴う双方向のオンラインマッチング市場の課題に対処する,新たなレコメンデーションアルゴリズムを提案する。
混合クォータと相補的な選好制約の存在は、マッチングプロセスの不安定性を招き、この問題を解決するのが難しくなる。
この課題を克服するために、バンドレート学習フレームワークとして問題を定式化し、マルチエージェントマルチタイプトンプソンサンプリング(MMTS)アルゴリズムを提案する。
このアルゴリズムは、トンプソンサンプリングの強度と新しい二重マッチング手法を組み合わせて、安定したマッチング結果を提供する。
我々の理論的分析は、MMTSが安定性を達成できることを示すものであり、全会社のクォータ$Q$、利用可能なタイプワーカーの最大サイズの平方根である$\sqrt{K_{\max}T}}とタイムホライズン$T$に対して線形性を示す高い確率で、合計$\widetilde{\mathcal{O}}(Q{\sqrt{K_{\max}T}})$-Bayesian regretを持つ。
さらに,様々な環境下でのMMTSの有効性についてもシミュレーション研究を行った。
実験で使われたコードを提供しています。
関連論文リスト
- Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - 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) - Multi-Agent Bayesian Optimization with Coupled Black-Box and Affine
Constraints [21.38692458445459]
ブラックボックス制約と既知のアフィン制約を結合した分散マルチエージェントベイズ最適化の問題について検討する。
単一エージェントの場合と同様の後悔/違反境界を実現するアルゴリズムが提案されている。
論文 参考訳（メタデータ） (2023-10-02T08:07:36Z) - Langevin Thompson Sampling with Logarithmic Communication: Bandits and
Reinforcement Learning [34.4255062106615]
トンプソンサンプリング(TS)は、使用が容易で、経験的性能に訴えるため、シーケンシャルな意思決定に広く用いられている。
バッチ化された$textitLangevin Thompson Sampling$アルゴリズムを提案する。
アルゴリズムは計算効率が高く,MABでは$mathcalO(log T)$,RLでは$mathcalO(sqrtT)$と同じオーダー最適後悔保証を維持している。
論文 参考訳（メタデータ） (2023-06-15T01:16:29Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Optimal and Efficient Dynamic Regret Algorithms for Non-Stationary
Dueling Bandits [27.279654173896372]
我々は,非定常的あるいは時間的に異なる選好の下で,$K$のDueling Banditsにおける空力的後悔の最小化問題について検討した。
これは、エージェントが各ラウンドで一対のアイテムを選択し、このペアに対する相対的な二項のウィンロスフィードバックのみを観察するオンライン学習設定である。
論文 参考訳（メタデータ） (2021-11-06T16:46:55Z) - Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。
エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文 参考訳（メタデータ） (2021-06-05T09:16:28Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳（メタデータ） (2020-09-04T04:10:39Z) - Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal
Sample Complexity [67.02490430380415]
モデルに基づくMARLは、Nash平衡値(NE)を求めるために$tilde O(|S||B|(gamma)-3epsilon-2)$のサンプル複雑性を実現する。
また、アルゴリズムが報酬に依存しない場合、そのようなサンプル境界は最小値(対数因子まで)であり、アルゴリズムは報酬知識のない遷移サンプルを問合せする。
論文 参考訳（メタデータ） (2020-07-15T03:25:24Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。