論文の概要: Double Matching Under Complementary Preferences
- arxiv url: http://arxiv.org/abs/2301.10230v1
- Date: Tue, 24 Jan 2023 18:54:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-25 12:41:17.227512
- Title: Double Matching Under Complementary Preferences
- Title(参考訳): 相補的選好下での二重マッチング
- Authors: Yuantong Li, Guang Cheng, Xiaowu Dai
- Abstract要約: 本稿では,市場を補完的な選好でマッチングする問題に対処する新しいアルゴリズムを提案する。
相補的な選好の存在は、マッチングプロセスにおける不安定をもたらす可能性がある。
このアルゴリズムは、トンプソンサンプリングの強度を二重マッチング手法と組み合わせて、安定したマッチング結果を得る。
- 参考スコア(独自算出の注目度): 18.03464967426957
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a new algorithm for addressing the problem of
matching markets with complementary preferences, where agents' preferences are
unknown a priori and must be learned from data. The presence of complementary
preferences 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 double matching technique to achieve a
stable matching outcome. Our theoretical analysis demonstrates the
effectiveness of MMTS as it is able to achieve stability at every matching
step, satisfies the incentive-compatibility property, and has a sublinear
Bayesian regret over time. Our approach provides a useful method for addressing
complementary preferences in real-world scenarios.
- Abstract(参考訳): 本稿では,エージェントの嗜好が未知であり,データから学ばなければならない市場と相補的な選好とのマッチング問題に対処する新しいアルゴリズムを提案する。
相補的な選好が存在するとマッチングプロセスが不安定になり、この問題を解くのが難しくなる。
この課題を克服するために、バンドレート学習フレームワークとして問題を定式化し、マルチエージェントマルチタイプトンプソンサンプリング(MMTS)アルゴリズムを提案する。
このアルゴリズムは、トンプソンサンプリングの強度を二重マッチング手法と組み合わせ、安定したマッチング結果を得る。
理論的解析により,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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。