論文の概要: Thompson Sampling for Bandit Learning in Matching Markets
- arxiv url: http://arxiv.org/abs/2204.12048v1
- Date: Tue, 26 Apr 2022 03:01:17 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-27 15:20:50.489024
- Title: Thompson Sampling for Bandit Learning in Matching Markets
- Title（参考訳）: 一致する市場でのバンディット学習のためのトンプソンサンプリング
- Authors: Fang Kong, Junming Yin, Shuai Li
- Abstract要約: トンプソンサンプリング(TS)もまた一般的な手法であり、実装が簡単で経験的性能が良く、多くの注目を集めている。
本稿では,新たな反復的マッチング市場におけるTSに対する最初の後悔分析について述べる。
- 参考スコア（独自算出の注目度）: 10.71976801619354
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The problem of two-sided matching markets has a wide range of real-world
applications and has been extensively studied in the literature. A line of
recent works have focused on the problem setting where the preferences of
one-side market participants are unknown \emph{a priori} and are learned by
iteratively interacting with the other side of participants. All these works
are based on explore-then-commit (ETC) and upper confidence bound (UCB)
algorithms, two common strategies in multi-armed bandits (MAB). Thompson
sampling (TS) is another popular approach, which attracts lots of attention due
to its easier implementation and better empirical performances. In many
problems, even when UCB and ETC-type algorithms have already been analyzed,
researchers are still trying to study TS for its benefits. However, the
convergence analysis of TS is much more challenging and remains open in many
problem settings. In this paper, we provide the first regret analysis for TS in
the new setting of iterative matching markets. Extensive experiments
demonstrate the practical advantages of the TS-type algorithm over the ETC and
UCB-type baselines.
- Abstract（参考訳）: 双方向マッチング市場の問題には、幅広い実世界の応用があり、文献で広く研究されている。
最近の一連の研究では、一方の市場参加者の好みが不明な問題設定に焦点が当てられ、他方の参加者と反復的に相互作用することで学習されている。
これらの研究はすべて、マルチアーム・バンディット(MAB)における2つの共通戦略である、探索-then-commit(ETC)と上信頼境界(UCB)アルゴリズムに基づいている。
トンプソンサンプリング(TS)もまた一般的な手法であり、実装が簡単で経験的性能が良く、多くの注目を集めている。
多くの問題において、UTBとETC型アルゴリズムが既に分析されているとしても、研究者はTSの利点について研究している。
しかし、TSの収束解析はより困難であり、多くの問題設定では未解決のままである。
本稿では,新たな反復的マッチング市場におけるTSに対する最初の後悔分析について述べる。
大規模な実験は、ETCおよびUTB型ベースラインに対するTS型アルゴリズムの実用的利点を示す。
関連論文リスト
- Robustness Assessment of Mathematical Reasoning in the Presence of Missing and Contradictory Conditions [48.251724997889184]
我々は、ミス・コントラクタリー条件(PMC)に関する問題というベンチマークを開発する。
本稿では,これらのシナリオにおける数ショットプロンプト手法の性能を評価するための2つの新しい指標を提案する。
SMT-LIB Prompting (SLP) と呼ばれる,SMT-LIB言語を用いて直接解決する代わりに,この問題をモデル化する手法を提案する。
論文 参考訳（メタデータ） (2024-06-07T16:24:12Z) - 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) - On Pitfalls of Test-Time Adaptation [82.8392232222119]
TTA(Test-Time Adaptation)は、分散シフトの下で堅牢性に取り組むための有望なアプローチとして登場した。
TTABは,10の最先端アルゴリズム,多種多様な分散シフト,および2つの評価プロトコルを含むテスト時間適応ベンチマークである。
論文 参考訳（メタデータ） (2023-06-06T09:35:29Z) - A Gold Standard Dataset for the Reviewer Assignment Problem [117.59690218507565]
類似度スコア(Similarity score)とは、論文のレビューにおいて、レビュアーの専門知識を数値で見積もるものである。
私たちのデータセットは、58人の研究者による477の自己申告された専門知識スコアで構成されています。
2つの論文をレビュアーに関連付けるタスクは、簡単なケースでは12%～30%、ハードケースでは36%～43%である。
論文 参考訳（メタデータ） (2023-03-23T16:15:03Z) - Two-sided Competing Matching Recommendation Markets With Quota and Complementary Preferences Constraints [13.069703665055084]
本稿では,両面のオンラインマッチング市場において,補完的な嗜好とクォータ制約を伴う問題に対処する新しい推奨アルゴリズムを提案する。
混合クォータと相補的な選好制約の存在は、マッチングプロセスの不安定性を引き起こす。
バンドレート学習の枠組みとしてこの問題を定式化し,マルチエージェント多型トンプソンサンプリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-24T18:54:29Z) - Thompson Sampling for Robust Transfer in Multi-Task Bandits [36.82266781427533]
本研究では,オンラインマルチタスク学習における課題について検討する。
我々は、より一般的なオンラインマルチタスク学習プロトコルのためのトンプソンサンプリング(TS)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-17T05:28:01Z) - Meta-Thompson Sampling [35.98471817519713]
本稿では、未知の事前分布から引き出された問題インスタンスと相互作用し、よりよく探索することを学ぶトンプソンサンプリングの変種を提案する。
我々のアルゴリズムは前者をメタ学習し、メタTSと呼ぶ。
論文 参考訳（メタデータ） (2021-02-11T17:07:25Z) - Combinatorial Pure Exploration with Full-bandit Feedback and Beyond:
Solving Combinatorial Optimization under Uncertainty with Limited Observation [70.41056265629815]
最適化アルゴリズムを開発する際、エッジウェイトなどのパラメータが入力として正確に知られていることが一般的である。
本稿では、最近、限られたフィードバックを伴う純粋探索問題に対する手法について概説する。
論文 参考訳（メタデータ） (2020-12-31T12:40:52Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z) - Double Explore-then-Commit: Asymptotic Optimality and Beyond [101.77632893858063]
ガウス級報酬を用いたマルチアームバンディット問題について検討する。
本研究では,探索-then-commit (ETC) アルゴリズムの変種により,マルチアームバンディット問題に対する最適性が得られることを示す。
論文 参考訳（メタデータ） (2020-02-21T08:07:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。