論文の概要: Player-optimal Stable Regret for Bandit Learning in Matching Markets
- arxiv url: http://arxiv.org/abs/2307.10890v1
- Date: Thu, 20 Jul 2023 14:10:33 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-21 12:49:22.305237
- Title: Player-optimal Stable Regret for Bandit Learning in Matching Markets
- Title（参考訳）: 競争市場における帯域学習のためのプレイヤー最適安定レグレット
- Authors: Fang Kong, Shuai Li
- Abstract要約: ここでは、各プレイヤーの最適な安定な後悔は、$O(Klog T/Delta2)$、$K$は腕の数、$T$は地平線、$Delta$は、最初の$N+1$の腕の中でプレイヤーの最小の好みの差であることを示す。
我々の研究は、プレイヤー・ペシミカルの安定したマッチング目標がより弱かったり、特別な仮定を持った市場のみに適用されたりした以前の作品を大幅に改善する。
- 参考スコア（独自算出の注目度）: 12.54215178882448
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The problem of matching markets has been studied for a long time in the
literature due to its wide range of applications. Finding a stable matching is
a common equilibrium objective in this problem. Since market participants are
usually uncertain of their preferences, a rich line of recent works study the
online setting where one-side participants (players) learn their unknown
preferences from iterative interactions with the other side (arms). Most
previous works in this line are only able to derive theoretical guarantees for
player-pessimal stable regret, which is defined compared with the players'
least-preferred stable matching. However, under the pessimal stable matching,
players only obtain the least reward among all stable matchings. To maximize
players' profits, player-optimal stable matching would be the most desirable.
Though \citet{basu21beyond} successfully bring an upper bound for
player-optimal stable regret, their result can be exponentially large if
players' preference gap is small. Whether a polynomial guarantee for this
regret exists is a significant but still open problem. In this work, we provide
a new algorithm named explore-then-Gale-Shapley (ETGS) and show that the
optimal stable regret of each player can be upper bounded by $O(K\log
T/\Delta^2)$ where $K$ is the number of arms, $T$ is the horizon and $\Delta$
is the players' minimum preference gap among the first $N+1$-ranked arms. This
result significantly improves previous works which either have a weaker
player-pessimal stable matching objective or apply only to markets with special
assumptions. When the preferences of participants satisfy some special
conditions, our regret upper bound also matches the previously derived lower
bound.
- Abstract（参考訳）: 市場マッチングの問題は、その適用範囲が多岐にわたることから、長い間文献で研究されてきた。
安定マッチングを見つけることは、この問題における共通の均衡目標である。
市場参加者は通常自分の好みについて不確実であるため、最近のリッチな作品のラインは、一方の参加者(プレイヤー)が他方(腕)との反復的な相互作用から未知の好みを学ぶオンライン設定を研究している。
このシリーズの以前の作品の多くは、プレイヤーの最小予測の安定マッチングと比較して定義されるプレイヤー・ペシムの安定な後悔に対する理論的保証のみを導出することができる。
しかし、悲観的安定マッチングの下では、プレイヤーは全ての安定マッチングの中で最小の報酬しか得られない。
プレイヤーの利益を最大化するために、プレイヤー・オプティマイズ・マッチが最も望ましい。
\citet{basu21beyond} はプレイヤー最適の安定な後悔に対する上限をもたらすが、プレイヤーの好みの差が小さい場合には指数関数的に大きい。
この後悔に対する多項式保証が存在するかどうかは重要な問題であるが、まだ未解決の問題である。
本研究は,探索-テーマ-ゲイル-シャプリー (ETGS) という新しいアルゴリズムを提供し,各プレイヤーの最適な安定な後悔は,$O(K\log T/\Delta^2)$,$K$は武器数,$T$は地平線,$\Delta$は最初の$N+1$ランクのアーム間のプレイヤーの最小の選好ギャップであることを示す。
この結果は、より弱いプレイヤー・ペシムの安定的目標を持つか、特別な仮定を持つ市場のみに適用する以前の作品を大幅に改善する。
参加者の嗜好がいくつかの特別な条件を満たすとき、我々の後悔の上界も以前導出された下界と一致する。
関連論文リスト
- Improved Bandits in Many-to-one Matching Markets with Incentive Compatibility [12.05174711411919]
両面のマッチング市場は、そのリッチな応用のために、文献で広く研究されている。
まず,1対1設定のための既存のアルゴリズムをこのより一般的な設定に拡張し,プレイヤー最適後悔に対するほぼ最適境界を実現することを示す。
本稿では,アダプティブ・サーベイ・then-deferred (AETDA) アルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-01-03T03:45:35Z) - Competing Bandits in Time Varying Matching Markets [1.1470070927586014]
両面の非定常マッチング市場におけるオンライン学習の課題について検討し,安定したマッチングに収束することが目的である。
非定常性を扱うための単純な再起動戦略を組み合わせたRCB(Restart Competing Bandits)アルゴリズムを提案する。
提案アルゴリズムにより,各プレイヤーは,エージェントの嗜好の変動数に対して,$widetildemathcalO(L1/2_TT1/2)$の均一なサブ線形後悔を受けることを示す。
論文 参考訳（メタデータ） (2022-10-21T02:36:57Z) - Learning Correlated Equilibria in Mean-Field Games [62.14589406821103]
我々は平均場相関と粗相関平衡の概念を発展させる。
ゲームの構造に関する仮定を必要とせず,効率よくゲーム内で学習できることが示される。
論文 参考訳（メタデータ） (2022-08-22T08:31:46Z) - Can Reinforcement Learning Find Stackelberg-Nash Equilibria in
General-Sum Markov Games with Myopic Followers? [156.5760265539888]
我々は,マルチプレイヤーのジェネラルサムマルコフゲームについて,リーダーに指名されたプレイヤーとフォロワーに指名されたプレイヤーの1人を用いて研究した。
そのようなゲームに対して、我々のゴールは、政策対 $(pi*, nu*)$ であるスタックルバーグ・ナッシュ均衡 (SNE) を見つけることである。
オンラインとオフラインの両方でSNEを解くために,サンプル効率強化学習(RL)アルゴリズムを開発した。
論文 参考訳（メタデータ） (2021-12-27T05:41:14Z) - Learning Equilibria in Matching Markets from Bandit Feedback [139.29934476625488]
不確実性の下で安定した市場成果を学習するためのフレームワークとアルゴリズムを開発する。
私たちの研究は、大規模なデータ駆動の市場において、いつ、どのように安定したマッチングが生じるかを明らかにするための第一歩を踏み出します。
論文 参考訳（メタデータ） (2021-08-19T17:59:28Z) - Bandit Learning in Decentralized Matching Markets [82.39061186055775]
私たちは、一方の市場(プレーヤー)が他方の側(腕)の好みについて事前知識を持っていない両面マッチング市場を研究し、経験からその好みを学ぶ必要があります。
このモデルは、標準のマルチアームバンディットフレームワークを競合する分散型マルチプレイヤー設定に拡張します。
アームの選好が共有されるたびにアルゴリズムがインセンティブ互換であることが示されるが、選好が完全に一般的である場合には必ずしもそうではない。
論文 参考訳（メタデータ） (2020-12-14T08:58:07Z) - Multitask Bandit Learning Through Heterogeneous Feedback Aggregation [35.923544685900055]
我々は,この問題を,一組のプレイヤーが一組のアームと同時に相互作用する,$epsilon$-multi-player multi-armed bandit問題として定式化する。
我々は、異なるプレイヤーが収集した報酬を適応的に集約する高信頼な有界アルゴリズム、RobostAgg$(epsilon)$を開発する。
論文 参考訳（メタデータ） (2020-10-29T07:13:28Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳（メタデータ） (2020-08-10T08:30:52Z) - Learning Zero-Sum Simultaneous-Move Markov Games Using Function
Approximation and Correlated Equilibrium [116.56359444619441]
両プレイヤーのゼロサム有限ホライゾンマルコフゲームに対する効率の良い強化学習アルゴリズムを開発した。
オフライン環境では、両プレイヤーを制御し、双対性ギャップを最小化してナッシュ平衡を求める。
オンライン環境では、任意の相手と対戦する1人のプレイヤーを制御し、後悔を最小限に抑える。
論文 参考訳（メタデータ） (2020-02-17T17:04:16Z) - Selfish Robustness and Equilibria in Multi-Player Bandits [25.67398941667429]
ゲームでは、複数のプレイヤーが同時に腕を引いて、同じ腕を同時に引っ張る場合、0の報酬で衝突する。
プレイヤーが集団報酬を最大化する協力的ケースは、主に考慮されてきたが、悪意のあるプレイヤーにとっては非常に重要かつ困難な問題である。
代わりに、社会的福祉を犠牲にして、個人の報酬を最大化するインセンティブを持つより自然な利己的なプレイヤーについて検討する。
論文 参考訳（メタデータ） (2020-02-04T09:50:28Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。