論文の概要: Improved Bandits in Many-to-one Matching Markets with Incentive
Compatibility
- arxiv url: http://arxiv.org/abs/2401.01528v1
- Date: Wed, 3 Jan 2024 03:45:35 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-04 15:24:45.895889
- Title: Improved Bandits in Many-to-one Matching Markets with Incentive
Compatibility
- Title(参考訳): インセンティブ互換性のある多対一マッチング市場におけるバンディットの改善
- Authors: Fang Kong, Shuai Li
- Abstract要約: 両面のマッチング市場は、そのリッチな応用のために、文献で広く研究されている。
本稿では,インセンティブの整合性を確保しつつ,多国間市場における後悔感を高めることを目的とする。
我々は、オンラインDA(ODA)アルゴリズムを考案し、この設定に対して$O(NKlog T/Delta2)$ player-pessimal stable regret boundを定めている。
- 参考スコア(独自算出の注目度): 14.237542701166037
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Two-sided matching markets have been widely studied in the literature due to
their rich applications. Since participants are usually uncertain about their
preferences, online algorithms have recently been adopted to learn them through
iterative interactions. \citet{wang2022bandit} initiate the study of this
problem in a many-to-one setting with \textit{responsiveness}. However, their
results are far from optimal and lack guarantees of incentive compatibility. An
extension of \citet{kong2023player} to this more general setting achieves a
near-optimal bound for player-optimal regret. Nevertheless, due to the
substantial requirement for collaboration, a single player's deviation could
lead to a huge increase in its own cumulative rewards and an $O(T)$ regret for
others. In this paper, we aim to enhance the regret bound in many-to-one
markets while ensuring incentive compatibility. We first propose the adaptively
explore-then-deferred-acceptance (AETDA) algorithm for responsiveness setting
and derive an $O(N\min\left\{N,K\right\}C\log T/\Delta^2)$ upper bound for
player-optimal stable regret while demonstrating its guarantee of incentive
compatibility, where $N$ represents the number of players, $K$ is the number of
arms, $T$ denotes the time horizon, $C$ is arms' total capacities and $\Delta$
signifies the minimum preference gap among players. This result is a
significant improvement over \citet{wang2022bandit}. And to the best of our
knowledge, it constitutes the first player-optimal guarantee in matching
markets that offers such robust assurances. We also consider broader
\textit{substitutable} preferences, one of the most general conditions to
ensure the existence of a stable matching and cover responsiveness. We devise
an online DA (ODA) algorithm and establish an $O(NK\log T/\Delta^2)$
player-pessimal stable regret bound for this setting.
- Abstract(参考訳): 両面のマッチング市場は、リッチな応用のために文献で広く研究されている。
参加者は通常、好みについて不確実であるため、最近は反復的な相互作用を通じて学習するためにオンラインアルゴリズムが採用されている。
\citet{wang2022bandit} は \textit{responsiveness} を持つ多対一の設定でこの問題の研究を開始する。
しかし、彼らの結果は最適ではなく、インセンティブの互換性の保証がない。
より一般的な設定への \citet{kong2023player} の拡張は、プレイヤー-最適後悔に対するほぼ最適境界を達成する。
それでも、コラボレーションのかなりの要件のため、シングルプレーヤーの偏差は、自身の累積報酬の大幅な増加と、他者への後悔の意を表す$O(T)$である。
本稿では,インセンティブ互換性を確保しつつ,多対一市場における後悔感を高めることを目的とする。
最初に、応答性設定のための適応的に探索する-then-deferred-acceptance (aetda) アルゴリズムを提案し、プレイヤー-オプティカルな後悔の上限として$o(n\min\left\{n,k\right\}c\log t/\delta^2)$を導出し、インセンティブ互換性の保証を示す一方で、$n$はプレイヤーの数を表し、$k$はアームの数、$t$は時刻の地平線を表し、$c$はアームの総容量、$\delta$はプレイヤー間の最小の好みギャップを示す。
この結果は \citet{wang2022bandit} を大幅に改善した。
そして、私たちの知る限りでは、このような堅牢な保証を提供するマッチングマーケットにおける、最初のプレイヤー最適保証を構成する。
また、より広範な \textit{substitutable} の選好についても検討し、安定なマッチングとカバー応答性を保証するための最も一般的な条件の1つである。
オンラインDA(ODA)アルゴリズムを考案し,$O(NK\log T/\Delta^2)$ player-pessimal stable regret bound for this set。
関連論文リスト
- Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [56.457634640638254]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳(メタデータ) (2023-10-02T08:15:52Z) - Player-optimal Stable Regret for Bandit Learning in Matching Markets [12.54215178882448]
ここでは、各プレイヤーの最適な安定な後悔は、$O(Klog T/Delta2)$、$K$は腕の数、$T$は地平線、$Delta$は、最初の$N+1$の腕の中でプレイヤーの最小の好みの差であることを示す。
我々の研究は、プレイヤー・ペシミカルの安定したマッチング目標がより弱かったり、特別な仮定を持った市場のみに適用されたりした以前の作品を大幅に改善する。
論文 参考訳(メタデータ) (2023-07-20T14:10:33Z) - Provably Efficient Generalized Lagrangian Policy Optimization for Safe
Multi-Agent Reinforcement Learning [105.7510838453122]
制約付きマルコフゲームを用いたオンライン安全なマルチエージェント強化学習について検討する。
我々は,このラグランジアン問題を解くための高信頼強化学習アルゴリズムを開発した。
提案アルゴリズムは,オンラインミラー降下によるミニマックス決定主元変数と,投影勾配ステップによる双対変数を更新する。
論文 参考訳(メタデータ) (2023-05-31T22:09:24Z) - Constant or logarithmic regret in asynchronous multiplayer bandits [22.376992460581594]
マルチプレイヤーのバンディット問題は、まず探索-then-commit (ETC)アルゴリズムで取り組んだ。
最適ポリシーが各アームに少なくとも1人のプレイヤーを割り当てる場合、常にインスタンス依存の後悔をもたらすアルゴリズムであるCautious Greedyを導入する。
論文 参考訳(メタデータ) (2023-05-31T09:35:03Z) - Competing Bandits in Time Varying Matching Markets [1.1470070927586014]
両面の非定常マッチング市場におけるオンライン学習の課題について検討し,安定したマッチングに収束することが目的である。
非定常性を扱うための単純な再起動戦略を組み合わせたRCB(Restart Competing Bandits)アルゴリズムを提案する。
提案アルゴリズムにより,各プレイヤーは,エージェントの嗜好の変動数に対して,$widetildemathcalO(L1/2_TT1/2)$の均一なサブ線形後悔を受けることを示す。
論文 参考訳(メタデータ) (2022-10-21T02:36:57Z) - Provably Efficient Fictitious Play Policy Optimization for Zero-Sum
Markov Games with Structured Transitions [145.54544979467872]
本研究では,ゼロサムマルコフゲームに対して,構造的だが未知の遷移を伴う架空のプレイポリシー最適化アルゴリズムを提案し,解析する。
我々は、2年制の競争ゲームシナリオで、$K$のエピソードに続き、$widetildemathcalO(sqrtK)$ regret boundsを証明した。
提案アルゴリズムは,アッパー信頼境界(UCB)型最適化と,同時政策最適化の範囲内での架空のプレイの組み合わせを特徴とする。
論文 参考訳(メタデータ) (2022-07-25T18:29:16Z) - The Pareto Frontier of Instance-Dependent Guarantees in Multi-Player
Multi-Armed Bandits with no Communication [10.446001329147112]
マルチプレイヤーのマルチアームバンディット問題について検討する。
この問題では、$m$プレーヤーは、合計報酬を$K > m$アームから最大化するために協力する。
ここで$Delta$は$m$-thと$m+1$-stのベストアームのギャップである。
論文 参考訳(メタデータ) (2022-02-19T18:19:36Z) - Bandit Learning in Decentralized Matching Markets [82.39061186055775]
私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。
このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。
アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
論文 参考訳(メタデータ) (2020-12-14T08:58:07Z) - Is Reinforcement Learning More Difficult Than Bandits? A Near-optimal
Algorithm Escaping the Curse of Horizon [88.75843804630772]
エピソード強化学習は文脈的包帯を一般化する。
長期計画の地平線と未知の状態依存的な遷移は、サンプルの複雑さに若干の困難をもたらす。
MVPは$left(sqrtSAK + S2Aright)$ regretを楽しみ、$Omegaleft(sqrtSAK + S2Aright)$ lower bound of emphcontextual bandits to logarithmic termsに近づいている。
論文 参考訳(メタデータ) (2020-09-28T17:52:32Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳(メタデータ) (2020-08-10T08:30:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。